Munich Personal RePEc Archive

An algorithm for the proportional division of indivisible items

Brams, Steven J. and Kilgour, D. Marc and Klamler, Christian (2014): An algorithm for the proportional division of indivisible items.

[thumbnail of MPRA_paper_56585.pdf] PDF

Download (254kB)


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.

Atom RSS 1.0 RSS 2.0

Contact us: mpra@ub.uni-muenchen.de

This repository has been built using EPrints software.

MPRA is a RePEc service hosted by Logo of the University Library LMU Munich.