The Existence of Maximin Share Allocations is delta 2 P-complete

arXiv:2609.15841 · cs.GT, cs.DS · Submitted 2026-09-14 · Read on arXiv

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

Where the paper says it

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

It proves that deciding the existence of an MMS allocation for additive goods is DP-hard, even when considering five agent types (Theorem 1. p. 4
Where the paper says it

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.

1). Furthermore, for 2-additive valuations—a class generalizing additive valuations—the decision problem is shown to be delta P squared-complete (Theorem 1. p. 2
Where the paper says it

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.

2), resolving a prior gap noted by Bouveret and Lemaître. p. 4
Where the paper says it

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

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. p. 5
Where the paper says it

Corollary 1. Unless P = NP, there is no FPTAS for computing the optimal MMS (approximation) ratio of an additive goods instance.

5).

The hardness extends to weaker complexity classes: it is shown to be weakly co-NP-hard even for three agents (Theorem 1. p. 4

Where the paper says it

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.

3), and strongly co-NP-hard when the number of agents is unrestricted (Theorem 1. p. 0
Where the paper says it

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.

4). The strong co-NP-hardness result indicates that the problem remains hard even with unary numerical values, ruling out an FPTAS unless P = NP. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

A verification problem is also provided showing that deciding if an allocation is an MMS allocation is co-NP-complete (Proposition 3. p. 3
Where the paper says it

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.

3). These hardness results are demonstrated by constructing specific instances based on KPW core matrices and Feige, Sapir, and Tauber no-instances. p. 5
Where the paper says it

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.

The paper extends these findings to the chores setting via a polynomial-time transformation (Theorem 1. p. 0

Where the paper says it

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.

6). For 2-additive chores instances, the decision problem is delta P squared-complete when restricted to monotone submodular cost functions (Theorem 1. p. 5
Where the paper says it

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.

6). More generally, deciding whether an additive chores instance admits an MMS allocation is DP-hard and strongly co-NP-hard (Corollary 10. p. 5
Where the paper says it

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.

2), while for 2-additive chores instances, it is delta P squared-complete when restricted to monotone submodular cost functions that are non-negative on every bundle. p. 5
Where the paper says it

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

Where the paper says it

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.

4). Furthermore, the existence of an MMS allocation for additive chores instances is equivalent to whether the 3-WAY PARTITION instance is a no-instance (Lemma 9. p. 5
Where the paper says it

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.

1).

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

Where the paper says it

Corollary 1. Unless P = NP, there is no FPTAS for computing the optimal MMS (approximation) ratio of an additive goods instance.

3), derived from an inverse-polynomial gap between cases where an allocation exists and when it does not exist, implying strong NP-hardness. p. 0
Where the paper says it

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.

The transfer lemma (Lemma 10. p. 5
Where the paper says it

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.

1) allows hardness results from the goods setting to be transferred to the chores setting, showing that if a problem is hard for additive/monotone submodular non-negative 2-additive goods instances, it is also hard for the corresponding chores instances with polynomial construction complexity. p. 3
Where the paper says it

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.

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

  1. 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 that unless P = NP, there is no FPTAS for computing the optimal MMS (approximation) ratio of an additive goods instance.

  2. 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."

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

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

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

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

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

Related papers