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.
Proof: Suppose by contradiction that there exists an alternative assignment, with the same price-vector, that is strictly better for at least one partner.
The protocol by Francis Su[1] makes the following assumptions on the preferences of the partners: Normalize the total rent to 1.
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 Rental Harmony protocol has been popularized in several news articles,[9][10] and has several online implementations.
It is an open question, whether there is an even weaker assumption that guarantees existence of rental harmony.
A key notion in the cardinal solutions is a maxsum (aka utilitarian) allocation.
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.
Brams and Kilgour[8]: 305–328 [14] suggest the Gap Procedure: The idea behind the last step is that the next-lowest valuations represent the "competition" on the rooms.
When there are many item and complex constraints, the initial step - finding a maxsum allocation - may be difficult to calculate without a computer.
Sung and Vlach[4] prove the following general properties of allocations: Based on these properties, they propose the following algorithm: 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 (if possible) and polynomial run-time, and in addition, it guarantees that every envious partner gets a free room.
[15] provides an implementation of a similar solution, also based on solving a linear-programming problem but citing a different paper.
Gal, Mash, Procaccia and Zick,[17] 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 egalitarian rule - maximizing the minimum utility of an agent subject to envy-freeness - attains optimal results.
Peters, Procaccia and Zhu[18] study a practical setting in which agents may be unsure about their valuations.
Procaccia, Velez and Yu[19] present an efficient algorithm for finding whether there exists an allocation that is both EF and affordable.
Airiau, Gilbert, Grandi, Lang and Wilczynski[20] suggest two solutions to overcome the non-existence problem with budget constraints: Both these relaxations significantly enlarge the set of EF allocations.
Velez[21] studies EF rent division under soft budget constraints.
He shows that, the complete-information non-cooperative outcomes of each of the algorithms are exactly the EF allocations w.r.t.
true preferences, iff the number of allowed disutilities is bounded.
Arunachaleswaran, Barman and Rathi[23] study a setting substantially more general than quasilinear, in which the utility of each agent from each room can be any piecewise linear function of the rent.
They also show that the problem lines in the intersection of the complexity classes PPAD and PLS.
[24] This result can be generalized for greater flexibility on the indivisible objects, and a proof of coalitional strategy-proofness.
A randomized mechanism returns a probability distribution over room-assignments and rent-divisions.
This condition is trivial to achieve in a truthful mechanism: randomise over all possible allocations with equal probability and charge each partner
This randomized mechanism is truthful-in-expectation, since every partner has an equal probability to land in each room and the expected payment is
[27] This is defined by counting, for each profile, the number of agents who can manipulate the rule.