Document Open Access Logo

Cake Cutting: An Envy-Free and Truthful Mechanism with a Small Number of Cuts

Authors Takao Asano, Hiroyuki Umeda

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.15.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • cake-cutting problem
  • envy-freeness
  • fairness
  • truthfulness
  • mechanism design

Metrics

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

Abstract

The mechanism for the cake-cutting problem based on the expansion process with unlocking proposed by Alijani, Farhadi, Ghodsi, Seddighin, and Tajik [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] uses a small number of cuts, but is not actually envy-free and truthful, although they claimed that it is envy-free and truthful. In this paper, we consider the same cake-cutting problem and give a new envy-free and truthful mechanism with a small number of cuts, which is not based on their expansion process with unlocking.

Cite As Get BibTex

Takao Asano and Hiroyuki Umeda. Cake Cutting: An Envy-Free and Truthful Mechanism with a Small Number of Cuts. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.15

Author Details

Takao Asano
  • Chuo University, Tokyo, Japan
Hiroyuki Umeda
  • Chuo University, Tokyo, Japan

Acknowledgements

The first author would like to thank Professor Shigeo Tsujii of Chuo University.

References

  1. Reza Alijani, Majid Farhadi, Mohammad Ghodsi, Masoud Seddighin, and Ahmad S. Tajik. Envy-free mechanisms with minimum number of cuts. In 31st AAAI Conference on Artificial Intelligence, 2017, pages 312-318, 2017. Google Scholar
  2. Takao Asano and Hiroyuki Umeda. An envy-free and truthful mechanism for the cake-cutting problem. In RIMS Kôkyûroku 2154, Kyoto University, April, 2020, pages 54-91, 2020. Google Scholar
  3. Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In 57th Annual Symposium on Foundations of Computer Science, 2016, pages 416-427, 2016. Google Scholar
  4. Haris Aziz and Chun Ye. Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In 10th International Conference on Web and Internet Economics, 2014, pages 1-14, 2014. Google Scholar
  5. Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, and Endong Yang. Optimal proportional cake cutting with connected pieces. In 26th AAAI Conference on Artificial Intelligence, 2012, pages 1263-1269, 2012. Google Scholar
  6. Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, and Ariel D. Procaccia. On maxsum fair cake divisions. In 26th AAAI Conference on Artificial Intelligence, 2012, pages 1285-1291, 2012. Google Scholar
  7. Steven J. Brams, Michael Jones, and Christian Klamler. Proportional pie-cutting. International Journal of Game Theory, 36:353-367, 2008. Google Scholar
  8. Ioannis Caragiannis, John K. Lai, and Ariel D. Procaccia. Towards more expressive cake cutting. In 22nd International Joint Conference on Artificial Intelligence, 2011, pages 127-132, 2011. Google Scholar
  9. Yiling Chen, John K. Lai, David C. Parkes, and Ariel D. Procaccia. Truth, justice, and cake cutting. Games and Economic Behavior, 77:284-297, 2013. Google Scholar
  10. Xiaotie Deng, Qi Qi, and Amin Saberi. Algorithmic solutions for envy-free cake cutting. Operations Research, 60:1461-1476, 2012. Google Scholar
  11. Jeff Edmonds and Kirk Pruhs. Balanced allocations of cake. In 47th Annual Symposium on Foundations of Computer Science, 2006, pages 623-634, 2006. Google Scholar
  12. Paul W. Goldberg, Alexandros Hollender, and Warut Suksompong. Contiguous cake cutting: hardness results and approximation algorithms. In 34th AAAI Conference on Artificial Intelligence, 2020, pages 1990-1997, 2020. Google Scholar
  13. P. Hall. On representations of subsets. Journal of London Mathematical Society, 10:26-30, 1934. Google Scholar
  14. David Kurokawa, John K. Lai, and Ariel D. Procaccia. How to cut a cake before the party ends. In 27th AAAI Conference on Artificial Intelligence, 2013, pages 555-561, 2013. Google Scholar
  15. Avishay Maya and Noam Nisan. Incentive compatible two player cake cutting. In 8th International Conference on Web and Internet Economics, 2012, pages 170-183, 2012. Google Scholar
  16. Ariel D. Procaccia. Cake cutting: not just child’s play. Commun. ACM, 56:78-87, 2013. Google Scholar
  17. Jack M. Robertson and William A. Webb. Cake Cutting Algorithms: Be Fair If you Can. A.K. Peters, 1998. Google Scholar
  18. Masoud Seddighin, Majid Farhadi, Mohammad Ghodsi, Reza Alijani, and Ahmad S. Tajik. Expand the shares together: envy-free mechanisms with a small number of cuts. Algorithmica, 81:1728-1755, 2019. Google Scholar
  19. Hugo Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948. Google Scholar
  20. Walter Stromquist. How to cut a cake fairly. American Mathematical Monthly, 87:640-644, 1980. Google Scholar
  21. Walter Stromquist. Envy-free cake divisions cannot be found by finite protocols. The Electronic Journal of Combinatorics, 15:#R11 (pp.1-10), 2008. Google Scholar
  22. Francis E. Su. Rental harmony: Sperner’s lemma in fair division. American Mathematical Monthly, 106:930-942, 1999. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact