Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.
In the typical setting, there are partners who rent together an -room house for cost fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view to the main road, etc. The following two problems should be solved simultaneously:
(a) Assign a room to each partner, (b) Determine the amount each partner should pay, such that the sum of payments equals the fixed cost.
There are several properties that we would like the assignment to satisfy. Non-negativity (NN): all prices must be 0 or more: no partner should be paid to get a room. Envy-freeness (EF): Given a pricing scheme (an assignment of rent to rooms), we say that a partner prefers a given room if he believes that the parcel of room+rent is weakly better than all other parcels. EF means that every partner prefers his allotted room. I.e, no partner would like to take another room at the rent assigned to that room. Pareto-efficiency (PE): No other assignment of partners to rooms is weakly better for all partners and strictly better for at least one partner (given the price-vector).
Envy-freeness implies Pareto-efficiency. Proof: Suppose by contradiction that there exists an alternative assignment, with the same price-vector, that is strictly better for at least one partner. Then, in the current allocation, that partner is envious.
The rental-harmony problem has been studied under two different assumptions on the partners' preferences: In the ordinal utility version, each partner has a preference relation on bundles [room, price]. Given a price-vector, the partner should only be able to say which room (or rooms) he prefers to rent at that price. In the cardinal utility version, each partner has a vector of monetary valuations. The partner should say, for each room, exactly how much money he is willing to pay for that room. The partner is assumed to have quasilinear utility, i.e., if he values the room as and pays , his net utility is . The cardinal assumption implies the ordinal assumption, since given a valuation vector it is always possible to construct a preference relation. The ordinal assumption is more general and puts less mental burden on the partners.
Ordinal version
Su: one person per room The protocol by Francis Su makes the following assumptions on the preferences of the partners: Good house: In any partition of the rent, each person finds at least one room+rent parcel acceptable. No externalities: The preference relation of each partner depends on the rooms and the rents, but not on choices made by others. Miserly tenants: every tenant weakly prefers a free room (a room with a rent of 0) over any other room. Topologically closed preference sets: A partner who prefers a room for a convergent sequence of prices, prefers that room at the limiting price.
Normalize the total rent to 1. Then each pricing scheme is a point in an -dimensional simplex with vertices in . Su's protocol operates on a dualized version of this simplex in a similar way to the Simmons–Su protocols for cake-cutting: for every vertex of a triangulation of the dual simplex, which corresponds to a certain price scheme, it asks the owning partner "which room do you prefer in that pricing scheme?". This results in a Sperner coloring of the dual simplex, and thus there exists a small sub-simplex which corresponds to an approximate envy-free assignment of rooms and rents.
Su's protocol returns a sequence of allocations which converges to an envy-free allocation. The prices are always non-negative. Hence, the outcome satisfies the NN and EF requirements.
Su's Rental Harmony protocol has been popularized in several news articles, and has several online implementations.
Azriely and Shmaya: room-mates Azriely and Shmaya generalize Su's solution to a situation in which the capacity of each room may be larger than one (i.e., several partners can live in the same room).
They prove the existence of envy-free allocations in the following conditions: Good house: Every partner likes at least one of the rooms given each price vector. No externalities: All partners like free rooms. Miserly partners: The preferences are continuous in prices.
The main tools used in the proof are: The K-K-M-S theorem - a generalization of the K-k-m theorem. Hall's marriage theorem.
Their solution is constructive in the same sense as Su's solution - there is a procedure that approximates the solution to any given precision.
General properties of ordinal protocols A. In both Su's solution and Azrieli&Shmaya's solution, the preference relation of each partner is allowed (but not obliged) to depend on the entire price-vector. I.e, a partner may say "if room A costs 1000, then I prefer room B to room C, but if room A costs only 700, then I prefer room C to room B".
There are several reasons such generality can be useful. Future planning. Suppose the partner thinks that room A is best, then B, then C. If A is expensive, the partner settles on B. But if A is cheaper, the partner might buy C (which is the cheapest), and then save some money and switch to A. Incomplete information. The price-vector may give the partner some indication on the quality of rooms. Neighbors. The price-vector may allow the partner to predict, to some extent, what kind of people are going to live in the neighboring rooms. Irrationality effects, e.g. framing effects. If room B and room C are of the same quality and have the same price, then the partner may buy A. But, if room B becomes more expensive, then the partner may switch to C, thinking that "it is the same as B but in bargain price..".
B. Both Su's solution and Azrieli&Shmaya's solution make a "Miserly tenants" assumption - they assume that a tenant always prefers a free room to a non-free room. This assumption is strong and not always realistic. If one of the rooms is very bad, it is possible that some tenants will not want to live in that room even for free. This is easy to see in the cardinal version: if you believe that room A is worth 0 and room B is worth 100, and room A is free and room B costs 50, then you certainly prefer room B.
Su suggests to weaken this assumption in the following way: each partner never chooses the most expensive room if there is a free room available. This does not require the person to choose the free room. In particular, this will hold if a person always prefers a free room to a room costing at least of the total rent. However, even this weakened assumption might be unrealistic, as in the above example.
Segal-Halevi shows that the assumption can be weakened even further. Let us say that a price T is too high for some agent i if, whenever some room costs T and some other room is free, no agent prefers the room that costs T. Rental harmony exists whenever there exists a price that is too high for all agents. This assumption is weaker than the miserly tenants assumption, and weaker than quasilinearity. It is an open question, whether there is an even weaker assumption that guarantees existence of rental harmony.
Cardinal version As explained above, the input to the cardinal version is a matrix of bids: every partner has to submit a bid to each room, saying how much (in dollars) this room is worth for him. It is usually assumed that agents have quasilinear utilities, so that their utility to a room is their value for the room minus the room price.
A key notion in the cardinal solutions is a maxsum (aka utilitarian) allocation. This is an allocation of partners to rooms, that maximizes the sum of bids. The problem of finding a maxsum allocation is known as the assignment problem, and it can be solved by the Hungarian algorithm in time (where is the number of partners). Every EF allocation is maxsum and every maxsum allocation is PE.
Incompatibility of EF and NN The two requirements of envy-freeness and non-negative payments are not always compatible. For example, suppose the total cost is 100 and the valuations are: Room 1 Room 2 Partner 1 150 0 Partner 2 140 10 Here, the only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. In order to make sure partner 2 does not envy, partner 1 must pay 115 and partner 2 must pay -15.
In this example, the sum of valuations is more than the total cost. If the sum of valuations equals the total cost, and there are two or three partners, then there always exists an EF and NN allocation. But if there are four or more partners, then again EF and NN might be incompatible, as in the following example (see for proof): Room 1 Room 2 Room 3 Room 4 Partner 1 36 34 30 0 Partner 2 31 36 33 0 Partner 3 34 30 36 0 Partner 4 32 33 35 0
Note that this example does not occur in the ordinal version, since the ordinal protocols make the "Miserly Partners" assumption - partners always prefer free rooms. When this assumption holds, there always exists an EF+NN allocation. But, in the above example, the assumption does not hold and an EF+NN allocation does not exist. Therefore, the protocols in the cardinal version have to compromise between EF and NN. Each protocol makes a different compromise.
Brams and Kilgour: NN but not EF Brams and Kilgour suggest the Gap Procedure: Calculate a maxsum allocation. If the max-sum is less than the total cost, then the problem is unsolvable, since the partners do not want to pay the total amount required by the houseowner. If the max-sum exactly equals the total cost, then the rooms are allocated and the partners pay their valuations. If the max-sum is more than the total cost, then the prices are lowered based on the gap between these prices and the next-lowest valuations (see the book for more details). The idea behind the last step is that the next-lowest valuations represent the "competition" on the rooms. If there a room is more wanted by the next-highest bidder, then it should cost more. This is similar in spirit to the Vickrey auction. However, while in the Vickrey auction the payment is entirely independent of the partner's bid, in the Gap procedure the payment is only partially independent. Therefore, the Gap procedure is not strategyproof.
The Gap Procedure always assigns non-negative prices. Because the assignment is maxsum, it is obviously also Pareto-efficient. However, some partners may be envious. I.e, the Gap procedure satisfies NN and PE but not EF.
Moreover, the Gap Procedure may return non-envy-free allocations, even when EF allocations exist. Brams relates to this problem saying that: "Gap prices do take into account the competitiveness of bidding for goods, which makes the pricing mechanism market-oriented. Although envy-freeness is a desirable property, I prefer a marketlike mechanism when there is a conflict between these two properties; partners should pay more when bids are competitive, even at the sacrifice of causing envy".
Haake and Raith and Su: EF but not NN Haake, Raith and Su present the Compensation Procedure. The problem it solves is more general than the rental-harmony problem in certain aspects: The number of indivisible items to divide (m) may differ from the number of partners (n). There can be arbitrary constraints on bundles of items, as long as they are anonymous (do not differentiate between partners based on their identity). For example, there can be no constraint at all, or a constraint such as "each partner must receive at least a certain number of items", or "some items must be bundled together" (e.g. because they are land-plots that must remain connected), etc.