# simplification_and_improvement_of_mms_approximation__7fa3ed3c.pdf

Simplification and Improvement of MMS Approximation

Hannaneh Akrami1,2 , Jugal Garg3 , Eklavya Sharma3 and Setareh Taki4

1Max Planck Institute for Informatics, Germany 2Graduiertenschule Informatik, Universit at des Saarlandes, Germany 3University of Illinois at Urbana-Champaign, USA 4Grubhub, USA hakrami@mpi-inf.mpg.de, {jugal,eklavya2}@illinois.edu, Staki@grubhub.com

We consider the problem of fairly allocating a set of indivisible goods among n agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. The Garg-Taki algorithm gives the current best approximation factor of ( 3

4 + 1 12n). Most of these results are based on complicated analyses, especially those providing better than 2/3 factor. Moreover, since no tight example is known of the Garg-Taki algorithm, it is unclear if this is the best factor of this approach. In this paper, we significantly simplify the analysis of this algorithm and also improve the existence guarantee to a factor of ( 3

36, 3 16n 4)). For small n, this provides a noticeable improvement. Furthermore, we present a tight example of this algorithm, showing that this may be the best factor one can hope for with the current techniques.

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 ( 3

4 + 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 ( 3

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 3

4 + 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 3

4 + 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 Related Work Computing the maximin share of any agent is NP-hard (even for 2 agents)1, but a PTAS exists [Woeginger, 1997]. Procac-

1by a straightforward reduction from the partition problem.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

cia 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. 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 ( 3

4 + 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], Any Price 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

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) := P 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

MMSn u(S) := max X Πn(S)

n min j=1 u(Xj).

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), to Ord(I) is defined as the instance (N, [|M|], bv), where for each i N and j [|M|], bvi,j is the jth largest number in the multiset {vi,g | g M}.

In Theorem 3.2 of [Barman and Krishnamurthy, 2020], it was shown that the transformation to Ord is α-MMSpreserving, i.e., for a fair division instance I, given an αMMS allocation of to Ord(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].

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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: 1. vi(S) αMMS|N| vi (M).

2. MMS|N| 1 vj (M \S) MMS|N| vj (M) for all j N \{i}.

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. S1 := {g1}. 2. S2 := {g|N|, g|N|+1} if |M| |N| + 1, else S2 := .

3. S3 := {g2|N| 1, g2|N|, g2|N|+1} if |M| 2|N|+1, else S3 := . 4. S4 := {g1, g2|N|+1} if |M| 2|N| + 1, else S4 := .

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

αMMSi > vi(Sk) = X

g Sk vi,g |Sk| min g Sk vi,g = kvi,t.

Hence, j t, we have vi,j vi,t < αMMSi/k.

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 bvi,g := vi,g/vi(P (i) j ). 4: end for 5: return (N, M, bv).

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 P j N vi(Qj) =

vi(M) = P j N vi(P (i) j ) = |N|. The algorithm normalize (c.f. Algorithm 1) converts a fair division instance to a normalized instance. Lemma 4. Let (N, M, bv) = normalize((N, M, v)). Then for any allocation A, vi(Ai) bvi(Ai)MMS|N| vi (M) for all i N.

Proof. Let βi := MMSn vi(M). For any good g P (i) j ,

bvi,g = vi,g/vi(P (i) j ) vi,g/βi. Hence, vi,g bvi,gβi. Hence, vi(Ai) bvi(Ai)βi.

Lemma 4 implies that normalize is α-MMS-preserving, since if A is an α-MMS allocation for the normalized instance (N, M, bv), 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 approx MMS (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:

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Algorithm 2 approx MMS(I, α) Input: Fair division instance I = (N, M, v) and approximation factor α. Output: Allocation A = (A1, . . . , An).

1: b I = to Ord(normalize(reduceα(to Ord(I)))) 2: b A = bag Fill(b I, α). 3: Use b A to compute an allocation A for I with the same MMS approximation as b A. (This can be done since Sections 2.1, 2.2 and 2.3 show that to Ord, 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 bag Fill 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 approx MMS so that it works for α = 3

36, 3 4(4n 1)). Our algorithm approx MMS 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 b I := to Ord(normalize(reduce3/4(to Ord(I)))). Then b I is ordered, normalized, and totally-3/4-irreducible. Furthermore, the transformation of I to b I is 3/4-MMS-preserving, i.e., a 3/4-MMS allocation of b I can be used to obtain a 3/4-MMS allocation of I.

Proof. Let I(1) := to Ord(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, b I is totally-3/4-irreducible. b I is also normalized, since for each agent, to Ord only changes the identities of the goods, but the (multi-)set of values of the goods remains the same. Hence, b I is ordered, normalized, and totally3/4-irreducible. Since to Ord, 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 to Ord twice, since reduce requires the input to be ordered, reduce may not preserve normalizedness, and normalize may not preserve orderedness.

Algorithm 3 bag Fill(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(to Ord(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 bag Fill(I, α), creates n bags, where the jth 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

36, 3 4(4n 1)).) bag Fill 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. bag Fill(I, α) allocates a bag Bk to agent i only if vi(Bk) α. Hence, to prove that bag Fill(I, 3/4) returns a 3/4-MMS allocation, it suffices to show that bag Fill 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 bag Fill terminates. We consider two groups of agents. Let N 1 be the set of agents who value all the initial bags at most

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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 bag Fill 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 bag Fill 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,

vi,2n k+1 min g {g1,g2,g3} vi,g 1

g {g1,g2,g3} vi,g

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

vi(B k) = vi(B k \ g) + vi,g < 3

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 jth bag is unallocated. Hence, vi(B j) < 3/4 and

n = vi(M) = vi(B j) + X

k [n]\{j} vi(B k)

(since M = S k [n] B k)

< (n 1) + 3

4, (by Lemma 7)

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

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

Lemma 9. i N 2 = vi,2n+1 < 1/12.

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,

vi,2n+1 < 3

4 vi,1 (since R4(3/4) is not applicable)

12. (since vi,1 > 2/3)

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.

Lemma 10. k A , va(B k) < 5/6.

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 bag Fill would assign B k \ {g} to agent i instead of adding g to it. Hence,

va(B k) = va(B k \ {g}) + va,g

4 + va,2n+1 (since va(B k \ g) < 3/4 and va,g va,2n+1)

(va,2n+1 < 1/12 by Lemma 9)

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.

Lemma 11. P k A+ va(B k) < |A+| + min(ℓ, |A+|)/12.

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

k A+ va(B k) =

k S va,k + X

k L va,2n k+1

k A+\S va,k + X

k A+\L va,2n k+1

By Lemma 6, we get va,2n k+1 1

3. Since va,k < 3/4 and |S| 1, we get

k S va,k + X

k L va,2n k+1 < |S| 3

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

2n + 1 k + ℓ

Figure 1: The items [2n] are arranged in a table, where the kth column is Bk := {k, 2n + 1 k}. For i N 1, we have vi(Bk) = vi,k + vi,2n+1 k 1 for all k. However, a N 1. Hence, we look for the smallest shift ℓsuch that va,k + va,2n+1 k+ℓ 1 for all k.

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, X

k A+\S va,k + X

k A+\L va,2n k+1

k [|A+| ℓ] (va,gk+ℓ+ va,2n gk+1) |A+| ℓ. (2)

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

Lemma 12. va([m] \ [2n]) > ℓ/4.

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

va([m] \ [2n]) X

j L va(Pj \ {j})

j L (va(Pj) va,j)

(va,j < 3/4 by Lemma 2)

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,

vi(Bk) vi,k vi,t > 2

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,

vi(Bk) = vi,k + vi,2n k+1 2 vi,2n t+1 > 1

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

n = va([m]) = X

k [n] va(B k)

k A va(B k) + X

k A+ va(B k) + X

k A0 va(B k)

6|A | + |A+| + ℓ

(by Lemmas 10 and 11)

Hence, |A | < ℓ/2. Now we show that there are enough goods in [m] \ [2n] to fill the bags in A .

ℓ 4 va([m] \ [2n]) (by Lemma 12)

k A (va(B k) va(Bk))

(since B k = Bk [2n] for k A+ A0)

(by Lemmas 10 and 13)

6, (since |A | < ℓ/2)

which is a contradiction.

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

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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 ( 3

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 ( 3

36, 3 4(4n 1)))-MMS allocation exists.

Algorithm approx MMS 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 approx MMS to the case where α > 3/4. approx MMS 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 bag Fill. In Appendix A.3, we show that when α 3

36, 3 4(4n 1)), bag Fill 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 ( 3

4 + 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

2n 1 (j 1)/2

4n 2 if j 2n n 4n 2 if j > 2n .

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],

(4n 2)u(Mi+1) = (4n 2)(u(i + 2) + u(2n + 1 i) + u(2n + i))

= 2n 1 ji + 1

k + 2n 1 j2n i

= (2n 1 i/2 ) + (n 1 + i/2 ) + n = 4n 2.

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

MMSscore(A) := n min i=1 vi(Ai) MMSi .

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 bag Fill(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

MMSscore(A) 3n 4n 2 = 3

4 + 3 8n 4.

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 bag Fill(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 bag Fill 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

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.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

[Akrami et al., 2023] Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki. Simplification and improvement of MMS approximation. ar Xiv:2303.16788v1, 2023.

[Amanatidis et al., 2016] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. On truthful mechanisms for maximin share allocations. In International Joint Conference on Artificial Intelligence, pages 31 37, 2016.

[Amanatidis et al., 2017a] Georgios Amanatidis, Georgios Birmpas, George Christodoulou, and Evangelos Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness. In ACM Conference on Economics and Computation, pages 545 562, 2017.

[Amanatidis et al., 2017b] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms (TALG), 13(4):1 28, 2017.

[Aziz et al., 2017] Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. Algorithms for max-min share fair allocation of indivisible chores. In AAAI Conference on Artificial Intelligence, 2017.

[Aziz et al., 2019] Haris Aziz, Bo Li, and Xiaowei Wu. Strategyproof and approximately maxmin fair share allocation of chores. In International Joint Conference on Artificial Intelligence, pages 60 66, 2019.

[Babaioff and Feige, 2022] Moshe Babaioff and Uriel Feige. Fair shares: Feasibility, domination and incentives. In ACM Conference on Economics and Computation, page 435. Association for Computing Machinery, 2022.

[Babaioff et al., 2021] Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair-share allocations for agents with arbitrary entitlements. In ACM Conference on Economics and Computation, pages 127 127, 2021.

[Barman and Krishnamurthy, 2020] Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation algorithms for maximin fair division. ACM Transactions on Economics and Computation (TEAC), 8(1):1 28, 2020.

[Barman et al., 2018] Siddharth Barman, Arpita Biswas, Sanath Krishnamurthy, and Yadati Narahari. Groupwise maximin fair allocation of indivisible goods. In AAAI Conference on Artificial Intelligence, 2018.

[Barman et al., 2019] Siddharth Barman, Ganesh Ghalme, Shweta Jain, Pooja Kulkarni, and Shivika Narang. Fair division of indivisible goods among strategic agents. In International Conference on Autonomous Agents and Multi Agent Systems, page 1811 1813, 2019.

[Bei et al., 2022] Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong. The price of connectivity in fair division. SIAM Journal on Discrete Mathematics, 36(2):1156 1186, 2022.

[Biswas and Barman, 2018] Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In IJCAI, pages 91 97, 2018. [Bouveret and Lemaˆıtre, 2016] Sylvain Bouveret and Michel Lemaˆıtre. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2):259 290, 2016. [Budish, 2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Chaudhury et al., 2021] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envyfreeness. SIAM Journal on Computing, 50(4):1336 1358, 2021. [Farhadi et al., 2019] Alireza Farhadi, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Sebastien Lahaie, David Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods to asymmetric agents. Journal of Artificial Intelligence Research, 64:1 20, 2019. [Feige and Norkin, 2022] Uriel Feige and Alexey Norkin. Improved maximin fair allocation of indivisible items to three agents. ar Xiv:2205.05363, 2022. [Feige et al., 2021] Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. In International Conference on Web and Internet Economics, pages 355 372. Springer, 2021. [Garg and Taki, 2021] Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. Artificial Intelligence, page 103547, 2021. [Garg et al., 2018] Jugal Garg, Peter Mc Glaughlin, and Setareh Taki. Approximating maximin share allocations. In Symposium on Simplicity in Algorithms (SOSA 2019), volume 69, pages 20:1 20:11, 2018. [Gates et al., 2020] Vael Gates, Thomas L. Griffiths, and Anca D. Dragan. How to be helpful to multiple people at once. Cognitive Science, 44, 2020. [Ghodsi et al., 2018] Mohammad Ghodsi, Mohammad Taghi Haji Aghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. In ACM Conference on Economics and Computation, pages 539 556, 2018. [Gourv es and Monnot, 2019] Laurent Gourv es and J erˆome Monnot. On maximin share allocations in matroids. Theoretical Computer Science, 754:50 64, 2019. [Hosseini and Searns, 2021] Hadi Hosseini and Andrew Searns. Guaranteeing maximin shares: Some agents left behind. In International Joint Conference on Artificial Intelligence, pages 238 244, 2021. [Huang and Lu, 2021] Xin Huang and Pinyan Lu. An algorithmic framework for approximating maximin share allocation of chores. In ACM Conference on Economics and Computation, pages 630 631, 2021.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

[Kurokawa et al., 2016] David Kurokawa, Ariel D Procaccia, and Junxing Wang. When can the maximin share guarantee be guaranteed? In AAAI Conference on Artificial Intelligence, 2016. [Kurokawa et al., 2018] David Kurokawa, Ariel D Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM (JACM), 65(2):1 27, 2018. [Li and Vetta, 2021] Zhentao Li and Adrian Vetta. The fair division of hereditary set systems. ACM Transactions on Economics and Computation (TEAC), 9(2):1 19, 2021. [Procaccia and Wang, 2014] Ariel D Procaccia and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. In ACM Conference on Economics and Computation, pages 675 692, 2014. [Truszczynski and Lonc, 2020] Miroslaw Truszczynski and Zbigniew Lonc. Maximin share allocations on cycles. Journal of Artificial Intelligence Research, 69:613 655, 2020. [Woeginger, 1997] Gerhard J Woeginger. A polynomialtime approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4):149 154, 1997.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)