Simplification and Improvement of MMS Approximation

1 Introduction

Fair division of a set of indivisible goods among n agents with diverse preferences is a fundamental problem in many areas, including game theory, social choice theory, and multi-agent systems. We assume that agents have additive valuations. Maximin share (MMS) is one of the most popular fairness notion in this setting, introduced by Budish [2011], which has attracted a lot of attention in recent years. It is preferred by participating agents over other notions, as shown in reallife experiments by [Gates et al., 2020]. Every agent i has an associated threshold, called her maximin share (MMSi), defined as the maximum value i can get by partitioning the set of goods into n bundles (one for each agent) and picking a lowest-value bundle. An agent considers an allocation to be fair if she receives goods of total value at least her MMS.

A natural question is whether we can always find an allocation that gives each agent her MMS. Surprisingly, such an allocation need not always exist. Procaccia and Wang [2014] showed examples for any n ≥ 3 in which MMS allocations do not exist. This motivated them to initiate the study of approximate MMS. Agent i considers an allocation to be αMMS fair to her for α ∈ (0, 1) if she receives goods of total value at least α · MMSi. They showed that a 2/3-MMS allocation always exists. Ghodsi et al. [2018] improved this result by showing the existence of a 3/4-MMS using a sophisticated algorithm with a very involved analysis. More recently, Garg and Taki [2021] improved this result to ( 34 + 1 12n )-MMS using a simple combinatorial algorithm, though their analysis remains quite involved. Furthermore, there is no tight example known for this algorithm, so it is unclear if this is the best factor of the approach.

A complementary problem is to construct examples with the smallest upper bound on α, say α∗ , such that α-MMS allocations do not always exist for α > α∗ . Feige, Sapir, and Tauber [2021] recently obtained the best-known α∗ = 1 - 1/n4 for n ≥ 4. They also gave an improved value of α∗ = 39/40 for the special case of n = 3 agents. However, there is still a substantial gap between the lower and upper bounds.

In this paper, we investigate the Garg-Taki algorithm and obtain the following results.

• A significantly simple analysis of the algorithm.
• An improved bound of ( 34 + min( 1 36 , 3 4(4n-1) ))- MMS by slightly modifying the algorithm. Since min( 1 36 , 3 4(4n-1) ) ≥ 1 12n for all n ≥ 3, this provides noticeable improvement for small n. We note that 34 + 1 12n was the best-known bound for n > 4.
• A tight example of the Garg-Taki's and our algorithms, which shows the limits of this approach in obtaining a better bound of 34 + O(1). Interestingly, our example only utilizes identical valuations, for which MMS allocations are known to exist.

Our simplified analysis not only helped us to improve the MMS bound but also, together with the tight example, shed more light on why and for which instances the algorithm cannot do better. We believe that these results would help reduce the gap further between the lower and upper bounds.

1.1 RelatedWork

Computing the maximin share of any agent is NP-hard (even for 2 agents) 1 , but a PTAS exists [Woeginger, 1997]. Procaccia and Wang [2014] showed the existence of a 2/3-MMS allocation, which can also be computed in polynomial time for a constant n. Later, the algorithm was modified [Amanatidis et al., 2017b; Kurokawa et al., 2018] to compute a (2/3-ε)- MMS allocation in polynomial time (here ε > 0 is a parameter of the algorithm, whose running time increases with 1/ε). Barman and Krishnamurthy [2020] gave a simple greedy algorithm with an involved analysis to find a 2 3 (1+ 1 3n-1 )-MMS allocation. Garg et al. [2018] gave a simple algorithm with a simple analysis to output a 2/3-MMS allocation.

1 by a straightforward reduction from the partition problem.

Ghodsi et al. [2018] showed the existence of a 3/4-MMS allocation using a complicated algorithm and analysis. Garg and Taki [2021] showed how to find a 3/4-MMS allocation in strongly polynomial time, and showed that ( 34 + 1 12n )-MMS allocations exist. Their results use simple algorithms, but their analysis is still quite involved.

Special cases. Amanatidis et al. [2017b] showed that when m ≤ n + 3, an MMS allocation always exists. Feige et al. [2021] improved this to m ≤ n+5. For n = 2, MMS allocations always exist [Bouveret and Lemaˆıtre, 2016]. For n = 3, the MMS approximation was improved from 3/4 [Procaccia and Wang, 2014] to 7/8 [Amanatidis et al., 2017b] to 8/9 [Gourv`es and Monnot, 2019], and then to 11/12 [Feige and Norkin, 2022]. For n = 4, Ghodsi et al. [2018] showed the existence of 4/5-MMS.

Experiments. Bouveret and Lemaˆıtre [2016] showed that MMS allocations usually exist (for data generated randomly using uniform or Gaussian valuations). Amanatidis et al. [2017b] gave a simple and efficient algorithm and showed that when the valuation of each good is drawn independently and randomly from the uniform distribution on [0, 1], the algorithm's output is an MMS allocation with high probability when the number of goods or agents is large. Kurokawa et al. [2016] gave a similar result for arbitrary distributions of sufficiently large variance.

Chores. MMS can be analogously defined for fair division of chores. MMS allocations do not always exist for chores [Aziz et al., 2017], which motivated the study of approximate MMS [Aziz et al., 2017; Barman and Krishnamurthy, 2020; Huang and Lu, 2021], with the current best approximation ratio being 11/9. For 3 agents, 19/18-MMS allocations exist [Feige and Norkin, 2022].

Other settings. MMS has also been studied for non-additive valuations [Barman and Krishnamurthy, 2020; Ghodsi et al., 2018; Li and Vetta, 2021]. Generalizations have been studied where restrictions are imposed on the set of allowed allocations, like matroid constraints [Gourv`es and Monnot, 2019], cardinality constraints [Biswas and Barman, 2018], and graph connectivity constraints [Bei et al., 2022; Truszczynski and Lonc, 2020]. Stretegyproof versions of fair division have also been studied [Barman et al., 2019; Amanatidis et al., 2016; Amanatidis et al., 2017a; Aziz et al., 2019]. MMS has also inspired other notions of fairness, like weighted MMS [Farhadi et al., 2019], AnyPrice Share (APS) [Babaioff et al., 2021], Groupwise MMS [Barman et al., 2018; Chaudhury et al., 2021], 1-out-of-d share [Hosseini and Searns, 2021], and self-maximizing shares [Babaioff and Feige, 2022].

1.2 Outline of This Paper

In Section 2, we give formal definitions, notations, and preliminaries. In Section 3, we give a very simple proof that (a minor modification of) the Garg-Taki algorithm [2021] outputs a 3/4-MMS allocation. In Section 4, we improve the analysis to show that the output is a ( 3 4 +min( 1 36 , 3 4(4n-1) ))- MMS allocation. In Section 5, we give a tight example for our algorithm.

2 Preliminaries

For any non-negative integer n, let [n] := {1, 2, . . . , n}.

A fair division instance I is specified by a triple (N, M, v), where N is the set of agents, M is the set of goods, and vi,g is the value of good g ∈ M for agent i ∈ N. For a set S of goods, define vi(S) := ∑g∈S vi,g. Then vi is called agent i's valuation function. Intuitively, vi(S) is a measure of how valuable S is to i. For ease of notation, we write vi(g) instead of vi({g}). We can assume without loss of generality that N = [n] and M = [m], where n = |N| and m = |M| (though when dealing with multiple related fair division instances, not making this assumption can sometimes simplify notation).

For a set S of goods, let Πn(S) denote the set of partitions of S into n bundles. For any valuation function u, define

When the fair division instance (N,M, v) is clear from context, we write MMSi instead of MMS|N| vi (M) for conciseness.

2.1 Ordered Instance

Definition 1. A fair division instance (N,M, v) is called ordered if there is an ordering [g1, g2, . . . , g|M|] of goods M such that for each agent i, vi,g1 ≥ vi,g2 ≥ . . . ≥ vi,g|M| .

We will now see how to reduce the problem of finding an α-MMS allocation to the special case of ordered instances.

Definition 2. For the fair division instance I := (N,M, v), toOrd(I) is defined as the instance (N, [|M|], ̂ v), where for each i ∈ N and j ∈ [|M|], ̂ vi,j is the j th largest number in the multiset {vi,g | g ∈M}.

In Theorem 3.2 of [Barman and Krishnamurthy, 2020], it was shown that the transformation toOrd is α-MMSpreserving, i.e., for a fair division instance I, given an αMMS allocation of toOrd(I), we can compute an α-MMS allocation of I in polynomial time. (The proof is based on ideas by Bouveret and Lemaˆıtre [2016]).

2.2 Valid Reductions

We use a technique called valid reduction, that helps us reduce a fair division instance to a smaller instance. This technique has been implicitly used in [Bouveret and Lemaˆıtre, 2016; Kurokawa et al., 2016; Kurokawa et al., 2018; Amanatidis et al., 2017b; Ghodsi et al., 2018; Garg et al., 2018] and explicitly used in [Garg and Taki, 2021].

Definition 3 (Valid reduction). In a fair division instance (N,M, v), suppose we give the goods S to agent i. Then we are left with a new instance (N \ {i},M \ S, v). Such a transformation is called a valid α-reduction if both of these conditions hold:

Note that valid reductions are α-MMS-preserving, i.e., if A is an α-MMS allocation of an instance obtained by performing a valid reduction, then we can get an α-MMS allocation of the original instance by giving goods S to agent i and allocating the remaining goods as per A. A valid reduction, therefore, helps us reduce the problem of computing an α-MMS allocation to a smaller instance.

We now describe four standard transformations, called reduction rules, and show that they are valid reductions.

Definition 4 (Reduction rules). Consider an ordered fair division instance (N,M, v), where M := {g1, . . . , g|M|} and vi,g1 ≥ . . . ≥ vi,g|M| for every agent i. Define

1. S3 := {g2|N|-1, g2|N|, g2|N|+1} if |M| ≥ 2|N|+1, else S3 := ∅.

Reduction rule Rk(α): If vi(Sk) ≥ αMMSi for some agent i, then give Sk to i.

A fair division instance is called Rk(α)-irreducible if Rk(α) cannot be applied, i.e., vi(Sk) < αMMSi for every agent i (otherwise it is called Rk(α)-reducible). An instance is called totally-α-irreducible if it is Rk(α)-irreducible for all k ∈ [4].

Lemma 1 (Lemma 3.1 in [Garg and Taki, 2021]). For an ordered instance and for α ≤ 1, R1(α), R2(α), and R3(α) are valid α-reductions. For an ordered instance and for α ≤ 3/4, if the instance is R1(α)-irreducible and R3(α)-irreducible, then R4(α) is a valid α-reduction.

Lemma 2. Let I := ([n], [m], v) be an ordered instance where vi,1 ≥ . . . ≥ vi,m for each agent i. For any k ∈ [3], if I is Rk(α)-irreducible, then for each agent i and every good j > (k - 1)n, we have vi,j < αMMSi/k.

Proof. Since I is Rk(α)-irreducible, we get vi(Sk) < αMMSi for each agent i. Let t := (k -1)n+1. Then

Lemma 3. If an ordered instance (N,M, v) is R1(α)- irreducible for any α ≤ 1, then |M| ≥ 2|N|.

Proof. Assume |M| < 2|N|. Pick any agent i ∈ N. Let P be an MMS partition of agent i. Then some bundle Pj contains a single good {g}. Then vi,g = vi(Pj) ≥ MMSi. Hence, the instance is not R1(α)-irreducible for any α ≤ 1. This is a contradiction. Hence, |M| ≥ 2|N|.

Algorithm 1 normalize((N, M, v))

• 1: for i ∈ N do
• 2: Compute agent i's MMS partition P (i) .
• 3: ∀j ∈ N, ∀g ∈ P (i) j , let ̂ vi,g := vi,g/vi(P (i) j ).
• 4: end for
• 5: return (N,M, ̂ v).

We would like to convert fair division instances into totally-α-irreducible instances. This can be done using a very simple algorithm, which we call reduceα. This algorithm works for α ≤ 3/4. It takes an ordered fair division instance as input and repeatedly applies the reduction rules R1(α), R2(α), R3(α), and R4(α) until the instance becomes totallyα-irreducible. The reduction rules can be applied in arbitrary order, except that R4(α) is only applied when R1(α) and R3(α) are inapplicable.

Note that the application of reduction rules changes the number of agents and goods, which affects subsequent reduction rules. More precisely, the sets S1, S2, S3, S4 (as defined in Definition 4) can change after applying a reduction rule. So, for example, it is possible that an instance is R2(α)- irreducible, but after applying R3(α), the resulting instance is R2(α)-reducible.

2.3 Normalized Instance

Definition 5 (Normalized instance). A fair division instance (N,M, v) is called normalized if for every agent i, there is a partition P (i) := (P (i) 1 , . . . , P (i) |N| ) of M such that vi(P (i) j ) = 1 ∀j ∈ N.

Note that for a normalized instance, every agent's MMS value is 1. Furthermore, for each agent i and for every MMS partition Q of agent i, we have vi(Qj) = 1 ∀j ∈ N, since each partition has total value at least 1 and ∑j∈N vi(Qj) =

The algorithm normalize (c.f. Algorithm 1) converts a fair division instance to a normalized instance.

Lemma 4. Let (N,M, ̂ v) = normalize((N,M, v)). Then for any allocation A, vi(Ai) ≥ ̂ vi(Ai)MMS|N| vi (M) for all i ∈ N.

Lemma 4 implies that normalize is α-MMS-preserving, since if A is an α-MMS allocation for the normalized instance (N, M, ̂ v), then A is also an α-MMS allocation for the original instance (N,M, v).

3 Simple Proof for Existence of 3/4-MMS Allocations

We give an algorithm, called approxMMS (c.f. Algorithm 2), that takes as inputs a fair division instance and an approximation factor α, and outputs an α-MMS allocation. It works in three major steps:

Algorithm 2 approxMMS(I, α)

Input: Fair division instance I = (N,M, v) and approximation factor α.

Output: Allocation A = (A1, . . . , An).

• 1: ̂ I = toOrd(normalize(reduceα(toOrd(I))))
• 2: ̂ A = bagFill(̂ I, α).
• 3: Use ̂ A to compute an allocation A for I with the same MMS approximation as ̂ A. (This can be done since Sections 2.1, 2.2 and 2.3 show that toOrd, reduceα, and normalize are α-MMS-preserving.)

4: return A

1. Reduce the problem of finding an α-MMS allocation to the special case where the instance is Ordered, Normalized, and totally-α-Irreducible (ONI).
2. Compute an α-MMS allocation for this special case using the bagFill algorithm (c.f. Algorithm 3).
3. Convert this allocation for the special case to an allocation for the original fair division instance.

We describe steps 1 and 3 in Section 3.1 and step 2 in Section 3.2. In this section, we only consider the case where α = 3/4. In Section 4, we slightly modify approxMMS so that it works for α = 3 4 +min( 1 36 , 3 4(4n-1) ). Our algorithm approxMMS is almost the same as the algorithm of Garg and Taki [2021]. The only difference is that, unlike them, we ensure that the output of step 1 is normalized.

3.1 Obtaining an Ordered Normalized Irreducible (ONI) Instance

Lemma 5. Let I be a fair division instance. Let ̂ I := toOrd(normalize(reduce3/4(toOrd(I)))). Then ̂ I is ordered, normalized, and totally-3/4-irreducible. Furthermore, the transformation of I to ̂ I is 3/4-MMS-preserving, i.e., a 3/4-MMS allocation of ̂ I can be used to obtain a 3/4-MMS allocation of I.

Proof. Let I (1) := toOrd(I). Then I (2) := reduce3/4(I (1) ) is totally-3/4-irreducible and ordered, since the application of reduction rules preserves orderedness.

Let I (3) := normalize(I (2) ). By Lemma 4, normalize does not increase the ratio of a good's value to the MMS value. Hence, ̂ I is totally-3/4-irreducible. ̂ I is also normalized, since for each agent, toOrd only changes the identities of the goods, but the (multi-)set of values of the goods remains the same. Hence, ̂ I is ordered, normalized, and totally3/4-irreducible.

Since toOrd, reduce3/4, and normalize are 3/4-MMSpreserving operations, their composition is also 3/4-MMSpreserving.

The order of operations is important here, as well as the need to call toOrd twice, since reduce requires the input to be ordered, reduce may not preserve normalizedness, and normalize may not preserve orderedness.

Algorithm 3 bagFill(I, α)

Input: Ordered instance I = ([n], [m], v) with m ≥ 2n and approximation factor α.

Output: (Partial) allocation A = (A1, . . . , An).

1: for k ∈ [n] do 2: Bk = {k, 2n+1-k}. 3: end for 4: UG = [m] \ [2n] // unassigned goods 5: UA = [n] // unsatisfied agents 6: UB = [n] // unassigned bags 7: while UA ̸= ∅ do // loop invariant: |UA| = |UB| 8: if ∃i ∈ UA, ∃k ∈ UB, such that vi(Bk) ≥ α then 9: // assign the kth bag to agent i: 10: Ai = Bk 11: UA = UA \ {i} 12: UB = UB \ {k} 13: else if UG ̸= ∅ then 14: g = arbitrary good in UG 15: k = arbitrary bag in UB 16: // assign g to the kth bag: 17: Bk = Bk ∪ {g}. 18: UG = UG \ {g} 19: else 20: error: we ran out of goods. return null. 21: end if 22: end while 23: return (A1, . . . ,An)

Garg and Taki [2021] transform the instance as reduce3/4(toOrd(I)), since they do not need the input to be normalized.

3.2 3/4-MMS Allocation of ONI Instance

Let ([n], [m], v) be a fair division instance that is ordered, normalized, and totally-3/4-irreducible (ONI). Without loss of generality, assume that vi,1 ≥ vi,2 ≥ . . . ≥ vi,m for each agent i.

Our algorithm, called bagFill(I, α), creates n bags, where the j th bag contains goods {j, 2n + 1 - j}. (To create bags in this way, there must be at least 2n goods. This is ensured by Lemma 3.) It then repeatedly adds a good to an arbitrary bag, and as soon as some agent i values a bag more than α, that bag is allocated to i. The algorithm terminates when all agents have been allocated a bag. See Algorithm 3 for a more precise description. (In this section, we set α = 3/4. In Section 4, we set α = 3 4 +min( 1 36 , 3 4(4n-1) ).) bagFill computes a partial allocation, i.e., some goods may remain unallocated. But that can be easily fixed by arbitrarily allocating those goods among the agents.

bagFill(I, α) allocates a bag Bk to agent i only if vi(Bk) ≥ α. Hence, to prove that bagFill(I, 3/4) returns a 3/4-MMS allocation, it suffices to show that bagFill terminates successfully, i.e., line 20 is never executed.

For k ∈ [n], let Bk := {k, 2n + 1 - k} be the initial contents of the kth bag and B′k be the kth bag's contents after bagFill terminates. We consider two groups of agents. Let N 1 be the set of agents who value all the initial bags at most

1. Formally, N 1 := {i ∈ [n] | ∀k ∈ [n], vi(Bk) ≤ 1}. Let N 2 := [n] \ N 1 = {i ∈ [n] | ∃k ∈ [n] : vi(Bk) > 1} be the rest of the agents.

Let UA be the set of agents that did not receive a bag when bagFill terminated. Note that UA is non-empty iff we execute line 20. We first show that all agents in N 1 receive a bag, i.e., UA ∩N 1 = ∅. Then we show that UA ∩N 2 = ∅. Together, these facts establish that bagFill terminates successfully, and hence its output is 3/4-MMS.

Lemma 6. Let ([n], [m], v) be an ordered and normalized fair division instance. For all k ∈ [n] and agent i ∈ [n], if vi,k + vi,2n-k+1 > 1, then vi,2n-k+1 ≤ 1/3 and vi,k > 2/3.

Proof. It suffices to prove vi,2n-k+1 ≤ 1/3 and then vi,k > 2/3 follows. Let P = (P1, . . . , Pn) be an MMS partition of agent i. For j ∈ [k] and j ′ ∈ [2n+1-k], vi,j+vi,j ′ ≥ vi,k+ vi,2n+1-k > 1, since the instance is ordered. Furthermore, j and j ′ cannot be in the same bundle in P, since the instance is normalized. In particular, no two goods from [k] are in the same bundle in P. Hence, assume without loss of generality that j ∈ Pj for all j ∈ [k].

For all j ∈ [k] and j ′ ∈ [2n - k + 1], j ′ ̸∈ Pj. Thus, {k + 1, . . . , 2n - k + 1} ⊆ Pk+1 ∪ . . . ∪ Pn. By pigeonhole principle, there exists a bundle B ∈ {Pk+1, . . . , Pn} that contains at least 3 goods g1, g2, g3 in {k+1, . . . , 2n-k+1}. Hence,

Lemma 7. Let i be any agent. For all k ∈ [n], if vi(Bk) ≤ 1, then vi(B′k ) ≤ 1.

Proof. If B′k = Bk, then the claim obviously holds. Now assume Bk ⊊ B′k . Let g be the last good that was added to B′k . We have vi(B′k \ g) < 3/4, otherwise g would not be added to B′k . Also note that g > 2n and hence vi,g < 1/4 by Lemma 2. Thus, we have

Lemma 8. UA ∩N 1 = ∅, i.e., every agent in N 1 gets a bag.

Proof. For the sake of contradiction, assume UA ∩N 1 ̸= ∅. Hence, ∃i ∈ UA ∩N 1 . Also, for some j ∈ [n], the j th bag is unallocated. Hence, vi(B′j ) < 3/4 and

which is a contradiction. Hence, UA ∩ N 1 = ∅.

Now we prove that bagFill allocates a bag to all agents in N 2 , i.e., UA ∩N 2 = ∅.

Proof. Since i ∈ N 2 , there exists a bag Bk such that vi(Bk) > 1. By Lemma 6, vi,k > 2/3. Thus, vi,1 > 2/3. Moreover,

From now on assume for the sake of contradiction that UA ̸= ∅. Let a be a fixed agent in UA. By Lemma 8, a ∈ N 2 . Let A+ := {k ∈ [n] | va(Bk) > 1}, A- := {k ∈ [n] | va(Bk) < 3/4}, and A0 := {k ∈ [n] | 3/4 ≤ va(Bk) ≤ 1}. We will try to get upper bounds on va(B′k ) for each of the cases k ∈ A+, k ∈ A-, and k ∈ A0 .

Note that n = |A+|+|A-|+|A0 |. Also, n ∈ A- since the instance is R2(3/4)-irreducible, and |A+| ≥ 1 since a ∈ N 2 .

Proof. If B′k = Bk, then va(B′k ) < 3/4 < 5/6. Otherwise, let g be the last good that was added to B′k . Then va(B′k \ {g}) < 3/4, otherwise bagFill would assign B′k \ {g} to agent i instead of adding g to it. Hence,

Let ℓ be the smallest such that for all k ∈ [ℓ +1, n], va,k + va,2n-k+1+ℓ ≤ 1. See Fig. 1 for a better understanding of ℓ. Note that ℓ ≥ 1, since a ∈ N 2 .

Proof. Let S ∈ A+ be the set of min(ℓ, |A+|) smallest indices in A+ and L ∈ A+ be the set of min(ℓ, |A+|) largest indices in A+. Since |A+| ≥ 1 and ℓ ≥ 1, we get |S| = |L| ≥ 1. Note that

By Lemma 6, we get va,2n-k+1 ≤ 1 3 . Since va,k < 3/4 and |S| ≥ 1, we get

If ℓ ≥ |A+|, then |S| = |L| = |A+|, and we are done. Now assume ℓ < |A+|. Then |S| = |L| = ℓ.

Let A+ := {g1, . . . , g|A+|} and g1 < . . . < g|A+|. Then A+ \ S = {gℓ+1, . . . , g|A+|} and A+ \ L = {g1, . . . , g|A+|-ℓ}. The idea is to pair the goods gk+ℓ and 2n - gk + 1 (for k ∈ [|A+| - ℓ]) and prove that their value is at most 1 for agent a.

Since gk+ℓ ≥ gk + ℓ, we get va,gk+ℓ + va,2n-gk+1 ≤ 1 by definition of ℓ. Hence,

Equations (1) and (2) imply Lemma 11.

Proof. By definition of ℓ, there exists a good k ∈ {ℓ, . . . , n} such that va,k + va,2n-k+ℓ > 1. Hence, for all j ∈ [k] and t ≤ [2n-k+ℓ], we have va,j +va,t ≥ va,k +va,2n-k+ℓ > 1. Let P := (P1, . . . , Pn) be an MMS partition of agent a. Then, for j ∈ [k] and t ∈ [2n - k + ℓ], j and t cannot be in the same bundle in P, since the instance is normalized. In particular, no two goods from [k] are in the same bundle in P . Hence, assume without loss of generality that j ∈ Pj for all j ∈ [k]. Thus, [2n - k + ℓ] \ [k] ⊆ Pk+1 ∪ . . . ∪ Pn.

Bundles in {P1, . . . , Pk} can only have goods from [k], [2n] \ [2n - k + ℓ], and [m] \ [2n]. There are k - ℓ goods in [2n] \ [2n-k+ℓ]. Hence, at least ℓ bundles in {P1, . . . , Pk} have just 1 good from [2n]. Let L be the indices of these bundles, i.e., L := {t ∈ [k] | |Pt ∩ [2n]| = 1}. Then

Lemma 13. For all i ∈ N 2 and k ∈ [n], vi(Bk) > 1/2.

Proof. Fix an i ∈ N 2 . Let t be smallest such that vi(Bt) > 1. By Lemma 6, vi,t > 2/3. Hence, for all k ≤ t,

Since vi(Bt) = vi,t + vi,2n-t+1 > 1 and vi,t < 3/4 (by Lemma 2), we get vi,2n-t+1 > 1/4. For all k > t, we have k < 2n - k + 1 < 2n - t + 1. Hence,

Lemma 14. UA∩N 2 = ∅, i.e., every agent in N 2 gets a bag.

Proof. Assume for the sake of contradiction that UA ∩N 2 ̸= ∅. Then, as discussed before, we fix an agent a ∈ UA ∩ N 2 and define A+, A-, A0 , and ℓ.

Hence, |A-| < ℓ/2.

Now we show that there are enough goods in [m] \ [2n] to fill the bags in A-.

By Lemmas 8 and 14, we get that UA = ∅, i.e., every agent gets a bag, and hence, bagFill's output is 3/4-MMS.

4 Better than 3/4-MMS

In this section, we give an overview of how to refine the techniques of Section 3 to get an algorithm that outputs a ( 34 +min( 1 36 , 3 4(4n-1) ))-MMS allocation. The details can be found in Appendix A of the full version of our paper [Akrami et al., 2023].

Theorem 1. For any fair division instance with additive valuations, a ( 34 +min( 1 36 , 3 4(4n-1) ))-MMS allocation exists.

Algorithm approxMMS from Section 3 does not work with α > 3/4, since R4(α) may not be a valid reduction. To fix this, we modify R4(α) using the dummy goods technique from [Garg and Taki, 2021].

Consider the fair division instance ([n], [m], v). When performing R4(α), in addition to giving the goods S4 := {1, 2n + 1} to some agent i for whom vi(S4) ≥ αMMSi, we create a dummy good g where vj(g) := max(0, vj(S4) - MMSj) for each agent j ̸= i. With this change, R4(α) becomes a valid reduction even for α > 3/4. See Appendix A.1 for a proof. Note that dummy goods are fictional, i.e., they exist solely to guide the valid reductions. No agent is allocated a dummy good.

Formally, a fair division instance with dummy goods is represented as a tuple I := (N,M, v,D), where D is the set of dummy goods and M is the set of non-dummy goods. We can extend the concepts of Section 2.1 (ordered instance), Section 2.2 (valid reductions), and Section 2.3 (normalized instance) to instances with dummy goods. See Appendix A.2 for details. In particular, instance (N,M, v,D) is ordered iff (N,M, v) is ordered, and (N,M, v,D) is normalized iff (N, M ∪ D, v) is normalized.

With these modifications, we can extend approxMMS to the case where α > 3/4. approxMMS first transforms the instance into an ordered, normalized, and totally-α-irreducible instance. Then it discards all the dummy goods and allocates the remaining goods using the algorithm bagFill. In Appendix A.3, we show that when α ≤ 3 4 +min( 1 36 , 3 4(4n-1) ), bagFill allocates a bag of value at least α to every agent. Our proof is almost the same as that in Section 3. The main difference is that the analogue of Lemma 14 (Lemma 25 in Appendix A) involves more elaborate algebraic manipulations so that we can get tighter bounds.

5 Tight Example

We give an almost tight example for our algorithm and Garg and Taki's [2021] algorithm. We show that these algorithms' output on this example is not better than ( 34 + 3 8n-4 )-MMS.

Example 1. Consider a fair division instance with n agents and m = 3n - 1 goods. All agents have the same valuation function u, where

Lemma 15. Example 1 is normalized.

Proof. Let M1 := {1, 2} and for i ∈ [n - 1], let Mi+1 := {i+2, 2n+1-i, 2n+i}. Then for any i ̸= j, Mi ∩Mj = ∅. Also, u(M1) = u(1) + u(2) = 1 and for each i ∈ [n - 1],

Define the MMSscore of an allocation as the maximum α such that it is an α-MMS allocation. Formally, for an allocation A := (A1, . . . , An),

Theorem 2. Let I be the fair division instance of Example 1. Let S1 := {1}, S2 := {n, n+1}, S3 := {2n-1, 2n, 2n+1}, S4 := {1, 2n + 1}. Consider a fair division algorithm that either outputs bagFill(I, α) for some α, or allocates the set Sk, for some k ∈ [4], to an agent i, and allocates the remaining goods to the remaining agents in an unspecified way. Let A be the allocation output by this algorithm. Then

Proof. u(S1) = 1/2, u(S2) = u(S4) = (3n- 1)/(4n- 2), and u(S3) = 3n/(4n - 2). Hence, if the algorithm allocates Sk to an agent i, for some k ∈ [4], then that agent will get a bundle of value at most 3n/(4n - 2).

Now suppose that the algorithm outputs bagFill(I, α). Every bag initially has value τ := (3n - 1)/(4n - 2). If α ≤ τ , then no bag receives any more items, and each agent gets a bag of value τ . If α > τ , then we run out of goods and bagFill fails (i.e., returns null), since there are n bags but only n - 1 goods in [m] \ [2n].

6 Conclusion

In fair division of indivisible goods, MMS is one of the most popular notions of fairness, and determining (tight lower and upper bounds on) the maximum α for which α-MMS allocations are guaranteed to exist is an important open problem.

To gain a better understanding of this problem, we thoroughly studied Garg and Taki's [2021] algorithm for obtaining 3/4-MMS allocations. We considerably simplified its analysis and our techniques helped improve the best-known MMS approximation factor to 3 4 + min( 1 36 , 3 4(4n-1) ). Furthermore, we presented a tight example that reveals a fundamental barrier towards improving the MMS approximation guarantee using techniques in [Garg and Taki, 2021].

Acknowledgements

Jugal Garg and Eklavya Sharma were supported by NSF Grant CCF-1942321.