Document Open Access Logo

Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average

Authors Yusuke Kobayashi , Ryoga Mahara

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.55.pdf
  • Filesize: 0.78 MB
  • 13 pages

Document Identifiers

Author Details

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

Funding

This work was partially supported by the joint project of Kyoto University and Toyota Motor Corporation, titled "Advanced Mathematical Science for Mobility Society", and by JSPS, KAKENHI grant numbers JP19H05485, 20H05795, and 22H05001, Japan.

Acknowledgements

The authors would like to thank anonymous reviewers for their comments.

Cite AsGet BibTex

Yusuke Kobayashi and Ryoga Mahara. Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.55

Abstract

We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate notions of proportionality have been considered in the previous work. Among them, proportionality up to the maximin good (PROPm) has been the best approximate notion of proportionality that can be achieved for all instances. In this paper, we introduce the notion of proportionality up to the least valued good on average (PROPavg), which is a stronger notion than PROPm, and show that a PROPavg allocation always exists. Our results establish PROPavg as a notable non-trivial fairness notion that can be achieved for all instances. Our proof is constructive, and based on a new technique that generalizes the cut-and-choose protocol.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Discrete Fair Division
  • Indivisible Goods
  • Proportionality

Metrics

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

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, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris. Fair division of indivisible goods: A survey. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.07551.
  3. Haris Aziz, Bo Li, Herve Moulin, and Xiaowei Wu. Algorithmic fair allocation of indivisible items: A survey and new questions. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.08713.
  4. Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. Operations Research Letters, 48(5):573-578, 2020. Google Scholar
  5. Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, and Daniel Schoepflin. Achieving proportionality up to the maximin item with indivisible goods. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5143-5150, 2021. Google Scholar
  6. Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, and Daniel Schoepflin. PROPm allocations of indivisible goods to multiple agents. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 24-30, 2021. Google Scholar
  7. Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy algorithms for maximizing Nash social welfare. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 7-13, 2018. Google Scholar
  8. Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. (Almost full) EFX exists for four agents (and beyond). arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.10654.
  9. Steven J Brams, Steven John Brams, and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996. Google Scholar
  10. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 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. 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 (EC), pages 527-545, 2019. Google Scholar
  13. 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, 7(3):1-32, 2019. Google Scholar
  14. 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
  15. Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. Improving EFX guarantees through rainbow cycle number. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 310-311, 2021. Google Scholar
  16. Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. SIAM Journal on Computing, 50(4):1336-1358, 2021. Google Scholar
  17. Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 629-646, 2017. Google Scholar
  18. Andreas Darmann and Joachim Schauer. Maximizing Nash product social welfare in allocating indivisible goods. European Journal of Operational Research, 247(2):548-559, 2015. Google Scholar
  19. Andrew L Dulmage. A structure theory of bipartite graphs of finite exterior dimension. The Transactions of the Royal Society of Canada, Section III, 53:1-13, 1959. Google Scholar
  20. Andrew L Dulmage and Nathan S Mendelsohn. Coverings of bipartite graphs. Canadian Journal of Mathematics, 10:517-534, 1958. Google Scholar
  21. P Hall. On representatives of subsets. Journal of the London Mathematical Society, 1(1):26-30, 1935. Google Scholar
  22. 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 (EC), pages 125-131, 2004. Google Scholar
  23. Ryoga Mahara. Existence of EFX for two additive valuations. arXiv preprint, 2020. URL: http://arxiv.org/abs/2008.08798.
  24. Ryoga Mahara. Extension of additive valuations to general valuations on the existence of EFX. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA), pages 66:1-15, 2021. Google Scholar
  25. Hervé Moulin. Fair division and collective welfare. MIT press, 2004. Google Scholar
  26. Hervé Moulin. Fair division in the internet age. Annual Review of Economics, 11:407-441, 2019. Google Scholar
  27. Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2):1039-1068, 2020. Google Scholar
  28. Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can, 1998. Google Scholar
  29. 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