Figure 1

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.
<http://www.math.hmc.edu/funfacts>.

