IDEAS home Printed from https://ideas.repec.org/p/has/discpr/1819.html

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," KRTK-KTI 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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    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. Mithun Chakraborty & Ayumi Igarashi & Warut Suksompong & Yair Zick, 2019. "Weighted Envy-Freeness in Indivisible Item Allocation," Papers 1909.10502, arXiv.org, revised Mar 2021.
    2. 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.
    3. 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.
    4. 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.

    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 & Avinatan Hassidim & Yonatan Aumann, 2020. "Envy-Free Division of Land," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 896-922, August.
    2. 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.
    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. Erel Segal-Halevi & Shmuel Nitzan, 2014. "Cake Cutting – Fair and Square," Working Papers 2014-01, Bar-Ilan University, Department of Economics.
    6. 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.
    7. 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.
    8. Legut, Jerzy, 2020. "Simple fair division of a square," Journal of Mathematical Economics, Elsevier, vol. 86(C), pages 35-40.
    9. 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.
    10. 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.
    11. Sherstyuk, Katerina, 1998. "How to Gerrymander: A Formal Analysis," Public Choice, Springer, vol. 95(1-2), pages 27-49, April.
    12. R. Pablo Arribillaga & Agustín G. Bonifacio, 2025. "Not obviously manipulable allotment rules," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 80(1), pages 355-380, August.
    13. Qiushi Chen & Robert Newton & Paul Griffin, 2025. "Fair allocation strategies for opioid settlements," Health Care Management Science, Springer, vol. 28(3), pages 335-356, September.
    14. 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.
    15. Thomson, William, 2005. "Divide-and-permute," Games and Economic Behavior, Elsevier, vol. 52(1), pages 186-200, July.
    16. Doğan, Battal, 2016. "Nash-implementation of the no-envy solution on symmetric domains of economies," Games and Economic Behavior, Elsevier, vol. 98(C), pages 165-171.
    17. Balazs Sziklai & Erel Segal-Halevi, 2015. "Resource-monotonicity and Population-monotonicity in Cake-cutting," KRTK-KTI WORKING PAPERS 1552, Institute of Economics, Centre for Economic and Regional Studies.
    18. Ji-Won Park & Jaeup U. Kim & Cheol-Min Ghim & Chae Un Kim, 2021. "The Boltzmann fair division for distributive justice," Papers 2109.11917, arXiv.org, revised Nov 2021.
    19. Mackenzie, Andrew, 2019. "A foundation for probabilistic beliefs with or without atoms," Theoretical Economics, Econometric Society, vol. 14(2), May.
    20. Nicolò, Antonio & Yu, Yan, 2008. "Strategic divide and choose," Games and Economic Behavior, Elsevier, vol. 64(1), pages 268-289, September.

    More about this item

    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 The email address of this maintainer does not seem to be valid anymore. Please ask Nora Horvath to update the entry or send us the correct address (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.