# JACM6406 39

## Transcript

2 39:2 Y. (Kobi) Gal et al. 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 , such that each player’s values for j for room has value In more detail, suppose each player v i ij for getting room the rooms sum up to the total rent. The (quasi-linear) utility of player at price p i j j v is − p (Foley . A solution (i.e., an assignment of the rooms and division of the rent) is envy free j ij ) if the utility of each player for getting his room at its price is at least as high as getting any 1967 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 1983 exists (Svensson ). 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 } ,givesroom 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 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 (Alkan et al. ). In particular, if we were to 1991 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 con- straint; understand the relationship between natural optimization objectives; and measure the theoretical and practical benefits of optimization in rent division. 1.1 Real-World Connections and Implications: The Spliddit Service The aforementioned challenges are especially pertinent when put in the context of Spliddit ( www.spliddit.org ), a not-for-profit fair division website (Goldman and Procaccia ). Spliddit 2014 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 2004 solution assuming quasi-linear utilities. While many users were satisfied with the results (based 1 ), the algorithm does provide nonintuitive solutions in some cases. on their reported evaluations 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.” Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

3 Which Is the Fairest (Rent Division) of Them All? 39:3 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 article. 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 divi- sion research (Goldman and Procaccia ). This real-world dataset is exciting because, as noted 2014 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 realis- ), 2009 tic, 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 substi- tutes for money.” By 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 solu- tions based on the actual instances they participated in. This is exactly what we do in this article. 1.2 Our Results 3 , by constructing a general yet simple algorithmic framework for optimization We start, in Section 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 2 players to rooms and then solve a linear program to compute the optimal envy-free prices. 4 is to understand the relation between two solution concepts: the Our main goal in Section 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. Based on these results, we have implemented the polynomial-time algorithm of Section , with 3 3 As noted earlier, it has been deployed on Spliddit since April 2015. the maximin objective function. The remainder of the article focuses on demonstrating that the foregoing approach is indeed effective, via theory and experiments. Here our contribution is twofold. First, we show—in Sec- tion 5 —that when values are drawn from a uniform Dirichlet distribution, and there are two or three players (the most common cases on Spliddit), the expected difference between the worst and best envy-free solutions in terms of disparity is significant. This means that, in theory, there is scope for significant improvement according to the equitability criterion. But do we also see an improvement in practice? We answer this question in the positive using Spliddit data. Indeed, we show that real-world instances give rise to significant differences, according to both the max- imin and equitability objectives, between the maximin solution (which optimizes both objectives 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). In other words, if we reduce the computational resources required for each instance by some factor, then we reduce the total computational resources required across tens of thousands of instances by the same factor, and that leads to significant savings. 3 To be completely precise, the algorithm deployed on Spliddit first tries to maximize the minimum utility, subject to envy freeness as well as an additional constraint: prices must be nonnegative. If an envy-free solution with nonnegative prices does not exist (Brams and Kilgour 2001 ), it removes the nonnegative price constraint (in which case a solution always exists). Most of our results go through even when prices are assumed to be nonnegative. In any case, real-world instances where negative prices actually help are extremely rare, so throughout the article prices are unconstrained. Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

5 Which Is the Fairest (Rent Division) of Them All? 39:5 ) report that fair division algorithms were rated less desirable than imperfect allo- Gosselin ( 2011 )findthat cations that did not employ any fairness criterion, while Schneider and Krämer ( 2004 subjects preferred envy-free solutions to a divide-and-choose method that does not guarantee envy freeness. Herreiner and Puppe ( , 2010 ) find that envy freeness was a dominant factor 2009 in the allocations favored by subjects, but that it was a secondary criterion to Pareto optimality or inequality-minimizing allocations. Kohler ( 2013 ) 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. 2THEMODEL = { 1 ,..., n } and a set of We are interested in rent division problems involving a set of players [ n ] + j ∈ R for each room . We assume without rooms [ i has a nonnegative value v n ]. Each player ij loss of generality that the total rent is 1, and also assume (with loss of generality) that for all ∑ n 1. We can therefore represent an instance of the rent division problem as a right = v ], n [ ∈ i ij 1 j = + ∈ M V stochastic (rows sum to 1) matrix ( R ) . n n × :[ n ] → [ n ], where σ ( i ) is the room assigned to An assignment of the rooms is a permutation σ n . The division of rent is represented through a vector of (possibly negative) prices ∈ R player i p ∑ n such that . p j = is the price of room p 1; j i i 1 = ( σ , p ) for a rent division problem V , the quasi-linear utility of player i is denoted Given a solution if the utility of each player for her room is at ( , p ) = v σ envy free (EF) . A solution is p − u i ( i ) i ( iσ ) σ σ ) p ( is EF if and only if least as high as any other room. Formally, , , i ∈ [ n ] , v ∀ j (1) . p − p − v ≥ j ij i ) ) σ ( i ( iσ 3 COMPUTATION OF OPTIMAL ENVY-FREE SOLUTIONS As noted previously, it is possible to compute an envy-free solution to a given rent division problem ). We are interested in choosing among envy-free allocations by 1995 in polynomial time (Aragones optimizing an objective function, subject to the envy-freeness constraint. Our goal in this section is to show that this can be done in polynomial time, when the objective function is the minimum of linear functions of the utilities. n n is polynomial in ,..., f t : R . Given a rent → R be linear functions, where f Let Theorem 3.1. t 1 over ( u )) ( , , p ) ,..., u p ( σ σ , p ) that maximizes the minimum of f division instance V , a solution ( σ n q 1 ∈ [ ] subject to envy freeness can be computed in polynomial time. all q t Natural examples of objective functions of the form specified in the theorem are max- imizing the minimum utility and minimizing the maximum difference in utilities; we dis- 4 . The former objective can be directly captured cuss these objectives in detail in Section n [ ∈ i for all ( u ) ( σ , p ) ]. The latter criterion u p ( σ , p )) = u , ( σ ,..., n by setting t f ,and = n i 1 i 2 ) p ) and f , ( u σ ( σ , p . Indeed, ,..., u ( ( σ , p )) = u u ( σ , p ) − n = t is also captured by setting i n 1 ij j , so maximizing the mini- f ) ( u p ( σ , p ) ,..., u , ( } , p )) = − max { u σ ( σ , p ) − u ( σ min j i n 1 ij [ n ] i , j ∈ [ n ] i , j ∈ mum of these linear functions is equivalent to minimizing the maximum difference in utilities. Our polynomial-time algorithm relies on a connection between envy-free rent division and the Walrasian equilibrium . To understand this connection, imagine a more general setting concept of n ] are interested in purchasing bundles of goods G ; here, each buyer i has where a set of buyers [ G ) S :2 to every bundle of goods. A Walrasian → R , assigning a value v ( v a valuation function i i is the bundle G ⊆ A of the goods to buyers (where ) ,..., A equilibrium is an allocation A ( = A n i 1 given to buyer i ), coupled with a price vector p that assigns a price to each good, such that each Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

6 39:6 Y. (Kobi) Gal et al. p ; formally: player receives the best bundle of goods that she can buy for the price v . A ) − p ( A ) ≥ ( (2) ( S ) − p ( S ) ∈ ∀ ] i , S ⊆ G , n v [ i i i i ∑ n . The following prop- v ) ( A welfare maximizing A We say that an allocation is if it maximizes i i 1 = i erties of Walrasian equilibria are well known; see, for example, the book of Mas-Colell et al. ( 1995 , Chapter 16). ( A , p ) is a Walrasian equilibrium, then A Theorem 3.2 (1st Welfare Theorem). If is a welfare- maximizing allocation. ′ A , p ) If A Theorem 3.3 (2nd Welfare Theorem). ( is a Walrasian equilibrium and is a welfare- ′ A p , = ) is a Walrasian equilibrium as well. Furthermore, v ( ( A p ) − ) A ( maximizing allocation, then i i i ′ ′ [ . ) − p ( A ( ] ) for all i ∈ A n v i i i Now, an EF solution in the rent division setting is a Walrasian equilibrium in the setting where S ⊆ the goods are the rooms and the valuation function of each player for a subset n ]ofroomsis [ given by v ( S ) = max ) 1 valuations)—it is easily seen that Equation ( v unit demand (these are ij j ∈ i S ) in this case. This means that we can apply the welfare theorems to 2 coincides with Equation ( 5 For example, we can immediately deduce a simple result of Svensson ( ): any 1983 EF allocations. ′ ′ p , ) such that ( σ ( σ , p EF solution is Pareto efficient, in the sense that there is no other solution ) ′ ′ ( σ ) , p ]. To see this, note n ≥ u [ ( σ , p ) for all i ∈ [ n ], with strict inequality for at least one i ∈ u i i ′ . , and the sum of prices is 1 under both and p is welfare maximizing by Theorem 3.2 p that σ We are now ready to present our polynomial-time algorithm for maximizing the minimum of f of the utilities, subject to EF; it is given as Algorithm 1. ,..., linear functions f 1 t ALGORITHM 1: ∑ n σ ∈ { argmax (1) Let be a welfare-maximizing assignment v } π ( i ) iπ i 1 = by solving the linear program p (2) Compute a price vector R max p ) − ( v v ] ,..., [ ∈ − p q ∀ t f ≤ R s.t.: q σ ( ) nσ ) σ ( n ) 1 ( σ ) 1 ( n 1 , ] [ ∈ − p j n i ∀ ≥ v p − v ij j ( ) i ( iσ i σ ) n ∑ p = 1 j 1 = j σ of players to rooms; this The algorithm starts by computing a welfare-maximizing assignment can be done in polynomial time, as this task reduces to the maximum weight bipartite matching on each edge problem, with players on one side of the graph, rooms on the other, and a weight v ij ,..., , which com- p ) . It then solves (in polynomial time) a linear program, with variables p , i ( j n 1 putes optimal envy-free prices with respect to . The first constraint sets (in an optimal solution) σ ( · ) . Envy freeness is enforced by the R to the minimum of the linear functions f the objective q second constraint, and the third constraint guarantees that the prices sum to 1. However, it may not be immediately clear why starting from an arbitrary welfare-maximizing assignment allows us to compute the optimal solution subject to envy freeness. This is formally established in the proof that follows. 5 In the context of rent division, Theorems 3.2 and 3.3 can also be derived from the results of Alkan et al. ( 1991 ) and Svensson ( 2009 ). Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

7 Which Is the Fairest (Rent Division) of Them All? 39:7 ∗ ∗ ) be the solution that maximizes the minimum of , p Proof of Theorem 3.1. Let ( σ subject to EF. Furthermore, let ,..., · ( · ) ) σ be the welfare-maximizing allocation computed ( f f 1 t ∗ ∗ ∗ ∗ , for all ) is such that u ) ( σ , p p ) = u σ ( 3.3 , σ ( , p in the first step of Algorithm 1. By Theorem i i ∗ ) is EF, and σ , p i ∈ N . In particular, ( ∗ ∗ ∗ ∗ ∗ ∗ min ( u (3) ( σ , p . ) ,..., u σ ( σ , p )) )) = min ( u ,..., ) , f p ( u f ( σ , p 1 q q 1 n n q ∈ t ] t [ ∈ q ] [ ∗ is a feasible solution to the linear program, we have that its optimal solution p satisfies Because p ∗ ∗ min u p f , ( u σ ( σ , p ) ,..., u ( ( σ , p )) ≥ min u ,..., ) (4) . f p ( )) , ( σ 1 n n 1 q q ] t [ ∈ ] t [ ∈ q q 3 4 ) together, we see that we must have equality in Equation ( 4 ), and that Putting Equations ( ) and ( σ , p ) is an optimal envy-free solution.  ( 4 RELATIONS BETWEEN THE FAIREST SOLUTIONS Algorithm 1 allows us to maximize the minimum of linear functions of the utilities, subject to EF, in polynomial time. With the potential computational barrier out of the way, we would like to understand which optimization objective to use. Specifically, we focus on two natural optimization objectives and evaluate their properties. equitability .Let EF We refer to the first objective as V ) be the set of all EF solutions for V .Given ( a solution ( σ , p ) ∈ EF ( V ) ,wedefine D ( σ , p ) as the difference between the utilities of the happiest player and the worst-off player under the solution ( , p ) ,thatis, σ ( σ } ) p { u , . σ , p ) − u ( ( max σ D p , ) = i j ∈ , N j i measures the social disparity under the solution In more general terms, the function σ , p ) ;we D ( ∗ ∗ ( σ would like to minimize this quantity. A solution p ) equitable if it minimizes D over , is called V ) ,thatis, EF ( ∗ ∗ , p . ) ∈ arg min { } D σ , p ) | ( σ , p ) ∈ EF ( V ) ( σ ( Herreiner and Puppe ( 2009 ) demonstrate via experiments with human subjects that equitability is of great importance in determining whether an allocation is perceived to be fair by people. Alternatively, instead of minimizing social disparity, one might be interested in maximizing the utility of the worst-off player. More formally, given an EF solution ( σ , p ) ,welet U ( σ , p ) = u ( σ , p ) ;if min N i i ∈ ∗ ∗ ) p ) ) ∈ arg max { U ( σ , p (5) | ( σ , p , ∈ EF ( V ) } , ( σ ∗ ∗ p , solution. maximin ) is a σ then we say that ( Alkan et al. ( 1991 ) argue that the maximin solution—which they call the value-Rawlsian solution —is compelling on philosophical grounds. Mathematically, they demonstrate that the max- imin solution is associated with a unique vector of utilities, making this solution even more appealing. The fact that equitable and maximin allocations are constrained to be EF again allows us to em- ∗ ∗ ) , p is equitable (max- ) to great effect. Indeed, if 3.3 σ ( ploy the Second Welfare Theorem (Theorem ′ ′ ∗ is a welfare-maximizing assignment, then ( σ ) , p is equitable (maximin, σ imin, respectively), and respectively). Therefore, hereinafter we assume without loss of generality that the identity assign- ment σ ( i ) = i is welfare maximizing and simply use D ( p ) or U ( p ) to refer to these measures under the identity assignment. In particular, we can talk about equitable or maximin vectors of prices with respect to the identity assignment. At first glance, the equitability and maximin criteria seem equally appealing. Which one leads to fairer solutions? The next theorem shows that we do not have to choose—the maximin solution is equitable. Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

8 39:8 Y. (Kobi) Gal et al. ∗ If p Theorem 4.1. is a maximin vector of prices, then it is also equitable. p p ) = , it will be useful to think of the following graph Proof. Given an EF vector of prices Γ( to ] ) ; the nodes in Γ( p ) are the players, and there is a directed edge from i E j if i weakly envies ( [ , n (recall that we are assuming the identity assignment). We say that − p p = v i − v j —that is, i ii ij j i i p ; similarly, a player i is called rich if if has maximum utility is poor has minimum utility under . under p ∗ i has a path to is a maximin rent division, then every nonpoor player p We first claim that if ∗ ∗ apoorplayerin . Indeed, assume for contradiction that this is not the case, and let Γ( p be ) T ∗ ∗ ) ; by assumption, T  ∅ ,and Γ( the set of all players that have no path to poor players under p ∗ ∗ T  ∅ as well ([ n ] \ T ] contains, at the very least, the poor players, who have a path of length \ [ n defined as follows: q 0 to themselves). Let us observe the vector of prices { ∗ p T + εi ∈ i ∗ q = . | | ε T i ∗ p − T \ i ∈ [ n ] ∗ i | T −| n ∗ ∗ { u is a very small constant, which is in particular smaller than min ε Here, , p ( ) − u | ( id , p id ) j i ∗ ∗ ∗ ∗ p ) > u ∈ ( id , p , ) } .Let i , j ∈ [ n ] such that i weakly envies j j id p .If i , j ∈ T ( or i , under u i j ∗ still weakly envies belongs to ,then i i : their prices changed by the same amount. If j \ n T [ ] ∗ ∗ j ; otherwise, there would be a path from n ] \ T ,then cannot belong to [ i to some poor player, T ∗ ∗ ∗ belongs to n \ T belongs to [ .If j ] T i ,then i enjoyed and a contradiction to the definition of T j suffered an increase, so i does not envy j under q . We conclude that a decrease in rent, whereas ∗ includes all poor players, the mini- is envy free, by our choice of q ] \ T n .However,because[ ε ∗ ∗ , a contradiction to p being a maximin EF rent q p mum utility under is strictly higher than under division. ∗ ∗ ∗ > ( p D ) be an equitable EF price vector. Suppose for contradiction that D ( q .Ifall ) Next, let q ∗ ∗ ∗ ,then p ) = 0 ≤ D ( q D ) , which is impossible. Hence, there ( players have the same utility under p ∗ . p must be some rich players that are not poor under ∗ ∗ ∗ 0. This means that every ) − U ( ≥ q ) ; since p ε is a maximin EF rent division, p U = ε We write ( ∗ could have had their utility decreased by at most ε . In other words, if i is a poor player under p ∗ ∗ ∗ ∗ ∗ . Moreover, since q ( ≤ ε ,then D ( p − ) > D q p ) by assumption, it must be poor player under p i i ∗ had their utility decreased by strictly more than ε ;thisis the case that the rich players under p is a rich player, then because if i ∗ ∗ ∗ ∗ u ) ( − min , ) id q , u id ( id , p , ) > max ( u min − ) u p ( id , q j i j j ∈ [ n ] j ] ∈ j [ n n ∈ j [ ] ∗ ∗ ∗ ∗ u and therefore ,or, ) > max ε ( + ( id , q id ) + ε , which implies that u ) ( id , p , ) > u p ( id , q u i i j i ∈ [ n ] j ∗ ∗ − p . > ε equivalently, q i i We know that there is a path from at least one rich player (who is not poor) to at least one poor ∗ ∗ ∗ ∗ ∗ ( i , j ) on that path such that q p − − . ) . In particular, there must be an edge > q p p Γ( player in i j i j ∗ ∗ ∗ Γ( p By the definition of v . It follows that − p p ) = v , − ij ii j i ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ v − p − − + ( p q v − q v = ) < , ) − p = v + ( p q q − ii ij ij ii i i j i j i j j ∗ . contradicting the envy freeness of q Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

9 Which Is the Fairest (Rent Division) of Them All? 39:9 By contrast, an equitable solution may not be maximin, as the following example shows. Example 4.2 (An equitable solution that is not maximin). This example is particularly appealing, as it is a real-world instance submitted by Spliddit users: 2227 708 0   258 1378 1299   . 1000 1000 935   i ; the max- Note that the total rent is \$2,935. The optimal room assignment gives room i to player 1 1 1 2 ∗ ∗ ∗ p imin rent division is 1813 , 521 ) = = , with a utility vector of u ) ( id , p , ) = 413 600 ( , u p ( id , 2 1 3 3 3 3 2 2 2 2 ∗ ∗ 777 , p ) ) = 413 , any solution 364, and by Theorem .Wehave D ( p , u 4.1 777 ( = − 413 id = 3 3 3 3 3 2 2 2 ′ p that has the same disparity is equitable. However, the price vector 721 ( 642 , = ) is 1570 , 3 3 3 1 1 1 ′ ′ ′ ′ u an EF rent division, resulting in 656 = ) ( u id , id , p p ) = 656 , p , u ( ( id , p ) ) = 292 = D ,and ( 3 2 1 3 3 3 1 1 656 − 292 = 364 as well; that is, it is equitable, but the minimum utility is (much) smaller than 3 3 ∗ . p that under , which is men- money-Rawlsian solution Let us now discuss a third optimization objective, the ) and implemented in polynomial time by Aragones ( 1995 ). The latter tioned by Alkan et al. ( 1991 author describes the following procedure for finding EF solutions. Begin by finding a welfare- i goes to maximizing assignment of rooms (again, assume without loss of generality that room ∗ ∗ ∗ ∗ n R Q ∈ of nonnegative values such that v = + q and q ≥ v + ); next, find a vector q i player ii ij + j i ∑ n ∗ ∗ q i − is minimized. That is, each player q pays a value of . Next, increase the prices of all play- = i 1 i i ∗ ∗ α ( q is a valid price vector. = 1; that is, the vector − α ,..., ) such that ers by a quantity Q − nα α While the money-Rawlsian solution is interesting, it may be “maximally unfair” in terms of disparity, as the following example shows. Example 4.3 (The money-Rawlsian solution may maximize disparity). We analyze the following rent division instance: ) ( 10 . V = 1 1 2 2 ∗ ( = 0 ,..., 0 ) . A uniform ,and q The welfare-maximizing assignment allocates room to player i i increase in rent will ensue, resulting in the price vector ( 1 / 2 , 1 / 2 ) and the utility vector ( 1 / 2 , 0 ) . Crucially, the money-Rawlsian price vector maximizes disparity among all EF solutions. Note that ) ( / 4 , 1 the maximin price vector is 4 3 , which, of course, minimizes disparity. / To conclude, so far we know that the maximin solution, the equitable solution, and the money- Rawlsian solution can be computed in polynomial time. Moreover, Theorem 4.1 shows that the maximin solution, which by definition maximizes the minimum utility, also minimizes disparity (among all EF solutions)—so it is a refinement of the equitable solution. In stark contrast, the money-Rawlsian solution may disparity (among all EF solutions). We therefore view maximize the maximin solution as the clear choice and focus on analyzing its effectiveness hereinafter. 5 ON THE IMPORTANCE OF BEING EQUITABLE Our goal in this section is to understand how much better the maximin solution is, in terms of the maximin and disparity objectives, compared to suboptimal solutions on average . In Section 5.1 ,we show that the expected gain in terms of reducing disparity is significant in a formal probabilistic model. For this theoretical analysis, we focus on the cases of two and three players, which are the most common on Spliddit. We also focus on the equitability criterion, but the same ideas can be applied to the maximin criterion. In Section 5.2 , we conduct an empirical analysis, showing significant gains in both of our primary objective functions on real data from Spliddit. Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

10 39:10 Y. (Kobi) Gal et al. 5.1 The Benefit Is Significant in Theory + ∗ player rent division problem, let n Given an D D max ) V ( = D ( p ) ,and ) = ( V ∈ ) V ( EF p + V ( ( D is the highest utility difference between the best- and worst-off p ) ;thatis, D ) min ) EF ∈ V p ( ∗ V ( ) is the difference between the EF solution, whereas D players under the disparity- maximizing best- and worst-off players under the equitable solution discussed earlier. In order to establish the potential impact of minimizing disparity, we would like to show that instances where the differ- + ∗ V ) − D ) ( V ( is significant are a common occurrence. D ence + ∗ ) ] for rent division instances ( V [ − D D ( V ) E More formally, we are interested in computing V ∼ μ n player rent division instances. In our theoretical results sampled from some distribution μ over n rooms. In over each player’s values for the that follow, we use the uniform Dirichlet distribution ∈ [ n ] chooses a valuation profile uniformly at random from the more detail, each − 1 dimen- i n ,..., X 1] , ∼U [0 X sional simplex. Such uniform distributions can be generated as follows: let 1 n 1 − X ≤···≤ be the variables X 1], and let , be independent uniform random variables on [0 ( n ) 1 ) ( 1 − − X ,..., X − , X ( = X v sorted according to their order statistics; then the vector 1 ( ( 1 − 1 ) ) 2 ( ) n corresponds to a sample from the uniform Dirichlet distribution. ) X , 1 − X ) − 1 ) 2 − n ( n ( . Let us start with the setting where there are only two players. In that case, The Two-Player Case a valuation matrix can be written as ( ) − v 1 v 1 1 , v v 1 − 2 2 where v v , ∈ [0 , 1]. To draw a random instance, we simply need to draw v 1]. We use , v , ∼U [0 2 2 1 1 ∗ + ) [ ) ( V D − D ]. ( V two lemmas to exactly calculate E μ ∼ V − − 2 . Then there exists an EF price vector p n Let = Lemma 5.1. ( p ) = 0 . D such that Proof. We again assume that the identity assignment is welfare maximizing. Given a price ( p vector , p and solving for ) , the player utilities are v p − p − and 1 − v 1 − p = ; setting p 2 2 2 1 1 1 2 1 v + v 1 2 = 1 − v yields − p − p p . = v 1 1 2 2 1 2 It remains to make sure that this solution is indeed envy free. Under this price vector, we have v v − v + v 1 2 2 1 , and her utility from room 2 is 1 − − v 1 − ( = ) that player 1’s utility from room 1 is 1 2 2 − v v 1 2 . Now, if player 1 envies player 2, then < v is v i to player i , in which case allocating room 2 1 2 not a welfare-maximizing assignment. To see this, note that − − v ≥ v + 1 . v ⇐⇒ v + ≥ v 1 v 1 2 1 2 2 1 Thus, under this price vector, player 1 does not envy player 2. Now, player 2’s utility from room 2 − v v v v − + v v 1 1 2 2 2 1 = , which is not more than his or her utility − v , and her utility from room 1 is is 2 2 2 2 from her own room as previously argued. + v + v v v − − 2 1 1 2 −  ( = 0. , = ) is an EF price vector for which D ( p 1 ) p To conclude, 2 2 Lemma 5.2. Given a two-player rent division instance ( ) v − v 1 1 1 = V , − 1 v v 2 2 + − ) = | v ( V v . | it holds that D 2 1 Proof. Suppose that v v (the case of ≥ v is handled similarly). In this case, we can as- < v 2 1 2 1 is EF if and only if p . v ≤ , p ) ≤ v sume that room i i p ( . A price vector is assigned to player 2 1 1 2 1 D p ) is the maximum of linear functions, its maxima occur on vertices of the polyhe- Since ( dron of EF rent divisions. Thus, the maximum difference in player utilities must occur when p 1 v or v = .Notethat u ( v , 1 − v ) = equals either , u ( v , 1 − v ) = v − v ,and u ( v , 1 − v ) 0 1 2 1 1 1 2 1 1 1 2 2 1 2 + − v  , u . ( v v , 1 − v − v = 0. Thus, in either case D ) ( V ) = v 1 1 2 2 2 2 2 Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

11 Which Is the Fairest (Rent Division) of Them All? 39:11 + ∗ V ) − D ( ( V ) ] in the two-player case, we simply need to D Therefore, in order to estimate [ E 3. We include the proof for completeness. / ], which is clearly 1 − v | | calculate E v [ 2 1 Theorem 5.3. Let ( ) v − v 1 1 1 V = v 1 v − 2 2 1 + ∗ [ ∼U ( 0 , 1 ) ;then E . D , ( V ) − D v ( V ) ] = v be a two-player rent division instance, where 2 1 3 + ∗ D 5.2 and 5.1 Proof. According to Lemmas , = | v D − v ( | and V ) ( V ) = 0. Thus, we need to 1 2 calculate ∫ ∫ ∫ ∫ 1 v 1 1 1 + D [ E − v dv | ] = V ) ) ( = v | v − − v v | dv ( dv E = 2 [ | v dv ] 1 2 2 1 1 1 2 2 1 2 0 0 0 0 ∫ 1 1 1 2 , ( v ) = dv 2 = 1 1 2 3 0 where the third equality follows from symmetry between v v .  and 2 1 . We now proceed to tackle the three-player rent division case, in Three Players, and Beyond the foregoing regime. While our results for this case are not nearly as tight as for the case of two players, we provide an in-depth analysis of an interesting class of three player rent division instances. This class includes instances where all players mostly agree on the value of one room but disagree on the values of the other two. ∗ ( ε ) be the class of three-player rent division instances that satisfy the More formally, let C | ], but n − − v v |≤ ε for all i , k ∈ [ | for which j following property: there exists some room v  i ij kj [ 2 ε for all  ∈ [ n ] \{ j } and all i ∈ |≥ n ], k ∈ [ n ] \{ i } . The next lemma—whose proof is given in v k  ∗ V allows for an extremely ( ε ) ,then V C is in the appendix—shows that if a rent division instance ∑ v − 1 ) / 3; however, it also admits ( equitable EF solution, where each player has utility of nearly ii i an EF solution where one of the players has utility 0—the worst possible outcome. ∑ v − 1 ii − − + ∗ i U ( p ) ) ≥ , then there exist EF price vectors − ( and p ε such that p If V ∈C Lemma 5.4. 3 2 + ∗ + ( p V ) = 0 .Moreover, D ε ( ,but ) ≤ ε ,but D U ( V ) ≥ 2 ε . 3 ∗ C By proving a lower bound on the probability that rent division instances belong to ( ,we ε ) can establish the following theorem, whose proof appears in the appendix. Theorem 5.5. Let V be a three-player rent division instance drawn from the uniform Dirichlet < 1 / 5 , distribution; then, for any ε 15189 + 3 4 5 6 2 ∗ ε ( V ≥ ε ] ≥ ( . D − − 4560 ε ) + 1902 ε V − 312 ε ) + 18 ε D Pr[ 5 + ∗ V ) − 07 ( ( V ) ≥ 0 . D implies that with probability at least 0.019, D For example, Theorem 5.5 (which is 7% of the total rent). With smaller probability of roughly 0.00024, the difference is huge— almost 20% of the total rent. By contrast, it is intuitive that as n grows, we cannot expect the difference in disparity to remain bounded away from zero. The reason is that for any fixed ε > 0, it is likely that all players agree ] with high probability. n [ ∈ k , − v j | < ε for all i , v | ;thatis, ε on the values of all rooms up to jk ik This property guarantees that near equitability holds for all EF rent divisions. Indeed, when all players agree on all values up to ε , choosing different EF price vectors causes little difference in players’ utilities; in a sense, there is very little “wiggle room” due to players’ utility vectors being so similar to one another. Formally: Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

12 39:12 Y. (Kobi) Gal et al. ∈ for all EF payment v | < ε for all i , j , k − [ n ] ,then D ( p ) ≤ ε If Lemma 5.6. V | is such that v jk ik vectors . p is allocated to player i .If p is EF, then v Proof. Assume again that room − p i ≥ v , − p j ii i ij p of each other, we have that ≥ v ε − ]. Since the values are within − for all i , j ∈ [ n p and v ji j jj i ) − p ≥ |≤ v p − p , − ε ; similarly, we have that v id − p ( ≥ v u − p − − ε .Thus, | u ) ( id , p v i ii j j jj j jj ii i i . ε  Now it remains to show that values are indeed likely to be close to each other. 1 + ε ( n ) = ] Theorem 5.7. . For any = , lim ε Pr[ D = ( V ) < ε 1 →∞ n ) n ( o Proof. By Lemma 5.6 , it is sufficient to prove that lim . 1 Pr[ ∀ i , j , k ∈ [ n ] , | v = − v ] | < ε ij ik n →∞ 1 − n .By ( − ε ) is exactly i ε 1 Observe that the probability that player evaluates room 1 at least at j ∈ [ n ]. Taking a union bound over all players and rooms, symmetry, this is true for any room − n 2 1 o ( ,wehavethat ) n ( ≥ ε ] ≤ n / 1 1 − ε ) = ε . However, for we obtain that Pr[ ∈ i , j [ ∃ v ]s.t. n ij n 1 − 2 lim = 1 ε )  n 0. − ( →∞ n 5.2 The Benefit Is Significant in Practice Earlier we analytically established the potential for significantly reducing disparity by using the maximin solution. In the remainder of the section, we demonstrate the practical benefit of the maximin solution with respect to real-world instances that were submitted by Spliddit users. In our empirical results, we compare the maximin solution to an arbitrary EF solution, which is obtained by solving a feasibility linear program without an optimization objective. By contrast, the theoretical analysis compares the maximin solution to the worst EF solution. We note that similar empirical results are obtained when comparing the maximin solution to the algorithm of 2004 ). Abdulkadiroğlu et al. ( D and U (which are simultaneously The comparison is in terms of both of our main objectives, D would be significantly lower ,and U optimized by the maximin solution). We expected that sig- nificantly higher , in the maximin solution compared to an arbitrary EF solution. We focus our analysis on 1,358 rent division instances involving 3,682 players, which were sub- mitted on Spliddit between January 2015 and December 2015. The number of instances for each number of players 2, 3, 4, 5, 6, 7, 8, and 9 is 698, 445, 160, 35, 9, 8, 1, and 2, respectively. We only use instances that include two, three, or four players, for which we have at least 160 instances in the database and for which obtaining statistical significance was possible. Importantly, note that this is a small subset of the 13,277 rent division instances created by Spliddit users by the time the analysis was conducted, in December 2015; this is because we selected instances very conserva- tively, to ensure the ecological validity of our analysis. For example, Spliddit allows a “live demo” mode of interaction, and we excluded instances created that way. To illustrate users’ values for rooms in the Spliddit dataset, we present Figure 1 ,whichvisu- alizes the distribution for two-player instances. The x-axis shows the value of player 1 for room 1, and the y-axis shows the value of player 2 for room 1. The total rent is normalized to \$1, so each player’s value for room 2 is simply the complement of the displayed value; that is, the point , ( y ) corresponds to an instance where the values of player 1 are ( x , 1 − x ) and those of player x 2are ( y , 1 − y ) . The diagonal from points ( 0 , 0 ) to ( 1 , 1 ) represents the points in which players completely agree on the rooms’ values. We color each instance according to its distance from this line, using shades of red for shorter distances and shades of blue for longer distances. Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

13 Which Is the Fairest (Rent Division) of Them All? 39:13 Fig. 1. The distribution of values for two-player Spliddit instances (normalized to a total rent of \$1). The figure reveals several interesting phenomena. First, there is a significant cluster of instances . 5 , 0 0 5 ) mark, implying that both players are indifferent between that is centered on or close to the ( . 0 . 5 , 0 . 5 ) point, in which one of the players the two rooms. Second, we see a “cross” centered at the ( is indifferent, while the other player prefers one of the two rooms. Third, there are some instances x ∈{ 0 , 1 } or y ∈{ 0 , 1 } ); that is, they desire a in which one or both of the players are obstinate (i.e., specific room at any cost. Let us now turn to the comparison we promised previously. Given a rent division instance V , ∗ EF p denote the price denote the price vector associated with the maximin solution, and p let D ( p ) and vector associated with an arbitrary EF solution, as discussed earlier. As before, we let (assuming ( ) denote the social disparity and utility of the worst-off player under price vector p p U D a welfare-maximizing assignment of players to rooms). The improvement in social disparity ∗ EF p , and the ) ) − D ( p ( from using the maximin price vector over the EF vector is defined as D U from using the maximin price vector over the improvement in the utility of the worst-off player ∗ EF ( ) − . ) p U p EF vector is defined as U ( 2 Figure out of the total rent in D and U .Asshownby shows the percentage of improvement the figure, for = 2 , n , 4, the disparity associated with the maximin outcome is significantly lower 3 than that of the EF solution (9% of the total rent on average), and the utility of the worst-off player associated with the maximin solution is significantly higher than that of the EF solution (4% of the total rent on average). This trend is exhibited with respect to each value of n . We note the following points. First, the degree of improvement in both D U becomes smaller and 5.1 as the number of players grows, which is in the same spirit as the results of Section .However, qualitative difference, for even in cases where the improvement is relatively small, it still makes a example, when the maximin solution achieves zero disparity, and the arbitrary EF solution achieves strictly positive disparity (we discuss this fact in the next section). In addition, as noted earlier, the vast majority of Spliddit instances include two or three players, for which the improvement in D and U is higher than four players. Lastly, although this is not shown in the figure, an improvement in both D and U occurs in over 90% of the instances, for n ∈{ 2 , 3 , 4 } . 6USERSTUDY In the previous sections, we established, both theoretically and empirically, the benefits of the maximin approach to computing envy-free solutions for rent division problems. The question Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

14 39:14 Y. (Kobi) Gal et al. D Fig. 2. Average percentage of improvement (out of the total rent) in social disparity and utility of the worst- off player U when using the price vector associated with the maximin solution, compared to an arbitrary EF solution, on Spliddit instances. addressed by this section is, are people willing to accept such solutions in practice? To answer this question, we conducted the following user study. 6.1 Study Design People who used the Spliddit service during the year 2015 were invited (via email) to participate in a short study to evaluate the new allocation method. We targeted users who participated in rent division instances on Spliddit that included two, three, or four players. In order to use Spliddit, one need not supply an email address; users can opt to send out URLs to other users, which is what the vast majority of users choose to do. We only contacted users who supplied their email address—a relatively small subset of the users who were involved in rent division instances. All participants were given a \$10 compensation that did not depend on their responses. In total, the invitation email was sent to 344 Spliddit users, of which 46 users (13%) chose to participate. The study was approved by the Institutional Review Board (IRB) of Carnegie Mellon University. The study followed a within-subject design, by which each of the subjects was shown, in random order, an arbitrary EF solution (as discussed in Section 5.2 ) and the maximin solution, applied to their original problem instance . Importantly, we wished to preserve the privacy of players regarding their evaluations over the different rooms. Therefore, each player that participated in the study was shown a slightly modified version of their own rent division problem. Information that was already known to each subject was identical to the original Spliddit instance, including the total rent, the number of rooms, their names, the subject’s own values for the different rooms, and the allocation of the rooms to the players. Information that was perturbed to preserve the privacy of the other players included their names, which were changed to “Alice,” “Bob,” or “Claire,” depending on whether there were two, three, or four players, and the other players’ valuations, which were randomly increased or decreased by a value of up to 15% under the constraint that the total rent is unchanged, and that player valuations are still valid (nonnegative and sum to the total rent). Figure 3 shows an example of the arbitrary EF allocation for one of the instances in the study, from the perspective of a player called Hugo. The allocation of Hugo (room Verde, utility = \$21) is shown in the “window” at the right-hand side of the “house.” The value of this room for each of Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

15 Which Is the Fairest (Rent Division) of Them All? 39:15 Fig. 3. A visualization of a problem instance in the user study (from the point of view of a tenant named Hugo). the players is displayed using a bar graph, with Hugo’s own value highlighted via the green bar. The price paid by Hugo for room Verde (\$2 , 382) is visualized as a horizontal line “cutting” through the value bars of the players. This provides a vivid graphical description of the values and utilities of the players for this room and makes it easy for participants to reason about fairness properties relating to the proposed solution. For example, it is easy to see that none of the other players envies room Verde for the proposed price. The other windows in the house show the allocations of the players Alice and Bob in a similar way. The subjects were shown the two solutions—maximin and arbitrary EF—for the instance pre- sented to them. Both solutions include the same room allocation, but possibly differ in the prices paid by the players. The two solution outcomes were shown in sequence, and in random order. For example, the maximin solution for the rent division instance shown in Figure provides the same 3 room assignment as the EF solution, but the utility of all players is \$344 (compared to utilities of \$21 for Hugo, \$825 for Claire, and \$186 for Alice under the arbitrary EF solution). Note that the disparity under the maximin solution is zero in this example, which was also the case in many of the other instances included in the study (see later). The subjects were asked to rate two different aspects of each of the two solutions on a scale from 1 to 5, with 1 being least satisfied and 5 being most satisfied. The two aspects are the subject’s individual allocation and the allocations of the other players. The two questions were phrased as follows (using the rent division instance of Figure 3 for illustration purposes): Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

16 39:16 Y. (Kobi) Gal et al. Fig. 4. Results of the user study. (Individual) “This question relates to your own allocation. In other words, we would like you to your own benefit. How happy are you with getting the to pay attention only room called Verde for \$2,382?” “This question relates to the allocation for everyone else . How fair do you rate the (Others) allocation for Bob and Claire?” In both questions, players were able to write an argument or justification for their rating. To cancel order effects, the two questions were presented in random order. 6.2 Results We hypothesized that players would rate their own allocation under the maximin solution signifi- cantly higher than under the EF solution, and similarly for the allocation of the other participants. Figure shows the results of the user study. For each number of players (two, three, or four), we 4 show the average satisfaction level reported for the arbitrary EF solution and maximin solution when relating to each player’s individual outcome (left chart) and others’ outcomes (right chart). In all cases, the maximin solution is rated significantly higher than the envy-free solution for both questions, passing a Wilcoxon signed-rank test with p < 0 . 04. Anecdotally, based on textual feedback, subjects had a good understanding of the experiment. As an example, on the instance of Figure , the subject identified as Hugo wrote regarding his own 3 outcome: “It looks like I am overpaying.” And for the allocation of the other players: “They both get much more benefit.” Why did players overwhelmingly prefer the prices from the maximin solution over the arbitrary EF solution? Given the high importance attributed to social disparity when reasoning about fair di- vision (Herreiner and Puppe 2009 ), we hypothesized that the price vectors of the maximin solution exhibited significantly lower disparity than the price vectors of the EF solution. This was supported by many of the textual comments relating to social disparity. Figure 5 shows the cumulative dis- tribution of disparity across all instances that were included in the user study. The x-axis indicates the disparity as percentage of the total rent. As shown by the figure, the disparity associated with the maximin solution is indeed significantly lower. In fact, in many instances, the disparity is zero under the maximin solution. (For the n = 2 case, Lemma 5.1 shows that the minimum disparity is Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

17 Which Is the Fairest (Rent Division) of Them All? 39:17 Fig. 5. Cumulative distribution over the social disparity across all instances that were included in the user study. The x-axis indicates the percentage of social disparity out of the total rent price. zero for any instance.) We believe that this large difference in disparity played a key role in sub- jects’ preference for the maximin solution, trumping the relatively small improvement in utilities. 7 DISCUSSION There are two practical questions that inevitably come up when we present our work on rent division and its deployed application. The first question is whether participants can achieve a better outcome by misreporting their values. Indeed, they can, and the reason we do not address such game-theoretic concerns is twofold. First, envy freeness is inherently incompatible with strategy-proofness (immunity to 1979 ) and the strategic manipulation). This follows from the classic result of Green and Laffont ( fact that envy freeness implies Pareto efficiency in our setting. More importantly, we believe that, in rent division, strategic behavior does not play a significant role in practice. In particular, most Spliddit users do not know how the algorithm works, as we do not attempt to explain the algorithm itself, only its fairness guarantees. While users can experiment with Spliddit’s demo mode to de- termine the impact of various reported values on the outcome, doing this effectively would require an accurate estimate of the values submitted by others, and seems quite unwieldy in general. That said, being able to give some game-theoretic guarantees would be desirable, of course. The second question is whether the quasi-linear utility model truly captures people’s prefer- ences. For example, one participant might believe that it is unfair that he is paying more for a room he values highly, when his housemate values the two rooms equally (this happens under the maximin solution in Example 4.3 ); or some participants may have budget constraints—they simply cannot pay more than a certain price. Clearly, these are valid concerns. However, there is a tradeoff between expressiveness and ease of elicitation. We believe that quasi-linear utilities hit a sweet spot between the two, in the sense that they are reasonably expressive, yet very easy to elicit (each user simply reports a value for each room). Nevertheless, some of us are studying rent division algorithms that support richer utility functions. Taking a broader viewpoint, computational fair division is a prime example of how the interac- tion between computer science and economics can lead to novel applications. We find it particu- larly exciting that fundamental theoretical questions in this field have direct real-world implica- tions, both on Spliddit (Caragiannis et al. 2016 ) and beyond (Budish et al. 2017 ). The current article Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

18 39:18 Y. (Kobi) Gal et al. takes the computational fair division agenda a step further, by tying together theory, experiments on real data, a carefully designed user study, and a deployed application. APPENDIX 5.5 A PROOF OF THEOREM 5.4 We start by restating, and proving, Lemma . 2 1 − OPT − ∗ − + . ∈C Lemma V If 5.4 ε ( p ) ) ≥ , then there exist EF price vectors p U and − p ( ε , such that 3 3 + ∗ + ) = 0 .Moreover, D 2 ( V ) ≤ ε ,but D ε ( V ) ≥ . p U but ( be a three-player rent division instance such that v V Proof. Let x − , v = − = y 1 = x v , i i 3 i i 2 i 1 i ,where x N . We assume w.l.o.g. that y ∈ ∈ [0 , 1] for all i ≤ y i i i i x − x (1) |≤ | for all ]. , j ∈ [ n ε i j ε 2 ≥ y − + 2 ε , y y ≤ . y (2) 3 1 2 1 i to player First, we claim that the only optimal room allocation in this case is allocating room ; the total utility from this allocation is i v v ε + v . ≥ x ε + y 3 − x + + ε + 1 − y 1 + 2 + = 11 1 1 1 33 22 1 ; having Having player 1 swap rooms with either player 2 or 3 results in a utility loss of at least 2 ε ε . Finally, v players 2 or 3 swap rooms results in a utility loss of at least 3 v and + + ε ≤ 1 − 2 v 13 32 21 ;we + v i + v to player ≤ v − ε . Thus, the only optimal room allocation is allocating room i 1 23 31 12 ∑ n . v OPT again write = ii i = 1 ) y , y − − is EF. Indeed, player 1’s utility from 1 , x x ( Next, we claim that the payoff division 1 1 1 1 ε every room is 0, so she envies no one. Moreover, player 2 receives a utility of at least 2 from her room, a negative utility from room 3, and a utility of at most from room 1; this similarly holds ε + . V ) ≥ max { v ( v − , v ε − v }≥ D for player 3; thus, 13 33 22 12 Finally, let us set 1 − OPT 1 − OPT 1 − OPT 2 ε ε − − p ε . − − , p , p − − − = v = v v = + 22 3 11 33 2 1 3 3 3 3 3 3 1 − OPT ε 2 1 − OPT − − − = ) − , . In particular, ε ,and u + ( id , p ( ) = u ( id id , p p ) = u We have that 3 2 1 3 3 3 3 − ε . Moreover: ) = p ( D 2 1 − OPT ε − OPT 1 − − ≤ v = ε + − − + y = − p − + x x p − y v 1 12 1 2 11 2 2 1 3 3 3 3 1 − OPT 5 ε OPT − 1 − − + v < − ε + < p − 1 + y = + − p v − y 1 − 11 13 3 1 1 3 3 3 3 3 1 ε 1 − OPT − OPT 2 − − ≤ = + ε v + x ≤ − p + ε − x − − p v 22 1 1 21 1 2 3 3 3 3 1 OPT − OPT − 1 − − < < v − 2 ε − ( 1 − y + − 2 ε ) + p v p ≤ 1 − y − 1 1 23 22 2 3 3 3 1 − OPT 2 − − v < + ε − x − − v x ε p p ≤ + − 33 1 1 31 1 3 3 3 OPT − 1 − − v < y p − x − − ε − ( y − − x p + ε ) + v . ≤ 1 33 1 1 1 32 3 2 3 − is EF, which concludes the proof.  Thus, p Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

19 Which Is the Fairest (Rent Division) of Them All? 39:19 We are now ready to prove the theorem. ∗ C Proof of Theorem 5.5. The proof bounds the probability of drawing an instance in ) ε .We ( ∗ ( with ε agreement on the first room is equal to having ) ε observe that the probability of ∈C V ∗ ) , and having players agree on rooms 2 or 3. Thus, using the notations of the proof of ( ε ∈C V , 5.4 Lemma ∗ ∗ ε ) ] = 3 · . V Pr[ ( ( ε ) ∧∀ i , j : | x ] − x ε | < ∈C ∈C Pr[ V j i : , σ Moreover, given a permutation → ∗ > ( ε ) ∧∀ i , j : | x > − x y | < ε ∧ y ] y ∈C V Pr[ j i ( 2 ) σ 1 σ ( 3 ) σ ( ) ∗ x ε ) ∧∀ i , j : | x − ( | < ε ∧ y > y > y ] , V Pr[ = ∈C j 3 1 i 2 and thus, ∗ | ( ε ) ] = 18 Pr[ ∀ i , j : | x (6) − x , ] < ε ∧ y y > y > V ∈C Pr[ 1 j 2 3 i 5.4 . which is exactly the case discussed in Lemma ε a ,then ,if ε 3 + = a , y a = b such that b ≥ > x 25 and fixed . 0 < ε We next claim that for 1 1 2 ) ( + < ε ∧ y (7) > y , + 2 ε ∧ y − > y ε − 2 ε ] = 12 ε x ( 1 − b − 2 ε ) | b − a 2 ∀ j Pr[ : | x , i 3 1 2 j i 1 ε ,then a and if ≤ ] ε 2 + y > y − x ∧ | < ε ∧ y ε > y 2 + x | : j , i ∀ Pr[ 3 1 1 j 2 i (8) ε ( 1 = b − 2 ε )( 2 b − a − 5 ε )( ε + 2 a ) . 2 − , x that satisfy the , y y , x We establish these equations via simple integration over all values of 2 2 3 3 2 , 3 { ) by the joint density for uniform order statistics, conditions, multiplying (for each player in } which is 2. For Equation ( 7 ), we get that the probability we wish to estimate is ∫ ∫ ∫ ∫ ε + b − 2 1 a ε 4 1 . | = = x ε a x 2 : | x + − a b , | x = − x − | < ε ε y x y 2 3 2 2 2 3 3 3 The condition | x is more easily represented if we split the integral into two − a | , | x ε − x < | 3 2 2 paths: ∫ ∫ ∫ ∫ ∫ ∫ ∫ ∫ b − 2 ε a ε 2 − b ε x + + ε ε + a a 1 1 3 4 1 + 4 1 x ε = b a = + 2 = a ε x = ε = 2 + ε − a b = x − ε = = − x y x y y y x x 3 3 2 3 2 2 3 3 3 3 2 [ ] ∫ ∫ ∫ ∫ ∫ ∫ a ε b − 2 ε ε 2 − + x a + ε b a ε + 3 ( ε ) = 2 1 − b − 4 + 1 1 − a = a = ε x = − x ε x ε − a = = = x y y x x x 2 3 3 3 2 3 3 3 3 [ ] ∫ ∫ ∫ ∫ ε − 2 ε − 2 b a ε + a b 4 1 − = b − 2 ε ) ( − + ) 2 ε ) + x ( ε 2 + x − a ( a 3 3 a x = x ε = = = a − x y x y 3 3 3 3 3 3 [ ] ∫ ∫ ∫ ∫ ∫ ∫ − 2 ε a ε 2 + b ε a − b b − 2 ε ε + a 1 ) = b − ( 2 ε − 4 x ( a ) + x ( − − a ) + ε 2 3 3 = x = = x = = a − ε a − ε x = a x y y x x y 3 3 3 3 3 3 3 3 3 ] [ 1 1 2 2 2 ε ε 3 b ( ) ε ( 8 − a − 2 ε ) − − a 3 − ( 3 b − 3 a − 4 ε ) − b b ε ) ε 2 − 4 − 1 ( 4 = 6 6 2 ) ( ) 1 − b − 2 ε ( . b − a − 2 ε ε = 12 This establishes Equation ( 7 ). For Equation ( 8 ), we repeat the computation for the case where + ∈ to the ranges x ε ∈ [0 , a ] , x ]. It holds [ a , ε ] , x a ∈ [ ε , , splitting the integration on x < a ε 3 3 3 3 Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

20 39:20 Y. (Kobi) Gal et al. that ∫ ∫ ∫ ∫ 2 − ε ε 1 a b + 4 1 x ε = x 2 : | x + − a | , | 0 b − x = | < ε x = y y x 2 2 2 3 3 3 2 3 [ ∫ ∫ ∫ ∫ ∫ ∫ ∫ ∫ − a + ε ε b x 2 + ε 1 2 ε − ε 1 a b 3 4 = + 1 1 2 ε x ε = 2 = = = a 0 0 + = b 0 = = x = b + x y y x x y x y 2 3 3 3 2 3 3 2 3 2 ] ∫ ∫ ∫ ∫ a ε b − 2 ε ε + + a 1 + 1 = x = 2 + = x b − ε ε ε = x x y y 3 3 3 2 2 3 [ ] ∫ ∫ ∫ ∫ ∫ ∫ ∫ ∫ ∫ a ε + a a ε b − 2 ε ε 2 − b ε ε x 2 + ε − b + ε a + 3 4 ( 1 − = ) − 2 ε b + 1 1 + 1 x 0 = ε = 0 − x 0 = x = = a = ε = = x = x x x y y y x x x 3 3 2 2 3 3 3 2 3 3 3 3 3 [ ] ∫ ∫ ∫ ∫ ∫ ∫ 2 ε ε ε ε a b b − 2 ε − b − 2 a + = 2 4 ε ( 1 b − − ) ε ( x a + + ε ) + ( a + ε ) + ( ) 2 − x 3 3 = x = a = ε x = x = = 0 y x x y x y 3 3 3 3 3 3 3 3 3 [ ∫ ∫ ε a 2 ε 1 4 − b ( = − ) a ( b − 2 ε − x )( )( x ) + ε ) + ε x − ε 2 − ( b + 3 3 3 x x = 0 = a 3 3 ] ∫ a + ε + ε 2 ( b − 2 ε − x )( ) a − x + 3 3 = ε x 3 [ ∫ ∫ ∫ a a ε ε ) 4 ( 1 − b − = 2 ( b − 2 ε − x 2 ) x − + ε + ) b ( x − ( b − 2 ε − x ) ) ε ( a + ε 3 3 3 3 = a = 0 = 0 x x x 3 3 3 ] ∫ ∫ + a ε + ε a ) ε 2 + a ( + 2 ε − x ) ) − x ( b − x − ε 2 ( b − 3 3 3 ε = ε = x x 3 3 ) ( 1 5 2 2 3 ) 11 ε a ( 2 b − ε 2 − ε − ) a ab + ( ε − ) b 1 − 2 ( = 4 2 2 ( ) 1 2 2 aε 11 − bε ε 5 ε 2 − + a 2 − ab 4 ( ε 1 − b − 2 4 = ) 2 − 2 − b − 2 ε )( 2 b − a 1 5 ε )( ε + 2 a ) . ( ε = ). This establishes Equation ( 8 Next, we claim that if < . 2, then 0 ε 317 52 760 5063 4 3 6 2 5 ε ε ε ε ε ∧ y + > y . + 2 ε ∧ y < > y + + 2 ε ] ≥ ε − x − − | (9) x j ∀ i , : | Pr[ 3 i j 2 1 1 3 30 3 3 Indeed,notethatfor ε < 0 . 2, we have ε < 1 − 4 ε . Using Equations ( 7 ) and ( 8 ), > y x ] | < ε ∧ y ε − y 2 + 2 ε ∧ y + > Pr[ i ∀ , j : | x 3 1 2 j i 1 ε ≤ x ∧ ε 2 + + y − x > | < ε ∧ y y > y ∧ ] 2 ε ∀ x = Pr[ i , | : j 3 1 1 2 j 1 i Pr[ + i , j : | x ∀ ] − x ε | < ε ∧ y > > y x + 2 ε , y ∧ > y ε + 2 3 1 1 2 j i 1 ∫ ∫ 1 − 2 ε ε a 2 · + ε )( ε 5 − 2 a 2 ε ( ) − b − 2 ε )( 2 b − 1 ≥ 3 + a ε b 0 = a = ∫ ∫ − 4 ε 1 − 2 ε 1 2 ) ε 2 a − b )( ε 2 2 · 12 ε − ( 1 − b − + = a = b ε ε + a 3 52 760 317 5063 6 4 5 3 2 ε ε ε ε + − + − ε , = 3 3 3 30 which establishes Equation ( 9 ) Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

21 Which Is the Fairest (Rent Division) of Them All? 39:21 ∗ Fig. 6. The lower bound on the likelihood of ( ε ) ,where ε ∈ [0 , 0 . 2] is plotted on the x -axis. ∈C V 9 ) with Equation ( 6 Finally, in order to obtain the lower bound, we simply combine Equation ( ), ε 0 . 2, ) by 18. It follows that for 9 that is, multiply the bound of Equation ( < 15189 ∗ 6 5 4 3 2 ε ε ) − 4560 ε ] + 1902 ε ≥ − 312 ε . + 18 ε (  ∈C Pr[ V 5 ∗ 6 provides a graphical representation of our lower bound on Pr[ ∈C Figure V ε ) ( ] as a function . ε of ACKNOWLEDGMENTS We thank Ron Kupfer for helpful comments. REFERENCES A. Abdulkadiroğlu, T. Sönmez, and M. U. Ünver. 2004. Room assignment-rent division: A market approach. Social Choice 22, 3 (2004), 515–538. and Welfare A. Alkan, G. Demange, and D. Gale. 1991. Fair allocation of indivisible goods and criteria of justice. Econometrica 59, 4 (1991), 1023–1039. E. Aragones. 1995. A derivation of the money Rawlsian solution. 12 (1995), 267–276. Social Choice and Welfare Journal of Political Economy 109 (2001), 418–443. S. J. Brams and D. M. Kilgour. 2001. Competitive fair division. E. Budish, G. P. Cachon, J. Kessler, and A. Othman. 2017. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research 65, 2 (2017), 314–336. I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. 2016. The unreasonable fairness of maximum Nash product. In Proceedings of the 17th ACM Conference on Economics and Computation (EC’16) . 305–322. N. Dupuis-Roy and F. Gosselin. 2011. The simpler, the better: A new challenge for fair-division theory. In Proceedings of . 3229–3234. the 33rd Annual Meeting of the Cognitive Science Society (CogSci’11) Yale Economics Essays 7 (1967), 45–98. D. Foley. 1967. Resource allocation and the public sector. SIGecom Exchanges 13, 2 (2014), 41–46. J. Goldman and A. D. Procaccia. 2014. Spliddit: Unleashing fair division algorithms. Incentives in Public Decision Making . North Holland. J. R. Green and J.-J. Laffont. 1979. C.-J. Haake, M. G. Raith, and F. E. Su. 2002. Bidding for envy-freeness: A procedural approach to n -player fair-division problems. Social Choice and Welfare 19 (2002), 723–749. D. K. Herreiner and C. D. Puppe. 2009. Envy freeness in experimental fair division problems. 67, 1 Theory and Decision (2009), 65–100. D. K. Herreiner and C. D. Puppe. 2010. Inequality aversion and efficiency with ordinal and cardinal social preferences—An experimental study. Journal of Economic Behavior & Organization 76, 2 (2010), 238–253. F. Klijn. 2000. An algorithm for envy-free allocations in an economy with indivisible objects and money. Social Choice and Welfare 17 (2000), 201–215. S. Kohler. 2013. Envy can promote more equal division in alternating-offer bargaining. Journal of Neuroscience, Psychology, and Economics 1, 6 (2013), 31–41. Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

22 39:22 Y. (Kobi) Gal et al. Microeconomic Theory A. Mas-Colell, M. D. Whinston, and J. R. Green. 1995. . Oxford University Press. G. Schneider and U. S. Krämer. 2004. The limitations of fair division: An experimental evaluation of three procedures. Journal of Conflict Resolution 48, 4 (2004), 506–524. F. E. Su. 1999. Rental harmony: Sperner’s lemma in fair division. 106, 10 (1999), 930–942. American Mathematical Monthly L.-G. Svensson. 1983. Large indivisibles: An analysis with respect to price equilibrium and fairness. Econometrica 51, 4 (1983), 939–954. L.-G. Svensson. 2009. Coalitional strategy-proofness and fairness. Economic Theory 40, 2 (2009), 227–245. K. Tadenuma and W. Thomson. 1991. No-envy and consistency in economies with indivisible goods. 59, 6 Econometrica (1991), 1755–1767. K. Tadenuma and W. Thomson. 1995. Refinements of the no-envy solution in economies with indivisible goods. Theory and Decision 39, 2 (1995), 189–206. R. Velez. 2017. Sharing an increase of the rent fairly. Social Choice and Welfare 48, 1 (2017), 59–80. Received September 2016; accepted July 2017 Journal of the ACM, Vol. 64, No. 6, Article 39. Publication date: November 2017.

### Related documents ### RIE Tenant List By Docket Number

SCRIE TENANTS LIST ~ By Docket Number ~ Borough of Bronx SCRIE in the last year; it includes tenants that have a lease expiration date equal or who have received • This report displays information on ... ### Out of Reach 2018

2018 of OUT REACH THE HIGH COST OF HOUSING MADE POSSIBLE BY THE GENEROSITY OF: ### Out of Reach 2016

No Refuge for Low Income Renters MADE POSSIBLE BY THE GENEROSITY OF: ### Small Area Fair Market Rent Demonstration Evaluation Interim Report

Small Area Fair Market Rent Demonstration Evaluation Interim Report U.S. Department of Housing and Urban Development | Office of Policy Development and Research ### Man, Economy, and State with Power and Market ### What Happens to Low Income Housing Tax Credit Properties at Year 15 and Beyond?

WHAT HAPPENS TO LOW–INCOME HOUSING TAX CREDIT PROPERTIES AT YEAR 15 AND BEYOND? U.S. Department of Housing and Urban Development | Office of Policy Development and Research ### Microsoft Word Sec8HousingChoice Website Abridged FINAL BW 9 27 2017.rtf

e c ram The New York City Department of Housing Preservation and Development g hoi c ro g p usin o h Section 8 Housing Choice Voucher Program Briefing Book voucher ### Losing Home 2018

LOSING HOME The Human Cost of Eviction in Seattle A Report by the Seattle Women's Commission and the Housing Justice Project of the King County Bar Association. ### Government Finance Statistics Manual 2014

MANUAL GOVERNMENT FINANCE STATISTICS MANUAL 2014 2014 INTERNATIONAL MONETARY FUND ### Capital Volume I

Capital A Critique of Political Economy Volume I Book One: The Process of Production of Capital First published: in German in 1867, English edition first published in 1887; Source: First English editi... ### seea cf final en

System of Environmental-Economic Accounting 2012 Central Framework Food and European Organisation for The World Bank United International Economic Co-operation Monetary Commission Agriculture Nations ... ### ruta i xx.indd

WHERE IS THE Wealth of NATIONS? ### A Treatise on Political Economy ### The Rate of Return on Everything, 1870–2015

FEDERAL RESERVE BANK OF SAN FRANCISCO WORKING PAPER SERIES –2015 The Rate of Return on Everything, 1870 Òscar Jordà Reserve Bank of San Francisco Federal University of California, Davis Katharina Knol... ### doj final opinion

UNITED STAT ES DIS TRICT COURT IC F OR THE D ISTR T OF CO LU M BIA UNITED STAT F AMERICA, : ES O : : la in t if f, P 99 No. on cti l A vi Ci : 96 (GK) -24 : and : TOBACCO-F UND, : REE KIDS ACTION F : ... ### EPRS STU(2016)558777 EN

- The Cost of Non Europe in the Sharing Economy Economic, Social and Legal Challenges and Opportunities STUDY EPRS | European Parliamentary Research Service Author: Pierre Goudin Unit European Added V... ### Markets Not Capitalism

markEts not caPItalIsm individualist anarchism against bosses, inequality, corporate power, and structural poverty Edited by Gary Chartier & Charles W. Johnson ### Facing Our Future

Ou Facing r Fut ure Afte of n the Children i rmath Immigration Enforcement y udr Cha Ajay F a Randy Capps c i n Pedr Manuel Juan a oz g O u ñeda Rosa Mar ia Ca sta r F Rober t Santos u t u r tt Molly ... ### A Good Tax: Legal and Policy Issues for the Property Tax in the United States

YOUNGMAN A GOOD TAX Legal and Policy Issues for the Property Tax in the United States Joan Youngman “In this marvelous book, Joan Youngman makes a spirited case for a vibrant local property tax. She p... ### News and noise in the housing market

Working Paper Series Andrea Gazzani News and noise in the housing market 1933 / No 2016 July Note: This Working Paper should not be reported as representing the views of the European Central Bank (ECB...