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.

This is the latest version of this item.

[img] PDF
MPRA_paper_56585.pdf

Download (254kB)

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.

Available Versions of this Item

  • An algorithm for the proportional division of indivisible items. (deposited 12. Jun 2014 18:20) [Currently Displayed]
UB_LMU-Logo
MPRA is a RePEc service hosted by
the Munich University Library in Germany.