# fair_rent_division_on_a_budget__abcbac79.pdf

Fair Rent Division on a Budget

Ariel D. Procaccia Computer Science Department Carnegie Mellon University

Rodrigo A. Velez Department of Economics Texas A&M University

Dingli Yu Institute for Interdisciplinary Information Sciences Tsinghua University

The standard approach to fair rent division assumes that agents have quasi-linear utilities, and seeks allocations that are envy free; it underlies an algorithm that is widely used in practice. However, this approach does not take budget constraints into account, and, therefore, may assign agents to rooms they cannot afford. By contrast, we design a polynomial-time algorithm that takes budget constraints as part of its input; it determines whether there exist envy-free allocations that satisfy the budget constraints, and, if so, computes one that optimizes an additional criterion of justice. In particular, this gives a polynomial-time implementation of the budget-constrained maximin solution, where the maximization objective is the minimum utility of any agent. We show that, like its non-budget-constrained counterpart, this solution is unique in terms of utilities (when it exists), and satisfies additional desirable properties.

1 Introduction

A recent story in New Scientist1 nicely introduces a familiar dilemma: Every renter knows that not all rooms are created equally. One bedroom might have an en-suite bathroom and a view of the seaside, whereas another is half the size and overlooks a dump. It s only fair that the person who gets the better room pays a larger share of the rent. The question [...] is: how much? The ubiquity and simplicity of the rent division problem have made it a poster child for computational fair division. Indeed, of the five applications on the not-for-profit fair division website Spliddit.org (Goldman and Procaccia 2014), the rent calculator is the most popular almost 30,000 rent division instances have been created by users since the website s launch in November 2014. The standard rent division setup involves n agents, who share an apartment with n rooms. Every agent has a value for each room. An allocation matches the agents with rooms, and assigns a price to each room, such that the prices add up

Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 1https://www.newscientist.com/article/2137642maths-website-stops-you-being-ripped-off-by-yourflatmates

to the total rent. We make the standard assumption that the utility functions of the agents are quasi-linear: the utility of an agent for getting a room he values at x for the price of y is x y. The goal is to find an allocation that is envy free: the utility of each agent for his room at its price should be at least as high as his utility for any other room, at the price of that room. It is well known that an envy-free allocation always exists (Svensson 1983), and one can be computed in polynomial time (Aragones 1995). In fact, there is an embarrassment of riches, as there are typically many envy-free allocations, which necessitates selecting between them. A natural choice is the maximin solution of Alkan et al. (1991), which selects the allocation that maximizes the minimum utility of any agent, subject to the envy-freeness constraint. A linear-programming-based algorithm of Gal et al. (2017) can compute the maximin solution in polynomial time; this algorithm has been deployed on Spliddit since May 2015. One advantage of the foregoing approach (especially the assumption of quasi-linear utilities) is that preference elicitation is straightforward: participants only need to report their value for each room. It many ways, it does hit a sweet spot between expressiveness and ease of elicitation. But it certainly does not address the needs of some users, and its most prominent shortcoming is ignoring budget constraints. This is reflected in feedback from Spliddit users the following representative example was submitted in December 2016:

I ve tried to use your fair calculator, but it did not work in my case. In our situation, I am the guy with the most tight [sic] budget. Unfortunately, your system does not take into account the maximum budget restrictions. I was assigned an option that was too expensive for me, so it did not help. Please advise if there is a way to use the system, taking that kind of limitation into account.

Unfortunately, when agents are budget-constrained, an envy-free allocation is no longer guaranteed to exist. For example, suppose there are two agents; a total rent of $1000; two rooms where the first is valued at $800 by both agents, and the second is valued at $200 by both agents; and budget constraints of $600 for both agents. To avoid envy, the desirable room must be priced at $800, but this is more than either agent can pay.

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

Our goal in this paper, therefore, is to gain a rigorous understanding of the budget-constrained rent division problem. In particular, we would like to be able to say (algorithmically) when the set of envy-free allocations is nonempty under budget constraints, and, when it is, select among these allocations in a principled way.

1.1 Our Results In Section 3, we construct a polynomial-time (LP-based) algorithm that computes an optimal allocation with respect to a given (linear) criterion of justice, subject to the envyfreeness constraints and the given budget constraints, when a feasible allocation exists. This algorithm extends that of Gal et al. (2017) to the budget-constrained setting, but, for reasons that we explain in detail, its design and analysis are significantly more involved. The obvious next question is: What should we use as the optimization objective? The foregoing algorithm can be used to compute the budget-constrained maximin solution which maximizes the minimum utility of any agent subject to envy-freeness and the budget constraints when a feasible solution exists. It can also compute the budget-constrained version of the equitable solution (Gal et al. 2017), where the objective is to minimize the maximum difference in utilities between any two agents. We show that the properties that make the maximin solution attractive in the non-budgetconstrained setting extend to the budget constrained setting: it is unique in terms of utilities, and it dominates the equitable solution, in the sense that any budget-constrained maximin solution is a budget-constrained equitable solution, but not vice versa. Finally, we extend our algorithms in order to compute, in polynomial time, an optimal allocation, subject to the envy-freeness constraint and the minimization of the maximum budget violation among agents this recommendation exists for all possible instances.

1.2 Significance in AI Work on computational fair division has been featured prominently in recent AI conferences (Bliem, Bredereck, and Niedermeier 2016; Kurokawa, Procaccia, and Wang 2016; Brˆanzei et al. 2016; Aziz et al. 2017; Bei, Qiao, and Zhang 2017; Bouveret et al. 2017; Menon and Larson 2017; Aleksandrov and Walsh 2017). The surge in excitement is driven in part by a newfound understanding that, beyond potential applications to multiagent systems, fair division algorithms can play a role in helping groups of people make decisions on a large scale. Our paper contributes to this line of work in that it is driven by real-world needs, and provides practicable solutions that are likely to be deployed.

2 The Model

We study the allocation of a set of n objects A of indivisible goods, that we refer to as rooms, among a set of n agents N {1, ..., n}. Generic rooms are denoted by letters such as a, b. Each agent is to receive a room and pay an amount of money for it. Agents have quasi-linear preferences on their allotments, i.e., agent i s utility from receiving room a and paying pa for it is via pa. The profile of agents values

is v (via)i N,a A. We assume that individual payments should add up to a fixed amount that we refer to as the house rent r. An economy is then a tuple e (N, A, v, r). An allocation for e (N, A, v, r) is a pair (σ, p), where the assignment σ : N A is a bijection, and the vector of prices p (pa)a A is such that

a A pa = r. That is, under the allocation (σ, p), agent i is assigned the room σ(i) for the price pσ(i). An allocation is envy free if no agent prefers the consumption of any other agent at the allocation, i.e., for all i, j N,

viσ(i) pσ(i) viσ(j) pσ(j).

The set of envy-free allocations for the economy e is F(e).2 We assume that agents may be budget constrained. For each i, there is bi R {+ } which is the maximum amount that the agent can pay for any room. The vector of budget constraints is b (bi)i N. An allocation (σ, p) satisfies budget constraints b if for each i N, pσ(i) bi. For a vector of budget constraints b, the set of envy-free budgetconstrained allocations is Fb(e). It is well known that for each e, F(e) is a non-empty compact set. Moreover, one can calculate directly from an agent s utility function an upper bound for his consumptions in each allocation in F(e). Thus, we can assume without loss of generality that b Rn.

3 A Polynomial-Time Algorithm

For a given economy, e (N, A, v, r) and a vector of budget constraints b, we are primarily interested in determining whether Fb(e) = . If so, we are interested in selecting an element of Fb(e) that optimizes an additional criterion of justice. The rest of the section is devoted to understanding and proving the following theorem, which is our main result: Theorem 1. Let e (N, A, v, r), b (bi)i N, and, for s [t], where t is polynomial in n, let fs : Rn R be a linear function. Then there is a polynomial-time algorithm that determines whether Fb(e) = , and, if so, outputs an allocation (σ, p) Fb(e) that maximizes

min s [t] fs v1σ(1) pσ(1), . . . , vnσ(n) pσ(n)

over all allocations in Fb(e). Gal et al. (2017) pay special attention to two particular optimization objectives: maximizing the minimum utility of any agent, which is obtained by simply letting

fi v1σ(1) pσ(1), . . . , vnσ(n) pσ(n) = viσ(i) pσ(i) for all i N; and minimizing the social disparity defined as the maximum difference in utilities between any

2Notice that we allow negative payments and we do not restrict valuation profiles. Thus, in our domain there are profiles in which there is no envy-free allocation with non-negative prices. At the cost of some additional notation one can easily add reasonable restrictions on preferences which would guarantee envy-free allocations with non-negative prices (Velez 2017). In practice, this is a rather minor issue, as on Spliddit only a tiny fraction of instances lead to negative prices.

two agents which can also be easily captured using the same formalism. We discuss the relation between these two objectives in Section 4; for now we focus on the algorithmic question. Our starting point is a simple algorithm of Gal et al. (2017), which achieves the equivalent result to Theorem 1 without budget constraints, i.e., it finds the optimal allocation in F(e) (which is always nonempty, under their assumptions on valuations). However, we provide the requisite background from a different viewpoint, in order to be consistent with the subsequent presentation of our own algorithm. For e (N, A, v, r), an assignment σ is efficient if it maximizes the sum of agents values, i.e., i N viσ(i), among all assignments. Basic LP theory shows that the dual variables in the problem determining an efficient assignment provide an envy-free allocation (Alkan, Demange, and Gale 1991, Duality Theorem). This implies that each efficient assignment can be completed into an envy-free allocation. Conversely, an assignment in an envy-free allocation is always efficient (Svensson 1983). Two additional facts solve the puzzle. For any two allocations {(σ, p), (μ, q)} F(e), both (μ, p) and (σ, q) are also in F(e) (Svensson 2009).3 Moreover, each agent is indifferent between (σ, p) and (μ, p) (this follows from Lemma 1 below). Thus, as observed by Gal et al. (2017), it is sufficient to calculate an efficient assignment σ (which can be done in polynomial time by reducing the problem to maximum weight matching in a bipartite graph), and then solving the following LP, which uses the same notations as Theorem 1:

max x,pσ(1),...,pσ(n)x

i N pσ(i) = r

s [t], x fs v1σ(1) pσ(1), . . . , vnσ(n) pσ(n)

i, j N, viσ(i) pσ(i) viσ(j) pσ(j) To be clear, the second constraint guarantees that x is set to the minimum of the given linear functions, and the third ensures that the allocation (σ, p) is envy free. It is tempting think that one can adapt the algorithm of Gal et al. (2017) to our problem by simply adding the budget constraints to the above LP:

max x,pσ(1),...,pσ(n)x

i N pσ(i) = r

s [t], x fs v1σ(1) pσ(1), . . . , vnσ(n) pσ(n)

i, j N, viσ(i) pσ(i) viσ(j) pσ(j) i N, pσ(i) bi (1) However, the basic premise behind their algorithm that one can start from any efficient assignment is false in our setting, as shown by the following example.

3We provide a simple proof of this fact embedded in our proof of Lemma 2.

Example 1. Let N = {1, 2}, A = {a, b}, and r = 1. For i = 1, 2, via=1 and vib=0. Moreover, b1 = 1 and b2 = 0. The allocation that assigns room a to agent 1 for pa = 1, and room b to agent 2 for pb = 0, is envy free and satisfies the budget constraints. However, if we start from assigning room a to agent 2, and room b to agent 1 which is also efficient then there is no vector of prices that leads to an envy-free allocation satisfying the budget constraints: Due to the budget constraint of agent 2, we must have pσ(2) = 0, even though he is now assigned the valuable room, so agent 1 must be envious.

Example 1 suggests that we need to develop a new algorithmic approach in order to prove Theorem 1. We start with several lemmas. The first (Lemma 1) is well known. We present a proof of Lemma 3 for completeness. The rest are new.

Lemma 1 (Alkan, Demange, and Gale 1991). Let {(σ, p), (μ, q)} F(e). Then σ and μ are both bijections between the following sets:

{i N : viσ(i) pσ(i) > viμ(i) qμ(i)} and

{a A : pa < qa}, {i N : viσ(i) pσ(i) = viμ(i) qμ(i)} and

{a A : pa = qa}, {i N : viσ(i) pσ(i) < viμ(i) qμ(i)} and

{a A : pa > qa}.

Before proceeding, we introduce a concept that has played a role in several previous papers. For each (σ, p) F(e) define the weak envy graph by Γ(σ, p) (N, E), where (i, j) E if and only if viσ(i) pσ(i) = viσ(j) pσ(j). That is, it is the graph where the vertices are agents, and there is an edge between i and j if i weakly envies j under (σ, p). Note that i cannot strictly envy j because the allocation is envy free.

Lemma 2. Let {(σ, p), (μ, q)} F(e). for all i N, j = σ 1(μ(i)), i and j are strongly connected in both Γ(σ, p) and Γ(μ, p).

Proof. Since {(σ, p), (μ, q)} F(e), (μ, p) F(e).4 By Lemma 1 applied to (σ, p) and (μ, p), for each i N,

viσ(i) pσ(i) = viμ(i) pμ(i),

i.e., (i, σ 1(μ(i))) is an edge of Γ(σ, p). Let ν = σ 1 μ, then i ν(i) = j ν2(i) i is a cycle in Γ(σ, p), because ν is a permutation on N and can be decomposed into cycles. Similarly, we have (ν(i), i) is an edge of Γ(μ, p) for all i N, and hence i, ν(i) = j, ν2(i), ν3(i), . . . are also strongly connected in Γ(μ, p).

4This was proved by Svensson (2009), and also follows from the Second Welfare Theorem, as noted by Gal et al. (2017). The following is a simple proof: Suppose that {(σ, p), (μ, q)} F(e). Since (μ, q) F(e), for each i N, viσ(i) qσ(i) viμ(i) qμ(i). Adding up these n inequalities we find expressions that are equal because both σ and μ are efficient. Thus, for each i N, viσ(i) qσ(i) = viμ(i) qμ(i), and it follows that (σ, q) F(e).

Lemma 3 (Andersson, Ehlers, and Svensson 2014). The set of strongly connected components of Γ(σ, p) is invariant for each allocation in F(e).

Proof. Suppose that {(σ, p), (μ, q)} F(e). Then, (σ, q) F(e) (Svensson 2009). Suppose without loss of generality that 1, ..., K are the vertices of cycle {(1, 2), ..., (K, 1)} Γ(σ, p). Since (σ, q) F(e), for each k = 1, .., K, vkσ(k) qσ(k) vkσ(k+1) qσ(k+1) where K + 1 = 1. Adding up these K inequalities we find expressions that are equal because both σ and the assignment obtained by reshuffling along the cycle are efficient. Thus, for each for each k = 1, .., K, vkσ(k) qσ(k) = vkσ(k+1) qσ(k+1). It follows that the set of strongly connected components of Γ(σ, p) is contained in that of Γ(σ, q). Let (i, j) be an edge of Γ(σ, q). Let k N be such that μ(k) = σ(j), and, therefore,

viσ(i) + qσ(i) = viμ(k) + qμ(k).

By Lemma 1, and using {(μ, q), (σ, q)} F(e),

viμ(i) + qμ(i) = viσ(i) + qσ(i).

Combining the two equalities, we get

viμ(i) + qμ(i) = viμ(k) + qμ(k),

that is, (i, k) is an edge of Γ(μ, q). Now, by Lemma 2, since j = σ 1(μ(k)), j and k are strongly connected in Γ(μ, q). We conclude that there is a path from i to j in Γ(μ, q). Since this is true for every edge (i, j) of Γ(σ, q), the set of strongly connected components of Γ(σ, q) is contained in that of Γ(μ, q).

Lemma 3 allows us to define the set of strongly connected components of the envy-free graph associated with a triple (N, A, v) as Γ(σ, p) for some r R and (σ, p) F(N, A, v, r). Let C(N, A, v) be the partition of N into strongly connected components of the envy-free graph in the set of economies {(N, A, v, r) : r R}. For technical reasons which will become clear momentarily, we are especially interested in the class of economies where all agents are strongly connected. The following lemma states some useful properties of envy-free allocations in these economies.

Lemma 4. Let N, A, v, and suppose that C(N, A, v) = {N}. Then for all r R:

1. If {(σ, p), (μ, q)} F(N, A, v, r), then p = q. 2. Each agent is indifferent among all allocations in F(N, A, v, r). 3. Let (σ, p) F(N, A, v, r). For any s R, (μ, q) F(N, A, v, s), and a A, qa = pa + (s r)/n. 4. The rent of each room in any element of F(N, A, v, r) is an increasing function of r.

Proof. We first prove Statement 1. Suppose (i, j) is an edge of Γ(σ, p) and pσ(j) qσ(j). Then

viσ(i) pσ(i) = viσ(j) pσ(j) viσ(j) qσ(j) viσ(i) qσ(i),

where the first transition follows from the former assumption, the second from the latter, and the third from (σ, q) F(N, A, v, r) (Svensson 2009). Thus, pσ(i) qσ(i). Thus, if there is a path from i to j in Γ(σ, p) and pσ(j) qσ(j), then pσ(i) qσ(i). Since a A pa = a A qa, there is a A such that pa qa. Thus, using the assumption that C(N, A, v) = {N}, for each a A, pa qa. We conclude that p = q. Statement 2 follows directly from 1 and Lemma 1. Statement 3 follows from Statement 1 and the observation that, since preferences are quasi-linear, (μ, q) F(N, A, v, s), where q is defined by qa = pa + (s r)/n for all a A. Statement 4 follows directly from Statement 3.

Observe that the envy-free graph could have been defined by identifying vertices with rooms, not agents as we did. Doing so would also produce a partition of the set of rooms into strongly connected components that is common for all envy-free allocations in an economy. There is a one-to-one correspondence between the two approaches.

Lemma 5. Let e (N, A, v, r) and C C(N, A, v). Then, for any two efficient assignments for e, σ and μ, σ(C) = μ(C).

Proof. Let {(σ, p), (μ, q)} F(e). Let i N and let C C(N, A, v) be such that i C. Let j be such that μ(j) = σ(i). Recall that (σ, q) F(e) (Svensson 2009). By Lemma 2, since i = σ 1(μ(j)), i, j must be strongly connected in Γ(σ, q). By Lemma 3, j C as well. We conclude that σ(C) μ(C).

The previous lemma implies that even though there can be many efficient assignments in an economy, there is only one efficient assignment of rooms among the strongly connected components of the envy-free graph of the economy. Given N, A, v, and C C(N, A, v), let A(C) be the set of rooms received by agents in C at some envy-free allocation for e. Furthermore, let v C and b C be the restrictions of the two vectors to C, and let δC R the maximum s R for which Fb C(C, A(C), v C, s) = . Note that δC exists because utility functions are continuous.

Lemma 6. Let e (N, A, v, r) and a vector of budget constraints b. For each C C(N, A, v), let b C (bi)i C, v C (via)i C,a A(C), and suppose that (μC, p A(C)) Fb C(C, A(C), v C, δC). Let μ be the allocation that for each i N, μ(i) = μC(i) where C C(N, A, v) and i C. Then, Fb(e) = if and only if LP (1) for assignment μ is feasible.

Proof. Clearly Fb(e) = if LP (1) is feasible. In the other direction, suppose that (σ, q) Fb(e). We claim that (μ, q) Fb(e). We know that (μ, q) F(e) (Svensson 2009). To show that the budget constraints are satisfied, let C C(N, A, v). Then

i C qμ(i) =

i C qσ(i) δC,

where the equality holds due to Lemma 5, and the inequality holds because otherwise (σC, q A(C)) Fb C(C, v C, s) with

s > δC. By Statement 4 in Lemma 4, for each i C, qμ(i) pμ(i) bi.

Thus, we can restrict the solution of our problem to economies that are fully connected. Our first algorithm, given as Algorithm 1, applies to such economies. The algorithm uses a budget-aware type of weak envy graph, which we denote by Γb(σ, p) = (N, E), where

E = {(i, j) : viσ(i) pσ(i) = viσ(j) pσ(i) and pσ(j) < bi}.

1: compute (σ, p) F(N, A, v, r) for some r R 2: let Δ R such that

(σ, (pa Δ)a A) Fb(N, C, v, r nΔ)

and there is i N such that pσ(i) = bi 3: p (pσ(i) Δ)i N 4: r r nΔ 5: while i N s.t. pσ(i) = bi and i is not a vertex of a cycle of Γb(σ, p) do 6: if i N s.t. pσ(i) = bi then {Case 1} 7: Δ mini N(bi pσ(i)) 8: p (pa + Δ)a A 9: r r + nΔ 10: else {Case 2} 11: find i N s.t. pσ(i) = bi and i is a vertex of a cycle C of Γb(σ, p) 12: σ reshuffle of σ along C 13: end if 14: end while 15: return r and (σ, p)

Algorithm 1: Maximum-rent envy-free allocation in a fully connected economy.

Lemma 7. For each N, A, v such that C(N, A, v) = {N}, and b (bi)i N, Algorithm 1 terminates in polynomial time. If r and (σ, p) are the output of Algorithm 1, (σ, p) Fb(N, A, v, r), and δN = r, i.e., for each s > r, Fb(N, A, v, s) = .

Proof. We first prove that Algorithm 1 terminates in polynomial time. The initial computation of (σ, p) in Line 1 can be done, e.g., using the algorithm of Gal et al. (2017). Case 2 (Line 10) is repeated at most n times before the algorithm either terminates or Case 1 (Line 6) holds. Case 1 holds at most n2 times, because here an agent meets his budget constraint for a certain room, and the prices of rooms strictly increase each time Case 1 holds. We now turn to the claims about the output of the algorithm; suppose r and (σ, p) are that output. By construction, (σ, p) Fb(N, A, v, r), as this holds before the while loop, and every subsequent operation maintains envy-freeness and budget feasibility. Next, we claim that for each s > r, Fb(N, A, v, s) = . Suppose for the sake of contradiction that there is s > r and (μ, q) Fb(N, A, v, s). Let Δ (s r)/n. By Statement 3 of Lemma 4, for each a A, qa = pa + Δ. Recall that

(μ, p) F(N, A, v, r) (Svensson 2009). Similarly to the proof of Lemma 2, by Lemma 1, we have that for all i N,

viσ(i) pσ(i) = viμ(i) pμ(i).

Along with pμ(i) = qμ(i) Δ < bi,

it follows that (i, σ 1(μ(i))) must be an edge of Γb(σ, p) for any i. Let ν = σ 1 μ, then for all i N, i ν(i) ν2(i) i is a cycle of Γb(σ, p). Also notice that the while loop only terminates when there is i N such that pσ(i) = bi. Therefore, agent i satisfies the conditions of Case 2, and the algorithm should not have terminated.

We are finally ready to present our main algorithm, given as Algorithm 2, and its analysis, which completes the proof of Theorem 1.

1: compute (σ, p) F(N, A, v, r) 2: C strongly connected components of Γ(σ, p) 3: for each C C do 4: (μC, p C) output of Algorithm 1 on C, A(C), v C, and b C 5: end for 6: let μ : N A s.t. for all i N, μ(i) = μC(i) for C C s.t. i C 7: if LP (1) for μ is feasible then 8: p solution of LP (1) for μ 9: return (μ, p) 10: else 11: return no solution 12: end if Algorithm 2: Optimal envy-free allocation subject to budget constraints.

Proof of Theorem 1. We first claim that if the algorithm outputs no solution then Fb(e) = . Indeed, by Lemma 7, the rent r output by Algorithm 1 on component C is exactly the δC in the statement of Lemma 6, hence the claim follows from Lemma 6. Next, suppose that the algorithm outputs (μ, p). Since this allocation solves LP (1), (μ, p) Fb(e). Let (η, q) be a maximizer of the minimum of f1, ..., ft applied to the vector of utilities among all allocations in Fb(e). Then as a byproduct of Lemma 6, we have (μ, q) Fb(e), which means that (μ, q) is an optimal solution to LP (1). Moreover, by Lemma 1, all agents are indifferent between (μ, q) and (η, q), so the objective value under (μ, p) must be at least the objective value under (η, q).

4 Fairest Budget-Constrained Allocations

The algorithm of Section 3 provides a practical method for selecting an allocation in Fb(e) maximizing an objective function, when Fb(e) = . Gal et al. (2017) have identified the maximin solution, which maximizes the minimum utility of any agent subject to envy-freeness, as an especially desirable solution. Our goal in this section is to show that

this solution has similar properties even under budget constraints. Formally, given an allocation (σ, p) F(N, A, v, r), let U(σ, p) = min i N viσ(i) pσ(i).

The budget-constrained maximin solution returns an allocation in argmax(σ,p) Fb(e) U(σ, p) when Fb(e) = . The following theorem asserts that agent utilities under the budget-constrained maximin solution are unique, thus eliminating the potential need to select among multiple solutions; it extends a result of Alkan et al. (1991) to the budgeted setting. Theorem 2. Let {(σ, p), (μ, q)} argmax (σ ,p ) Fb(e) U(σ , p ).

Then for all i N, viσ(i) pσ(i) = viμ(i) qμ(i). Proof. We first claim that it is sufficient to show that for every {(σ, p), (σ, q)} argmax(σ ,p ) Fb(e) U(σ , p ), p = q, i.e., we can assume the two assignments are identical. Indeed, let (σ, p) and (μ, q) be budget-constrained maximin solutions, and let (η, o) be the output of Algorithm 2. Then, as a byproduct of Lemma 6, {(η, p), (η, q)} Fb(e). By Lemma 1, all agents are indifferent between (σ, p) and (η, p), and between (μ, q) and (η, q), that is, {(η, p), (η, q)} argmax (σ ,p ) Fb(e) U(σ , p ).

Now, suppose for contradiction that there exist {(σ, p), (σ, q)} argmax (σ ,p ) Fb(e) U(σ , p )

such that p = q. Consider the price vector o such that a A, oa = max{pa, qa}. Although

i N oσ(i) > r, o clearly satisfies the budget constraints, i.e., for all i N, oσ(i) bi. Moreover, (σ, o) is envy free, because for all i, j N, viσ(i) oσ(i) = min{viσ(i) pσ(i), viσ(i) qσ(i)}

min{viσ(j) pσ(j), viσ(j) qσ(j)}

= viσ(j) oσ(j).

i N oσ(i), and define a price vector o by o a = oa (s r)/n for all a A. Then

i N o σ(i) =

oσ(i) (s r)/n = s s + r = r.

In addition, (s r)/n > 0, so (σ, o ) Fb(N, A, v, r). Finally, since for all i N, viσ(i) o σ(i) > viσ(i) oσ(i) = viσ(i) max{pσ(i), qσ(i)},

it holds that U(σ, o ) = min i N(viσ(i) o σ(i))

> min i N(viσ(i) max{pσ(i), qσ(i)})

= min{U(σ, p), U(σ, q)}. We conclude that that (σ, p) and (σ, q) are not budgetconstrained maximin solutions a contradiction to our assumption.

While the budget-constrained maximin solution is conceptually appealing, previous work in behavioral economics (Herreiner and Puppe 2009) has shown that social disparity the maximum difference in utilities between any two agents plays a major role in whether allocations are perceived as fair. Formally, define

D(σ, p) = max i N (viσ(i) pσ(i)) min i N(viσ(i) pσ(i)).

The budget-constrained equitable solution returns an allocation in argmin(σ,p) Fb(e) D(σ, p) when Fb(e) = . Surprisingly, Gal et al. (2017) show that, without budget constraints, any maximin solution is also an equitable solution. Here we generalize their result to the budget-constrained setting.5

Theorem 3. If (σ, p) is a budget-constrained maximin solution, then it is a budget-constrained equitable solution.

Proof. Let G = (N {0}, E) be a directed graph such that there is a edge from i N to 0 if and only if viσ(i) pσ(i) = U(σ, p) or pσ(i) = bi; and there is a edge from i N to j N if and only if

viσ(i) pσ(i) = viσ(j) pj.

We first claim that for all i N, there is a path from i to 0. Indeed, assume for contradiction that this is not the case, and let S be the set of all i N that have paths to 0 in G. Since S = and N S = , we can define another price vector p such that

p σ(i) = pσ(i) ε i S pσ(i) + |S| n |S|ε i / S

where ε > 0. Clearly i N p σ(i) = r. Also, we can set ε small enough to satisfy the following properties:

i / S, viσ(i) p σ(i) > U(σ, p);

i / S, p σ(i) < bi;

i / S, j S, viσ(i) p σ(i) > viσ(j) p σ(j). (This is because no i / S weakly envies j S in (σ, p), otherwise i would have a path to 0.)

Therefore, (σ, p ) Fb(N, A, v, r). Moreover, since for all i S,

viσ(i) p σ(i) > viσ(i) pσ(i) U(σ, p),

U(σ, p ) > U(σ, p), which contradicts the assumption that (σ, p) is a budget-constrained maximin solution.

5In contrast to the other sections of the paper, in which substantial technical difficulties have to be addressed, the core of the argument here is similar to that of Gal et al. (2017). The maximin solution is characterized by paths of the weak envy graph that flow from each agent to either a budget-constrained agent or a minimum utility agent. Thus, no agent who is indirectly budget constrained can reduce his utility while maintaining no-envy and satisfying the budget constraints. Of course, reducing utility disparity requires some agent to decrease his utility. Thus the problem is reduced, as in the work of Gal et al. (2017), to showing that this cannot be done among the agents who are not budget constrained.

Next, let (σ , p ) be a budget-constrained equitable solution. Using similar arguments to those at the beginning of the proof of Theorem 2, we can assume without loss of generality that σ = σ, that is, it is sufficient to show that D(σ, p) D(σ, p ). Let ε = U(σ, p) U(σ, p ). Since (σ, p) is a budgetconstrained maximin solution, ε 0. We claim that for all a A, p a pa + ε. Indeed, consider a path

in G. Since such a path exists for all i1 N, it is sufficient to prove that p σ(i1) pσ(i1) + ε. We prove the claim by induction on the length of the path ℓ. First, when ℓ= 1, there are two cases for the edge from i1 to 0: if pσ(i1) = bi1, then

p σ(i1) bi1 pσ(i1) + ε;

and if vi1σ(i1) pσ(i1) = U(σ, p),

p σ(i1) vi1σ(i1) U(σ, p )

= vi1σ(i1) U(σ, p) + ε

= pσ(i1) + ε.

When ℓ> 1, the induction assumptions gives us p σ(i2) pσ(i2) + ε. Then

p σ(i1) vi1σ(i1) vi1σ(i2) + p σ(i2) vi1σ(i1) vi1σ(i2) + pσ(i2) + ε

= pσ(i1) + ε,

where the first transition holds because (σ, p ) is envy free, and the last transition holds because (i1, i2) is an edge of G. We can now conclude that

D(σ, p ) = max i N {viσ(i) p σ(i)} U(σ, p )

max i N {viσ(i) pσ(i) ε} U(σ, p) + ε

5 Extensions

In order to apply our results in practice, one would ask participants for both values and budget constraints, instead of just values. Now, there are two options. The first is to compute the budget-constrained maximin solution (Algorithm 2), and if Fb(e) is empty, simply compute the (nonbudget-constrained) maximin solution, and let users know that it is impossible to satisfy the budget constraints. The second option is to inform the choice of an envy-free allocation with the budget constraints, even when these cannot be satisfied. This suggest the following general approach. For an allocation (σ, p) for e, define its budget violation penalty as maxi N{0, pσ(i) bi}. We first find the allocations that minimize the budget violation penalty among all

envy-free allocations for e. We then maximize a given criterion of justice among these allocations. Note that selecting an element in Fb(e) that optimizes an objective function whenever Fb(e) = can be seen as an instance of this two-step approach. And it turns out that the more general approach is still implementable in polynomial time. Theorem 4. Let e (N, A, v, r), b (bi)i N, and, for s [t], where t is polynomial in n, let fs : Rn R be a linear function. Then there is a polynomial-time algorithm that outputs an allocation (σ, p) F(e) that maximizes

min s [t] fs v1σ(1) pσ(1), . . . , vnσ(n) pσ(n)

over all allocations in F(e) that minimize the budget violation penalty. We present the proof of this theorem in the full version of the paper.6 Specifically, we construct a polynomial-time algorithm that produces an allocation that minimizes the budget violation penalty among all envy-free allocations. We find that if this allocation violates the budget constraints, it necessarily maximizes any additional criteria of justice among all envy-free allocations that minimize the maximum budget violation penalty. If the allocation produced by the new algorithm satisfies the budget constraints, Algorithm 2 produces the desired outcome. Going a step further, using the ideas of Section 3 and some additional machinery, we design, in the full version of the paper, a purely combinatorial algorithm that transforms the allocation produced by the foregoing algorithm into a budget-constrained maximin solution in O(n3) time.

6 Discussion

We conclude with a discussion of a several interesting issues.

The need for computational efficiency. From a computational complexity viewpoint, all of our algorithms are practicable. One may wonder, though, why computational complexity is even an issue, given that typical rent division instances are small (the vast majority of real-world instances have up to 4 agents). The reason is that the number of instances is relatively large. Spliddit, for example, employs Amazon Web Services, so running its algorithms comes at a cost. Informally speaking, if algorithm A is, say, twice as computationally efficient as Algorithm B, then the cost of solving tens of thousands of instances using algorithm A would (ideally) be half that of Algorithm B.

An alternative approach (which does not work). In a masterpiece of mathematical exposition, Su (1999) presents an algorithm for envy-free rent division that relies on Sperner s Lemma; this Algorithm was actually implemented in 2014 by the New York Times.7 The algorithm asks participants a sequence of queries ( which room would you prefer

6Available from http://procaccia.info/research. 7https://www.nytimes.com/2014/04/29/science/todivide-the-rent-start-with-a-triangle.html

at these prices? ), until it converges to an (approximately) envy-free allocation. Even though Su s assumptions on utility are relatively weak, his approach has several shortcomings. First, preference elicitation is cumbersome, as it requires repeated interaction with users, and, moreover, that interaction may be lengthy as the rate of convergence can be exponential in the tolerance for envy. Second, the approach makes it impossible to select among envy-free allocations (or, at least, it is unknown how to do so), and, therefore, it may lead to envy-free allocations that are intuitively unfair. Even more importantly for the present paper, it seems inherently impossible to adapt Su s algorithm to the budgetconstrained case, as a participant must be able to choose a room under every rent division, including those where the prices of all rooms violate his budget constraints.

Incentives. A natural question is whether our algorithms are manipulable, that is, whether an agent can benefit by misrepresenting his preferences; the answer is yes , not only for our algorithms, but for any algorithm that produces an envy-free allocation for the utility reports (Alkan, Demange, and Gale 1991). However, as Gal et al. (2017) argue, the incentive problem may be mitigated in practice by the fact that participants are typically unaware of how the algorithm works (apart from its fairness guarantees), which makes strategic manipulation difficult. But we can say even more. Velez (2015) shows that, in the non-budget-constrained setting, each envy-free algorithm has the remarkable property that the set of envy-free allocations, for true utilities, coincides with the set of limit equilibrium outcomes (Radner 1980) of their induced complete information games. The budget-constrained setting creates more opportunities for manipulation, as now agents report their values for the rooms (as before) and, additionally, their budget constraints. However, it is possible to show that the result of Velez (2015) goes through, by extending his analysis. Therefore, when agents know each other well and strategically engage in manipulating the algorithm, we can still expect to obtain an envy-free allocation.

Acknowledgments

This work was partially supported by NSF grants IIS1350598, IIS-1714140, CCF-1525932, and CCF-1733556; by ONR grants N00014-16-1-3075 and N00014-17-1-2428; and by a Sloan Research Fellowship.

References Aleksandrov, M., and Walsh, T. 2017. Pure Nash equilibria in online fair division. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 42 48. Alkan, A.; Demange, G.; and Gale, D. 1991. Fair allocation of indivisible goods and criteria of justice. Econometrica 59(4):1023 1039. Andersson, T.; Ehlers, L.; and Svensson, L.-G. 2014. Budget-balance, fairness and minimal manipulability. Theoretical Economics 9(3):753 777.

Aragones, E. 1995. A derivation of the money Rawlsian solution. Social Choice and Welfare 12:267 276. Aziz, H.; Rauchecker, G.; Schryen, G.; and Walsh, T. 2017. Algorithms for max-min share fair allocation of indivisible chores. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 335 341. Bei, X.; Qiao, Y.; and Zhang, S. 2017. Networked fairness in cake cutting. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 3632 3638. Bliem, B.; Bredereck, R.; and Niedermeier, R. 2016. Complexity of efficient and envy-free resource allocation: Few agents, resources, or utility levels. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 102 108. Bouveret, S.; Cechl arov a, K.; Elkind, E.; Igarashi, A.; and Peters, D. 2017. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 135 141. Brˆanzei, S.; Caragiannis, I.; Kurokawa, D.; and Procaccia, A. D. 2016. An algorithmic framework for strategic fair division. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 418 424. Gal, Y.; Mash, M.; Procaccia, A. D.; and Zick, Y. 2017. Which is the fairest (rent division) of them all? Journal of the ACM. Forthcoming. Goldman, J., and Procaccia, A. D. 2014. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13(2):41 46. Herreiner, D. K., and Puppe, C. D. 2009. Envy freeness in experimental fair division problems. Theory and decision 67(1):65 100. Kurokawa, D.; Procaccia, A. D.; and Wang, J. 2016. When can the maximin share guarantee be guaranteed? In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 523 529. Menon, V., and Larson, K. 2017. Deterministic, strategyproof, and fair cake cutting. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 352 358. Radner, R. 1980. Collusive behavior in noncooperative epsilon-equilibria of oligopolies with long but finite lives. Journal Economic Theory 22(2):136 154. Su, F. E. 1999. Rental harmony: Sperner s lemma in fair division. American Mathematical Monthly 106(10):930 942. Svensson, L.-G. 1983. Large indivisibles: An analysis with respect to price equilibrium and fairness. Econometrica 51(4):939 954. Svensson, L.-G. 2009. Coalitional strategy-proofness and fairness. Economic Theory 40(2):227 245. Velez, R. A. 2015. Sincere and sophisticated players in an equal-income market. Journal Economic Theory 157(0):1114 1129. Velez, R. A. 2017. Equitable rent division. Mimeo, Department of Economics, Texas A&M University.