Rental Harmony: Sperner's Lemma in Fair Division

Abstract

We wish to explain a powerful approach to fair-division questions that unifies these problems and provides new methods for achieving approximate envy-free divisions, in which each person feels she received the “best” share. This approach was carried out by Forest Simmons [13] for cake-cutting and depends on a simple combinatorial result known as Sperner’s lemma. We show that the Sperner’s lemma approach can be adapted to treat chore division and rent-partitioning as well, and it generalizes easily to any number of players. From a pedagogical perspective, this approach provides a nice, elementary demonstration of how ideas from many pure disciplines—combinatorics, topology, and analysis—can combine to address a real-world problem. Better yet, the proofs can be converted into constructive fair-division procedures.

Tasks

Reproductions