The best approximation ratio for maximin share allocations

When indivisible goods are divided among agents, each agent's maximin share is the value she could secure by splitting the goods into as many bundles as there are agents and receiving the worst one. Allocations that give everyone their full maximin share need not exist, so the question is the largest fraction of it that can always be guaranteed; preprints from 2025 and 2026 place that fraction between 7/9 and 20/21.

Problem

There are $n$ agents and a set $M$ of $m$ indivisible goods. Agent $i$ has an additive valuation: $v_i(S) = \sum_{g \in S} v_i(g)$ with $v_i(g) \ge 0$. Write $\Pi_n(M)$ for the partitions of $M$ into $n$ bundles (some possibly empty). The maximin share of agent $i$ is

$$\mathrm{MMS}_i = \max_{(P_1,\dots,P_n) \in \Pi_n(M)} \; \min_{j} v_i(P_j).$$

An allocation $(A_1,\dots,A_n) \in \Pi_n(M)$ is $\alpha$-MMS if $v_i(A_i) \ge \alpha \cdot \mathrm{MMS}_i$ for every agent $i$. Let $\alpha^*$ be the supremum of the $\alpha$ such that every instance, with any numbers of agents and goods, has an $\alpha$-MMS allocation.

Question. Determine $\alpha^*$. The best claimed bounds, both in unrefereed preprints, are $7/9 \le \alpha^* \le 20/21$; the best refereed ones are $10/13 \le \alpha^* \le 39/40$. The source page lists $7/9 \le \alpha^* \le 39/40$.

Background

The maximin share was introduced by Budish (2011) in his work on combinatorial assignment. Kurokawa, Procaccia and Wang showed that for additive valuations an allocation giving every agent her full maximin share may not exist, while a $2/3$ fraction can always be guaranteed [1]. Since then, approximate MMS has become a standard benchmark in fair division, and the gap between what can be guaranteed and what can fail has narrowed from both sides. The question was posted on TCS Open Problems in 2026.

What is known

• Guarantees. $2/3$ (Kurokawa, Procaccia and Wang) [1]; $3/4 + 3/3836$ (Akrami and Garg, 2023); $10/13$ (Heidari, Kaviani, Seddighin and Shahrezaei, SODA 2026) [5]; $7/9$ (Huang and Zhou, preprint, November 2025), who also give an algorithm computing a $(7/9-\varepsilon)$-MMS allocation in time $\frac{1}{\varepsilon}\,\mathrm{poly}(n,m)$ [4]. The first version of the $7/9$ proof had a bug; the authors fixed it in a largely rewritten version in September 2026, which is not yet refereed.
• Impossibility. Feige, Sapir and Tauber built three agents and nine goods for which some agent always gets at most $39/40$ of her maximin share, and showed this gap is the worst possible with nine goods; for $n \ge 4$ agents their examples give $1 - 1/n^4$ [2]. Ezra and Garbuz (September 2026, unrefereed preprint) found four agents and eleven goods that bring the bound down to $20/21$, and showed that for large $n$ some agent can be held to $1-\Omega((\log n)^{-2})$ of her share [3].
• Few agents. For three agents, $11/12$-MMS allocations always exist (Feige and Norkin, 2022) [6].

What would count as progress

• An explicit instance (agents' values for each good) in which every allocation leaves some agent below $\alpha \cdot \mathrm{MMS}_i$ for some $\alpha < 20/21$. With a dozen goods this is quick to check by exhaustive search: compute each maximin share by enumerating partitions, then enumerate all allocations.
• A proof that $\alpha$-MMS allocations always exist for some $\alpha > 7/9$, ideally with a polynomial-time algorithm.
• The exact value for three agents, where the guarantee is between $11/12$ and $39/40$.

References

1. D. Kurokawa, A. D. Procaccia and J. Wang, Fair enough: guaranteeing approximate maximin shares, J. ACM 65(2) (2018), article 8. doi:10.1145/3140756
2. U. Feige, A. Sapir and L. Tauber, A tight negative example for MMS fair allocations, WINE 2021, LNCS 13112 (2022), 355–372. doi:10.1007/978-3-030-94676-0_20
3. T. Ezra and T. Garbuz, Improved impossibility bounds for maximin share allocations, preprint (2026). arXiv:2609.15085
4. X. Huang and S. Zhou, An FPTAS for 7/9-approximation to maximin share allocations, preprint (2025, revised 2026). arXiv:2511.13056
5. E. Heidari, A. Kaviani, M. Seddighin and A. Shahrezaei, Improved maximin share guarantee for additive valuations, SODA 2026, 2239–2290. doi:10.1137/1.9781611978971.81
6. U. Feige and A. Norkin, Improved maximin fair allocation of indivisible items to three agents, 2022. arXiv:2205.05363

Source

Imported from TCS Open Problems, Problem 4, curated by Kunal Marwaha. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.