Robust Rental Harmony

Other web apps for splitting rent are bad, because they yield edge-case solutions that result in envy if your preferences change slightly (see below for an explanation). Use this one instead.

Table Entry

Total rent per month:

Number of rooms:

Number the rooms of your house starting at “0”, and have each housemate privately identify privately his/her least favorite room and write down a bid of $0 for that room. Next, have them privately write down how much extra they’d be willing to pay monthly (assuming they’re playing close-to-average rent) for each other room. Then, reveal those values, enter them into the Marginal Values table below, and click “go”!  Marginal values: Text Entry (optional) If you prefer, you can enter the data using this text format instead: Total rent per month: Marginal values: Why I wrote this algorithm When a group of friends rents a shared house, each housemate is assigned a certain room and pays a certain price, such that the total price adds up to the rent on the house. An “envy free” rent assignment is one where no one is envious of anyone else’s (room,price). Another way of saying it is that it’s a way of putting prices on the rooms such that everyone has a different favorite room. That would be nice, wouldn’t it? Well, under mild hypotheses about the preferences of the housemates, this turns out to always be possible! Francis Su called this situation “Rental Harmony”, and this algorithm represents an improvement over other online apps I’ve seen for achieving it. Use cases. This and other rental harmony solutions are most appropriate to apply when a group of people are moving into a house at the same time. For example, if 4 people are about to rent a house with a total monthly rent of \$4000, they can use this algorithm to see who gets which rooms and for how much. More interestingly, if Alice and Bob are already living in a five-room house with spaces for three more people to move in, they can fix the total rent for those three rooms, and let the newcomers use this algorithm to divide the rooms and rent between them, just as if the union of those three rooms were a house in itself.

Existing tools for calculating envy free rent division are suboptimal (e.g., spliddit.org), in that they tend to return price assignments that are “on the boundary of envy”: if someone’s preferences changes by an infinitesimal amount, the solution can cease to be envy free. And in real life, people’s preferences do tend to drift a little as time passes, so I prefer to assign rooms and prices in such a way that is “as far from envy as possible” to mitigate the risk of future envy as well.

I call this “Robust Rental Harmony”, and it’s what I wrote this algorithm to do! It uses some fun tricks with simplicial geometry to find the (room, price) assignment that is as far as possible from all the envy-freeness constraints, and runs in polynomial time. I’m working on a paper with my friend Jacob Tsimerman where we’ll explain it in more technical detail, but in the meantime, you can go ahead and use it to split your rent Super Optimally Fairly. I’ve tested it on many thousands of randomly-generated housemate preferences, and it should be good to go 🙂

When not to use this algorithm. When some people live in a house already and some new people are moving in, it would be a bit unfair to run this algorithm on the whole group because it might force the existing residents to change rooms when they wouldn’t otherwise have to. As such, the existing residents would (if rational) end up bidding higher for their own current rooms in order to prevent that. Similarly, this algorithm also doesn’t make a lot of sense for re-organizing a house that’s already occupied, because again, it will make folks will exaggerate the values of their own rooms in the bidding process to prevent moving. For the purpose of re-organizing a house, it’s better for housemates to just offer each other trades, like “I’ll let you have my room for its current price minus $X/mo, if you let me have yours at its current price plus$X/mo.”, unless it looks clear that a subgroup of three or more people are all definitely going to shuffle rooms for some reason.

Thanks to Chelsea Voss for helping me build a web interface for the algorithm; you rock Chelsea! See https://github.com/critcha/rentdivision/ if you want to view the source.