# when_do_envyfree_allocations_exist__8f3febb2.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

When Do Envy-Free Allocations Exist?

Pasin Manurangsi Department of EECS UC Berkeley

Warut Suksompong Department of Computer Science University of Oxford

We consider a fair division setting in which m indivisible items are to be allocated among n agents, where the agents have additive utilities and the agents utilities for individual items are independently sampled from a distribution. Previous work has shown that an envy-free allocation is likely to exist when m = Ω(n log n) but not when m = n+o(n), and left open the question of determining where the phase transition from non-existence to existence occurs. We show that, surprisingly, there is in fact no universal point of transition instead, the transition is governed by the divisibility relation between m and n. On the one hand, if m is divisible by n, an envy-free allocation exists with high probability as long as m 2n. On the other hand, if m is not almost divisible by n, an envy-free allocation is unlikely to exist even when m = Θ(n log n/ log log n).

1 Introduction Resource allocation is a fundamental task that occurs in a great number of everyday situations, from allocating school supplies to children and course slots in universities to students, to allocating machine processing time to users and kidneys to kidney transplant patients. One of the principal concerns when allocating resources to interested agents is fairness: we want all agents to feel that they receive a fair share of the resources. There is a rich and beautiful theory of fair division that goes back several decades and has been studied in mathematics, economics, and more recently in computer science (Brams and Taylor, 1996; Moulin, 2003). In order to reason about fairness, we must deﬁne when an allocation is considered to be fair . One of the most prominent fairness notions is envy-freeness, which means that every agent likes her allocated portion at least as much as that of any other agent (Foley, 1967; Varian, 1974). While an envy-free allocation can always be obtained when we allocate divisible goods such as land or machine processing time (Stromquist, 1980), this is not the case when it comes to allocating indivisible goods like jewelry and artworks. Indeed, if a single bracelet or painting is to be divided between two agents, then no matter how the division is performed, the agent who does not receive the item will be left envying the other agent.

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Given that the existence of envy-free allocations cannot be guaranteed in general for indivisible goods, an important question is therefore when such allocations exist. Dickerson et al. (2014) investigated this question under a simple model where the agents have additive utilities and their utilities for individual items are drawn at random from probability distributions. If the number of items, m, is less than the number of agents, n, no envy-free allocation exists since any allocation necessarily leaves some agent empty-handed and envious. Dickerson et al. showed that even when the number of items slightly exceeds the number of agents m = n + o(n) an envy-free allocation is still unlikely to exist. However, as soon as the number of items is larger than the number of agents by a logarithmic factor m = Ω(n log n) an envyfree allocation exists with high probability, and can furthermore be obtained by simply giving each item to the agent with the highest utility for it. Dickerson et al. also found the phase transition from non-existence to existence to be quite sharp in computer experiments, and left open the question of determining where this transition occurs. Is the logarithmic factor in the upper bound necessary, or do we already have existence when, say, m = 1.001n? In this paper, we show that, surprisingly, there is in fact no universal point of transition between non-existence and existence. Instead, the transition is governed by the divisibility relation between m and n. On the one hand, if m is divisible by n, we show that an envy-free allocation exists with high probability as long as m 2n (Theorem 3.1). Our result improves upon the aforementioned m = Ω(n log n) upper bound and moreover completely closes the gap for the case of divisibility, since Dickerson et al. s lower bound already implies that the same result does not hold when m = n.1 On the other hand, if m is not almost divisible by n, in the sense that the remainder of the division is between nϵ and n nϵ for some constant ϵ (0, 1), we show that an envy-free allocation is unlikely to exist as long as m = O(n log n/ log log n) (Theorem 4.1). This comes to within a Θ(log log n) factor of matching their upper bound. Both our existence and non-existence results rely on several new key ideas. In particular, for the existence result we need a com-

1We do note, however, that Dickerson et al. s upper bound holds under a weaker assumption on the distributions. For example, it does not assume that the utilities are drawn from the same distribution for all agents and items.

pletely different algorithm, since the welfare-maximizing algorithm used to achieve existence for m = Ω(n log n) cannot yield any improvement of this bound (Proposition 3.2).

1.1 Related Work

Besides the work of Dickerson et al. (2014) that we mentioned, several other works have investigated the asymptotic existence and non-existence of fair allocations for various fairness notions. Suksompong (2016) considered proportional allocations allocations in which every agent receives at least 1/n of her value for the whole set of items and showed that such allocations exist with high probability if m is a multiple of n or m = ω(n). Kurokawa, Procaccia, and Wang (2016) showed that an allocation that satisﬁes the maximin share criterion is likely to exist as long as either m or n goes to inﬁnity.2 As in our work, both Kurokawa, Procaccia, and Wang (2016) and Suksompong (2016) used techniques from the theory of matchings in random graphs to establish the existence of fair allocations. Amanatidis et al. (2017) also addressed the existence of allocations satisfying the maximin share criterion. Finally, Manurangsi and Suksompong (2017) considered the setting where goods are allocated to groups of agents and generalized Dickerson et al. (2014) s results on envy-freeness to that setting. Since envy-free allocations cannot always be obtained even in the simplest setting with two agents and one item, a recent line of work has focused on relaxations of envyfreeness with the goal of recovering the guaranteed existence. These relaxations include envy-freeness up to one good any envy that an agent has towards another agent can be eliminated by removing some item from the latter agent s bundle and envy-freeness up to any good any such envy can be eliminated by removing any item from the latter agent s bundle. It has been shown that these relaxations do provide existence guarantees in a number of settings (Lipton et al., 2004; Caragiannis et al., 2016; Conitzer, Freeman, and Shah, 2017; Amanatidis, Birmpas, and Markakis, 2018; Barman, Krisnamurthy, and Vaish, 2018; Biswas and Barman, 2018; Plaut and Roughgarden, 2018).

2 Preliminaries

A set M = [m] of indivisible items is to be allocated to a set N = [n] of agents, where we use [k] to denote the set {1, 2, . . . , k}. Each agent i has a nonnegative utility ui(j) for item j. We assume that the utility ui(j) lies in [0, 1]; this does not introduce a loss of generality since we can scale down all utilities by their maximum. The utilities of the agents are additive, i.e., ui(M ) = P

j M ui(j) for any M M. The additivity assumption is made in several works on fair division and, in particular, in all of the works on the asymptotic existence of fair allocations mentioned in Section 1.1. A bundle refers to a subset of M. An allocation is a partition of M into n bundles (M1, M2, . . . , Mn), where bundle

2We refer to their paper for the deﬁnition, but remark here that both proportionality and the maximin share criterion are weaker than envy-freeness when utilities are additive.

Mi is allocated to agent i. An allocation is said to be envyfree for agent i if ui(Mi) ui(Mj) for any j N, and envy-free if it is envy-free for every agent i N. For agents i N and items j M, the utilities ui(j) are drawn independently from a distribution U. A distribution is said to be non-atomic if it does not put positive probability on any single point. The condition that we will impose on U for our results is that it behaves like a polynomial close to 1 in the sense that the function g(α) = Pru U[u 1 α] is bounded above and below by a polynomial. This is formalized in the following deﬁnition.

Deﬁnition 2.1. Let θ, q be any positive real numbers. A probability distribution U on [0, 1] is said to be (θ, q)- polynomially bounded below (resp. above) at 1 if for every α (0, 1], we have Pru U[u > 1 α] θ αq (resp. Pru U[u > 1 α] θ αq). A probability distribution U is said to be polynomially bounded at 1 if there exist constants θ, θ, q > 0 such that U is (θ, q)-polynomially bounded below at 1 and (θ, q)- polynomially bounded above at 1.

We assume in Section 3 that U is polynomially bounded at 1 and in Section 4 that U is polynomially bounded below at 1. To illustrate the generality of this deﬁnition, consider any non-atomic continuous distribution U whose probability density function f U is bounded below (resp. above) around 1, i.e., there exist ϵ, β > 0 such that f U(x) β (resp. f U(x) β) for all x 1 ϵ. One can check that U is polynomially bounded below (resp. above) at 1 with parameters θ = ϵ β (resp. θ = max{β, 1/ϵ}) and q = 1. This immediately implies that the uniform distribution on [0, 1] and a normal distribution (with any mean and variance) truncated at 0 and 1 are polynomially bounded at 1, as both have probability density functions that are bounded both above and below in [0, 1]. For completeness, let us also provide examples of distributions that are not polynomially bounded at 1. The ﬁrst example is when Pru U[u = 1] > 0. In this case, clearly the distribution is not polynomially bounded above at 1. Another example is if we take any U such that Pru U[u 1 1/2i] = 1/2i2 for all integer i 0. It is not hard to see that this distribution is not polynomially bounded below at 1.

Indeed, for any ﬁxed q > 0, we have limi (1/2i2) (1/2i)q = 0, which means that there is no θ > 0 such that Pru U[u 1 α] θ αq for all α (0, 1]. Finally, a statement is said to hold with high probability if the probability that it holds approaches 1 as n .

3 Existence

In this section, we investigate the existence front of envyfree allocations. We ﬁrst show that the welfare-maximizing algorithm of Dickerson et al. (2014) cannot yield any improvement of the m = Ω(n log n) bound. We then prove the main existence result of this paper, which holds for any m 2n that is a multiple of n:

Theorem 3.1. Let r 2 be an integer, and suppose that m = rn. Assume that U is polynomially bounded at 1. With

high probability, there exists an envy-free allocation. Moreover, there is a polynomial-time algorithm that computes such an allocation.

A bonus of our algorithm is that it returns a balanced allocation, i.e., one that gives every agent the same number of items. This may be desirable in situations where capacity constraints are involved, for example if we divide artworks between museums or players between sports teams.

3.1 The Limit of the Welfare-Maximizing Algorithm Recall the main existence result of Dickerson et al. (2014): when m = Ω(n log n), the welfare-maximizing algorithm, which allocates each item to the agent who values it most, is likely to produce an envy-free allocation. We observe that this bound is tight up to a constant factor for m = n log n ω(n) items, the welfare-maximizing allocation is unlikely to be envy-free. An implication of this observation is that the welfare-maximizing algorithm fails to be envyfree in the case where m = rn, for any positive integer r log n ω(1). By contrast, the algorithm that we will present ﬁnds an envy-free allocation with high probability for any integer r 2.

Proposition 3.2. Let m = n log n ω(n), and suppose that U is non-atomic. Then, with high probability, the welfaremaximizing allocation is not envy-free.

Proof. The proposition follows from a classical result on the coupon collector s problem. In this problem, there is an urn of n coupons. Each turn, a coupon is drawn uniformly at random from the urn and immediately returned to the urn. Erd os and R enyi (1961) proved that with high probability, after n log n ω(n) turns, some coupon has not been drawn. The connection between the coupon collector s problem and our setting is fairly simple. First, the non-atomic assumption on the distribution implies that, almost surely, all items yield positive utility to every agent, and every item has only one agent who values it most. As a result, the welfaremaximizing allocation assigns each item to each agent with probability 1/n. If we view each agent as a coupon in the coupon collector s problem, Erd os and R enyi s result implies that with high probability, some agent does not receive any item in this allocation. From the positive utility observation, the allocation cannot be envy-free.

3.2 Warm-Up: A Simpliﬁed Algorithm for r 3 The remainder of Section 3 is devoted to proving Theorem 3.1; we assume throughout that m = rn for some integer r 2. As Dickerson et al. (2014) already showed that the theorem holds for r = Ω(log n), it sufﬁces for us to establish the statement for r = O(log n). Nevertheless, we will prove the statement for r en0.1, which is much stronger; while this is not necessary, we do so to demonstrate that our algorithm and its analysis are robust and apply even when the number of items is signiﬁcantly larger than the number of agents. Before we proceed to the actual algorithm, let us provide the intuition behind the algorithm by describing a simpler

algorithm that works in all cases except when r = 2. For the sake of exposition, we shall restrict ourselves to the case where the distribution U is the uniform distribution on [0, 1] and r > 2 is a constant (i.e., does not grow with n). We shall also sometimes be informal here; all proofs will be formalized in the rest of Section 3. The simpliﬁed algorithm tries to ﬁnd an allocation that satisﬁes the following two properties: (i) each agent receives exactly r items, and (ii) each agent has utility at least τ := 1 2 log n/n for every item that she receives. If at least one such allocation exists, the algorithm outputs any of them. Else, it outputs NULL. Note that determining whether such an allocation exists and ﬁnding one if it exists can be done in polynomial time by reducing to matching: we create a bipartite graph (N [r], M, E), where ((i, ℓ), j) E if and only if ui(j) τ. A desired allocation corresponds to a perfect matching in this graph.3

For the sake of convenience, we introduce the notion of rmatching, which allows us to focus on the graph with vertex set N instead of N [r]. In an r-matching, each left vertex can be matched to as many as r right vertices, whereas each right vertex is still allowed to be matched to at most one left vertex.

Deﬁnition 3.3. An r-matching of a bipartite graph G is a subgraph of G such that every left vertex has degree at most r and every right vertex has degree at most 1. An r-matching is said to be perfect if every left vertex has degree exactly r and every right vertex has degree exactly 1.

As with normal matchings, a perfect r-matching can be computed in polynomial time by creating r copies of each left vertex and ﬁnding a perfect matching. With this deﬁnition, our simpliﬁed algorithm can be described as follows.

Algorithm 1 Simpliﬁed Algorithm for r 3

1: procedure THRESHOLDMATCHINGτ(N, M, {ui}i [n]) 2: for i = 1, 2, . . . , n do 3: M τ(i) {j M | ui(j) τ}

4: Let G τ = (N, M, E τ) denote the graph where (i, j) E τ iff j M τ(i). 5: if G τ contains a perfect r-matching then 6: return any perfect r-matching of G τ 7: else 8: return NULL

We now sketch the proof of correctness of Algorithm 1, which consists of two parts. Firstly, we argue that with high probability, the algorithm returns a perfect r-matching in G τ (i.e., does not output NULL). Secondly, we show that the output allocation is envy-free with high probability.

Existence of a perfect r-matching in G τ. For the ﬁrst part, we evoke a classical result regarding the existence of a perfect matching in bipartite random graphs. Recall that

3We write (U, V, E) to denote a bipartite graph with the set of vertices U and V in the partition, which we refer to as the set of left vertices and right vertices respectively, and the set of edges E.

for any positive integers a, b and any p [0, 1], a bipartite graph sampled from the Erd os-R enyi random bipartite graph distribution G(a, b, p) consists of left and right vertex sets A and B of size a and b respectively, and for any pair of vertices a A and b B, the edge (a, b) occurs with probability p independently of other pairs of vertices. Proposition 3.4 (Erd os and R enyi (1964)). Let G be a bipartite graph sampled from the Erd os-R enyi random bipartite graph distribution G(n, n, p), where p = (log n + ω(1))/n. Then, with high probability, G contains a perfect matching. To show that a perfect r-matching is likely to exist in G τ, we arbitrarily partition the item set M into r parts M (1), . . . , M (r), each of size n. We also create a bipartite graph H(a) for a = 1, 2, . . . , r where the left vertex set is N, the right vertex set is M (a), and each (i, j) is an edge iff ui(j) τ. Now, since τ = 1 2 log n/n, for each a the graph H(a) is distributed according to the Erd os-R enyi random bipartite graph distribution G(n, n, 2 log n/n). As a result, Proposition 3.4 implies that H(a) contains a perfect matching with high probability. By taking the union of the perfect matchings in H(1), . . . , H(r), we conclude that G τ contains a perfect r-matching with high probability. This completes the ﬁrst part of the proof sketch.

Envy-freeness of output allocation. Next, we argue that with high probability, any allocation output by Algorithm 1 is envy-free. Consider any such allocation. Since every agent receives r items, each of which yields utility at least τ to her, her total utility is at least r τ = r 2r log n/n. It therefore sufﬁces to show that with high probability, for every i = i, the utility of agent i for agent i s bundle Mi is at most r 2r log n/n. We will show that with high probability, for every i = i, agent i values at most r 1 items in Mi more than 1 2r log n/n. This is sufﬁcient because these r 1 items can each contribute utility at most 1 to agent i , whereas the remaining item contributes utility at most 1 2r log n/n to her. It follows that the utility of agent i for Mi does not exceed (r 1)+(1 2r log n/n) = r 2r log n/n. Fix two distinct i, i [n]. Let Ei,i denote the bad event that there exist r items j1, . . . , jr for which ui(jk) τ and ui (jk) 1 2r log n/n for k = 1, 2, . . . , r. Consider any item j M. Since we assume that ui(j) and ui (j) are drawn independently from the uniform distribution on [0, 1], the probability that item j satisﬁes the two inequalities above for i and i is at most 2 log n

n = 4r log2 n

n2 . Using the union bound over all subsets of r items, we have

Pr[Ei,i ] m r

r = o(n 2),

where we use the inequality m r mr and the assumption that r 3 is constant. Applying the union bound again over all i, i , the probability that at least one bad event occurs is o(1). This concludes our proof sketch for the simpliﬁed algorithm.

3.3 The Algorithm

Having described the simpliﬁed algorithm, we now proceed to the actual algorithm. Before we do so, let us note that Algorithm 1 does not work for r = 2. This is because when r = 2, there is a constant probability that some pair of agents have the same two most valued items. In this case, Algorithm 1 could output an allocation that assigns both items to one of the two agents, which would mean that this agent is envied by the other agent. To make Algorithm 1 work for r = 2, recall that the algorithm could fail if it is possible to ﬁnd r items in the candidate item set of agent i (i.e., the set of items for which agent i has utility at least τ) that another agent i values more than r τ in total. The modiﬁcation to the algorithm is simple: remove any such problematic items from the candidate set of i before we try to ﬁnd a perfect r-matching in the graph. There are multiple ways to implement this removal step. The way we use, which we feel is quite natural, is to continue removing from the candidate set of agent i an item which agent i values the most, until the r items in the candidate set of i that are most highly valued by i are not valued more than r τ in total. The pseudo-code of the algorithm is presented below as Algorithm 2; here we use sum-topr(S) to denote the sum of the r largest elements of S for any multiset of real numbers S (or the sum of all elements if S contains less than r elements). The set in line 5 of the algorithm is considered as a multiset. The appropriate value of τ depends on the distribution U and will be speciﬁed later.

Algorithm 2 Algorithm for any r 2

1: procedure THRESHOLDMATCHINGWITHREMOVALτ (N, M, {ui}i [n]) 2: for i = 1, 2, . . . , n do 3: M τ(i) {j M | ui(j) τ} 4: for i [n] \ {i} do 5: while sum-topr {ui (j) | j M τ(i)} > r τ do 6: M τ(i) M τ(i) \ arg maxj M τ (i) ui (j)

7: Let G τ = (N, M, E τ) denote the graph where (i, j) E τ iff j M τ(i). 8: if G τ contains a perfect r-matching then 9: return any perfect r-matching of G τ 10: else 11: return NULL

The above modiﬁcation ensures that if Algorithm 2 returns an allocation, it must be envy-free. Indeed, each agent i has utility at least τ for every item assigned to her in the r-matching, so her total utility is at least r τ. On the other hand, by construction of the graph G τ, each agent i values the r items assigned to agent i at most r τ. Thus, the output allocation must be envy-free. In order to establish Theorem 3.1, it therefore remains to show that with an appropriate choice of τ, a perfect rmatching in G τ exists with high probability. Recall our assumption that the distribution U from which the utilities are drawn is polynomially bounded at 1. Let θ, θ, q > 0 be

the associated parameters. It sufﬁces to prove the following lemma:

Lemma 3.5. Set τ := 1 64 log m

θn 1/q in Algorithm 2, and

let 2 r en0.1. Then, with high probability, the graph G τ contains a perfect r-matching.

Note that the condition r en0.1 implies that τ > 0 for large enough n. The proof of Lemma 3.5 consists of two parts. First, in Section 3.4, we show that only few edges are removed in line 6 of Algorithm 2; in particular, we show that with high probability, at most two edges adjacent to any particular vertex are removed. Then, in Section 3.5, we show that the existence of a perfect r-matching is locally resilient (see, e.g., (Sudakov and Vu, 2008)) in the following sense: even if we remove a low-degree subgraph from a random graph sampled from the Erd os-R enyi random bipartite graph distribution with sufﬁciently large probability, then the remaining graph still contains a perfect r-matching with high probability. Putting these two parts together yields Lemma 3.5; this is done in Section 3.6. Before we proceed to proving Lemma 3.5, we perform some preliminary calculations. Picking α = 1 τ in Deﬁnition 2.1, we have Pru U[u > τ] 64 log m

n . On the other hand, writing τ := 3τ 2 and letting α = 1 τ in Deﬁnition 2.1 yields Pru U[u > τ ] θ(3(1 τ))q = C log m

n for the constant C := 3q 64θ

3.4 Bounding the Number of Edges Removed Let E τ and E τ denote the set of edges as deﬁned in Algorithm 1 and 2, respectively. The main result of this subsection is the following lemma: Lemma 3.6. With high probability, the graph (N, M, E τ \ E τ) has maximum degree at most 2. In addition to the graphs G τ and G τ (as deﬁned in Algorithm 1 and 2 respectively), we consider the graph G>τ = (N, M, E>τ ) which can be deﬁned analogously. That is, the neighbor set of i N in G>τ is M>τ (i) := {j M | ui(j) > τ }. The next proposition states that, for any edge (i, j) that is removed in line 6 of Algorithm 2, the edge (i, j) must be part of a complete bipartite subgraph K2, 2r/3 +1 of the graph G>τ .4 We note that this is similar to the argument for the simpliﬁed algorithm in Section 3.2, which, in the new language, states that any edge (i, j) that would be removed in line 6 of Algorithm 2 must be part of a complete bipartite subgraph K2,r of the graph G>τ , where the threshold τ there is chosen (differently) to be 1 2r log n/n. Proposition 3.7. If (i, j) E τ \ E τ, then there exists i

such that |M>τ (i) M>τ (i )| > 2r/3 and j M>τ (i) M>τ (i ).

Proof. First, let us argue that j M>τ (i) M>τ (i ). The assumption that (i, j) E τ immediately implies

4The notation Ka,b refers to a complete bipartite graph with left and right vertex sets of size a and b, respectively.

that j M>τ (i) since τ = 3τ 2 < τ. Let i N be the vertex in line 5 of Algorithm 2 that causes the removal of the edge (i, j). At this line, we have sum-topr {ui (j ) | j M τ(i)} > r τ and j arg maxj M τ (i) ui (j ). Hence, ui (j) (r τ)/r = τ > τ , and therefore j M>τ (i ). We have thus shown that j M>τ (i) M>τ (i ). Next, let y = min{r, |M>τ (i) M>τ (i )|}. The condition sum-topr {ui (j ) | j M τ(i)} > r τ at the time when the edge (i, j) is removed implies that

r τ < sum-topr {ui (j ) | j M τ(i)}

sum-topr ({ui (j ) | j M>τ (i)})

y 1 + (r y) τ

= y + (r y)(3τ 2) = (3 3τ)y + (3τ 2)r,

which implies that y > 2r/3, as claimed.

We now use Proposition 3.7 to prove Lemma 3.6. We consider two cases: r 3 and r = 2.

The Case r 3. The proof for the case r 3 is similar to that of the simpliﬁed algorithm (Section 3.2). In particular, we show that with high probability, no edge is removed in Algorithm 2. This also means that Algorithms 1 and 2 are equivalent with high probability.

Proposition 3.8. Let 3 r en0.1. Then, with high probability, E τ = E τ.

Proof. For convenience, let p>τ := Pru U[u > τ ]. Note that p>τ C log m

n C0/n0.9 for C0 := 2C, where the last inequality holds for sufﬁciently large n. We will argue that with high probability, there are no distinct i, i N such that |M>τ (i) M>τ (i )| > 2r/3. Together with Proposition 3.7, this implies that no edge is removed and therefore E τ = E τ. To show this, we use the standard ﬁrst moment method. Fix distinct i, i N and a subset S M of size x := 2r/3 + 1. The probability that S M>τ (i) M>τ (i ) is exactly (p>τ )2x. Hence, by taking the union bound over all choices of i, i and S, the probability that |M>τ (i) M>τ (i )| > 2r/3 for some i, i is at most

(p>τ )2x n2 em

(since x 3) (n(p>τ )1.2)2 em(p>τ )1.2

(since x > 2r/3) < (n(p>τ )1.2)2 1.5en(p>τ )1.2 x

(since p>τ C0

n0.9 ) (C1.2 0 n 0.08)2(1.5e C1.2 0 n 0.08)x

which concludes the proof.

The Case r = 2. As argued earlier, in the case r = 2, some edges must be removed in order to guarantee that the output allocation is envy-free. The following proposition ensures that with high probability, for any vertex, at most two edges adjacent to it are removed in Algorithm 2.

Proposition 3.9. Let r = 2. Then, with high probability, the graph (N, M, E τ \ E τ) has maximum degree at most 2.

Proof. Observe that, for r = 2, Proposition 3.7 can be restated as follows: if (i, j) E τ \ E τ, then there exist i N and j M such that i, i , j, j form a complete bipartite graph K2,2 in the graph G>τ . Now, suppose that some vertex u N M appears in at least three edges in E τ \ E τ. The previous paragraph implies each such edge must be contained in a copy of K2,2 in the graph G>τ . Since the three edges from u are distinct, not all three of these copies can be identical. As a result, u must be contained in two different copies of K2,2, which means that at least one of the graphs shown in Figure 1 must appear as a subgraph of G>τ . Notice that by the union bound, for any graph H = (VH, EH), the probability that it appears as a subgraph of G>τ is at most

(n + m)|VH|(p>τ )|EH| (3n)|VH| C log m

n |EH| . How-

ever, all graphs H in Figure 1 satisfy |EH| |VH| + 1. Hence, the probability that each of them appears as a subgraph is at most (C log n)O(1)

n = o(1). Using the union bound, the probability that at least one of these graphs appears as a subgraph of G>τ is also o(1). This implies that the probability that at least one of the vertices is adjacent to more than two edges in E τ \ E τ is o(1), as desired.

Finally, we note that Propositions 3.8 and 3.9 together imply Lemma 3.6.

3.5 Local Resilience of Perfect r-Matching In this subsection, we show that in a random bipartite graph sampled from the Erd os-R enyi random bipartite graph distribution G(n, rn, p) with sufﬁciently large p, not only does a perfect r-matching exist, but the existence is also robust in the following sense: even if we remove edges from the graph, as long as not too many edges adjacent to each vertex are removed, a perfect r-matching still exists. Such robustness is known in the literature as local resilience. In particular, the local resilience of perfect matchings was shown by Sudakov and Vu (2008). We will extend their proof to the case of perfect r-matchings. However, we note that our bound will be slightly weaker than theirs, since our main goal is to derive a bound that is sufﬁcient for the algorithm to work and not to ﬁnd the best possible parameters. A typical method for establishing the existence of a perfect matching, which was used both by Sudakov and Vu (2008) and by Erd os and R enyi (1964), is to show that the graph satisﬁes the condition of Hall s Marriage Theorem. For any graph G and any set S of vertices in G, denote by NG(S) the set of vertices adjacent to at least one vertex in S.

Proposition 3.10 (Hall s Marriage Theorem). Let G = (A, B, E) be any bipartite graph such that |A| = |B|. If

|NG(S)| |S| for all subsets S A, then G has a perfect matching.

Recall that G = (A, B, E) has a perfect r-matching if and only if the graph (A [r], B, E ), where ((a, ℓ), b) E iff (a, b) E, has a perfect matching. Hence, Hall s Marriage Theorem immediately extends to r-matchings:

Proposition 3.11. Let G = (A, B, E) be any bipartite graph such that |B| = r|A|. If |NG(S)| r|S| for all subsets S A, then G has a perfect r-matching.

One way to show that the condition of Hall s Marriage Theorem is satisﬁed is to show that there is at least one edge between any sets S A and T B of appropriate sizes. To ensure that the existence of a perfect r-matching is locally resilient, we need to show not only that one edge exists, but also that many edges exist. This can be done via standard concentration bounds. For any graph G and any sets S, T of vertices in G, denote by EG(S, T) the set of edges connecting a vertex in S to a vertex in T.

Lemma 3.12. Let G = (A, B, E) be a graph sampled from the Erd os-R enyi random bipartite graph distribution G(n, m, p) with p 64 log m

n . Then, with high probability, the following holds for all subsets S A and T B such that |T| = m r|S| + 1:

|EG(S, T)| > (16 log m) min{|S|, |T|}. (1)

The proof of Lemma 3.12 can be found in the full version of this paper (Manurangsi and Suksompong, 2018). With Lemma 3.12 ready, we now establish the local resilience of the existence of perfect r-matchings in random graphs.

Lemma 3.13. Let G = (A, B, E) be a graph sampled from the Erd os-R enyi random bipartite graph distribution G(n, m, p) with p 64 log m

n . Then, with high probability, for any subgraph H = (A, B, E ) of G with maximum degree at most 16 log m, the graph G H = (A, B, E \ E ) contains a perfect r-matching.

Proof. From Lemma 3.12, with high probability, (1) holds for all S A, T B with |T| = m r|S| + 1. We claim that this implies that G H = (A, B, E \ E ) contains a perfect r-matching. Suppose for the sake of contradiction that G H does not contain an r-perfect matching. Proposition 3.11 implies that there exists a set S A such that |NG H(S)| r|S| 1. Let T be any subset of B\NG H(S) of size m r|S|+1. Since T NG H(S) = , we have EG H(S, T) = . However, by (1), |EG(S, T)| > (16 log m) min{|S|, |T|}. This means that at least one vertex in S T has degree more than 16 log m in H, which is a contradiction.

3.6 Putting Things Together With Lemmas 3.6 and 3.13 in hand, we can (ﬁnally) prove Lemma 3.5.

Proof of Lemma 3.5. First, Lemma 3.6 ensures that with high probability, for each vertex, at most two edges adjacent to it are removed from G τ in Algorithm 2, where G τ is

Figure 1: All possible unions of two distinct complete bipartite graphs K2,2 which share at least one vertex u, up to isomorphism. The shaded vertices constitute one copy of K2,2 whereas the thickened vertices constitute another.

deﬁned as in Algorithm 1. Recall also that G τ is distributed according to the Erd os-R enyi random bipartite graph distribution G(n, m, p) with p = Pru U[u τ] 64 log m

n . It therefore follows from Lemma 3.13 that a perfect rmatching exists in G τ with high probability.

4 Non-Existence Our main non-existence result states that envy-free allocations are unlikely to exist if m = O(n log n/ log log n) is not close to being a multiple of n. This improves upon the m = n + o(n) lower bound of Dickerson et al. (2014) and comes to within a Θ(log log n) factor of matching their upper bound.

Theorem 4.1. For any real numbers θ > 0, ϵ (0, 1), and q 1, there exists c > 0 depending only on θ, ϵ, q such that the following holds: For any positive integer r c log n log log n, if m [rn + nϵ, (r + 1)n nϵ] and U is (θ, q)-polynomially bounded below at 1, then, with high probability, there is no envy-free allocation.

We remark that since we only require the distribution to be polynomially bounded below, the assumption q 1 does not introduce a loss of generality. Next, we give an overview of the proof of Theorem 4.1; the full proof can be found in the full version of this paper (Manurangsi and Suksompong, 2018). The proof is based on the ﬁrst moment method; the key is to show that for any ﬁxed allocation, the probability (over the random utilities drawn) that it is envy-free is 1/nm. Since there are nm possible allocations, the union bound implies that with high probability, no envy-free allocation exists. To give an intuition for this bound, let us consider a simpliﬁed setting where m = (r + 0.5)n and the distribution U is uniform on [0, 1]. Intuitively, the more balanced the allocation is, the harder it is to bound the probability that the allocation is envy-free. Following this intuition, let us consider the most balanced allocation where 0.5n agents receive r+1 items and the remaining agents receive r items. The key observation is that, for the allocation to be envy-free for every agent in the latter group, any such agent must have utility at most r for the r+1 items in the bundle of any agent in the ﬁrst group. For a ﬁxed agent in the second group and a ﬁxed agent in the ﬁrst group, this happens with probability

at most 1 1/(r + 1)r+1. Indeed, if each of the r + 1 items yields utility at least r/(r + 1) to the agent, the requirement is not satisﬁed. Now, since there are 0.25n2 such pairs of agents, the probability that this ﬁxed allocation is envy-free

is at most 1 1 (r+1)r+1 0.25n2 = exp Θ n2 (r+1)r+1 .

Hence, as long as r log n/ log log n, this term is at most, say, exp( n1.9), which is indeed much smaller than n m. The full proof proceeds along the lines of the argument above, but we need to be more careful as we must also deal with other less balanced allocations.

5 Discussion

In this paper, we study the existence and non-existence of envy-free allocations and essentially close the gap left open by Dickerson et al. (2014) with regard to the transition between the two phases. On the positive side, we show that if the number of items is a multiple of the number of agents, an envy-free allocation is likely to exist as long as the former quantity is at least twice the latter. On the negative side, we show that if the number of items is not close to being a multiple of the number of agents, an envy-free allocation is unlikely to exist even when the former quantity exceeds the latter by almost a logarithmic factor. Both of our results make use of several new ideas that may be useful for other problems in fair division. As we mentioned earlier, all of the works on the asymptotic existence of fair allocations thus far have assumed that agents are endowed with additive utilities. While additivity provides a reasonable trade-off between simplicity and expressiveness, it would be interesting to establish analogous results that hold for more general classes of utilities. Going beyond additivity introduces several complications; for example, the welfare-maximizing allocation is no longer simply the one that assigns every item to the agent who values it most, and giving an agent several goods that she values highly does not guarantee that the agent will also have a correspondingly high value for the whole bundle. Nevertheless, a starting point may be to prove results for speciﬁc distributions over utilities from a well-structured class such as that of submodular valuations. Another possible avenue for future work is to consider the setting where instead of allocating items to individual agents, we divide them among groups of agents (Segal-

Halevi and Nitzan, 2016; Segal-Halevi and Suksompong, 2018; Suksompong, 2018a,b). The agents in each group share the same set of items but may have different preferences. This is the case, for example, when dividing household goods among families or resources between departments in a university. Manurangsi and Suksompong (2017) generalized the results of Dickerson et al. (2014) to the group setting and left a logarithmic gap between existence and non-existence. We are hopeful that the techniques we introduce in the present work will help towards closing this gap as well.

Acknowledgments This work was partially supported by NSF Awards CCF1655215, CCF-1813188, CCF-1815434, and by a Stanford Graduate Fellowship. We would like to thank the anonymous reviewers for their helpful comments.

References Amanatidis, G.; Markakis, E.; Nikzad, A.; and Saberi, A. 2017. Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms 13(4):52. Amanatidis, G.; Birmpas, G.; and Markakis, E. 2018. Comparing approximate relaxations of envy-freeness. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence, 42 48. Barman, S.; Krisnamurthy, S. K.; and Vaish, R. 2018. Finding fair and efﬁcient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation, 557 574. Biswas, A., and Barman, S. 2018. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence, 91 97. Brams, S. J., and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation, 305 322. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation, 629 646. Dickerson, J. P.; Goldman, J.; Karp, J.; Procaccia, A. D.; and Sandholm, T. 2014. The computational rise and fall of fairness. In Proceedings of the 28th AAAI Conference on Artiﬁcial Intelligence, 1405 1411. Erd os, P., and R enyi, A. 1961. On a classical problem of probability theory. Magyar Tudom anyos Akad emia Matematikai Kutat o Int ezet enek K ozlem enyei 6:215 220. Erd os, P., and R enyi, A. 1964. On random matrices. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 8:455 461. Foley, D. K. 1967. Resource allocation and the public sector. Yale Economics Essays 7(1):45 98.

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 Artiﬁcial Intelligence, 523 529.

Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, 125 131.

Manurangsi, P., and Suksompong, W. 2017. Asymptotic existence of fair divisions for groups. Mathematical Social Sciences 89:100 108.

Manurangsi, P., and Suksompong, W. 2018. When do envyfree allocations exist? Co RR abs/1811.01630.

Moulin, H. 2003. Fair Division and Collective Welfare. MIT Press. Plaut, B., and Roughgarden, T. 2018. Almost envy-freeness with general valuations. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, 2584 2603.

Segal-Halevi, E., and Nitzan, S. 2016. Envy-free cakecutting among families. Co RR abs/1607.01517.

Segal-Halevi, E., and Suksompong, W. 2018. Democratic fair allocation of indivisible goods. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence, 482 488.

Stromquist, W. 1980. How to cut a cake fairly. The American Mathematical Monthly 87(8):640 644.

Sudakov, B., and Vu, V. H. 2008. Local resilience of graphs. Random Structures and Algorithms 33(4):409 433.

Suksompong, W. 2016. Asymptotic existence of proportionally fair allocations. Mathematical Social Sciences 81:62 65.

Suksompong, W. 2018a. Approximate maximin shares for groups of agents. Mathematical Social Sciences 92:40 47.

Suksompong, W. 2018b. Resource Allocation and Decision Making for Groups. Ph.D. Dissertation, Stanford University.

Varian, H. R. 1974. Equity, envy, and efﬁciency. Journal of Economic Theory 9:63 91.