An algorithm for the proportional division of indivisible items

Steven Brams (), D. Marc Kilgour and Christian Klamler

MPRA Paper from University Library of Munich, Germany

Abstract: An allocation of indivisible items among n ≥ 2 players is proportional if and only if each player receives a proportional subset—one that it thinks is worth at least 1/n of the total value of all the items. We show that a proportional allocation exists if and only if there is an allocation in which each player receives one of its minimal bundles, from which the subtraction of any item would make the bundle worth less than 1/n. We give a practicable algorithm, based on players’ rankings of minimal bundles, that finds a proportional allocation if one exists; if not, it gives as many players as possible minimal bundles. The resulting allocation is maximin, but it may be neither envy-free nor Pareto-optimal. However, there always exists a Pareto-optimal maximin allocation which, when n = 2, is also envy-free. We compare our algorithm with two other 2-person algorithms, and we discuss its applicability to real-world disputes among two or more players.

Keywords: Fair division; indivisible items; proportionality; envy-freeness (search for similar items in EconPapers)
JEL-codes: C71 C78 D61 D63 D74 D78 (search for similar items in EconPapers)
Date: 2014-05
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://mpra.ub.uni-muenchen.de/56587/1/MPRA_paper_56585.pdf original 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:pra:mprapa:56587

Access Statistics for this paper

More papers in MPRA Paper from University Library of Munich, Germany Ludwigstraße 33, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Joachim Winter ().