IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i3p1875-1903.html

Fair Cake Division Under Monotone Likelihood Ratios

Author

Listed:
  • Siddharth Barman

    (Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560012, India)

  • Nidhi Rathi

    (Department of Mathematics, Indian Institute of Science, Bangalore 560012, India)

Abstract

This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. Although multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likelihood ratio property (MLRP), then strong algorithmic results hold for various notions of fairness and economic efficiency. Addressing cake-cutting instances with MLRP, first we develop an algorithm that finds cake divisions (with connected pieces) that are envy free, up to an arbitrary precision. The time complexity of our algorithm is polynomial in the number of agents and the bit complexity of an underlying Lipschitz constant. We obtain similar positive results for maximizing social, egalitarian, and Nash social welfare. Many distribution families bear MLRP. In particular, this property holds if all the value densities belong to any one of the following families: Gaussian (with the same variance), linear, Poisson, and exponential distributions, linear translations of any log-concave function. Hence, through MLRP, the current work obtains novel cake-cutting algorithms for multiple distribution families.

Suggested Citation

  • Siddharth Barman & Nidhi Rathi, 2022. "Fair Cake Division Under Monotone Likelihood Ratios," Mathematics of Operations Research, INFORMS, vol. 47(3), pages 1875-1903, August.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:3:p:1875-1903
    DOI: 10.1287/moor.2021.1192
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1192
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1192?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gans, Joshua S. & Smart, Michael, 1996. "Majority voting with single-crossing preferences," Journal of Public Economics, Elsevier, vol. 59(2), pages 219-237, February.
    2. Herve Moulin, 2004. "Fair Division and Collective Welfare," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262633116, December.
    3. 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.
    4. Kaneko, Mamoru & Nakamura, Kenjiro, 1979. "The Nash Social Welfare Function," Econometrica, Econometric Society, vol. 47(2), pages 423-435, March.
    5. Weller, Dietrich, 1985. "Fair division of a measurable space," Journal of Mathematical Economics, Elsevier, vol. 14(1), pages 5-17, February.
    6. Athey, Susan, 2001. "Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information," Econometrica, Econometric Society, vol. 69(4), pages 861-889, July.
    Full references (including those not matched with items on IDEAS)

    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. Cole, Richard & Tao, Yixin, 2021. "On the existence of Pareto Efficient and envy-free allocations," Journal of Economic Theory, Elsevier, vol. 193(C).
    2. 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.
    3. Jose Apesteguia & Miguel A. Ballester & Jay Lu, 2017. "Single‐Crossing Random Utility Models," Econometrica, Econometric Society, vol. 85, pages 661-674, March.
    4. Michael Sockin & Mindy Z Xiaolan, 2023. "Delegated Learning and Contract Commonality in Asset Management," Review of Finance, European Finance Association, vol. 27(6), pages 1931-1975.
    5. 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.
    6. 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.
    7. Kyropoulou, Maria & Ortega, Josué & Segal-Halevi, Erel, 2022. "Fair cake-cutting in practice," Games and Economic Behavior, Elsevier, vol. 133(C), pages 28-49.
    8. Bhardwaj, Bhavook & Kumar, Rajnish & Ortega, Josué, 2020. "Fairness and efficiency in cake-cutting with single-peaked preferences," Economics Letters, Elsevier, vol. 190(C).
    9. Siddharth Barman & Sanath Kumar Krishnamurthy & Rohit Vaish, 2018. "Greedy Algorithms for Maximizing Nash Social Welfare," Papers 1801.09046, arXiv.org.
    10. Erel Segal-Halevi & Shmuel Nitzan, 2014. "Cake Cutting – Fair and Square," Working Papers 2014-01, Bar-Ilan University, Department of Economics.
    11. Xiaohui Bei & Guangda Huzhang & Warut Suksompong, 2020. "Truthful fair division without free disposal," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 55(3), pages 523-545, October.
    12. Yuchen Hu & Henry Zhu & Emma Brunskill & Stefan Wager, 2024. "Minimax-Regret Sample Selection in Randomized Experiments," Papers 2403.01386, arXiv.org, revised Jun 2024.
    13. Orit Arzi & Yonatan Aumann & Yair Dombb, 2016. "Toss one’s cake, and eat it too: partial divisions can improve social welfare in cake cutting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 46(4), pages 933-954, April.
    14. Antonio Nicolò & Andrés Perea y Monsuwe & Paolo Roberti, 2012. "Equal opportunity equivalence in land division," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 3(1), pages 133-142, March.
    15. Erel Segal-Halevi & Balázs R. Sziklai, 2019. "Monotonicity and competitive equilibrium in cake-cutting," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 68(2), pages 363-401, September.
    16. Yuan Gao & Christian Kroer, 2023. "Infinite-Dimensional Fisher Markets and Tractable Fair Division," Operations Research, INFORMS, vol. 71(2), pages 688-707, March.
    17. 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.
    18. Yuan Gao & Christian Kroer, 2020. "Infinite-Dimensional Fisher Markets and Tractable Fair Division," Papers 2010.03025, arXiv.org, revised Apr 2021.
    19. Persson, Torsten & Tabellini, Guido, 2002. "Political economics and public finance," Handbook of Public Economics, in: A. J. Auerbach & M. Feldstein (ed.), Handbook of Public Economics, edition 1, volume 3, chapter 24, pages 1549-1659, Elsevier.
    20. Francisco Martínez-Mora & M. Socorro Puy, 2009. "Off-the-peak preferences over government size," Working Papers 2009-9, Universidad de Málaga, Department of Economic Theory, Málaga Economic Theory Research Center.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    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:inm:ormoor:v:47:y:2022:i:3:p:1875-1903. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.