×

Rental harmony: Sperner’s lemma in fair division. (English) Zbl 1010.05077

In this nice article the author proves the following theorem: Suppose \(n\) housemates in an \(n\)-bedroom house seek to decide who gets which room and for what part of the total rent. Also, suppose that the following conditions hold: (1) In any partition of the rent, each person finds some room acceptable. (2) Each person always prefers a free room (one that costs no rent) to a non-free room. (3) A person who prefers a room for a convergent sequence of prices prefers that room at the limit price. Then there exists a partition of the rent so that each person prefers a different room. The proof is essentially based on an \(n\)-dimensional version of Sperner’s lemma on labelling of triangulations of a triangle using some dualization. This approach was first carried out by F. Simmons for envy-free cake cutting which is also described in this paper. The proofs can be converted into constructive fair-division procedures.

MSC:

05D05 Extremal set theory
05A18 Partitions of sets
91B08 Individual preferences
PDFBibTeX XMLCite
Full Text: DOI Link