IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1912.00459.html
   My bibliography  Save this paper

Fair Division with Bounded Sharing

Author

Listed:
  • Erel Segal-Halevi

Abstract

A set of objects is to be divided fairly among agents with different tastes, modeled by additive value functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then fair division may not exist. How many objects must be shared between two or more agents in order to attain a fair division? The paper studies various notions of fairness, such as proportionality, envy-freeness and equitability. It also studies consensus division, in which each agent assigns the same value to all bundles --- a notion that is useful in truthful fair division mechanisms. It proves upper bounds on the number of required sharings. However, it shows that finding the minimum number of sharings is, in general, NP-hard even for generic instances. Many problems remain open.

Suggested Citation

  • Erel Segal-Halevi, 2019. "Fair Division with Bounded Sharing," Papers 1912.00459, arXiv.org.
    • Handle: RePEc:arx:papers:1912.00459
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1912.00459
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Anna Bogomolnaia & Hervé Moulin & Fedor Sandomirskiy & Elena Yanovskaya, 2017. "Competitive Division of a Mixed Manna," Econometrica, Econometric Society, vol. 85(6), pages 1847-1871, November.
    3. Anna Bogomolnaia & Herve Moulin & Fedor Sandomirskiy & Elena Yanovskaya, 2016. "Dividing Goods and Bads Under Additive Utilities," HSE Working papers WP BRP 153/EC/2016, National Research University Higher School of Economics.
    4. Simina Br^anzei & Fedor Sandomirskiy, 2019. "Algorithms for Competitive Division of Chores," Papers 1907.01766, arXiv.org, revised Jul 2023.
    5. Anna Bogomolnaia & Herve Moulin & Fedor Sandomirskiy & Elena Yanovskaya, 2016. "Dividing Goods or Bads Under Additive Utilities," HSE Working papers WP BRP 147/EC/2016, National Research University Higher School of Economics.
    6. Anna, Petrenko, 2016. "Мaркування готової продукції як складова частина інформаційного забезпечення маркетингової діяльності підприємств овочепродуктового підкомплексу," Agricultural and Resource Economics: International Scientific E-Journal, Agricultural and Resource Economics: International Scientific E-Journal, vol. 2(1), March.
    7. Nimrod Megiddo, 1991. "On Finding Primal- and Dual-Optimal Bases," INFORMS Journal on Computing, INFORMS, vol. 3(1), pages 63-65, February.
    8. Fedor Sandomirskiy & Erel Segal-Halevi, 2019. "Efficient Fair Division with Minimal Sharing," Papers 1908.01669, arXiv.org, revised Apr 2022.
    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. Fedor Sandomirskiy & Erel Segal-Halevi, 2019. "Efficient Fair Division with Minimal Sharing," Papers 1908.01669, arXiv.org, revised Apr 2022.
    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. Soroush Ebadian & Dominik Peters & Nisarg Shah, 2022. "How to Fairly Allocate Easy and Difficult Chores," Post-Print hal-03834514, HAL.
    4. Hao Guo & Weidong Li & Bin Deng, 2023. "A Survey on Fair Allocation of Chores," Mathematics, MDPI, vol. 11(16), pages 1-28, August.
    5. Pavel Konyukhovskiy & Victoria Holodkova & Aleksander Titov, 2019. "Modeling Competition between Countries in the Development of Arctic Resources," Resources, MDPI, vol. 8(1), pages 1-17, March.
    6. Misha Gavrilovich & Victoria Kreps, 2016. "Games with Incomplete Information on One Side as Games with Incomplete Information on Both Sides and Asymmetric Computational Resources," HSE Working papers WP BRP 154/EC/2016, National Research University Higher School of Economics.
    7. Yves Sprumont, 2020. "Nash welfarism and the distributive implications of informational constraints," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(1), pages 49-64, April.
    8. Alper Atamtürk & Andrés Gómez, 2017. "Maximizing a Class of Utility Functions Over the Vertices of a Polytope," Operations Research, INFORMS, vol. 65(2), pages 433-445, March-Apr.
    9. Erling D. Andersen, 1999. "On Exploiting Problem Structure in a Basis Identification Procedure for Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 95-103, February.
    10. Yann Briheche & Frederic Barbaresco & Fouad Bennis & Damien Chablat, 2018. "Theoretical Complexity of Grid Cover Problems Used in Radar Applications," Journal of Optimization Theory and Applications, Springer, vol. 179(3), pages 1086-1106, December.
    11. Atlanta Chakraborty & Vijay Chandru & M. R. Rao, 2020. "A linear programming primer: from Fourier to Karmarkar," Annals of Operations Research, Springer, vol. 287(2), pages 593-616, April.
    12. 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.
    13. Anna Bogomolnaia & Hervé Moulin & Fedor Sandomirskiy & Elena Yanovskaya, 2017. "Competitive Division of a Mixed Manna," Econometrica, Econometric Society, vol. 85(6), pages 1847-1871, November.
    14. Vivian Welch & Christine M. Mathew & Panteha Babelmorad & Yanfei Li & Elizabeth T. Ghogomu & Johan Borg & Monserrat Conde & Elizabeth Kristjansson & Anne Lyddiatt & Sue Marcus & Jason W. Nickerson & K, 2021. "Health, social care and technological interventions to improve functional ability of older adults living at home: An evidence and gap map," Campbell Systematic Reviews, John Wiley & Sons, vol. 17(3), September.
    15. Persson, Petra & Qiu, Xinyao & Rossin-Slater, Maya, 2021. "Family Spillover Effects of Marginal Diagnoses: The Case of ADHD," IZA Discussion Papers 14020, Institute of Labor Economics (IZA).
    16. Menkhoff, Lukas & Miethe, Jakob, 2019. "Tax evasion in new disguise? Examining tax havens' international bank deposits," EconStor Open Access Articles and Book Chapters, ZBW - Leibniz Information Centre for Economics, vol. 176, pages 53-78.
    17. Ran Abramitzky & Roy Mill & Santiago Pérez, 2020. "Linking individuals across historical sources: A fully automated approach," Historical Methods: A Journal of Quantitative and Interdisciplinary History, Taylor & Francis Journals, vol. 53(2), pages 94-111, April.
    18. Werner Eichhorst & Ulf Rinne, 2017. "Digital Challenges for the Welfare State," CESifo Forum, ifo Institute - Leibniz Institute for Economic Research at the University of Munich, vol. 18(04), pages 03-08, December.
    19. Sant'Anna, Ana Claudia & Bergtold, Jason & Shanoyan, Aleksan & Caldas, Marcellus & Granco, Gabriel, 2021. "Deal or No Deal? Analysis of Bioenergy Feedstock Contract Choice with Multiple Opt-out Options and Contract Attribute Substitutability," 2021 Conference, August 17-31, 2021, Virtual 315289, International Association of Agricultural Economists.
    20. Tommaso Colussi & Ingo E. Isphording & Nico Pestel, 2021. "Minority Salience and Political Extremism," American Economic Journal: Applied Economics, American Economic Association, vol. 13(3), pages 237-271, July.

    More about this item

    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:arx:papers:1912.00459. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.