Achieving Rental Harmony with a Secretive Roommate
2019
AbstractGiven the subjective preferences of n roommates in an n-bedroom apartment, one can use Sperner’s lemma to find a division of the rent such that each roommate prefers a distinct room. At the resulting rent division, no roommate has a strictly stronger preference for a different room. We give a new elementary proof that the subjective preferences of only n – 1 of the roommates actually suffice to achieve this envy-free rent division. Our proof, in particular, yields an algorithm to find such a division of rent. The techniques also give generalizations of Sperner’s lemma including a new proof of a conjecture of Meunier.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
13
Citations
NaN
KQI