Munich Personal RePEc Archive

Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm

Brams, Steven J. and Kilgour, D. Marc and Klamler, Christian (2013): Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm.

[img]
Preview
PDF
MPRA_paper_47400.pdf

Download (240kB) | Preview

Abstract

Many procedures have been suggested for the venerable problem of dividing a set of indivisible items between two players. We propose a new algorithm (AL), related to one proposed by Brams and Taylor (BT), which requires only that the players strictly rank items from best to worst. Unlike BT, in which any item named by both players in the same round goes into a “contested pile,” AL may reduce, or even eliminate, the contested pile, allocating additional or more preferred items to the players. The allocation(s) that AL yields are Pareto-optimal, envy-free, and maximal; as the number of items (assumed even) increases, the probability that AL allocates all the items appears to approach infinity if all possible rankings are equiprobable. Although AL is potentially manipulable, strategizing under it would be difficult in practice.

UB_LMU-Logo
MPRA is a RePEc service hosted by
the Munich University Library in Germany.