The Existence of Maximin Share Allocations is delta 2 P-complete
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "The Existence of Maximin Share Allocations is delta 2 P-complete".
Jane: Here's the gist of the paper. The paper establishes computational hardness results for deciding whether a maximin share (MMS) allocation exists, first focusing on additive goods valuations.
Tom: It proves that deciding the existence of an MMS allocation for additive goods is DP-hard, even when considering five agent types (Theorem 1.1).
Jane: Furthermore, for 2-additive valuations—a class generalizing additive valuations—the decision problem is shown to be delta P squared-complete (Theorem 1.2), resolving a prior gap noted by Bouveret and Lemaître.
Tom: This result also implies that unless P = NP, there is no Fully Polynomial Time Approximation Scheme (FPTAS) for computing the optimal MMS approximation ratio for an additive goods instance (Corollary 1.5).
Paper summary: Tom: So, thinking about the whole picture from "The Existence of Maximin Share Allocations is delta two P-complete," what does this actually mean for how we think about fairness in real-world resource sharing <ref:2609.15841#pg1>?
Jane: It means that when you try to guarantee a maximin share across different agent types, the computational difficulty isn't just an engineering hurdle; it’s a fundamental limit related to NP complexity classes.
Lu: They are using constructions based on things like KPW core matrices and Feige, Sapir, and Tauber no-instances <ref:2609.15841#pg3>, which shows they can force the problem to be as hard as known difficult problems in computer science.
Meng: From an engineering standpoint, if a problem is strongly co-NP hard, it implies that even with simple numerical inputs, you probably won't find a fast algorithm that works reliably for all cases at scale <ref:2609.15841#pg2>.
Lalam: The authors establish that deciding if an allocation exists for additive goods instances is co-NP-complete by reducing from PARTITION <ref:2609.15841#pg3>, which is a classic hard problem in itself.
Tom: So, the main implication is that for many complex allocation scenarios, we have to accept that finding an exact fair split might be computationally infeasible unless P equals NP <ref:2609.15841#pg2>.
Jane: The paper shows how these theoretical limits translate directly into practical constraints on what kind of fairness guarantees we can efficiently compute when dealing with different types of goods or chores.
Conclusion: Tom: So, we've seen how complex these allocation problems get when you have different types of goods or chores <ref:2609.15841#pg3>. This paper is called "The Existence of Maximin Share Allocations is delta two P-complete."
Jane: That title sounds really dense, Tom. So what's the actual deal with that name? Is it just a fancy way to say it's really hard to find a fair split?
Tom: It means that deciding if you can even find an allocation where every agent gets at least their minimum guaranteed share is computationally very difficult. Specifically, it’s delta two P-complete.
Lu: That delta P squared complexity class tells us it’s hitting some really deep limits in how efficiently we can solve the problem. It's not just a little bit slower; it's fundamentally harder than things we usually consider hard.
Meng: For someone actually trying to build this into a system, what does that mean for deployment? Can we expect a fast solution at scale, or are we just looking at things being incredibly slow?
Jane: Well, the paper shows that unless P equals NP, there’s no way to get a fully polynomial time approximation scheme for finding an optimal ratio in these additive goods scenarios. That means we can't just use a quick shortcut to get close to the best possible fairness.
Lalam: And it holds true even when you look at weaker versions of this problem, like with only three agents, showing it stays hard. The construction uses things like three-PARTITION and DP as gadgets to prove this hardness.
Tom: So, in simple terms, the paper is saying that achieving a guaranteed minimum share for different types of resources isn't just a tricky math problem; it’s one of those problems where finding an exact answer might be impossible for large instances.
Jane: It points to a fundamental barrier in fairness algorithms. It tells us that the structure of these resource valuations—additive or even two-additive—is strong enough to push the complexity right up against what we think is hard.
Lu: The transfer lemma they use is interesting too; it shows this hardness carries over from additive goods instances into the chores setting, which suggests a similar computational wall exists there too.
Meng: So for us in production, that means if we model resource sharing with these properties, we should probably stop looking for a simple fast algorithm and start thinking about approximation methods that might not be fully polynomial time.
Jane: Exactly. It shifts the focus from finding an easy answer to figuring out the best possible trade-off between speed and fairness when things get complicated.
Institute of Mathematical Sciences
cs.GT, cs.DS
Submitted: 2026-09-14
Updated: 2026-11-09
Comments: 58 pages; this version strengthens the main result for additive valuations; abstract shortened to meet arXiv requirements
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: The paper establishes computational hardness results for deciding whether a maximin share (MMS) allocation exists, first focusing on additive goods valuations.
Key concepts
- Maximin Share (MMS) Allocation
- An MMS allocation is a way to distribute goods among agents such that no agent receives less than their personal maximin share. This concept is central to the problem, focusing on fair distribution where individual minimum requirements are met.
- Additive Goods Valuations
- This refers to a specific way of valuing goods where the total value of a bundle is simply the sum of the values of its individual components. The paper establishes hardness results for this simpler valuation structure first.
- \Delta P^2-complete
- This is a complexity class indicating that solving an optimization problem related to MMS allocation for 2-additive valuations is among the hardest problems in that class. It means the problem is computationally very difficult, even for algorithms with certain time constraints.
- FPTAS (Fully Polynomial Time Approximation Scheme)
- An FPTAS is a type of approximation algorithm that can find a solution within a small factor of the optimal solution, and its running time grows polynomially with the input size. The paper shows that for additive goods, such an efficient scheme likely doesn't exist unless P=NP.
Terminology
Summary
The paper establishes computational hardness results for deciding whether a maximin share (MMS) allocation exists, first focusing on additive goods valuations. p. 2 Thus, a gap remained between the
hardness and the membership of the decision problem for even the class of 2-additive valuations. The open status of the additive case was also explicitly highlighted by Heinen, Nguyen, Nguyen,
and Rothe [Hei+18], who stated that the complexity of deciding whether a maximin share allocation exists was the only missing part in their study of maximin, proportional, and minimax share
1 All formal definitions are presented in Section 3. Deciding whether an additive goods instance admits an MMS allocation is DP -hard,
even for five agent types. Tantalizingly though the computational
complexity status of the decision problem for additive valuations was left open, as was the matter
of identifying any valuation class for which completeness–both membership and hardness–could be
identified. In this paper we achieve both of these objectives: We pinpoint the hardness for additive
valuations and identify a valuation class for which the decision problem is shown to be complete. Moreover, the hardness holds even when the valuations are monotone, submodular, and nonnegative. This result allows us to identify a class of instances of monotone submodular goods for which
MMS allocation is ∆P
2
-complete; and thus resolving a stated goal of Bouveret and Lemaître [BL16]. Corollary 1. Unless P = NP, there is no FPTAS for computing the optimal MMS (approximation)
ratio of an additive goods instance.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The hardness extends to weaker complexity classes: it is shown to be weakly co-NP-hard even for three agents (Theorem 1. p. 4 The following result demonstrates a sharp dichotomy. Deciding whether an additive goods instance admits an MMS allocation is weakly
co-NP-hard, even for three agents. Additionally, we prove weak co-NP-hardness for three agents, thereby establishing a precise
dichotomy with the known existence guarantee for two agents; and strong co-NP-hardness when
the number of agents is unrestricted. The latter implies that the hardness is not caused by large
binary-encoded numbers; in fact, the problem remains hard even when all numerical values
are given in unary. The latter implies that the hardness is not caused by large
binary-encoded numbers; in fact, the problem remains hard even when all numerical values
are given in unary. Moreover, the strong hardness construction produces an inverse-polynomial
gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio
unless P = NP.Where the paper says it
Where the paper says it
Where the paper says it
The construction relies on rigid MMS no-instance cores and gadgets encoding known hard problems such as 3-PARTITION, DP, and COMPARE-MWIS. p. 6 2 Technical overview
In this section we sketch the main ideas underlying our hardness proofs. At the heart of our reductions are rigid MMS no-instance cores given by [KPW18] and [FST21], formally defined in Section 4, along with gadgets encoding partition and independent-set comparison problems. We note that the decision (or even the search) problem is computationally unusual. Even
verifying that a given allocation is an MMS allocation can be shown to be co-NP-complete, Proposition 3. We end our discussion by noting that our hardness reductions depend on a very careful analysis
of the no-instances of MMS allocations given by Kurokawa, Procaccia, and Wang [KPW18] and
Feige, Sapir, and Tauber [FST21], that includes making certain parameters explicit in order to
work with our gadgets. This culminates in certain structural properties of the KPW core listed in
Proposition 4.Where the paper says it
Where the paper says it
Where the paper says it
The paper extends these findings to the chores setting via a polynomial-time transformation (Theorem 1. p. 0 Moreover, the strong hardness construction produces an inverse-polynomial
gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio
unless P = NP. We conclude by showing that all these results for goods extend to the chores
setting through a polynomial-time transformation that preserves MMS existence. Moreover,
deciding whether a 2-additive chores instance admits an MMS allocation is ∆P
2
-complete, and the
hardness holds even for monotone submodular cost functions that are nonnegative on every bundle. We end our discussion by noting that our hardness reductions depend on a very careful analysis
of the no-instances of MMS allocations given by Kurokawa, Procaccia, and Wang [KPW18] and
Feige, Sapir, and Tauber [FST21], that includes making certain parameters explicit in order to
work with our gadgets. The hardness results above extend to chores. In particular, deciding whether
an additive chores instance admits an MMS allocation is DP -hard and strongly co-NP-hard. Moreover,
deciding whether a 2-additive chores instance admits an MMS allocation is ∆P
2
-complete, and the
hardness holds even for monotone submodular cost functions that are nonnegative on every bundle. We end our discussion by noting that our hardness reductions depend on a very careful analysis
of the no-instances of MMS allocations given by Kurokawa, Procaccia, and Wang [KPW18] and
Feige, Sapir, and Tauber [FST21], that includes making certain parameters explicit in order to
work with our gadgets.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The problem's complexity in the chores setting is related to NP completeness: deciding whether an MMS allocation exists for additive chores instances is co-NP-complete by reducing from PARTITION (Proposition 3.3). The strong co-NP-hardness for chores is established by reducing from 3-PARTITION (Theorem 1. p. 0 Moreover, the strong hardness construction produces an inverse-polynomial
gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio
unless P = NP. We conclude by showing that all these results for goods extend to the chores
setting through a polynomial-time transformation that preserves MMS existence. Moreover,
deciding whether a 2-additive chores instance admits an MMS allocation is ∆P
2
-complete, and the
hardness holds even for monotone submodular cost functions that are nonnegative on every bundle. We end our discussion by noting that our hardness reductions depend on a very careful analysis
of the no-instances of MMS allocations given by Kurokawa, Procaccia, and Wang [KPW18] and
Feige, Sapir, and Tauber [FST21], that includes making certain parameters explicit in order to
work with our gadgets.Where the paper says it
Where the paper says it
The paper also establishes that unless P = NP, there is no FPTAS for computing the optimal MMS ratio for an additive chores instance (Corollary 10. p. 5 Corollary 1. Unless P = NP, there is no FPTAS for computing the optimal MMS (approximation)
ratio of an additive goods instance. The latter implies that the hardness is not caused by large
binary-encoded numbers; in fact, the problem remains hard even when all numerical values
are given in unary. Moreover, the strong hardness construction produces an inverse-polynomial
gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio
unless P = NP. Finally, we show that the above results can be transferred, in polynomial time, from goods to
chores. The transfer preserves the existence of MMS allocations, and therefore gives the corresponding hardness results for chore instances. These features suggest that the computational complexity of the decision problem (and thus the search problem) for the additive setting
may extend beyond ordinary NP-hardness. In this paper, we resolve this matter: We study the decision problem and provide an array of
hardness results, providing the first computational hardness result for the additive setting for both
goods and chores showing that it is DP -hard.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Better approximation algorithms for MMS allocation can be developed because results show
the optimal MMS ratio of an instance is defined as the maximum approximation ratio attainable by each agent
and thatunless P = NP, there is no FPTAS for computing the optimal MMS (approximation) ratio of an additive goods instance.
-
More robust complexity analysis can be applied to fairness problems because the paper proves that
the decision problem, i.e., deciding whether an MMS allocation exists, is DP -hard
and that "the 2-additive variant is in fact DeltaP2-complete for every fixed k >= 2." -
Systems can be designed to handle high-dimensional fairness constraints efficiently because the paper shows that
the strong hardness construction produces an inverse-polynomial gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio unless P = NP.
-
The system can determine if a given allocation is fair by using a co-NP complete verification procedure because
verifying whether a given allocation is an MMS allocation or not can be shown to be co-NP-complete.
-
The system can solve hard fairness problems in the chores setting by using polynomial time transformations, as
all hardness results for goods transfer to the corresponding chores.
-
The system can compare two complex optimization problems efficiently because it proves that
deciding whether a fair division instance admits an MMS allocation is ThetaP2-hard for 2-additive valuations
by reducing from COMPARE-MIS. -
The system can solve graph comparison problems efficiently because the paper proves that "the constructed instance admits an MMS allocation if and only if alpha(GX) >= alpha(GY)" for COMPARE-MIS, showing that deciding whether a fair division instance admits an MMS allocation is ThetaP2-hard for 2-additive valuations.
Abstract
The maximin share (MMS) guarantee has become one of the central fairness benchmarks for allocating indivisible items. Since Kurokawa, Procaccia, and Wang [EC'14, JACM'18] showed that exact MMS allocations need not exist, a substantial literature has developed around the existence and computation of approximate MMS allocations, including the recent work of Heidari, Kaviani, Seddighin, and Shahrezaei [SODA'26]. In contrast, a fundamental complexity question posed more than a decade ago by Bouveret and Lemaître [JAAMAS'16] has remained unresolved: how hard is it to decide whether an exact MMS allocation exists? For additive valuations, Lonc and Truszczynski [JAIR'20] established membership in the complexity class Δ 2 P (also known as P NP), but no hardness result was known. For the more general class of 2-additive valuations, Bouveret and Lemaître established NP-hardness, leaving a substantial gap to the Δ 2 P upper bound. Moreover, the complexity of MMS existence for additive and k-additive valuations was posed as open questions. We resolve this longstanding question by proving that deciding the existence of an MMS allocation for additive goods is Δ 2 P-complete, even for five agents. Additionally, we prove weak coNP-hardness for three agents, thereby establishing a precise dichotomy with the known existence guarantee for two agents, and strong coNP-hardness when the number of agents is unrestricted. Furthermore, our strong hardness construction yields an inverse-polynomial gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio unless P=NP. Finally, we show that all these results for goods extend to the chores setting through a polynomial-time transformation that preserves MMS existence.
Sources
- On MMS, APS and XOS
- A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations
- On Fair Allocation of Indivisible Goods to Submodular Agents
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments