Rental harmony


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:
There are several properties that we would like the assignment to satisfy.
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:
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:
  1. Good house: In any partition of the rent, each person finds at least one room+rent parcel acceptable.
  2. No externalities: The preference relation of each partner depends on the rooms and the rents, but not on choices made by others.
  3. Miserly partners: every partner weakly prefers a free room over any other room.
  4. 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.
and provide popularized explanations of Su's Rental Harmony protocol.
and provide on-line 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.
They prove the existence of envy-free allocations in the following conditions:
  1. Good house: Every partner likes at least one of the rooms given each price vector.
  2. No externalities: All partners like free rooms.
  3. Miserly partners: The preferences are continuous in prices.
The main tools used in the proof are:
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 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.
  1. 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, and then save some money and switch to A.
  2. Incomplete information. The price-vector may give the partner some indication on the quality of rooms.
  3. 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.
  4. 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.

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 this room is worth for him.
A key notion in the cardinal solutions is a maxsum 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 . 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 1Room 2
Partner 11500
Partner 214010

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 :
Room 1Room 2Room 3Room 4
Partner 13634300
Partner 23136330
Partner 33430360
Partner 43233350

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:
  1. Calculate a maxsum allocation.
  2. 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.
  3. If the max-sum exactly equals the total cost, then the rooms are allocated and the partners pay their valuations.
  4. 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.
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 assignes 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 et al. present the Compensation Procedure. The problem it solves is more general than the rental-harmony problem in certain aspects:
There is a "qualification requirement" for a partner: the sum of his bids must be at least the total cost.
The procedure works in the following steps.
  1. Find a maxsum allocation - an allocation with a highest sum-of-utilities that satisfies the constraints on bundles of items. If there are no constraints, then an allocation that gives each item to the partner with the highest valuation is maxsum. If there are constraints, then a maxsum allocation might be more difficult to find.
  2. Charge from each partner the value of the bundle allocated to him. This creates the initial pool of money.
  3. Pay the cost from the initial pool. If all partners satisfy the qualification requirement, then the money in the pool is sufficient, and there may be some remaining surplus.
  4. Eliminate envy by compensating envious partners. There are at most rounds of compensation. The procedure is fully descriptive and says explicitly which compensations should be made, and in what order. Moreover, it is simple enough to be carried out without computer support.
  5. The sum of compensations made in all rounds is the smallest sum that is required to eliminate envy, and it never exceeds the surplus. If some surplus remains, it can be divided in any way that does not create envy, e.g., by giving an equal amount to each partner.
When there are many item and complex constraints, the initial step - finding a maxsum allocation - may be difficult to calculate without a computer. In this case, the Compensation Procedure may start with an arbitrary allocation. In this case, the procedure might conclude with an allocation that contains envy-cycles. These cycles can be removed by moving bundles along the cycle. This strictly increases the total sum of utilities. Hence, after a bounded number of iterations, a maxsum allocation will be found, and the procedure can continue as above to create an envy-free allocation.
The Compensation Procedure might charge some partners a negative payment. This means that the Compensation Procedure is EF but not NN. The authors say:
However, other authors claim that, in the usual housemates scenario:

Abdulkadiroglu and Sonmez and Unver: EF and NN if possible

Abdulkadiroğlu et al. suggest a market-based approach. It is a combination of an ascending auction and a descending auction. It is simplest to describe as a continuous-price auction:
  1. Initialize the price of each room to of the total house cost.
  2. Calculate the demand-set of each partner: the room or set of rooms he likes most at the current prices.
  3. Calculate the set of over-demanded rooms.
  4. Increase the price of all over-demanded rooms in the same rate;
  5. Simultaneously, decrease the price of all other rooms in the same rate, such that the sum of prices of all rooms always equals the total cost.
  6. At each instant, update the demand of each partner and the set of over-demanded rooms.
  7. When the set of over-demanded rooms is empty, stop and apply Hall's marriage theorem to allocate to each partner a room in their demand-set.
In practice, it is not necessary to change the price continuously, since the only interesting prices are prices in which the demand-sets of one or more partners change. It is possible to calculate the set of interesting prices in advance, and convert the continuous-price auction to a discrete-price auction. This discrete-price auction stops after a finite number of steps.
The returned allocation is always envy-free. The prices may be negative, like in the procedure of Haake et al. However, in contrast to that procedure, the prices are non-negative if there exists an EF allocation with non-negative prices.

Sung and Vlach: EF and NN if possible

Sung and Vlach prove the following general properties of allocations:
  1. Envy-freeness implies maxsum: given an allocation x, if there is a price-vector p with which x is envy-free, then x is maxsum.
  2. Max-sum implies envy-freeness: given a price-vector p, if there is an allocation x with which p is envy-free, then p is envy-free for any maxsum allocation.
Based on these properties, they propose the following algorithm:
  1. Find a maxsum allocation.
  2. Find a minsum price-vector, subject to the envy-freeness constraint. Such price-vector is a solution of a linear programming problem, and it can be found by the Bellman–Ford algorithm.
  3. If the min-sum equals the total cost, implement the maxsum allocation with the minsum prices and finish.
  4. If the min-sum is less than the total cost, then increase all prices in a constant rate until the sum equals the total cost. Changing all prices by the same amount ensures that the assignment remains envy-free.
  5. If the min-sum is more than the total cost, then there is no solution satisfying both NN and EF. There are several possible ways to proceed:
  6. * Decrease all prices in a constant rate until the sum equals the total cost. Some prices will necessarily be negative, as in the solution of Haake Raith and Su.
  7. * Decrease only the positive prices in a constant rate, until the sum equals the total cost. Here, the prices do not change by the same amount, so some partners will necessarily envious, as in the solution of Brams and Kilgour. However, in this solution, the envious partners get their room for free.
The runtime complexity of both finding maxsum allocation and finding minsum prices is.
The solution of Sung and Vlach seems to have all the desirable properties of the previous protocols, i.e.: PE and EF and NN and polynomial run-time, and in addition, it guarantees that every envious partner gets a free room. provides an implementation of a similar solution, also based on solving a linear-programming problem but citing a different paper.

Mash, Gal, Procaccia and Zick: EF and maximin

Gal, Mash, Procaccia and Zick, based on their experience with the rent division application in the Spliddit website, note that envy-freeness alone is insufficient to guarantee the satisfaction of the participants. Therefore they build an algorithmic framework, based on linear programming, for calculating allocations that are both envy-free and optimize some criterion. Based on theoretic and experimental tests, they conclude that the maximin criterion - maximizing the minimum utility of an agent subject to envy-freeness - attains optimal results.
Note that, since their solution is always EF, it might return negative prices.

Budget considerations

Most papers in the cardinal model assume that agents have Quasilinear utility functions - their utility is the room value minus the price. But in reality, agents have budget constraints - if the room price is above their budget, the utility drops much faster than linearly. Procaccia, Velez and Yu study this model and present an algorithm for finding whether there exists an EF allocation satisfying the budget constraints, and if so, find such an allocation that satisfies an additional fairness criterion.

Strategic considerations

All protocols surveyed so far assume that the partners reveal their true valuations. They are not strategyproof - a partner can gain by reporting false valuations. Indeed, strategyproofness is incompatible with envy-freeness: there is no deterministic strategyproof protocol that always returns an envy-free allocation. This is true even when there are only two partners and when the prices are allowed to be negative. Proof:
Assume that the total cost is 100 and the partners' valuations are as below :
Room 1Room 2
Partner 1100x
Partner 2100y

The only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. Let be the price of room 2. To ensure partner 1 does not envy, we must have. To ensure partner 2 does not envy, we must have.
Suppose a deterministic protocol sets the price to some value in. If the price is more than, then partner 2 has an incentive to report a lower value of, which is still above, in order to push his payment down towards. Similarly, if the price is less than, then partner 1 has an incentive to report a higher value of, which is still below, in order to push the payment of partner 2 up towards . Hence, the mechanism cannot be strategyproof.
Researchers have coped with this impossibility in two ways.

Sun and Yang: Changing the problem

There is a variant of the problem in which, instead of assuming that the total house cost is fixed, we assume that there is a maximum cost for each room. In this variant, a strategyproof mechanism exists: the deterministic allocation-rule selecting the min-sum cost is strategyproof.
This result can be generalized for greater flexibility on the indivisible objects, and a proof of coalitional strategy-proofness.

Dufton and Larson: Using randomization

Going back to the original rental-harmony problem, it is possible to consider randomized mechanisms. A randomized mechanism returns a probability distribution over room-assignments and rent-divisions. A randomized mechanism is truthful in expectation if no partner can increase the expected value of his utility by mis-reporting his valuations to the rooms. The fairness of a randomized mechanism can be measured in several ways:
1. Ex-ante Envy-Freeness means that no partner envies the lottery of any other partner. This condition is trivial to achieve in a truthful mechanism: randomise over all possible allocations with
equal probability and charge each partner of the total cost. But this condition is not appealing, since there is a large chance that in the final outcome, many partners will be envious. They may not be comforted by the fact that the lottery has been fair.
2. Guaranteed Probability of Envy-Freeness means that there is a certain probability such that, regardless of the partners' valuations, with probability at least, the final outcome will be envy-free. It is possible to achieve a GPEF of in the following way: find an envy-free assignment; choose an integer at random; and move each partner cyclically rooms to the right. This randomized mechanism is truthful-in-expectation, since every partner has an equal probability to land in each room and the expected payment is of the total cost, regardless of the partner's bid. The probability of having an EF allocation is the probability that, which is exactly. This is not encouraging, since the probability of envy-freeness converges to 0 when the number of partners grows. But it is impossible to do better: in every truthful-in-expectation mechanism, the GPEF is at most.
3. Expected Number of Envy-Free partners means that there is a certain integer such that, if we average the number of partners who do not envy in all possible outcomes of the mechanism, then regardless of the partners' valuations, the expectation is at least. The ENEF criterion seems more appropriate than the GPEF criterion, because it measures not only the probability of entire envy-freeness, but also the quality of the cases in which the allocation is not entirely envy-free. The maximum ENEF of a truthful-in-expectation mechanism is at most. It is possible to attain this bound for. For, there is a truthful-in-expectation mechanism that almost attains this bound: the ENEF is. The general idea is as follows. Use the VCG mechanism to calculate a maxsum assignment and payments. Select one partner at random. Ignore that partner and use VCG again. Combine the outcomes in a way which guarantees that the total payment equals the total cost. It is possible to show that: the mechanism is truthful-in-expectation; all partners except the ignored partner do not envy. Hence, the ENEF is. Simulations show that in about 80% of the cases, the GPEF of this mechanism is also at its maximum of.

Andersson and Ehlers and Svensson: Attaining partial-strategyproofness

A possible relaxation of the strategyproofness requirement is to try to minimize the "degree of manipulability". This is defined by counting, for each profile, the number of agents who can manipulate the rule. Maximally-preferred fair allocation rules are the minimally manipulable fair and budget-balanced allocation rules according to this new concept. Such rules choose allocations with the maximal number of agents for whom the utility is maximized among all fair and budget-balanced allocations.