IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v70y2022i3p1762-1782.html
   My bibliography  Save this article

Efficient Fair Division with Minimal Sharing

Author

Listed:
  • Fedor Sandomirskiy

    (Department of Humanities and Social Sciences, California Institute of Technology (Caltech), Pasadena, California 91125; International Laboratory of Game Theory and Decision Making, Higher School of Economics, St. Petersburg 194100, Russia)

  • Erel Segal-Halevi

    (Computer Science Department, Ariel University, Ariel 40700, Israel)

Abstract

A collection of objects, some of which are good and some of which are bad, is to be divided fairly among agents with different tastes, modeled by additive utility functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then a fair division may not exist. What is the smallest number of objects that must be shared between two or more agents to attain a fair and efficient division? In this paper, fairness is understood as proportionality or envy-freeness and efficiency as fractional Pareto-optimality. We show that, for a generic instance of the problem (all instances except a zero-measure set of degenerate problems), a fair fractionally Pareto-optimal division with the smallest possible number of shared objects can be found in polynomial time , assuming that the number of agents is fixed. The problem becomes computationally hard for degenerate instances, where agents’ valuations are aligned for many objects.

Suggested Citation

  • Fedor Sandomirskiy & Erel Segal-Halevi, 2022. "Efficient Fair Division with Minimal Sharing," Operations Research, INFORMS, vol. 70(3), pages 1762-1782, May.
    • Handle: RePEc:inm:oropre:v:70:y:2022:i:3:p:1762-1782
    DOI: 10.1287/opre.2022.2279
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2022.2279
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2022.2279?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
    ---><---

    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:oropre:v:70:y:2022:i:3:p:1762-1782. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.