Communications of the ACM

Research highlights

Which Is the Fairest (Rent Division) of Them All?

By Kobi Gal, Ariel D. Procaccia, Moshe Mash, Yair Zick
Communications of the ACM, February 2018, Vol. 61 No. 2, Pages 93-100
10.1145/3166068
Comments

"Mirror mirror on the wall, who is the fairest of them all?"
    The Evil Queen

Back to Top

Abstract

What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness constraint, in order to pinpoint the "fairest" solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives, and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015.

Back to Top

1. Introduction

Many a reader may have personally experienced the rent division problem: several housemates move in together, and need to decide who gets which room, and at what price. The problem becomes interesting—and, more often than not, a source of frustration—when the rooms differ in quality. The challenge is then to achieve "rental harmony"¹⁸ by assigning the rooms and dividing the rent fairly.

In more detail, suppose each player i has value v_ij for room j, such that each player's values for the rooms sum up to the total rent (see Figure 1a). The (quasilinear) utility of player i for getting room j at price p_j is v_ij – P_j (see Figure 1b). A solution (i.e. an assignment of the rooms and division of the rent) is envy free⁸ if the utility of each player for getting his room at its price is at least as high as getting any other room at the price of that room (see Figure 1c). More generally, one can think of this problem as allocating indivisible goods and splitting a sum of money—but we adopt the rent division terminology, which grounds the problem and justifies our assumptions.

Figure 1. Envy-free solutions, illustrated.

Envy freeness is undoubtedly a compelling fairness notion. But what makes it truly powerful in the context of rent division is that an envy-free solution to a rent division problem always exists.¹⁹ Even better, such a solution can be computed in polynomial time.³

However, envy freeness in and of itself is insufficient to guarantee satisfactory solutions. For example, consider an apartment with three rooms and total rent of $3000. Each player i has value $3000 for room i, and value $0 for the two other rooms. Furthermore, consider the solution that assigns room 1 to player 1 at $3000, and, for i ∈ {2, 3}, gives room i to player i for free. This solution is envy free: players 2 and 3 are obviously overjoyed, while player 1 is indifferent between the three rooms. However, from an interpersonal perspective, this solution is not fair at all, as the distribution of prices between players is unequal. An intuitive alternative solution here would be to keep the same assignment of rooms, but equally split the rent between the different rooms—$1000 per room—thereby equalizing the utilities of the players.

The challenge, therefore, is to choose among many possible envy-free solutions. And, arguably, the most natural way to do this is to optimize a function of the utilities that meets desirable social criteria, subject to the envy freeness constraint.² In particular, if we were to maximize the minimum utility of any player subject to envy freeness, or if we were to minimize the maximum difference in utilities subject to envy freeness, we would obtain the aforementioned solution in the example. This focus on optimization in rent division motivates us to

... design polynomial-time algorithms for optimization under the envy freeness constraint; understand the relationship between natural optimization objectives; and measure the benefits of optimization in rent division.

 1.1. Real-world connections and implications: The Spliddit service

The above challenges are especially pertinent when put in the context of Spliddit (www.spliddit.org), a not-for-profit fair division website.⁹ Spliddit offers "provably fair solutions" for the division of credit, indivisible goods, chores, fare—and, of course, rent. Since its launch in November 2014, Spliddit has attracted more than 100,000 users, who, in particular, have created 27,344 rent division instances (as of July 6, 2017).

Until April 2015, Spliddit's rent division application relied on the algorithm of Abdulkadiroğlu et al.,¹ which elicits the values of the players for the rooms, and computes an envy-free solution assuming quasi-linear utilities. While many users were satisfied with the results (based on their reported evaluations), the algorithm does provide nonintuitive solutions in some cases. This prompted an investigation of alternative approaches, and ultimately led to the deployment of a new algorithm in April 2015, based entirely on the results presented in (the original version of) this paper.

It is important to point out that Spliddit not only motivates our research questions, but also helps answer them. Indeed, while Spliddit's primary goals are making fair division methods accessible to people, and outreach, a secondary goal is the collection of an unprecedented dataset for fair division research.⁹ This real-world dataset is exciting because, as noted by Herreiner and Puppe,¹² fair division is hard to study in the lab: researchers can tell subjects what their valuations are for different goods, but these values are not ecologically realistic, in that they do not represent subjects' actual preferences. To quote Herreiner and Puppe,¹² "the goods in the lab are not really distributed among participants, but serve as temporary substitutes for money." In contrast, Spliddit instances are ecologically valid, as they are posed by real people facing real division problems. Thus the Spliddit data enables studies at a realistic level and scale that was not possible before. Even better, we can ask Spliddit users to evaluate different solutions based on the actual instances they participated in. This is exactly what we do in this paper.

 1.2. Our results

We start, in Section 3, by constructing a general yet simple algorithmic framework for optimization under the envy freeness constraint. Specifically, our algorithm maximizes the minimum of linear functions of the utilities, subject to envy freeness, in polynomial time. We do this by using the Second Welfare Theorem to argue that we can employ any welfare-maximizing assignment of players to rooms, and then solve a linear program to compute the optimal envy free prices.^a

Our main goal in Section 4 is to understand the relation between two solution concepts: the maximin solution,² which maximizes the minimum utility of any player subject to envy freeness; and the equitable solution, which minimizes disparity—the maximum difference in utilities—subject to envy freeness. (Our algorithm can compute either solution in polynomial time.) Our most significant result in this section is proving that the maximin solution is also equitable, but not every equitable solution is maximin.

Based on these results, we have implemented the polynomial-time algorithm of Section 3, with the maximin objective function.^b As noted above, it has been deployed on Spliddit since April 2015.

The remainder of the paper focuses on demonstrating that the foregoing approach is indeed effective. Here our contribution is twofold. First, we show that real-world instances give rise to significant differences, according to both the maximin and equitability objectives, between the maximin solution (which optimizes both objectives simultaneously) and an arbitrary envy-free solution (which does not attempt to optimize either objective).

Second, we report results from a user study. We contacted Spliddit users, and asked them to compare two solutions: the maximin solution, and an arbitrary envy-free solution. Crucially, the two solutions were computed on each user's actual Spliddit instance (the values of other tenants were perturbed to preserve privacy). Subjects were asked to subjectively rate the solutions in terms of fairness to themselves, and fairness to others. The results show a significant advantage for the maximin solution in both questions, thereby demonstrating the added value of optimization and supporting the decision to use the maximin solution on Spliddit.

 1.3. Related work

The idea of refining envy-free solutions has been explored in several papers,^{2, 20, 21, 22} typically from an axiomatic viewpoint. We focus on the work of Alkan et al.,² who study the more general problem of allocating goods and dividing money. They start by proving the existence of envy-free solutions in this setting, but, like us, they ultimately employ criteria of justice in order to find the "best" envy-free solutions. They are especially interested in the maximin solution, which they call the value-Rawlsian solution; and the solution that maximizes the minimum amount of money allocated to any player, subject to envy freeness, which they call the money-Rawlsian solution. They show that the maximin solution is unique, as are a number of less attractive solutions (minimize the maximum utility, maximize the utility of one particular player). Finally, they show that these criteria imply solutions with a monotonicity property: if the amount of money is increased, the utility of all players is strictly higher (this property is moot in our setting). Alkan et al.² do not provide algorithmic results.

Aragones³ designs a polynomial-time algorithm for computing the money-Rawlsian solution of Alkan et al.² Her combinatorial algorithm does not extend to other criteria. In contrast, our LP-based framework is significantly more general, and, in particular, allows us to compute the maximin solution (which we view as the most attractive) in polynomial time. Our algorithmic approach is also much simpler. It is worth noting that Klijn¹⁴ gives a different polynomial-time algorithm for computing envy-free solutions, without guaranteeing any additional properties (other than being extreme points of a certain polytope).

There are (at least) three marketlike mechanisms for computing solutions for the rent division problem assuming quasi-linear utilities, by Brams and Kilgour,⁴ Haake et al.,¹¹ and Abdulkadiroğlu et al.¹ All three do not consider optimization criteria; in the case of the mechanism of Brams and Kilgour,⁴ the solution may not be envy free. As mentioned above, the mechanism of Abdulkadiroglu et al.¹ was deployed on Spliddit until April 2015.

One fundamentally different approach to rent division that we would like to discuss in more detail is that of Su.¹⁸ He does not assume quasi-linear utilities; rather, his main assumption is that a player would always prefer getting a free room to getting another room at a positive price (the so-called miserly tenants assumption). Under this assumption, Su¹⁸ designs an algorithm that converges to an (approximately) envy-free solution, by iteratively querying players about their favorite room at given prices. While eschewing the quasi-linear utilities assumption is compelling, a (crucial, in our view) disadvantage of this approach is that preference elicitation is very cumbersome. Interestingly, Su's method was implemented by the New York Times.^c

Relatively few papers explore fair allocations among people in lab settings, and there is inconclusive evidence about the types of solution criteria that are favored by people. Dupuis-Roy and Gosselin⁷ report that fair division algorithms were rated less desirable than imperfect allocations that did not employ any fairness criterion, while Schneider and Krämer¹⁷ find that subjects preferred envy-free solutions to a divide-and-choose method that does not guarantee envy freeness. Herreiner and Puppe^{12, 13} find that envy freeness was a dominant factor in the allocations favored by subjects, but that it was a secondary criterion to Pareto optimality or inequality minimizing allocations. Kohler¹⁵ proposes an equilibrium strategy for repeated negotiation that incorporates fairness and envy concerns. In all of these papers, the studies were conducted in a controlled lab setting in which subjects' valuations over goods were imposed on the subjects, or the goods to be allocated were chosen by the experimenters themselves.

Back to Top

2. The Model

We are interested in rent division problems involving a set of players [n] = {1, . . ., n}, and a set of rooms [n]. Each player i has a non-negative value v_ij ∈ ℝ⁺ for each room j. We assume without loss of generality that the total rent is 1, and also assume (with loss of generality) that for all We can therefore represent an instance of the rent division problem as a right stochastic (rows sum to 1) matrix V ∈

---

No entries found