Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  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
All rights reserved.

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

Rental Harmony

Figure 1
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>.

Share

References:
Keywords:    fair division, game theory
Subjects:    other
Level:    Easy
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
4.12
 
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!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

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