You and your college friends decide to rent a house together, and the N of you have found a house with N bedrooms. However, the house has rooms of different sizes, different features, and each of you have different preferences.
Is it always possible to split the rent and price the rooms in such a way that each person will want a different room?
The answer is yes, under mild conditions!
The Rental Harmony Theorem (Su, 1999) says:
If the following conditions hold:
- (Good House) Each player finds some room acceptable in every pricing scheme,
- (Closed Preference Sets) A room that is preferred for a convergent sequence of prices will be preferred in the limit,
- (Miserly Tenants) In any pricing scheme which includes a free room, the most expensive room is never chosen,
then there will be a pricing scheme in which each person will prefer a different room!
By the way, if you drop the Miserly Tenants condition, the theorem is still true if you allow “negative rents”, i.e., you can still find a solution but it may be one in which you are paying one of the other housemates to live with you! (In that case you could ditch the subsidized housemate and use the extra room and extra money in other ways?)
The Math Behind the Fact:
The proof of this fact uses Sperner’s Lemma, and is a nice application of combinatorial topology to game theory. See the reference.
How to Cite this Page:
Su, Francis E., et al. “Rental Harmony.” Math Fun Facts. <https://www.math.hmc.edu/funfacts>.
References
F. Su, “Rental harmony: Sperner’s lemma in fair division”,
Amer. Math. Monthly, December 1999.
Fun Fact suggested by:
Francis Su