hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Easy level:

# Rental Harmony

 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.

Su, Francis E., et al. "Rental Harmony." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References:

Keywords:    fair division, game theory
Subjects:    other
Level:    Easy
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
4.14
current
rating
Click to rate this Fun Fact...
*   Awesome! I totally dig it!
*   Fun enough to tell a friend!
*   Mildly interesting
*   Not really noteworthy
and see the most popular Facts!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!