A Caltech Library Service

Efficient Fair Division with Minimal Sharing

Sandomirskiy, Fedor and Segal-Halevi, Erel (2022) Efficient Fair Division with Minimal Sharing. Operations Research, 70 (3). pp. 1762-1782. ISSN 0030-364X. doi:10.1287/opre.2022.2279.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Sandomirskiy, Fedor0000-0001-9886-3688
Segal-Halevi, Erel0000-0002-7497-5834
Issue or Number:3
Record Number:CaltechAUTHORS:20220914-906538200
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116911
Deposited By: Tony Diaz
Deposited On:22 Sep 2022 19:40
Last Modified:22 Sep 2022 19:40

Repository Staff Only: item control page