# fair_division_under_cardinality_constraints__253ab287.pdf

Fair Division Under Cardinality Constraints

Arpita Biswas and Siddharth Barman Indian Institute of Science arpitab@iisc.ac.in, barman@iisc.ac.in

We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods i.e., the goods are categorized and a limit is speciﬁed on the number of goods that can be allocated from each category to any agent. The objective here is to ﬁnd a fair allocation in which the subset of goods assigned to any agent satisﬁes the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied (unconstrained) fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist even under matroid constraints.

1 Introduction

A large body of recent work in algorithmic game theory, artiﬁcial intelligence, and computational social choice has been directed towards understanding the problem of allocating indivisible goods among agents in fair manner; see, e.g., [Brandt et al., 2016] and [Endriss, 2017] for excellent expositions. This recent focus on indivisible goods is motivated, in part, by applications (such as division of inheritance and partitioning computational resources in a cloud computing environment) which inherently entail allocation of resources that cannot be fractionally allocated. In fact, algorithms developed for ﬁnding fair allocations of indivisible goods have been implemented in speciﬁc settings; for instance, Course Match [Budish et al., 2016] is employed for course allocation at the Wharton School in the University of Pennsylvania

and the website Spliddit (www.spliddit.org) [Goldman and Procaccia, 2014] provides online access to fair division algorithms. Note that, though the theory of fair division is extensive, classical notions of fairness such as envy freeness1 typically address allocation of divisible goods and are not representative in the indivisible setting. For instance, while an envy-free allocation of divisible goods is guaranteed to exist [Stromquist, 1980], such an existence result does not hold for indivisible goods.2

Motivated by these considerations, recent results have formulated and studied solution concepts for fairly allocating indivisible goods [Budish, 2011; Procaccia and Wang, 2014; Bouveret and Lemaˆıtre, 2014]. Arguably, the two most prominent notions of fairness in this context are (i) envy freeness up to one good (EF1) and (ii) the maximin share guarantee (MMS). These solution concepts were deﬁned by Budish [Budish, 2011] and they, respectively, provide a cogent analogue of envy-freeness and proportionality3 in the context of indivisible goods:

An allocation is said to be EF1 if every agent values her bundle at least as much as any other agent s bundle, up to the removal of the most valuable good from the other agent s bundle. EF1 allocations are guaranteed to exist; by contrast, for indivisible goods envy-free allocations might not exist. Another attractive feature of EF1 is that it is computationally tractable: even under combinatorial valuations, EF1 allocations can be found efﬁciently [Lipton et al., 2004]. Furthermore, under additive valuations, this notion of fairness is compatible with Pareto efﬁciency [Caragiannis et al., 2016].

An allocation is said to satisfy MMS if each agent receives a bundle of value at least as much as her maximin share. These shares are deﬁned as the maximum value that an agent can guarantee for herself if she were to

1An allocation is said to be envy-free if each agent values her bundle at least as much as she values any other agent s bundle[Foley, 1967; Varian, 1974]. 2If we have a single indivisible good and two agents, then in any allocation, the losing agent is bound to be envious. 3An allocation is said to be proportionally fair among n agents, if every agent gets a bundle of value at least 1/n times her value for the entire set of goods.

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

partition the set of goods into n bundles and then, from those bundles, receive the minimum valued one; here, n is the total number of agents. This can be interpreted via an application of the standard cut-and-choose protocol over indivisible goods: if agent i is (hypothetically) asked to partition the set of goods into n bundles and the remaining (n 1) agents were to select their bundles before i, then a risk-averse agent would ﬁnd a partition which maximizes the least valued bundle. This value, that the agent i can guarantee for herself, is called the maximin share of i. Even though MMS allocations are not guaranteed to exist [Procaccia and Wang, 2014; Kurokawa et al., 2016], it admits efﬁcient approximation guarantees, in particular, assuring that each agent receives a bundle of value at least 2/3 times her maximin share [Procaccia and Wang, 2014; Amanatidis et al., 2015; Barman and Krishnamurthy, 2017].4 Note that these results establish an absolute guarantee, i.e., they show that an approximately maximin fair allocation always exists. The existence and computational results developed for EF1 and MMS provide a sound understanding of fair division of indivisible goods. However, it is relevant to note that the vast majority of work in this thread of research is solely focussed on the unconstrained version of the problem.5 To address this limitation, and motivated by the fact that in many real-world settings the allocations are required to satisfy certain criteria, we study a relevant, constrained version of the fair division problem. In particular, we consider a setting wherein the indivisible goods are categorized and a limit is speciﬁed on the number of goods that can be allocated from each category to any agent. Here, the objective is to ﬁnd a fair allocation in which the subset of goods assigned to any agent satisﬁes the given cardinality constraints. We shall see that this corresponds to a fair allocation problem under a partition matroid constraint. The following stylized example adapted from [Gourv es et al., 2014] demonstrates the applicability of such constraints: A museum decides to open new branches, and thereby needs to transfer some of the exhibits from the main museum to the newly opened ones. The exhibits are categorized into, say, statues, paintings, and pottery. In addition, there is an upper limit on the number of exhibits that every newly opened branch can accommodate from each category. The question now is to ﬁnd a feasible division of the exhibits which is fair to the curators of each of the new branches.

Our Contributions: We establish the following results under additive valuations and cardinality (partition matroid) constraints:

1. EF1 allocations are guaranteed to exist. In particular, we develop a combinatorial algorithm which, for a given

4For additive valuations, Ghodsi et al. [Ghodsi et al., 2017] provide an improved approximation guarantee of 3/4. 5The work of Bouveret et al. [Bouveret et al., 2017] along with [Gourv es and Monnot, 2017] and [Gourv es et al., 2014] are notable exceptions. These results are discussed in Section 1.1.

fair division instance with additive valuations and cardinality constraints, ﬁnds an EF1 allocation in polynomial time (Theorem 1).

2. In this constrained setting, a constant-factor approximate MMS allocation always exists and can be computed in polynomial time (Theorem 2). Note that, in this setting, the value of the maximin share of each of the n agents is obtained by considering only feasible allocations (see Equation (1) in Section 2). That is, here, the maximin share of an agent is deﬁned to be maximum value that she can guarantee for herself if she were to partition the set of goods into n bundles, each of which must satisfy the cardinality constraints, and from them receive the minimum valued one.

3. We also consider fair division subject to matroid constraints (Section 6) and show that if the agents have identical, additive valuations, then again an EF1 allocation is guaranteed to exist (Theorem 3).

1.1 Related Work The fairness notions EF1 and MMS were deﬁned by Budish [Budish, 2011] (see also [Moulin, 1990]), and have been extensively studied since then. These two solution concepts are incomparable, i.e., one does not imply the other [Caragiannis et al., 2016]. The existence of EF1 allocations can be established via the cycle-elimination algorithm [Lipton et al., 2004]. Fair division instances wherein the agents valuations are binary and additive always admit MMS allocations [Bouveret and Lemaˆıtre, 2014]. However, there exists intricate counterexamples that refutes the universal existence of MMS allocations, even under additive valuations [Procaccia and Wang, 2014; Kurokawa et al., 2016]. This lead to a study of approximate maximin share allocations, α-MMS, where each agent receives a bundle whose value to her is at least α (0, 1) times her maximin share. In particular, efﬁcient algorithms are provided to compute a 2/3-MMS allocation [Procaccia and Wang, 2014; Amanatidis et al., 2015]. More recently, constant-factor approximation guarantees for MMS in settings wherein the valuations are not necessarily additive have been established in [Barman and Krishnamurthy, 2017] and [Ghodsi et al., 2017]. Speciﬁcally, for submodular valuations Ghodsi et al. [Ghodsi et al., 2017] have developed an efﬁcient algorithm for computing 1/3-MMS allocations. As mentioned previously, the work on fair division of indivisible goods is primarily conﬁned to the unconstrained setting. Exceptions include the setting considered in [Bouveret et al., 2017] and [Ferraioli et al., 2014]. In [Bouveret et al., 2017], they consider fair division of goods which correspond to vertices of a given graph, and the problem is to fairly allocate a connected subgraph to each agent. They also show that MMS allocations might not exist for general graphs; however, it can be efﬁciently computed when the underlying graph is a tree. Ferraioli et al. [Ferraioli et al., 2014] consider fair division problems where each agent must receive exactly k goods, for a given integer k, and provide an algorithm to efﬁciently com-

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

pute a 1/k-approximate MMS allocation. A different kind of matroid constraint is considered in [Gourv es and Monnot, 2017] and [Gourv es et al., 2014]. In particular, their problem formulation requires that the union of all the allocated goods is an independent set of a given matroid. This setup is incomparable to the one considered in this paper. Specifically, while we ensure that in the computed fair allocation each agent s bundle satisﬁes the partition matroid constraint and all the goods are allocated, these requirements are not imposed in [Gourv es and Monnot, 2017] and [Gourv es et al., 2014].

2 Notation and Preliminaries An instance of the fair division problem comprises of a tuple [m], [n], (vi)i [n] , where [m] = {1, 2, . . . , m} denotes the set of indivisible goods, [n] = {1, 2, . . . , n} denotes the set of agents, and vis specify the valuation (preferences) of the agents, i [n], over the set of goods. Throughout, we will assume that, for each agent i, the valuation vi : 2[m] 7 R+ is additive, i.e., for all agents i [n] and subsets S [m], vi(S) = P g S vi ({g}). Also, we have vi ({g}) 0 for all i [n] and g [m]. For ease of notation, we will use vi(g), instead of vi({g}), to denote the valuation of agent i for a good g. Write Πt(S) to denote the set of all t-partitions of a subset of goods S [m]. An allocation, A, refers to an n-partition A = (A1, A2, . . . , An) Πn([m]), where Ai is the subset of goods (bundle) allocated to agent i. In this work we focus on ﬁnding fair allocations which satisfy given cardinality constraints. Speciﬁcally, we are given a partition of the set of goods consisting of ℓdifferent categories {C1, C2, . . . , Cℓ}, and associated with each category h {1, 2, . . . , ℓ} we have a (cardinality) threshold kh. In this setup, an allocation A = (A1, A2, . . . , An) is said to be feasible iff, for every bundle Ai and category h, the cardinality constraint holds: |Ai Ch| kh. Throughout, we will use F to denote the set of feasible allocations, F := {A Πn([m]) | |Ai Ch| kh for all i [n] and h [ℓ]}. To ensure that F is nonempty, we require that the threshold kh |Ch|

n for all categories h [ℓ]. We will use [m], [n], (vi)i [n], F to denote an instance of the fair division problem subject to cardinality constraints. Overall, our goal is to ﬁnd fair allocations contained in F.6 In this work, we provide existential and algorithmic results for the following fairness notions: Envy-free up to one good (EF1): In a fair division instance [m], [n], (vi)i [n], F , an allocation A = (A1, A2, . . . , An) F is said to be EF1 iff for every pair of agents i, j [n] there exists a good g Aj such that vi(Ai) vi(Aj \ {g}). Maximin Share Guarantee (MMS): Given an instance [m], [n], (vi)i [n], F , the (constrained) maximin share

6Note that the set F might be exponential in size, but it is speciﬁed in an efﬁcient manner via the partition {C1, C2, . . . , Cℓ} and thresholds kh. Setting ℓ=1, C1=[m], k1=m, we get F=Πn([m]). Hence, this formulation is a strict generalization of the unconstrained fair division problem.

of agent i is deﬁned as

CMMSi := max (P1,...,Pn) F min j [n] vi(Pj). (1)

An allocation A = (A1, . . . , An) F is said satisfy MMS iff for i [n], we have vi(Ai) CMMSi. Since MMS allocations are not guaranteed to exist, the objective is to ﬁnd feasible allocations (A1, . . . , An) F wherein each agent gets a bundle of value at least α (0, 1] times CMMSi; with factor α being as large as possible. We call such allocations α-MMS.

3 Main Results The key results established in this paper are: Theorem 1. Given any fair division instance [m], [n], (vi)i [n], F with additive valuations and cardinality constraints (F = ), there exists a polynomial time algorithm for ﬁnding a feasible EF1 allocation7. This theorem is established in Section 4 and it implies that as long as the set of feasible allocations F is nonempty it admits an EF1 (i.e., a fair) allocation. Theorem 2. Given any fair division instance [m], [n], (vi)i [n], F with cardinality constraints (F = ) and additive valuations, a 1/3-MMS allocation can be computed in polynomial time. Analogous to the EF1 case, this theorem provides an absolute, existence guarantee for approximate maximin fair allocations under cardinality constraints. A proof of this result appears in Section 5. We also establish that when the valuations are identical, then EF1 allocations exist even under matroid constraints; see Theorem 3 in Section 6.

4 EF1 Allocations Under Cardinality Constraints: Proof of Theorem 1 In the unconstrained setting, there exist efﬁcient algorithms for ﬁnding EF1 allocations; see, e.g., the cycle-elimination algorithm [Lipton et al., 2004] and the round-robin method [Caragiannis et al., 2016]. However, the allocations obtained by these algorithms are not guaranteed to satisfy the given cardinality constraints. We bypass this issue by developing a polynomial-time algorithm, ALG 1, for ﬁnding an allocation A which is not only EF1, but also feasible, i.e., A F. ALG 1 is based on an interesting modiﬁcation of the roundrobin algorithm: initially, ALG 1 selects an arbitrary order (permutation) over the agents σ := (σ(1), . . . , σ(n)). It then picks an unallocated category h and executes the Greedy Round-Robin algorithm (ALG 2) with the n agents, |Ch| goods (from category Ch), and the selected order σ. ALG 2 follows the ordering σ in a round-robin fashion (i.e., it selects agents, one after the other, from σ(1) to σ(n)), and

7One can construct examples to show that stronger fairness notions than EF1 in particular, envy-free up to the least valued good (EFX) [Caragiannis et al., 2016] and envy-free up to one leastpreferred good (EFL) [Barman et al., 2018] are not guaranteed to exist under cardinality constraints.

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

Algorithm 1 ALG 1 Input : A fair division instance [m], [n], (vi)i, F with additive valuations and cardinality constraints. Output: A feasible EF1 allocation 1: Initialize allocation A0 = (A0 1, . . . , A0 n) with A0 i for each agent i [n]. 2: Fix an (arbitrary) ordering of the agents σ = (σ(1), σ(2), . . . , σ(n)) 3: for h = 1 to ℓdo 4: Bh Greedy-Round-Robin(Ch, [n], (vi)i, σ). 5: Set Ah i Ah 1 i Bh i for all i [n]. 6: Using Lemma 1, update Ah = (Ah 1, . . . , Ah n) to obtain an acyclic envy graph G(Ah). 7: Update σ to be a topological ordering of G(Ah).

8: Return Aℓ.

iteratively assigns to the selected agent an unallocated good from Ch that she desires the most. Finally, it returns an allocation Bh Πn(Ch).

Algorithm 2 Greedy-Round-Robin (ALG 2) Input : An instance C, [n], (vi)i with additive valuations and an ordering σ of [n]. Output: An allocation of the given |C| goods among n agents 1: Initialize bundle Bi , for each agent i [n], the set of unallocated goods M C, and t 0. 2: while M = do 3: t t + 1. 4: for i = 1 to n do 5: Set gt σ(i) arg maxg M vσ(i)(g)

6: Update Bσ(i) Bσ(i) {gt σ(i)}

7: Update M M \ {gt σ(i)}. 8: if M == then 9: break; 10: Return B = (B1, . . . , Bn).

After allocating all the goods of a category h, Step 6 of ALG 1 creates an envy graph8 G(Ah). It was established in [Lipton et al., 2004] that one can always efﬁciently update a given partial allocation such that the resulting envy graph is acyclic:

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

Finally, σ is updated to be a topological ordering of the

8An envy graph, for an allocation A, is a directed graph that captures the envy between agents in A. Speciﬁcally, the nodes in the envy graph represent the agents and it contains a directed edge from i to j iff i envies j, i.e., iff vi(Ai) < vi(Aj).

acyclic directed graph G(Ah). This new ordering is then used for the next category of goods. The feasibility of the computed allocation, Aℓ, directly follows from the fact that (for each h [ℓ]) ALG 2 distributes the |Ch| goods evenly among n agents. In particular, the roundrobin nature of ALG 2 ensures that, Bh i , the set of goods allocated to agent i from category h satisﬁes:9

|Bh i | |Ch|

In Lemma 2 we show that, for each h [ℓ], the partial allocation obtained after the allocating the ﬁrst h categories, Ah, is EF1. Since Algorithm 1 allocates all the m goods, the ﬁnal allocation, Aℓ, is EF1 as well. This, along with the observation that ALG 1 runs in polynomial time completes the proof of Theorem 1. Next, we establish a proposition which will be used in the proof of Lemma 2. Proposition 1. Given any fair division instance C, [n], (vi)i with additive valuations and an ordering of agents σ, the allocation B = (B1, . . . , Bn) obtained by ALG 2 satisﬁes the following properties: (1) For any two indices i < j, the agent σ(i) does not envy agent σ(j), i.e., vσ(i)(Bσ(i)) vσ(i)(Bσ(j)). (2) B is EF1.

Proof. Write T := |C|

n to denote the total number of rounds of ALG 2. In each round, for i < j, agent σ(i) gets to choose her most desired good among the unallocated goods before agent σ(j). Hence, if gt σ(i) and gt σ(j) denote the good assigned to agent σ(i) and σ(j), respectively, in the tth round, then vσ(i)(gt σ(i)) vσ(i)(gt σ(j)) for all t {1, . . . , T}. Since the valuations are additive, the stated property holds: vσ(i)(Bσ(i)) vσ(i)(Bσ(j)). It is known that the round-robin algorithm results in an EF1 allocation [Caragiannis et al., 2016], we repeat the argument for completeness: If index i is less than j, then agent σ(i) does not envy agent σ(j). On the other hand, even if i > j the good allocated to agent σ(i) in the tth round is of value (under vσ(i)) no less than the good allocated to agent σ(j) in the (t + 1)th round: vσ(i)(gt σ(i)) vσ(i)(gt+1 σ(j)) for all t {1, . . . , T 1}. Summing we get, PT 1 t=1 vσ(i)(gt σ(i)) vσ(i)(Bσ(j)) vσ(i)(g1 σ(j)). Thus, the allocation B is EF1.

Lemma 2. ALG 1 returns an EF1 allocation.

Proof. We will show inductively that, for each h [ℓ], the partial allocation obtained after allocating the ﬁrst h categories, Ah, is EF1. Hence, the returned allocation, Aℓis EF1 as well. The base case (h = 1) follows from Proposition 1; since A1 = B1, the proposition ensures that B1 is EF1. By the induction hypothesis we have that Ah is EF1 and, by construction, the corresponding envy graph G(Ah) is

9Recall that the underlying feasible set of allocations F is nonempty if and only if the integer limit kh |Ch|

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

acyclic. Next, we will show that this continues to hold for the next category h + 1. Note that the ordering of agents for (executing ALG 2 over) the category Ch+1 is obtained by topologically sorting G(Ah). Let π be that topological ordering and write π 1(a) as the index of agent a according to the ordering π. Now, if agent a envies b in Ah, then there is a directed edge from a to b in G(Ah) and, hence, π 1(a) < π 1(b). In this case, Proposition 1 ensures that a does not envy b in Bh+1, i.e., we have va(Bh+1 a ) va(Bh+1 b ). The fact that Ah is EF1 gives us va(Ah a) va(Ah b ) va(g), for some g Ah b . Summing the last two inequalities and noting that Ah+1 a = Ah a Bh+1 a and Ah+1 b = Ah b Bh+1 b we get that Ah+1 is EF1 with respect to agent a and b. The complementary case wherein a does not envy b in Ah is analogous, since Bh+1 is guaranteed to be EF1 in itself. Overall, this establishes the stated claim, that the ﬁnal allocation Aℓis EF1.

Lemma 2 along with the feasibility argument mentioned above (and the direct observation that ALG 1 runs in polynomial time) proves Theorem 1.

5 MMS Under Cardinality Constraints: Proof of Theorem 2 To obtain an α-approximate maximin share allocation (αMMS) under cardinality constraints we deﬁne a nonnegative, monotone, submodular function Fi( ), for each agent i [n] which helps in reducing a fair division problem under additive valuations and cardinality constraints to an unconstrained fair division problem under monotone, submodular valuations Fi. Recall that a function Fi( ) is said to be monotone and submodular iff for all subsets A B [m] and g [m] \ B, we have F(A) F(B) and F(A {g}) F(A) F(B {g}) F(B). We deﬁne the function Fi( ) : 2[m] R as follows Fi(S) := X

h [ℓ] f h i (S) where,

f h i (S) :=

g S Ch vi(g), if |S Ch| kh X

g Top kh i (S Ch) vi(g), otherwise

Here, Topk i (T) denotes the set of the k most valued (by agent i) goods contained in T. The following lemma asserts that Fis are submodular; its proof is deferred to a full version of the paper. Lemma 3. For each agent i [n] the function Fi( ) (deﬁned above) is monotone, nonnegative, and submodular. Recall that the set of feasible allocations F is nonempty iff the cardinality thresholds kh |Ch|

n for all categories h [ℓ]. Assuming nonempty set of feasible allocations, we establish the following lemma. Lemma 4. If for all the categories h [ℓ], the cardinality threshold satisﬁes kh |Ch|

n , then for each agent

i [n], the value of max (P1,...,Pn) F min j [n] vi(Pj) equals

max (P1,...,Pn) Πn([m]) min j [n] Fi(Pj).

Proof. We ﬁx an agent i [n] and ﬁrst show that the left-hand side of the stated equality is upper bounded by the right-hand side. Write (A 1, . . . , A n) arg max(P1,...,Pn) F minj [n] vi(Pj). Since |A j Ch| kh for all h and j, we have Fi(A j) = vi(A j) for all j. Now, the inequality minj [n] Fi(A j) max(P1,...,Pn) Πn([m]) minj [n] Fi(Pj) establishes the upper bound. We complete the proof by showing that an inequality holds in the other direction as well. Write (B 1, . . . , B n) arg max(P1,...,Pn) Πn([m]) minj [n] Fi(Pj). Say (B 1, . . . , B n) / F, then there exists an index b [n] and h [ℓ] such that |B b Ch| > kh. Since kh |Ch|

n , an averaging argument implies that there exists another index a [n] for which |B a Ch| < kh. Now, consider the lowest valued (by agent i) good g B b Ch. Note that Fi(B b ) = Fi(B b \ {g}) and Fi(B a {g}) Fi(B a). Hence, we can iteratively perform such swaps till all the cardinality constraints are satisﬁed. That is, we can obtain an allocation, say B = (B 1, . . . , B n) F, which is feasible and satisﬁes Fi(B j) Fi(B j ) for all j [n]. The feasibility of B ensures that the following equality holds for all j: Fi(B j) = vi(B j). Therefore, minj [n] Fi(B j) = minj [n] vi(B j) max(P1,...,Pn) F minj [n] vi(Pj). Hence, the left-hand side of the equality stated in the lemma is at least as much as the right-hand side.

Under submodular valuations a 1/3-MMS allocation can be computed efﬁciently in the unconstrained setting [Ghodsi et al., 2017]. Therefore, for an unconstrained fair division instance over the m goods and with submodular valuations of the n agents as (Fi)i, we can efﬁciently ﬁnd an allocation A = (A1, . . . , An) Πn([m]) which is 1/3-MMS. Employing a swap argument similar to the one used in the proof of Lemma 4 we can efﬁciently convert A into a feasible allocation B F which satisﬁes Fi(Bi) Fi(Ai), for all i [n]. That is, for the unconstrained instance, B is a 1/3MMS allocation as well. In addition, the feasibility of B implies that Fi(Bi) = vi(Bi), for all i. Overall, via Lemma 4 (i.e., the fact that the maximin shares of each agent i in the constructed unconstrained instance is equal to the underlying CMMSi value), we get that B is a feasible, 1/3-MMS allocation for the constrained instance. This completes the proof of Theorem 2.

6 Identical Valuations and Matroid Constraint This section shows that if the additive valuations of the agents are identical (i.e., vi = vj for all i, j [n]), then an EF1 allocation is guaranteed to exist even under a matroid constraint. Matroids have been studied extensively in mathematics and computer science; see, e.g. [Oxley, 1992]. These structures provide an encompassing framework for representing combinatorial constraints; in particular, the cardinality constraints

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

considered in the previous sections correspond to a particular matroid, called the partition matroid. Formally, a matroid is deﬁned as a pair ([m], I) where [m] is the ground set of elements and I referred to as independent sets is a nonempty collection of subsets of [m] that satisﬁes: (i) Hereditary property: If B I and A B, then A I, and (ii) Independent Set Exchange: If A, B I and |A| < |B|, then there exist an element x B \ A such that A {x} I. We consider a fair division instance [m], [n], (vi)i [n], M where M denotes the set of all allocations which satisfy the underlying matroid constraint, M := {A = (A1, . . . , An) Πn([m]) | Ai I for all i [n]}. Here, the main result is as follows Theorem 3. Every fair division instance [m], [n], (vi)i [n], M under additive, identical valuations and matroid constraint, M = , admits an EF1 allocation.

Proof. We establish the result by showing that an allocation which maximizes the Nash Social Welfare over the set M is necessarily EF1. For an allocation A = (A1, . . . , An), the Nash Social Welfare (NSW) is deﬁned as the geometric mean of the agents valuations, NSW(A) := (Q i [n] vi(Ai))1/n. Let v( ) denote identical, additive valuations of the agents. We assume v(g) > 0 for all g [m] and consider an optimal allocation A arg max B M NSW(B), which satisﬁes

NSW(A) > 0.10 We will prove that A is EF1. Since A M, the stated claim follows. Say, for contradiction, that A is not an EF1 allocation, then we will show that there exists another allocation A M along with agents i and j, such that A h = Ah, for all other agents h [n] \ {i, j}, and min{v(A i), v(A j)} > min{v(Ai), v(Aj)}. The last inequality and the fact that v(A i) + v(A j) = v(Ai) + v(Aj) imply v(A i) v(A j) > v(Ai) v(Aj). Therefore, we get NSW(A ) > NSW(A), which contradicts the optimality of A. Note that, if A is not EF1 then there exists a pair of agents i, j such that

(E) : v(Ai) < v(Aj) v(g) for all g Aj.

Note that if there exists a good g in Aj such that Ai {g} is independent (i.e., Ai {g} I), then swapping g from Aj to Ai gives us the desired allocation A (with a strictly higher NSW than A). Hence, we analyze the case in which no such good exists. In particular, we have Ai g / I for all g Aj. This condition implies that |Ai| |Aj|; otherwise, the Independent Set Exchange property of matroids would ensure the existence of a good g Aj such that Ai {g} I. Write t := |Aj|. Let ˆAi denote a subset of Ai of cardinality t and hence, ˆAi is also independent by the Hereditary property of independent sets of matroids. Since ˆAi and Aj are independent and | ˆAi| = |Aj| = t, there exist t componentwise distinct pairs of goods {(gi z, gj z) ( ˆAi, Aj) | z [t]}

10If the optimal NSW over M is zero, then it must be the case that we have less than n goods. For such an instance, an allocation wherein each agent gets at most one good is both feasible and EF1.

such that ( ˆAi \ {gi z}) {gj z} and (Aj \ {gj z}) {gi z} are independent for all z [t] [Goemans, 2009]. Since the pairs are distinct, Aj = {gj z | z [t]} and ˆAi = {gi z | z [t]}. In addition, the envy between agent i and j (i.e., v(Aj) > v(Ai) v( ˆAi)) implies that there exists index y [t] for which v(gj y) > v(gi y). Consider the allocation A wherein A i = (Ai \ {gi y}) {gj y}, A j = (Aj \ {gj y}) {gi y}, and A h = Ah for all other agents. Note that v(A i) = v(Ai) + v(gj y) v(gi y) > v(Ai). Furthermore, v(A j) = v(Aj) v(gj y) + v(gi y) > v(Ai); the last inequality follows from (E). Hence, min{v(A i), v(A j)} > v(Ai) = min{v(Ai), v(Aj)}, which implies that the NSW of A is higher than that of A. This, by contradiction, completes the proof.

7 Conclusion and Future Work

This paper extends the active line of work on fair division of indivisible goods and shows that fairness guarantees are not lost by imposing cardinality constraints. In particular, we show that EF1 allocations are guaranteed to exist even under cardinality constraints. Note that, though the round-robin method [Caragiannis et al., 2016] and cycle-elimination algorithm [Lipton et al., 2004] efﬁciently ﬁnd EF1 allocations in the unconstrained setting, these algorithms can lead to an allocation which does not satisfy the cardinality constraints. In this paper we bypass this issue by combining the round-robin method with envy graphs in an interesting manner. The universality of EF1 is further strengthened by our result which shows that if the agents valuations are identical (and additive), then fair (EF1) allocations exist even under matroid constraints. Establishing such a guarantee along with computational results for heterogeneous valuations (additive and beyond) remains an interesting direction of future work.11

We also show that, even under cardinality constraints, approximate maximin fair allocations always exist and can be computed efﬁciently. This result is obtained by reducing the constrained version of the problem (with additive valuations) to an unconstrained one (with submodular valuations). This reduction might be useful for addressing other constrained, fair division problems. Going forward it would be quite relevant to study fair division, both unconstrained and constrained, among strategic agents.

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.

11In and of itself, the approach used in Section 6 does not establish such a guarantee: one can construct instances where the agents have additive (but different) valuations and the allocation that maximizes the Nash social welfare, subject to cardinality constraints, is not EF1.

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

[Amanatidis et al., 2015] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation Algorithms for Computing Maximin Share Allocations. In 42nd International Colloquium on Automata, Languages, and Programming, ICALP, pages 39 51, 2015.

[Barman and Krishnamurthy, 2017] Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation Algorithms for Maximin Fair Division. In ACM Conference on Economics and Computation, EC, pages 647 664, 2017.

[Barman et al., 2018] Siddharth Barman, Arpita Biswas, Sanath Kumar Krishnamurthy, and Y. Narahari. Groupwise Maximin Fair Allocation of Indivisible Goods. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence, 2018.

[Bouveret and Lemaˆıtre, 2014] Sylvain Bouveret and Michel Lemaˆıtre. Characterizing Conﬂicts in Fair Division of Indivisible Goods using a Scale of Criteria. In International Conference on Autonomous Agents and Multi-Agent Systems, pages 1321 1328, 2014.

[Bouveret et al., 2017] Sylvain Bouveret, Katar ına Cechl arov a, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair Division of a Graph. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, IJCAI, pages 135 141, 2017.

[Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D. Procaccia. Handbook of Computational Social Choice. Cambridge University Press, 2016.

[Budish et al., 2016] Eric Budish, G erard P Cachon, Judd B Kessler, and Abraham Othman. Course Match: A largescale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2):314 336, 2016.

[Budish, 2011] Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6):1061 1103, 2011.

[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 ACM Conference on Economics and Computation, EC, pages 305 322, 2016.

[Endriss, 2017] Ulle Endriss. Trends in Computational Social Choice. Elsevier, 2017.

[Ferraioli et al., 2014] Diodato Ferraioli, Laurent Gourv es, and J erˆome Monnot. On Regular and Approximately Fair Allocations of Indivisible Goods. In International conference on Autonomous Agents and Multi-Agent Systems, AAMAS, pages 997 1004, 2014.

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

[Ghodsi et al., 2017] Mohammad Ghodsi, Mohammad Taghi Haji Aghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvement and generalization. ar Xiv preprint ar Xiv:1704.00222, 2017. [Goemans, 2009] M Goemans. Lecture notes on Matroid Intersection (Lecture 11). Massachusetts Institute of Technology, Combinatorial Optimization, 2009. [Goldman and Procaccia, 2014] Jonathan R. Goldman and Ariel D. Procaccia. Spliddit: unleashing fair division algorithms. SIGecom Exchanges, 13(2):41 46, 2014. [Gourv es and Monnot, 2017] Laurent Gourv es and J erˆome Monnot. Approximate Maximin Share Allocations in Matroids. In 10th International Conference on Algorithms and Complexity, CIAC, pages 310 321, 2017. [Gourv es et al., 2014] Laurent Gourv es, J erˆome Monnot, and Lydia Tlilane. Near fairness in matroids. In Proceedings of the 21st European Conference on Artiﬁcial Intelligence, ECAI, pages 393 398, 2014. [Kurokawa et al., 2016] David Kurokawa, Ariel D. Procaccia, and Junxing Wang. When Can the Maximin Share Guarantee Be Guaranteed? In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence, pages 523 529, 2016. [Lipton et al., 2004] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On Approximately Fair Allocations of Indivisible Goods. In ACM conference on Electronic Commerce, EC, pages 125 131, 2004. [Moulin, 1990] Herv e Moulin. Uniform Externalities: Two axioms for fair allocation. Journal of Public Economics, 43(3):305 326, 1990. [Oxley, 1992] James G Oxley. Matroid Theory, 1992. [Procaccia and Wang, 2014] Ariel D Procaccia and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. In ACM Conference on Economics and Computation, EC, pages 675 692, 2014. [Stromquist, 1980] Walter Stromquist. How to Cut a Cake Fairly. The American Mathematical Monthly, 87(8):640 644, 1980. [Varian, 1974] Hal R Varian. Equity, Envy, and Efﬁciency. Journal of Economic Theory, 9(1):63 91, 1974.

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