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 n {\displaystyle n} partners who rent together an n {\displaystyle n} -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 v {\displaystyle v} and pays p {\displaystyle p} , his net utility is v − p {\displaystyle v-p} . 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 ( n − 1 ) {\displaystyle (n-1)} -dimensional simplex with n {\displaystyle n} vertices in R n {\displaystyle \mathbb {R} ^{n}} . 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.
… excerpt ends here. Continue reading the full article.
