I am part of a group of 5 students who wish to rent a house with 5 rooms of uneven size. We each have different budgets.

Initially, a suggestion was made that we just hunted for a house with a rental cost 5 times the person with the lowest budget and then allocate the rooms by lottery.

However, this seems a sub optimal approach, since some of us would happily pay extra if we could get a slightly larger house and then pay extra for the larger rooms.

Given some of us are prepared to pay more for a larger room in the house, how can we match the rooms with each person's budget and willingness to pay extra for a larger rooms?

Further it would be great if any solution was generic to a range of potential rental houses, each of which has rooms of varying size (as we are looking at a number of houses).

I originally thought that we could have an auction for the rooms, but noted that the aggregate bids must add up to the cost to rent the whole house. I then thought we could do relative bids (how much extra we would be willing to pay for the largest room compared with the second largest and so on), but this approach left the possibility that the solution would produce bids higher than someone's individual budget.

This seems to be an optimisation problem constrained by each individuals personal budget and the rental cost of the house as a whole.

Do you have any ideas how to solve this?

Regards

Justin

Roughly speaking, you need to compute the aggregate valuation of the students for each house. They should then rent the house for which the gap between their aggregate valuation and the house’s rent is the largest. They can then allocate the surplus (valuation minus rent) among themselves in some way – for instance, divide it equally. So, for instance, if the valuation of student i for the room she ends up getting is B_i, and the total rent is R, then the aggregate valuation is V=B_1+...+B_5. The surplus is then V-R. Each student gets (V-R)/5, so the rent student i pays is B_i-(V-R)/5 under equal division.

The problem is figuring out the aggregate valuation of the students for each house. First you would have to induce each student to reveal her valuation of each room in a house. Then you then need to find the optimal assignment of students to rooms in the house, which is easy: it is the assignment that maximizes the sum of students’ valuations of the rooms to which they are assigned. Let the valuation of student i for her room in this optimal assignment be B_i. You can then apply the algorithm of the first paragraph, using B_1 through B_5 and the rent R as inputs.

The main difficulty is inducing the students to truthfully reveal their valuations of each room in each house. It is hard because a student’s valuation of a room depends on what will happen if she doesn’t get the room, which itself is a very complex problem. Also, students have incentives to understate their valuations in order to reduce the rent they ultimately pay.

“A shortcut is simply to ask each student to reveal her valuation of each room. Since these “bids” may not be truthful or accurate, the outcome may not be efficient. But this would be a quick and dirty way to solve the problem.”