Munich Personal RePEc Archive

The undercut procedure: an algorithm for the envy-free division of indivisible items

Brams, Steven J. and Kilgour, D. Marc and Klamler, Christian (2009): The undercut procedure: an algorithm for the envy-free division of indivisible items.

[img]
Preview
PDF
MPRA_paper_12774.pdf

Download (863Kb) | Preview

Abstract

We propose a procedure for dividing indivisible items between two players in which each player ranks the items from best to worst and has no information about the other player’s ranking. It ensures that each player receives a subset of items that it values more than the other player’s complementary subset, given that such an envy-free division is possible. We show that the possibility of one player’s undercutting the other’s proposal, and implementing the reduced subset for himself or herself, makes the proposer “reasonable” and generally leads to an envy-free division, even when the players rank items exactly the same. Although the undercut procedure is manipulable, each player’s maximin strategy is to be truthful. Applications of the undercut procedure are briefly discussed.

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