Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3391403.3399511acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article
Open access

EFX Exists for Three Agents

Published: 13 July 2020 Publication History

Abstract

We study the problem of distributing a set of indivisible items among agents with additive valuations in a fairmanner. The fairness notion under consideration is Envy-freeness up to anyitem (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al.[9] by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.

References

[1]
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. 2017. Approximation algorithms for computing maximum share allocations. ACM Transactions on Algorithms, Vol. 13, 4 (2017), 52:1--52:28.
[2]
Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. 2017. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS). 1--12.
[3]
Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V. Vazirani. 2018. Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. In Proceedings of the 29th Symposium on Discrete Algorithms (SODA). 2274--2290.
[4]
Siddharth Barman and Sanath Kumar Krishnamurthy. 2017. Approximation algorithms for maximin fair division. In Proceedings of the 18th ACM Conference on Economics and Computation (EC). 647--664.
[5]
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. 2018. Finding Fair and Efficient Allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC). 557--574.
[6]
Sylvain Bouveret and Michel Lemaître. 2016. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. In Autonomous Agents and Multi-Agent Systems (AAMAS) 30, 2. 259--290.
[7]
Eric Budish. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, Vol. 119, 6 (2011), 1061--1103.
[8]
Eric Budish, Gé rard P. Cachon, Judd B. Kessler, and Abraham Othman. 2017. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation. Operations Research, Vol. 65, 2 (2017), 314--336.
[9]
Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019. Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the 20th ACM Conference on Economics and Computation (EC). 527--545.
[10]
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2016. The Unreasonable Fairness of Maximum Nash Welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (EC). 305--322.
[11]
Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. 2018. On Fair Division for Indivisible Items. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS. 25:1--25:17.
[12]
Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. 2020 a. EFX Exists for Three Agents. CoRR, Vol. Abs/2002.05119 (2020).
[13]
Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. 2020 b. A Little Charity Guarantees Almost Envy-Freeness. In Proceedings of the 31st Symposium on Discrete Algorithms (SODA). 2658--2672.
[14]
Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay Vazirani, and Sadra Yazdanbod. 2017. Convex Program Duality, Fisher Markets, and Nash Social Welfare. In Proc. 18th Conf. Economics and Computation (EC).
[15]
Richard Cole and Vasilis Gkatzelis. 2018. Approximating the Nash Social Welfare with Indivisible Items. SIAM J. Comput., Vol. 47, 3 (2018), 1211--1236.
[16]
Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. 2018. Approximating the Nash Social Welfare with Budget-Additive Valuations. In Proceedings of the 29th Symposium on Discrete Algorithms (SODA). 2326--2340.
[17]
Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. 2020. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. In Proceedings of the 31st Symposium on Discrete Algorithms (SODA). 2673--2687.
[18]
Jugal Garg and Peter McGlaughlin. 2019. Improving Nash Social Welfare Approximations. In IJCAI. ijcai.org, 294--300.
[19]
Jugal Garg, Peter McGlaughlin, and Setareh Taki. 2019. Approximating Maximin Share Allocations. In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA), Vol. 69. 20:1--20:11.
[20]
Jugal Garg and Setareh Taki. 2019. An Improved Approximation Algorithm for Maximin Shares. CoRR, Vol. Abs/1903.00029 (2019).
[21]
Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. 2018. Fair Allocation of Indivisible Goods: Improvements and Generalizations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC) . 539--556.
[22]
Jonathan R. Goldman and Ariel D. Procaccia. 2014. Spliddit: unleashing fair division algorithms. In SIGecom Exchanges 13(2). 41--46.
[23]
David Kurokawa, Ariel D. Procaccia, and Nisarg Shah. 2018a. Leximin Allocations in the Real World. ACM Trans. Economics and Comput., Vol. 6, 3--4 (2018), 11:1--11:24.
[24]
David Kurokawa, Ariel D. Procaccia, and Junxing Wang. 2018b. Fair enough: Guaranteeing approximate maximin shares. Journal of ACM, Vol. 65, 2 (2018), 8:1--27.
[25]
Euiwoong Lee. 2017. APX-hardness of Maximizing Nash Social Welfare with Indivisible Items. Inf. Process. Lett., Vol. 122 (2017), 17--20.
[26]
Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC). 125--131.
[27]
Benjamin Plaut and Tim Roughgarden. 2018. Almost Envy-Freeness with General Valuations. In Proceedings of the 29th Symposium on Discrete Algorithms (SODA). 2584--2603.
[28]
Hugo Steinhaus. 1948. The Problem of Fair Division. Econometrica, Vol. 16, 1 (1948), 101--104.

Cited By

View all
  • (2024)A Complete Landscape for the Price of Envy-FreenessProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662975(1183-1191)Online publication date: 6-May-2024
  • (2024)On the Complexity of Pareto-Optimal and Envy-Free LotteriesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662872(244-252)Online publication date: 6-May-2024
  • (2024)Parameterized Guarantees for Almost Envy-Free AllocationsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662862(151-159)Online publication date: 6-May-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation
July 2020
937 pages
ISBN:9781450379755
DOI:10.1145/3391403
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2020

Permissions

Request permissions for this article.

Check for updates

Badges

  • Best Student Paper

Author Tags

  1. EFX allocations
  2. discrete fair division
  3. nash welfare

Qualifiers

  • Research-article

Funding Sources

  • NSF

Conference

EC '20
Sponsor:
EC '20: The 21st ACM Conference on Economics and Computation
July 13 - 17, 2020
Virtual Event, Hungary

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)284
  • Downloads (Last 6 weeks)36
Reflects downloads up to 09 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)A Complete Landscape for the Price of Envy-FreenessProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662975(1183-1191)Online publication date: 6-May-2024
  • (2024)On the Complexity of Pareto-Optimal and Envy-Free LotteriesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662872(244-252)Online publication date: 6-May-2024
  • (2024)Parameterized Guarantees for Almost Envy-Free AllocationsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662862(151-159)Online publication date: 6-May-2024
  • (2024)Maximum Nash Social Welfare Under Budget-Feasible EFXIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.333210411:2(1810-1820)Online publication date: Mar-2024
  • (2024)Envy-free Relaxations for Goods, Chores, and Mixed ItemsTheoretical Computer Science10.1016/j.tcs.2024.114596(114596)Online publication date: Apr-2024
  • (2024)The existence and efficiency of PMMS allocationsTheoretical Computer Science10.1016/j.tcs.2024.114388989:COnline publication date: 21-Mar-2024
  • (2024)Almost Proportional Allocations of Indivisible Chores: Computation, Approximation and EfficiencyArtificial Intelligence10.1016/j.artint.2024.104118(104118)Online publication date: Mar-2024
  • (2024)Approximately EFX allocations for indivisible choresArtificial Intelligence10.1016/j.artint.2023.104037326(104037)Online publication date: Jan-2024
  • (2024)Algorithms for Future Mobility SocietyAdvanced Mathematical Science for Mobility Society10.1007/978-981-99-9772-5_9(173-185)Online publication date: 14-Mar-2024
  • (2024)Envy-Free and Efficient Allocations for Graphical ValuationsAlgorithmic Decision Theory10.1007/978-3-031-73903-3_17(258-272)Online publication date: 16-Oct-2024
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media