Parameterized Guarantees for Almost Envy-Free Allocations
Pages 151 - 159
Abstract
We study fair allocation of indivisible goods among agents with additive valuations. We obtain novel approximation guarantees for two of the strongest fairness notions in discrete fair division, namely envy-free up to the removal of any positively-valued good (EFx) and pairwise maximin shares (PMMS). Our approximation guarantees are in terms of an instance-dependent parameter γ ∈ (0,1] that upper bounds, for each indivisible good in the given instance, the multiplicative range of nonzero values for the good across the agents.
First, we consider allocations wherein, between any pair of agents and up to the removal of any positively-valued good, the envy is multiplicatively bounded. Specifically, the current work develops a polynomial-time algorithm that computes a ( 2 over γ √ 5+4 γ-1 &41;-approximately EFx allocation for any given fair division instance with range parameter γ ∈ (0,1]. For instances with γ ≥ 0.511, the obtained approximation guarantee for EFx surpasses the previously best-known approximation bound of (φ-1) ≈ 0.618, here φ denotes the golden ratio.
Furthermore, we study multiplicative approximations for PMMS. For fair division instances with range parameter γ ∈ (0,1], the current paper develops a polynomial-time algorithm for finding allocations wherein the PMMS requirement is satisfied, between every pair of agents, within a multiplicative factor of 5 over 6 γ. En route to this result, we obtain novel existential and computational guarantees for 5 over 6-approximately PMMS allocations under restricted additive valuations.
References
[1]
Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. 2023. EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. In 24th ACM Conference on Economics and Computation, EC 2023. Association for Computing Machinery, Inc, 61.
[2]
Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. 2022a. EFX allocations: Simplifications and improvements. arXiv preprint arXiv:2205.07638 (2022).
[3]
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, and Ernest van Wijland. 2022b. Maximizing Nash social welfare in 2-value instances. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 4760--4767.
[4]
Hannaneh Akrami, Rojin Rezvan, and Masoud Seddighin. 2022c. An EF2X Allocation Protocol for Restricted Additive Valuations. In Thirty-First International Joint Conference on Artificial Intelligence. IJCAI, 17--23.
[5]
Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. 2015. Online fair division: analysing a food bank problem. In Proceedings of the 24th International Conference on Artificial Intelligence. 2540--2546.
[6]
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A Voudouris, and Xiaowei Wu. 2022. Fair division of indivisible goods: A survey. arXiv preprint arXiv:2208.08782 (2022).
[7]
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A Voudouris. 2021. Maximum Nash welfare and other stories about EFX. Theoretical Computer Science, Vol. 863 (2021), 69--85.
[8]
Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. 2020. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Computer Science, Vol. 841 (2020), 94--109.
[9]
Siddharth Barman, Debajyoti Kar, and Shraddha Pathak. 2023. Parameterized Guarantees for Almost Envy-Free Allocations. arXiv preprint arXiv:2312.13791 (2023).
[10]
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. 2018. Greedy Algorithms for Maximizing Nash Social Welfare. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. 7--13.
[11]
Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. 2020. Finding fair and efficient allocations when valuations don't add up. In International Symposium on Algorithmic Game Theory. Springer, 32--46.
[12]
Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. 2022. Fixed-point cycles and approximate EFX allocations. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
[13]
Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. 2022. Almost full EFX exists for four agents. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 4826--4833.
[14]
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia. 2016. Handbook of Computational Social Choice 1st ed.). Cambridge University Press, USA.
[15]
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. Oper. Res., Vol. 65 (2017), 314--336.
[16]
Franklin Camacho, Rigoberto Fonseca-Delgado, Ramón Pino Pérez, and Guido Tapia. 2021. Beyond identical utilities: buyer utility functions and fair allocations. arXiv:2109.08461 (2021).
[17]
Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019a. Envy-freeness up to any item with high Nash welfare: The virtue of donating items. In Proceedings of the 2019 ACM Conference on Economics and Computation. 527--545.
[18]
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. 2019b. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), Vol. 7, 3 (2019), 1--32.
[19]
Shayan Chashm Jahan, Masoud Seddighin, Seyed-Mohammad Seyed-Javadi, and Mohammad Sharifi. 2022. Rainbow Cycle Number and EFX Allocations:(Almost) Closing the Gap. arXiv e-prints (2022), arXiv-2212.
[20]
Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. 2020. EFX exists for three agents. In Proceedings of the 21st ACM Conference on Economics and Computation. 1--19.
[21]
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2021a. Improving EFX guarantees through rainbow cycle number. In Proceedings of the 22nd ACM Conference on Economics and Computation. 310--311.
[22]
Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. 2021b. A little charity guarantees almost envy-freeness. SIAM J. Comput., Vol. 50, 4 (2021), 1336--1358.
[23]
Yongheng Deng, Tien Foo Sing, and Chaoqun Ren. 2013. The story of Singapore's public housing: From a nation of home-seekers to a nation of homeowners. In The future of public housing. Springer, 103--121.
[24]
Lester E Dubins and Edwin H Spanier. 1961. How to cut a cake fairly. The American Mathematical Monthly, Vol. 68, 1P1 (1961), 1--17.
[25]
Soroush Ebadian, Dominik Peters, and Nisarg Shah. 2022. How to Fairly Allocate Easy and Difficult Chores. In 21st International Conference on Autonomous Agents and Multiagent Systems.
[26]
Alireza Farhadi, MohammadTaghi Hajiaghayi, Mohamad Latifian, Masoud Seddighin, and Hadi Yami. 2021. Almost envy-freeness, envy-rank, and nash social welfare matchings. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5355--5362.
[27]
Uriel Feige. 2022. Maximin fair allocations with two item values. Unpublished Manuscript (2022).
[28]
Uriel Feige, Ariel Sapir, and Laliv Tauber. 2021. A tight negative example for MMS fair allocations. In International Conference on Web and Internet Economics. Springer, 355--372.
[29]
Michal Feldman, Simon Mauras, and Tomasz Ponitka. 2023. On optimal tradeoffs between EFX and nash welfare. arXiv preprint arXiv:2302.09633 (2023).
[30]
Duncan Karl Foley. 1966. Resource allocation and the public sector. Yale University.
[31]
Jugal Garg and Aniket Murhekar. 2023. Computing fair and efficient allocations with few utility values. Theoretical Computer Science, Vol. 962 (2023), 113932.
[32]
Jugal Garg, Aniket Murhekar, and John Qin. 2022. Fair and efficient allocations of chores under bivalued preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 5043--5050.
[33]
Jonathan Goldman and Ariel D Procaccia. 2015. Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges, Vol. 13, 2 (2015), 41--46.
[34]
Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. 2014. Near Fairness in Matroids. In ECAI, Vol. 14. 393--398.
[35]
David Kurokawa. 2017. Algorithms for Fair Division. PhD Thesis, Carnegie Mellon University (2017).
[36]
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. 125--131.
[37]
Ryoga Mahara. 2023. Extension of additive valuations to general valuations on the existence of EFX. Mathematics of Operations Research (2023).
[38]
Hervé Moulin. 2004. Fair division and collective welfare. MIT press.
[39]
Hervé Moulin. 2019. Fair division in the internet age. Annual Review of Economics, Vol. 11 (2019), 407--441.
[40]
Benjamin Plaut and Tim Roughgarden. 2020. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, Vol. 34, 2 (2020), 1039--1068.
[41]
Canice Prendergast. 2017. How food banks use markets to feed the poor. Journal of Economic Perspectives, Vol. 31, 4 (2017), 145--162.
[42]
Ariel D Procaccia. 2020. Technical perspective: An answer to fair division's most enigmatic question. Commun. ACM, Vol. 63, 4 (2020), 118--118.
[43]
Nisarg Shah. 2017. Spliddit: two years of making the world fairer. XRDS: Crossroads, The ACM Magazine for Students, Vol. 24, 1 (2017), 24--28.
[44]
Hal R Varian. 1974. Equity, envy, and efficiency. Journal of Economic Theory, Vol. 9, 1 (1974), 63--91.
Index Terms
- Parameterized Guarantees for Almost Envy-Free Allocations
Recommendations
Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare
We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions of ...
Envy-free auctions for digital goods
EC '03: Proceedings of the 4th ACM conference on Electronic commerceWe study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: item Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. ...
Envy-Free and Efficient Allocations for Graphical Valuations
Algorithmic Decision TheoryAbstractWe consider the complexity of finding envy-free allocations for the class of graphical valuations. Graphical valuations were introduced by Christodoulou et al. [14] as a structured class of valuations that admit allocations that are envy-free up ...
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
- Research-article
Funding Sources
- Science Engineering Research Board
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
- 22Total Downloads
- Downloads (Last 12 months)22
- Downloads (Last 6 weeks)2
Reflects downloads up to 23 Nov 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