Splitting Apartment Rent – A Case of Fair Division

Paying rent – it’s an annoyance that many of us have to deal with on a regular basis. But, it’s also a source of interesting mathematics. Splitting rent in an equitable way is a classic problem in fair division, one which I’ve posed to my own students in the following manner:

Suppose that three people are renting a house together and they want to fairly split the rent.  The house has one master bedroom and two (equally sized) smaller bedrooms.  The person who takes the master bedroom will have their own bathroom, while the other two will have to share a bathroom.  How can these three people equally split the rent?

I received a wide variety of responses to this question, ranging from the simplest case of dividing the rent into three equal pieces to more complicated schemes where the rent was divided proportional to the square footage of the bedroom. Some students even went so far as to ask, is there even a way to fairly divide the rent so that everyone gets the bedroom they prefer?

Looking for an answer to my students’ question led me to the housemates problem (or room assignment-rent division problem). In this problem, several people agree to rent a house together. Then, they must allocate the rooms in the house while also dividing the rent, both in a way that everyone agrees is fair.

One approach to fairly assign rooms and divide the rent is a modification of the method of sealed bids. Suppose we are in the situation described above, with three friends in a house where there is a master bedroom with private bath, and two (smaller) bedrooms with a shared bath. Each friend will privately decide what each room is worth to them, with the restriction that the “value” of the three rooms for each person adds up to the total rent. Then, each friend is assigned a room based on these “values” in such a way as to maximize th

e total money paid. Now, we have an assignment of people to rooms that everyone will consider fair (where “fair” means that no one is forced to pay more for a room than they feel it is worth). But what happens if the maximized total money paid is more than the rent? The simplest method is to divide the surplus evenly among the three friends, though more complicated strategies are possible.

In general, we ask, is there always a way to assign rent so that each person will prefer a different room? While this task may sound impossible, it can be shown that under mild assumptions, the answer is yes! We have the following theorem:

Rental Harmony Theorem: Suppose  housemates in an -bedroom house seek to decide who gets which room and for what part of the total rent. Also suppose the following conditions hold:

1. (Good House) In any partition of the rent, each person finds some room acceptable.
2. (Miserly Tenants) Each person always prefers a free room (one thatcosts no rent) to a non-free room.
3. (Closed Preference Sets) A person who prefers a room for a convergent sequence of prices prefers that room at the limiting price.

Then, there exists a partition of the rent so that each person prefers a different room.

The assumptions that we must place on the problem are mild, and model the real world application nicely. The first condition ensures that the problem is well-posed, basically saying that each person will find at least one room acceptable (which is reasonable, because otherwise they wouldn’t have agreed to rent the house in the first place). The second condition is not always applicable to the real world situation. There are cases where someone would be willing to pay a little bit of rent for a room that is nicer than a free one. However, this condition can be relaxed to say that the person does not always have to choose the free room. Finally, the last condition allows for someone to equally prefer two rooms (in which case they can be assigned either room).

But how can we prove this? The answer can be found in a surprising place – the land of combinatorics and Sperner’s Lemma!

Sperner’s Lemma: Any Sperner-labeled triangulation of an -simplex must contain an odd number of fully labeled elementary -simplices. In particular, there is at least one.

Using Sperner’s Lemma, we can create a proof that leads to a constructive fair-division procedure for the room assignment-rent division problem. Suppose there are  housemates, with  rooms to assign. In addition, suppose that the total rent is 1. Then, the set of all pricing schemes forms an  simplex in .

We can triangulate this simplex and label each vertex of the triangulation with the name of one of the housemates (who will be considered the “owner” of that vertex). Each vertex corresponds to a p

ricing scheme for the rooms. We proceed by constructing new labelings by asking the owner of each vertex: “If the rent were to be divided according to this pricing scheme, which room would you choose?” Here is where condition (1) is needed – no matter the pricing scheme, each person will prefer at least one room (ties can be broken randomly). Such a labeling is shown below for  people.

This labeling is not exactly a Sperner labeling. However, with slight modifications, we can find a Sperner-like combinatorial lemma that applies to this rent-partitioning simplex. Once we have this modified lemma, we proceed by taking finer and finer triangulations, which ultimately leads to a rent-division scheme in which all housemates prefer different rooms. This process has been implemented to provide an online fair division calculator that can equitably divide such things as rent, chores, or other goods. So the next time you and your roommates need to split the rent in a fair way, head online and let the math figure it out for you!

Sources:
Su, Francis Edward. Rental Harmony: Sperner’s Lemma in Fair Division. American Mathematics Monthly, 106 (1999), 930-942.
Fair Division Calculator: http://www.math.hmc.edu/~su/fairdivision/calc/