Rental harmony

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 O(n^3) (where n 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 ≤ n2). 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 x,y are parameters and 0): The only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. Let p_2 be the price of room 2 (so that the price of room 1 is 100-p_2). To ensure partner 1 does not envy, we must have p_2\geq x/2. To ensure partner 2 does not envy, we must have p_2\leq y/2. Suppose a deterministic protocol sets the price p_2 to some value in [x/2,y/2]. If the price is more than x/2, then partner 2 has an incentive to report a lower value of y, which is still above x, in order to push his payment down towards x/2. Similarly, if the price is less than y/2, then partner 1 has an incentive to report a higher value of x, which is still below y, in order to push the payment of partner 2 up towards y/2 (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. 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: 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 (individually and coalitionally) 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. == See also ==