Answer: \(\mathrm{NP}\text{-complete}\), even for \(M=2\), \(\alpha_0=1\), and dyadic supplies and masses.
Theorem 3.4 — class: algorithmic
Given a finite set of complete valuation types \(T\) with masses \(\mu_t\), finite indivisible good classes \(G\), per-capita supplies \(s_g\), and additive values \(v_t(g)\in\{1,\ldots,M\}\), let \(\pi_r\) be a lottery over integral bundles \(b\in\mathbb Z_{\ge0}^{G}\) for report \(r\in T\). Maximize \(\alpha\), or decide whether \(\alpha\ge\alpha_0\), subject to \(\sum_{r\in T}\mu_r\sum_b\pi_r(b)b_g=s_g\), \(\sum_b\pi_t(b)v_t(b)\ge\sum_b\pi_r(b)v_t(b)\) for all \(t,r\), and \(v_t(b)\ge\alpha V_t\) whenever \(\pi_r(b)>0\), where \(V_t=\sum_{g\in G}s_gv_t(g)\).
A society is specified by its support: a nonempty list \(T\) of \(\tau\) complete valuation types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=|G|\ge1\) indivisible good classes, binary-rational per-capita supplies \(s_g\ge0\) with \(\sum_gs_g>0\), and additive values \(v_t(g)\in\{1,\ldots,M\}\), where \(M\ge1\) is an input integer. Write \(v_t(b)=\sum_gb_gv_t(g)\) and \(V_t=\sum_gs_gv_t(g)\).
For each allowed report \(r\in T\), choose a probability distribution \(\pi_r\) on \(\mathbb Z_{\ge0}^{G}\) with finite first moments; bundles have no additional size cap. Require exact aggregate feasibility \(\sum_r\mu_r\sum_b\pi_r(b)b_g=s_g\) for every \(g\).
Truthfulness in expectation means \(\sum_b\pi_t(b)v_t(b)\ge\sum_b\pi_r(b)v_t(b)\) for all \(t,r\in T\). The guaranteed fairness factor \(\alpha\) requires \(v_t(b)\ge\alpha V_t\) for every \(t,r\in T\) and every \(b\) with \(\pi_r(b)>0\).
Given a binary-rational threshold \(\alpha_0\in[0,1]\), is deciding whether such lotteries exist with \(\alpha\ge\alpha_0\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\) and \(M\), where \(L\) is the total binary input length.
For discrete societies, an efficient truthful randomized allocation guarantees every recipient at least \((1-\epsilon)/k\) of every truthful agent’s total value, for \(k\) agents and \(n\) goods when \(0<\epsilon<1\) and \(MkM^k/n<\epsilon\). [Mossel–Tamuz](https://www.tamuz.caltech.edu/papers/1003.5480.pdf)
For finitely many agents and non-atomic resources, truthful randomized equal division exists; this concerns divisible resources, rather than the mass society with integral bundles above. Neither verified result classifies the decision problem above. [Mossel–Tamuz](https://www.tamuz.caltech.edu/papers/1003.5480.pdf)
1. Result
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when
\(\displaystyle M=2,\qquad \alpha_0=1,\qquad s_g\in\left\{\frac14,\frac12\right\},\)
and every type mass is a positive dyadic rational.
The proof first eliminates the truthfulness constraints, then encodes graph coloring through the integral bundles. A finite-certificate argument establishes membership in \(\mathrm{NP}\).
2. Pooling eliminates the truthfulness constraints
Because every \(V_t\) is positive, existence with some \(\alpha\ge\alpha_0\) is equivalent to existence at \(\alpha=\alpha_0\).
Define
\(\displaystyle h_t=\left\lceil\alpha_0V_t\right\rceil,\qquad B=\left\{b\in\mathbb Z_{\ge0}^{G}:v_t(b)\ge h_t\text{ for every }t\in T\right\}.\)
The rounding is exact because every bundle value is integral.
Lemma. The instance is feasible if and only if there is one probability distribution \(p\) on \(B\), with finite first moments, whose mean is \(s\).
Proof. Given feasible report lotteries, define their pooled distribution by
\(\displaystyle p(b)=\sum_{r\in T}\mu_r\pi_r(b).\)
It is a probability distribution, its support lies in \(B\), and aggregate feasibility gives
\(\displaystyle \sum_b p(b)b_g=s_g\qquad\text{for every }g.\)
Its first moments are finite because there are finitely many report lotteries with finite first moments.
Conversely, given such a distribution \(p\), set \(\pi_r=p\) for every report \(r\). Aggregate feasibility holds because the masses sum to one. Fairness holds because \(p\) is supported on \(B\). For every \(t,r\),
\(\displaystyle \sum_b\pi_t(b)v_t(b)=\sum_b\pi_r(b)v_t(b),\)
so every truthfulness inequality holds with equality. \(\square\)
Thus the positive masses affect neither the existence criterion nor the hardness mechanism.
3. At threshold one, fairness inequalities become equalities
Suppose \(\alpha_0=1\), and let \(p\) be the pooled distribution. For every type \(t\),
\(\displaystyle v_t(b)\ge V_t\quad\text{on the support of }p,\qquad \mathbb E_p[v_t(b)]=v_t(s)=V_t.\)
Consequently,
\[\displaystyle v_t(b)=V_t\qquad\text{for every }t\text{ and every }b\text{ with }p(b)>0.\tag{1}\]
Indeed, the nonnegative random variable \(v_t(b)-V_t\) has expectation zero. Any positive-probability bundle with strictly positive excess would contradict that expectation.
4. Hardness with values one and two
We reduce from proper graph four-colorability. This problem is \(\mathrm{NP}\)-hard: graph three-colorability is \(\mathrm{NP}\)-complete, and adjoining one vertex adjacent to every original vertex transforms three-colorability into four-colorability. A four-coloring of the enlarged graph leaves at most three colors available to the original graph; conversely, a three-coloring extends by assigning the new vertex a fourth color. The starting hardness theorem is established in [Garey–Johnson–Stockmeyer](https://doi.org/10.1016/0304-3975(76)90059-1).
Let \(H=(U,E)\) be a finite simple graph, with \(n=|U|\ge1\) and \(e=|E|\). Use colors indexed by \(\{0,1,2,3\}\).
Goods and supplies. Introduce goods
\(\displaystyle x_{u,c}\quad(u\in U,\ c\in\{0,1,2,3\}),\)
and slack goods
\(\displaystyle z_{a,c}\quad(a\in E,\ c\in\{0,1,2,3\}).\)
Set
\(\displaystyle s_{x_{u,c}}=\frac14,\qquad s_{z_{a,c}}=\frac12.\)
There are \(m=4n+4e\) goods, and their total supply is
\(\displaystyle S=\sum_gs_g=n+2e.\)
Valuation types. Every unspecified value below is one.
These types are distinct, complete, and have values in \(\{1,2\}\). Their number is
\(\displaystyle \tau=1+n+4e.\)
Their total supply values are
\[\displaystyle V_{t_0}=S,\qquad V_{t_u}=S+1,\qquad V_{t_{a,c}}=S+1.\tag{2}\]
For the vertex types, the extra value is \(4\cdot\frac14=1\). For the edge-color types, it is \(\frac14+\frac14+\frac12=1\).
Choose positive dyadic masses as follows. Let \(q=\lceil\log_2\tau\rceil\), give each nonbaseline type mass \(2^{-q}\), and give the baseline type mass
\(\displaystyle \mu_{t_0}=1-(\tau-1)2^{-q}.\)
The baseline mass is positive because \(2^q\ge\tau\). Finally, set \(\alpha_0=1\).
Feasibility implies a proper coloring. Suppose the constructed instance is feasible. Take any positive-probability bundle \(b\) from its pooled distribution.
Write \(|b|=\sum_gb_g\). By (1) and the baseline equality,
\(\displaystyle |b|=S.\)
Subtracting this equality from each vertex-type equality in (2) gives
\[\displaystyle \sum_{c=0}^{3}b_{x_{u,c}}=1\qquad\text{for every }u.\tag{3}\]
The coordinates are nonnegative integers. Therefore exactly one of the four coordinates in (3) is one, and the others are zero. Assign that color to \(u\).
Likewise, subtracting the baseline equality from each edge-color equality gives
\[\displaystyle b_{x_{u,c}}+b_{x_{v,c}}+b_{z_{a,c}}=1.\tag{4}\]
The endpoints of an edge cannot both receive color \(c\), because then the left side of (4) would be at least two. Thus the extracted coloring is proper.
A proper coloring implies feasibility. Conversely, suppose \(\kappa:U\to\{0,1,2,3\}\) is a proper coloring.
For each \(j\in\{0,1,2,3\}\), shift every color by \(j\) modulo four. Define an integral bundle \(b^{(j)}\) by putting one unit in \(x_{u,c}\) precisely when \(u\)'s shifted color is \(c\), and setting, for each edge \(a=\{u,v\}\),
\(\displaystyle b^{(j)}_{z_{a,c}}=1-b^{(j)}_{x_{u,c}}-b^{(j)}_{x_{v,c}}.\)
Properness ensures that these slack coordinates belong to \(\{0,1\}\). Each vertex contributes one unit, and each edge contributes two slack units. Hence
\(\displaystyle |b^{(j)}|=n+2e=S.\)
Equations (3) and (4) hold, so every bundle has exactly the total supply value \(V_t\) under every type \(t\). Every bundle therefore satisfies fairness at threshold one.
Choose the four bundles with probability \(\frac14\) each. Every vertex visits every color once, giving
\(\displaystyle \mathbb E[b_{x_{u,c}}]=\frac14.\)
For an edge, its two differently colored endpoints occupy any specified color in exactly two of the four shifts. Thus
\(\displaystyle \mathbb E[b_{z_{a,c}}]=\frac12.\)
The mean is exactly \(s\). The pooling lemma supplies truthful report lotteries.
This proves the required equivalence.
Reduction size. The construction has
\(\displaystyle m=4(n+e),\qquad \tau=1+n+4e,\qquad M=2.\)
Its explicit valuation matrix and numerical data have binary length \(O((n+e)^2)\), and can be constructed in that many bit operations. The reduction is therefore polynomial.
5. Finite certificates and membership in NP
For a general instance, define
\(\displaystyle H_*=\max_{t\in T}h_t,\qquad C=\left\{c\in B:\sum_gc_g\le H_*\right\}.\)
Every fair bundle \(b\) contains a fair bundle \(c\le b\) belonging to \(C\). To prove this, choose a coordinatewise minimal fair sub-bundle of \(b\). Such a choice exists because \(b\) has finitely many sub-bundles.
If its total size exceeded \(H_*\), removing any one present unit would leave a bundle \(c'\) with
\(\displaystyle v_t(c')\ge\sum_gc'_g\ge H_*\ge h_t\qquad\text{for every }t,\)
using the assumption that every individual value is at least one. This contradicts minimality.
It follows that the instance is feasible exactly when there exist numbers \(\lambda_c\) satisfying
\[\displaystyle \lambda_c\ge0,\qquad \sum_{c\in C}\lambda_c=1,\qquad \sum_{c\in C}\lambda_cc_g\le s_g\quad\text{for every }g.\tag{5}\]
For necessity, replace each bundle in a feasible pooled lottery by a fixed fair sub-bundle in \(C\). This gives a distribution on the finite set \(C\), whose mean is coordinatewise at most \(s\).
For sufficiency, let
\(\displaystyle d=s-\sum_{c\in C}\lambda_cc\ge0.\)
Choose \(c\) with probabilities \(\lambda_c\). Independently choose a nonnegative integral random vector \(D\) with mean \(d\): each coordinate is its floor plus a Bernoulli variable whose mean is its fractional part. Then \(c+D\) is fair, has mean \(s\), and has finite support. Apply the pooling lemma.
It remains to bound the certificate length. The feasible region in (5) is a compact rational polytope. At an extreme point, at most \(m+1\) variables \(\lambda_c\) are positive. Indeed, if more were positive, their augmented columns \((c,1)\in\mathbb R^{m+1}\) would be linearly dependent. A sufficiently small perturbation in both directions along that dependence would preserve normalization, every coordinate mean, and nonnegativity, contradicting extremality.
For these at most \(m+1\) selected bundles, the corresponding rational feasible polytope has an extreme point. Its defining coefficients have absolute value at most \(H_*+1\). Clearing the supply denominators and applying Cramer's rule bounds each probability's encoding length by
\(\displaystyle O\!\left(L+m\log\bigl((m+1)(H_*+1)\bigr)\right).\)
Also,
\(\displaystyle H_*\le\left\lceil M\sum_gs_g\right\rceil,\)
so \(\log(H_*+1)=O(L+\log(m+1))\). The selected bundles and probabilities consequently have polynomial total encoding length.
A verifier checks their integrality, fairness, normalization, and the inequalities (5) using exact rational arithmetic in polynomial time. This proves membership in \(\mathrm{NP}\), and completes the \(\mathrm{NP}\)-completeness proof.
6. Running times and easy boundary cases
A deterministic algorithm enumerates \(C\) and solves the rational linear feasibility problem (5). Since
\(\displaystyle |C|\le(H_*+1)^m,\)
polynomial-time rational linear programming gives the bit running-time bound
\(\displaystyle (H_*+1)^{O(m)}\operatorname{poly}(m,\tau,L,\log(M+1)).\)
Using \(H_*\le\lceil Mm2^L\rceil\), a bound expressed entirely in the requested parameters is
\(\displaystyle 2^{O(m(L+\log(M+1)+\log(m+1)))}\operatorname{poly}(m,\tau,L,\log(M+1)).\)
In particular, this is \(2^{O(mL)}\operatorname{poly}(L)\) under the explicit input encoding. The certificate verification runs in polynomial time.
For \(M=1\), all bundle values equal their total size. Writing \(S=\sum_gs_g\), feasibility is equivalent to
\(\displaystyle S\ge\lceil\alpha_0S\rceil.\)
Necessity follows by taking expectations. For sufficiency, with \(h=\lceil\alpha_0S\rceil>0\), the vector \((h/S)s\le s\) lies in the convex hull of the fair bundles \(h e_g\); apply (5). The case \(h=0\) is immediate. This criterion is computable in polynomial time.
For \(m=1\), every positive valuation coefficient cancels from the fairness inequality. Feasibility is likewise equivalent to
\(\displaystyle s_g\ge\lceil\alpha_0s_g\rceil,\)
and is polynomial-time decidable for arbitrary \(M\).
The hardness result therefore already begins at \(M=2\), with unbounded \(m\) and \(\tau\). Unless \(\mathrm P=\mathrm{NP}\), no algorithm polynomial in \(m,\tau,L,M\) solves the general problem.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned decision problem in substance: its reduction establishes \(\mathrm{NP}\)-hardness under the stated restrictions, and its certificate argument establishes membership in \(\mathrm{NP}\). I found one minor imprecision in the certificate-size discussion, but no major mathematical gap.
The assumptions imply \(V_t>0\) for every type: some supply is positive, and every valuation coefficient is positive. A lottery satisfying fairness at some \(\alpha\ge\alpha_0\) also satisfies it at \(\alpha_0\); conversely, feasibility at \(\alpha_0\) meets the decision requirement.
Since \(v_t(b)\) is integral, replacing \(v_t(b)\ge\alpha_0V_t\) by \(v_t(b)\ge h_t\), where \(h_t=\lceil\alpha_0V_t\rceil\), is exact. This includes \(\alpha_0=0\).
Fairness in the task applies to every type, every report, and every bundle receiving positive probability. Consequently, every report lottery is supported on the same set \(B\).
The pooled distribution has total probability one, finite first moments, and mean \(s\). These conclusions use precisely the normalization of the masses, their nonnegativity, and the finiteness of the report set.
Conversely, assigning the same pooled distribution to every report satisfies all truthfulness inequalities with equality. Expected valuations are finite because there are finitely many goods, bounded valuation coefficients, and finite first moments.
Thus the lemma establishes an exact equivalence, rather than merely a necessary relaxation. The claim that masses do not affect feasibility is justified.
For each type, fairness makes \(v_t(b)-V_t\) nonnegative on the support, while exact aggregate feasibility makes its expectation zero. Therefore every positive-probability bundle has zero excess.
Bundles form a countable set, so this conclusion applies individually to every support bundle as claimed. There is no passage from an almost-sure statement to an unjustified assertion about zero-probability bundles.
The cited graph three-colorability hardness theorem is appropriate; the cited paper treats its \(\mathrm{NP}\)-completeness, including restricted graph families. [Garey–Johnson–Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
The universal-vertex transformation correctly reduces three-colorability to four-colorability in both directions.
The constructed society satisfies the task’s input requirements:
The restriction to \(n\ge1\) causes no hardness issue: the universal-vertex transformation already produces a nonempty graph.
A probability distribution on the countable bundle set has at least one positive-probability bundle. For such a bundle, the baseline equality fixes its total size at \(S\).
Subtracting the baseline equality from each vertex equality gives exactly one unit among that vertex’s four color coordinates. Nonnegative integrality therefore selects exactly one color.
Subtracting it from each edge-color equality gives the displayed slack equation. If both endpoints selected the same color, its left-hand side would be at least two, contradicting its value of one.
Every extracted coloring is consequently proper. No bundle-size cap is assumed or introduced.
Properness ensures that each slack coordinate is either zero or one. For each edge, exactly two colors are occupied by its endpoints, so exactly two slack coordinates equal one. This verifies the total bundle size \(n+2e\).
The vertex and edge-color equations then verify every type’s required equality.
Under the four cyclic shifts, each vertex occupies each color exactly once. For each edge and specified color, the two endpoints occupy that color in two distinct shifts. Hence the slack mean is exactly \(1/2\), and the vertex-coordinate mean is exactly \(1/4\).
The resulting finite lottery has the required mean and finite first moments. The pooling lemma supplies the required truthful report lotteries.
The explicit valuation matrix has quadratic size in \(n+e\); the masses require only logarithmically many bits each. The stated polynomial reduction size is valid.
A coordinatewise minimal fair sub-bundle exists because a fixed integral bundle has finitely many sub-bundles.
If its size exceeds the integer \(H_*\), deleting one present unit leaves size at least \(H_*\). Since every unit is worth at least one to every type, the remaining bundle is still fair. This contradicts minimality and verifies the claimed size bound.
When \(H_*=0\), the zero bundle is fair and is the minimal sub-bundle, so the argument covers this boundary case.
Necessity of (5) follows by replacing each bundle with a selected fair sub-bundle. The selection occurs on a countable set and requires no additional measurable-selection assumption.
Sufficiency also holds: the proposed integral random vector \(D\) has finite support and mean \(d\), and adding it preserves fairness because all valuation coefficients are positive. Thus the coordinatewise inequalities in (5) genuinely suffice for exact feasibility.
Conditional on feasibility, the region in (5) is a nonempty compact rational polytope and has an extreme point. The linear-dependence perturbation argument correctly bounds its positive support by \(m+1\): preserving all coordinate means preserves every inequality, including the tight ones.
The subsequent use of a vertex on the selected coordinates and Cramer’s rule is appropriate. Rational vertex-size bounds and their determinant justification are standard. [MIT linear-programming notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html)
Minor issue: The sentence “Its defining coefficients have absolute value at most \(H_*+1\)” is ambiguous and false if it includes the right-hand sides. Supplies need not obey that bound.
A concrete example is \(m=\tau=M=1\), \(s_g=4\), and \(\alpha_0=0\). Then \(H_*=0\), while the supply inequality has right-hand side \(4>H_*+1\).
This does not invalidate the certificate bound: the matrix entries have the claimed bound, and the supplies’ encoding lengths are already included in \(L\).
Minimum clarification: Specify that the bound applies to the coefficient matrix before denominator clearing, and explicitly account for the supply right-hand sides through their total input encoding length \(L\). Briefly identify the independent tight equations to which Cramer’s rule is applied. These are routine expositional clarifications requiring no new mathematical argument.
The bound on \(\log(H_*+1)\), the polynomial encoding length of the selected bundles, and exact rational certificate verification are otherwise valid.
The enumeration bound \(|C|\le(H_*+1)^m\) holds because each coordinate lies between zero and \(H_*\). Testing fairness and constructing the rational feasibility instance require polynomial work per candidate. Polynomial-time rational linear feasibility therefore gives the stated exponential upper bound.
The conversion to the requested parameters is valid under the explicit binary input encoding. In particular, \(m\), \(\tau\), and \(\log(M+1)\) are bounded by the input length up to encoding constants, supporting the simplified bound.
For \(M=1\), fairness is exactly a lower bound on integral bundle size. The stated necessity follows from expectation; the supplied convex-hull argument verifies sufficiency when \(h>0\). The case \(h=0\) is covered by the zero bundle and the established augmentation construction.
For \(m=1\), division by the positive valuation coefficient leaves the same bundle-count threshold for every type. The stated criterion is therefore correct, including supplies below one and threshold zero.
Since hardness already holds at \(M=2\), the final exclusion of an algorithm polynomial in \(m,\tau,L,M\), unless \(\mathrm P=\mathrm{NP}\), follows.
⟨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.