We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under matroid constraints and two generalizations: p-extendible system and independence system constraints. The objective is to find fair and efficient allocations in which the subset of items assigned to every agent satisfies the given constraint. We focus on a common fairness notion of envy-freeness up to one item (EF1) and a well-known efficient (and fair) notion of the maximum Nash social welfare (Max-NSW). By using properties of matroids, we demonstrate that the Max-NSW allocation, implying Pareto optimality (PO), achieves a tight 1/2-EF1 under matroid constraints. This result resolves an open question proposed in prior literature [26]. In particular, if agents have 2-valued ( \(\{1, a\}\) ) valuations, we prove that the Max-NSW allocation admits \(\max \{1/a^2, 1/2\}\) -EF1 and PO. Under strongly p-extendible system constraints, we show that the Max-NSW allocation guarantees \(\max \{1/p, 1/4\}\) -EF1 and PO for identical binary valuations. Indeed, the approximation of 1/4 is the ratio for independence system constraints and additive valuations. Additionally, for lexicographic preferences, we study possibly feasible allocations other than Max-NSW admitting exactly EF1 and PO under the above constraints.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Fairness of Maximum Nash Social Welfare Under Matroid Constraints and Beyond

  • Yuanyuan Wang,
  • Xin Chen,
  • Qingqin Nong

摘要

We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under matroid constraints and two generalizations: p-extendible system and independence system constraints. The objective is to find fair and efficient allocations in which the subset of items assigned to every agent satisfies the given constraint. We focus on a common fairness notion of envy-freeness up to one item (EF1) and a well-known efficient (and fair) notion of the maximum Nash social welfare (Max-NSW). By using properties of matroids, we demonstrate that the Max-NSW allocation, implying Pareto optimality (PO), achieves a tight 1/2-EF1 under matroid constraints. This result resolves an open question proposed in prior literature [26]. In particular, if agents have 2-valued ( \(\{1, a\}\) ) valuations, we prove that the Max-NSW allocation admits \(\max \{1/a^2, 1/2\}\) -EF1 and PO. Under strongly p-extendible system constraints, we show that the Max-NSW allocation guarantees \(\max \{1/p, 1/4\}\) -EF1 and PO for identical binary valuations. Indeed, the approximation of 1/4 is the ratio for independence system constraints and additive valuations. Additionally, for lexicographic preferences, we study possibly feasible allocations other than Max-NSW admitting exactly EF1 and PO under the above constraints.