Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, even when \(\tau=s=2\); therefore \(\mathrm{NP}\)-hard under polynomial-time Turing reductions.
Corollary 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of deciding whether a given balanced allocation is PO is coNP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite good catalogue \(G\), \(k\in\mathbb{N}\), rational per-capita supplies \(\rho\in\mathbb{Q}_+^G\) with \(\sum_{g\in G}\rho_g=k\), valuation types \(v_t\in\mathbb{Q}_+^G\), rational masses \(\mu\in\mathbb{Q}_+^\tau\) with \(\sum_t\mu_t=1\), and an explicit finite-support candidate allocation \(y_{t,B}\) over integral bundles \(B\in\mathbb{Z}_+^G\) satisfying \(\sum_g B_g=k\), \(\sum_B y_{t,B}=\mu_t\), and \(\sum_{t,B}y_{t,B}B_g=\rho_g\), decide whether there is no nontrivial mass-preserving reassignment \(z_{t,B,B'}\) such that \(\sum_{B'}z_{t,B,B'}=y_{t,B}\), \(\sum_{t,B,B'}z_{t,B,B'}B'_g=\rho_g\), \(z_{t,B,B'}=0\) whenever \(v_t(B')<v_t(B)\), and \(\sum_{t,B,B':\,v_t(B')>v_t(B)}z_{t,B,B'}>0\).
Let \(G\) be a nonempty catalogue of \(m\) good categories, with repeatable copies, and let \(k\geq1\) be an integer. Write \(\mathcal B_k=\{B\in\mathbb Z_{\geq0}^{G}:\sum_g B_g=k\}\). Type \(t\) has nonnegative rational additive valuations \(v_t(B)=\sum_g v_{tg}B_g\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(\sum_t\mu_t=1\).
The input includes nonnegative rational supplies \(\rho_g\) with \(\sum_g\rho_g=k\), and an explicit list of positive rational entries \(y_{t,B}\), with omitted entries zero, satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B}y_{t,B}B_g=\rho_g\).
An improving reassignment consists of nonnegative real masses \(z_{t,B,B'}\), indexed by \(B,B'\in\mathcal B_k\), satisfying \(\sum_{B'}z_{t,B,B'}=y_{t,B}\), \(\sum_{t,B,B'}z_{t,B,B'}B'_g=\rho_g\), and \(z_{t,B,B'}=0\) whenever \(v_t(B')<v_t(B)\), with \(\sum_{t,B,B':v_t(B')>v_t(B)}z_{t,B,B'}>0\). Destination bundles range over all of \(\mathcal B_k\).
Decide whether no improving reassignment exists. Is this problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions? State running times in \(m,\tau,s,L\), where \(s\) is the number of listed allocation entries and \(L\) is the total binary input length, including \(k\) and bundle coordinates.
For finite agents and individually distinct goods, checking balanced Pareto optimality is \(\mathrm{coNP}\)-complete, whereas checking balanced fractional Pareto optimality is polynomial-time solvable ([source](https://arxiv.org/html/2603.05956v1)). No result settling the mass-reassignment problem defined above was located.
1. Classification. The problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. Consequently, it is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, and a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).
Hardness holds even when \(\tau=s=2\), both types have mass \(\frac12\), and all valuations are nonnegative integers. The binary encoding of \(k\) is essential to the reduction below.
2. An arithmetic problem used in the reduction. Consider binary-encoded positive integers \(a_1,\ldots,a_n,T\). The question is whether
\(\displaystyle \sum_{i=1}^{n}a_i d_i=T\quad\text{for some }d\in\mathbb Z_{\geq0}^{n}.\)
This unbounded subset-sum problem is \(\mathrm{NP}\)-complete. Membership follows because every solution satisfies \(d_i\leq T\). For completeness, here is a reduction establishing hardness from the standard positive-integer SUBSET SUM problem, whose \(\mathrm{NP}\)-completeness is classical. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Let the SUBSET SUM instance consist of positive integers \(w_1,\ldots,w_r,W\). Define
\(\displaystyle M=r+1,\qquad H=M^r,\qquad S=\sum_{i=1}^{r}M^{i-1},\qquad Q=1+W+r\max_i w_i.\)
For each \(i\), introduce two available numbers
\(\displaystyle u_i=Q(H+M^{i-1})+w_i,\qquad \ell_i=Q(H+M^{i-1}),\)
and set the target to \(U=Q(rH+S)+W\). All these numbers have binary length polynomial in the original input length.
Suppose nonnegative multiplicities \(x_i,y_i\) satisfy
\(\displaystyle \sum_i(x_i u_i+y_i\ell_i)=U.\)
Write \(c=\sum_i(x_i+y_i)\). Every available number is at least \(QH\), while \(S\leq H-1\) and \(W<Q\) imply \(U<(r+1)QH\). Thus \(c\leq r\).
Reduction modulo \(Q\) gives \(\sum_i x_iw_i\equiv W\pmod Q\). Both sides lie between zero and \(Q-1\), since \(\sum_i x_iw_i\leq r\max_iw_i<Q\). Hence \(\sum_i x_iw_i=W\). Subtracting this equality and dividing by \(Q\) yields
\(\displaystyle cH+\sum_i(x_i+y_i)M^{i-1}=rH+S.\)
Every coefficient \(x_i+y_i\) is at most \(r=M-1\), so the sum on the left after \(cH\) is at most \(H-1\). Taking integer quotients by \(H\) gives \(c=r\). Uniqueness of base-\(M\) representation then gives \(x_i+y_i=1\) for every \(i\). Consequently, \(x\in\{0,1\}^{r}\) solves the original SUBSET SUM instance.
Conversely, a solution of SUBSET SUM selects \(u_i\) for each chosen index and \(\ell_i\) for every other index, giving sum \(U\). This proves the claimed hardness.
3. Construction of the reassignment instance. Fix an unbounded subset-sum instance \(a_1,\ldots,a_n,T\), with every number positive. Introduce \(m=n+2\) categories: item categories \(g_1,\ldots,g_n\), a marker \(h\), and a filler \(f\). Set
\(\displaystyle k=nT+1,\qquad p=(a_1,\ldots,a_n,T,0).\)
Here \(p(B)\) means the auxiliary integer weight \(p\cdot B\), not a valuation shared by both types.
There are two types, denoted \(A\) and \(R\), each of mass \(\frac12\). Define their category valuations by
\(\displaystyle v_{A,g_i}=(k+1)a_i+1,\qquad v_{A,h}=(k+1)T,\qquad v_{A,f}=0,\)
and
\(\displaystyle v_{R,g_i}=a_i,\qquad v_{R,h}=T,\qquad v_{R,f}=0.\)
Their initial bundles are
\(\displaystyle B^A=(0,\ldots,0,1,k-1),\qquad B^R=(T,\ldots,T,0,1).\)
Both bundles have cardinality \(k\). List precisely the two allocation entries
\(\displaystyle y_{A,B^A}=y_{R,B^R}=\frac12,\)
and define supplies by
\(\displaystyle \rho=\frac12(B^A+B^R)=\left(\frac T2,\ldots,\frac T2,\frac12,\frac k2\right).\)
These supplies are positive and sum to \(k\). The allocation and mass consistency conditions therefore hold.
All coordinates and valuations have binary length polynomial in the unbounded subset-sum input length. In particular, writing the coordinate \(T\) does not require listing \(T\) copies. Thus this is a polynomial-time construction with \(\tau=s=2\).
4. Correctness of the reduction. We prove that an improving reassignment exists exactly when the unbounded subset-sum instance has a solution.
For any destination bundle \(D\), write \(c(D)=\sum_{i=1}^{n}D_{g_i}\). Then
\(\displaystyle v_A(D)=(k+1)p(D)+c(D),\qquad 0\leq c(D)\leq k.\)
Type \(A\)'s initial utility is \((k+1)T\). If \(p(D)<T\), integrality gives \(p(D)\leq T-1\), and therefore
\(\displaystyle v_A(D)\leq(k+1)(T-1)+k=(k+1)T-1.\)
Such a destination is forbidden. Thus every permitted destination for type \(A\) satisfies \(p(D)\geq T=p(B^A)\).
For type \(R\), its valuation is exactly \(p\). Every permitted destination therefore satisfies
\(\displaystyle p(D)\geq p(B^R)=T\sum_i a_i.\)
Now consider any reassignment satisfying the nonworsening constraints. Every positive reassigned mass has a nonnegative change in its auxiliary weight. Supply conservation gives
\(\displaystyle \sum_{t,B,D}z_{t,B,D}\bigl(p(D)-p(B)\bigr)=0.\)
This is a finite sum of nonnegative terms. Hence every positive reassigned mass must satisfy \(p(D)=p(B)\).
It follows that type \(R\) can never improve strictly. Every destination used by type \(A\) has \(p(D)=T\), and its utility gain is exactly \(c(D)\). Thus an improving reassignment must use a type-\(A\) destination with \(p(D)=T\) and \(c(D)>0\).
The marker contributes weight \(T\) per copy, and every item category has positive weight. Consequently, such a destination contains no marker: one marker would force all item coordinates to zero, and two markers would exceed weight \(T\). Its item coordinates therefore satisfy
\(\displaystyle \sum_i a_iD_{g_i}=T.\)
They constitute a solution to unbounded subset sum. This argument applies to arbitrary real reassignment masses.
Conversely, suppose \(d\in\mathbb Z_{\geq0}^{n}\) satisfies \(\sum_i a_id_i=T\). Put \(r=\sum_i d_i\). Positivity of the weights implies \(1\leq r\leq T\) and \(d_i\leq T\). Define destinations
\(\displaystyle D^A=(d_1,\ldots,d_n,0,k-r),\qquad D^R=(T-d_1,\ldots,T-d_n,1,r).\)
Their coordinates are nonnegative, and both bundles have cardinality \(k\). Moreover,
\(\displaystyle D^A+D^R=B^A+B^R,\)
so assigning mass \(\frac12\) of each type to its corresponding destination preserves every supply.
Type \(A\)'s destination utility is \((k+1)T+r\), strictly exceeding its initial utility. Type \(R\)'s destination utility is
\(\displaystyle \sum_i a_i(T-d_i)+T=T\sum_i a_i,\)
equal to its initial utility. This is an improving reassignment.
Therefore the existence of improvement is \(\mathrm{NP}\)-hard under many-one reductions. Equivalently, deciding that no improvement exists is \(\mathrm{coNP}\)-hard. An unbounded subset-sum algorithm can also make one query to the no-improvement problem and negate the answer, establishing the requested \(\mathrm{NP}\)-hardness under Turing reductions.
5. Polynomial-size certificates and running times. Index the listed source entries by \(j\in\{1,\ldots,s\}\), recording their types \(t_j\), bundles \(B^j\), and masses \(y_j\). For each permitted destination \(D\), introduce \(x_{j,D}\), and define
\(\displaystyle e_{j,D}=\begin{cases}1,&v_{t_j}(D)>v_{t_j}(B^j),\\0,&v_{t_j}(D)=v_{t_j}(B^j).\end{cases}\)
Improvement exists precisely when the following finite linear program has positive optimum:
\(\displaystyle \max \sum_{j,D}e_{j,D}x_{j,D},\)
subject to
\(\displaystyle \sum_Dx_{j,D}=y_j\quad\text{for every }j,\qquad \sum_{j,D}x_{j,D}D_g=\rho_g\quad\text{for every }g,\qquad x_{j,D}\geq0.\)
Only permitted destinations occur. Omitted source entries require no variables, because their zero source masses force every outgoing mass to be zero.
The initial allocation makes this polytope nonempty. It is bounded, since its variables are nonnegative and sum to one. Hence its linear objective attains its maximum at a vertex.
A vertex has at most \(s+m\) positive variables. Indeed, if the corresponding constraint columns were linearly dependent, a nonzero dependence would allow sufficiently small perturbations in both directions while preserving nonnegativity and all equalities, contradicting extremality.
These positive variables also have polynomial binary length. To verify this explicitly, let their number be \(q\leq s+m\), and select \(q\) independent constraint rows. The resulting square matrix has integer entries of absolute value at most \(k\). The selected right-hand side has a common denominator of binary length at most \(L\). Cramer's rule and Hadamard's determinant bound therefore give each mass binary length
\(\displaystyle O\!\left(L+q\bigl(\log(k+1)+\log(q+1)\bigr)\right).\)
Each destination needs \(O(m\log(k+1))\) bits. Thus a positive optimum supplies a polynomial-size certificate listing at most \(s+m\) destinations, their source indices, and rational masses. Exact checking of utilities, supplies, source masses, and strict improvement takes \((m+\tau+s+L)^{O(1)}\) bit operations.
The improvement problem is consequently in \(\mathrm{NP}\), and the no-improvement problem is in \(\mathrm{coNP}\). Together with the reduction, this proves completeness.
For a deterministic upper bound, let
\(\displaystyle N=\lvert\mathcal B_k\rvert=\binom{k+m-1}{m-1}.\)
Enumerating destinations and solving the explicit rational LP takes
\(\displaystyle (m+\tau+s+L+sN)^{O(1)}\)
bit operations. Since \(N\leq(k+1)^{m-1}\) and \(k<2^L\), a bound stated solely in the requested parameters is
\(\displaystyle 2^{O(mL)}(m+\tau+s+L)^{O(1)}.\)
For every fixed \(k\), the inequality \(N\leq m^k\) instead gives running time \((m+\tau+s+L+sm^k)^{O(1)}\), which is polynomial.
6. Why the fractional-allocation test does not settle this problem. The cited paper permits fractional goods within each recipient's bundle and tests the resulting additive utility. Here, every positive reassigned mass must receive an integer bundle satisfying its source utility threshold. These feasible sets can differ. [Kawase and Mahara, Section 3, Theorem 1](https://arxiv.org/html/2603.05956v1).
For an explicit example, take the construction above with \(n=1\), \(a_1=2\), and \(T=1\). Then \(k=2\), the valuations are
\(\displaystyle v_A=(7,3,0),\qquad v_R=(2,1,0),\)
and the initial bundles are \(B^A=(0,1,1)\) and \(B^R=(1,0,1)\), each with mass \(\frac12\). No improving mass reassignment exists, because \(2d=1\) has no nonnegative integer solution.
Nevertheless, the fractional destinations
\(\displaystyle \widetilde D^A=\left(\frac12,0,\frac32\right),\qquad \widetilde D^R=\left(\frac12,1,\frac12\right)\)
each have cardinality two and preserve aggregate supplies. Type \(A\)'s utility rises from \(3\) to \(\frac72\), while type \(R\)'s remains \(2\). Thus replacing the destination-bundle constraints by a fractional-goods LP would give the wrong answer even on this small instance.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated problem. The reduction establishes hardness for the exact mass-reassignment model, including arbitrary real reassignment masses and unrestricted integer destination bundles. The certificate argument establishes membership in $\mathrm{coNP}$ for the no-improvement problem. I found no major or minor mathematical issues requiring repair.
The reduction from positive-integer SUBSET SUM to unbounded subset sum is correct.
$$cH+\sum_i(x_i+y_i)M^{i-1}=rH+S.$$
Membership in $\mathrm{NP}$ is also justified: positive weights imply $d_i\leq T$, so a solution has polynomial binary length. The invoked source problem is the standard positive-integer SUBSET SUM problem.
The constructed instance satisfies every input requirement.
The initial bundle sizes are
$$|B^A|=1+(k-1)=k,\qquad |B^R|=nT+1=k.$$
The coordinatewise average of the initial bundles is exactly the stated supply vector. Its total supply is
$$\frac{nT}{2}+\frac12+\frac{k}{2}=k,$$
using $k=nT+1$.
Both types have positive rational mass, all valuations are nonnegative integers, and the two listed allocation entries satisfy the type-mass and supply equalities.
The binary lengths of $k$, the coordinates, and the valuation coefficients are polynomial in the arithmetic input length. The construction consequently establishes the claimed restriction $\tau=s=2$ without implicitly expanding repeated copies.
This is the central part of the reduction, and it is valid.
For type $A$, the decomposition
$$v_A(D)=(k+1)p(D)+c(D)$$
and the bound $c(D)\leq k$ ensure that an integer auxiliary weight below $T$ cannot meet the initial utility threshold. The displayed calculation correctly gives a utility shortfall of at least one.
For type $R$, nonworsening directly requires auxiliary weight at least its initial auxiliary weight because its valuation equals $p$.
Thus every positive reassignment mass has nonnegative auxiliary-weight change. The conservation identity
$$\sum_{t,B,D}z_{t,B,D}\bigl(p(D)-p(B)\bigr)=0$$
follows from destination supply conservation and the source-mass equalities. There are finitely many bundles, even though their number can be exponentially large. Hence this is a finite sum of nonnegative terms, and every term with positive mass must have zero auxiliary-weight change.
The consequences are correctly stated:
Such a destination cannot contain a marker. A marker already contributes all of weight $T$, while every item has positive weight. Its item coordinates therefore satisfy the original unbounded subset-sum equation.
This reasoning does not require rational reassignment masses. It excludes improvement for arbitrary real masses when the arithmetic instance has no solution.
The proposed destinations are valid.
From positivity of the arithmetic weights,
$$1\leq r=\sum_i d_i\leq T,\qquad d_i\leq T.$$
These inequalities ensure that every destination coordinate is nonnegative, including the filler coordinate $k-r$ and the residual coordinates $T-d_i$.
Their cardinalities are
$$|D^A|=r+(k-r)=k,$$
and
$$|D^R|=nT-r+1+r=k.$$
The identity $D^A+D^R=B^A+B^R$ holds coordinatewise, so the two destination assignments of mass $\frac12$ preserve all supplies.
The utility calculations are correct: type $A$ gains $r>0$, while type $R$ retains its initial utility. The construction therefore gives an improving reassignment.
The reduction orientation is also correct. Arithmetic yes-instances correspond to improvement yes-instances, establishing $\mathrm{NP}$-hardness of improvement and $\mathrm{coNP}$-hardness of no improvement. Negating one answer from a no-improvement oracle yields the claimed polynomial-time Turing reduction.
The finite LP exactly represents the task. Its variables preserve each listed source separately, so it does not weaken the source-specific utility thresholds. Omitted sources have zero outgoing mass and can correctly be discarded.
The objective counts strictly improving mass. Its positivity is therefore equivalent to the task’s strict-improvement condition.
The initial allocation supplies feasibility. Nonnegative variables with total mass one supply boundedness. The standard finite-dimensional LP fact that a linear objective on a nonempty bounded polytope has a maximizing vertex applies with all hypotheses satisfied.
The support bound is correct. More than $s+m$ positive columns would be linearly dependent. A sufficiently small perturbation in either direction along that dependence preserves the equalities and nonnegativity, contradicting extremality.
The rational bit-length bound also checks out:
$$O\!\left(L+q\bigl(\log(k+1)+\log(q+1)\bigr)\right)$$
bound.
Thus a positive optimum has a polynomial-size rational certificate, despite the original permission to use real masses. Exact certificate checking is polynomial in the requested parameters. This establishes improvement in $\mathrm{NP}$ and no improvement in $\mathrm{coNP}$.
The deterministic upper bounds are consistent with the explicit LP:
No polynomial-time algorithm for unrestricted binary-encoded instances is claimed.
The cited paper defines balanced fractional allocations through fractional shares of individually distinct goods and tests additive utility at the resulting fractional allocation. Its Theorem 1 gives the relevant polynomial-time test. The prover correctly treats this as a different model, rather than applying that theorem to the present task. See the [paper’s model and Theorem 1](https://arxiv.org/html/2603.05956v1).
The numerical example is correct:
The example therefore supports the stated distinction.
The argument establishes $\mathrm{coNP}$-completeness under polynomial-time many-one reductions and the requested $\mathrm{NP}$-hardness under polynomial-time Turing reductions. No additional clarification or mathematical repair is needed.
⟨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.