IDEAS home Printed from https://ideas.repec.org/p/has/discpr/1819.html
   My bibliography  Save this paper

The complexity of cake cutting with unequal shares

Author

Listed:
  • Agnes Cseh

    (Hungarian Academy of Sciences, Centre for Economic and Regional Studies, Institute of Economics)

  • Tamás Fleiner

    (Department of Computer Science and Information Theory, Budapest University of Technology and Economics)

Abstract

An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.

Suggested Citation

  • Agnes Cseh & Tamás Fleiner, 2018. "The complexity of cake cutting with unequal shares," CERS-IE WORKING PAPERS 1819, Institute of Economics, Centre for Economic and Regional Studies.
    • Handle: RePEc:has:discpr:1819
    as

    Download full text from publisher

    File URL: http://www.mtakti.hu/wp-content/uploads/2018/09/MTDP1819.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Berliant, Marcus & Thomson, William & Dunz, Karl, 1992. "On the fair division of a heterogeneous commodity," Journal of Mathematical Economics, Elsevier, vol. 21(3), pages 201-216.
    2. Segal-Halevi, Erel & Nitzan, Shmuel & Hassidim, Avinatan & Aumann, Yonatan, 2017. "Fair and square: Cake-cutting in two dimensions," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 1-28.
    3. Harunor Shishido & Dao-Zhi Zeng, 1999. "Mark-Choose-Cut Algorithms For Fair And Strongly Fair Division," Group Decision and Negotiation, Springer, vol. 8(2), pages 125-137, March.
    4. Steven Brams & Michael Jones & Christian Klamler, 2008. "Proportional pie-cutting," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 353-367, March.
    5. Brams, Steven J. & Jones, Michael A. & Klamler, Christian, 2010. "Divide-and-conquer: A proportional, minimal-envy cake-cutting algorithm," MPRA Paper 22704, University Library of Munich, Germany.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Eleonora Cresto & Diego Tajer, 2022. "Fair cake-cutting for imitative agents," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(4), pages 801-833, May.
    2. Anna Bogomolnaia & Hervé Moulin, 2023. "Guarantees in Fair Division: General or Monotone Preferences," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 160-176, February.
    3. Mithun Chakraborty & Ayumi Igarashi & Warut Suksompong & Yair Zick, 2019. "Weighted Envy-Freeness in Indivisible Item Allocation," Papers 1909.10502, arXiv.org, revised Mar 2021.
    4. Erel Segal-Halevi & Shmuel Nitzan, 2019. "Fair cake-cutting among families," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 53(4), pages 709-740, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Erel Segal-Halevi & Shmuel Nitzan, 2019. "Fair cake-cutting among families," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 53(4), pages 709-740, December.
    2. Erel Segal-Halevi & Shmuel Nitzan & Avinatan Hassidim & Yonatan Aumann, 2020. "Envy-Free Division of Land," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 896-922, August.
    3. Josué Ortega & Erel Segal-Halevi, 2022. "Obvious manipulations in cake-cutting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(4), pages 969-988, November.
    4. Anna Bogomolnaia & Hervé Moulin, 2023. "Guarantees in Fair Division: General or Monotone Preferences," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 160-176, February.
    5. Thomson, William, 2011. "Chapter Twenty-One - Fair Allocation Rules," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 21, pages 393-506, Elsevier.
    6. Segal-Halevi, Erel & Nitzan, Shmuel & Hassidim, Avinatan & Aumann, Yonatan, 2017. "Fair and square: Cake-cutting in two dimensions," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 1-28.
    7. Erel Segal-Halevi & Shmuel Nitzan, 2014. "Cake Cutting – Fair and Square," Working Papers 2014-01, Bar-Ilan University, Department of Economics.
    8. Legut, Jerzy, 2020. "Simple fair division of a square," Journal of Mathematical Economics, Elsevier, vol. 86(C), pages 35-40.
    9. Fabio Maccheroni & Fabio Maccheroni & Massimo Marinacci & Massimo Marinacci, 2003. "How to cut a pizza fairly: Fair division with decreasing marginal evaluations," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 457-465, June.
    10. Dall'Aglio, M. & Brânzei, R. & Tijs, S.H., 2008. "Cooperation in Dividing the Cake," Discussion Paper 2008-101, Tilburg University, Center for Economic Research.
    11. Pálvölgyi, Dénes & Peters, Hans & Vermeulen, Dries, 2014. "A strategic approach to multiple estate division problems," Games and Economic Behavior, Elsevier, vol. 88(C), pages 135-152.
    12. Marco Dall’Aglio & Rodica Branzei & Stef Tijs, 2009. "Cooperation in dividing the cake," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 17(2), pages 417-432, December.
    13. Sherstyuk, Katerina, 1998. "How to Gerrymander: A Formal Analysis," Public Choice, Springer, vol. 95(1-2), pages 27-49, April.
    14. Nhan-Tam Nguyen & Dorothea Baumeister & Jörg Rothe, 2018. "Strategy-proofness of scoring allocation correspondences for indivisible goods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(1), pages 101-122, January.
    15. Marco LiCalzi & Antonio Nicolò, 2009. "Efficient egalitarian equivalent allocations over a single good," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 40(1), pages 27-45, July.
    16. William Thomson, 2007. "Children Crying at Birthday Parties. Why?," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 31(3), pages 501-521, June.
    17. Chen, Yiling & Lai, John K. & Parkes, David C. & Procaccia, Ariel D., 2013. "Truth, justice, and cake cutting," Games and Economic Behavior, Elsevier, vol. 77(1), pages 284-297.
    18. Thomson, William, 2005. "Divide-and-permute," Games and Economic Behavior, Elsevier, vol. 52(1), pages 186-200, July.
    19. Kyropoulou, Maria & Ortega, Josué & Segal-Halevi, Erel, 2022. "Fair cake-cutting in practice," Games and Economic Behavior, Elsevier, vol. 133(C), pages 28-49.
    20. Hao Guo & Weidong Li & Bin Deng, 2023. "A Survey on Fair Allocation of Chores," Mathematics, MDPI, vol. 11(16), pages 1-28, August.

    More about this item

    Keywords

    fair division; cake cutting; unequal shares; complexity;
    All these keywords.

    JEL classification:

    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:has:discpr:1819. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Nora Horvath (email available below). General contact details of provider: https://edirc.repec.org/data/iehashu.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.