Answer: \(\mathsf{NP}\)-complete, even for \(\tau=1\), uniform capacities \(q_g=1/m\), integer utilities and threshold, and \(m=2T\).
Theorem 5.4 — class: hardness
Given a mass-one society with one type \(a\), common utility \(u:G\to\mathbb{Q}_{\ge 0}\), \(T\) rounds, per-round good capacities \(q_g\ge 0\), and threshold \(\kappa\), does there exist \(y_\sigma\ge 0\) for trajectories \(\sigma\in G^T\) such that \(\sum_\sigma y_\sigma=1\), \(\sum_{\sigma:\,\sigma_t=g}y_\sigma\le q_g\) for every round \(t\) and good \(g\), and every trajectory with \(y_\sigma>0\) satisfies \(\sum_{t=1}^{T}u(\sigma_t)\ge\kappa\)? The optimization version maximizes the essential-minimum trajectory utility.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here the society has one type \(a\) of mass \(1\), so \(\tau=1\).
Let \(G\) be a nonempty set of \(m\) goods, with common utility \(u:G\to\mathbb{Q}_{\ge0}\), capacities \(q_g\in\mathbb{Q}_{\ge0}\) satisfying \(\sum_{g\in G}q_g\ge1\), and threshold \(\kappa\in\mathbb{Q}_{\ge0}\). These rationals and the positive integer \(T\) are binary encoded; \(L\) is the total input bit length.
Capacities are renewed each round, unused capacity is allowed, and each individual receives exactly one good per round; the same good may recur in an individual's trajectory.
A feasible assignment consists of real masses \(y_\sigma\ge0\), indexed by \(\sigma\in G^T\), such that \(\sum_{\sigma\in G^T}y_\sigma=1\) and \(\sum_{\sigma:\sigma_t=g}y_\sigma\le q_g\) for every \(t\in\{1,\ldots,T\}\) and \(g\in G\). It meets the threshold when \(y_\sigma>0\) implies \(\sum_{t=1}^T u(\sigma_t)\ge\kappa\).
Is deciding whether a feasible assignment meets the threshold in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard? State running times in \(m\), \(\tau\), \(L\), and \(T\), with polynomial time measured against the binary input length.
For finitely many agents with identical utilities and unit capacity per good per round, threshold feasibility is \(\mathsf{NP}\)-complete; exact optimization is polynomial-time solvable when \(T\) is a multiple of the number \(n\) of agents. [Source](https://arxiv.org/html/2510.04624v1#S5.SS3)
No result settling exactly the mass-assignment problem above was located in the search.
The decision problem is \(\mathsf{NP}\)-complete, even when \(\tau=1\), every capacity is \(q_g=1/m\), all utilities and the threshold are integers, and \(m=2T\).
Consequently, a polynomial-time algorithm in the binary input length \(L\) exists if and only if \(\mathsf{P}=\mathsf{NP}\). The proof below applies directly to the stated mass-assignment model.
For a trajectory \(\sigma\in G^T\), define its count vector \(x(\sigma)\) by
\[
\text{}
\]
\(x_g(\sigma)=|\{t:\sigma_t=g\}|\).
Thus \(x(\sigma)\in\mathbb Z_{\ge0}^m\), \(\sum_gx_g(\sigma)=T\), and its utility is \(\sum_gu(g)x_g(\sigma)\). Define
\(\mathcal H=\{x\in\mathbb Z_{\ge0}^m:\sum_gx_g=T,\ \sum_gu(g)x_g\ge\kappa\}\).
Lemma. Threshold feasibility is equivalent to feasibility of the rational linear system
\(\displaystyle p_x\ge0\quad(x\in\mathcal H),\qquad \sum_{x\in\mathcal H}p_x=1,\qquad \sum_{x\in\mathcal H}p_xx_g\le Tq_g\quad(g\in G).\)
Proof. Given a feasible trajectory assignment, aggregate the masses of trajectories having the same count vector. Then
\(\displaystyle \sum_xp_xx_g=\sum_{t=1}^T\sum_{\sigma:\sigma_t=g}y_\sigma\le Tq_g.\)
Every positive-mass count vector belongs to \(\mathcal H\).
Conversely, suppose the displayed system is feasible. For each \(x\) with positive mass, choose a length-\(T\) word containing \(x_g\) copies of each good \(g\). Distribute mass \(p_x/T\) to each of its \(T\) cyclic rotations, adding masses when rotations coincide.
At any fixed position, exactly \(x_g\) of these rotations contain \(g\). Hence the mass receiving \(g\) in each round is
\(\displaystyle \sum_xp_x\frac{x_g}{T}\le q_g.\)
Every rotation has utility \(\sum_gu(g)x_g\ge\kappa\), and the total mass is one. This proves the equivalence. \(\square\)
We use the classical \(\mathsf{NP}\)-complete problem \(\mathsf{PARTITION}\): given positive binary-encoded integers \(a_1,\ldots,a_n\), decide whether some \(S\subseteq\{1,\ldots,n\}\) satisfies \(2\sum_{i\in S}a_i=\sum_{i=1}^na_i\). Its \(\mathsf{NP}\)-completeness is established in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Write
\(A=\sum_{i=1}^na_i,\qquad B=n+1,\qquad M=2nA+1,\qquad C=\sum_{i=1}^nB^{i-1}.\)
Create two goods \(g_i^0,g_i^1\) for each index \(i\), and set
\(m=2n,\qquad T=n,\qquad q_{g_i^0}=q_{g_i^1}=\frac1{2n},\qquad \kappa=MC+A.\)
Their common utilities are
\(u(g_i^0)=MB^{i-1},\qquad u(g_i^1)=MB^{i-1}+2a_i.\)
The society consists of one type of mass one. All utilities and the threshold are nonnegative integers, and the capacities sum to one.
Every utility and the threshold have bit length \(O(\log(A+1)+n\log(n+1))\). Thus the construction takes polynomial time in the source input length and produces an instance of polynomial binary length.
Suppose the constructed instance is feasible, and use the lemma to obtain masses \(p_x\). Put
\(\displaystyle z_g=\sum_xp_xx_g.\)
For every good, \(z_g\le Tq_g=1/2\). Also,
\(\displaystyle \sum_gz_g=\sum_xp_x\sum_gx_g=T=n.\)
There are \(2n\) goods, so their upper bounds sum to \(n\). Therefore every bound is attained: \(z_g=1/2\) for every \(g\).
Consequently, the average trajectory utility is
\(\displaystyle \sum_xp_x\sum_gu(g)x_g =\frac12\sum_{i=1}^n\bigl(u(g_i^0)+u(g_i^1)\bigr) =MC+A=\kappa.\)
Every positive-mass count vector has utility at least \(\kappa\). Since their average equals \(\kappa\), each has utility exactly \(\kappa\).
Choose any positive-mass count vector \(x\). Define
\(c_i=x_{g_i^0}+x_{g_i^1},\qquad V=\sum_{i=1}^na_i x_{g_i^1}.\)
Its exact utility equation is
\(\displaystyle M\sum_{i=1}^nc_iB^{i-1}+2V=MC+A.\)
Because \(\sum_gc_g\) here is represented by \(\sum_ic_i=n\), we have
\(\displaystyle 0\le V\le nA,\qquad 0\le2V\le2nA<M,\qquad 0\le A<M.\)
Reducing the exact utility equation modulo \(M\) therefore gives \(2V=A\): the two congruent quantities are both between zero and \(M-1\). Substituting back yields
\(\displaystyle \sum_{i=1}^nc_iB^{i-1}=\sum_{i=1}^nB^{i-1}.\)
Each \(c_i\) satisfies \(0\le c_i\le n=B-1\). Both sides are therefore base-\(B\) expansions with valid digits. Uniqueness of positional representation implies \(c_i=1\) for every \(i\).
Thus \(x_{g_i^1}\in\{0,1\}\), and the set \(S=\{i:x_{g_i^1}=1\}\) satisfies
\(\displaystyle 2\sum_{i\in S}a_i=2V=A.\)
The original partition instance is a yes-instance.
Conversely, suppose \(S\) satisfies \(2\sum_{i\in S}a_i=A\).
Define \(x\) by choosing \(g_i^1\) when \(i\in S\), and \(g_i^0\) otherwise, with one chosen good from each pair. Define \(\bar x\) by choosing the opposite good in every pair.
Both count vectors have total count \(n\), and both have utility \(MC+A=\kappa\), because \(S\) and its complement each have sum \(A/2\).
Assign mass \(1/2\) to each count vector. Every good then has expected count \(1/2=Tq_g\). By the lemma, these masses yield a feasible trajectory assignment meeting the threshold.
The reduction is therefore correct in both directions, proving \(\mathsf{NP}\)-hardness.
It remains to justify a polynomial certificate despite the potentially enormous trajectory set.
Add nonnegative slack variables to the count-vector linear system:
\(\displaystyle \sum_xp_x=1,\qquad \sum_xp_xx_g+s_g=Tq_g\quad(g\in G).\)
This system has \(r=m+1\) equality constraints. Its feasible region, when nonempty, is compact: the masses lie between zero and one, and \(0\le s_g\le Tq_g\). Hence it has an extreme point.
At an extreme point, the columns corresponding to positive variables are linearly independent. Otherwise, a nonzero dependence would allow sufficiently small perturbations in both directions, preserving all equalities and nonnegativity, contradicting extremality. Thus at most \(m+1\) variables are positive, and in particular at most \(m+1\) count vectors have positive mass.
The equality matrix is integral, with entries bounded by \(T\). Let \(D\) be the product of the denominators of the capacities. Its bit length is \(O(L)\), and multiplying the right-hand side by \(D\) gives integers of bit length \(O(L+\log(T+1))\).
The matrix has full row rank whenever \(\mathcal H\) is nonempty: the slack columns span the last \(m\) coordinates, and any count-vector column has first coordinate one. Extend the positive columns of an extreme point to a basis. Cramer’s rule, together with the determinant bound for an \(r\)-dimensional integer matrix, shows that each positive mass has numerator and denominator bit length
\(O\bigl(L+m\log(m+1)+m\log(T+1)\bigr).\)
A certificate therefore lists at most \(m+1\) integer count vectors and their rational masses. Each count-vector entry needs only \(O(\log(T+1))\) bits. All threshold, normalization, and capacity inequalities can be checked by exact rational arithmetic in polynomial time.
Since \(m\) and \(\log(T+1)\) are bounded by the binary input length, the certificate size and verification time are polynomial in \(L\). The problem belongs to \(\mathsf{NP}\).
For the specified model, \(\tau=1\) throughout.
Let \(H=\binom{T+m-1}{m-1}\), the number of nonnegative integer count vectors summing to \(T\). Enumerating these vectors, retaining those meeting the threshold, and solving the lemma’s rational linear system takes
\((H+m+L)^{O(1)}\)
bit operations. This follows from polynomial-time rational linear programming: there are at most \(H\) variables, \(m+1\) constraints, and coefficients of polynomial bit length.
In particular:
The enumeration bound is generally exponential in the binary length of \(T\). Moreover, the reduction already has \(T=m/2\), so even a running-time bound polynomial in \(m,\tau,L,T\) would imply \(\mathsf{P}=\mathsf{NP}\). Hardness therefore persists with unary-encoded \(T\), although this reduction uses binary-encoded utilities of potentially large numerical magnitude.
⟨structured verdict parsed — rendered above⟩
The prover establishes that the stated mass-assignment problem is \(\mathsf{NP}\)-complete, including the claimed restricted instances. The reduction and the polynomial certificate argument are sound. I found no major issue; two minor presentation issues are listed below.
Both directions of the lemma are correct.
Aggregating trajectory masses preserves total mass and threshold satisfaction. For each good, its expected count equals the sum of its marginal masses over all rounds, so the bound \(Tq_g\) follows from the original constraints.
Conversely, distributing each count-vector mass over all \(T\) cyclic rotations produces the required marginal \(p_xx_g/T\) at every position. Rotations must be counted with multiplicity; the prover explicitly handles this by adding masses when rotations coincide. Thus periodic words do not invalidate the construction.
The lemma respects the model’s requirements:
This construction proves existence; it need not explicitly enumerate the trajectories in polynomial time. Consequently, binary encoding of \(T\) presents no problem for this equivalence.
The phrase “rational linear system” describes its coefficients, rather than requiring the original real masses to be rational. Section 3 subsequently establishes the existence of a rational certificate.
The source problem is correctly specified as equal-sum partition of positive binary-encoded integers. Its \(\mathsf{NP}\)-completeness is a valid standard premise, also stated in [MIT’s complexity lecture notes](https://people.csail.mit.edu/rrw/6.1400-2025/lec19-color.pdf).
The constructed instance satisfies every input restriction:
The encoding estimate is correct. The largest positional factor is \(B^{n-1}\), whose bit length is \(O(n\log(n+1))\). Multiplication by \(M=2nA+1\), and the additions appearing in the utilities and threshold, give the stated bound
\(O(\log(A+1)+n\log(n+1))\).
There are only \(2n\) utilities to encode. Thus the complete output size and construction time are polynomial in the source input length. Large numerical utility values do not invalidate a reduction with binary encoding.
This step is correct.
Every expected count satisfies \(z_g\le 1/2\). Their sum is \(n\), which equals the sum of all \(2n\) upper bounds. Hence every bound must be attained.
The average utility calculation is exact:
\[ \frac12\sum_{i=1}^{n}\bigl(u(g_i^0)+u(g_i^1)\bigr)=MC+A=\kappa. \]
Every count vector with positive mass has utility at least \(\kappa\). Because the distribution is finite and has average exactly \(\kappa\), none of its positive-mass vectors can have utility strictly greater than \(\kappa\).
Saturation is used only for the constructed instances, where capacities sum to \(1\). The prover does not incorrectly assume it for general inputs allowing unused capacity.
The arithmetic and digit argument are correct.
The count vector has total count \(n\), so \(0\le V\le nA\). Therefore
\(0\le 2V\le 2nA<M\), and also \(0\le A<M\).
Reducing the exact utility equation modulo \(M\) is legitimate because all its terms are integers. The two residues \(2V\) and \(A\) lie in the stated range, so congruence implies equality.
After substituting \(2V=A\), the positional sums coincide. Each \(c_i\) lies between \(0\) and \(n=B-1\), so both expressions have valid base-\(B\) digits. Uniqueness of positional representation therefore applies without carries and gives \(c_i=1\).
Nonnegative integer counts then imply \(x_{g_i^1}\in\{0,1\}\), and the selected indices give exactly the required partition.
Odd \(A\) is also handled: the forced equation \(2V=A\) cannot hold. No separate parity assumption is needed.
Minor issue 1 — undefined notation. The sentence beginning “Because \(\sum_gc_g\) here…” uses \(c_g\), which was never defined. The surrounding definition and the explicit identity \(\sum_ic_i=n\) make the intended statement unambiguous.
Minimum clarification: Remove the undefined expression and state the total-count identity using the defined \(c_i\).
The converse is correct.
Each of the two complementary count vectors chooses exactly one good from every pair and has total count \(n\). The partition and its complement each contribute additional utility \(A\), so both vectors have utility \(\kappa\).
Giving each vector mass \(1/2\) makes every good’s expected count \(1/2=Tq_g\). The established lemma then yields a trajectory assignment satisfying every round’s capacity constraints.
Thus the reduction proves equivalence, rather than merely one implication.
The certificate argument is valid even when \(T\) is binary encoded.
The slack-variable feasible region is finite-dimensional, closed, and bounded. Every mass lies in \([0,1]\), and each slack lies in \([0,Tq_g]\). A nonempty such polytope has an extreme point.
The argument that positive columns are linearly independent is correct: a dependence supported on positive variables permits sufficiently small perturbations in both directions. Hence at most \(m+1\) variables are positive, including at most \(m+1\) count-vector variables.
The matrix entries are integers bounded by \(T\); the slack entries are also covered because \(T\ge1\). If feasibility holds, \(\mathcal H\) is nonempty. Its columns together with the slack columns give full row rank, as claimed.
The denominator product \(D\) has bit length bounded by the total encoded denominator length. Clearing the right-hand-side denominators therefore costs only \(O(L+\log(T+1))\) bits. Cramer’s rule and the standard determinant estimate support the stated polynomial bound on mass numerators and denominators.
Each count-vector entry is at most \(T\), so its encoding uses only \(O(\log(T+1))\) bits. The verifier can check nonnegativity, total counts, utilities, normalization, and expected-count bounds using exact rational arithmetic. It never needs to expand the certificate into length-\(T\) trajectories.
Zero capacities and zero utilities cause no failure in this reasoning. If \(\mathcal H\) is empty, normalization makes feasibility impossible.
Minor issue 2 — determinant theorem not stated precisely. The phrase “the determinant bound for an \(r\)-dimensional integer matrix” leaves the particular bound unstated. The claimed bit-length consequence is correct, but the requested verification standard calls for an explicit theorem statement.
Minimum clarification: State the determinant inequality being invoked, including its dependence on dimension and entry magnitude, and indicate that it also bounds the determinants occurring after replacement of a column by the cleared right-hand side. This is a routine exposition repair.
The enumeration count \(H=\binom{T+m-1}{m-1}\) is correct.
The resulting LP has at most \(H\) mass variables, \(m+1\) constraints, and coefficient bit lengths polynomial in the input length. Polynomial-time rational LP feasibility therefore gives the stated bound \((H+m+L)^{O(1)}\).
Both specializations are valid:
The second bound is polynomial in the numerical value of \(T\) for fixed \(m\), not necessarily in its binary encoding length. The prover explicitly acknowledges this distinction.
Finally, the reduction has \(T=n=m/2\). A running time polynomial in \(m,\tau,L,T\) would consequently solve the source instances in polynomial time. The unary-\(T\) hardness claim is therefore justified. The write-up correctly refrains from claiming hardness with numerically bounded utilities.
The supplied finite-agent result is not used to infer hardness for divisible masses. The prover establishes hardness directly for the requested continuous model.
The target is resolved, with only the two minor clarifications above.
⟨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.