Answer: \(\mathrm{NP\text{-}hard}\); indeed, the threshold problem is \(\mathrm{NP\text{-}complete}\) under polynomial-time value evaluation, and every approximation factor \(\alpha>5/6\) is \(\mathrm{NP\text{-}hard}\), even for the singleton distribution \(\mu_t=1\) without expanding agent copies.
Theorem 5.1 — class: hardness
In an instance ([𝑛], [𝑚], (𝑣𝑖)𝑖∈[𝑛]), it is NP-hard to compute the MMS value of an agent approximately up to a factor better than 5/6, when the agent has a submodular valuation function, even when all the marginal utilities are in {0, 1/2, 1}. An immediate corollary, using Claim 2.1, is that computing the APS value approximately up to a factor better than 5/6 is also NP- hard for such an agent. The proof of the theorem has three parts. First, we show a reduction from the known NP-complete problem 3-D-MATCHING to a fair allocation instance with agents with identical valuations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an explicitly represented finite indivisible-good set \(G\), a population scale \(N\), a rational distribution \(\mu\) over complete submodular valuation types whose marginal values lie in \(\{0,1/2,1\}\), and a target type \(t\) with \(N\mu_t\in\mathbb{Z}\), decide whether \(\operatorname{MMS}_{N,t}(G)=\max_{(S_1,\ldots,S_N)\in\Pi_N(G)}\min_{j\in[N]}v_t(S_j)\ge q\), or approximate this value within a factor better than \(5/6\), without expanding the \(N\mu_t\) identical agents. The one-type case \(\mu=\delta_t\), with \(3N\) goods and the paper’s ternary valuation, is the hardness instance.
A type \(v:2^G\to\mathbb{R}_{\ge0}\) is submodular and has ternary marginals if \(v(S\cup\{g\})-v(S)\in\{0,1/2,1\}\) for every \(S\subseteq G\) and \(g\notin S\). Let \(\Pi_N(G)\) be the set of partitions \((S_1,\ldots,S_N)\) of \(G\), and define \(\operatorname{MMS}_{N,t}(G)=\max_{(S_1,\ldots,S_N)\in\Pi_N(G)}\min_{j\in[N]}v_t(S_j)\).
Target. Given \(G,N,\mu,t,q\), where \(\mu\) is a rational distribution over finitely many such types and \(N\mu_t\in\mathbb{Z}\), is deciding whether \(\operatorname{MMS}_{N,t}(G)\ge q\), or approximating it within a factor strictly better than \(5/6\), in polynomial time or NP-hard without expanding the \(N\mu_t\) copies of type \(t\)?
Nearest known results. For explicitly listed agents with identical submodular valuations whose marginals lie in \(\{0,1/2,1\}\), approximating an agent's MMS within a factor strictly better than \(5/6\) is NP-hard. The hardness construction uses one valuation type, \(3N\) goods, and \(N\) identical agents.
Assume that each valuation type is represented by a polynomial-size description permitting polynomial-time value evaluation, as in the stated hardness result. Then:
Thus compressing identical agents into a rational type distribution does not remove the hardness.
The reduction below is the compact one-type version of the construction underlying Theorem \(5.1\) of Kulkarni, Kulkarni, and Mehta. [AAMAS 2024 paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p1057.pdf)
Let \(X,Y,Z\) be pairwise disjoint sets of cardinality \(r\), and let \(\mathcal T\subseteq X\times Y\times Z\). The NP-complete question is whether \(\mathcal T\) contains \(r\) pairwise disjoint triples covering \(X\cup Y\cup Z\).
Construct the following compact MMS instance:
The valuation has a polynomial-size description: it suffices to store \(\mathcal T\). Evaluating \(v(S)\) requires computing \(|S|\) and, only when \(|S|=3\), testing membership in \(\mathcal T\).
For \(g\notin S\), let \(\Delta(g\mid S)=v(S\cup\{g\})-v(S)\). Directly from the definition,
Consequently every marginal belongs to \(\{0,1/2,1\}\).
It remains to verify submodularity. For finite set functions, it suffices to prove diminishing returns: if \(A\subseteq B\) and \(g\notin B\), then \(\Delta(g\mid A)\ge\Delta(g\mid B)\).
Thus \(v\) is submodular and satisfies the required ternary-marginal promise.
First, \(v(S)\le3\) for every \(S\subseteq G\), so \(\operatorname{MMS}_{r,t}(G)\le3\).
Suppose that \(\mathcal T\) contains a perfect \(3\)-dimensional matching. Its \(r\) triples partition \(G\), and every such triple has value \(3\). Therefore \(\operatorname{MMS}_{r,t}(G)=3\).
Conversely, suppose that \(\operatorname{MMS}_{r,t}(G)\ge3\). There is then a partition \((S_1,\ldots,S_r)\) of \(G\) in which every bundle has value \(3\).
Every bundle must have exactly three goods. Indeed, the average bundle cardinality is \(3\). If some bundle contained at least four goods, another would contain at most two goods and hence have value at most \(2\), contradicting the assumed minimum value \(3\).
A three-good bundle has value \(3\) exactly when it belongs to \(\mathcal T\). Hence \(S_1,\ldots,S_r\) are \(r\) disjoint triples in \(\mathcal T\) covering \(G\), and therefore form a perfect \(3\)-dimensional matching.
We have proved the equivalence
\[
\operatorname{MMS}_{r,t}(G)\ge3
\quad\Longleftrightarrow\quad
(X,Y,Z,\mathcal T)\text{ has a perfect }3\text{-dimensional matching}.
\]
Therefore the threshold problem is NP-hard under polynomial-time many-one reductions.
If the \(3\)-dimensional matching instance is positive, the MMS value is \(3\).
If it is negative, the MMS value is not \(3\). Every bundle value lies in \(\{0,1,2,5/2,3\}\), and hence every partition minimum, and therefore the MMS optimum itself, lies in this set. Consequently a negative instance satisfies
\[
\operatorname{MMS}_{r,t}(G)\le5/2.
\]
Let \(\alpha>5/6\), and suppose an algorithm returns a lower approximation \(A\) satisfying
\[
\alpha\operatorname{MMS}_{r,t}(G)\le A\le\operatorname{MMS}_{r,t}(G).
\]
On a positive instance, \(A\ge3\alpha>5/2\). On a negative instance, \(A\le5/2\). Comparing \(A\) with \(5/2\) would therefore decide \(3\)-Dimensional Matching. Thus approximation within every fixed factor strictly better than \(5/6\) is NP-hard.
The same argument applies if the algorithm returns a partition whose minimum bundle value is at least \(\alpha\) times the optimum.
The displayed definition of \(\operatorname{MMS}_{N,t}(G)\) depends only on \(G\), \(N\), and \(v_t\); the distribution \(\mu\) and the number \(N\mu_t\) do not otherwise occur in the objective.
In the reduction, \(\mu\) is the singleton distribution \(\mu_t=1\). The output contains:
Although the agents are compressed, the \(3r\) goods are explicitly present, exactly as required by the target input. Therefore the reduction is polynomial in the compact input size and does not conceal any expansion of the type multiplicity.
If the intended alternative definition used \(N\mu_t\), rather than \(N\), as the number of MMS bundles, the same reduction still applies because \(\mu_t=1\).
Under a polynomial-time value-evaluation representation, the promised threshold problem is also in NP. A partition can be encoded by assigning each good an index in \([N]\), using \(O(|G|\log N)\) bits. Only the nonempty bundles need separate evaluation; all unused indices represent identical empty bundles. Thus the decision problem is NP-complete under this standard representation.
⟨structured verdict parsed — rendered above⟩
The reduction correctly establishes NP-hardness of the threshold problem and hardness of every fixed approximation factor \(\alpha>5/6\), provided valuations use a succinct representation that can encode the displayed function and evaluate it exactly in polynomial time. The singleton distribution \(\mu_t=1\) genuinely avoids expanding identical agent copies.
The central mathematical argument is sound. The only issues are minor formalization gaps concerning the input representation, the identification of tuples with sets, and the optional NP-membership claim.
The reduction maps a perfect \(3\)-dimensional matching instance with \(|X|=|Y|=|Z|=r\) to:
Thus \(N\mu_t=r\in\mathbb Z\), and no list of \(r\) agents or \(r\) valuation copies is created. Storing \(\mathcal T\) and the fixed evaluation rule takes polynomial space in the source instance.
This part is correct.
There is, however, a formal encoding issue: the target problem does not specify how valuations are represented. The prover explicitly adds a polynomial-time evaluation assumption, which is necessary, but “a polynomial-size description permitting polynomial-time evaluation” does not by itself define a target language for a formal many-one reduction. The hardness result is valid for any standard representation capable of encoding this valuation family, such as an explicit list of \(\mathcal T\) together with the fixed rule, but that representation should be declared precisely.
All possible cardinalities are covered, including \(S=\varnothing\), and every assigned value is nonnegative.
There is a minor type mismatch in the notation \(S\in\mathcal T\): \(\mathcal T\subseteq X\times Y\times Z\) consists of ordered triples, whereas \(S\subseteq G\) is a set. Because \(X,Y,Z\) are pairwise disjoint, there is a canonical identification between a tuple \((x,y,z)\) and the set \(\{x,y,z\}\), but the identification is not stated. The valuation should formally refer to the corresponding family of three-element subsets.
This does not affect the substance of the reduction.
The marginal calculations are correct:
Hence every marginal lies in \(\{0,1/2,1\}\).
The diminishing-returns verification covers every possible cardinality of \(A\):
Thus the proof of submodularity is complete.
The construction and theorem citation agree with Theorem \(5.1\) of the cited [AAMAS 2024 paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p1057.pdf).
A perfect \(3\)-dimensional matching supplies \(r\) disjoint designated triples covering all \(3r\) goods. These form an \(r\)-partition in which every bundle has value \(3\).
Since \(v(S)\le3\) for every \(S\), this proves that the MMS is exactly \(3\). This direction is correct.
Suppose a partition into \(r\) bundles has minimum value \(3\). Every bundle then has value \(3\).
The average bundle cardinality is \(3\). If one bundle had at least four goods, the remaining bundle cardinalities could not all be at least three; hence some bundle would have at most two goods and value at most \(2\), a contradiction. Therefore every bundle has exactly three goods.
A three-good bundle has value \(3\) precisely when it corresponds to a member of \(\mathcal T\). The bundles are disjoint and cover \(G\), so they yield a perfect \(3\)-dimensional matching.
This direction is correct. Strictly, the reduction should either restrict to the standard NP-hard family with \(r\ge2\) or mention the trivial \(r=1\) case, although no actual failure occurs when \(r=1\).
The equivalence between a positive perfect-matching instance and the threshold condition \(\operatorname{MMS}_{r,t}(G)\ge3\) is established. The construction is polynomial in the source size under the stated succinct representation.
Therefore the threshold problem is NP-hard under that representation.
Every bundle value belongs to \(\{0,1,2,5/2,3\}\). Therefore every partition minimum belongs to this set, and the maximum over partition minima also belongs to it.
If the matching instance is negative, the decision equivalence excludes MMS value \(3\); consequently the MMS is at most \(5/2\).
For a standard maximization approximation satisfying \(\alpha\operatorname{MMS}\le A\le\operatorname{MMS}\):
Thus comparison with \(5/2\) decides perfect \(3\)-dimensional matching. The same reasoning works when the algorithm returns a feasible partition with minimum value at least \(\alpha\) times optimum.
This correctly proves hardness for every fixed \(\alpha>5/6\). The approximation convention should remain explicit because other, nonstandard two-sided conventions would require separate formulation.
The proposed certificate is polynomial-sized even when \(N\) is binary encoded: assigning each of \(|G|\) goods a label in \([N]\) takes \(O(|G|\log N)\) bits, and at most \(|G|\) distinct bundles are nonempty.
The verifier can evaluate each nonempty bundle and, if empty bundles are permitted, evaluate the empty set once. This supports membership in NP if:
These qualifications are omitted. They affect only the optional NP-completeness strengthening, not the NP-hardness or approximation result.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.