LIPIcs.FSTTCS.2018.25.pdf
- Filesize: 0.57 MB
- 17 pages
Document
On Fair Division for Indivisible Items
Authors
-
Part of:
Volume:
38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-12-05
Cite As Get BibTex
Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. On Fair Division for Indivisible Items. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.25
Abstract
We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric mean of the utilities of the agents. Each good comes in multiple items or copies, and the utility of an agent diminishes as it receives more items of the same good. The utility of a bundle of items for an agent is the sum of the utilities of the items in the bundle. Each agent has a utility cap beyond which he does not value additional items. We give a polynomial time approximation algorithm that maximizes Nash social welfare up to a factor of e^{1/{e}} ~~ 1.445. The computed allocation is Pareto-optimal and approximates envy-freeness up to one item up to a factor of 2 + epsilon.
Subject Classification
ACM Subject Classification
- Theory of computation → Approximation algorithms analysis
Keywords
- Fair Division
- Indivisible Goods
- Envy-Free
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In ITCS, pages 36:1-36:12, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.36.
- Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V. Vazirani. Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. In SODA, pages 2274-2290, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.147.
- Siddharth Barman, Sanath Kumar Krishna Murthy, and Rohit Vaish. Finding Fair and Efficient Allocations. CoRR, abs/1707.04731, 2017. to appear in EC 2018. URL: http://arxiv.org/abs/1707.04731.
- Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare. In EC, pages 305-322, 2016. URL: http://dx.doi.org/10.1145/2940716.2940726.
- Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, and Sadra Yazdanbod. Convex Program Duality, Fisher Markets, and Nash Social Welfare. In EC, pages 459-460, 2017. URL: http://dx.doi.org/10.1145/3033274.3085109.
- Richard Cole and Vasilis Gkatzelis. Approximating the Nash Social Welfare with Indivisible Items. In STOC, pages 371-380, 2015. URL: http://dx.doi.org/10.1145/2746539.2746589.
-
J. Edmonds and R.M. Karp. Theoretical Improvements in algorithmic efficiency for network flow problems. J. ACM, 19:248-264, 1972.
-
E. Eisenberg and D. Gale. Consensus of subjective probabilities: The Pari-Mutuel method. The Annals Math. Statist., 30:165-168, 1959.
- Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Approximating the Nash Social Welfare with Budget-Additive Valuations. . In SODA 2018, pages 2326-2340, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.150.
- Euiwoong Lee. APX-hardness of maximizing Nash social welfare with indivisible items. Inf. Process. Lett., 122:17-20, 2017. URL: http://dx.doi.org/10.1016/j.ipl.2017.01.012.
- R.M. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer. Certifying algorithms. . Computer Science Review, 5(2):119-161, 2011. URL: http://dx.doi.org/10.1016/j.cosrev.2010.09.009.
-
Hervé Moulin. Fair division and collective welfare. MIT Press, 2003.
-
J. Nash. The Bargaining Problem. Econometrica, 18:155-162, 1950.
- Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, and Jörg Rothe. Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Autonomous Agents and Multi-Agent Systems, 28(2):256-289, 2014. URL: http://dx.doi.org/10.1007/s10458-013-9224-2.