Rental harmony
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 <math>n</math> partners who rent together an <math>n</math>-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 <math>v</math> and pays <math>p</math>, his net utility is <math>v-p</math>. 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 and has several online implementations.
Azriely and Shmaya: room-mates Azriely and Shmaya 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 <math>O(n^3)</math> (where <math>n</math> is the number of partners). Every EF allocation is maxsum and every maxsum allocation is PE. 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". provides an implementation of a similar solution, also based on solving a linear-programming problem but citing a different paper.
Aragones: EF and money-Rawlsian Aragones presented a polytime algorithm for finding an EF solution that, among all EF solutions, maximizes the smallest payment by an agent (it is called the Money Rawlsian solution).
Mash, Gal, Procaccia and Zick: EF and egalitarian 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 egalitarian-rule - 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.
The maximin solution is implemented in the spliddit.org website and in the pref.tools website.
Peters, Procaccia and Zhu: Robust EF Peters, Procaccia and Zhu study a practical setting in which agents may be unsure about their valuations.
Agents with a limited budget ### Hard budget constraints 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. In fact, an agent always prefers any room with a price at most his budget, to a room with a price larger than his budget.
In this case, there may not exist a price-vector that is both EF and affordable. For example, present an efficient algorithm for finding whether there exists an allocation that is both EF and affordable. If so, it finds an allocation that, among all EF affordable allocations, maximizes the smallest utility (as in egalitarian-item-allocation).
Airiau, Gilbert, Grandi, Lang and Wilczynski suggest two solutions to overcome the non-existence problem with budget constraints:
- Relaxing EF to budget-friendly EF, which means that agent i is allowed to envy agent j if j pays more than i*s budget. A BF-EF allocation is more likely to exist than an EF allocation, but still not guaranteed to exist. They show a MILP for computing a BF-EF allocation if it exists. They also show a polytime algorithm for a fixed price-vector, and a pseudopolytime algorithm for a fixed room assignment.
- Allowing fractional allocation, i.e., allocate (1,2) with price to agents (1,2) for half a year and reverse the allocation for the other half, and charge each agent 500. They show a linear program for finding a fractional EF allocation if it exists. They show that finding an EF allocation with a smallest amount of total switches is NP-hard (by reduction from Partition problem or from Hamming salesman problem), but can be solved in time O(2k) by dynamic programming, where k is the size of the Birkhoff algorithm (k ≤ n*2). They conjecture that minimizing the largest amount of switches per agent is NP-hard too.
Both these relaxations significantly enlarge the set of EF allocations. However, even with each of these relaxations, an EF allocation might not exist.
Soft budget constraints Velez studies EF rent division under soft budget constraints. Each agent reports their values for rooms, their budget, and their marginal disutility from having to pay more than the budget (e.g. the interest rate). He presents an algorithm that find an EF rent division that is, moreover, egalitarian (max min utility), or money-Rawlsian (min-max rent), or satisfies one of other similar conditions. The run-time is in O(nk+c), where n is the number of agents, k is the number of different disutility values (e.g. different interest rates), and c>2 is some constant.
Velez studies the strategic properties of these algorithms. 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.
Piecewise linear utilities Arunachaleswaran, Barman and Rathi 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. This setting generalizes the soft budget constraint. As there is a too-high price, an EF allocation always exists. They show an FPTAS - an algorithm that finds an allocation that is EF up to (1+ε), in time polynomial in 1/ε and nk+c, where n is the number of agents, k is the number of different disutility values (e.g. different interest rates), and c>2 is some constant. They also show that the problem lines in the intersection of the complexity classes PPAD and PLS.
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 (where <math>x,y</math> are parameters and <math>0<x<y<100</math>):
The only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. Let <math>p_2</math> be the price of room 2 (so that the price of room 1 is <math>100-p_2</math>). To ensure partner 1 does not envy, we must have <math>p_2\geq x/2</math>. To ensure partner 2 does not envy, we must have <math>p_2\leq y/2</math>.
Suppose a deterministic protocol sets the price <math>p_2</math> to some value in <math>[x/2,y/2]</math>. If the price is more than <math>x/2</math>, then partner 2 has an incentive to report a lower value of <math>y</math>, which is still above <math>x</math>, in order to push his payment down towards <math>x/2</math>. Similarly, if the price is less than <math>y/2</math>, then partner 1 has an incentive to report a higher value of <math>x</math>, which is still below <math>y</math>, in order to push the payment of partner 2 up towards <math>y/2</math> (and thus push his own payment down). 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.