How to allocate rooms in a rented space in the fairest fashion?

July 26, 2005 10:18 AM

A house with 7 rooms of varying quality is being split between 7 college students. The rent is a fixed amount. The students place differeng importance on the value of their money vs. the size of the rooms they will get. What is the best method of allocating the rooms so that everyone is optimally happy?

Disclaimer: I'm a complete novice at economics, but thought it would be interesting to see how it might be applied to solve a day-to-day problem, which is, I might add, real.

Not everyone agrees on which rooms have the highest quality.

I realize that optimal utility can be measured several different ways -- is there a method that would optimize for the most salient possibilities, i.e.:

-sum of the utilities
-maximizing the minimum utility
-maximizing the median utility
-etc.

When I say method I mean an actual way these rooms could be allocated. For example, one such possibility is a room auction where rooms are auctioned off one by one and the total rent remaining to be divided lessened by the winning amount each time. But then in which order should the rooms be auctioned, given that not everyone agrees about which rooms are the best rooms to have?

Or perhaps first, second, third, etc. choices of rooms should be auctioned off? What might be the problems with that system?

Any help would be appreciated. This is a real problem, by the way, not just an academic exercise!

posted by shivohum to human relations (38 comments total)

You could try to have them write their first two preferences down. Depending on how evenly the preferences are divided, they'd get one of their top two choices.

Or have them draw randomly which room they get and let them figure out amongst themselves through swapping and such what room they get.
posted by geoff. at 10:33 AM on July 26, 2005

One possiblitity is to model this using the Stable Marriages Problem. Have each person make a list of what rooms they want and in what order. Then have each room make a list of what tenants they want and in what order.
Err, since most rooms can't speak English, you'll need to make the lists for the rooms based on how much the tenant is paying in rent.

(Sorry, no real-life suggestions from me, just academic exercises.)
posted by CrunchyFrog at 10:34 AM on July 26, 2005

Or perhaps first, second, third, etc. choices of rooms should be auctioned off?

That would be my intuition, but in order for the people left at the end to not get shafted, you'd probably have to require that the first few rooms go for some minimum bid which is greater than (total rent/7).
posted by juv3nal at 10:34 AM on July 26, 2005

You want a fair division. There's an applet here for what are called "envy-free chore divisions", and which also claims to find solutions to "rent problems" (!). Here's a PDF of an American Mathematical Monthly article by the same fellow, that's right up your alley:

My friend's dilemma was a practical question that mathematics could answer, both elegantly and constructively. He and his housemates were moving to a house with rooms of various sizes and features, and were having trouble deciding who should get which room and for what part of the total rent. He asked, "Do you think there's always a way to partition the rent so that each person will prefer a different room?" ... As we shall see, with mild assumptions, the answer is yes.

Or, if you're feeling frisky, you could try a version of the fair division algorithm from Cryptonomicon.
posted by gleuschk at 10:40 AM on July 26, 2005

My answer's of academic interest, but this sort of problem comes up in several instances, like taxation and allocating inheritances, and is known as the cake-cutting problem or fair division. There are methods for dividing resources in a 'fair' and 'envy-free' way. There are whole books on it, actually.
posted by driveler at 10:42 AM on July 26, 2005

Here's a better explanation of Su's algorithm than the one in the paper I linked above.
posted by gleuschk at 10:47 AM on July 26, 2005

Here's what we did:

1. Assign each room some number of "units" based on its quality. For example, room one may deserve 3 units, while rooms two and three may both deserve 5 units.

2. Divide the rent by the total number units.

3. Multiply the "unit amount" by the number of units each room receives to determine rent.
posted by defreckled at 10:48 AM on July 26, 2005

Figure out the top 3 rooms - decided by everybody writing down their requested room and picking the 3 most selected in the top 2. Or top 3.

Then the bidding would start at $100 (or more?) more than the total rent / 7, for each room, in a random oder. This would mean that roommates who want nice rooms would pay more for them than roommates who either want smaller rooms or are of more limited means. I'd propose that the minimum-premium paid for each of the top 3 rooms be consistent across all of the three rooms.

Then the remaining four people can split the less desireable rooms, either evenly (based on the remaineder of the bidding), or they could keep bidding. But that's probably not necessary.

Here's what I can't figure out. Say that I'm the poorest kid in the house. And say that, because I know that, I don't really much care which room I get -- though I want it to be as cheap as possible (maximizing my benefit). Should I game the system by choosing as my "top choice" rooms the rooms that I think will sell for the highest price? Or should I pick the room I want (smallest, crappiest, windowless cell) and then second, the second crappiest room, and so on?

I guess I'm asking what business is it of people who DON'T want to pay more than 1/7th of total, to determine what the "best" room is? Since that person (or people) does not even want one of the bigger/better rooms, why shouldn't he recuse himself from the bidding AND the selection? I can't decide about this. If you think of the house as a community, then it does make sense to me. But if you think of it as 7 independent actors, it doesn't make sense (and the cheaper students should stay out of selecting which room is best or 2nd best).

P-S-and-by-the-way, good luck trying to live with 6 other people.
posted by zpousman at 10:49 AM on July 26, 2005

The problem with an auction is that valuation might differ from ability to pay, causing that most dreaded of all things: Pareto-inferiority.

I'd suggest starting with a lottery and then allow trading.

For example, people might agree that an ex-ante fair system would be for everyone to pay 1/7 of the rent, and to assign people randomly to rooms. Then allow people to trade: I'll pay $X of your rent if you switch rooms with me. This allows a poor student with high valuation of the room to retain the room.

Or they might agree on some initial schedule of rents based on room size and obvious amenities, and then assign people randomly, and then allow trading.
posted by ROU_Xenophobe at 10:50 AM on July 26, 2005

You could do the auction in relative units. For example, start the opening bid for each room at 100 (regardless of the actual cost), and let people bid accordingly. Then when all 7 rooms have been auctioned, take the total amount of the final bids, and scale that to the total amount of the rent. In this scenario the people wouldn't know how much their bids are actually going to cost until the the thing is over, but they do know that the higher they bid the higher the percentage of the total they'll be paying.

So that the order doesn't really matter, you could do the auction for all 7 at once -- people just keep giving new bids for any room until there are no new bids.

For example, suppose the 7 bids are 100, 100, 125, 150, 150, 200, 210 and the total rent is $2500. Total of the bids comes to 1035, so then just multiply each final bid by (2500 / 1035 = 2.42) to get the actual rent amount. So the people that bid 100 end up paying $242, the person that bid 210 pays $508, and so on.
posted by Rhomboid at 10:53 AM on July 26, 2005

glueschk's links answers my problem. Askmefi just answers a question I didn't even know I had!? </ voice = "satisfied customer">
posted by zpousman at 10:54 AM on July 26, 2005

Here's an idea: Add up the square feet of each room. Ensure that for extra amenities a penalty is assigned (say 1.5x sq feet for the size of walk in closets, 2x sq feet for the size of private bathrooms). Divide the entire rent for everything that needs to be realized by the size of the rooms, giving you $/sq feet and just charge based on that.

It only makes sense that people who are using more space pay more.

If the prices end up being such that nobody wants the more expensive rooms, you would adjust the pricing of them down accordingly (bringing the prices on the low end up to match) until an equilibrium is reached.

The best part is if you do this you'll also have the floor plan mapped out, which is invaluable to people bringing in lots of furniture.
posted by shepd at 11:10 AM on July 26, 2005

I had the same situation in undergrad. We just let the landlord take care of it. He set the prices and we settled who stayed in which room.
posted by jmgorman at 11:34 AM on July 26, 2005

ROU_X makes a very good point that I think would be worth considering.
posted by dame at 11:35 AM on July 26, 2005

I like shepd's idea. When I was an undegrad, I shared a townhome with 2 friends. Each of the bedrooms was a different size, and the larger bedrooms paid more rent. It worked out well because I was willing to take the smaller room in order to save money on rent, while my roommates were able to work out the larger rooms among themselves based on who was willing to pay the most money. And we all agreed that if anyone was incredibly unhappy halfway through the year, we would re-evaluate and switch rooms.
posted by geeky at 11:44 AM on July 26, 2005

The desireability of a room may have nothing to do with its size. I would want a quiet room, low traffic (maybe farthest from the main door and kitchen), warm (if it's in the north), and with a good window and closet space. I'd take the smallest room if it had all that.

Run an auction like you said. If the total house rent due is 700 dollars (to make the math easy), start with each room priced at 100 dollars. Then let people bid for the most desired room (vote on which rooms you like best, second best, and third best), but let that drive down the prices of the other rooms equally. If room A is bid up by 60 dollars over the base cost by the time bidding stops, the winner will pay 160 dollars and bidding for each of the other rooms starts at 90 dollars. The you take bids on the next most desired room.

Do not consider who can afford what. The better-off students will drive the prices down for the others, so it works out fairly enough. If the worst room is really unwanted, it will at least be cheap as hell, and the person stuck with that room can spend the extra money on earplugs, sedatives, trips home, or whatever it takes to make him or her feel better.

After things are settled, any changes of mind can be taken care of by private agreements to swap rooms. Just get it all in writing before people start living there.
posted by pracowity at 11:53 AM on July 26, 2005

I think common rooms (kitchen, living room, common bathroom) should account for some base rent.

This way there is there is a minimum per-room rate for the least desirable room that reflects these basic amenities, so that others don't feel like the cheapest person is getting a free ride.

Plus a stopwatch timing all hot showers for when utility bills arrive.
posted by BleachBypass at 12:20 PM on July 26, 2005

In this scenario the people wouldn't know how much their bids are actually going to cost until the the thing is over, but they do know that the higher they bid the higher the percentage of the total they'll be paying.

Isn't that inherently problematic? You run into the real likelihood that people could bid "beyond their means" without knowing it because they have no idea how much actual money it's going to come out to.
posted by juv3nal at 12:21 PM on July 26, 2005

ROU is absolutely right about the auction. With no opposing bidders fair prices can't be found, so it can't work with such a small sample size.
posted by Chuckles at 12:26 PM on July 26, 2005

Why not go ahead with a straight economic solution? Consider a more simplified version of pracowity's proposal. Have everyone bid a "premium" on the room or rooms they want. Highest bidder gets the room. Subtract the cumulative premiums from the total rent and split the remainder by seven.

The only contingencies you would need to look out for: If someone is the highest bidder on more than one room, then that person is stuck with their highest bid. If there are no bids on multiple rooms, then assign at random.

As far as the "overpriced room" problem: If you trust your roommates to do math during the bidding process, rather than blindly bidding up the price, then it shouldn't be a problem.
posted by Scooter at 12:37 PM on July 26, 2005

Don't auction off rooms, auction off first picks. Not everyone will necessarily have the same favourite.

Get everyone to list their room preferences. Bid for first pick. The starting bid is an equal share of the rent. The winner gets the first room on their list. Remove that room from everyone else's lists. Repeat.
posted by RobotHero at 1:01 PM on July 26, 2005

Make up a chart with each room on it. Each room is initially priced at rent/7.

Put everyone in a circle or line, and randomly choose who goes first.

The person whose turn it is can place a bid on a room of their choice, unless they're already the high bidder on a room, in which case they are skipped that round.

Repeat until everyone is high bidder on a room.

You'll probably end up with more bid than the rent. Excess goes first to utilities, then buying nice stuff for common areas--furniture, utensils, group dinners, housekeeping services, etc.
posted by trevyn at 1:43 PM on July 26, 2005

Auction off first picks doesn't work for the person who wants the small room/cheap rent. Many of these "bidding" schemes are like that: How do you bid for "I just want the cheapest"?
posted by duck at 1:53 PM on July 26, 2005

This is interesting, because we are seeing a split between allocating the rooms and pricing them. Which is reasonable.

To price the rooms, I suggest this: give everybody, say, 35 points. Each person assigns each room some point rating (minimum of 1 for a dank, crumbling closet). Then total up the values. The rents will be assigned in proportion to the room scores. Note that this omits the common areas--add some constant value to all the scores to cover that.

To assign the rooms, I suggest a closed-bid auction, again using completely abstract points. Say each person has 10 points to bid. If you've got a room you doubt others will want, you can safely bank all 10 points on that room. If there are three you want, you're going to need to decide how badly you want them. Ties will be resolved by arm-wrestling.
posted by adamrice at 2:14 PM on July 26, 2005

The problem with an auction is that valuation might differ from ability to pay.

ROU is absolutely right about the auction. With no opposing bidders fair prices can't be found, so it can't work with such a small sample size.

With all due respect - since there is a fixed total amount to be paid, a bidder who is outbid still benefits - he/she ends up paying less of the total amount of rent. It isn't true that all roommate have to have identical incomes in order for things to be fair.
posted by WestCoaster at 2:14 PM on July 26, 2005

Duck said: "Auction off first picks doesn't work for the person who wants the small room/cheap rent. Many of these "bidding" schemes are like that: How do you bid for "I just want the cheapest"?"

Easy. Don't bid, and take what's left at the end.
posted by RobotHero at 2:33 PM on July 26, 2005

Go back to gleuschk's first comment and links. Ignore most everyone else here. Also note this paper [pdf] which describes the algorithm used by the HRS option on the applet--it's easy enough to do by hand if you don't trust the applet.

This method has the advantage that not only is everyone satisfied; they're also non-envious, meaning they wouldn't trade with anyone else's room/rent combination even if they could. Many of the procedures suggested here do not meet this criteria. For example, pracowity's suggestion (auction off rooms individually, with each auction result potentially lowering the starting bid for subsequent rooms) may result in someone saying, "Gee, I know I bid $125/mo for my room, but if I knew I could have gotten the crappy room for only $20/mo I would have taken that instead!" A fair division avoids this sort of situation.
posted by DevilsAdvocate at 2:48 PM on July 26, 2005

duck, you're right. But, there's a solution: just pass. If you're bidding for first pick, then don't bid. You get the later/last pick, and either a equal share of the rent or an equal share depressed by the premium the higher bidders paid.
posted by RikiTikiTavi at 2:55 PM on July 26, 2005

Step 1: divide the total rent (say $700) by 2 ($350). Each roommate pays a base amount that's an equal share of this ($50).
Step 2: briefly discuss among the 7 what makes each room more or less desirable (size, location, etc.)
Step 3: half of you (probably the 3 who care least) decide how to split the remaining rent ($350) among the 7 rooms without any more input from the other half (those who care most); you now have a total price associated with each room (ranging, say, from $70 to $150)
Step 4: those (4) of you who care most get the list of prices of rooms; start choosing with the most expensive room. If anyone is willing to take one of the rooms uncontested at the price listed, you get it. If there's a dispute, the people involved can bid higher; the amount extra paid for the room is split evenly to reduce everyone's rent, or to buy some sort of extras monthly for the house. Absolutely nobody pays less than the initial base amount ($50).
Throughout the process, keep in mind you're dealing with your friends; make sure nobody gets screwed.
(Fair division gap procedure looks pretty good, and I prob. wouldn't object if it were suggested to me, but would be a problem in cases where some people have much fewer resources, and can't pay the second-highest bid on a room. And the java applet with negative rents is wacky.)
(Obviously, I am not an economist.)
posted by mistersix at 3:05 PM on July 26, 2005

And the java applet with negative rents is wacky.

Choose the "HRS" option and you don't have to deal with negative rents. I played around with the "Interactive Sperner" option (the one with the wacky negative rents), given a reasonable model of a set of bidders, and it didn't come to a non-envious solution, at least not in any reasonable amount of time (and I ran it through probably a couple of hundred questions).

Fair division gap procedure looks pretty good, and I prob. wouldn't object if it were suggested to me, but would be a problem in cases where some people have much fewer resources, and can't pay the second-highest bid on a room.

No one pays more than they bid on a room--it's not as if someone else can force you into paying higher than your highest bid, regardless of their bids. However, as the paper on the HRS algorithm notes, the gap procedure doesn't necessarily produce a fair division when used for more than three people.
posted by DevilsAdvocate at 3:24 PM on July 26, 2005

may result in someone saying, "Gee, I know I bid $125/mo for my room, but if I knew I could have gotten the crappy room for only $20/mo I would have taken that instead!"

That's why I said you should let people strike deals after the fact. The $125/month person might find a way to swap with the $20/month person with an adjustment of costs to something like $100/month and $45/month. Then the low spender gets a presumably good room for $100 and the big spender suddenly has an extra $80/month to spend on whisky. Or just run the auction again, but only for the dissatisfied people and only to divide up their portion of the rent as determined by the first auction. The satisfied people would stay locked in to the rooms and rents they won in the first round.
posted by pracowity at 3:31 PM on July 26, 2005

That's why I said you should let people strike deals after the fact. The $125/month person might find a way to swap with the $20/month person with an adjustment of costs to something like $100/month and $45/month.

The $20/month person might refuse to trade at any price, so even with post-auction swaps this method is not guaranteed to produce an envy-free rent allocation.

Or just run the auction again, but only for the dissatisfied people and only to divide up their portion of the rent as determined by the first auction.

That only helps if the guy who won the crappy room for $20/month is also dissatisfied.
posted by DevilsAdvocate at 3:42 PM on July 26, 2005

A friend had a similar situation and they just wrote on slips of paper the maximum amount they would be happy to pay for each bedroom. Whoever bid the most got the room. If there is any excess over the total rent you can just scale down accordingly. There is a potential for people to screw it up by low-balling, and my friend said if that had happened they would have tried a different system, but luckily it worked out. Has the advantage of being simple for everyone to understand.
posted by mai at 4:10 PM on July 26, 2005

Mai's suggestion makes a lot of sense. I think that I've heard of bidding systems similar to this, but where the winner only pays as much as the next-highest bidder (or $1 more, actually), regardless of his actual bid. The logic there is that a room with only one person who really wants it (and bids high) doesn't get priced as high as one where 2+ people really want it. Or to put it another way, you aren't penalized for bidding high on a room if you're the only one who wants it.
posted by adamrice at 4:43 PM on July 26, 2005

How do you bid for "I just want the cheapest"?"

Easy. Don't bid, and take what's left at the end.

This, like many of the suggestions in this thread, can most easily seen to be inoperative by dropping from 7 people to 2.

I have a bit of advice, regardless of what system you use (though I would go with gleuschk's applet link, where there are actual theorems involved, rather than just the first thing an AskMe poster thought of). Make the process slow enough (perhaps over several days) so that anyone submitting a bid is sure they know what the effect will be. Theorems or no theorems, you want to avoid people's lingering resentment over having been rushed into a stupid decision. (Even if it's their own fault. You have to live with them!)
posted by Aknaton at 5:20 PM on July 26, 2005

mai, isn't there guaranteed to be an excess with that method?

In which case, I would put all the excess into the kitty for utilities. Since everyone has expressed their willingness to pay, it would be appropriate to put the excess share into joint expenditures.
posted by wilful at 5:20 PM on July 26, 2005

These are great answers, thanks! Can someone clue me in quickly on how the HRS method in the java applet compares to the Auto-choose Sperner method? And what advantages, if any, either might have over the gap method outlined in the MathTrek link? Thanks.
posted by shivohum at 7:38 PM on July 26, 2005

whoops nevermind about how the gap method compares... didn't remember the comment on the paper showing that gap procedure doesn't necessarily work with more than 3 people
posted by shivohum at 7:40 PM on July 26, 2005