# groupwise_maximin_fair_allocation_of_indivisible_goods__bc8a14ba.pdf

Groupwise Maximin Fair Allocation of Indivisible Goods

Siddharth Barman Indian Institute of Science barman@iisc.ac.in

Arpita Biswas Indian Institute of Science arpitab@iisc.ac.in

Sanath Kumar Krishnamurthy Chennai Mathematical Institute sanathkumar9@cmi.ac.in

Yadati Narahari Indian Institute of Science narahari@iisc.ac.in

We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin share is defined as the minimum utility that an agent can guarantee for herself when asked to partition the set of goods into n bundles such that the remaining (n 1) agents pick their bundles adversarially. An allocation is deemed to be fair if every agent gets a bundle whose valuation is at least her maximin share. Even though maximin shares provide a natural benchmark for fairness, it has its own drawbacks and, in particular, it is not sufficient to rule out unsatisfactory allocations. Motivated by these considerations, in this work we define a stronger notion of fairness, called groupwise maximin share guarantee (GMMS). In GMMS, we require that the maximin share guarantee is achieved not just with respect to the grand bundle, but also among all the subgroups of agents. Hence, this solution concept strengthens MMS and provides an ex-post fairness guarantee. We show that in specific settings, GMMS allocations always exist. We also establish the existence of approximate GMMS allocations under additive valuations, and develop a polynomial-time algorithm to find such allocations. Moreover, we establish a scale of fairness wherein we show that GMMS implies approximate envy freeness. Finally, we empirically demonstrate the existence of GMMS allocations in a large set of randomly generated instances. For the same set of instances, we additionally show that our algorithm achieves an approximation factor better than the established, worst-case bound.

1 Introduction

In recent years, the topic of fair division of indivisible goods has received significant attention in the computer science, mathematics, and economics communities, see, for instance, Chapter 12 in (Brandt et al. 2016). A central motivation behind this thread of research is the fact that classical notions of fairness such as envy freeness (EF)1 and proportional-

Copyright 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 1An allocation is called envy free if every agent values her bundle at least as much she values any other agent s bundle (Foley 1967; Varian 1974; Stromquist 1980).

ity2 which were developed for divisible goods (that can be fractionally allocated), do not translate well to the indivisible case. For instance, if there is a single indivisible good and two agents, then no allocation can guarantee EF or proportionality. But, given that a number of real-world settings (such as budgeted course allocations (Budish 2011), division of inheritance, and partitioning resources in a cloud computing environment) entail allocation of discrete/indivisible goods, it is essential to define and study solution concepts which are applicable for a fair division of indivisible goods. Classically, the applicability of solution concepts is studied via existence results. Understanding if and when a solution concept is guaranteed to exist is of fundamental importance in microeconomics and other related fields. Such existence results have been notably complemented by research in algorithmic game theory and artificial intelligence that has focused on computational issues surrounding the underlying solution concepts. Broadly, our results contribute to these key themes by establishing both existential and algorithmic results for a new notion of fairness. In the context of fair division, the focus on developing efficient algorithms is motivated, in part, by websites such as Spliddit3 (Goldman and Procaccia 2015) and Adjusted Winner4 (Brams and King 2005), which offer fair solutions for dividing goods. Spliddit has attracted more than fifty thousand users and, among other services, it computes allocations which are fair with respect to the standard notions of fairness. One of the solution concepts considered by Spliddit is the maximin share guarantee (MMS). The MMS solution concept was defined in the notable work of (Budish 2011), and it deems an allocation to be fair if each agent gets a bundle of value greater than or equal to an agent-specific threshold, called the maximin share of the agent. Specifically, the maximin share of an agent corresponds to the maximum value that the agent can attain for herself if she is hypothetically asked to partition the set of goods into n bundles and, then, the remaining (n 1) agents pick their bundles adversarially. Hence, a risk-averse agent i would partition the goods (into n bundles) such that value of

2An allocation, among n agents, is called proportionally fair if every agent s value for her share is at least 1/n times the total value of all the goods (Steinhaus 1948). 3www.spliddit.org 4http://www.nyu.edu/projects/adjustedwinner/

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

the least desirable bundle (according to her) in the partition is maximized. The value of the least desirable bundle in such a partition is called the maximin share of agent i. This definition can be interpreted as a natural generalization of the classical cut-and-choose protocol. Although maximin shares provide a natural benchmark to define fairness, this solution concept has its own drawbacks. In particular, MMS is not sufficient to rule out unsatisfactory allocations; see Section 3 for an example. Moreover, different MMS allocations can be drastically different in terms of, say, the social welfare of the agents. Motivated by these considerations, we define a strictly stronger notion of fairness, called groupwise maximin share guarantee (GMMS). Intuitively, GMMS provides an expost fairness guarantee: it ensures that, even after the allocation has been made, the maximin share guarantee is achieved not just with respect to the grand bundle of goods, but also among all the subgroups of agents J [n]. Specifically, we say that an allocation is GMMS if, for all groups J [n] and agents i J, the value of i s bundle in the allocation is no less than the maximin share of i restricted to J. That is, if the agent i were to repeat the thought experiment (of dividing all the goods allocated to the agents in group J, so that the other |J| 1 agents pick their bundles adversarially) to calculate her maximin share restricted to J, then the value of her bundle is at least this threshold. This definition directly ensures that groupwise maximin share guarantee is a stronger solution concept: GMMS implies MMS. In Section 3, we show that GMMS can, in fact, be arbitrarily better than an allocation that just satisfies MMS. GMMS also strictly generalizes pairwise maximin share guarantee (PMMS), a notion defined by (Caragiannis et al. 2016). In PMMS, the maximin share guarantee is required only for pairs of agents, but not necessarily for the grand bundle. Section 2.1, provides an example which establishes that GMMS is a strict generalization of PMMS and MMS. The relevance of GMMS is also substantiated by the fact that it implies other complementary notions of fairness, which do not follow from MMS alone. In the context of indivisible goods, relaxations of envy freeness, such as EF15 (Budish 2011) and EFX6 (Caragiannis et al. 2016) have also been studied. In Section 4 we show that (unlike MMS) GMMS fits into this scale of fairness and, in particular, a GMMS allocation is guaranteed to be EFX (and hence EF1). These implications essentially follow from the observation that, by definition, a GMMS allocation is PMMS as well. (Caragiannis et al. 2016) have shown that PMMS implies EFX, and hence we obtain the desired implications. Throughout the paper, we focus on additive valuations, and a high-level contribution of our work is to show that under additive valuations, a number of useful (existence, algorithmic, and approximation) results which have been es-

5An allocation is said to be envy-free up to one good (EF1) if no agent envies any other after removing at most one good from the other agent s bundle; see Definition 4. 6An allocation is said to be envy-free up to the least valued good (EFX) if no agent envies any other agent after removing any positively valued good from the other agent s bundle; see Definition 5.

tablished for MMS continue to hold for GMMS as well.

1.1 Our Contributions In addition to proving a scale of fairness for GMMS, we establish the following results: 1. Approximate groupwise maximin share allocations always exist under additive valuations. Prior work has shown that there are instances wherein no allocation is MMS (Procaccia and Wang 2014; Kurokawa, Procaccia, and Wang 2016). These non-existence results have motivated a detailed study of approximate MMS allocations, i.e., allocations in which each agent gets a bundle of value (multiplicatively) close to her maximin share. Along these lines, we consider approximate GMMS (see Definition 3), and show that, under additive valuations, a 1/2-GMMS allocation always exists. In addition, such an allocation can be found in polynomial time. 2. GMMS allocations are guaranteed to exist when the valuations of the agents are either binary or identical. 3. Analogous to the experimental results for MMS (Bouveret and Lemaˆıtre 2014), GMMS allocations exist empirically. These simulation results indicate that we do not fall short on such generic existence results by strengthening the maximin solution concept.

1.2 Related Work As mentioned earlier, (Budish 2011) introduced the notion of maximin share guarantee (MMS), and it has been extensively studied since then. In particular, (Bouveret and Lemaˆıtre 2014) showed that if the agents valuations are additive, then an envy free (or proportional) allocation will be MMS as well. They also established that MMS exists under binary, additive valuations. Their experiments, using different distributions over the valuations, did not yield a single example wherein an MMS allocation did not exist. (Kurokawa, Procaccia, and Wang 2016) showed that MMS allocations exist with high probability when valuations are drawn randomly. However, (Procaccia and Wang 2014) provided intricate counterexamples to refute the universal existence of MMS allocations, even under additive valuations. This motivated the study of approximate maximin share allocations, αMMS, where each agent obtains a bundle of value at least α (0, 1) times her maximin share. (Procaccia and Wang 2014) established the existence of 2/3-MMS, and developed a polynomial-time algorithm to obtain such an allocation when the number of agents is a fixed constant. Later, (Amanatidis et al. 2015) showed that a 2/3-MMS can be computed in polynomial (in the number of players) time. Approximate maximin share allocations have also been studied for general valuations. (Barman and Krishnamurthy 2017) have developed an efficient algorithm which finds a 1/10-MMS allocation under submodular valuations. More recently, (Ghodsi et al. 2017) have improved the approximation guarantee for additive valuations to 3/4. They have also developed constant-factor approximation guarantees for submodular and XOS valuations, along with a logarithmic approximation for subadditive valuations.

(Aziz et al. 2017) studied the fair division of indivisible chores (negatively valued goods) and have developed an efficient algorithm which finds a 2-MMS allocation. (Caragiannis et al. 2016) defined another important fairness notion called pairwise maximin share guarantee (PMMS). As mentioned previously, under PMMS, the maximin share guarantee is required only for pairs of agents, and not even for the grand bundle. They also established that PMMS and MMS are incomparable: neither one of these solution concepts implies the other.

2 Preliminaries and Notation We consider the problem of finding a fair allocation of a set of indivisible goods [m] = {1, . . . , m}, among a set of agents [n] = {1, . . . , n}. For a subset of goods S [m] and integer t, let Πt(S) denote the set of all t partitions of S. An allocation is defined as an n-partition (A1, A2, . . . , An) Πn([m]), where Ai is the set of goods allocated to agent i. The preference of the agents over the goods is specified via valuations. Specifically, we denote the valuation of an agent i [n] for a subset of goods S [m] by vi(S). In this work, we assume the valuations to be non-negative and additive, i.e., vi ({g}) 0 for all g [m] and vi(S) = g S vi ({g}). For ease of presentation, we will use vi(g) for agent i s valuation of good g, i.e., for vi({g}). As mentioned previously, the fairness notions considered in this work are defined using thresholds called maximin shares. Formally, given an agent i, parameter k Z+, and subset of goods S [m], the kmaximin share of i restricted to S is defined as μk i (S) := max(P1,...,Pk) Πk(S) minj [k] vi(Pj). Throughout, MMSi will be used to denote the maximin share of an agent i with respect to the grand bundle, MMSi := μn i ([m]). We will now formally define maximin share allocation (MMS allocation). Definition 1 (Maximin Share Allocation). An allocation (A1, . . . , An) is said to be an MMS allocation iff for all agents i [n] we have vi(Ai) MMSi. A different solution concept defined by (Caragiannis et al. 2016) requires the maximin share guarantee to hold only for every pair of agents, i.e., an allocation A = (A1, . . . , An) is said to achieve pairwise maximin share guarantee (PMMS) iff for all i, j [n], we have vi(Ai) μ2 i (Ai Aj) and vj(Aj) μ2 j(Ai Aj). In this paper, we strengthen MMS and PMMS, and define a stronger threshold for each agent i [n], namely groupwise maximin share (GMMSi). Formally,

GMMSi = max J [n],J i μ|J| i

Now we define groupwise maximin share allocation (GMMS allocation). Definition 2 (Groupwise Maximin Share Allocation). An allocation (A1, . . . , An) is said to be a GMMS allocation iff for all agents i [n] we have vi(Ai) GMMSi. Note that an allocation (A1, . . . , An) is GMMS iff

vi(Ai) μ|J| i

j J Aj for all J [n] such that i J.

The fact that there are fair division instances which do not admit an MMS allocation directly implies that GMMS allocation are not guaranteed to exist either. Therefore, we consider approximate GMMS allocations. Definition 3 (Approximate Groupwise Maximin Share Allocation). An allocation (A1, . . . , An) is said to be an α-approximate groupwise maximin share allocation (αGMMS) iff for all agents i [n] we have vi(Ai) αGMMSi. A 1-approximate groupwise maximin share allocation is a GMMS allocation.

2.1 GMMS Strictly Generalizes MMS and PMMS In this section, we provide an example to show that allocations which achieve both MMS and PMMS might not be GMMS. Let us consider an instance with 9 agents and 8 goods G = {g1, g2, . . . , g8}. This ensures that MMSi = 0 for all i [n] and, hence, all the allocations are MMS. Let us fix an agent, say i = 1. Let her valuation for 8 goods be v1(g1) = v1(g2) = v1(g3) = 5, v1(g4) = v1(g5) = 3, and v1(g6) = v1(g7) = v1(g8) = 1. For all other agents i {2, . . . , 9}, let vi(gz) = 0 for all z {1, . . . , 7} and vi(g8) = 1. Now, let us consider an allocation A1 = {g1}, A2 = {g2, g4}, A3 = {g3, g5}, A4 = {g6, g7, g8}, and A5 = A6 = A7 = A8 = . This allocation satisfies both MMS and PMMS. However, the maximin share for the group of agents J = {1, 2, 3, 4} is μ4 1(A1 . . . A4) = 6 > 5 = v1(A1), and hence the allocation is not GMMS. This illustrates the fact that GMMS is a distinct solution concept which strictly generalizes both PMMS and MMS. This example can be extended to construct instances that admit allocations which satisfy the maximin share guarantee for all subgroups of, say, size at most k, but are still not GMMS.

3 GMMS can be arbitrarily better than MMS In this section, we provide a class of examples where an MMS allocation is not necessarily satisfactory in terms of agents valuations. In particular, we show that imposing GMMS leads to allocations which Pareto dominate an allocation which only satisfies MMS. Consider n agents and a set of n + 3 goods (where [m] = {g1, . . . , gn+3}), along with parameter V and a sufficiently small ε; 0 < ε V . The valuations are assumed to be additive and are as follows: For agents i {1, . . . , n 1},

V, z {1, . . . , n 3} V/2, z {n 2, n 1} V/2 ε, z {n, n + 2} V/2 + ε, z {n + 1, n + 3} For the agent n,

V, z {1, . . . , n 1} 0, z {n, n + 1} ε, z {n + 2, n + 3}

Note that in this fair division instance the maximin share of the first (n 1) agents, MMSi = V for all i {1, . . . , n}. In addition, the maximin share of the last agent, MMSn, is 2ε. Now, consider the allocation A = (A1, . . . , An) wherein Ai = {gi}, i {1, . . . , n 3}, An 2 = {gn 2, gn 1},

An 1 = {gn, gn+1}, and An = {gn+2, gn+3}. Allocation A is MMS since vi(Ai) = V for each i {1, . . . , n 1} and vn(An) = 2ε. In this allocation the valuation of agent n is unsatisfactorily low. Another relevant observation is that this allocation is not GMMS. Below, we show that in this instance any GMMS allocation allocates a bundle of value V to every agent, including agent n. The fact that A is not GMMS follows by considering the goods allocated to agents n 2 and n, i.e., let S := An 2 An = {gn 2, gn 1, gn+1, gn+3}. Now, μ2 n(S) = V + ε, but vn(An) = 2ε V . Furthermore, it can be observed that it is necessary to allocate the agent n at least one of her high valued goods {1, . . . , n 1} to satisfy GMMS. Thus, GMMS allocation would always ensure that a bundle of at least V is allocated to all the agents. That is, in this instance, unsatisfactorily low valuations can be avoided by imposing the groupwise maximin share guarantee.

4 Scale of Fairness As mentioned earlier, envy freeness (EF) is a well-studied solution concept in the context of fair division of divisible items. However, for indivisible goods, a simple example with one positively valued good and two agents shows that envy-free allocations do not always exist. Hence, for indivisible goods, natural relaxations of envy freeness in particular, EF1 and EFX have been considered in the literature. We now provide formal definitions of these relaxations. Definition 4 (Envy-free up to one good (Budish 2011)). An allocation A = (A1, A2, . . . , An) is said to be envy-free up to one good (EF1) iff for every pair of agents i, j [n] there exists a good g Aj such that vi(Ai) vi(Aj \ {g}). Definition 5 (Envy-free up to the least positively valued good (Caragiannis et al. 2016)). An allocation A = (A1, A2, . . . , An) is said to be envy-free up to the least valued good (EFX) iff for every pair of agents i, j [n] and for all goods g Aj {g [m] | vi(g ) > 0} (i.e., for all goods g in Aj which are positively valued by agent i) we have vi(Ai) vi(Aj \ {g}). Note that the above mentioned definitions imply that, for additive valuations, an EFX allocation is necessarily EF1 as well. Next we show that, interestingly, these relaxed versions of envy freeness are implied by GMMS, but not by MMS. Proposition 1 (Scale of Fairness). In any fair division instance with additive valuations 1. If an allocation A is envy free (EF) then it achieves groupwise maximin share guarantee (GMMS) as well. 2. If an allocation B is GMMS then it is EFX (and, hence, EF1) as well.

Proof. First we will show that EF implies GMMS: Assume that the allocation A = (A1, . . . , An) is envy free, that is, for all i, j [n] we have vi(Ai) vi(Aj). Therefore, for any agent i and any group of agents J [n] we have |J|vi(Ai) j J vi(Aj). Since the valuation vi is additive, this inequality leads to the following bound vi(Ai) 1 |J|vi(S); here S = j JAj. Now, an averaging argument establishes the following inequality: for

any |J|-partition of S if (P1, P2, . . . , P|J|) Π|J|(S) then vi(Ai) min1 k |J| vi(Pk). Hence, vi(Ai) max(P1,...,P|J|) Π|J|(S) mink vi(Pk) = μ|J| i (S), and we get that A is GMMS. Next, we argue that GMMS implies EFX: (Caragiannis et al. 2016) have shown that that PMMS implies EFX. By definition, GMMS implies PMMS. Hence, a GMMS allocation is guaranteed to be EFX.

Note that (Caragiannis et al. 2016) also provided an example to show that maximin share guarantee by itself does not imply EF1. Hence, an MMS allocation is not necessarily EFX. Consider a fair division instance with three agents, five goods, and each agent values each good at 1. The maximin share of all the agents is 1. Thus, the allocation A1 = {g1, g2, g3}, A2 = {g4} and A3 = {g5} satisfies MMS, but not EF1. This is because agents 2 and 3 continue to envy agent 1 even if a single good is removed from A1. This, overall, shows that while MMS is not enough to guarantee weaker notions of envy freeness, GMMS ensures fairness in terms of such notions, and secures a place in the scale of fairness.

Next we will consider the complementary direction of going from bounded envy to groupwise maximin fairness. In particular, we will establish existence and algorithmic results for approximate GMMS by considering a solution concept which is stronger than EF1, but weaker than EFX. Specifically, we will define allocations which are envy-free up to one less-preferred good (EFL) see Definition 6 below and show that such allocations are guaranteed to exist, when the valuations are additive. Note that, in contrast, the generic existence of EFX allocations remains an interesting open question. Furthermore, we will prove that EFL allocations can be computed in polynomial time and, under additive valuations, such allocations imply 1/2-GMMS.

Definition 6. An allocation A = (A1, A2, . . . , An) is said to be envy-free up to one less-preferred good (EFL) if for every pair of agents i, j [n] at least one of the following conditions hold:

Aj contains at most one good which is positively valued by i; |Aj {g | vi(g ) > 0}| 1 There exists a good g Aj such that vi(Ai) vi(Aj \ {g}) and vi(Ai) vi({g}).

The fact that an EFL allocation is EF1 follows directly from the definitions of these solution concepts. Also, note that if an allocation (A1, . . . , An) is EFX then for any pair of agents i, j [n] with |Aj {g | vi(g ) > 0}| > 1 the second condition in the definition of EFL holds. In particular, write Ai j := Aj {g | vi(g ) > 0} and consider two distinct goods ˆg, g Ai j. Since the allocation is EFX, we have vi(Ai) vi(Aj \ {ˆg}) and vi(Ai) vi(Aj \ { g}). Note that ˆg Aj \ { g}, and, hence, vi(Ai) vi(ˆg). This implies that good ˆg satisfies the second condition in Definition 6. Hence, any EFX allocation is EFL as well. With this new fairness notion, we have the following chain of implications: EF GMMS EFX EFL EF1.

5 An Approximation Algorithm for GMMS Our main result in this section shows that 1/2-GMMS allocations always exist under additive valuation, and such allocations can be found efficiently.

Theorem 1. Every fair division instance with additive valuations admits a 1/2-approximate groupwise maximin share allocation. Furthermore, such an allocation can be found in polynomial time.

Proof-Sketch The proof proceeds in two steps. First, we provide a constructive proof for the existence of EFL allocations, under additive valuations (Section 5.1). Next, we complete the proof by showing that EFL implies 1/2-GMMS (in Section 5.2)

5.1 Existence of EFL Allocations This section shows that EFL allocations are guaranteed to exist when the valuations are additive. Specifically, we develop an algorithm that always finds such an allocation.

Lemma 1. Given any fair division instance with additive valuations, Algorithm 1 finds an EFL allocation in polynomial time.

Algorithm 1 iteratively allocates the goods and maintains a partial allocation, A = (A1, . . . , An), of the goods assigned so far. In each iteration, the algorithm selects an agent i who is not currently envied by any other agent, and allocates i an unassigned good of highest value (under vi). Throughout the execution of the algorithm, the existence of an unenvied agent is ensured by maintaining a directed graph, G(A), that captures the envy between agents. The nodes in this envy graph represent the agents and it contains a directed edge from i to j iff i envies j, i.e., vi(Ai) < vi(Aj). The following lemma, established in (Lipton et al. 2004), shows that if any iteration leads to a cycle in the envy graph G(A), then we can always resolve it to obtain an acyclic envy graph without decreasing the valuation of any agents. The fact that G(A) is acyclic for a partial allocation A implies that it contains a source node, i.e., an agent i who is not envied by other agents. Although, Algorithm 1 is similar to the one developed in (Lipton et al. 2004) which efficiently finds EF1 allocations here, instead of assigning goods in an arbitrary order, we always allocate to an unenvied agent the available good she values the most. This is crucial for obtaining an EFL allocation.

Lemma 2. (Lipton et al. 2004) Given a partial allocation A = (A1, . . . , An) of a subset of goods S [m], we can find another partial allocation B = (B1, . . . , Bn) of S in polynomial time such that (i) The valuations of agents for their bundles do not decrease, that is, vi(Bi) vi(Ai) for all i [n]. (ii) The envy graph G(B) is acyclic.

Proof of Lemma 1. Write A = (A1, . . . , An) to denote the allocation returned by Algorithm 1. First, we note that an inductive argument proves that A is EF1. In fact, we will show that the EF1 condition holds for A with respect to the last (in terms of the algorithm s allocation order) good g assigned to

Algorithm 1 Finding an EFL Allocation Input : n agents, m items, and valuations vi{g} for each agent i [n] and for each good g [m]. Output: An EFL allocation. 1: Initialize allocation A = (A1, A2, . . . , An) with Ai = for each agent i [n], and M = [m]. 2: Initialize directed envy graph G(A) = ([n], E) where E = . 3: while M = do 4: Pick a source vertex i of G(A). {such a vertex always exists, since G(A) is acyclic.} 5: Pick g arg maxj M vi{g}. 6: Update Ai Ai {g} and M M \ {g}. 7: while the current envy graph G(A) contains a cycle do 8: Update A (using Lemma 2) to remove the cycle. 9: end while 10: end while 11: Return A.

each bundle Aj. Write gt to denote the good allocated in the tth iteration of Algorithm 1; hence, the goods are allocated in the following order g1, g2, . . . , gm. The initial partial allocation ( , , . . . , ) is EF1 (in fact, it is envy free). Now, say that in the jth iteration the algorithm allocates good gj to agent i. Write Aj = (Aj 1, . . . , Aj n) and Aj+1 = (Aj+1 1 , . . . , Aj+1 n ), respectively, to denote the partial allocations before and after the jth iteration. The induction hypothesis implies that Aj is EF1 with respect to the last assigned good. Therefore, for every pair of agents r, s [n], we have vr(Aj r) vr(Aj s \ {ga}), where ga is the last good assigned to the bundle Aj s (i.e., for any other good gb Aj s, we have b < a). Since the good gj is allocated to agent i, it must be the case that i is a source vertex in G(Aj), i.e., no agent envies i under Aj. This implies that, vr(Aj r) vr(Aj i) = vr((Aj i {gj})\{gj}) for all r [n]. Note that at this point of time, gj is the last good assigned to the bundle Aj i. In addition, from the proof of Lemma 2, we know that Aj+1 is a permutation of the allocation (Aj 1, Aj 2, . . . , Aj i {gj}, . . . , Aj n), and vr(Aj+1 r ) vr(Aj r) for all r [n]. Hence, for every pair of agents r, s [n] there exists a good ga Aj+1 s such that vr(Aj+1 r ) vr(Aj+1 s \ {ga}). In addition, ga is the last good assigned to the bundle Aj+1 s . That is, the stated property holds for Aj+1 as well. Now, we will use this observation to prove that A is EFL. Specifically, we show the EFL conditions hold for, say, agent 1 (analogous arguments establish the claim for the other agents). Suppose that, during the execution of the algorithm, agent 1 receives its first good, gt, in the tth iteration. Note that the partial allocation before the tth iteration, say At = (At 1, . . . , At n), satisfies |At i {g [m] : v1(g ) > 0}| 1 for all i [n]. This bound follows from the observation that during any previous iteration s < t, the selected source vertex i (i.e., the agent that gets a new good during the sth iteration) does not contain any good which is positively valued by agent 1; otherwise, i would have been envied by 1, contradicting the fact that it is a source vertex. Hence, each bundle in At contains at most one good from

the set {g [m] : v1(g ) > 0}. Let us now consider the final allocation A = (A1, . . . , An) and any agent j [n]. If |Aj {g [m] : v1(g ) > 0}| 1, then the first condition in the definition of EFL holds and we are done, else if |Aj {g [m] : v1(g ) > 0} | > 1, then bundle Aj must have received a good after the tth iteration. This is consequence of the above-mentioned property of the partial allocation At. Write gℓto denote the last good allocated to the bundle Aj. We have ℓ> t, since gℓwas assigned to Aj after the tth iteration. Also, in the tth iteration good gt was selected instead of gℓ, hence it must be the case that v1(gt) v1(gℓ). Note that, as mentioned before, the EF1 condition holds for Aj with respect to gℓ, i.e., v1(A1) v1(Aj \ {gℓ}). In addition, Lemma 2 implies that v1(A1) v1({gt}). Therefore, if |Aj {g [m] : v1(g )}| > 1 for any j [n], then there exists a good gℓsuch v1(A1) v1(Aj \ {gℓ}) and v1(A1) v1(gℓ). Hence, A is an EFL allocation.

5.2 EFL implies Approximate GMMS Lemma 3. In any fair division instance with additive valuations, if an allocation A = (A1, . . . , An) is EFL, then it is 1/2-GMMS allocation as well.

Proof. Fix an agent i and a set of k agents, J [n] which contains i, i.e., |J| = k and J i. Also, let S = j JAj denote the set of all the goods allocated to the agents in J. We will show that agent if (A1, . . . , An) is EFL, then vi(Ai) is at least 1

2 times the maximin share of i restricted to S, i.e., vi(Ai) 1

2μk i (S). This establishes the stated claim. Write Si [m] to denote the set of goods which are positively valued by i, Si := {g [m] | vi(g ) > 0}. Now, among the set of agents J \{i} consider the ones who are allocated at most one good from Si; specifically, let T := {j J \ {i} | |Aj Si| 1}. Write J := J \ T, t := |J |, and S = j J Aj. Note that the agent i belongs to the group J , and for all j J we have |Aj Si| > 1. Therefore, the fact that A is EFL implies that, for all j J , there exists a good g(j) Aj such that vi(Ai) vi(Aj \ {g(j)}) and vi(Ai) vi(g(j)). In other words, for the additive valuation vi, we have 2vi(Ai) vi(Aj). We will now establish the multiplicative bound with respect to μt i (S ) (the maximin share of i restricted to S ) and prove that μt i (S ) μt i(S). This will complete the proof. Since vi is additive, an averaging argument gives us

μt i (S ) 1

t vi(S ) = 1

j J vi(Aj) 1

t 2t vi(Ai)

Here, the last inequality uses the bound 2vi(Ai) vi(Aj) for all j J . Therefore, vi(Ai) 1 2μt i (S ). To complete the proof, we need to show that μt i (S ) μt i(S). Note that while considering the maximin shares of agent i we can restrict our attention to Si (the set of goods which are positively valued by i). In particular, the equalities μt i (S ) = μt i (S Si) and μt i(S) = μt i(S Si) imply that, without loss of generality, we can work under the assumptions that S Si and S Si. Effectively, for all j J, we can slightly abuse notation and denote Aj Si

by Aj. Now, consider the allocation M = (M1, . . . , Mt) arg max (B1,...,Bt) Πt(S) min j [t] vi(Bj).

We have, minj J vi(Mj) = μt i(S). Also, note that |Aj| 1 for each agent j K = J \ J . Therefore, there are at most |K| = t t bundles in M with items from S \ S . We choose t bundles from M = (M1, . . . , Mt) which do not contain any item from S \ S . Let us call these new bundles M = (M 1, . . . , M t ). By the definition of M, the value of each such bundle for agent i is greater than or equal to μt i(S), that is, vi(M j) μt i(S) for all j [t ]. Since we have assumed that all items have nonnegative values, adding more items from the remaining (t t ) bundles to any of the bundles in M can only increase the value of the partitions. Thus, μt i (S ) μt i(S), which implies that vi(Ai) 1

Lemmas 1 and 3 directly establish Theorem 1. We note that both in terms of the algorithm and EFL s implication the approximation guarantee established here is essentially tight; this observation can be proved by considering simple examples.

6 Guaranteed Existence of GMMS Allocations in Restricted Settings In this section, we prove the existence of GMMS for relevant valuation classes. Theorem 2. Groupwise maximin share allocations always exist under additive, binary valuations, i.e., such allocations exist when the additive valuations satisfy vi(g) {0, 1} for all agents i [n] and goods g [m].

Proof. To prove the theorem, it suffices to show that under additive, binary valuations, EF1 implies GMMS. Recall that EF1 allocations are guaranteed to exist. Let A = (A1, . . . , An) be an EF1 allocation. Fix an agent i and a group of agents J i. Also, write S := j J Aj. Next we

complete the proof by showing that vi(Ai) μ|J| i (S). Since the valuations are binary, for any subset of goods B [m], the total value vi(B) is a non-negative integer. Therefore, μ|J| i (S) must be a non-negative integer. Moreover, since the valuations are additive, we have 1 |J|vi(S)

μ|J| i (S). In addition, the facts that (a) A is an EF1 allocation and (b) the maximum value of any good is 1 imply vi(Ai) vi(Aj) 1 for all j J. Therefore,

|J||J|vi(Ai) 1

j J\{i} (vi(Aj) 1)

|J|(vi(S) |J| + 1) = 1

|J|vi(S) |J| 1

μ|J| i (S) |J| 1

|J| > μ|J| i (S) 1.

The last inequality vi(Ai) μ|J| i (S) > 1 implies vi(Ai) μ|J| i (S) since vi(Ai) and μ|J| i (S) are integers. Overall, the inequality vi(Ai) μ|J| i (S) shows that the EF1 allocation A is GMMS as well. This completes the proof.

Note that the following theorem holds for general combinatorial valuations and is not limited to the additive case.

Theorem 3. If all the n agents in a fair division instance have the same valuation (i.e., vi = vj for all i, j [n]), then a groupwise fair allocation is guaranteed to exist.

Proof. Given a fair division instance with m goods and n agents with the same valuation function v, we will define an order on Πn([m]), the set of n-partitions of [m]. For vectors u, u Rn, we say that u lexicographically dominates u if u = u , or there exists an index a [n] such that u(a) > u (a) and for all b < a we have u(b) = u (b); here, u(k) and u (k) denotes the kth smallest component of u and u , respectively. Extending this definition, an allocation (A1, . . . , An) Πn([m]) is said to lexicographically dominate another allocation (B1, . . . , Bn) Πn([m]) iff the vector of valuations (v(A1), . . . , v(An)) lexicographically dominates (v(B1), . . . , v(Bn)). Note that lexicographic domination defines a total order over the equivalence classes of n-partitions. In addition, up to permutations of the valuation vector, there exists a unique maximal allocation with respect to this order, i.e., there exists an allocation A = (A 1, . . . , A n) which lexicographically dominates all other allocations. We will show that A is GMMS. For contradiction, say that this is not the case, and the GMMS condition is violated for subset J [n] and agent i J, i.e., vi(A i ) < μ|J| i (S); here S := j JA j. Since the valuations are identical, the maximin share of each agent in J restricted to S is the same, i.e., μ|J| i (S) = μ|J| k (S), for all k J. Hence, GMMS condition must also be violated for agent arg minj J v(A j). This observation and the definition of maximin shares imply that there exists a |J|-partition of S, say (M1, . . . , M|J|), such that min1 a |J| v(Ma) > minj J v(A j). Now, consider an allocation B = (B1, . . . , Bn) obtained from A by (i) replacing the |J| bundles A js (for j J) with Mas (for 1 a |J|), and (ii) setting Bk = A k for all k / J. Note that, even under any permutation of the bundles, the allocation B = A . Also, the construction of B ensures that it lexicographically dominates A . This contradicts the maximality (under the defined lexicographic order) of A and, hence, the stated claim follows.

7 Some Empirical Results

For an experimental investigation, we generated 1000 random instances, for several combinations of n agents and m goods (n ranging from 3 to 5, and m from 3 to 11), by randomly drawing the valuations from two different distributions (a) gaussian distribution with mean 0.5, standard deviation 0.1 (truncated at 0 to ensure nonnegative valuations) and (b) uniform distribution [0, 1]. These are the same set of experiments that (Bouveret and Lemaˆıtre 2014) carried out for studying the existence of various fairness notions under additive valuations. In addition, we considered the modification of these instances wherein all the agents agree on the same ranking of the goods, but may have different valuations for the same

item. Such instances are said to have same-order preferences (SOP), and were studied by (Bouveret and Lemaˆıtre 2014). They showed that, when it comes to (empirically) finding an MMS allocation, SOP instances are the hardest. We observe similar results for GMMS: finding a GMMS allocation, done using brute-force search, requires noticeably more time in SOP instances, than in non-SOP instances. Our empirical results and observations are summarized below:

1. GMMS allocations exist empirically in all randomly generated instances (which is similar to the experimental results for MMS (Bouveret and Lemaˆıtre 2014)). These simulation results indicate that we may not fall short on such generic existence results by strengthening the maximin solution concept.

2. Allocations generated by the EFL algorithm (Algorithm 1) on the random instances achieve an approximation factor of 0.98 (on an average) which is better than our theoretically obtained worst-case bound of 0.5. The approximation factor (on average) is lower for SOP than for non-SOP instances. Moreover, we observe that, for randomly generated instances, the approximation factor is better when the number of items is a multiple of the number of agents. This may be because of the round robin nature of the algorithm which gives an agent her most desirable good at each round.

3. As expected, our proposed EFL algorithm ran much faster than the (exponential-time) algorithm for finding exact GMMS. Our algorithm was about 107 times faster than the exact GMMS computation on a machine with a quad Intel Core i7 processor and 32 GB RAM.

8 Conclusion and Future Work

In this paper, we introduced the concept of GMMS to address fair allocation of indivisible goods, thereby strengthening the well-studied notions of MMS and PMMS. We established the existence of 1/2-GMMS under additive valuations, and developed an efficient algorithm for finding such allocations. We also proved that under specific settings exact GMMS allocations always exist. In addition, GMMS allocations were always found in our experiments (over a large number of randomly generated instances). This indicates why it seems nontrivial to obtain simpler7 examples which refute the guaranteed existence of GMMS allocations. Finding an instance which admits an MMS allocation but not a GMMS allocation remains an interesting, open problem. Our work addresses key questions about groupwise fairness when the valuations are additive, and it motivates the study of this notion in more general settings, e.g., under submodular valuations, or under additional constraints, such as the ones considered by (Bouveret et al. 2017). Another interesting direction of future work is to understand groupwise fair division of indivisible goods among strategic agents.

7The intricate examples showing the nonexistence of MMS under additive valuations (Procaccia and Wang 2014; Kurokawa, Procaccia, and Wang 2016) also serve as counterexamples for GMMS.

Acknowledgments. Siddharth Barman was supported by a Ramanujan Fellowship (SERB - SB/S2/RJN-128/2015). Arpita Biswas gratefully acknowledges the support of a Google Ph D Fellowship Award.

References Amanatidis, G.; Markakis, E.; Nikzad, A.; and Saberi, A. 2015. Approximation algorithms for computing maximin share allocations. In International Colloquium on Automata, Languages, and Programming, 39 51. Springer. Aziz, H.; Rauchecker, G.; Schryen, G.; and Walsh, T. 2017. Approximation algorithms for max-min share allocations of indivisible chores and goods. In Proceedings of the Thirty First AAAI Conference on Artificial Intelligence, 335 341. Barman, S., and Krishnamurthy, S. K. 2017. Approximation algorithms for maximin fair division. In Proceedings of the 2017 ACM Conference on Economics and Computation, 647 664. Bouveret, S., and Lemaˆıtre, M. 2014. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. In Proceedings of International Conference on Autonomous Agents and Multi-Agent Systems, 1321 1328. Bouveret, S.; Cechlaova, K.; Elkind, E.; Igarashi, A.; and Peters, D. 2017. Fair division of a graph. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, 135 141. Brams, S. J., and King, D. L. 2005. Efficient fair division: Help the worst off or avoid envy? Rationality and Society 17(4):387 421. Brandt, F.; Conitzer, V.; Endriss, U.; Procaccia, A. D.; and Lang, J. 2016. Handbook of Computational Social Choice. Cambridge University Press. Budish, E. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119(6):1061 1103.

Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The unreasonable fairness of maximum nash welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation, 305 322. ACM.

Foley, D. 1967. Resource allocation in the public sector. Yale Economic Essays 7:73 76.

Ghodsi, M.; Haji Aghayi, M.; Seddighin, M.; Seddighin, S.; and Yami, H. 2017. Fair allocation of indivisible goods: Improvement and generalization. ar Xiv preprint ar Xiv:1704.00222.

Goldman, J., and Procaccia, A. D. 2015. Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges 13(2):41 46.

Kurokawa, D.; Procaccia, A. D.; and Wang, J. 2016. When can the maximin share guarantee be guaranteed? In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, volume 16, 523 529.

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

Procaccia, A. D., and Wang, J. 2014. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, 675 692. ACM.

Steinhaus, H. 1948. The problem of fair division. Econometrica 16:101 104.

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

Varian, H. R. 1974. Equity, envy, and efficiency. Journal of economic theory 9(1):63 91.