# Is an Auction the Best Way to Solve the Roommate/Rent Dilemma?

(Photo: Matthew Jording)

We’ve blogged before about the very common roommate/rent dilemma — that is, how to fairly split rent among roommates given that different rooms have different features. A reader named Michael Jancsy writes in with an auction solution and a request for feedback:

I recently designed an auction website [called “The Rent Is Too Damn Fair”] to help friends split apartments … The auction works by allowing each roommate to bid on each room in an apartment, and then identifies the permutation of roommates to rooms with the largest consumer surplus (sum of all bids minus rent paid to landlord) to decide who should live in what room. Each person’s rent is then calculated by dividing the surplus evenly over the occupants, so that the difference between a person’s bid and the rent paid is the same for each person.

It’s a pretty rudimentary design, but I hope it will be superior to the methods more commonly used, such as basing rent only on square footage. I am somewhat concerned, though, that it is not strategy-proof.

I believe what Michael means by “strategy-proof” is that some people will likely try to game the auction to their advantage. So: feel free to give him your general feedback but especially with an eye toward his model’s shortcomings.

#### Lia

Unfortunately this system doesn't seem to take the 'couples' issue into consideration which is a growing issue in shared living spaces. For example, 4 rooms, 4 people is somewhat easy to split up either evenly or by room size. In this scenario, each room's occupant is then sharing common space evenly because each room only has 1 person. It gets much more complicated with couples. Sure they can pay for the bigger room, but they also use twice as much fridge space, make twice as much of a mess etc. Dividing up the use of the common space, then, really complicates the matter. When we come up with a formula for THAT, I'll be shouting from the roof tops.

#### Andrew

If I don't mind the worst room, I can just bid \$1 on all of them.

You could easily set a minimum rent.

#### Daniel

I can get any room by bidding \$100 on that one and \$1 on the other two, also I get to pay a really low rent (under \$100).

I think the sum of the 3 rooms for each person should be the same, and each distribute that sum between the rooms. for example: the total rent is \$1500, so I distribute the \$1500 like \$400 - \$450 - \$650, the other two do the same and then the algoryth runs selecting the best room for each one.

#### Bill

In this structure of dividing the surplus equally the person making the least contribution to the "surplus" has a disproportionate benefit so your system is already gamed. Seems the appropriate method would be to divide the surplus in proportion to the rents bid thus adjusting to the actual rent paid. Second question how does your system handle a bid of \$1 or a situation when total bids are less than the actual rent?

#### Beigemartin

I really like the idea - we did something similar but less formal, this auction looks good, but probably has a few holes.

The first strategy which struck me with this system here is to bid zero for all rooms. You will get a room and pay little rent. Following that if other people do likewise there may not being enough maximum bids to cover the rent - what happens to the system here?

Is there a Nash equilibrium at all bids being zero?

#### Joe W

It's a good idea, but does is it biased towards someone who has more to spend? They may not actually value the room any more than the other person, but can afford to throw more money at the situation.

If out of a group someone *really* want the room but can only afford \$500, and someone else doesn't really care but can easily afford \$550 - then the amount offered trumps all other considerations.

Yup, that's the point, after all.

#### KevinH

The only blanket strategy that I can see is if you didn't care which room you got, you might be able to pay very little/no rent. Just bid \$1 on each room. Assuming you allow for negative surplus (and I think the way the code would be written you'd have to explicitly check for that for it to even be noticed) then you could basically make the other faithfully betting roommates split your rent. You'd pay somewhere <= 1/n of your theoretical rent.

However, I wouldn't worry too much about these type of extreme strategies. As long as you show everyone involved all of the bids after, then free-riders will know that they will be found out, and therefore probably won't even try to screw over their new roommates in the first place. Even when they do attempt to get dirt cheap rent, there's nothing to say your website is legally binding, so the roommates may fall back onto a plan B after seeing their supposed friend's sneaky play.

#### KevinH

Couple more thoughts.

The tendency to underbid will stronger the more equal the room quality is. However in those situations people probably didn't need your site in the first place.

You could completely destroy the incentive to underbid if you allowed there to be fewer rooms than people. Then the person who bids the least won't get to live there! Might start more fights than than the system would save however...

#### Seminymous Coward

The auction is presumably only between a number of bidders equal to the number of rooms. As such, a \$0 bid for all rooms would give a non-picky bidder a final rent equal to the negative of their share of the surplus. I suppose that "surplus" would actually be negative in this case, barring extravagant bids by the others, so that might not constitute a problem.

Negative bids are definitely problematic, but you forgot to ban them.

#### Seminymous Coward

I apologize for the double post, but, well, there are no edits.

For a concrete example of the possible issue with \$0 bids, one can take your sandbox example with Amy's bids zeroed out to get these results: Amy lives in Room 3 for \$16.67. Peter lives in Room 1 for \$816.67. Moe lives in Room 2 for \$966.67.

#### Jeff

To avoid problems with underbidding, what if the minimum bid is square-footage based, which means that if there is a clear "better" room, it will only be bid *up* from there, and all other rooms will be cheaper for the people willing to settle.

Ex: 3-bedroom, 1200sf apartment, \$4500 (I'm thinking NYC here...) All 3 bedrooms are 200 sf and common areas are 600sf total, no room has its own bathroom or anything.

So each room starts at \$1500. Say one room has the southern exposure and larger closets, and roommate A bids that up to \$2000. B & C aren't willing to touch that, but roommate B is willing to pay a little extra for the second bedroom, which has, I don't know, a less-awkward layout. He bids \$1600. So now they both pay what they're willing and C, who was willing to take any room, only has to pay 900. There's less of a free-rider problem, but C still gets a deal.

You could also do it where the highest bid end up paying X% or \$X over the next-highest bid. So above, if A had bid \$2000 but B had bid \$1700, A would only have to pay \$100 or 10% or whatever more than B's bid. This would keep someone from having to overpay because they wanted to secure a specific room.

Or maybe that's fair...

#### Andy

This system is not jealously-proof. In other words, upon using the website and seeing the resulting rents, it's possible that Person A will be jealous of the room/rent that person B got and will regret participating in this particular system.

I saw an academic paper long ago that guaranteed (subject to reasonable restrictions) the existence of a jealously-free rent arrangement: a set of prices for each room where each person will have a different first choice of room. Then you just give everyone their first choice and they are all happy (or at least not jealous of anyone else's room/rent). I don't believe the paper gave a method for determining these prices but in practice it is pretty easy to iterate until you get it.

#### Seth

I remember one of my college professors (Professor Su) working on this... this is the relevant paper: https://docs.google.com/viewer?url=http%3A%2F%2Fwww.math.hmc.edu%2F~su%2Fpapers.dir%2Frent.pdf from (http://www.math.hmc.edu/~su/papers.html).

This might be the paper you were thinking of.

#### Mudlock

I was reading about a solution to this just the other day: http://agtb.wordpress.com/2012/08/15/fair-division-and-the-whining-philosophers-problem/

The downside is that it's iterative (i.e., slow) but the up-front time investment is surely worth avoiding the creeping hatred of inequitable rent.

#### Steven

My buddies and I on a ski trip came up with an easy efficient auction that solves this problem. Basically take the worst room and put 100% of the rent on that room. Then each person bids on the other rooms which reduce the worst room’s price. Eventually the worst room will be cheap enough that someone will take it. Example. Three rooms with rent of \$300
Person 1 bids \$50 for Master
Person 2 bids \$25 for comfy room
Person 3 doesn't want to pay \$225 for the worst room so they bid \$50 for comfy room
Person 2 now doesn't have a room and doesn't want to pay \$200 for worst room so he bids \$75 for Master
Etc.

Everyone pays what they are willing to pay for the room they want. As a bonus it keeps gaming the system to a minimum. Yes someone can bid up a room they don't want but they may get stuck paying for it. Only downside is that you have to wait to get outbid before bidding on another room. One winter the worst room went for \$25 and I would have taken it for \$50 but was stuck with my last bid. (We discussed an end of round clearing where anyone could out bid anyone else but decided that it would be a real pain and lead to gaming the system)

#### Jeremy Kay

As many people have pointed out, the current method does not work very well because of incentives to under-bid so I would throw out your way of considering consumer surplus because of the under-bidding problem. Rather than the current method, I would suggest a system where the loser (ie. the person who lost all the other bids and ends up with the worst room) pays the rents less the total of all other bids. This system does not work very well for two roommates with different upper rent limits; however, should work well for most others.

#### Jonah

An important thing to make sure is that each person's bids sum to the total rent, so that they're giving a plausibly honest assessment of the values of the rooms. (This also prevents gaming of the system IF you don't know anything about your housemates' preferences.) This will avoid the easy problems mentioned by others, where you can list each room as \$0.

But unfortunately, even with that condition, it's still possible for someone to pay negative rent even when the bids are all positive, if there's some room that everyone agrees is very undesirable. Consider a \$100/month apartment with four rooms and housemates whose bids (for room A, B, C, D, respectively) are [40,30,29,1], [30,30,38,2], [27,50,20,3], and [32,32,32,4]. It's easy to find the maximum surplus here (in fact each room has a unique highest bidder), but the last roommate ends up paying negative four dollars per month after subtracting her share of the surplus.

Unfortunately, I believe any possible algorithm for 4 or more roommates is susceptible to either negative rents (like this one) or envy (some roommate thinks another one is getting a better deal). I think this is due to Brams and Kilgour in "Competitive Fair Division", but I unfortunately I don't have the right journal access.

#### Jim Hughes

I have used a similar system in the past that I believe is fair and very hard to game. Interested to see the problems people can find with it:

My situation was 5 guys renting a 5 bedroom house. Before starting, we agreed on a ranking of the rooms by order of preference, 1 through 5.

First, we have a round of bidding for the most desired room. Rent for the house was \$2000, so opening bid for this room was \$2000/5 guys = \$400. Everyone is allowed to bid, and eventually the room is won at \$500.

Next, we bid on the second most desired room. Remaining rent is \$2000 - \$500 paid for the first room = \$1500. Therefore, the starting bid is \$1500/4 remaining bidders = \$375. Room 2 is almost as good, and it goes for \$480.

Repeat with the third most desired room: \$2000 rent - \$500 (room 1) - \$480 (room 2) = \$1020 remaining in rent/3 bidders = \$340 opening bid. There is a larger drop in quality from room 2, and room 3 goes for \$390.

With 2 roommates remaining, there is \$630 left for rooms 4 and 5. They're almost identical, though one shares a wall with the bathroom. One roommate is willing to spend \$5 extra to be away from the bathroom. He pays \$320 for room 4, and the last roommate gets room 5 for \$310.

Potential problem:
If the roommates can't agree on an order of preference, then they can vote and the opinion of the majority will prevail. You only need 2 people to agree that a room is better for the bidding to be fair. If you think room #2 is better than room #1, then you simply abstain from bidding on room #1.