Generalized Rental Harmony

Abstract

Rental harmony is the problem of assigning rooms in a rented house to tenants with different preferences, and simultaneously splitting the rent among them, such that no tenant envies the bundle (room and price) given to another tenant. Various researchers have studied this problem mainly under two incompatible assumptions: the miserly tenants assumption—each tenant prefers a free room to a room with a positive price; and the quasilinear tenants assumption—each tenant attributes a monetary value to each room, and prefers a room of which the difference between value and price is maximum. This article shows that the main technique used for rental harmony with miserly tenants, using Sperner’s lemma, can be adapted to a much more general class of preferences, one that contains both miserly tenants and quasilinear tenants as special cases. As a corollary, some recent results derived for miserly tenants are found to be applicable to this more general class, too.

MSC:

• Primary 91B32

Acknowledgments

I am grateful to Guillaume Chèze, Yaron Azrieli, Eran Shmaya, Rodrigo Velez, Frédéric Meunier, Shira Zerbib, two anonymous reviewers, and the editor of this Monthly for their kind and helpful comments. This work was partially supported by the Israel Science Foundation grant no. 712/20.

Notes

1 We cannot just assume that the agent always prefers a single room, since this assumption is incompatible with continuity. For example, suppose there are two rooms, and Alice prefers room 1 when $p_1<500$ and room 2 when $p_1>500$. Then the continuity assumption requires that when $p_1=500$ she prefers both rooms.

We could strengthen the miserly tenants assumption and require that, when there are free rooms, all the best rooms of every agent must be free rooms. But this would make the theorem weaker. For example, the theorem would not be applicable to indifferent agents, who prefer all rooms regardless of their prices, even though an envy-free allocation obviously exists in this case.

2 An affirmative answer has recently been given to two of these questions: roommates [11] and a secretive agent [3].

3 Negative prices may make sense in some situations. For example, if one of the rooms requires constant maintenance in order to prevent nuisances to the other rooms, then the tenants might agree to pay anyone who will take this room and do the maintenance job.

4 Brams and Kilgour [6] show an example with n = 4 agents and rooms, in which for each agent the sum of values of all rooms equals R, and still there are negative prices in any envy-free allocation.

5 The term “Archimedean” was coined by Rodrigo Velez. A similar assumption, called “Assumption A1,” is presented in his recent survey paper [21].

6 This observation is based on the author’s experience teaching fair division to computer programmers.

7 They used a reduction to the standard setting: For each room j, construct c_j sub-rooms with capacity 1, and let each agent value all sub-rooms of room j by v_j. Note that this reduction cannot be used for miserly tenants, since it does not preserve the miserly tenants assumption. For example, suppose the living room has capacity 2 and the basement has capacity 1. Suppose the two sub-rooms of the living room are priced at 0 and 200 and the basement is priced at 200. Then the living room and the basement have the same positive price, so a tenant who prefers the basement satisfies the miserly tenants assumption in the original problem, but not in the modified problem.

8 They assume that each agent has a utility function that assigns a utility to each combination of room and price. They assume that all utility functions are continuous, monotonically decreasing in the price, and bounded. The boundedness assumption is equivalent to the Archimedean tenants assumption.

9 For the sake of readability, we focus on a setting of two houses with equal rents, but the results can be easily extended to more than two houses, and to houses with different total rents.

10 If both houses have free rooms, then every agent has a best pair in which both rooms are free.

11 As an example, suppose $m=n=2$ and consider two agents, Alice and George, with the following demand functions. The best pairs of Alice are the pairs in which both rooms cost at most $R/4$ (if any), and the cheaper among the two pairs (1, 1) and (2, 2). The best pairs of George are the pairs in which both rooms cost at most $R/4$ (if any), and the cheaper among the two pairs (1, 2) and (2, 1). It can be verified that these demand functions are continuous and satisfy the miserly tenants assumption, and that an envy-free allocation does not exist for any pair of price vectors. See Theorem 3 and Figure 4 of [7].

12 For simplicity we state their argument only for the special case k = 2, which is sufficient for our purpose.

13 This is why we need $2n-1$ agents to start with.

Additional information

Funding

I am grateful to Guillaume Chèze, Yaron Azrieli, Eran Shmaya, Rodrigo Velez, Frédéric Meunier, Shira Zerbib, two anonymous reviewers, and the editor of this Monthly for their kind and helpful comments. This work was partially supported by the Israel Science Foundation grant no. 712/20.

Notes on contributors

Erel Segal-Halevi

Erel Segal-Halevi started to study fair division after reading the Biblical commandment to “divide the land equally” (Ezekiel 47:14). This study led him to do a Ph.D. in computer science (Bar-Ilan University, 2013–2017), focusing on algorithms for fair division of land. He is currently teaching and developing algorithms for fair division and some other economic problems.