Which is the Fairest (Rent Division) of Them All? [Extended Abstract]

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" [Su, 1999] by assigning the rooms and dividing the rent fairly.

In more detail, suppose each player i has value vij for room j, such that each player's values for the rooms sum up to the total rent. The (quasilinear) utility of player i for getting room j at price pj is vij - pj. A solution (i.e. an assignment of the rooms and division of the rent) is envy free [Foley, 1967] 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. 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.

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 [Svensson, 1983]. Even better, such a solution can be computed in polynomial time [Aragones, 1995].

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 $3. Each player i has value $3 for room i, and value $0 for the two other rooms. Furthermore, consider the solution that assigns room 1 to player 1 at $3, 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 - $1 per room - thereby equalizing player utilities.

The challenge, therefore, is to choose among many possible envy-free solutions. 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 [Alkan et al., 1991]. 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 theoretical and practical benefits of optimization in rent division.

The above challenges are especially pertinent when put in the context of Spliddit (www.spliddit.org), a not-forprofit fair division website [Goldman and Procaccia, 2014]. 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 60,000 users, who, in particular, have created 13,277 rent division instances (as of February 19, 2016).

Until April 2015, Spliddit's rent division application relied on the algorithm of Abdulkadiro˘glu et al. [2004], 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 1 ), 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 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 [Goldman and Procaccia, 2014]. This realworld dataset is exciting because, as noted by Herreiner and Puppe [2009], fair division is hard to study in the lab: researchers can tell subjects in the lab what their valuations are for different goods, but these values are not ecologically realistic, in that they do not represent subjects' actual preferences.

2 A Summary of Our Contributions

As this paper serves an expository purpose, we refer our readers to the full version of this work [Gal et al., 2016]

We construct 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. 2

Our next goal is to understand the relation between two solution concepts: the maximin solution [Alkan et al., 1991], 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.

1 An example of one of many positive reviews: "This tool helped us a lot. We live in a flat populated by international, young people, so it's been almost a revolving door of roommates [...] With your method we were able to avoid any long discussions. Thank you."

2 It is interesting to note that, even though the instances on Spliddit are small, computational tractability does play a key role, as there are many instances and computation incurs a cost (Spliddit uses Amazon Web Services to run all its algorithms).

Based on these results, we implemented the polynomialtime rentdivision algorithm, with the maximin objective function. 3 As noted above, it has been deployed on Spliddit since April 2015.

The remainder of our work focuses on demonstrating that the foregoing approach is indeed effective, via theory and experiments. Here our contribution is twofold. Using Spliddit data, we show that the improvement can be significant, according to both the maximin and equitability objectives; indeed, our analysis shows that outcome disparity improved by 9% of total rent, and by 4% with respect to the maximin objective.

Second, we report results from a user study, which has been a long time in the making. 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. On average, users ranked the maximin outcome by more than a full point higher (on a scale of 1-5); furthermore, their textual feedback provides anecdotal evidence that the maximin solution is perceived as fairer.