IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v131y2022icp197-221.html

Almost envy-free allocations with connected bundles

Author

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

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. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su–Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.

Suggested Citation

  • Bilò, Vittorio & Caragiannis, Ioannis & Flammini, Michele & Igarashi, Ayumi & Monaco, Gianpiero & Peters, Dominik & Vinci, Cosimo & Zwicker, William S., 2022. "Almost envy-free allocations with connected bundles," Games and Economic Behavior, Elsevier, vol. 131(C), pages 197-221.
    • Handle: RePEc:eee:gamebe:v:131:y:2022:i:c:p:197-221
    DOI: 10.1016/j.geb.2021.11.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825621001524
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2021.11.006?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
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Xiaotie Deng & Qi Qi & Amin Saberi, 2012. "Algorithmic Solutions for Envy-Free Cake Cutting," Operations Research, INFORMS, vol. 60(6), pages 1461-1476, December.
    2. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
    3. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    4. Barbanel, Julius B. & Brams, Steven J., 2004. "Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond," Mathematical Social Sciences, Elsevier, vol. 48(3), pages 251-269, November.
    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. Mackenzie, Andrew & Komornik, Vilmos, 2023. "Fairly taking turns," Games and Economic Behavior, Elsevier, vol. 142(C), pages 743-764.
    2. Pranay Gorantla & Kunal Marwaha & Santhoshini Velusamy, 2022. "Fair allocation of a multiset of indivisible items," Papers 2202.05186, arXiv.org, revised Nov 2022.
    3. Igarashi, Ayumi & Kawase, Yasushi & Suksompong, Warut & Sumita, Hanna, 2024. "Fair division with two-sided preferences," Games and Economic Behavior, Elsevier, vol. 147(C), pages 268-287.

    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. Vittorio Bilò & Ioannis Caragiannis & Michele Flammini & Ayumi Igarashi & Gianpiero Monaco & Dominik Peters & Cosimo Vinci & William Zwicker, 2021. "Almost Envy-Free Allocations with Connected Bundles," Post-Print hal-03834506, HAL.
    2. Vittorio Bil`o & Ioannis Caragiannis & Michele Flammini & Ayumi Igarashi & Gianpiero Monaco & Dominik Peters & Cosimo Vinci & William S. Zwicker, 2018. "Almost Envy-Free Allocations with Connected Bundles," Papers 1808.09406, arXiv.org, revised May 2022.
    3. Fedor Sandomirskiy & Erel Segal-Halevi, 2019. "Efficient Fair Division with Minimal Sharing," Papers 1908.01669, arXiv.org, revised Apr 2022.
    4. 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.
    5. 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.
    6. Erel Segal-Halevi & Shmuel Nitzan, 2014. "Cake Cutting – Fair and Square," Working Papers 2014-01, Bar-Ilan University, Department of Economics.
    7. Dolf Talman & Zaifu Yang, 2012. "On a Parameterized System of Nonlinear Equations with Economic Applications," Journal of Optimization Theory and Applications, Springer, vol. 154(2), pages 644-671, August.
    8. Erlanson, Albin & Szwagrzak, Karol, 2013. "Strategy-Proof Package Assignment," Working Papers 2013:43, Lund University, Department of Economics.
    9. Aygün, Orhan & Turhan, Bertan, 2021. "How to De-reserve Reserves," ISU General Staff Papers 202103100800001123, Iowa State University, Department of Economics.
    10. Herings, P.J.J. & Talman, A.J.J. & Yang, Z.F., 1999. "Variational Inequality Problems With a Continuum of Solutions : Existence and Computation," Other publications TiSEM 73e2f01b-ad4d-4447-95ba-a, Tilburg University, School of Economics and Management.
    11. Parag A. Pathak & Alex Rees-Jones & Tayfun Sönmez, 2025. "Immigration Lottery Design: Engineered and Coincidental Consequences of H-1B Reforms," The Review of Economics and Statistics, MIT Press, vol. 107(1), pages 1-13, January.
    12. Julien Combe & Vladyslav Nora & Olivier Tercieux, 2021. "Dynamic assignment without money: Optimality of spot mechanisms," Working Papers 2021-11, Center for Research in Economics and Statistics.
    13. Luofeng Liao & Christian Kroer, 2024. "Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions," Papers 2406.15522, arXiv.org, revised Mar 2025.
    14. van der Laan, Gerard & Talman, Dolf & Yang, Zaifu, 2011. "Solving discrete systems of nonlinear equations," European Journal of Operational Research, Elsevier, vol. 214(3), pages 493-500, November.
    15. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    16. Eric Budish & Gérard P. Cachon & Judd B. Kessler & Abraham Othman, 2017. "Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation," Operations Research, INFORMS, vol. 65(2), pages 314-336, April.
    17. Alejandro Jofré & R. Terry Rockafellar & Roger J-B. Wets, 2007. "Variational Inequalities and Economic Equilibrium," Mathematics of Operations Research, INFORMS, vol. 32(1), pages 32-50, February.
    18. Parag A. Pathak & Tayfun Sönmez & M. Utku Ünver & M. Bumin Yenmez, 2024. "Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Healthcare Rationing," Management Science, INFORMS, vol. 70(6), pages 3999-4036, June.
    19. 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.
    20. Shikhman, V. & Nesterov, Yu. & Ginsburgh, V., 2018. "Power method tâtonnements for Cobb–Douglas economies," Journal of Mathematical Economics, Elsevier, vol. 75(C), pages 84-92.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    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:eee:gamebe:v:131:y:2022:i:c:p:197-221. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.