Efficient Fair Division with Minimal Sharing

Fedor Sandomirskiy and Erel Segal-Halevi

Papers from arXiv.org

Abstract: A collection of objects, some of which are good and some 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 in order 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.

Date: 2019-08, Revised 2022-04
New Economics Papers: this item is included in nep-des and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Published in Operations Research 70(3):1762-1782, 2022

Downloads: (external link)
http://arxiv.org/pdf/1908.01669 Latest version (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:arx:papers:1908.01669

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().