On the existence of EFX under picky or non-differentiative agents
Pages 2534 - 2536
Abstract
In this paper, we consider the fair division of indivisible goods under arguably the strongest envy-based fairness notion of envy-free up to any item (EFX). Extending the long line of work on special cases of additive valuations, we show existence of EFX for the following two cases: (i) instances where agents are very picky, i.e., each agent likes at most four items positively. (ii) ternary instances where the value of an agent for an item is 0, a, or b for 0 < a < b ≤ 2a. In both cases, the existence is shown by designing an efficient algorithm to find an EFX allocation.
References
[1]
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris. 2020. Maximum Nash Welfare and Other Stories About EFX. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (IJCAI). 24--30.
[2]
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.
[3]
Steven J. Brams and Alan D. Taylor. 1996. Fair division - from cake-cutting to dispute resolution. Cambridge University Press.
[4]
Xiaolin Bu, Jiaxin Song, and Ziqi Yu. 2023. EFX Allocations Exist for Binary Valuations. In Frontiers of Algorithmics - 17th International Joint Conference, IJTCS-FAW 2023 Macau, China, August 14-18, 2023, Proceedings (Lecture Notes in Computer Science, Vol. 13933), Minming Li, Xiaoming Sun, and Xiaowei Wu (Eds.). Springer, 252--262. https://doi.org/10.1007/978-3-031-39344-0_19
[5]
Eric Budish and Estelle Cantillon. 2010. The Multi-Unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard. American Economic Review 102 (2010).
[6]
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Trans. Economics and Comput. 7, 3 (2019), 12:1--12:32.
[7]
Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. 2020. EFX Exists for Three Agents. In EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, Péter Biró, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia (Eds.). ACM, 1--19. https://doi.org/10.1145/ 3391403.3399511
[8]
George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. 2023. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson (Eds.). ACM, 473--488. https://doi.org/10.1145/3580507.3597764
[9]
Envy-free Cake Cutting [n.d.]. https://en.wikipedia.org/wiki/Envy-free_cake-cutting.
[10]
R. Etkin, A. Parekh, and D. Tse. 2005. Spectrum Sharing for Unlicensed Bands. In In Proceedings of the first IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks.
[11]
Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, and Nithin Varma. 2023. EFX Exists for Four Agents with Three Types of Valuations. CoRR abs/2301.10632 (2023). https://doi.org/10.48550/arXiv.2301.10632 arXiv:2301.10632
[12]
Pranay Gorantla, Kunal Marwaha, and Santhoshini Velusamy. 2023. Fair allocation of a multiset of indivisible items. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, 304--331. https://doi.org/10.1137/1.9781611977554.ch13
[13]
Vasilis Livanos, Ruta Mehta, and Aniket Murhekar. 2022. (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna. In 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022, Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, and Matthew E. Taylor (Eds.). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 1678--1680. https: //doi.org/10.5555/3535850.3536074
[14]
Ryoga Mahara. 2021. Extension of Additive Valuations to General Valuations on the Existence of EFX. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference) (LIPIcs, Vol. 204), Petra Mutzel, Rasmus Pagh, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 66:1--66:15. https://doi.org/10.4230/LIPIcs.ESA. 2021.66
[15]
Ryoga Mahara. 2023. Existence of EFX for two additive valuations. Discret. Appl. Math. 340 (2023), 115--122. https://doi.org/10.1016/j.dam.2023.06.035
[16]
Benjamin Plaut and Tim Roughgarden. 2020. Almost Envy-Freeness with General Valuations. SIAM J. Discret. Math. 34, 2 (2020), 1039--1068. https://doi.org/10. 1137/19M124397X
[17]
John Winsor Pratt and Richard Jay Zeckhauser. 1990. The Fair and Efficient Division of the Winsor Family Silver. Management Science 36, 11 (1990), 1293--1301.
[18]
Ariel D. Procaccia. 2020. Technical Perspective: An Answer to Fair Division's Most Enigmatic Question. Commun. ACM 63, 4 (March 2020), 118. https: //doi.org/10.1145/3382131
[19]
Hugo Steinhaus. 1948. The Problem of Fair Division. Econometrica 16, 1 (1948), 101--104.
[20]
T. W.M. Vossen. 2002. Fair allocation concepts in air traffic management. Ph.D. Dissertation. University of Maryland, College Park.
Index Terms
- On the existence of EFX under picky or non-differentiative agents
Recommendations
Prior-free auctions for budgeted agents
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceWe consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service ...
Prior-free auctions for budgeted agents
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceWe consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service ...
Existence of EFX for two additive valuations
AbstractFair division of indivisible items is a well-studied topic in Economics and Computer Science. The objective is to allocate items to agents in a fair manner, where each agent has a valuation for each subset of items. Envy-freeness is one of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
2898 pages
ISBN:9798400704864
- General Chairs:
- Mehdi Dastani,
- Jaime Simão Sichman,
- Program Chairs:
- Natasha Alechina,
- Virginia Dignum
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 06 May 2024
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Funding Sources
- NSF
Conference
AAMAS '24
Sponsor:
AAMAS '24: International Conference on Autonomous Agents and Multiagent Systems
May 6 - 10, 2024
Auckland, New Zealand
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 26Total Downloads
- Downloads (Last 12 months)26
- Downloads (Last 6 weeks)8
Reflects downloads up to 16 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in