Efficient Fair Division with Minimal Sharing

Fedor Sandomirskiy () and Erel Segal-Halevi ()
Additional contact information
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

Operations Research, 2022, vol. 70, issue 3, 1762-1782

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.

Keywords: Market Analytics and Revenue Management; fair division; polynomial-time algorithm; discrete objects; fractional Pareto-optimality; envy-freeness; proportional fairness (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2279 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:3:p:1762-1782

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().