--- title: "Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory" authors: - "Pasin Manurangsi" - "Warut Suksompong" doi: "10.24963/ijcai.2021/47" url: "https://ijcai.org/proceedings/2021/47" pdf: "https://ijcai.org/proceedings/2021/0047.pdf" venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence" year: 2021 pages: "335-341" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Resource Allocation" - "Agent-based and Multi-agent Systems: Computational Social Choice" --- # Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory Pasin Manurangsi, Warut Suksompong *Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 335-341. DOI: [10.24963/ijcai.2021/47](https://doi.org/10.24963/ijcai.2021/47) ## Abstract We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the $n$ agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to $\Theta(\sqrt{n})$ goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to $o(\sqrt{n})$ goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory. ## Full text ## 1 Introduction Resource allocation problems arise in numerous facets of modern society, from allotting supplies to neighborhoods in a city to distributing personnel among governmental organizations. A principal consideration when allocating resources is fairness: the society is better off when all parties involved feel that they receive a fair share of the resource. It therefore comes as no surprise that the study of how to allocate resources fairly-commonly referred to as fair division-has received substantial attention in economics and, as societies becomes more interconnected and applications grow in scale, in computer science [Brams and Taylor, 1996; Moulin, 2003; Thomson, 2016; Moulin, 2019] The vast majority of the fair division literature assumes that each involved party consists of a single agent. Yet, in many resource allocation scenarios, especially large-scale ones, resources are allocated to groups of agents-even though the agents in each group share the same set of goods, they may have varying preferences over different goods in the set. Indeed, some citizens of a neighborhood may benefit from new books allotted to the public library, while others would rather have additional fitness equipment in their local park. Similarly, members of an organization may have diverse opinions about the new personnel that they would like to have in their organization. These scenarios cannot be captured by the traditional fair division setting, in which each recipient of a bundle of goods is represented by a single preference. The group aspect of fair division has been addressed in a number of recent papers [Manurangsi and Suksompong, 2017; Ghodsi et al., 2018; Suksompong, 2018; Segal-Halevi and Nitzan, 2019; Segal-Halevi and Suksompong, 2019; Kyropoulou et al., 2020]. Most of these papers studied the important fairness notion of envy-freeness: an agent is said to be envy-free if she values the goods allocated to her group at least as much as those allocated to any other group. When goods are discrete-books, personnel, fitness equipment, and many other common supplies fall into this category-envyfreeness cannot always be satisfied even when allocating the goods among individual agents; indeed, this can be easily seen when there is a single valuable good and at least two agents. This observation has motivated relaxing the envyfreeness criterion to envy-freeness up to c goods (EFc), which means that any agent's envy toward another group can be eliminated by removing at most c goods from that group's bundle, where c ≥ 1 is an integer parameter. When allocating goods among individual agents, an EF1 allocation can be found regardless of the number of agents [Lipton et al., 2004]. However, the picture for group allocation is much less clear, even in the simplest case of two groups. Segal-Halevi and Suksompong [2019] showed that if the two groups contain n agents in total and the agents have additive valuations, then an EFn allocation is guaranteed to exist. Their result follows by applying a classic theorem on consensus halving, i.e., a partition of a set of divisible goods into two parts such that every agent values both parts equally. Since there is always a consensus halving in which at most n goods are divided [Alon, 1987; Simmons and Su, 2003], rounding such a consensus halving yields an EFn allocation. 1 On the other hand, Kyropoulou et al. [2020, Prop. 3.5] gave a simple example showing that it is impossible to ensure EFc for c ∈ o(logn), thereby leaving an exponential gap in this fundamental question. Can we always achieve an impressive fairness guarantee of mere logarithmic envy, or does the envy scale linearly with the number of agents in the worst case? 1 In fact, Segal-Halevi and Suksompong [2019] gave a slightly better guarantee of EF(n-1). This guarantee was obtained by finding a consensus halving for n - 1 of the agents, and letting the remaining agent choose the part that she prefers. ## 1.1 Our Results In this paper, we give a precise answer to the above question, and much more. We consider a general setting with n = n1 + · · · +nk agents distributed into k ≥ 2 groups consisting of n1, . . . , nk ≥ 1 agents, respectively. As is common in fair division, we assume that the agents have additive utilities over the goods. Besides EFc, we investigate relaxations of two other important fairness notions: proportionality-every agent believes that the share allocated to her group is worth at least 1/k of the entire set of goods-and consensus 1/kdivision-each agent finds all k bundles to be of equal value. 2 The precise definitions can be found in Section 2.1. For each fairness notion and each n1, . . . , nk, we are interested in the smallest positive value c such that an allocation satisfying that notion up to c goods always exists for agents with arbitrary additive utilities. For envy-freeness and proportionality, we denote this value of c by cEF (n1, . . . , nk) and cPROP (n1, . . . , nk), respectively. On the other hand, for consensus 1/k-division, the partition of agents into groups is inconsequential, so we use the notation cCD k (n). Our main results provide bounds on these values: Theorem 1.1. For any k, n1, . . . , nk ∈ N, Theorem 1.2. For any k, n1, . . . , nk ∈ N, Theorem 1.3. For any n, k ∈ N, Note that since max{n1, . . . , nk} ≥ n/k, all three bounds are asymptotically tight when k is constant. In particular, Theorem 1.1 answers the question that we posed earlier: taking k = 2, we find that the optimal envy-freeness guarantee for two groups is EFc where c ∈ Θ(√n). This significantly improves upon the lower bound of Ω(log n) and upper bound of O(n) from prior work, and implies that a decent, though not outstanding, fairness guarantee can be obtained. We establish Theorem 1.3 along with the upper bounds of Theorems 1.1 and 1.2 in Section 3, and the lower bounds of Theorems 1.1 and 1.2 in Section 4. Our main tools and techniques throughout this work come from discrepancy theory, an area of mathematics that studies how much deviation from the desired state is necessary in various settings-we provide the relevant background in Section 2.2. The tools that we use imply that for each of the fairness notions, an allocation satisfying the corresponding upper bound in Theorems 1.1-1.3 can be found efficiently. In light of this, a natural question is whether we can compute an allocation improving upon these bounds if such allocations are known to exist in a given instance. In Section 5, we provide a strong negative answer to this question: for example, we show that even if a fully envy-free allocation is known to exist for a certain instance, it is still NP-hard to find an allocation that is envy-free up to o(√n) goods for that instance. 2 When k = 2, consensus 1/k-division is better known as consensus halving [Simmons and Su, 2003]. ## 1.2 Further RelatedWork While fair division has a long and storied history, several fairness notions for the indivisible goods setting, including envyfreeness relaxations, have only been proposed and studied in the past few years [Bouveret et al., 2016; Markakis, 2017]. In the group setting, Kyropoulou et al. [2020] showed that EF1 can be guaranteed for all agents only when the groups are small-for instance, with two groups, an EF1 allocation does not always exist when both groups have size at least three. Segal-Halevi and Suksompong [2019] investigated democratic fairness, where the goal is to satisfy a certain fraction of the agents in each group. They showed that for two groups with any number of agents, there exists an allocation that is EF1 for at least half of the agents in each group-this ratio is tight in the worst case, and continues to be tight even if we relax EF1 to EFc for any constant c. Besides the model that we consider, a number of papers have studied related models and notions. Ghodsi et al. [2018] addressed rent division among groups, where in addition to deciding the allocation of the rooms, the agents must determine how to split the rent of their apartment. Benabbou et al. [2019] examined a group setting where the goods allocated to each group are further divided among the members of the group, so in contrast to our setting, each agent does not derive full utility from the bundle of her group. Several authors studied individual resource allocation using fairness notions relating different groups of agents, for example notions aiming to minimize envy that arises between groups [Berliant et al., 1992; Husseinov, 2011; Todo et al., 2011; Aleksandrov and Walsh, 2018; Conitzer et al., 2019; Aziz and Rey, 2020]. Like fair division in general, consensus 1/k-division and consensus halving have been studied by mathematicians and economists for several decades [Hobby and Rice, 1965; Alon, 1987; Simmons and Su, 2003], and attracted recent interest from computer scientists in light of new computational complexity results [Filos-Ratsikas and Goldberg, 2018; Filos-Ratsikas et al., 2020; Goldberg et al., 2020; Deligkas et al., 2021]. In particular, Filos-Ratsikas and Goldberg [2018] proved that approximate consensus halving of a one-dimensional heterogeneous divisible resource is PPAcomplete-this constituted the first PPA-completeness result for a problem that is "natural" in the sense that its description does not involve a polynomial-sized circuit. ## 2 Preliminaries Let G = [m] be the set of goods, where [r] := {1, 2, . . . , r} for any positive integer r. There are n = n1 + · · · + nk agents divided into k ≥ 2 groups, where group i contains ni ≥ 1 agents. Denote by a(i,j) the jth agent in group i. The utility of a(i,j) for good ℓ is given by u(i,j) (ℓ). We assume that the agents' utilities are additive, that is, u(i,j) (G′ ) = ∑ℓ∈G′ u(i,j) (ℓ) for every G′ ⊆ G. An allocation (A1, . . . ,Ak) is an ordered partition of the goods into k bundles, where bundle Ai is allocated to group i. In particular, A1 ∪ · · · ∪ Ak = G and Ai ∩ Aj = ∅ for i ̸= j. ## 2.1 Fairness Notions We are interested in the following fairness notions: Definition 2.1. Let c be a nonnegative integer. An allocation (A1, . . . ,Ak) is said to be - envy-free up to c goods (EFc) if, for every agent a(i,j) and every i′ ̸= i, there exists a set B ⊆ Ai′ with |B| ≤ c such that u(i,j) (Ai) ≥ u(i,j) (Ai′ \ B). - proportional up to c goods (PROPc) if, for every agent a(i,j) , there exists a set B ⊆ G \ Ai with |B| ≤ c such that u(i,j) (Ai) ≥ u(i,j) (G)/k - u(i,j) (B). - a consensus 1/k-division up to c goods if, for every agent a and every pair of bundles Ai,Ai′ , there exists B ⊆ Ai′ with |B| ≤ c such that a values Ai no less than Ai′ \ B. Note that unlike the first two notions, the third notion does not depend on how the agents are distributed across groups. For each k, n1, . . . , nk, let cEF (n1, . . . , nk) (resp., cPROP (n1, . . . , nk)) denote the smallest value of c such that an EFc (resp., PROPc) allocation is guaranteed to exist for agents with additive utilities. Similarly, let cCD k (n) denote the analogous value for consensus 1/k-division up to c goods when there are n agents and k bundles. We have the following relations between these values. Proposition 2.2. For any k, n′ , n1, . . . , nk ∈ N, we have - (a) cEF (n1, . . . , nk) ≤ cCD k (n1 + · · · +nk); - (b) cPROP (n1, . . . , nk) ≤ cEF (n1, . . . , nk); - (c) cEF (n′ , . . . , n′ ) ≥ cCD k (n′ ), where there are k copies of n′ on the left-hand side. Proof. We prove the three relations in turn. - (a) This follows immediately from the observation that a consensus 1/k-division up to c goods for n1 + · · · + nk agents is also envy-free up to c goods for these agents regardless of how the agents are distributed into groups. - (b) It suffices to show that for any c, every EFc allocation is also PROPc. Let (A1, . . . ,Ak) be an EFc allocation, and consider agent a(i,j) . By definition of EFc, for each i′ ̸= i, there exists Bi′ ⊆ Ai′ with |Bi′ | ≤ c such that u(i,j) (Ai) ≥ u(i,j) (Ai′ \ Bi′ ). Let B denote the set of the c most valuable goods for a(i,j) outside of Ai, breaking ties arbitrarily. We have u(i,j) (B) ≥ u(i,j) (Bi′) for all i′ ̸= i. Letting Bi = ∅, we have Hence, the allocation is PROPc, as desired. - (c) Given n′ agents, we make a copy of each agent in each of the k groups. Any EFc allocation with respect to these groups is also a consensus 1/k-division for the original agents. The conclusion follows. ## 2.2 Discrepancy Theory In this section, we outline the tools from discrepancy theory that we will use in this work. Intuitively, a basic connection between discrepancy theory and our group fair division setting is the following: Discrepancy theory considers a setting where there is a collection of subsets (also known as a set system) and we want to color the elements of the ground set in two colors so that each subset contains roughly the same number of elements of each color. The elements of the ground set correspond to the goods in our setting, while each subset represents an agent and its elements correspond to the goods that the agent values. The goal of discrepancy theory is therefore similar to that of dividing the goods into two sets so that each agent values the two sets almost equally. In this work, we view a vector v ∈ Rk also as a column matrix v ∈ Rk×1 . We use 1k to denote the k-dimensional all-1 vector; when the dimension is clear from context, we may drop the subscript and simply write 1. Furthermore, for a set S ⊆ [k], we write 1(S) ∈ {0, 1}k to denote the indicator vector of S, i.e., (1(S))i = 1 if and only if i ∈ S. For every p ∈ [1, ∞), we use ‖v‖p to denote the ℓp norm of v, defined by (∑i∈[k] |vi|p)1/p . The ℓ∞ norm of v, denoted by ‖v‖∞, is maxi∈[k] |vi|. The Hamming norm of v, denoted by ‖v‖0, is the number of non-zero coordinates of v. ## 2-Color Discrepancy As mentioned earlier, a classic scenario in discrepancy theory is when there is a set system and the goal is to color the elements in two colors in such a way that each subset contains roughly the same number of elements of each color. As Lov´asz et al. [1986] noted, this notion generalizes naturally to any matrix. Specifically, the discrepancy of a matrix A ∈ Rn×m is defined as Here x can be thought of as a 2-coloring and the quantity ‖A(0.5 · 1 - x)‖∞ measures how "unbalanced" it is. Let A priori, discmax (n) might even be infinite since we allow A to have an arbitrary number of columns. Remarkably, however, it is known 3,4 that discmax (n) is bounded by O(√n): Lemma 2.3 ([Alon and Spencer, 2000, Corollary 12.3.4]). For any n ∈ N, discmax (n) ≤ O(√n). 3 We note here that some of the bounds we refer to are stated only for 0-1 matrices A. However, one can check that they also hold for any matrix A ∈ [0, 1]n×m. See also the full version of our paper where we sketch how the constructive versions of these bounds can be derived [Manurangsi and Suksompong, 2021]. 4 See also [Spencer, 1985] on which this bound is based. The above bound is also known to be asymptotically tight: Lemma 2.4 ([Spencer, 1985]). For any n ∈ N, it holds that discmax (n) ≥ Ω(√n). Weighted Discrepancy. The p-weighted discrepancy [Doerr and Srivastav, 2003] is a generalization of discrepancy where 0.5 is replaced by some p ∈ [0, 1]: Similarly to above, let Using standard techniques in discrepancy theory, we can prove the following lower bound on wdiscmax p (n). (This bound was also implicit in the work of Doerr and Srivastav.) Proposition 2.5. For any p ∈ (0, 1/2] and any n ∈ N such that n ≥ 16/p, we have wdiscmax p (n) ≥ Ω(√pn). The proof of Proposition 2.5, as well as all omitted proofs, can be found in the full version of our paper [Manurangsi and Suksompong, 2021]. ## Multi-Color Discrepancy We will also use the extension of the 2-color definition to multi-color cases due to Doerr and Srivastav [2003]. Recall that a k-coloring of [m] is a function χ : [m] → [k]. The k-color discrepancy of A is defined as Note that disc(A, 2) coincides with disc(A) defined earlier. Similarly to above, we let The following lemma is a consequence of Corollary 3.5 of Doerr and Srivastav [2003] and Lemma 2.3. Lemma 2.6 ([Doerr and Srivastav, 2003]). For any n, k ∈ N, discmax (n, k) ≤ O(√n). Furthermore, Doerr and Srivastav also proved the following lower bound: 5 Lemma 2.7 ([Doerr and Srivastav, 2003, Theorem 5.2]). For any n, k ∈ N such that k ≥ 2, discmax (n, k) ≥ Ω(√n/k). ## 3 Approximate Fair Division From Multi-Color Discrepancy In this section, we derive generic upper and lower bounds for the value cCD k based on the multi-color discrepancy bounds discmax (n, k). Our results are stated formally below. Theorem 3.1. For any n, k ∈ N, we have 5 Doerr and Srivastav [2003] only stated their lower bound for n such that a Hadamard matrix of order n exists. However, as explained in our proof of Proposition 2.5, this implies the same asymptotic bound for all n ∈ N. . Theorem 3.2. For any n, k ∈ N, we have By the known bounds for discmax (Lemmas 2.6 and 2.7), the two results above yield Theorem 1.3. Using the relationships between cCD k , cEF , and cPROP established in Proposition 2.2, we get the following corollary: Corollary 3.3. For any k, n′ , n1, . . . , nk ∈ N, we have - (c) cEF (n′ , . . . , n′ ) ≥ ⌈discmax (n′ , k)⌉, where there are k copies of n′ on the left-hand side. Parts (a) and (b), together with the known upper bound for discmax (Lemma 2.6), give us the upper bounds in Theorems 1.1 and 1.2. On the other hand, part (c) is not sufficient for the lower bounds in these theorems yet, since the above corollary does not apply to the "unbalanced groups" case where some groups are small, e.g., when n1 = · · · = nk-1 = 1 and nk = n′ . Indeed, the lower bound parts of Theorems 1.1 and 1.2 will be handled in Section 4. ## 3.1 Lower Bound We prove Theorem 3.1 via a simple reduction that views each row of a matrix A as a vector of utilities for the goods. The existence of a consensus 1/k-division up to a small number of goods would imply a strong upper bound on the discrepancy of A. This is formalized below; since the distribution of agents into groups is irrelevant for consensus 1/k-division, we use the notation aj and uj instead of a(i,j) and u(i,j) . Proof of Theorem 3.1. Let ∆ := ⌈discmax (n, k)⌉. Note that ∆ - 1 < discmax (n, k). Thus, there exists m ∈ N and A ∈ [0, 1]n×m such that disc(A, k) > ∆ - 1. We define the agents' utilities by uj (ℓ) = Aj,ℓ for all j ∈ [n] and ℓ ∈ [m]. It suffices to show that there is no consensus 1/k-division up to ∆ - 1 goods with respect to these utilities. Suppose for the sake of contradiction that there is a consensus 1/k-division up to ∆ - 1 goods, (A1, . . . ,Ak). Let χ : [m] → [k] denote the coloring corresponding to this allocation, i.e., χ-1 (s) = As. Consider any agent aj . Since the allocation is a consensus 1/k-division up to ∆ - 1 goods and each good has value at most 1 to each agent, the following holds for all i, s ∈ [k]: Fix any s ∈ [k]. For each j ∈ [n], this inequality allows us to bound the jth entry of A ( 1k · 1 - 1(χ-1 (s))) as where the first inequality follows from the triangle inequality. Applying this for all j ∈ [n], we have disc(A, k) ≤ ∆-1, contradicting our assumption that disc(A, k) > ∆ - 1. ## 3.2 Upper Bound We next prove our upper bound (Theorem 3.2), which turns out to be more challenging than the lower bound. To demonstrate this, let us consider using the "reverse" of the reduction in the proof of Theorem 3.1; specifically, suppose we create one row for each agent corresponding to her utilities. The discrepancy bound ensures that we can divide the goods into k bundles so that each agent's utilities for the k bundles are not too different. However, this does not translate into any bound on the number of goods necessary in the relaxation of any of the fairness notions, since it is possible that an agent has a tiny utility for every good in some bundle. To tackle this issue, we must also ensure that each agent has some "large" (i.e., valuable) goods in every bundle. To this end, we divide the set of goods (with respect to each agent) into the set of large goods and the set of "small" goods. We create one row as before, but only for the small goods; this is to ensure that the utilities of the agent for the small goods do not differ by much between bundles. Additionally, we create a row corresponding to the large goods, which ensures that the agent has a non-trivial number of large goods in each bundle. When choosing the size of the set of large goods appropriately, this gives us the desired bound. We formalize this intuition in the proof below. Proof of Theorem 3.2. Let T := ⌈discmax (2n, k)⌉. For every agent aj , let Sj large ⊆ G denote the set of L := min{m, 3Tk} goods that the agent values the most (ties broken arbitrarily), and let pj := minℓ∈Sj large uj (ℓ). We define yj as the m-dimensional indicator vector of Sj large , i.e., yj = 1(Sj large ). We also define zj as the utility vector of the goods outside of Sj large , scaled by 1/pj , i.e., By our choice of Sj large and pj , we have zj ∈ [0, 1]m. (We use the convention 0/0 = 0, i.e., zj is the all-zero vector when pj = 0.) Finally, we define our matrix A = [y1 · · · ynz1 · · · zn ]T ; note that A ∈ [0, 1]2n×m. From the definition of discmax , there exists a coloring χ : [m] → [k] such that for all i ∈ [k]. We pick our allocation (A1, . . . ,Ak) according to χ, that is, Ai = χ-1 (i) for all i ∈ [k]. Next, we argue that for every pair i, i′ ∈ [k] and every agent aj , there exists B ⊆ Ai′ of size at most 4T such that uj (Ai) ≥ uj (Ai′ \B); this suffices to finish the proof. From (2) and the definition of A, we have Rearranging these, we have and A similar argument on bundle Ai′ implies and Let B := Ai′ ∩ Sj large . By (5), we have |B| ≤ L/k + T ≤ 4T . Now, if m ≤ 3T k, then we have L = m and Ai′ \B = ∅. Thus, uj (Ai) ≥ uj (Ai′ \ B) trivially holds in this case. Next, consider the case m > 3Tk, so L = 3Tk. In this case, we may bound uj (Ai) - uj (Ai′ \ B) as follows: where the first inequality follows from our definition of pj and the last inequality follows from L = 3Tk. This concludes the proof. ## 4 Lower Bounds FromWeighted Discrepancy In this section, we prove a lower bound on cPROP for k groups via weighted discrepancy: Theorem 4.1. For any n′ , k ∈ N, we have Combined with Proposition 2.2, this gives a similar lower bound for cEF (again, the left-hand side contains k - 1 1's): Corollary 4.2. For any n′ , k ∈ N, we have These two results, together with the lower bound on wdiscmax p (Proposition 2.5) and the observation that removing agents does not increase the value of cEF or cPROP , yield the lower bound parts of Theorems 1.1 and 1.2. More specifically, we claim that for any n1, . . . , nk, we have To see why this claim holds, first note that due to symmetry, we may assume that n1 = max{n1, . . . , nk}. Note also that if an allocation satisfies a fairness notion for a certain instance, it still satisfies the same fairness notion when we arbitrarily remove some agent(s) from some group(s). Hence, given any instance with group sizes n1, 1, . . . , 1, we may add agents with arbitrary utilities so that the group sizes become n1, . . . , nk and apply the bound for the latter case. This implies (7), whereupon we can apply Corollary 4.2 and Proposition 2.5 to derive Theorem 1.1. A similar argument can be used to derive Theorem 1.2 from Theorem 4.1. The proof of Theorem 4.1 can be found in the full version of our paper; we describe here the intuition behind it. We construct the utility functions of the agents so that if (A1, . . . ,Ak) is proportional up to a small number of goods, then x := 1(A1) gives us a small 1/k-weighted discrepancy. Similarly to the proof of Theorem 3.1, we start by creating n′ agents in the first group where each agent's utilities correspond to a row of A. This yields a lower bound on each entry of A · 1(A1). To get an upper bound, we simply create a "conjugate" of each of these agents in the first group, i.e., the conjugate utility of each good is simply 1 minus the original utility. However, this construction alone is not sufficient-for example, it is still possible to assign all goods to A1. To avoid this, we create one agent in each of the remaining groups with the same utility for all goods. This ensures that A1 has size roughly m/k, which turns out to be sufficient for bounding the 1/k-weighted discrepancy (using x := 1(A1)). ## 5 Computational Complexity Since efficient algorithms matching the bound in Lemma 2.6 are known [Bansal, 2010; Lovett and Meka, 2015] 6 and all of our upper bounds are obtained by polynomial-time reductions to this bound, it immediately follows that given the goods and the agents' utilities for them, we can efficiently find an allocation matching the upper bounds in our main theorems (Theorems 1.1-1.3). In summary, we have: Corollary 5.1. There exists a randomized polynomial-time algorithm that can compute a consensus 1/k-division (or an envy-free/proportional allocation) up to O(√n) goods. In light of the above corollary, a natural question is whether we can improve on this O(√n) bound if we know that, say, an unknown "fully fair" division exists for a given instance. For example, provided that there is a consensus 1/k-division in that instance, can we efficiently find an allocation that beats the upper bounds in Corollary 5.1? A similar question has been asked in the context of discrepancy theory; for the bound in Lemma 2.3, the answer was shown to be negative [Charikar et al., 2011], i.e., even when A has discrepancy zero, it is NP-hard to find x achieving discrepancy o(√n). In this section, we extend this hardness to the setting of fair division, as stated below. Theorem 5.2. For any constant k ∈ N \ {1}, there exists a constant εk > 0 such that it is NP-hard, given m goods and k groups, each containing n′ agents with additive utilities, to distinguish between the following two cases: 6 Please refer to the full version of our paper for more details [Manurangsi and Suksompong, 2021]. - (YES) There exists a consensus 1/k-division; - (NO) No allocation is proportional up to εk√n′ goods. In other words, when k is constant, we cannot asymptotically improve upon the bound in Corollary 5.1 even when we are promised that a consensus 1/k-division exists. Note that since consensus 1/k-division is the strongest notion and proportionality the weakest (see Proposition 2.2), this theorem is the "strongest possible". ## 6 Conclusion and FutureWork In this paper, we have studied the allocation of indivisible goods to groups of agents using the standard fairness notions of envy-freeness, proportionality, and consensus 1/kdivision. We presented bounds on the optimal relaxations of these notions that can be guaranteed for agents with additive valuations; all of the bounds are asymptotically tight when the number of groups is constant. Our results imply that relatively strong fairness guarantees can be provided for all agents even when agents in the same group, who share the same set of resources, have highly differing preferences. Moreover, we showed that computing allocations that improve upon these bounds is NP-hard even in instances where such allocations are known to exist. Besides closing the gaps left by our work, an interesting direction for future work is to consider agents with arbitrary monotonic utilities. Indeed, the techniques from discrepancy theory that we used crucially rely on the additivity assumption; so does the result of Alon [1987] that established the existence of a consensus 1/k-division for divisible goods. Even in the case of prime numbers k, where a consensus 1/kdivision can be guaranteed for non-additive utilities [FilosRatsikas et al., 2021], 7 it is unclear whether such a division can be rounded into a discrete allocation with a loss that is bounded only in terms of n. Beyond the setting of our paper, one could also consider allocating a mixture of indivisible and divisible goods [Bei et al., 2021] or allowing groups to have different entitlements which can correspond to the group sizes [Chakraborty et al., 2020] as well. ## Acknowledgments This work was partially supported by an NUS Start-up Grant. We would like to thank Paul Goldberg, Alexandros Hollender, and Ayumi Igarashi for interesting discussions and the anonymous reviewers for valuable comments. ## References 1. [Aleksandrov and Walsh, 2018] Martin Aleksandrov and Toby Walsh. Group envy freeness and group Pareto efficiency in fair division with indivisible items. In KI, pages 57-72, 2018. 2. [Alon and Spencer, 2000] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley, 2nd edition, 2000. 3. [Alon, 1987] Noga Alon. Splitting necklaces. Advances in Mathe- matics, 63(3):247-253, 1987. 4. [Aziz and Rey, 2020] Haris Aziz and Simon Rey. Almost group envy-free allocation of indivisible goods and chores. In IJCAI, pages 39-45, 2020. 5. [Bansal, 2010] Nikhil Bansal. Constructive algorithms for discrep- ancy minimization. In FOCS, pages 3-10, 2010. 6. [Bei et al., 2021] Xiaohui Bei, Zihao Li, Jinyan Lu, Shengxin Liu, and Xinhang Lu. Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293:103436, 2021. 7. [Benabbou et al., 2019] Nawal Benabbou, Mithun Chakraborty, Edith Elkind, and Yair Zick. Fairness towards groups of agents in the allocation of indivisible items. In IJCAI, pages 95-101, 2019. 8. [Berliant et al., 1992] Marcus Berliant, William Thomson, and Karl Dunz. On the fair division of a heterogeneous commodity. Journal of Mathematical Economics, 21(3):201-216, 1992. 9. [Bouveret et al., 2016] Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet. Fair allocation of indivisible goods. In Fe- lix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 12, pages 284-310. Cambridge University Press, 2016. 10. [Brams and Taylor, 1996] Steven J. Brams and Alan D. Taylor. A procedure for divorce settlements. Mediation Quarterly, 13(3):191-205, 1996. 11. [Chakraborty et al., 2020] Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick. Weighted envy-freeness in indivisible item allocation. In AAMAS, pages 231-239, 2020. 12. [Charikar et al., 2011] Moses Charikar, Alantha Newman, and Aleksandar Nikolov. Tight hardness results for minimizing dis- crepancy. In SODA, pages 1607-1614, 2011. 13. [Conitzer et al., 2019] Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan. Group fairness for the allocation of indivisible goods. In AAAI, pages 1853-1860, 2019. 14. [Deligkas et al., 2021] Argyrios Deligkas, John Fearnley, Themis- toklis Melissourgos, and Paul G. Spirakis. Computing exact solu- tions of consensus halving and the Borsuk-Ulam theorem. Jour- nal of Computer and System Sciences, 117:75-98, 2021. 15. [Doerr and Srivastav, 2003] Benjamin Doerr and Anand Srivastav. Multicolour discrepancies. Combinatorics, Probability and Com- puting, 12(4):365-399, 2003. 16. [Filos-Ratsikas and Goldberg, 2018] Aris Filos-Ratsikas and Paul W. Goldberg. Consensus halving is PPA-complete. In STOC, pages 51-64, 2018. 17. [Filos-Ratsikas et al., 2020] Aris Filos-Ratsikas, Alexandros Hol- lender, Katerina Sotiraki, and Manolis Zampetakis. Consensus- halving: Does it ever get easier? In EC, pages 381-399, 2020. 18. [Filos-Ratsikas et al., 2021] Aris Filos-Ratsikas, Alexandros Hol- lender, Katerina Sotiraki, and Manolis Zampetakis. A topologi- cal characterization of modulo-p arguments and implications for necklace splitting. In SODA, pages 2615-2634, 2021. Extended version available as arXiv:2003.11974. 19. [Ghodsi et al., 2018] Mohammad Ghodsi, Mohamad Latifian, Ar- man Mohammadi, Sadra Moradian, and Masoud Seddighin. Rent division among groups. In COCOA, pages 577-591, 2018. 20. [Goldberg et al., 2020] Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong. Consensus halving for sets of items. In WINE, pages 384-397, 2020. 21. [Hobby and Rice, 1965] Charles R. Hobby and John R. Rice. A moment problem in L1 approximation. Proceedings of the Amer- ican Mathematical Society, 16(4):665-670, 1965. 22. [Husseinov, 2011] Farhad Husseinov. A theory of a heterogeneous divisible commodity exchange economy. Journal of Mathemati- cal Economics, 47(1):54-59, 2011. 23. [Kyropoulou et al., 2020] Maria Kyropoulou, Warut Suksompong, and Alexandros A. Voudouris. Almost envy-freeness in group re- source allocation. Theoretical Computer Science, 841:110-123, 2020. 24. [Lipton et al., 2004] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair al- locations of indivisible goods. In EC, pages 125-131, 2004. 25. [Lovász et al., 1986] László Lovász, Joel Spencer, and Katalin Vesztergombi. Discrepancy of set-systems and matrices. Eu- ropean Journal of Combinatorics, 7(2):151-160, 1986. 26. [Lovett and Meka, 2015] Shachar Lovett and Raghu Meka. Con- structive discrepancy minimization by walking on the edges. SIAM Journal on Computing, 44(5):1573-1582, 2015. 27. [Manurangsi and Suksompong, 2017] Pasin Manurangsi and Warut Suksompong. Asymptotic existence of fair divisions for groups. Mathematical Social Sciences, 89:100-108, 2017. 28. [Manurangsi and Suksompong, 2021] Pasin Manurangsi and Warut Suksompong. Almost envy-freeness for groups: Improved bounds via discrepancy theory. CoRR, abs/2105.01609, 2021. 29. [Markakis, 2017] Evangelos Markakis. Approximation algorithms and hardness results for fair division. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 12, pages 231- 247. AI Access, 2017. 30. [Moulin, 2003] Hervé Moulin. Fair Division and Collective Wel- fare. MIT Press, 2003. 31. [Moulin, 2019] Hervé Moulin. Fair division in the internet age. An- nual Review of Economics, 11:407-441, 2019. 32. [Segal-Halevi and Nitzan, 2019] Erel Segal-Halevi and Shmuel Nitzan. Envy-free cake-cutting among families. Social Choice and Welfare, 53(4):709-740, 2019. 33. [Segal-Halevi and Suksompong, 2019] Erel Segal-Halevi and Warut Suksompong. Democratic fair allocation of indivisible goods. Artificial Intelligence, 277:103167, 2019. 34. [Simmons and Su, 2003] Forest W. Simmons and Francis Edward Su. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Mathematical Social Sciences, 45(1):15-25, 2003. 35. [Spencer, 1985] Joel Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society, 289(2):679- 706, 1985. 36. [Suksompong, 2018] Warut Suksompong. Approximate maximin shares for groups of agents. Mathematical Social Sciences, 92:40-47, 2018. 37. William Thomson. Introduction to the theory of fair allocation. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Com- putational Social Choice, chapter 11, pages 261-283. Cambridge University Press, 2016. 38. [Todo et al., 2011] Taiki Todo, Runcong Li, Xuemei Hu, Takayuki Mouri, Atsushi Iwasaki, and Makoto Yokoo. Generalizing envy- freeness toward group of agents. In IJCAI, pages 386-392, 2011.