Rental harmony

Rental harmony^[1][2] 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^[3][4] and room-assignment-rent-division^[5][6] are alternative names to the same problem.^{[7][8]: 305–328}

In the typical setting, there are ${\displaystyle n}$ partners who rent together an ${\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 ${\displaystyle v}$ and pays ${\displaystyle p}$, his net utility is ${\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.