Document Open Access Logo

Extension of Additive Valuations to General Valuations on the Existence of EFX

Author Ryoga Mahara

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.66.pdf
  • Filesize: 0.7 MB
  • 15 pages

Document Identifiers

Author Details

Ryoga Mahara
  • Research Institute for Mathematical Sciences, Kyoto University, Japan

Acknowledgements

The author would like to thank Yusuke Kobayashi for his generous support and useful discussion. This work was partially supported by the joint project of Kyoto University and Toyota Motor Corporation, titled "Advanced Mathematical Science for Mobility Society".

Cite AsGet BibTex

Ryoga Mahara. Extension of Additive Valuations to General Valuations on the Existence of EFX. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.66

Abstract

Envy-freeness is one of the most widely studied notions in fair division. Since envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling concept is envy-freeness up to any item (EFX). We study the existence of EFX allocations for general valuations. The existence of EFX allocations is a major open problem. For general valuations, it is known that an EFX allocation always exists (i) when n = 2 or (ii) when all agents have identical valuations, where n is the number of agents. it is also known that an EFX allocation always exists when one can leave at most n-1 items unallocated. We develop new techniques and extend some results of additive valuations to general valuations on the existence of EFX allocations. We show that an EFX allocation always exists (i) when all agents have one of two general valuations or (ii) when the number of items is at most n+3. We also show that an EFX allocation always exists when one can leave at most n-2 items unallocated. In addition to the positive results, we construct an instance with n = 3 in which an existing approach does not work as it is.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Discrete Fair Division
  • EFX allocations
  • General Valuations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A Voudouris. Maximum Nash welfare and other stories about efx. Theoretical Computer Science, 863:69-85, 2021. Google Scholar
  2. Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms (TALG), 13(4):1-28, 2017. Google Scholar
  3. Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Computer Science, 841:94-109, 2020. Google Scholar
  4. Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V Vazirani. Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2274-2290, 2018. Google Scholar
  5. Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash social welfare, matrix permanent, and stable polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS), pages 1-12, 2017. Google Scholar
  6. Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation algorithms for maximin fair division. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 647-664, 2017. Google Scholar
  7. Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557-574, 2018. Google Scholar
  8. Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. (almost full) EFX exists for four agents (and beyond). arXiv preprint arXiv:2102.10654, 2021. Google Scholar
  9. Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost envy-free allocations with connected bundles. In 9th Innovations in Theoretical Computer Science Conference (ITCS), pages 305-322, 2018. Google Scholar
  10. Sylvain Bouveret and Michel Lemaître. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2):259-290, 2016. Google Scholar
  11. Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. Google Scholar
  12. Eric Budish, Gérard P. Cachon, Judd B. Kessler, and Abraham Othman. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2):314-336, 2017. Google Scholar
  13. Ioannis Caragiannis, Nick Gravin, and Xin Huang. 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, pages 527-545, 2019. Google Scholar
  14. Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1-32, 2019. Google Scholar
  15. Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. On fair division for indivisible items. In Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 1-17, 2018. Google Scholar
  16. Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 1-19, 2020. Google Scholar
  17. Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. Improving EFX guarantees through rainbow cycle number. arXiv preprint arXiv:2103.01628, 2021. Google Scholar
  18. Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. In Proceedings of the 31st Symposium on Discrete Algorithms (SODA), pages 2658-2672, 2020. Google Scholar
  19. Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. Convex program duality, Fisher markets, and Nash social welfare. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 459-460, 2017. Google Scholar
  20. Richard Cole and Vasilis Gkatzelis. Approximating the Nash social welfare with indivisible items. SIAM Journal on Computing, 47(3):1211-1236, 2018. Google Scholar
  21. Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Approximating the Nash social welfare with budget-additive valuations. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2326-2340. SIAM, 2018. Google Scholar
  22. Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash social welfare under submodular valuations through (un) matchings. In Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, pages 2673-2687. SIAM, 2020. Google Scholar
  23. Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 379-380, 2020. Google Scholar
  24. Mohammad Ghodsi, Mohammad Taghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 539-556, 2018. Google Scholar
  25. Jonathan R. Goldman and Ariel D. Procaccia. Spliddit: unleashing fair division algorithms. ACM SIGecom Exchanges, 13(2):41-46, 2014. Google Scholar
  26. David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. Journal of ACM (JACM), 65(2):1-27, 2018. Google Scholar
  27. Euiwoong Lee. APX-hardness of maximizing Nash social welfare with indivisible items. Information Processing Letters, 122:17-20, 2017. Google Scholar
  28. Wenzheng Li and Jan Vondrák. A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. arXiv preprint arXiv:2103.10536, 2021. Google Scholar
  29. Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004. Google Scholar
  30. Ryoga Mahara. Existence of EFX for two additive valuations. arXiv preprint arXiv:2008.08798, 2020. Google Scholar
  31. Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2):1039-1068, 2020. Google Scholar
  32. Hugo Steinhaus. The problem of fair division. Econometrica, 16(1):101-104, 1948. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact