Fair Division Under Cardinality Constraints

1 Introduction

A large body of recent work in algorithmic game theory, artificial 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 finding fair allocations of indivisible goods have been implemented in specific 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 freeness 1 - 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 defined by Budish [Budish, 2011] and they, respectively, provide a cogent analogue of envy-freeness and proportionality 3 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 efficiently [Lipton et al., 2004]. Furthermore, under additive valuations, this notion of fairness is compatible with Pareto efficiency [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 defined as the maximum value that an agent can guarantee for herself if she were to

1 An 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].

2 If we have a single indivisible good and two agents, then in any allocation, the losing agent is bound to be envious.

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

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 find 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 efficient 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 specified on the number of goods that can be allocated from each category to any agent. Here, the objective is to find a fair allocation in which the subset of goods assigned to any agent satisfies 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 find 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

4 For additive valuations, Ghodsi et al. [Ghodsi et al., 2017] provide an improved approximation guarantee of 3/4.

5 The 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, finds an EF1 allocation in polynomial time (Theorem 1).
• 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 defined 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.
• 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 RelatedWork

The fairness notions EF1 and MMS were defined 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, efficient 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]. Specifically, for submodular valuations Ghodsi et al. [Ghodsi et al., 2017] have developed an efficient algorithm for computing 1/3-MMS allocations.

As mentioned previously, the work on fair division of indivisible goods is primarily confined 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 efficiently 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 efficiently compute 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 satisfies 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] ↦→ R+ is additive, i.e., for all agents i ∈ [n] and subsets S ⊆ [m], vi(S) = ∑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 finding fair allocations which satisfy given cardinality constraints. Specifically, 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 find 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

6 Note that the set F might be exponential in size, but it is specified in an efficient 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 defined as

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 find 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 finding a feasible EF1 allocation 7 .

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 efficient algorithms for finding 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 finding an allocation A which is not only EF1, but also feasible, i.e., A ∈ F.

ALG 1 is based on an interesting modification 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 GreedyRound-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

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

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 = (A01 , . . . ,A0n ) with A0i ← ∅ 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 Ahi ←Ah-1 i ∪Bh i for all i ∈ [n].
• 6: Using Lemma 1, update Ah = (Ah1 , . . . ,Ahn ) 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) ∈ argmaxg∈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 graph 8 G(Ah ). It was established in [Lipton et al., 2004] that one can always efficiently 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 find 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 acyclic directed graph G(Ah ). This new ordering is then used for the next category of goods.

8 An envy graph, for an allocation A, is a directed graph that captures the envy between agents in A. Specifically, 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).

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 satisfies: 9

In Lemma 2 we show that, for each h ∈ [ℓ], the partial allocation obtained after the allocating the first h categories, Ah , is EF1. Since Algorithm 1 allocates all the m goods, the final 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 satisfies 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, ∑T -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 first 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 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 π.

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

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(Aha ) ≥ va(Ahb ) - va(g), for some g ∈ Ahb . Summing the last two inequalities and noting that Ah+1 a = Aha ∪ Bh+1 a and Ah+1 b = Ahb ∪ 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 final 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 define 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).

Here, Topki (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(·) (defined 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 satisfies kh ≥ |Ch| n , then for each agent

Proof. We fix an agent i ∈ [n] and first show that the left-hand side of the stated equality is upper bounded by the right-hand side. Write (A∗1 , . . . ,A∗n ) ∈ argmax(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 ) ∈ argmax(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 satisfied. That is, we can obtain an allocation, say B′ = (B′1 , . . . ,B′n ) ∈ F, which is feasible and satisfies 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 efficiently 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 efficiently find 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 efficiently convert A into a feasible allocation B ∈ F which satisfies 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 andMatroid 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 considered in the previous sections correspond to a particular matroid, called the partition matroid. Formally, a matroid is defined 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 satisfies: (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 defined as the geometric mean of the agents' valuations, NSW(A) := (∏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 ∈ argmax B∈M NSW(B), which satisfies

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

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 {(giz , gjz ) ∈ ( ˆ Ai,Aj) | z ∈ [t]}

10 If 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 \ {giz }) ∪ {gjz } and (Aj \ {gjz }) ∪ {giz } are independent for all z ∈ [t] [Goemans, 2009]. Since the pairs are distinct, Aj = {gjz | z ∈ [t]} and ˆ Ai = {giz | 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(gjy ) > v(giy ).

Consider the allocation A′ wherein A′i = (Ai \ {giy }) ∪ {gjy }, A′j = (Aj \ {gjy }) ∪ {giy }, and A′h = Ah for all other agents. Note that v(A′i ) = v(Ai) + v(gjy ) - v(giy ) > v(Ai). Furthermore, v(A′j ) = v(Aj) - v(gjy ) + v(giy ) > 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 FutureWork

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] efficiently find 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 guaranteealong 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 efficiently. 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 PhD Fellowship Award.

11 In 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.