{'fraction_non_alphanumeric': 0.041821961680370084, 'fraction_numerical': 0.01955312494147173, 'mean_word_length': 3.8089705485004055, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Almost Envy-Freeness in Group Resource Allocation

We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under different assumptions on the valuations of the agents. In particular, our results cover cases of arbitrary monotonic, responsive, and additive valuations, while for the case of binary valuations we fully characterize the cardinalities of two groups of agents for which a fair allocation can be guaranteed with respect to both envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). Moreover, we introduce a new model where the agents are not partitioned into groups in advance, but instead the partition can be chosen in conjunction with the allocation of the goods. In this model, we show that for agents with arbitrary monotonic valuations, there is always a partition of the agents into two groups of any given sizes along with an EF1 allocation of the goods. We also provide an extension of this result to any number of groups.


Introduction
Fairness is one of the primary desiderata in decision-making procedures involving multiple agents. For instance, machine learning researchers have recently studied how to design classification systems that do not discriminate based on sensitive attributes such as race or gender [Dwork et al., 2012]. Another problem that is ubiquitous in every society is that of allocating resources among the members of the society. The study of how the allocation can be done fairly, commonly known as fair division, has found applications ranging from settling divorce disputes [Brams and Taylor, 1996] to sharing apartment rent [Su, 1999;Gal et al., 2017].
The vast majority of the fair division literature has focused on allocating resources among individual agents. However, in many practical situations the resources need to be allocated among groups of agents. The agents in each group share the same set of resources, but may have different preferences over them. For instance, the books allocated to a library can be enjoyed by all of its members, and it may be the case that some members prefer detective novels while others would rather read science fiction. Another example is the division of household goods between families; different members of a family may have contrasting opinions on the television or the sofa in their apartment.
The group aspect of fair division was introduced independently by Segal-Halevi and Nitzan [2016] and Manurangsi and Suksompong [2017]. Segal-Halevi and Nitzan investigated the allocation of divisible goods such as cake or land. In contrast, Manurangsi and Suksompong studied the group allocation of indivisible goods like books and cars. Both of these works used the fairness notion of envy-freenessan agent is said to be envy-free if she finds her group's share to be as least as good as the share of any other group. While envy-freeness cannot be guaranteed even when allocating indivisible goods among individuals (consider two agents who quarrel over a single valuable good), Manurangsi and Suksompong showed that if the agents' utilities for the goods are drawn at random, an envy-free allocation exists with high probability in the group setting as the number of agents and goods grows. Segal-Halevi and Suksompong [2018] then introduced the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. Among other fairness notions, they considered envy-freeness up to one good (EF1), which means that while some agent may envy another group under the given allocation, the envy can be eliminated by removing a single good from the other group's share. Segal-Halevi and Suksompong showed that for two groups, there always exists an allocation that is EF1 for at least 1/2 of the agents in each group, and the factor 1/2 cannot be improved. We refer to [Suksompong, 2018b] for an overview of the group fair division literature.
While the aforementioned works provide different methods for extending individual fair division to the group setting, in some situations it may be important that all agents receive a fairness guarantee with certainty regardless of their valuations. Suksompong [2018a] showed the possibilities and limitations of using the maximin share notion to guarantee every agent a fair share. In this work, we study the extent to which the recently introduced relaxations of envy-freeness, most notably EF1 and another notion called EFX, can be used for the same purpose. We show that while EF1 is surprisingly robust and can be guaranteed in a number of group settings, this is not the case for EFX. In addition, we introduce a new model in which the partition of the agents into groups is not fixed in advance, but instead can be chosen in conjunction with the allocation of the goods. This model captures settings where agents (or a central authority) can choose the group that they want to be part of, such as membership in a library or gym.

Our Results
With the exception of Section 5.2, we assume that the goods are allocated between two groups of agents. While this may seem restrictive at first glance, we remark here that fair division between two individual agents, which is much more restrictive, has received a significant amount of attention in the literature (e.g., [Brams and Fishburn, 2000;Brams et al., 2012Brams et al., , 2014Aziz, 2016;Kilgour and Vetschera, 2018]). Indeed, as we will see, the setting of two groups is quite rich and already allows for many interesting, non-trivial results.
In Section 3, we assume that the agents in the two predetermined groups have binary valuations, i.e., each agent either desires each good or not. We characterize the cardinalities of the groups for which an EF1 or EFX allocation always exists. Additionally, we consider a stronger variant of EFX introduced by Plaut and Roughgarden [2018], which we refer to as EFX 0 . We prove a very strong negative result for the group fairness setting, implying that this fairness notion can only be guaranteed when both groups are singletons.
Next, in Section 4, we consider more general classes of valuations. If one group is a singleton and the other group consists of two agents, we show that a balanced EF1 allocation always exists provided that the agents are endowed with responsive valuations, a general class that contains the well-studied class of additive valuations. Balancedness means that the sizes of the two bundles differ by at most one. Moreover, we establish a surprising connection between our group fair division problem and a class of graphs known as generalized Kneser graphs. We show that if a conjecture by Jafari and Alipour [2017] on the chromatic number of particular graphs from this class is true, it would imply that a balanced EF1 allocation exists whenever the two groups contain a total of at most five agents with arbitrary monotonic valuations. This bound would be tight due to our results in Section 3.
Finally, in Section 5 we examine the newly introduced setting where we assume that the partition of the agents into groups is no longer fixed and can be chosen along with the allocation of the goods. Our results indicate that if a central authority or the agents themselves have the power to decide which group to join, then fair allocations are much easier to achieve. In particular, we show that for two groups of agents with arbitrary monotonic valuations, it is always possible to simultaneously obtain a balanced partition of the agents and a balanced EF1 allocation of the goods. In addition, for any given sizes of the two groups, there is a partition of the agents conforming to those sizes together with an EF1 allocation of the goods. We also present an extension of this result to any number of groups.

Further Related Work
The fairness notions EF1 and EFX were introduced by Lipton et al. [2004] and Caragiannis et al. [2016], and studied in several papers over the last few years [Plaut and Roughgarden, 2018;Amanatidis et al., 2018;Biswas and Barman, 2018;Bilò et al., 2019;Oh et al., 2019]. For individual fair division, it is known that an EF1 allocation is guaranteed to exist for any number of agents with monotonic valuations, while the question remains open for EFX.
A recent paper by Ghodsi et al. [2018] addressed the problem of rent division for groups. In addition to determining the allocation of the rooms, the rent of the apartment must be divided among the agents. Like us, Ghodsi et al. also considered a model where the groups are not predetermined.
Another line of research has also considered group fairness in resource allocation but using a different kind of fairness notions than ours [Berliant et al., 1992;Husseinov, 2011;Todo et al., 2011;Aleksandrov and Walsh, 2018;Conitzer et al., 2019]. In these papers, the resources are allocated to individual agents, and the aim is to minimize the envy that arises between groups of these agents. In contrast, in our work the resources are allocated to groups of agents and shared as public goods among the agents within each group.
Recently, Biswas and Barman [2018] examined cardinality constraints in individual fair division, where the goods are categorized and there is a limit on the number of goods from each category that can be allocated to each agent. Our balancedness notion can be seen as a special case of these constraints.

Preliminaries
Let G = {g 1 , . . . , g m } denote the set of goods, and A the set of n agents. A bundle is a subset of G. The agents are partitioned into k ≥ 2 groups. We assume in Sections 3 and 4 that this partition is fixed in advance, and in Section 5 that the partition is variable and can be chosen. Denote by n i the size of group i (so n = k i=1 n i ), and a ij the jth agent of group i. The agents in each group will be collectively allocated a subset of G; denote by B i the bundle allocated to group i so that B i ∩ B j = ∅ for any i = j and ∪ k i=1 B i = G. A partition of the agents is called balanced if |n i − n j | ≤ 1 for any i, j. Similarly, an allocation of the goods is called balanced if ||B i | − |B j || ≤ 1 for any i, j.
Each agent a ij has some non-negative valuation u ij (G ′ ) for each set of goods G ′ ⊆ G; for convenience we write u ij (g) instead of u ij ({g}) for a good g ∈ G. Let u ij := (u ij (g 1 ), . . . , u ij (g m )) be the valuation vector of agent a ij for individual goods. We assume that valuations are • monotonic: u(G 1 ) ≤ u(G 2 ) for any G 1 ⊆ G 2 ⊆ G, and • binary if it is additive and u(g) ∈ {0, 1} for all g ∈ G.
Note that every additive valuation is responsive. Additive valuations are often assumed in recent fair division literature [Caragiannis et al., 2016;Amanatidis et al., 2018;Biswas and Barman, 2018;Conitzer et al., 2019]. An instance consists of agents, goods, and utility functions (and in the model of Sections 3 and 4, the partition of agents into groups). In Section 5, we simply denote the agents by a 1 , . . . , a n and their valuations by u 1 , . . . , u n . We are now ready to define the fairness notions that we consider in this paper.
Definition 2.1. An allocation (B 1 , . . . , B n ) is said to be • envy-free up to any good (EFX 0 ) for agent a ij if for any i ′ and any good g ∈ B i ′ , we have • envy-free up to any positively valued good (EFX) for agent a ij if for any i ′ and any good g • envy-free up to c goods (EFc) for agent a ij , for a given positive integer c, if for any i ′ there is a set An allocation is said to be envy-free if it is envy-free for every agent. When there are two groups, we say that an agent finds a bundle to be envy-free if the allocation that assigns the bundle to her group and the complement bundle to the other group is envy-free for her. Analogous definitions hold for EFX 0 , EFX, and EFc.
EFX 0 is a variant of EFX introduced by Plaut and Roughgarden [2018]. 1 For additive valuations, it is clear that each property in the list is stronger than the next, with EFX implying EF1. We will only consider EFX and EFX 0 in the context of additive valuations. In Sections 4 and 5 we only state results for EFX, but all of these results also hold for EFX 0 .

Fixed Groups with Binary Valuations
In this section, we assume that the agents have binary valuations and are partitioned in advance into two groups of size n 1 and n 2 . Note that any non-existence result for (n 1 , n 2 ) yields an analogous result for (n ′ 1 , n ′ 2 ) with n ′ 1 ≥ n 1 and n ′ 2 ≥ n 2 , since in the latter case a subset of n 1 agents from the first group and a subset of n 2 agents from the second group still need to consider the allocation fair. Similarly, an existence result for (n 1 , n 2 ) yields a corresponding result for (n ′ 1 , n ′ 2 ) with n ′ 1 ≤ n 1 and n ′ 2 ≤ n 2 . We begin by considering the notions EFX and EF1. In fact, for binary valuations one can easily verify that EFX and EF1 are equivalent, so it suffices to consider only EF1.
We first present two results that establish the existence of an EF1 allocation for the cases (n 1 , n 2 ) = (5, 1) and (3, 2). Before we present the proofs, we give a high-level overview of the arguments that we use. First, observe that since the valuations are binary, each good can be described by the set of agents who desire it. If two goods are desired by the same set of agents, we can allocate one to each group and then search for an EF1 allocation of the reduced instance with the remaining goods. Hence we may assume that every good is desired by a distinct subset of agents. This reduces the problem to a finite (but still large) number of possible instances. We then perform other preprocessing steps to reduce the number of cases even further. For example, if an agent desires an odd number of goods, the requirement that EF1 imposes on the agent remains the same when we perturb the valuation of the agent so that she no longer desires an arbitrary good. As a result, we may assume that every agent desires an even number of goods.
Proof. For the sake of convenience, we slightly modify the notation used in this proof. Consider an instance with two groups of agents A = {1, 2, 3, 4, 5} and B = {b}. For a set of goods G ′ ⊆ G, let d i (G ′ ) be the subset of goods in G ′ that agent i desires. For binary valuations, each good g ∈ G can be represented by the set of agents who desire it, i.e., we represent g by the set {i ∈ A ∪ B | g ∈ d i (G)}. First, we perform a number of preprocessing steps as follows. 1 In their paper this property is simply called EFX; we rename it to avoid confusion with the original definition of Caragiannis et al. [2016], which we refer to as EFX.
(P1) We allocate each good g ∈ d b (G) to group A; this reduces the problem to finding an EF1 allocation of the remaining goods. Hence, we may assume that d b (G) = G, and simply represent each good g as a subset of {1, 2, 3, 4, 5}.
(P2) If there are an odd number of goods, then we allocate an arbitrary good to group A; this again reduces the problem to finding an EF1 allocation of the remaining goods. Hence, we may assume that there are an even number of goods.
(P3) If there are two goods g and g such that g ⊆ g, then we allocate g to group A and g to agent b. More generally, if there are two disjoint sets of goods G 1 and G 2 of equal size such that |d i (G 1 )| ≥ |d i (G 2 )| for every agent i ∈ A, then we allocate G 1 to group A and G 2 to agent b. Therefore, in the following, we may assume that every good is represented by a distinct set of agents, and there is no subset-superset relations among the goods.
(P4) For any agent i ∈ A that desires an odd number of goods, we assume a modified valuation functionũ i such thatũ i (g * ) = 0 for some g * that is desired by agent i according to u i , and u i (g) = u i (g) for g = g * . This again reduces the problem to finding an EF1 allocation for the instance with modified valuation functions. After we perform this step, it may be possible to perform the previous steps again. In such a case, we keep performing these steps until no longer possible.
After the preprocessing, there are an even number of goods and every agent desires an even number of goods. We claim that actually there are no goods left. Assume otherwise.
• If there is a good g of size 0 or 5, then no other good g ′ can appear since g ′ would either be a superset or a subset of g, and step (P3) would have already allocated both g and g ′ . Therefore, there is only one good, contradicting the assumption that the number of goods is even.
• If there is a singleton good g = {i} for some i ∈ {1, 2, 3, 4, 5}, then no other good g ′ containing i can appear, since otherwise g ′ would be a superset of g. Therefore, agent i only desires one good, contradicting the assumption that every agent desires an even number of goods.
• If there is a good g of size 4, say g = {1, 2, 3, 4}, then any other good g ′ must contain 5, since otherwise g ′ would be a subset of g. Since there are an even number of goods, this means that agent 5 desires an odd number of goods, again contradicting the assumption that all agents in A desire an even number of goods.
Therefore, all goods correspond to subsets of size 2 or 3. Let k 2 and k 3 denote the number of goods of size 2 and 3, respectively. Since all agents desire an even number of goods, k 3 must be even, and since there are an even number of goods, k 2 must be even as well. It suffices to consider the case where k 2 ≥ k 3 . This is without loss of generality because if k 2 < k 3 , we can replace each good g by its complement A\g. In the new instance, there are still an even number of goods, every agent still desires an even number of goods, and k 2 ≥ k 3 . Moreover, if there is a preprocessing step that can be applied to the new instance, a corresponding step can be applied to the original instance.
Recall that |A| = 5 and every subset is represented by at most one good, so k 2 cannot exceed the number of sets of size 2 from a universe of size 5, which is 10. Since k 2 is even, k 2 ≥ k 3 , and k 2 + k 3 > 0, we have k 2 ∈ {2, 4, 6, 8, 10}. We consider each of these cases in turn.
• Case 2: k 2 = 8. Consider the two goods of size 2 that are absent. If they share one element, we may assume without loss of generality that they are {3, 5} and {4, 5}; if they do not share any element, we may assume that they are {2, 3} and {4, 5}. Either way, the goods then G 1 and G 2 should have already been allocated in step (P3), a contradiction.
• Case 3: k 2 = 6. First, note that if k 3 ≥ 2, then since we have already allocated all goods that form subset-superset relations in step (P3), we must have k 2 ≤ 5. Hence, k 3 = 0. If at least two of the agents desire four goods each, there must be at least seven goods in total, which is not the case. Since every agent desires an even number of goods, the only possibility is that one of the agents desires four goods and the remaining four agents two goods each. Assume without loss of generality that the goods • Case 5: k 2 = 2. Consider the two goods of size 2 that are present. Since these goods have to be distinct and all agents desire an even number of goods, we cannot have k 3 = 0, so k 3 = 2.
- In either case, we may set G 1 to contain the two goods of size 3 and G 2 = {{1, 2}, {3, 4}} and obtain a contradiction as before.
All cases have been exhausted, and the proof is complete.
Proof. For the sake of convenience, we slightly modify the notation used in this proof. Consider an instance with two groups of agents A = {1, 2, 3} and B = {x, y}. We represent each good by the set of agents who desire it. For convenience, we denote a good g as g = S T , where S ⊆ A and T ⊆ B are the subsets of agents who desire g in A and B, respectively. Similarly to the proof of Theorem 3.1, we can perform some preprocessing steps so that every good is desired by at least one agent in each group (if g = S T is such that S = ∅ or T = ∅, then we can simply allocate g to group B or group A, respectively), and every agent desires an even number of goods (if this is not the case, we modify the valuation function of every such agent by making the agent "undesire" an arbitrary good; this does not affect whether the agent considers an allocation to be EF1). We further assume that each agent in B desires at least one good; otherwise the problem reduces to the (n 1 , n 2 ) = (3, 1) case, which is already covered by Theorem 3.1.
If two goods g 1 = S T 1 1 and g 2 = S T 2 2 are such that S 1 ⊇ S 2 and T 1 ⊆ T 2 , then we can allocate g 1 to A and g 2 to B. Since the agents in A that desire g 2 also desire g 1 , and the agents in B that desire g 1 also desire g 2 , this reduces the problem to computing an EF1 allocation for the remaining goods. In the following we therefore assume that there do not exist two such goods; in particular, there is at most one good of type S T for each S ⊆ {1, 2, 3} and T ⊆ {x, y}, and there are at most three goods of type S T for each T ⊆ {x, y}. More generally, if there are two disjoint sets of goods G 1 and G 2 such that every agent in A desires at least as many goods in G 1 as in G 2 , while every agent in B desires at least as many goods in G 2 as in G 1 , we can allocate G 1 to A and G 2 to B. Consequently, we may assume that there do not exist two such sets of goods.
We now show that all goods have been allocated by the above preprocessing steps. By the above discussion, if the good {1, 2, 3} x is present, then no other good that agent x desires can be present, which means that x desires an odd number of goods, a contradiction. Hence, goods {1, 2, 3} x and {1, 2, 3} y are absent. Similarly, if the good {1} xy is present, then no other good that agent 1 desires can be present, meaning that 1 desires an odd number of goods, again contradicting the assumption that all agents desire an even number of goods. So, goods {1} xy , {2} xy , and {3} xy are absent. Therefore, the goods of type S xy that can be present are {1, 2} xy , {1, 3} xy , {2, 3} xy , and {1, 2, 3} xy . We consider some cases.
• Case 1: No good of type S xy is present. Since every agent desires an even number of goods and each agent in B desires at least one good, there are exactly two goods of type S x and two goods of type S y . Let these goods be S x 1 , S x 2 , T y 1 and T y 2 ; by the above preprocessing steps, there are no subset-superset relations between (S 1 , S 2 ) and (T 1 , T 2 ).
-Case 1.1: |S 1 | = |S 2 | = 1. Without loss of generality, assume that S 1 = {1} and S 2 = {2}. Since each agent desires an even number of goods, the other two goods are either {1} y and {2} y , or {1, 3} y and {2, 3} y . In the first case we set Then G 1 and G 2 should have been allocated during the preprocessing steps (since every agent desires the same number of goods in G 1 as in G 2 ), a contradiction.
-Case 1. , 3} xy must be absent. Since every agent desires an even number of goods, there is an odd number (one or three) of goods of type S x as well as an odd number of goods of type S y .
-Case 2.1: There is one good of type S x . Since each agent desires an even number of goods, there is also exactly one good of type T y with S ∩ T = ∅ and S ∪ T = {1, 2, 3}. By setting G 1 = {S x , T y } and G 2 = {{1, 2, 3} xy }, G 1 and G 2 should have already been allocated during the preprocessing steps, a contradiction.
-Case 2.2: There are three goods of type S x . These must be either then G 1 and G 2 should have already been allocated during the preprocessing steps, a contradiction. So, there is only one good of type S x and, similarly, only one good of type T y . Moreover, we must have 1, 2 ∈ S ∪ T since, again, both agents 1 and 2 desire an even number of goods. If we set G 1 = {S x , T y } and G 2 = {{1, 2} xy }, then G 1 and G 2 should have already been allocated during the preprocessing steps, a contradiction.
• Case 4: Good {1, 2, 3} xy is absent, and exactly two goods S xy with |S| = 2 are present. Without loss of generality, assume that these are {1, 2} xy and {1, 3} xy . By the preprocessing steps, goods {1, 2} x , {1, 2} y , {1, 3} x , and {1, 3} y must be absent. Since every agent desires an even number of goods, there is an even number (zero or two) goods of type S x and an even number of goods of type S y .
-Case 4.1: There is no good of type S x or no good of type S y . Let us assume the former; the latter case can be handled analogously. , 3} x , and {2, 3} y must be absent. Since every agent desires an even number of goods, there is an odd number (one or three) goods of type S x and an odd number of goods of type S y . The only possibility that makes each agent of group A desire an even number of goods is that there are three goods of each type: , 3} xy }, then G 1 and G 2 should have already been allocated during the preprocessing steps, a contradiction.
All cases have been exhausted, and the proof is complete.
The following results complete the characterization for EF1 (and EFX) by proving that existence is not guaranteed for larger sets.
Proof. Suppose that there are four goods. For each pair of goods, there is an agent in the first group who desires both of the goods in the pair but does not desire the remaining two goods. On the other hand, the singleton agent in the second group desires all goods. To guarantee EF1, this agent must receive at least two goods, leaving at most two goods for the first group. However, this leaves some agent in the first group with utility 0, and such an agent does not find the allocation to be EF1.
Proof. Suppose that there are four goods. The utilities in the first group are given by u 11 = (1, 0, 1, 0), u 12 = (1, 0, 0, 1), u 13 = (0, 1, 1, 0), and u 14 = (0, 1, 0, 1), and the utilities in the second group by u 21 = (1, 1, 0, 0) and u 22 = (0, 0, 1, 1). In an EF1 allocation, every agent needs at least one desired good. In particular, the second group needs one of the first two goods and one of the last two goods. However, any choice of these goods leaves some agent in the first group with utility 0, meaning that no allocation in EF1.
In the next proposition, we give a general example for EFc since this will be useful later on.
Proof. Suppose that there are 2c + 1 goods. For each subset of c + 1 goods, there is exactly one agent in each group who desires the goods in this subset and nothing else. Every agent must get at least one desired good in an EFc allocation. However, in any allocation one of the groups receives at most c goods. In that group, at least one of the agents does not get any desired good. Hence no allocation can be EFc.
Before addressing EFX 0 , we show that for two groups of arbitrary sizes, determining whether an EF1 (and EFX) allocation exists is computationally hard. Our reduction is similar to the one used by Segal-Halevi and Suksompong [2018] to show the hardness of deciding the existence of an allocation that gives every agent a positive utility.
Proposition 3.7. For two groups of agents with binary valuations, it is NP-complete to decide whether there exists an EF1 allocation.
Proof. The problem is in NP, since we can clearly verify in polynomial time whether an allocation is EF1 for every agent. To show hardness, we use a reduction from the MONOTONE 3-SAT problem, which asks whether a Boolean formula consisting of clauses with either three positive or three negative literals can be satisfied. In fact, we will use the slightly stronger version where the three literals in each clause are distinct; this version is still NP-complete [Li, 1997].
Given an instance of MONOTONE 3-SAT consisting of a formula φ, we construct an instance of our problem with two groups of agents A 1 and A 2 as follows: • For each variable, there is a corresponding good.
• For each clause with three positive literals, we create an agent in A 1 who desires exactly the three goods corresponding to the variables contained in the clause.
• For each clause with three negative literals, we create an agent in A 2 who desires exactly the three goods corresponding to the variables contained in the clause.
Note that every agent needs at least one desired good in order to be EF1. Any assignment that satisfies φ defines an allocation where the goods corresponding to true variables are allocated to group A 1 , while those corresponding to false variables are allocated to group A 2 . Since all clauses are satisfied, every agent receives utility at least 1 and is therefore EF1. Similarly, any EF1 allocation gives rise to a satisfying assignment for φ, completing the reduction.
We now turn to the stronger notion of EFX 0 , and show a negative result.
Proof. Suppose that there are six goods. The utilities are given by u 11 = (1, 1, 1, 0, 0, 0), u 12 = (0, 0, 0, 1, 1, 1), and u 21 = (1, 1, 1, 1, 1, 1). To guarantee EFX 0 , the singleton agent in the second group must receive at least three goods, leaving at most three goods for the first group. This means that at least one of the agents in the first group, say a 11 , receives at most one desired good. If a 11 does not receive any desired good, the allocation is clearly not EFX 0 for her. Else, she receives exactly one desired good. In this case, she has utility 2 for the second group's bundle, and at least one of the goods in that bundle yields utility 0 to her. Therefore the allocation cannot be EFX 0 .
In contrast, Plaut and Roughgarden [2018] showed that an EFX 0 allocation always exists if (n 1 , n 2 ) = (1, 1), even for arbitrary monotonic valuations. Combined with Proposition 3.8, this yields a complete characterization of EFX 0 for every class of valuations between binary and monotonic.

Fixed Groups with General Valuations
In this section, we again assume that the partition of the agents into two groups is predetermined, but allow them to have more general valuations.
We first show that the existence of EF1 allocations is guaranteed for (n 1 , n 2 ) = (2, 1). The proof relies on the following lemma which may be of independent interest. A partition of the goods in G into two bundles is said to be exact up to one good (Exact1) for an agent if the agent views each bundle to be EF1. As with allocations, we call a partition of the goods balanced if the sizes of the two bundles differ by at most one.
Lemma 4.1. For two agents with responsive valuations, there always exists a balanced partition of G into two bundles that is Exact1 for both agents.
Proof. Suppose first that the number of goods m is even, say m = 2t. Assume without loss of generality that the valuation u 1 of the first agent is such that u 1 (g 1 ) ≥ u 1 (g 2 ) ≥ · · · ≥ u 1 (g 2t ).
Construct an undirected graph H with 2t vertices corresponding to the goods, and add t red edges (g 1 , g 2 ), (g 3 , g 4 ), . . . , (g 2t−1 , g 2t ). Similarly, add t blue edges according to the valuation u 2 of the second agent. Since no two edges of the same color are adjacent, the graph cannot contain an odd cycle, which means that H is bipartite. Therefore, its vertices can be partitioned into disjoint independent sets V 1 and V 2 . If |V 1 | ≥ t + 1, there is an edge among the vertices in V 1 , a contradiction. An analogous statement holds for V 2 . It follows that |V 1 | = |V 2 | = t.
The partition (V 1 , V 2 ) is balanced; it remains to show that it is Exact1 for both agents. By symmetry, it suffices to prove this for the first agent. By construction, each of V 1 and V 2 contains exactly one good from each of the pairs (g 1 , g 2 ), (g 3 , g 4 ), . . . , (g 2t−1 , g 2t ). For i = 1, 2, . . . , t − 1, the ith best good in V 1 according to the first agent's valuation is no worse than the (i + 1)st best good in V 2 . Responsiveness then implies that the agent values V 1 at least as much as V 2 when the best good in V 2 is removed. This means that she regards V 1 to be EF1. Similarly, she regards V 2 to be EF1; hence the partition is Exact1 for her.
Suppose now that m = 2t − 1 is odd. We add a dummy good g 2t such that u i (G ′ ∪ {g 2t }) = u i (G ′ ) for i = 1, 2 and any G ′ ⊆ G. We then repeat the same procedure as in the case where m is even (placing g 2t at the end of each agent's ranking of single goods), and remove g 2t from the resulting partition. The final partition is balanced, and a similar proof as before shows that it is Exact1 for both agents.
Note that the lemma no longer holds if we move to three agents (while still keeping the partition into two bundles), even for binary valuations. Indeed, if there are three goods and each of the three agents desires a distinct subset of two goods, then no partition is Exact1 for all three agents.
Lemma 4.1 yields the following EF1 existence result.
Proof. Choose two arbitrary agents and consider a balanced partition of G into two bundles that is Exact1 for both agents; such a partition exists by Lemma 4.1. Let the remaining agent choose for her group the bundle that she prefers, and allocate the other bundle to the other group. It is clear that the resulting allocation is balanced and EF1.
In light of Theorem 4.2 and our characterization for binary valuations in Section 3, it is natural to ask whether EF1 can also be guaranteed for larger groups with additive valuations and beyond. While we were unable to settle this question, we show that the existence of EF1 allocations would be guaranteed for almost all of the remaining cases provided that a graph-theoretic conjecture of Jafari and Alipour [2017] is true. To describe the conjecture and its implications in our setting, we need to introduce a class of graphs called generalized Kneser graphs. 2 Definition 4.3. Let b ≥ r ≥ s be positive integers and consider an underlying set of elements U such that |U | = b. The generalized Kneser graph K(b, r, s) is an undirected graph with all r-element subsets of U as its vertices. Two vertices are connected by an edge if and only if the corresponding subsets intersect in at most s − 1 elements.
Recall that the chromatic number of a graph H, denoted by χ(H), is the minimum number of colors needed to color the vertices of H so that any two adjacent vertices have different colors. For example, K(4, 2, 2) is a clique of size 6, so its chromatic number is 6.
We are now ready to establish the connection between the generalized Kneser graph and our fair division problem.
Theorem 4.4. Let z := min r≥2 χ(K(2r, r, 2)). For two groups with at most z − 1 agents in total and arbitrary monotonic valuations, a balanced EF1 allocation always exists.
Proof. Suppose first that the number of goods m is even, say m = 2t. If t = 1, any allocation that gives one good to each group is balanced and EF1, so we may assume that t ≥ 2. Consider the graph K(2t, t, 2) with the vertices corresponding to all balanced allocations, where we identify each vertex by the set of goods allocated to the first group.
Give each agent a distinct color, and let her color all allocations that she does not regard as EF1. We claim that no agent can color two adjacent vertices. Consider an agent in the first group with valuation u, and suppose for contradiction that she colors two adjacent vertices corresponding to the sets G 1 and G 2 . Since the two vertices are adjacent, |G 1 ∩ G 2 | ≤ 1. If G 1 ∩ G 2 = ∅, since |G 1 | = |G 2 | = t it holds that G 2 = G\G 1 . So the agent should consider one of the two allocations as EF, which is a contradiction to her coloring both vertices. Therefore |G 1 ∩ G 2 | = 1. Let g be the common good of G 1 and G 2 . Since the agent does not view G 1 to be EF1, we have u(G 1 ) < u(G 2 \{g}) = u((G\G 1 )\{g ′ }), where g ′ is the unique good that does not belong to G 1 ∪ G 2 . Similarly, since the agent does not view G 2 to be EF1, we have u(G 2 ) < u(G 1 \{g}). Monotonicity then implies that a contradiction. The claim can be proven similarly for agents in the second group by observing that for any two balanced allocations, the bundles allocated to the first group intersect in at most one good if and only if the same condition holds for the bundles allocated to the second group.
Since there are at most z − 1 agents, the number of colors is at most z − 1 ≤ χ(K(2t, t, 2)) − 1. Hence there is a vertex that does not receive any color. By definition, this vertex corresponds to a balanced allocation that is EF1 for all agents. This completes the proof for the case where m is even.
Suppose now that m = 2t−1 is odd. We add a dummy good g 2t such that u ij (G ′ ∪{g 2t }) = u ij (G ′ ) for all agents a ij and all G ′ ⊆ G. We then repeat the same procedure as in the case where m is even and remove g 2t from the resulting allocation. The final allocation is balanced, and a similar proof as before shows that it is EF1. Jafari and Alipour [2017] proved that K(2r, r, 2) ≤ 6 for all r ≥ 2, and conjectured that this bound is in fact always tight.
If Conjecture 4.5 is true, then together with Theorem 4.4, it would imply that a balanced EF1 allocation is guaranteed to exist for two groups with at most 5 agents in total and arbitrary monotonic valuations. 3 The bound of 5 cannot be improved to 6 due to Corollary 3.6. Moreover, this result would answer the EF1 existence question in the affirmative for all of the remaining group sizes except for the case (5, 1). We remark that for this case, a balanced EF1 allocation might not exist, even when valuations are binary.
Proof. Suppose that there are four goods. The utilities in the first group are given by u 11 = (1, 1, 0, 0), u 12 = (1, 0, 1, 0), u 13 = (1, 0, 0, 1), u 14 = (0, 1, 1, 0), u 15 = (0, 1, 0, 1), and in the second group by u 21 = (1, 1, 0, 0). The only balanced allocation that is EF1 for all agents in the first group is the allocation that gives the first two goods to the first group. However, this allocation is not EF1 for the singleton agent, so no balanced allocation is EF1. 4 We note that our techniques in Theorem 4.4 can be extended to weaker relaxations of envy-freeness. For any positive integer c, it is known that an EFc allocation is guaranteed to exist for two groups with at most c + 1 agents in total and additive valuations [Segal-Halevi and Suksompong, 2018]. On the other hand, letting z c := min r≥c+1 χ(K(2r, r, c + 1)), a similar proof as in Theorem 4.4 shows that an EFc allocation can always be found when the two groups contain at most z c − 1 agents in total with arbitrary monotonic valuations. Jafari and Alipour [2017] proved that χ(K(2r, r, c + 1)) ≤ 2c+2 c+1 for all r ≥ c + 1. If this inequality becomes equality for all r (in which case we would have z c = 2c+2 c+1 ), it would imply an exponential improvement in the relation between the number of agents and the number of goods in the EFc approximation. The bound z c − 1 would also be tight due to the instance in Proposition 3.5.
We conclude this section by showing that existence can no longer be guaranteed if we strengthen the fairness requirement from EF1 to EFX. Recall that for binary valuations, an EFX allocation always exists when one group contains at most five agents and the other group is a singleton. We show that this is not the case for additive valuations, even when the first group contains only two agents.
Proof. Suppose that there are four goods. The utilities are given by u 11 = (3, 1, 1, 1), u 12 = (1, 3, 1, 1), and u 21 = (3, 3, 1, 1). In an EFX allocation, the singleton agent in the second group needs either both of the first two goods, or one of the first two and at least one of the last two goods. The former option leaves both agents in the first group unsatisfied. For the latter option, assume without loss of generality that the singleton agent receives g 1 and g 3 . Then the resulting allocation is not EFX for a 11 . Hence there is no EFX allocation in this instance.
Since an EFX allocation always exists when (n 1 , n 2 ) = (1, 1) for arbitrary monotonic valuations [Plaut and Roughgarden, 2018], we have a complete characterization of EFX for every class of valuations between additive and monotonic.

Variable Groups
Thus far, we have worked under the assumption that the partition of agents into groups is determined in advance. This assumption is appropriate when we consider, for example, membership in a family or citizenship of a country. In other settings, however, the choice of the group to which the agents belong can be made by a central authority or by the agents themselves. This applies to membership in a library, gym, or other facilities.
With this motivation in mind, we depart from the framework of fixed groups in this section, and instead assume that the partition of the agents into groups can be chosen along with the allocation of the goods. Under this assumption, finding an EF1, EFX, or even envy-free allocation is trivial: simply put all agents in one group and allocate all goods to that group. However, this may lead to undesirable situations where a gym is overcrowded or a library does not have enough space to hold all of its books. As we will show, it is nevertheless possible to obtain a fair outcome that is moreover balanced with respect to both the agents and the goods, for any number of agents with general valuations.

Two Groups
We start with two groups and show that EF1 can be guaranteed for any desired sizes of these groups. Our algorithm generalizes the discrete "cut-and-choose" algorithm for allocating indivisible goods between two individual agents [Bilò et al., 2019;Oh et al., 2019].
Theorem 5.1. Let n be any positive integer. Suppose that there are n agents with arbitrary monotonic valuations, and let n 1 and n 2 be non-negative integers with n 1 + n 2 = n. There always exists a partition of the agents into two groups such that group i ∈ {1, 2} contains n i agents, along with an EF1 allocation of the goods to the two groups.
Proof. Arrange the goods in a line. Starting with an empty bundle, we add one good at a time from the left until at least n 1 agents find the bundle to be EF1. If this condition is met before we add any good, we give n 1 of these agents an empty bundle and the remaining n 2 agents the entire set G. Otherwise, denote by g the last good added to the bundle. We assign to the first group all agents who view the bundle as EF1 before the addition of g, along with an arbitrary subset of those who find it EF1 after g is added so that the first group has size n 1 . We allocate this bundle to the first group, and the remaining goods to the second group, which consists of the remaining agents.
Since the entire set G is EF1 for all agents, the process terminates. By construction, the agents in the first group regard the allocation as EF1, so we only need to show that the same holds for the second group. This is trivial if the second group receives the entire set G. Otherwise, let G L and G R be the bundles to the left and right of g, respectively (not containing g). Every agent in the second group does not find G L to be EF1, which means that she has more value for G R than G L . This implies that the agent finds G R to be EF1, as desired.
For the case where a balanced allocation of the goods is required, we prove that this can also be achieved and, in fact, it can always be combined with a balanced partition of the agents. This means that in our gym and library applications, it is possible to reach a balance in terms of the users as well as the resources.
Theorem 5.2. Let n be any positive integer, and suppose that there are n agents with arbitrary monotonic valuations. There always exists a balanced partition of the agents into two groups along with a balanced EF1 allocation of the goods to the two groups.
Proof. Suppose first that both the number of agents n and the number of goods m are even, say n = 2s and m = 2t. Assume for contradiction that there is no balanced partition along with a balanced allocation.
Arrange the goods around a circle with equal spacing between adjacent goods. Imagine a knife that cuts through the center of the circle, dividing the goods into two bundles G 1 and G 2 , each of size t. By our assumption, any balanced assignment of the agents to G 1 and G 2 does not result in an EF1 allocation. On the other hand, there does exist an assignment such that the resulting allocation is EF1 (e.g., an assignment that gives every agent her favorite bundle). Consider such an assignment that moreover minimizes the difference between the numbers of agents in the two groups. Assume without loss of generality that more than half of the agents are assigned to G 1 . If one of these agents finds G 2 to be EF1, we can reassign her to G 2 and reduce the discrepancy between the two groups. Hence all of these agents do not find G 2 to be EF1.
Next, we rotate the knife clockwise by one position, thereby moving a good g from G 1 to G 2 and another good g from G 2 to G 1 . Call the resulting bundles H 1 = (G 1 ∪ {g})\{g} and H 2 = (G 2 ∪ {g})\{g}, respectively. We claim that the agents who do not find G 2 to be EF1 regard H 1 as EF1. Denoting the valuation of an arbitrary such agent by u, we have where the first and third inequalities follow from monotonicity. So the agent indeed finds H 1 to be EF1. Since more than half of the agents do not find G 2 to be EF1, more than half of the agents regard H 1 as EF1. By our assumption, any balanced assignment of the agents to H 1 and H 2 does not result in an EF1 allocation. It follows that in any assignment such that the resulting allocation is EF1, more than half of the agents are assigned to H 1 . Additionally, more than half of the agents do not find H 2 to be EF1.
If we rotate the knife clockwise repeatedly, the same argument tells us that more than half of the agents do not find the second bundle (i.e., G 2 , H 2 , and so on) to be EF1. After t rotation steps, the knife has rotated halfway around the circle, and the second bundle coincides with the original first bundle G 1 . However, we know from earlier that more than half of the agents find G 1 to be EF1. This yields the desired contradiction.
Suppose now that n is odd or m is odd (or both). If n is odd, we add a dummy agent with an arbitrary monotonic valuation. If m is odd, we add a dummy good that always yields zero marginal utility for every agent. We then repeat the same procedure as in the case where m and n are even, and remove the dummy agent and/or the dummy good. The resulting partition and allocation are both balanced, and a similar proof as before shows that the allocation is EF1.
Theorem 5.2 yields the following result on individual fair division, which is new to the best of our knowledge.
Corollary 5.3. For two individual agents with arbitrary monotonic valuations, there always exists a balanced EF1 allocation.
When valuations are responsive, a balanced EF1 allocation (for arbitrarily many agents) can also be obtained by the round-robin algorithm, which lets the agents take turns choosing their favorite good from the remaining goods until all goods are taken (see, e.g., [Caragiannis et al., 2016]). However, the round-robin algorithm does not work for arbitrary monotonic valuations.
Turning our attention to EFX, we show that if we require the partition of the agents to be balanced, an EFX allocation might not exist; this complements Theorems 5.1 and 5.2 above. In addition, a balanced EFX allocation does not necessarily exist for two individual agents even when the agents have identical additive valuations, which complements Corollary 5.3.
Proposition 5.4. There does not always exist a balanced partition of the agents into two groups along with an EFX allocation of the goods to the two groups, even when valuations are additive.
Proof. Suppose that there are six agents and three goods. The utilities of the agents are given by u 1 = u 2 = (3, 1, 1), u 3 = u 4 = (1, 3, 1), and u 5 = u 6 = (1, 1, 3). If the allocation places all three goods in one bundle, all agents must be assigned to that bundle for the allocation to be EFX. Else, the allocation places two goods in one bundle and one good in the other bundle. In this case, at most two agents can be assigned to the second bundle in an EFX allocation, so the partition of agents would not be balanced. Hence there is no balanced partition of agents if the allocation must be EFX.
Proposition 5.5. Let m be a positive integer. There exists an instance with two individual agents who have identical additive valuations and m goods, such that in any EFX allocation, one of the agents receives exactly one good.
Proof. Consider two agents with the same additive valuation u(g 1 ) = m and u(g i ) = 1 for i = 2, 3, . . . , m. Assume without loss of generality that the first agent receives g 1 . If the first agent also receives another good g i , then the second agent's value for the first agent's bundle when g i is removed is at least m. On the other hand, the second agent's value for her own bundle is at most m − 2. Hence the first agent cannot receive another good besides g 1 .

Any Number of Groups
We now consider any number of groups and show how Theorem 5.1 can be partially extended to this setting. While we do not know whether EF1 or other relaxations of envy-freeness can be achieved in this general setting, we show that we can obtain a positive result for a weaker fairness notion called proportionality. An allocation of the goods in G to k groups is said to be proportional if every agent receives value at least 1/k of her value for the whole set G. As with envy-freeness, a proportional allocation does not always exist (e.g., when there are two individual agents and one valuable good), so it is necessary to consider a relaxation. Let u j,max := max m t=1 u j (g t ) denote the maximum value of agent a j for a single good.
Theorem 5.6. Let n and k be any positive integers. Suppose that there are n agents with additive valuations, and let n 1 , . . . , n k be non-negative integers with k i=1 n i = n. There always exists a partition of the agents into k groups such that group i contains n i agents, along with an allocation of the goods to the k groups such that each agent a j receives utility at least 1 k · u j (G) − k−1 k · u j,max .
Proof. Let w j := 1 k ·u j (G)− k−1 k ·u j,max . Arrange the goods in a line and process them from left to right. Suppose that we have already formed i − 1 groups. Starting with an empty bundle, we add one good at a time from the left until at least n i agents a j receive utility at least w j . If this condition is met before we add any good, assign n i of these agents to the ith group, give them an empty bundle, and remove them from consideration. Otherwise, denote by g the last good added to the bundle. Assign to the ith group all agents who already have enough utility before g is added, along with an arbitrary subset of those who have enough utility after g is added so that the group has size n i . Allocate the current bundle to the group, and remove the agents and goods involved from consideration. After we have formed k − 1 groups, simply assign the remaining agents to the kth group and give them the leftover goods.
Consider any agent a j . It suffices to show that if at most k − 1 groups have been formed, the agent still has utility at least w j for the remaining goods. The statement holds trivially if w j ≤ 0, so we may assume that w j > 0. If a group takes an empty bundle, a j loses utility 0. Else, denote by g the last good added to the bundle that a group takes. The agent a j has utility less than w j for the bundle before g is added, so she has utility less than w j + u j,max for the bundle with g. Hence the bundles that have been already allocated to groups are together worth at most (k−1)(w j +u j,max ) = k−1 k ·u j (G)+ k−1 k ·u j,max to a j . This means that a j has utility at least u j (G) − k−1 k · u j (G) + k−1 k · u j,max = w j for the remaining goods, as claimed.
Theorem 5.6 generalizes a result of Suksompong [2017], which holds for individual fair division (i.e., n i = 1 for all i = 1, . . . , k). The factor k−1 k in the approximation cannot be improved even in this special case.

Discussion
In this paper, we examine the fairness guarantees that can be obtained in the allocation of indivisible goods among groups of agents. For two fixed groups of agents, we provide a complete picture for EF1 and EFX when agents have binary valuations, and we present further positive and negative results for more general valuations. We also introduce a new model where the partition of the agents into groups can be determined along with the allocation of the goods, and show that it is possible to attain a balance in both the agents and the goods simultaneously.
Our work leaves many open questions for future study. For two groups, one could try to establish the existence of EF1 allocations for larger group sizes, either by settling the graph-theoretic conjecture of Jafari and Alipour [2017] or via other means. In addition, the questions that we study in this paper can also be asked for multiple groups; our techniques do not seem to extend easily to more than two groups in most cases. For individual fair division, we also leave the question of whether a balanced EF1 allocation can always be found for any number of agents; Corollary 5.3 gives a positive answer for the case of two agents. While the round-robin algorithm works when valuations are responsive, the question intriguingly remains open for arbitrary monotonic valuations.