IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1912.00459.html

Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations

Author

Listed:
  • Samuel Bismuth
  • Ivan Bliznets
  • Erel Segal-Halevi

Abstract

A set of objects is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If we consider the objects as indivisible, many instances of the decision problem: ``Is there a fair division of the objects among the agents'' are negative. In addition, this question is hard to solve even for most of the special cases. The latter reasons give us a good motivation to relax the problem for which the running time complexity is better, and the number of positive instances (admitting a fair division) will significantly grow. Whereas many works relax the fairness criteria, this paper introduces another relaxation: an agent is allowed to share a \emph{bounded} number of objects between two or more agents in order to attain fairness. The paper studies various notions of fairness, such as proportionality, envy-freeness, equitability, and consensus. We analyze the run-time complexity of finding a fair allocation with a given number of sharings under several restrictions on the agents' valuations, such as: binary, generalized-binary, and non-degenerate.

Suggested Citation

  • Samuel Bismuth & Ivan Bliznets & Erel Segal-Halevi, 2019. "Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations," Papers 1912.00459, arXiv.org, revised Jul 2025.
    • 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, . "Мaркування готової продукції як складова частина інформаційного забезпечення маркетингової діяльності підприємств овочепродуктового підкомплексу," Agricultural and Resource Economics: International Scientific E-Journal, Agricultural and Resource Economics: International Scientific E-Journal, vol. 2(01).
    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. 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.
    17. 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.
    18. Erkmen Giray Aslim, 2019. "The Relationship Between Health Insurance and Early Retirement: Evidence from the Affordable Care Act," Eastern Economic Journal, Palgrave Macmillan;Eastern Economic Association, vol. 45(1), pages 112-140, January.
    19. Edna P. Conwi & Alexander G. Cortez & Normita Ramos, 2016. "Effects of the Dualized Training Program on the Occupational Interest of the Students Enrolled in Bachelor of Science in Hotel and Restaurant Management," Indian Journal of Commerce and Management Studies, Educational Research Multimedia & Publications,India, vol. 7(1), pages 31-36, January.
    20. Nihan Akyelken, 2017. "Mobility-Related Economic Exclusion: Accessibility and Commuting Patterns in Industrial Zones in Turkey," Social Inclusion, Cogitatio Press, vol. 5(4), pages 175-182.

    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.