TY - JOUR
T1 - Fair Division of Indivisible Goods for a Class of Concave Valuations
AU - Chaudhury, Bhaskar Ray
AU - Cheung, Yun Kuen
AU - Garg, Jugal
AU - Garg, Naveen
AU - Hoefer, Martin
AU - Mehlhorn, Kurt
N1 - We thank the reviewers and the associate editor for their thorough reviews and comments. We thank Hannaneh Akrami for a careful reading of the paper. Jugal Garg was supported by NSF grant CCF-1942321 (CAREER). Martin Hoefer acknowledges financial support by DFG grant Ho 3831/5-1.
PY - 2022
Y1 - 2022
N2 - We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the well-studied case of additive valuations. We present a polynomial-time algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the state-of-the-art approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envy-freeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Pareto-optimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value.
AB - We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the well-studied case of additive valuations. We present a polynomial-time algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the state-of-the-art approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envy-freeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Pareto-optimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value.
UR - http://www.scopus.com/inward/record.url?scp=85132012327&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85132012327&partnerID=8YFLogxK
U2 - 10.1613/jair.1.12911
DO - 10.1613/jair.1.12911
M3 - Article
AN - SCOPUS:85132012327
SN - 1076-9757
VL - 74
SP - 111
EP - 142
JO - Journal of Artificial Intelligence Research
JF - Journal of Artificial Intelligence Research
ER -