Document Open Access Logo

Almost Envy-Free Allocations with Connected Bundles

Authors Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, William S. Zwicker

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.14.pdf
  • Filesize: 0.49 MB
  • 21 pages

Document Identifiers

Author Details

Vittorio Bilò
  • University of Salento, Lecce, Italy
Ioannis Caragiannis
  • University of Patras, Rion-Patras, Greece
Michele Flammini
  • Gran Sasso Science Institute and University of L'Aquila, L'Aquila, Italy
Ayumi Igarashi
  • Kyushu University, Fukuoka, Japan
Gianpiero Monaco
  • University of L'Aquila, L'Aquila, Italy
Dominik Peters
  • University of Oxford, Oxford, U.K.
Cosimo Vinci
  • University of L'Aquila, L'Aquila, Italy
William S. Zwicker
  • Union College, Schenectady, USA

Funding

D. Peters is supported by ERC grant 639945 (ACCORD). A. Igarashi is supported by KAKENHI (Grant-in-Aid for JSPS Fellows, No. 18J00997) Japan. While working on this paper, W. S. Zwicker was supported by the Oliver Smithies Visiting Fellowship at Balliol College, Oxford.

Cite As Get BibTex

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 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.14

Abstract

We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Mathematics of computing → Combinatoric problems
  • Mathematics of computing → Graph theory
Keywords
  • Envy-free Division
  • Cake-cutting
  • Resource Allocation
  • Algorithmic Game Theory

Metrics

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

Related Versions

References

  1. H. Aziz, I. Caragiannis, and A. Igarashi. Fair allocation of combinations of indivisible goods and chores. CoRR, 2018. arXiv:1807.10684. Google Scholar
  2. R. B. Bapat. A constructive proof of a permutation-based generalization of Sperner’s Lemma. Mathematical Programming, 44(1):113-120, 1989. Google Scholar
  3. J. B. Barbanel and S. J. Brams. Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond. Mathematical Social Sciences, 48(3):251-269, 2004. Google Scholar
  4. S. Barman, S. K. Krishnamurthy, and R. Vaish. Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (ACM-EC), pages 557-574, 2018. Google Scholar
  5. V. Bilò, I. Caragiannis, M. Flammini, A. Igarashi, G. Monaco, D. Peters, C. Vinci, and W. S. Zwicker. Almost Envy-Free Allocations with Connected Bundles. CoRR, 2018. arXiv:1808.09406. Google Scholar
  6. A. Biswas and S. Barman. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 91-97, 2018. Google Scholar
  7. A. Bogomolnaia, H. Moulin, F. Sandomirskyi, and E. Yanovskaya. Dividing goods and bads under additive utilities. CoRR, 2016. arXiv:1610.03745. Google Scholar
  8. J. A. Bondy and U. S. R. Murty. Graph Theory. Springer, 1st edition, 2008. Google Scholar
  9. S. Bouveret, K. Cechlárová, E. Elkind, A. Igarashi, and D. Peters. Fair division of a graph. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 135-141, 2017. Google Scholar
  10. S. J. Brams and A. D. Taylor. Fair division: from cake-cutting to dispute resolution. Cambridge University Press, 1996. Google Scholar
  11. S. J. Brams, A. D. Taylor, and W. S. Zwicker. A moving-knife solution to the four-person envy-free cake-division problem. Proceedings of the American Mathematical Society, 125(2):547-554, 1997. Google Scholar
  12. E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. Google Scholar
  13. I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (ACM-EC), pages 305-322, 2016. Google Scholar
  14. X. Deng, Q. Qi, and A. Saberi. Algorithmic solutions for envy-free cake cutting. Operations Research, 60(6):1461-1476, 2012. Google Scholar
  15. L. E. Dubins and E. H. Spanier. How to cut a cake fairly. The American Mathematical Monthly, 68(1):1-17, 1961. Google Scholar
  16. S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2(3):339-344, 1976. Google Scholar
  17. J. Hopcroft and R. Tarjan. Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372-378, 1973. Google Scholar
  18. A. Igarashi and D. Peters. Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 2019. arXiv:1811.04872. Google Scholar
  19. H. W. Kuhn. Some combinatorial lemmas in topology. IBM Journal of Research and Development, 4(5):518-524, 1960. Google Scholar
  20. A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. Theory of Graphs: International Symposium, pages 215-232, 1967. Google Scholar
  21. R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (ACM-EC), pages 125-131, 2004. Google Scholar
  22. F. Meunier and S. Zerbib. Envy-free divisions of a partially burnt cake. CoRR, 2018. arXiv:1804.00449. Google Scholar
  23. H. Oh, A. D. Procaccia, and W. Suksompong. Fairly Allocating Many Goods with Few Queries. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 2019. arXiv:1807.11367. Google Scholar
  24. A. D. Procaccia. Cake Cutting Algorithms. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 13. Cambridge University Press, 2016. Google Scholar
  25. J. Robertson and W. Webb. Cake-cutting algorithms: Be fair if you can. AK Peters/CRC Press, 1998. Google Scholar
  26. H. E. Scarf. The computation of equilibrium prices: an exposition. Handbook of Mathematical Economics, 2:1007-1061, 1982. Google Scholar
  27. E. Segal-Halevi. Fairly dividing a cake after some parts were burnt in the oven. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1276-1284, 2018. arXiv:1704.00726. Google Scholar
  28. W. Stromquist. How to cut a cake fairly. The American Mathematical Monthly, 87(8):640-644, 1980. Google Scholar
  29. F. E. Su. Rental harmony: Sperner’s lemma in fair division. The American Mathematical Monthly, 106(10):930-942, 1999. Google Scholar
  30. W. Suksompong. Fairly allocating contiguous blocks of indivisible items. In Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), pages 333-344, 2017. arXiv:1707.00345. Google Scholar
  31. R. E. Tarjan. Two streamlined depth-first search algorithms. CoRR, 9:85-94, 1986. 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 About DROPS Imprint Privacy Contact