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 (MMS i ), 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 α • MMS i . 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 +foot_0 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/n 4 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 4 + 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 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.
Computing the maximin share of any agent is NP-hard (even for 2 agents) 1 , but a PTAS exists [Woeginger, 1997]. Procac-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ès 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ès 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].
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.
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 v i,g is the value of good g ∈ M for agent i ∈ N . For a set S of goods, define v i (S) := g∈S v i,g . Then v i is called agent i's valuation function. Intuitively, v i (S) is a measure of how valuable S is to i. For ease of notation, we write v i (g) instead of v i ({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 MMS i instead of MMS |N | vi (M ) for conciseness.
We will now see how to reduce the problem of finding an α-MMS allocation to the special case of ordered instances.
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]).
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:
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 [Garg and Taki, 2021]). For an ordered instance and for α ≤ 1, R 1 (α), R 2 (α), and R 3 (α) are valid α-reductions. For an ordered instance and for α ≤ 3/4,
Pick any agent i ∈ N . Let P be an MMS partition of agent i. Then some bundle P j contains a single good {g}. Then v i,g = v i (P j ) ≥ MMS i . Hence, the instance is not R 1 (α)-irreducible for any α ≤ 1. This is a contradiction. Hence,
Compute agent i's MMS partition P (i) .
3:
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 R 1 (α), R 2 (α), R 3 (α), and R 4 (α) until the instance becomes totallyα-irreducible. The reduction rules can be applied in arbitrary order, except that R 4 (α) is only applied when R 1 (α) and R 3 (α) 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 S 1 , S 2 , S 3 , S 4 (as defined in Definition 4) can change after applying a reduction rule. So, for example, it is possible that an instance is R 2 (α)irreducible, but after applying R 3 (α), the resulting instance is R 2 (α)-reducible.
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
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 v i (Q j ) = 1 ∀j ∈ N , since each partition has total value at least 1 and
The algorithm normalize (c.f. Algorithm 1) converts a fair division instance to a normalized instance.
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).
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 = (A 1 , . . . , A n ).
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.
Lemma 5. Let I be a fair division instance. Let I := toOrd(normalize(reduce 3/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) := reduce 3/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 totally-3/4-irreducible.
Since toOrd, reduce 3/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.
// unassigned bags 7: while U A ̸ = ∅ do // loop invariant:
// assign the k th bag to agent i:
10:
else if U G ̸ = ∅ then // assign g to the k th bag:
17:
18:
else 20:
error: we ran out of goods. return null.
end if 22: end while 23: return (A 1 , . . . , A n ) Garg and Taki [2021] transform the instance as reduce 3/4 (toOrd(I)), since they do not need the input to be normalized.
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 v i,1 ≥ v i,2 ≥ . . . ≥ v i,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 B k to agent i only if v i (B k ) ≥ α. 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 B k := {k, 2n + 1 -k} be the initial contents of the k th bag and B ′ k be the k th 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
Let U A be the set of agents that did not receive a bag when bagFill terminated. Note that U A is non-empty iff we execute line 20. We first show that all agents in N 1 receive a bag, i.e., U A ∩ N 1 = ∅. Then we show that U A ∩ 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 ∈
Proof. It suffices to prove v i,2n-k+1 ≤ 1/3 and then v i,k > 2/3 follows. Let P = (P 1 , . . . , P n ) be an MMS partition of agent i.
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 ∈ P j for all j ∈ [k].
For all j ∈ [k] and j ′ ∈ [2n -k + 1], j ′ ̸ ∈ P j . Thus, {k + 1, . . . , 2n -k + 1} ⊆ P k+1 ∪ . . . ∪ P n . By pigeonhole principle, there exists a bundle B ∈ {P k+1 , . . . , P n } that contains at least 3 goods g 1 , g 2 , g 3 in {k + 1, . . . , 2n -k + 1}. Hence,
Let g be the last good that was added to B ′ k . We have v i (B ′ k \ g) < 3/4, otherwise g would not be added to B ′ k . Also note that g > 2n and hence v i,g < 1/4 by Lemma 2. Thus, we have
, every agent in N 1 gets a bag.
Proof. For the sake of contradiction, assume
which is a contradiction. Hence,
Now we prove that bagFill allocates a bag to all agents in N 2 , i.e., U A ∩ N 2 = ∅.
From now on assume for the sake of contradiction that
We will try to get upper bounds on v a (B ′ k ) for each of the cases k ∈ A + , k ∈ A -, and k ∈ A 0 .
Note that
Otherwise, let g be the last good that was added to
(v a,2n+1 < 1/12 by Lemma 9)
Let ℓ be the smallest such that for all k ∈ [ℓ + 1, n], v a,k + v a,2n-k+1+ℓ ≤ 1. See Fig. 1 for a better understanding of ℓ.
Proof. Let S ∈ A + be the set of min(ℓ,
By Lemma 6, we get v a,2n-k+1 ≤ 1 3 . Since v a,k < 3/4 and |S| ≥ 1, we get
(1)
However, a ̸ ∈ N 1 . Hence, we look for the smallest shift ℓ such that v a,k + v a,2n+1-k+ℓ ≤ 1 for all k.
) and prove that their value is at most 1 for agent a.
Since g k+ℓ ≥ g k + ℓ, we get v a,g k+ℓ + v a,2n-g k +1 ≤ 1 by definition of ℓ. Hence,
(2) Equations ( 1) and ( 2) imply Lemma 11.
Proof. By definition of ℓ, there exists a good k ∈ {ℓ, . . . , n} such that v a,k + v a,2n-k+ℓ > 1. Hence, for all j ∈ [k] and t ≤ [2n-k +ℓ], we have v a,j +v a,t ≥ v a,k +v a,2n-k+ℓ > 1.
Let P := (P 1 , . . . , P n ) 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 ∈ P j for ∈
(v a,j < 3/4 by Lemma 2)
Proof. Fix an i ∈ N 2 . Let t be smallest such that v i (B t ) > 1. By Lemma 6, v i,t > 2/3. Hence, for all k ≤ t,
Lemma 14. U A ∩ N 2 = ∅, i.e., every agent in N 2 gets a bag.
Proof. Assume for the sake of contradiction that U A ∩ N 2 ̸ = ∅. Then, as discussed before, we fix an agent a ∈ U A ∩ N 2 and define A + , A -, A 0 , and ℓ.
(by Lemmas 10 and 11)
Hence, |A -| < ℓ/2. Now we show that there are enough goods in
(by Lemmas 10 and 13)
which is a contradiction.
By Lemmas 8 and 14, we get that U A = ∅, 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 ( 3 4 + 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 ( 3 4 + min( 1 36 , 3 4(4n-1) ))-MMS allocation exists. Algorithm approxMMS from Section 3 does not work with α > 3/4, since R 4 (α) may not be a valid reduction. To fix this, we modify R 4 (α) using the dummy goods technique from [Garg and Taki, 2021].
Consider the fair division instance ([n], [m], v). When performing R 4 (α), in addition to giving the goods S 4 := {1, 2n + 1} to some agent i for whom v i (S 4 ) ≥ αMMS i , we create a dummy good g where v j (g) := max(0, v j (S 4 ) -MMS j ) for each agent j ̸ = i. With this change, R 4 (α) 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 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
With these modifications, we can extend approxMMS to the case where α > 3/4. first transforms 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.
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 Proof. Let M 1 := {1, 2} and for i ∈ [n -1], let M i+1 := {i + 2, 2n + 1 -i, 2n + i}. Then for any i ̸ = j, M i ∩ M j = ∅. Also, u(M 1 ) = u(1) + u(2) = 1 and for each i ∈ [n -1],
(4n -2)u(M i+1 ) = (4n -2)(u(i + 2) + u(2n + 1 -i) + u(2n + i))
Define the MMSscore of an allocation as the maximum α such that it is an α-MMS allocation. Formally, for an alloca- Proof. u(S 1 ) = 1/2, u(S 2 ) = u(S 4 ) = (3n -1)/(4n -2), and u(S 3 ) = 3n/(4n -2). Hence, if the algorithm allocates S k 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].
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].
by a straightforward reduction from the partition problem.Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence