# almost_envyfreeness_in_group_resource_allocation__8c120c4b.pdf

Almost Envy-Freeness in Group Resource Allocation

Maria Kyropoulou1 , Warut Suksompong2 and Alexandros A. Voudouris2

1School of Computer Science and Electronic Engineering, University of Essex 2Department of Computer Science, University of Oxford maria.kyropoulou@essex.ac.uk, {warut.suksompong, alexandros.voudouris}@cs.ox.ac.uk

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.

1 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 classiﬁcation 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 its members. 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 ﬁction. 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-freeness an agent is said to be envy-free if she ﬁnds 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. 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 [2018] 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 ﬁxed in advance, but instead can be chosen in conjunction with the

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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.

1.1 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 ﬁrst glance, we remark here that fair division between two individual agents, which is much more restrictive, has received a signiﬁcant amount of attention in the literature (e.g., [Brams and Fishburn, 2000; Brams et al., 2014; 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 EFX0. 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 wellstudied 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 ﬁve 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 ﬁxed 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.

1.2 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 in the last few years [Plaut and Roughgarden, 2018; Amanatidis et al., 2018; Biswas and Barman, 2018; Bil o 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. The group resource allocation problem with variable groups is similar to coalition formation problems [Dr eze and Greenberg, 1980; Bogomolnaia and Jackson, 2002] in the sense that there is ﬂexibility in how the agents form groups. However, in coalition formation the utilities of an agent depend on how the agents are grouped and there are no goods involved, whereas in our setting these utilities depend on how the goods are distributed and not how the agents are grouped.

2 Preliminaries

Let G = {g1, . . . , gm} 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 ﬁxed in advance, and in Section 5 that the partition is variable and can be chosen. Denote by ni the size of group i (so n = Pk i=1 ni), and aij the jth agent of group i. The agents in each group will be collectively allocated a subset of G; denote by Bi the bundle allocated to group i so that Bi Bj = for any i = j and k i=1Bi = G. A partition of the agents is called balanced if |ni nj| 1 for any i, j. Similarly, an allocation of the goods is called balanced if ||Bi| |Bj|| 1 for any i, j. Each agent aij has some nonnegative valuation uij(G ) for each set of goods G G; for convenience we write uij(g) instead of uij({g}) for a good g G. Let uij := (uij(g1), . . . , uij(gm)) be the valuation vector of agent aij for individual goods. When the identity of the agent is not important, we will drop the indices i, j from the valuation uij. We assume that the valuations are monotonic, i.e., u(G1) u(G2) for any G1 G2 G, and normalized, i.e., u( ) = 0. A valuation function u is said to be responsive if u(G {g}) u(G {g}) for any G G and any goods g, g G such that u(g) u(g). It is said to be additive if u(G ) = P

g G u(g) for any G G, and binary if it is additive and u(g) {0, 1} for all g G. Note that every

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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 a1, . . . , an and their valuations by u1, . . . , un. We are now ready to deﬁne the fairness notions that we consider in this paper.

Deﬁnition 2.1. An allocation (B1, . . . , Bn) is said to be

envy-free for agent aij if uij(Bi) uij(Bi ) for any i ;

envy-free up to any good (EFX0) for agent aij if for any i and any good g Bi , we have uij(Bi) uij(Bi \{g});

envy-free up to any positively valued good (EFX) for agent aij if for any i and any good g Bi such that uij(g) > 0, we have uij(Bi) uij(Bi \{g});

envy-free up to c goods (EFc) for agent aij, for a given positive integer c, if for any i there is a set B Bi with |B| c such that uij(Bi) uij(Bi \B).

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 ﬁnds 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 deﬁnitions hold for EFX0, EFX, and EFc.

EFX0 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 EFX0 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 EFX0. All omitted proofs can be found in the full version of this paper.2

3 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 n1 and n2. Note that any nonexistence result for (n1, n2) yields an analogous result for (n 1, n 2) with n 1 n1 and n 2 n2, since in the latter case a subset of n1 agents from the ﬁrst group and a subset of n2 agents from the second group still need to consider the allocation fair. Similarly, an existence result for (n1, n2) yields a corresponding result for (n 1, n 2) with n 1 n1 and n 2 n2. 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 sufﬁces to consider only EF1. We ﬁrst present two results that establish the existence of an EF1 allocation for the cases (n1, n2) = (5, 1) and (3, 2).

1In their paper this property is simply called EFX; we rename it to avoid confusion with the original deﬁnition of Caragiannis et al. [2016], which we refer to as EFX. 2https://arxiv.org/abs/1901.08463

While the proofs are quite lengthy and left to the full version, we give here a high-level overview. 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 ﬁnite (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. Consequently, we may assume that every agent desires an even number of goods. Theorem 3.1. For (n1, n2) = (5, 1) and binary valuations, an EF1 allocation always exists. Theorem 3.2. For (n1, n2) = (3, 2) and binary valuations, an EF1 allocation always exists. The following result completes the characterization for EF1 (and EFX) by proving that existence is not guaranteed for larger sets. Proposition 3.3. For (n1, n2) = (6, 1), (4, 2), or (3, 3) and binary valuations, an EF1 allocation does not always exist. Before addressing EFX0, 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.4. For two groups of agents with binary valuations, it is NP-complete to decide whether there exists an EF1 allocation. We now turn to the stronger notion of EFX0, and show a negative result. Proposition 3.5. For (n1, n2) = (2, 1) and binary valuations, an EFX0 allocation does not always exist. In contrast, Plaut and Roughgarden [2018] showed that an EFX0 allocation always exists if (n1, n2) = (1, 1), even for arbitrary monotonic valuations. Combined with Proposition 3.5, this yields a complete characterization of EFX0 for every class of valuations between binary and monotonic.

4 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 ﬁrst show that the existence of EF1 allocations is guaranteed for (n1, n2) = (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.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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 ﬁrst that the number of goods m is even, say m = 2t. Assume without loss of generality that the valuation u1 of the ﬁrst agent is such that u1(g1) u1(g2) u1(g2t). Construct an undirected graph H with 2t vertices corresponding to the goods, and add t red edges (g1, g2), (g3, g4), . . . , (g2t 1, g2t). Similarly, add t blue edges according to the valuation u2 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 V1 and V2. If |V1| t + 1, there is an edge among the vertices in V1, a contradiction. An analogous statement holds for V2. It follows that |V1| = |V2| = t. The partition (V1, V2) is balanced; it remains to show that it is Exact1 for both agents. By symmetry, it sufﬁces to prove this for the ﬁrst agent. By construction, each of V1 and V2 contains exactly one good from each of the pairs (g1, g2), (g3, g4), . . . , (g2t 1, g2t). For i = 1, 2, . . . , t 1, the ith best good in V1 according to the ﬁrst agent s valuation is no worse than the (i+1)st best good in V2. Responsiveness then implies that the agent values V1 at least as much as V2 when the best good in V2 is removed. This means that she regards V1 to be EF1. Similarly, she regards V2 to be EF1; hence the partition is Exact1 for her. The case where m is odd can be handled similarly; we leave the details to the full version.

Lemma 4.1 yields the following EF1 existence result.

Theorem 4.2. For (n1, n2) = (2, 1) and responsive valuations, a balanced EF1 allocation always exists.

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.3

Deﬁnition 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

3Kneser graphs have previously been used in the context of fair division and resource allocation by Suksompong [2016] and Plaut and Roughgarden [2018].

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 := minr 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 ﬁrst 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 ﬁrst 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 ﬁrst group with valuation u, and suppose for contradiction that she colors two adjacent vertices corresponding to the sets G1 and G2. Since the two vertices are adjacent, |G1 G2| 1. If G1 G2 = , since |G1| = |G2| = t it holds that G2 = G\G1. So the agent should consider one of the two allocations as EF, which is a contradiction to her coloring both vertices. Therefore |G1 G2| = 1. Let g be the common good of G1 and G2. Since the agent does not view G1 to be EF1, we have u(G1) < u(G2\{g}) = u((G\G1)\{g }), where g is the unique good that does not belong to G1 G2. Similarly, since the agent does not view G2 to be EF1, we have u(G2) < u(G1\{g}). Monotonicity then implies that

u(G1) < u(G2\{g}) u(G2) < u(G1\{g}) u(G1),

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 ﬁrst 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 deﬁnition, this vertex corresponds to a balanced allocation that is EF1 for all agents. This completes the proof for the case where m is even. The case where m is odd can be handled similarly; we leave the details to the full version.

Jafari and Alipour [2017] proved that K(2r, r, 2) 6 for all r 2, and conjectured that this bound is always tight.

Conjecture 4.5 ([Jafari and Alipour, 2017]). For any r 2, we have χ(K(2r, r, 2)) = 6.

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

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

arbitrary monotonic valuations.4 The bound of 5 cannot be improved to 6 due to Proposition 3.3. Moreover, this result would answer the EF1 existence question in the afﬁrmative 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.

Proposition 4.6. For (n1, n2) = (5, 1) and binary valuations, a balanced EF1 allocation does not always exist.

We note that our techniques in Theorem 4.4 can be extended to weaker relaxations of envy-freeness. Indeed we can similarly derive a corresponding result for EFc, for any positive integer c, if we consider graphs K(2r, r, c + 1). See the full version for the relevant discussion. 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 ﬁve agents and the other group is a singleton. We show that this is not the case for additive valuations, even when the ﬁrst group contains only two agents.

Proposition 4.7. For (n1, n2) = (2, 1) and additive valuations, an EFX allocation does not always exist.

Since an EFX allocation always exists when (n1, n2) = (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.

5 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 ﬁxed 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, ﬁnding 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.

4Jafari and Alipour [2017] also claimed that χ(K(2r, r, 2)) 4 for all r 2. In combination with our Theorem 4.4, this would imply that our Theorem 4.2 can be generalized to arbitrary monotonic valuations. However, the proof of their Theorem 5.1 contains an error when they claim that the intersection of the two k-subsets of color j has at most i 1 elements. It is only true that the intersection has at most i 1 elements in each of the two hemispheres, and therefore at most 2i 2 elements in total. It is not clear whether the proof can be recovered in light of this error.

5.1 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 o 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 n1 and n2 be nonnegative integers with n1 + n2 = n. There always exists a partition of the agents into two groups such that group i {1, 2} contains ni 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 n1 agents ﬁnd the bundle to be EF1. If this condition is met before we add any good, we give n1 of these agents an empty bundle and the remaining n2 agents the entire set G. Otherwise, denote by g the last good added to the bundle. We assign to the ﬁrst group all agents who view the bundle as EF1 before the addition of g, along with an arbitrary subset of those who ﬁnd it EF1 after g is added so that the ﬁrst group has size n1. We allocate this bundle to the ﬁrst 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 ﬁrst 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 GL and GR be the bundles to the left and right of g, respectively (not containing g). Every agent in the second group does not ﬁnd GL to be EF1, which means that she has more value for GR than GL. This implies that the agent ﬁnds GR 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 ﬁrst that both the number of agents n and the number of goods m are even, say n = 2s and m = 2t; we leave the case where either or both are odd to the full version. 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 G1 and G2, each of size t. By our assumption, any balanced assignment of the agents to G1 and G2 does not result in an EF1 allocation. On the other hand, there does exist an assignment

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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 G1. If one of these agents ﬁnds G2 to be EF1, we can reassign her to G2 and reduce the discrepancy between the two groups. Hence all of these agents do not ﬁnd G2 to be EF1. Next, we rotate the knife clockwise by one position, thereby moving a good g from G1 to G2 and another good g from G2 to G1. Call the resulting bundles H1 = (G1 {g})\{g} and H2 = (G2 {g})\{g}, respectively. We claim that the agents who do not ﬁnd G2 to be EF1 regard H1 as EF1. Denoting the valuation of an arbitrary such agent by u, we have u(H1) u(G1\{g}) > u(G2) u(G2\{g}) = u(H2\{g}), where the ﬁrst and third inequalities follow from monotonicity. So the agent indeed ﬁnds H1 to be EF1. Since more than half of the agents do not ﬁnd G2 to be EF1, more than half of the agents regard H1 as EF1. By our assumption, any balanced assignment of the agents to H1 and H2 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 H1. Additionally, more than half of the agents do not ﬁnd H2 to be EF1. If we rotate the knife clockwise repeatedly, the same argument tells us that more than half of the agents do not ﬁnd the second bundle (i.e., G2, H2, 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 ﬁrst bundle G1. However, we know from earlier that more than half of the agents ﬁnd G1 to be EF1. This yields the desired contradiction.

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.

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.

5.2 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 uj,max := maxm t=1 uj(gt) denote the maximum value of agent aj 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 n1, . . . , nk be nonnegative integers with Pk i=1 ni = n. There always exists a partition of the agents into k groups such that group i contains ni agents, along with an allocation of the goods to the k groups such that each agent aj receives utility at least 1

k uj(G) k 1

k uj,max. Theorem 5.6 generalizes a result of Suksompong [2019], which holds for individual fair division (i.e., ni = 1 for all i = 1, . . . , k). The factor k 1

k in the approximation cannot be improved even in this special case.

6 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 ﬁxed 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 graphtheoretic 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.

Acknowledgments This work is partially supported by the European Research Council (ERC) under grant number 639945 (ACCORD).

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [Aleksandrov and Walsh, 2018] Martin Aleksandrov and Toby Walsh. Group envy freeness and group Pareto efﬁciency in fair division with indivisible items. In KI, pages 57 72, 2018. [Amanatidis et al., 2018] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. Comparing approximate relaxations of envy-freeness. In IJCAI, pages 42 48, 2018. [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. [Bil o et al., 2019] Vittorio Bil o, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost envy-free allocations with connected bundles. In ITCS, pages 14:1 14:21, 2019. [Biswas and Barman, 2018] Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In IJCAI, pages 91 97, 2018. [Bogomolnaia and Jackson, 2002] Anna Bogomolnaia and Matthew O. Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38(2):201 230, 2002. [Brams and Fishburn, 2000] Steven J. Brams and Peter C. Fishburn. Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity. Social Choice and Welfare, 17(2):247 267, 2000. [Brams and Taylor, 1996] Steven J. Brams and Alan D. Taylor. A procedure for divorce settlements. Mediation Quarterly, 13(3):191 205, 1996. [Brams et al., 2014] Steven J. Brams, D. Marc Kilgour, and Christian Klamler. Two-person fair division of indivisible items: an efﬁcient, envy-free algorithm. Notices of the AMS, 61(2):130 141, 2014. [Caragiannis et al., 2016] Ioannis Caragiannis, David Kurokawa, Herv e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. In EC, pages 305 322, 2016. [Conitzer et al., 2019] Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan. Group fairness for the allocation of indivisible goods. In AAAI, 2019. Forthcoming. [Dr eze and Greenberg, 1980] Jacques H. Dr eze and Joseph Greenberg. Hedonic coalitions: optimality and stability. Econometrica, 48(4):987 1003, 1980. [Dwork et al., 2012] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In ITCS, pages 214 226, 2012. [Gal et al., 2017] Ya akov (Kobi) Gal, Moshe Mash, Ariel D. Procaccia, and Yair Zick. Which is the fairest (rent division) of them all? Journal of the ACM, 64(6):39:1 39:22, 2017.

[Ghodsi et al., 2018] Mohammad Ghodsi, Mohamad Latiﬁan, Arman Mohammadi, Sadra Moradian, and Masoud Seddighin. Rent division among groups. In COCOA, pages 577 591, 2018. [Husseinov, 2011] Farhad Husseinov. A theory of a heterogeneous divisible commodity exchange economy. Journal of Mathematical Economics, 47(1):54 59, 2011. [Jafari and Alipour, 2017] Amir Jafari and Sharareh Alipour. On the chromatic number of generalized Kneser graphs. Contributions to Discrete Mathematics, 12(2):69 76, 2017. [Kilgour and Vetschera, 2018] D. Marc Kilgour and Rudolf Vetschera. Two-player fair division of indivisible items: Comparison of algorithms. European Journal of Operational Research, 271(2):620 631, 2018. [Lipton et al., 2004] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In EC, pages 125 131, 2004. [Manurangsi and Suksompong, 2017] Pasin Manurangsi and Warut Suksompong. Asymptotic existence of fair divisions for groups. Mathematical Social Sciences, 89:100 108, 2017. [Oh et al., 2019] Hoon Oh, Ariel D. Procaccia, and Warut Suksompong. Fairly allocating many goods with few queries. In AAAI, 2019. Forthcoming. [Plaut and Roughgarden, 2018] Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. In SODA, pages 2584 2603, 2018. [Segal-Halevi and Nitzan, 2016] Erel Segal-Halevi and Shmuel Nitzan. Envy-free cake-cutting among families. Co RR, abs/1607.01517, 2016. [Segal-Halevi and Suksompong, 2018] Erel Segal-Halevi and Warut Suksompong. Democratic fair allocation of indivisible goods. In IJCAI, pages 482 488, 2018. Extended version: Co RR, abs/1709.02564. [Su, 1999] Francis Edward Su. Rental harmony: Sperner s lemma in fair division. The American Mathematical Monthly, 106(10):930 942, 1999. [Suksompong, 2016] Warut Suksompong. Assigning a small agreeable set of indivisible items to multiple players. In IJCAI, pages 489 495, 2016. [Suksompong, 2018] Warut Suksompong. Approximate maximin shares for groups of agents. Mathematical Social Sciences, 92:40 47, 2018. [Suksompong, 2019] Warut Suksompong. Fairly allocating contiguous blocks of indivisible items. Discrete Applied Mathematics, 260:227 236, 2019. [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.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)