--- title: "Almost Group Envy-free Allocation of Indivisible Goods and Chores" authors: - "Haris Aziz" - "Simon Rey" doi: "10.24963/ijcai.2020/6" url: "https://ijcai.org/proceedings/2020/6" pdf: "https://ijcai.org/proceedings/2020/0006.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "39-45" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Computational Social Choice" - "Agent-based and Multi-agent Systems: Resource Allocation" --- # Almost Group Envy-free Allocation of Indivisible Goods and Chores Haris Aziz, Simon Rey *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 39-45. DOI: [10.24963/ijcai.2020/6](https://doi.org/10.24963/ijcai.2020/6) ## Abstract We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and present stronger and relaxed versions that are especially suitable for the allocation of indivisible items. Of particular interest is a concept called group envy-freeness up to one item (GEF1). We then present a clear taxonomy of the fairness concepts. We study which fairness concepts guarantee the existence of a fair allocation under which preference domain. For two natural classes of additive utilities, we design polynomial-time algorithms to compute a GEF1 allocation. We also prove that checking whether a given allocation satisfies GEF1 is coNP-complete when there are either only goods, only chores or both. ## Full text ## 1 Introduction Fair division deals with the problem of assigning items to agents in the fairest way. Many fairness concepts have been proposed, and envy-freeness (EF) is viewed as the gold standard one. It stipulates that no agent should prefer what someone else got. However, the concept does not provide any fairness guarantees for groups of agents and also has a wellknown tension with efficiency [Caragiannis et al., 2012]. Berliant et al. [1992] introduced group envy-freeness (GEF). It generalizes envy-freeness for equal-sized groups of agents instead but with divisible items. Remarkably, it implies both envy-freeness and Pareto-optimality, the central concepts for fairness and efficiency respectively. Recently, Conitzer et al. [2019] generalized GEF for indivisible items and groups of different size by introducing group-fairness (GF). Because guaranteeing GF allocations is impossible, they proposed two relaxations of groupfairness, similar in spirit to the well-studied weakening of envy-freeness called envy-freeness up to one good (EF1). Allocations satisfying the relaxations of group-fairness can always be computed in pseudo-polynomial time. ∗Contact Author In their paper, Conitzer et al. [2019] assumed that the items allocated are "goods" for which agents have positive utility. Therefore the concepts and results do not apply to scenarios in which tasks or chores are to be allocated. Although the definition of group-fairness and group-envy freeness can be extended seamlessly in this case, their relaxations do not. In this paper, we take inspiration from the GF and GEF concepts and define several variants and relaxations of them that are well-defined for the more general setting of goods and chores. Our approach is similar to the work of Aziz et al. [2019] who introduced envy-freeness and proportionality in this context. Contributions. Our first conceptual contribution is to formalize relaxations of GEF for the case of goods and chores, called GEF1 (Section 3). We give general definitions which apply seamlessly to non-additive preference or even ordinal preferences (relation over subsets of items). We clarify the logical relations between these concepts through a clear taxonomy depicted in Figure 1. We present two key existence and algorithmic results (Sections 4 and 5). First, we present a polynomial-time algorithm that computes a GEF1 allocation for the case of identical utilities. The proof relies on connections with two-sided matching and Hall's marriage theorem. We then focus on a natural class of mixed utilities called ternary symmetric utilities and design a polynomial-time algorithm for finding GEF1 allocations. The algorithm involves network flows and makes use of several transformations of the utility functions. The results also provide additional insights on the connection between Nash social welfare and leximin-optimality . We prove that checking whether a given allocation satisfies GEF1 is coNP-complete for the cases of only goods, only chores and both (Section 6). We finally present several negative existence results on the way to extend GEF1 for groups of different size (Section 7). Related Work. Fair division is a dynamic field in economics and computer science [Aziz, 2020; Moulin, 2004; Brandt et al., 2016]. The prominent fairness concept is envyfreeness (EF) [Foley, 1967] which cannot be guaranteed with indivisible items. Several relaxations have been considered to overcome this, envy-freeness up to one good (EF1) [Budish, 2011] -which always exists [Lipton et al., 2004] and is compatible with Pareto-optimality [Caragiannis et al., 2016]- or envy-freeness up to any good (EFX). Berliant et al. [1992] generalized envy-freeness to groups of agents by introducing group envy-freeness (GEF) when items are divisible, extending the idea of coalition fairness [Schmeidler and Vind, 1972]. They proved existence of GEF allocations under monotonicity assumptions and showed the equivalence between EF and GEF. Husseinov [2011] extended it to weak group envy-freeness. Similar generalizations have been proposed with indivisible items. Todo et al. [2011] introduced envy-freeness of a group toward a group when monetary transfers between agents are allowed. Aleksandrov and Walsh [2018] presented another definition of GEF with groups of different sizes but which relies on interpersonal comparisons. Conitzer et al. [2019] defined group-fairness, a definition similar to that of Berliant et al. [1992] but considering indivisible goods and groups of different size. They also introduced two "up to one" relaxations of group-fairness for which they proved existence by using some variant of the Nash social welfare. Another line of work, similar in spirit but conceptually very different, is to consider pre-existing groups of agents taken as inputs of the procedures [Segal-Halevi and Suksompong, 2019; Kyropoulou et al., 2019; Benabbou et al., 2019] The chore division problem [Gardner, 1978], extends the classical fair division setting for items that are considered as chores for some agents. Brams and Taylor [1996] and SegalHalevi [2018] investigated the cake-cutting problem in this setting. Bogomolnaia et al. [2017] studied mixture of divisible goods and chores. Indivisible chores have also been considered [Aziz et al., 2017]. Aziz et al. [2019] presented a general framework for indivisible goods and chores with a focus on generalizing EF1 and designing algorithms for it. ## 2 Preliminaries Let N be a set of n agents and O a set of m items. Agent i ∈ N has preferences over sets of items represented by a utility function ui : 2O → R. Note that utility can be either positive or negative. For o ∈ O, we use ui(o) for ui({o}). Preferences are said to be additive if for every O ⊆ O, we have ui(O) = ∑o∈O ui(o). We assume additive preferences throughout the paper but our definitions apply to non-additive preferences and ordinal preferences as well. An item o ∈ O is a good for i if ui(o) ≥ 0 and chore for i if ui(o) ≤ 0. An allocation π = 〈π1, . . . , π|N| 〉 over O ⊆ O and N ⊆ N is a vector of sets of items πi ⊆ O for i ∈ N such that πi ∩ πj = ∅ for every distinct i, j ∈ N, and ⋃i∈N πi = O. We denote by πN = ⋃i∈N πi the set of items held by agents in N ⊆ N. Let π+ i = {o ∈ πi | ui(πi) - ui(πi\{o}) > 0} and πi = {o ∈ πi | ui(πi) - ui(πi\{o}) < 0} respectively be the sets of strict goods and strict chores in πi. We write Π(O,N) for the set of all the allocations over O ⊆ O and N ⊆ N . A triplet I = 〈N , O, (ui)i∈N 〉 is an instance and I, I +, I - are respectively the sets of all instances, those with only goods and those with only chores. Let us now introduce some properties of an allocation. We say that an allocation π′ Pareto-dominates another one π if all agents are better off in π′ and one is strictly better off: ∀i ∈ N, ui(π′i ) ≥ ui(πi) and ∃i ∈ N, ui(π′i ) > ui(πi). If no other allocation Pareto-dominates π, it is said to be Pareto-optimal. The Nash social welfare of π is defined as ∏i∈N |ui(πi)|. Next, we introduce envy-freeness and its relaxations with goods and chores [Aziz et al., 2019]. Definition 1 (Envy-freeness). An allocation π ∈ Π(O, N) is envy-free if for every i, j ∈ N, ui(πi) ≥ ui(πj). It is well known that for some instances, no allocation is envy-free. Two different relaxation of envy-freeness can then be considered. We say that an allocation π is envy-free up to one item (EF1) if for every i, j ∈ N, we have: Moreover, an allocation π ∈ Π(O,N) is envy-free up to any item (EFX) if for every i, j ∈ N, we have: ## 3 Fairness for Groups with Goods and Chores We now present our first contribution: group envy-freeness (GEF) and its relaxations with goods and chores. Definition 2 (GEF). An allocation π ∈ Π(O,N) is group envy-free (GEF) if for every non-empty groups S, T ⊆ N, |S| = |T|, there is no reallocation π′ ∈ Π(πT , S), such that for every i ∈ S, ui (π′i ) ≥ ui(πi), with one strict inequality. In words, GEF states that there is no reallocation of πT to the agents in S that is a Pareto improvement for them. Note that group-fairness (GF) 1 [Conitzer et al., 2019] is equivalent to GEF if equal sized groups of agents are compared. The name group envy-freeness is fromBerliant et al. [1992]. In the same spirit of EF1 and EFX, we introduce "up to one" and "up to any" relaxations for group envy-freeness. Definition 3 (GEF1). An allocation π ∈ Π(O,N) is GEF up to one item (GEF1) if for every non-empty groups S, T ⊆ N, |S| = |T|, every reallocation π′ ∈ Π(πT , S), and every agent i ∈ S, there exists Oi ⊆ πi ∪ π′+ i , |Oi| ≤ 1, such that 〈ui(π′i \Oi)〉i∈S does not Pareto-dominate 〈ui(πi\Oi)〉i∈S . Definition 4 (GEFX). An allocation π ∈ Π(O, N ) is GEF up to any item (GEFX) if for every non-empty groups S, T ⊆ N , |S| = |T|, for every reallocation π′ ∈ Π(πT , S), for every agent i ∈ S, and for every item o ∈ πi ∪ π′+ i , 〈ui(π′i \{o})〉i∈S does not Pareto-dominate 〈ui(πi\{o})〉i∈S . Observe that for positive additive utility functions, GEF1 is equivalent to group fairness up to one good after (GF1A) 2 [Conitzer et al., 2019] restricted to same sized groups, and with the additional conditions for GEF1 that agents should get non-zero utility after reallocation. Conitzer et al. [2019] also proposed group fairness up to one good before (GF1B) 3 1π is GF if for every non-empty S, T ⊆ N, π′ ∈ Π(πT , S), 〈|S|/|T |ui(π′i)〉i∈S does not Pareto-dominate 〈ui(πi)〉i∈S . 2π is GF1A if for every non-empty S, T ⊆ N, π′ ∈ Π(πT , S) s.t. ui(π′i) > 0 for all i ∈ S, there exists oi ∈ π′i for each i ∈ S s.t. 〈|S|/|T |(ui(π′i)〉i∈S does not Pareto-dominate 〈ui(πi ∪ {oi})〉i∈S . 3π is GF1B if for every non-empty S, T ⊆ N s.t. there exists π′′ ∈ Π(πT , S) with ui(π′′ i ) > 0 for all i ∈ S, there exists oj ∈ πj for each j ∈ T with πj ̸= ∅ s.t. for every π′ ∈ Π(πt\ ⋃j∈T oj, S), 〈|S|/|T |(ui(π′i)〉i∈S does not Pareto-dominate 〈ui(πi ∪ {oi})〉i∈S . Figure 1: Logical relationship between fairness criteria. Allocations satisfying concepts in dotted (resp. plain) are not (resp. are) guaranteed to exist. No existence result is known for concepts in dashed. ![Image](https://ijcai.org/proceedings/2020/fulltext/6/image_000000_263c4d4efafaf8b45d4eb1eff5ff7b5f9e5fcc527c7231aeb163b287b783f8b7.png) ## Algorithm 1 The Egal-Sequential Algorithm ``` Input: I = 〈N, O, (ui)i∈N )〉 with identical utility function u Output: π ∈ Π(O, N) an allocation satisfying EFX and GEF1 Set π to the empty allocation Order items o1, . . . , om in O in decreasing order of |u(o)| for j = 1 to m do if u(oj) ≥ 0 then Choose i∗ ∈ argmini∈N u(πi) else Choose i∗ ∈ argmaxi∈N u(πi) Give oj to i∗ : πi∗ ← πi∗ ∪ {oj} return π ``` which is no longer relevant when there are chores since removing items cannot be done "before". GEF1 can be seen as an argument in favour of the GF1A. It is however only reasonable when agents have positive utilities. GEF1 with groups of different size is discussed in Section 7. To conclude this section, we present in Figure 1 a taxonomy of the different criteria discussed above. ## 4 The Egal-Sequential Algorithm for Identical Utilities In this section, we present the Egal-Sequential Algorithm that returns a GEF1 allocation when preferences are identical. Identical preferences constitute an important and natural class of preferences especially if the item's values are objective or publicly known. The algorithm allocates sequentially the items in decreasing order of absolute utility. The item to be allocated is given to the worse off agent if it is a good and to the better off agent otherwise. This is a natural extension of a standard approach for achieving EFX when there are only goods. We prove in two steps that this ensures GEF1. We first show that the Egal-Sequential Algorithm returns an EFX allocation and then that every EFX allocation is also GEF1 when preferences are identical, that is, when there exists a common utility function u such that for every i ∈ N , ui = u. Lemma 1. For identical utilities, the Egal-Sequential Algorithm returns an EFX allocation in O(max{m log m, mn}). Lemma 2. Under identical utilities, any allocation satisfying EFX also satisfies GEF1. Proof. Consider an EFX allocation π that is not GEF1. Since preferences are identical, assume w.l.o.g. that no item gives zero utility. If such items exist, they can be allocated to any agent without changing anything. As π is not GEF1, there exist S ⊆ N, T ⊆ N, |S| = |T| and π′ ∈ Π(πT , S) such that ∀i ∈ S, ∀o ∈ πi ∪ π′+ i , u(π′i \{o}) ≥ u(πi\{o}) with one strict inequality. For i ∈ S, we introduce si defined as: Violating GEF1 then implies: ∀i ∈ S, u(π′i ) - u(πi) ≥ si with one inequality being strict. The 0 component in the definition of si is meant to tackle the case when πi = π′+ i = ∅, in which case we should have πi = ∅ to get a GEF1 violation, hence we have u(πi) = u(π′i ) and si = 0 is a suitable bound. By summing the inequalities of the violation of GEF1 over i ∈ S, we obtain ∑i∈S u(π′i ) - ∑i∈S u(πi) > ∑i∈S si. Since utilities are identical and additive this implies: Moreover, as π is EFX, we have ∀i, j ∈ N, ∀o ∈ πi ∪ π+ j , u(πi\{o}) ≥ u(πj\{o}). For i, j ∈ N, we introduce si,j defined by: The 0 component is once again here to take care of the case when πi ∪ π+ j = ∅. We have thus: Our goal is now to sum up inequalities (2) to obtain a contradiction with (1). We are looking for a set of pairs (i, j), called M ∗ , such that each i ∈ S and each j ∈ T appear once and only once, and such that ∑(i,j)∈M∗ ≤ ∑i∈S si. To do so, we find a suitable matching in a bipartite graph. Let us consider the bipartite graph G = 〈S ∪ T, E〉 where nodes represent agents in S and in T . There is an edge (i, j) ∈ E between agents i ∈ S and j ∈ T if and only if π′+ i ∩πj ̸= ∅, that is, i receives some of j's goods in π′ . We consider a partition S+ ∪ S- of S where: For X ⊆ S, we write N(X) its neighbourhood in the graph G: N(X) = {j ∈ T | ∃i ∈ X, (i, j) ∈ E}. A symmetric definition holds for N(Y ) where Y ⊆ T . We claim that there always exists a matching M ⊆ S × T in G that matches all the agents in S+. Suppose for the sake of contradiction that such M does not exist. From Hall's theorem [Hall, 1935], there must exist X ⊆ S+ and Y ⊆ T such that Y = N(X) and |Y | < |X|. Let us assume that X is a smallest Hall's violater in G, and consider M ′ ⊆ X × Y a maximum matching between agents in X and in Y . By invoking Hall's theorem, we can then show in the following that M ′ always matches all the agents in Y . We now turn back to showing that M matches all the agents in S+. As M ′ matches all the agents in Y and u is additive, we have ∑(i,j)∈M′ u(πj) = u(πY ). Hence, by summing inequalities (2) for (i, j) ∈ M ′ , we obtain: Moreover summing inequalities yielded by the violation of GEF1 over i ∈ S in a similar manner as inequalities (1) brings u(πY )- ∑i∈X si ≥ u(πX). Together with (3), this leads to: Observe that for any pair of agents (i, j) such that there is an edge between i and j in G, we have: As |M ′ | < |X|, it is clear that ∑(i,j)∈M′ u(πi) < u(πX). Overall, we have: which contradicts (4). Therefore, no Hall's violator exists and the matching M does match all the agents in S+. Next we show that the existence of this matching M leads to a contradiction on the fact that π is not GEF1. We extend the matching M to match all the agents in S by arbitrarily pairing each agent i ∈ S- with an unmatched agent in T . Let the extended matching be called M ∗ . Observe that for any new pair of agents (i, k) ∈ M ∗ \M, we have i ∈ S-, that is πi ̸= ∅. Hence, for any agent j ∈ T, we have: By summing (2) over (i, j) ∈ M ∗ we obtain ∑(i,j)∈M∗ si,j ≥ u(πT ) - u(πS). From (5) and (6) we get that ∑(i,j)∈M∗ si,j ≤ ∑i∈S si, hence summing (2) over (i, j) ∈ M ∗ leads to a contradiction with (1). We have thus proved that π satisfies both EFX and GEF1. A direct consequence of these two lemmas is that the EgalSequential Algorithm computes GEF1 allocations. Theorem 1. For identical utilities, an allocation satisfying GEF1 always exists and can be computed in O(max{mlogm,mn}) time by the Egal-Sequential Algorithm. Conitzer et al. [2019] showed that for identical preferences their relaxation of group-fairness is implied by EFX. We extend their result in different ways. Firstly, our result applies in the case of mixed utilities. Secondly, we provide a linear time algorithm to compute GEF1 allocation with identical preferences. Finally, our proof does not involve the Nash social welfare which is not a suitable solution concept with chores. 4 4 When considering only chores, either maximizing or minimizing the absolute Nash social welfare does not imply EF1. ## 5 The Ternary FlowAlgorithm In this section, we focus on another restriction of the preferences, namely ternary symmetric preferences. We say that agent ai has ternary symmetric preferences if her preferences are additive and the utilities of the singletons are taken from the set {-αi, 0, αi} for a given αi > 0. We provide an algorithm that computes GEF1 allocations for ternary symmetric preferences. We do so by proving that any leximin-optimal allocation is also GEF1 and by providing an algorithm returning a leximin-optimal allocation in polynomial time. Similar links between leximin-optimality and envy-freeness concepts have been observed by Plaut and Roughgarden [2020] for the case of goods. We first provide a characterization of Pareto-optimality for ternary symmetric utilities. Lemma 3. Let I = 〈N,O, (ui)i∈N〉 be an instance with ternary symmetric utility functions. An allocation π ∈ Π(N, O) is Pareto-optimal iff for every item o ∈ O we have: For a profile of ternary symmetric preferences (ui)i∈N , we introduce the normalized profile(uNorm i )i∈N that corresponds to (ui)i∈N but such that every αi has been set to 1. For a normalized profile, every singleton has utility in {-1, 0, 1}. This preference domain models statements such as "I like", "I am indifferent" and "I do not like". It is close to the idea of approval and disapproval voting [Brams and Fishburn, 1978; Felsenthal, 1989]. In fair division, it is also known as dichotomous preferences [Bogomolnaia et al., 2005]. Next we introduce leximin optimality. For an allocation π we denote by ⃗u(π) ∈ Rn the vector of the utilities in π sorted in increasing order. For two vectors ⃗u,⃗v ∈ Rk , we say that ⃗u leximin-dominates ⃗v, written ⃗u ≻lex ⃗v, if there exists an i ≤ k such that ⃗uj = ⃗vj, ∀j < i, and ⃗ui > ⃗vi. Finally, π is leximin-optimal if there is no π′ such that ⃗u(π′ ) ≻lex ⃗u(π). Our algorithm uses the Nash Flow Algorithm [Darmann and Schauer, 2015]. It computes in polynomial time an allocation maximizing the Nash social welfare for binary preferences, i.e. the singletons' utilities are in {0, 1}, by finding a minimum integer flow in a specific cost flow network. The algorithm is not described here and we refer the interested reader to the paper. We first extend this result by showing that it returns leximin-optimal allocations. Lemma 4. Let I = 〈N,O, (ui)i∈N〉 ∈ I + be an instance with only goods and binary preferences. An allocation π is leximin-optimal iff it corresponds to a minimum cost integer flow in the network defined by the Nash Flow Algorithm. This equivalence implies that any leximin-optimal allocation also maximizes the Nash social welfare. It also implies that any leximin-optimal allocation is equivalent to the Maximal Nash Welfare (MNW) solution of Caragiannis et al. [2016] in which the number of agent with strictly positive utility is maximized and then for those agents, their Nash social welfare is maximized. ## Algorithm 2 The Ternary Flow Algorithm ``` Input: I = 〈N , O, (ui)i∈N )〉 with ternary symmetric utilities Output: π ∈ Π(O, N) a GEF1 allocation Set O+ = {o ∈ O : maxi∈N ui(o) > 0}. Set O0 = {o ∈ O : maxi∈N ui(o) = 0}. Set O- = {o ∈ O : maxi∈N ui(o) < 0}. Consider the utility functions (u′i)i∈N such that ∀i ∈ N, ∀o ∈ O+, we have u′i(o) = { 1 if uNorm i (o) = 1, 0 otherwise Let π be the Nash Flow Algorithm's result on 〈N , O+, (u′i)i∈N 〉. for o ∈ O- do Allocate o to i∗ ∈ argmaxi∈N uNorm i (πi). for o ∈ O0 do Allocate o to i∗ ∈ argmini∈N,uNorm i (o)=0 uNorm i (πi). return π ``` Corollary 1. For binary preferences, any leximin-optimal allocation π maximizes the Nash social welfare and a leximinoptimal allocation is equivalent to the MNW solution of Caragiannis et al. [2016]. Using the Nash flow algorithm, we propose the Ternary Flow Algorithm (Algorithm 2). It computes a leximinoptimal allocation on the normalized utilities which is a GEF1 allocation w.r.t. the original preferences. Note that thanks to Corollary 1, any algorithm maximizing the Nash welfare (or, equivalently, being leximin-opimal) for binary preferences can be used instead of the Nash flow algorithm. Lemma 5. For ternary symmetric preferences, the Ternary Flow Algorithm returns allocations that are leximin-optimal for the normalized preferences. Sketch of the proof. From Lemma 4 we know that the Nash Flow Algorithm's outcome is leximin-optimal. We claim that allocating the chores in o ∈ O- to the best off agent maintains leximin-optimality. The same hold for giving items in O0 to agents who value them 0. Lemma 6. If the preferences are normalised ternary symmetric, any leximin-optimal allocation also satisfies GEF1. Proof. In the followingwe consider a leximin-optimal allocation π. We can show that the agents' utility can not be too different because of leximin-optimality and that if one agent has negative utility, then all agents' utility is at most one more. The proofs of these two claims are omitted for space reason. For the sake of contradiction, assume that π is not GEF1. There exist then S, T ⊆ N , and π′ ∈ Π(πT , S) such that ∀i ∈ S, ∀o ∈ πi ∪ π′+ i , u(π′i \{o}) ≥ u(πi\{o}) with one strict inequality. Suppose w.l.o.g. that the utilities of the agents in S (resp. T), written s1, . . . , s|S| (resp. t1, . . . , t|S|), are ordered increasingly. From Lemma 3 we know that for every agent j ∈ T and i ∈ S, ui(πj) ≤ uj(πj). Hence, tj is an upper bound on the utility i can receive from j. To get a GEF1 violation, a reallocation of the items in πT should give utility at least si + 1 to every agent i ∈ S with one agent receiving strictly more. Let us denote by j ∗ ∈ T the index of the first tj such that tj > sj + 1. From Claim 2, it cannot be the case that sj ∗ < 0. From Claim 1, we know that if sj ∗ ≥ 0, tj ∗ does not have any item considered as goods for the agent i∗ , corresponding to sj ∗. Since utilities are ordered increasingly, it also holds for every j > j ∗ . Hence i∗ can only receive goods from agents j < j ∗ . However, for every j < j ∗ , we have sj = tj + 1. These agents can thus not provide enough goods to all agents i ≤ i∗ to get GEF1 violation. This proves that π is GEF1. From Lemma 5 and 6, we derive the statement for GEF1. Theorem 2. Let I = 〈N,O, (ui)i∈N〉 ∈ I be an instance with ternary symmetric utility functions. The Ternary Flow Algorithm computes in polynomial time a GEF1 allocation. ## 6 Testing GEF1 is coNP-complete We prove in this section that testing GEF1 is coNP-complete when there are only goods, only chores and both of them. The decision problem IS-GEF1 takes an instance I ∈ I and an allocation π as input and answers the question whether π is GEF1. We use IS-GEF1+ and IS-GEF1- to refer to the same decision problem when there are respectively only goods (I ∈ I +) and only chores (I ∈ I -). Theorem 3. The problems IS-GEF1, IS-GEF1+ and ISGEF1- are strongly coNP-complete. Proof. We only present the reduction for the IS-GEF1problem. By reducing the 3-PARTITION problem [Garey and Johnson, 1975], we show that checking if π violates GEF1 when there are only chores is strongly NP-complete. Given a multi-set of 3m numbers X = {x1, . . . , x3m} such that: ∀x ∈ X, 1/4 < x < 1/2 and ∑x∈X x = m, the 3PARTITION answers whether there is a partition (Xi)i∈J1,mK of X such that ∀i, ∑x∈Xi = 1. Let X = {x1, . . . , x3m} be an instance of the 3PARTITION problem. We present the instance (I, π) of the ISGEF1- problem. The set of chores is O = {g1, . . . , gm} ∪ {h1, . . . , hm}∪{l1, . . . , l3m}∪{o1, . . . , o2m} and the set of agents N = {a1, . . . , am} ∪ {b1, . . . , bm}. The utilities of the singletons are indicated in the table above where ϵ > 0 is a constant small enough, M is a constant greater than m+ 1 and the xi are ordered in a decreasing order. The initial allocation π ∈ Π(O,N), given as a entry of the IS-GEF1- problem and represented by the boxed items in the previous table, is defined as follow: We can show (omitted) that if there is a GEF1 violation, then it should be the case that S = T = N. We now prove that for S = T = N, there exists a reallocation π′ that is a GEF1 violation iff there exists a partition (Xi)i∈J1,mK of X satisfying the conditions of the 3PARTITION problem. | | g1 | . . . | gm | h1 | . . . | hm | l1 | l2 | l3 | . . . | l3m-2 | l3m-1 | l3m | o1 | . . . | om | om+1 | . . . | o2m | |-------|---------|---------|-------------|-------|---------|-------|------|------|------|---------|---------|---------|-------|------|---------|------|--------|---------|-------| | a1 | -m- ϵ | -M | -M | -1- ϵ | -M | 0 | -x1 | -x2 | -x3 | · · · | -x3m-2 | -x3m-1 | -x3m | 0 | -M | -M | -M | -M | -M | | . . . | -M | . . . | -M | -M | . . . | -M | -x1 | -x2 | -x3 | · · · | -x3m-2 | -x3m-1 | -x3m | -M | . . . | -M | -M | -M | -M | | am | -M | -M | -m- ϵ | -M | -M | -1- ϵ | -x1 | -x2 | -x3 | · · · | -x3m-2 | -x3m-1 | -x3m | -M | -M | 0 | -M | -M | -M | | b1 | -x2 -x3 | -M | -M | -M | -M | -M | -x1 | -x2 | -x3 | -M | -M | -M | -M | -M | -M | -M | 0 | -M | -M | | . . . | -M | . . . | -M | -M | -M | -M | -M | -M | -M | . . . | -M | -M | -M | -M | -M | -M | -M | . . . | -M | | bm | -M | -M | -x3m-1 -x3m | -M | -M | -M | -M | -M | -M | -M | -x3m-2 | -x3m-1 | -x3m | -M | -M | -M | -M | -M | 0 | Note that each gi chore should be allocated to bi in π′ , hence all "l" chores should be divided among "a" agents. "h" chores are allocated to "a" agents receiving 0 utility for it, similar reallocation is done for "o" chores. Hence one gets a violation iff it is possible to divide the "l" items into m parts of sum smaller than 1 + ϵ, that is of sum 1. For a suitable ϵ this is equivalent to the existence of a partition of X satisfying the conditions of the 3-PARTITION problem. This reduction is done in polynomial-time which concludes the proof. In this proof, the only possible violations of GEF1 are such that S = T = N. Hence, checking whether an allocation satisfies the Pareto-optimality relaxation derived from GEF1, is also coNP-complete. ## 7 GEF with Groups of Different Sizes In this section, we investigate the issue of extending GEF1 to groups of different size. We first introduce strong-GEF1. Definition 5 (s-GEF1). An allocation π is strongly-GEF1 (sGEF1) if for every non-empty groups S, T ⊆ N, every reallocation π′ ∈ Π(πT , S), and every agent i ∈ S, there exists Oi ⊆ πi ∪π′+ i with |Oi| ≤ 1, such that 〈 |S| |T | ui(π′i \Oi)〉i∈S Strong-GEF1 is the most natural way of extending GEF1 to groups of different sizes, however s-GEF1 allocations are not guaranteed to exist even when there are only goods. Consider an instance with three goods, o1, o2 and o3 and three agents a1, a2 and a3 with identical preferences: u(o1) = u(o2) = 1 and u(o3) = ϵ for 0 < ϵ < 1/3. First, note first that to be EF1, and thus potentially s-GEF1, an allocation should gives one good to each agent as otherwise there would be an envious agent. Consider then w.l.o.g. π in which ai gets oi. In this case, it can be checked that S = {a3}, T = {a1, a2, a3}, and π′ = 〈{o1, o2, o3}〉 is a witness of a s-GEF1 violation. Hence, no allocation can satisfy s-GEF1 in this instance. This negative result has been observed by Conitzer et al. [2019] (see their discussion on page 1856) and motivated them to change the definition as follow to obtain positive existence results. In the following definition, note the way the set Oi is added instead of being removed, compared to s-GEF1. Definition 6 (s-GEF1'). An allocation π is strongly-GEF1' (s-GEF1') if for every non-empty groups S, T ⊆ N , every reallocation π′ ∈ Π (πT , S), and every agent i ∈ S, there exists Oi ⊆ πi ∪π′+ i with |Oi| ≤ 1, such that 〈 |S| |T | ui(π′i ∪ Oi)〉i∈S does not Pareto-dominate 〈ui(πi ∪ Oi)〉i∈S . This definition is conceptually very different from that of s-GEF1 or EF1. Indeed, the underlying assumption is made that some items can be "duplicated" so that envy can be eliminated by giving these extra items. This assumption is not always reasonable and is not required by EF1 or s-GEF1. Moreover, just as EF, GEF1 is an ordinal concept in the sense that it applies seamlessly to ordinal preferences. Comparing groups of unequal sizes requires appropriate scaling of utilities which does not seem appropriate if the utilities are not additive and especially so if the preference relation is ordinal. Even though many papers in fair division focus on cardinal utilities, the most popular concepts such as envyfreeness and Pareto optimality are more universal. Although these drawbacks seem quite reasonable, one can still look for positive result with s-GEF1'. However, in the presence of chores, this is no longer possible. Consider three agents (a1, a2, a3) and three chores (o1, o2, o3) where every agent has utility -1 for o1 and o2 and -3 for o3. It is clear that for an allocation to be EF1, and thus s-GEF1', no agent should receive more than one chore. W.l.o.g., consider then π in which ai gets oi. We claim that S = {a3}, T = {a1, a2}, and π′ = 〈{o1, o2}〉 is a witness of a s-GEF1' violation and let the computations to the reader. This implies that no allocation is s-GEF1' in this instance. Overall, none of the natural generalizations of GEF1 are suitable for comparing groups of different size with chores. It can still be argued that comparisons between same-sized groups implicitly captures comparisons between different sized groups: for k ∈ N, one can compare the best subgroup in S of size k with the worst subgroup of T of size k. ## 8 Conclusion Inspired by the group envy-freeness concept, we formalized several relaxations for indivisible goods and chores. The concepts have both fairness and efficiency flavours. Our definitions are general and work well for ordinal and cardinal preferences involving goods and chores. We clarified the relation of GEF1 with other concepts and presented several positive computational results. In the paper, we focussed on additive utilities. For monotonic utility functions, even for two agents a GEF1 allocation is not guaranteed to exist. Several interesting questions arise as a result of our study. The main question left open is the existence of GEF1 allocations when there are goods and chores for additive preferences. The question has been answered positively in the case of goods. However the proof involves the Nash social welfare which cannot be used with chores (it, for instance, no longer implies EF1 when there are chores). Moreover, it is not clear how one should extend GEF1 for groups of different size in our context. Considering that protection of groups is one of the central concerns in new research on algorithmic fairness, we envisage GEF1 and its variants to spur further interesting work in the area. ## References 1. [Aleksandrov and Walsh, 2018] M. Aleksandrov and T. Walsh. Group envy freeness and group Pareto effi- ciency in fair division with indivisible items. In Proc. of 41st KI Conference, pages 57-72, 2018. 2. [Aziz et al., 2017] H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh. Algorithms for max-min share fair allocation of indivisible chores. In Proc. of 31st AAAI Conference, pages 335-341, 2017. 3. [Aziz et al., 2019] H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh. Fair allocation of indivisible goods and chores. In Proc. of 28th IJCAI, pages 53-59, 2019. 4. [Aziz, 2020] H. Aziz. Developments in multi-agent fair al- location. In Proc. of 34th AAAI Conference, 2020. 5. [Benabbou et al., 2019] N. Benabbou, M. Chakraborty, E. Elkind, and Y. Zick. Fairness towards groups of agents in the allocation of indivisible items. In Proc. of 28th IJ- CAI, pages 95-101, 2019. 6. [Berliant et al., 1992] M. Berliant, W. Thomson, and K. Dunz. On the fair division of a heterogeneous commodity. Journal of Mathematical Economics, 21(3):201-216, 1992. 7. [Bogomolnaia et al., 2005] A. Bogomolnaia, H. Moulin, and R. Stong. Collective choice under dichotomous prefer- ences. Journal of Economic Theory, 122(2):165-184, 2005. 8. [Bogomolnaia et al., 2017] A. Bogomolnaia, H. Moulin, F. Sandomirskiy, and E. Yanovskaya. Competitive divi- sion of a mixed manna. Econometrica, 85(6):1847-1871, 2017. 9. [Brams and Fishburn, 1978] S. J. Brams and P. C. Fishburn. Approval voting. American Political Science Review, 72(3):831-847, 1978. 10. [Brams and Taylor, 1996] S. J. Brams and A. D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cam- bridge University Press, 1996. 11. [Brandt et al., 2016] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia. Handbook of computational social choice. Cambridge University Press, 2016. 12. [Budish, 2011] E. Budish. The combinatorial assign- ment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. 13. [Caragiannis et al., 2012] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. The efficiency of fair division. Theory of Computing Systems, 50(4):589- 610, 2012. 14. [Caragiannis et al., 2016] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The un- reasonable fairness of maximum nash welfare. In Proc. of 17th ACM-EC Conference, pages 1-32, 2016. 15. [Conitzer et al., 2019] V. Conitzer, R. Freeman, N. Shah, and J. W. Vaughan. Group fairness for the allocation of indi- visible goods. In Proc. of 33rd AAAI Conference, pages 1853-1860, 2019. 16. [Darmann and Schauer, 2015] A. Darmann and J. Schauer. Maximizing nash product social welfare in allocating indi- visible goods. European Journal of Operational Research, 247(2):548-559, 2015. 17. [Felsenthal, 1989] D. S. Felsenthal. On combining approval with disapproval voting. Behavioral Science, 34(1):53-60, 1989. 18. [Foley, 1967] D. K. Foley. Resource allocation and the pub- lic sector. In Yale Economics Essays, volume 7. 1967. 19. [Gardner, 1978] M. Gardner. Aha! Aha! insight. Scientific American, 1978. 20. [Garey and Johnson, 1975] M. R. Garey and D. S. John- son. Complexity results for multiprocessor scheduling un- der resource constraints. SIAM Journal on Computing, 4(4):397-411, 1975. 21. [Hall, 1935] P. Hall. On representatives of subsets. Journal of the London Mathematical Society, 1(1):26-30, 1935. 22. [Husseinov, 2011] F. Husseinov. A theory of a heteroge- neous divisible commodity exchange economy. Journal of Mathematical Economics, 47(1):54-59, 2011. 23. [Kyropoulou et al., 2019] M. Kyropoulou, W. Suksompong, and A. A. Voudouris. Almost envy-freeness in group re- source allocation. In Proc. of 28th IJCAI, pages 400-406, 2019. 24. [Lipton et al., 2004] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indi- visible goods. In Proc. of 5th ACM-EC Conference, pages 125-131, 2004. 25. [Moulin, 2004] H. Moulin. Fair division and collective wel- fare. MIT press, 2004. 26. [Plaut and Roughgarden, 2020] B. Plaut and T. Roughgar- den. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2):1039- 1068, 2020. 27. [Schmeidler and Vind, 1972] D. Schmeidler and K. Vind. Fair net trades. Econometrica, 40(4):637-642, 1972. 28. [Segal-Halevi and Suksompong, 2019] E. Segal-Halevi and W. Suksompong. Democratic fair allocation of indivisible goods. Artificial Intelligence, 277:103-167, 2019. 29. [Segal-Halevi, 2018] E. Segal-Halevi. Fairly dividing a cake after some parts were burnt in the oven. In Proc. of 17th AAMAS Conference, pages 1276-1284, 2018. 30. [Todo et al., 2011] T. Todo, R. Li, X. Hu, T. Mouri, A. Iwasaki, and M. Yokoo. Generalizing envy-freeness toward group of agents. In Proc. of 22nd IJCAI, pages 386-392, 2011.