Answer: —
Theorem 3.3 — class: hardness
Given a finite catalogue of complete additive valuation types \(V\), rational population masses \(\mu\), rational per-capita supplies \(q\), and a target ratio \(\rho\), decide whether there exists a clone-stable truthful no-money mechanism assigning integral bundles with mass variables \(x_{v,b}\) satisfying \(\sum_b x_{v,b}=\mu_v\) and \(\sum_{v,b}b_kx_{v,b}=q_k\), while every assigned type \(v\) receives bundles with \(v\cdot b\ge\rho\,\operatorname{MMS}_v(q)\), where \(\operatorname{MMS}_v(q)=\sup_{\pi:\,\mathbb E_\pi[b]=q}\min_{b\in\operatorname{supp}(\pi)}v\cdot b\), and every denominator-cleared finite clone realization is individually truthful.
Let \(V\) be a finite catalogue of nonnegative additive valuation vectors for \(m\) goods, \(\mu\) a rational distribution on \(V\), \(q\) a rational vector of per-capita supplies, and \(\rho\) a rational target ratio. A bundle is \(b\in\mathbb Z_{\ge0}^{m}\). Define \(\operatorname{MMS}_{v}(q)=\sup_{\pi:\,\mathbb E_{\pi}[b]=q}\min_{b\in\operatorname{supp}(\pi)}v\cdot b\).
A clone-stable mechanism is a family of no-money allocation rules for finite populations obtained by scaling \(\mu\) and \(q\) by a common denominator. At every compatible scale, its allocation induces the same rational masses \(x_{v,b}\), with \(\sum_b x_{v,b}=\mu_v\) and \(\sum_{v,b}b_kx_{v,b}=q_k\). Each finite rule is individually truthful under unilateral reports from \(V\). Whenever \(x_{v,b}>0\), require \(v\cdot b\ge\rho\,\operatorname{MMS}_{v}(q)\).
Is deciding whether such a mechanism exists in P, or is it NP-hard?
For two finite agents and at least four indivisible goods, no deterministic truthful cardinal mechanism guarantees a maximin-share ratio above \(1/2\); for four or five goods, ratio \(1/2\) is achievable. No result for the exact mass-and-clone decision problem was verified.
I do not establish whether the stated mechanism-existence problem is in \(\mathrm{P}\) or is \(\mathrm{NP}\)-hard. I prove that its benchmark-threshold subproblem is \(\mathrm{NP}\)-complete, and give an exact finite formulation of the allocation-mass constraints without truthfulness. The missing step is relating these results to truthful implementation at every compatible scale.
For computational statements, assume valuation coordinates are nonnegative rationals encoded in binary. The hardness construction uses strictly positive integer valuations.
Fix \(v\in\mathbb Q_{\ge 0}^{m}\) and \(q\in\mathbb Q_{\ge 0}^{m}\).
Proposition 1. The supremum defining \(\operatorname{MMS}_{v}(q)\) is attained. Moreover, some attaining distribution has finite support and rational probabilities.
Proof. First, a distribution with mean \(q\) exists: independently round each coordinate of \(q\) to its floor or ceiling, with probabilities preserving its expectation.
Choose a positive integer \(L\) such that every coordinate of \(Lv\) is integral. Every bundle utility belongs to \(\frac1L\mathbb Z_{\ge 0}\). Consequently, the utilities in any nonempty support have a minimum.
For any distribution \(\pi\) with mean \(q\),
\( \displaystyle \min_{b\in\operatorname{supp}(\pi)}v\cdot b \le \mathbb E_{\pi}[v\cdot b] =v\cdot q. \)
Thus the set of achievable minimum utilities is a nonempty subset of the finite set
\( \displaystyle \left\{\frac jL: j\in\mathbb Z_{\ge 0},\ j\le L(v\cdot q)\right\}. \)
It therefore has a maximum. This proves attainment. The finite rational realization follows from Proposition 2 below, applied to that maximum. ∎
To establish that realization, fix a rational threshold \(t\ge 0\). Define
\( \displaystyle S_v(t)=\{b\in\mathbb Z_{\ge 0}^{m}:v\cdot b\ge t\}, \)
and let \(D_v(t)\) be the coordinatewise minimal elements of \(S_v(t)\). Here, coordinatewise minimal means that no distinct \(d'\in S_v(t)\) satisfies \(d'\le d\).
For \(t=0\), we have \(D_v(0)=\{0\}\). For \(t>0\), every \(d\in D_v(t)\) satisfies:
Indeed, if \(d_k>0\), minimality gives \(v\cdot(d-e_k)<t\), where \(e_k\) is the \(k\)-th unit vector. Hence
\( \displaystyle (d_k-1)v_k\le v\cdot(d-e_k)<t, \)
which implies the asserted bound. In particular, \(D_v(t)\) is finite.
Proposition 2. A distribution with mean \(q\), supported on \(S_v(t)\), exists if and only if the following finite system is feasible:
\[ \displaystyle \lambda_d\ge 0,\qquad \sum_{d\in D_v(t)}\lambda_d=1,\qquad \sum_{d\in D_v(t)}\lambda_d d\le q. \tag{1} \]
Whenever it is feasible, a finite rational distribution with mean exactly \(q\) exists.
Proof. Suppose first that \(\pi\) is such a distribution. Every \(b\in S_v(t)\) dominates a minimal element: repeatedly delete one unit of a good whenever the threshold remains satisfied. This process terminates because the sum of the coordinates decreases at every deletion.
Choose one resulting minimal element \(d(b)\le b\) for every \(b\). Pushing \(\pi\) forward under this map gives weights satisfying (1).
Conversely, suppose (1) is feasible. Its coefficients are rational, so it has a rational feasible solution. Explicitly, its feasible region is a nonempty compact rational polytope, and any vertex is rational.
Let
\( \displaystyle r=q-\sum_d\lambda_d d\ge 0. \)
Choose a finite rational distribution on \(Z\in\mathbb Z_{\ge 0}^{m}\) with mean \(r\), using independent floor-or-ceiling rounding. Independently choose \(D=d\) with probability \(\lambda_d\), and set \(B=D+Z\). Then
\( \displaystyle \mathbb E[B]=q,\qquad v\cdot B\ge v\cdot D\ge t. \)
Both distributions have finite support and rational probabilities, so their sum does too. ∎
Consider the auxiliary problem whose input is \((v,q,t)\) and whose question is whether
\( \displaystyle \operatorname{MMS}_{v}(q)\ge t. \)
Theorem 3. This auxiliary problem is \(\mathrm{NP}\)-complete. Hardness holds even when every valuation coordinate is a positive integer and every supply coordinate equals \(\frac12\).
Nonpositive thresholds are immediate, so assume \(t>0\).
By Propositions 1 and 2, a yes-instance is equivalent to feasibility of (1). Introduce nonnegative slack variables to replace its coordinatewise inequalities by equalities. The resulting system has \(m+1\) equations and a nonempty bounded feasible region.
At a vertex, at most \(m+1\) variables are positive: otherwise the corresponding columns would be linearly dependent, permitting a nonzero perturbation in both directions while preserving feasibility.
The coordinates of every \(d\in D_v(t)\) have polynomial binary length, by the bounds preceding Proposition 2. Cramer's rule therefore bounds the binary lengths of the vertex weights polynomially in the input length.
A certificate lists at most \(m+1\) bundles and their rational weights. The verifier checks nonnegativity, total weight one, expected bundle coordinatewise at most \(q\), and utility at least \(t\) for every listed bundle. These checks take polynomial time. Minimality need not be checked: any bundles passing these checks yield a valid distribution by the augmentation argument in Proposition 2.
Reduce from PARTITION, the classical \(\mathrm{NP}\)-complete problem. Its hardness is established in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let the input be positive integers \(a_1,\ldots,a_n\) with
\( \displaystyle \sum_{i=1}^{n}a_i=2B. \)
Restricting to even total sum preserves hardness: doubling every number transforms an arbitrary PARTITION instance into one with even total sum and preserves its answer.
Set
\( \displaystyle R=1+n+2B+n\max_i a_i,\qquad H=R^{n+1}. \)
Create two goods for each index \(i\), with valuations
\( \displaystyle v_{i,+}=H+R^i+a_i,\qquad v_{i,-}=H+R^i. \)
Give every good per-capita supply \(\frac12\), and define
\( \displaystyle T=nH+\sum_{i=1}^{n}R^i+B. \)
These numbers have polynomial binary length. Their construction is therefore polynomial-time. Moreover,
\[ \displaystyle v\cdot q =\frac12\sum_{i=1}^{n}(v_{i,+}+v_{i,-}) =T. \tag{2} \]
I claim that the PARTITION instance is a yes-instance exactly when \(\operatorname{MMS}_{v}(q)\ge T\).
Forward direction. Suppose \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=B\). Define a binary bundle \(b\) that selects the \(+\) good for \(i\in I\) and the \(-\) good for \(i\notin I\). Then \(v\cdot b=T\).
Its coordinatewise complement \(\mathbf1-b\) also has utility \(T\), because the total utility of all goods is \(2T\). Giving these two bundles probability \(\frac12\) each produces mean \(q\) and minimum utility \(T\).
Reverse direction. Suppose \(\operatorname{MMS}_{v}(q)\ge T\). By Proposition 1 and (2), an attaining distribution has every supported utility at least \(T\) and expected utility exactly \(T\). Thus every supported bundle has utility exactly \(T\). Choose one such bundle \(b\).
Let
\( \displaystyle \ell=\sum_{i=1}^{n}(b_{i,+}+b_{i,-}). \)
Every good has value at least \(H\). Also, because \(B<R\),
\( \displaystyle T<(n+1)H. \)
Consequently \(\ell\le n\).
Expanding \(v\cdot b=T\) gives
\[ \displaystyle \ell H+ \sum_{i=1}^{n}(b_{i,+}+b_{i,-})R^i+ \sum_{i=1}^{n}a_i b_{i,+} = nH+\sum_{i=1}^{n}R^i+B. \tag{3} \]
All displayed coefficients are valid base-\(R\) digits:
\( \displaystyle \ell\le n<R,\qquad b_{i,+}+b_{i,-}\le n<R, \)
and
\( \displaystyle \sum_i a_i b_{i,+}\le n\max_i a_i<R. \)
The right side likewise has valid digits because \(n<R\) and \(B<R\). Uniqueness of base-\(R\) representation in (3) implies
\( \displaystyle b_{i,+}+b_{i,-}=1\quad\text{for every }i, \qquad \sum_i a_i b_{i,+}=B. \)
Therefore each \(b_{i,+}\) is binary, and the indices for which it equals one solve PARTITION. This completes the reduction. ∎
We can also characterize the mass constraints after omitting truthfulness and the requirement of implementation at every prescribed scale.
Let \(t_v\ge 0\) be a specified rational utility threshold for each \(v\in V\).
Proposition 4. There exist finite rational masses \(x_{v,b}\) satisfying
\( \displaystyle \sum_bx_{v,b}=\mu_v,\qquad \sum_{v,b}b_kx_{v,b}=q_k, \)
with \(v\cdot b\ge t_v\) whenever \(x_{v,b}>0\), if and only if the finite system
\[ \displaystyle y_{v,d}\ge0,\qquad \sum_{d\in D_v(t_v)}y_{v,d}=\mu_v \quad(v\in V), \tag{4} \]
\[ \displaystyle \sum_{v\in V}\sum_{d\in D_v(t_v)}d_k y_{v,d}\le q_k \quad(k=1,\ldots,m) \tag{5} \]
is feasible.
Proof. Given the masses, replace every supported bundle by a coordinatewise minimal bundle below it. This preserves each type's mass and threshold, and can only decrease resource consumption. The resulting weights satisfy (4)–(5).
Conversely, choose a rational feasible solution of (4)–(5), which exists whenever the system is feasible because its feasible region is a bounded rational polytope. Write the unused supply as
\( \displaystyle r=q-\sum_{v,d}d\,y_{v,d}\ge0. \)
Choose a type \(v_0\) with \(\mu_{v_0}>0\). For this type, independently augment every bundle by an integer random vector of mean \(r/\mu_{v_0}\), using finite rational floor-or-ceiling rounding. Leave other types unchanged.
The total increase in consumption is exactly \(r\). Nonnegative valuations ensure that augmentation preserves every threshold. The resulting masses are finite and rational and satisfy the required equalities. ∎
For the task's thresholds, use
\( \displaystyle t_v=\max\{0,\rho\,\operatorname{MMS}_{v}(q)\}. \)
Proposition 1 ensures these thresholds are rational. Thus (4)–(5) exactly characterize the mass relaxation, although enumerating its columns or computing its thresholds need not take polynomial time.
Clearing denominators of a feasible finite mass vector realizes it as an allocation at some population size, and replication realizes it at every multiple of that size. This statement alone supplies neither truthful report-dependent rules nor implementation at smaller scales that the task might also require.
Benchmark hardness does not prove mechanism-existence hardness. A concrete obstruction to that inference is the single-type mass relaxation: if \(V=\{v\}\) and \(0\le\rho\le1\), an attaining distribution from Proposition 1 always gives feasible masses. Thus its feasibility is automatic even though computing its benchmark is \(\mathrm{NP}\)-hard.
Truthfulness introduces constraints absent from (4)–(5). Under deterministic dominant-strategy truthfulness, a finite rule \(A^{(N)}\), defined on all report profiles, must satisfy
\( \displaystyle v\cdot A_i^{(N)}(v,r_{-i}) \ge v\cdot A_i^{(N)}(w,r_{-i}) \)
for every agent \(i\), true type \(v\), alternative report \(w\), and opponents' report profile \(r_{-i}\). The mass constraints at the prescribed population composition do not specify these off-composition outcomes.
Accordingly, a complete classification still requires either a polynomial-time method handling those incentive and scale constraints, or a reduction proving hardness of the full mechanism-existence question. Neither implication is established here.
⟨structured verdict parsed — rendered above⟩
The output establishes correct partial results under its stated rational binary input model. Propositions 1, 2, and 4 and the benchmark-threshold NP-completeness theorem are sound. It does not classify the full clone-stable truthful mechanism-existence problem, and it explicitly acknowledges this limitation.
The appropriate status is partial, with one major unresolved issue relative to the assigned task. I found no mathematical error in the auxiliary results.
The prover assumes nonnegative rational valuation coordinates encoded in binary. This makes its computational claims well-defined. The original task explicitly specifies rationality for the distribution, supplies, and ratio, but not for valuations; consequently, the computational results should be understood under the prover’s stated additional input convention.
The output carefully distinguishes three questions:
Only the first two receive results. Neither is asserted to be equivalent to the third.
Verified.
\( \mathbb E[v\cdot b]=v\cdot q \).
Thus every achievable minimum lies between zero and \(v\cdot q\).
The all-zero valuation case is covered: its benchmark is zero.
Verified.
For positive thresholds, minimal bundles cannot contain a unit of a zero-valued good, since removing that unit preserves utility. For a positive-valued coordinate, the displayed inequality correctly yields
\(d_k\leq \lceil t/v_k\rceil\).
These bounds imply finiteness.
The deletion procedure terminates because the sum of bundle coordinates decreases. Its terminal bundle is coordinatewise minimal: if a smaller feasible bundle existed, a single deletion toward it would preserve feasibility by nonnegativity of valuations.
For the two implications:
The empty-minimal-set case causes no exception: the normalization equation is then infeasible. In particular, a zero valuation cannot support a positive threshold.
Verified.
The certificate argument remains valid even though the full column set may be exponentially large.
Nonpositive thresholds are correctly treated as automatic yes-instances.
Verified.
The source problem is the standard NP-complete integer PARTITION problem, cited to [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). The reduction respects its positive-integer input restriction.
Doubling all input numbers preserves the existence of an equal partition and ensures an even total. The constructed base satisfies \(R>n\), \(R>B\), and \(R>n\max_i a_i\).
The bit length of \(H=R^{n+1}\) is polynomial in the input length. The valuations and threshold consequently also have polynomial bit length.
Equation (2), \(v\cdot q=T\), is correct.
A partition selects exactly one good per index and has utility \(T\). The complement also has utility \(T\), and their equal-probability mixture has every supply coordinate equal to one half. This establishes the required benchmark inequality.
Attainment and the expectation identity force every supported bundle to have utility exactly \(T\). This reasoning also applies to countably infinite support: any positive-probability bundle with strictly greater utility would make the expectation exceed \(T\).
The inequality \(T<(n+1)H\) is valid. Specifically, the lower-order quantity \(\sum_{i=1}^{n}R^i+B\) is less than \(R^{n+1}\), with \(B<R\). Thus the number of items in the selected bundle is at most \(n\).
All coefficients in equation (3) are valid base-\(R\) digits:
There are therefore no carries. Uniqueness of positional representation gives exactly one good per pair and selected input sum \(B\). This establishes the reverse implication.
The argument proves ordinary NP-hardness; it does not claim strong NP-hardness.
Verified.
The forward replacement preserves each type’s mass and threshold while reducing consumption coordinatewise.
For the reverse implication, the feasible region is bounded because each type’s nonnegative weights sum to its prescribed mass. Rational feasibility therefore yields rational weights.
A positive-mass type exists because \(\mu\) is a distribution. Augmenting its conditional bundles by a vector with mean \(r/\mu_{v_0}\) increases aggregate consumption by exactly \(r\). Nonnegative valuations preserve the threshold. Finite support and rationality are preserved.
Zero-mass types and empty minimal-bundle sets are handled correctly by equation (4).
The thresholds \(t_v=\max\{0,\rho\,\operatorname{MMS}_v(q)\}\) are rational under the stated assumptions. Truncation at zero preserves the original utility requirement because bundle utilities are nonnegative.
The denominator-clearing statement establishes allocation at some population size and its multiples. The prover correctly refrains from treating this as implementation at every prescribed scale.
Major — the full mechanism-existence decision problem remains unresolved.
The auxiliary NP-hardness theorem supplies no reduction to the assigned decision problem. Proposition 4 omits both incentive constraints and implementation at every compatible scale.
The singleton-type observation correctly demonstrates why benchmark hardness alone is insufficient: for ratios between zero and one, the singleton mass relaxation is automatically feasible despite the hardness of the general benchmark-threshold problem.
The displayed dominant-strategy inequality is correct for deterministic rules defined on all report profiles. However, no construction or characterization establishes that feasible masses extend to such rules. Likewise, denominator clearing does not settle smaller compatible scales.
Minimum additional work needed: a classification must address the full decision problem, either through a polynomial-time algorithm incorporating incentive and scale requirements or through a polynomial-time hardness reduction whose equivalence includes both requirements. This requires substantive new mathematics, not merely clarification of the existing proofs.
⟨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.