d4-conf-ecai-2024-0358 (d4-conf-ecai-2024-0358)

Given \(p\) types with rational masses \(\mu_t>0\) summing to \(1\), utility vectors \(u_t\in\mathbb{Q}_{\ge 0}^{7}\), and rational per-capita supplies \(b_j\ge 0\), decide whether there is a finite-support assignment \(x_{t,z}\ge 0\) to integral bundles \(z\in\mathbb{Z}_{\ge 0}^{7}\) such that \(\sum_z x_{t,z}=\mu_t\), \(\sum_{t,z}z_jx_{t,z}\le b_j\) for each item type \(j\), and Nash welfare \(\exp(\sum_{t,z}x_{t,z}\log(u_t\cdot z))\) is at least a given threshold \(R>0\), with welfare zero if positive mass receives zero utility?

A society is given by its support: the list of \(\tau\ge1\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=7\) item types. Input utilities are additive vectors \(u_t\in\mathbb{Q}_{\ge0}^{m}\), supplies are per-capita quantities \(b_j\in\mathbb{Q}_{\ge0}\), and the threshold is \(R\in\mathbb{Q}_{>0}\), all encoded in binary. Let \(L\) be the total input bit length.
An assignment consists of real masses \(x_{t,z}\ge0\), only finitely many positive, indexed by types and integral bundles \(z\in\mathbb{Z}_{\ge0}^{m}\), satisfying \(\sum_zx_{t,z}=\mu_t\) and \(\sum_{t,z}z_jx_{t,z}\le b_j\) for every item type. Types may split their mass among bundles; unused supply is allowed.
Its Nash welfare is \(W(x)=\exp\bigl(\sum_{t,z:x_{t,z}>0}x_{t,z}\log(u_t\cdot z)\bigr)\), with \(W(x)=0\) if any positive mass receives zero utility. The decision problem asks whether some such assignment has \(W(x)\ge R\), with exact threshold comparison.

Is this decision problem solvable in polynomial time in \(m,\tau,L\), with \(m=7\) fixed, or is it NP-hard?

For finite agents and indivisible goods with binary-encoded multiplicities and nonnegative additive rational utilities, Nash-welfare threshold decision is NP-hard even with seven item types. [Source](https://journals.sagepub.com/doi/pdf/10.3233/FAIA240881)
No result settling exactly the mass-assignment decision problem above was located in the literature search.

Partial result: exact equivalence to product-of-powers comparison

I do not establish either polynomial-time solvability or $\mathrm{NP}$-hardness. I prove the following stronger characterization:

$$ \mathrm{MassNSW}_7\equiv_{\mathrm m}^{p}\mathrm{PoE}_{\ge}, $$

where $\mathrm{PoE}_{\ge}$ asks whether
$$ \prod_{i=1}^{n}a_i^{p_i}\ge \prod_{j=1}^{k}c_j^{q_j} $$
for positive integers $a_i,p_i,c_j,q_j$ encoded in binary.

The new direction is $\mathrm{MassNSW}_7\le_{\mathrm m}^{p}\mathrm{PoE}_{\ge}$. In fact, an exact welfare-maximizing assignment can be found in polynomial time; comparing its welfare with the input threshold is the remaining arithmetic problem.

All polynomial-time statements below concern the binary Turing model with $m=7$ fixed.

1. Positive welfare and a finite bundle domain

First, positive-welfare feasibility is polynomial-time decidable. Consider the rational linear feasibility problem
$$ y_{t,j}\ge0,\qquad y_{t,j}=0\ \text{if }u_{t,j}=0,\qquad \sum_jy_{t,j}=\mu_t,\qquad \sum_ty_{t,j}\le b_j. $$

If it is feasible, assign mass $y_{t,j}$ of type $t$ the unit bundle $e_j$. Every positively assigned bundle then has positive utility.

Conversely, in any positive-welfare assignment, every positively assigned bundle contains an item positively valued by its type. Select one such item from each bundle and discard the other items. The resulting unit-bundle assignment preserves type masses and weakly decreases resource use, so it gives a feasible solution of the displayed system.

Thus positive-welfare feasibility reduces to a rational linear program with at most $7\tau$ variables. If it fails, the threshold instance is negative because $R>0$.

Assume henceforth that positive welfare is feasible. Define
$$ M_t=\max_j u_{t,j}, \qquad C_t=\frac{\sum_ju_{t,j}b_j}{\mu_t}+M_t. $$

In particular, $M_t>0$ for every supported type.

Lemma 1. Every finite positive-welfare assignment is dominated in welfare by one whose positively assigned bundles of type $t$ satisfy
$$ 0<u_t\cdot z\le C_t, \qquad z_j=0\ \text{whenever }u_{t,j}=0. $$

Proof. Remove all zero-valued items first. Fix a type $t$, and let $V_t$ be its largest currently assigned utility. Let
$$ r_{t,j}=\sum_z z_jx_{t,z} $$
be its current resource totals.

There are finitely many integral bundles with utility in $(0,V_t]$ and zero coordinates on zero-valued items: every remaining coordinate satisfies $z_j\le V_t/u_{t,j}$. Over this finite set, maximize
$$ \sum_zx_{t,z}\log(u_t\cdot z) $$
while preserving mass $\mu_t$ and resource totals $r_{t,j}$. The original distribution is feasible, and the feasible set is compact, so a maximizer exists.

Suppose two positively assigned bundles have utilities $A>B$ with $A-B>M_t$. Choose a positively valued item present in the higher bundle, with value $v$. Then
$$ 0<v\le M_t<A-B. $$
Transfer one such item from the higher bundle to the lower bundle, doing this for an equal sufficiently small mass from each bundle. The resulting utilities satisfy
$$ A-v>B>0,\qquad B+v<A\le V_t. $$
Mass and resource totals are preserved. Moreover,
$$ (A-v)(B+v)-AB=v(A-B-v)>0. $$
The logarithmic objective strictly increases, contradicting optimality.

The supported utilities therefore differ by at most $M_t$. Their maximum is at most their conditional mean plus $M_t$, hence at most
$$ \frac{\sum_ju_{t,j}r_{t,j}}{\mu_t}+M_t \le \frac{\sum_ju_{t,j}b_j}{\mu_t}+M_t=C_t. $$
Performing this replacement independently for each type proves the lemma. $\square$

Every positive input rational lies between $2^{-L}$ and $2^L$. Consequently,
$$ C_t\le7\cdot2^{3L}+2^L\le8\cdot2^{3L}. $$
Every retained coordinate satisfies
$$ z_j\le\frac{C_t}{u_{t,j}}\le8\cdot2^{4L}. $$
Set
$$ K=8\cdot2^{4L}. $$

Define the finite sets
$$ \mathcal S_t= \left\{ z\in\mathbb Z_{\ge0}^{7}: 0<u_t\cdot z\le C_t,\ z_j=0\text{ if }u_{t,j}=0 \right\}. $$
Lemma 1 shows that optimizing over these sets suffices.

Add nonnegative supply slacks. The bounded allocation problem becomes
$$ Ax=d,\qquad x\ge0, $$
with $\tau+7$ rows. Its columns have two forms:

• A type–bundle column is $(e_t,z)$, with objective coefficient $\log(u_t\cdot z)$.
• A supply-slack column is $(0,e_j)$, with objective coefficient $0$.

Here $d$ consists of the masses and supplies. All entries of $A$ are integers bounded by $K$. The feasible set is compact: assignment variables are bounded by their type masses, and slacks are bounded by supplies.

It follows that a global welfare maximum exists. The number of columns may nevertheless be exponential, so an additional argument is needed to find it efficiently.

2. Every circuit involves at most sixteen variables

For a matrix $A$, a circuit is a nonzero vector in $\ker A$ whose support is inclusion-minimal among supports of nonzero kernel vectors.

The following property is the key consequence of having only seven resource constraints.

Lemma 2. Every circuit of the allocation matrix has support size at most
$$ 2m+2=16. $$
Its direction has a nonzero integer representative $g$ satisfying
$$ |g_i|\le H, \qquad H=(m+1)m!(2K)^m=8\cdot7!(2K)^7. $$

Proof. Consider a circuit supported on $k$ columns, touching $r$ type rows.

Each touched type must contribute at least two bundle columns: otherwise its type equation would force the coefficient of its sole column to be zero. Thus
$$ k\ge2r. $$

Choose one reference bundle column for each touched type. Subtract that reference column from each other bundle column of the same type. Leave slack columns unchanged. These invertible column operations put the restricted matrix into block form
$$ \begin{pmatrix} I_r&0\\ Z&D \end{pmatrix}, $$
where $D$ has $m$ rows and $q=k-r$ columns. Its entries have absolute value at most $2K$.

A circuit has restricted rank $k-1$. Therefore
$$ \operatorname{rank}D=k-1-r=q-1, $$
so $q\le m+1$. Also, $k\ge2r$ implies $r\le q$. Hence
$$ k=r+q\le2q\le2m+2. $$

Select $q-1$ independent rows of $D$. Their signed maximal minors give a nonzero integer kernel vector. Each coordinate has absolute value at most
$$ (q-1)!(2K)^{q-1}\le m!(2K)^m. $$
For $q=1$, the same statement uses the empty determinant, equal to one.

Recover each reference-column coefficient as the negative sum of the other bundle coefficients of that type. There are at most $q$ terms, so its absolute value is at most
$$ (m+1)m!(2K)^m=H. $$
The resulting vector is a nonzero integer representative of the original circuit. $\square$

We will also use the following elementary decomposition.

Lemma 3. Every nonzero $d'\in\ker A$ is a positive linear combination of circuit vectors conformal to $d'$. Here conformal means that each coordinate has the same sign as the corresponding coordinate of $d'$, or is zero.

Proof. Among nonzero kernel vectors conformal to $d'$, choose one, say $h$, with minimal support.

If the kernel restricted to that support had dimension at least two, choose a kernel vector $v$ on the same support independent of $h$. For sufficiently small perturbations, both $h+\varepsilon v$ and $h-\varepsilon v$ retain the prescribed signs. Move in a direction until a coordinate first becomes zero. The resulting vector is still nonzero, since $v$ is independent of $h$, and has smaller conformal support. This is a contradiction.

Thus $h$ is a circuit direction. Choose its bounded integer representative $g$ with the conformal orientation. Set
$$ \lambda=\min_{i:g_i\ne0}\frac{|d'_i|}{|g_i|}>0. $$
Then $d'-\lambda g$ remains conformal to $d'$ and has smaller support. Repeat. Each step removes at least one coordinate, so the procedure terminates and gives the required decomposition. $\square$

3. A uniform gap for nonzero circuit improvements

Let $c$ denote the true logarithmic objective coefficients, including zero coefficients for supply slacks.

For a circuit representative $g$ from Lemma 2,
$$ c\cdot g=\sum_i g_i\log v_i, $$
where there are at most sixteen positive rational utilities $v_i$.

Each utility has numerator and denominator of $O(L)$ bits. Explicitly, a common denominator for its seven utility coefficients is at most $2^{7L}$. Since $v_i\le C_t\le2^{3L+3}$, its corresponding numerator is at most $2^{10L+3}$. Thus both numerator and denominator are at most
$$ 2^{16(L+1)}. $$
Also,
$$ \log H\le72(L+1). $$

Writing each rational utility as a numerator divided by a denominator expresses $c\cdot g$ as a linear form in at most thirty-two logarithms of positive integers, with integer coefficients bounded by $H$.

We use the following unconditional form of the Baker–Wüstholz bound: for each fixed $n$, there is an effectively computable constant $C_n$ such that a nonzero linear form
$$ \Lambda=\sum_{i=1}^{n}k_i\log a_i $$
with integers $a_i\ge2$ and nonzero integers $k_i$ satisfies
$$ |\Lambda| \ge \exp\left( -C_n\prod_i\max\{1,\log a_i\}\, \log\max\{3,|k_1|,\ldots,|k_n|\} \right). $$
The constants can be bounded using the explicit formula in [Etessami–Stewart–Yannakakis, Theorem 3.1](https://arxiv.org/html/1304.5429).

Choose a fixed integer $C_*$ bounding these constants for $1\le n\le32$, and put
$$ Q(L)=C_*[16(L+1)]^{32}\,72(L+1), \qquad \gamma=2^{-2Q(L)}. $$
Terms with base one are omitted. Applying the theorem to every remaining nonzero circuit form gives
$$ c\cdot g\ne0 \quad\Longrightarrow\quad |c\cdot g|\ge e^{-Q(L)}\ge\gamma. $$
The last inequality follows from $\log2\ge1/2$.

Crucially, $Q(L)$ is a fixed polynomial. The bound is uniform over all bundles and all circuits, even though there may be exponentially many of them.

Set
$$ \delta=\frac{\gamma}{64H}. $$
This positive rational has polynomial encoding length.

Lemma 4. Suppose rational objective coefficients $\widehat c$ satisfy
$$ |\widehat c_i-c_i|\le\delta $$
for bundle columns and agree exactly with $c_i=0$ on slack columns. Then every maximizer of $\widehat c\cdot x$ over the allocation polytope also maximizes $c\cdot x$.

Proof. For every bounded circuit representative,
$$ |(\widehat c-c)\cdot g| \le16H\delta=\frac{\gamma}{4}. $$
Consequently,
$$ c\cdot g>0\quad\Longrightarrow\quad\widehat c\cdot g>0. $$

Suppose a surrogate maximizer $x$ is not a true maximizer. There is a feasible $y$ with
$$ c\cdot(y-x)>0. $$
By Lemma 3, $y-x$ is a positive combination of conformal circuit representatives. At least one, say $g$, satisfies $c\cdot g>0$, and therefore $\widehat c\cdot g>0$.

A sufficiently small positive step from $x$ in direction $g$ is feasible. Indeed, $Ag=0$, and whenever $g_i<0$, conformity gives $y_i-x_i<0$, which implies $x_i>0$. Thus all negative coordinates permit a sufficiently small step while preserving nonnegativity.

This step strictly improves the surrogate objective, contradicting the choice of $x$. $\square$

The lemma does not require preserving zero circuit improvements. It requires only preserving the signs of nonzero improvements.

4. Polynomially represented rational surrogate costs

It remains to construct coefficients $\widehat c$ that satisfy Lemma 4 and admit polynomial-time separation.

Every candidate utility lies between $2^{-L}$ and $2^{3L+3}$. Cover this range by the intervals
$$ I_s=[2^{s-1},2^s], \qquad -L\le s\le3L+3. $$
Write $S=3L+3$.

Compute a rational $\ell$ satisfying
$$ |\ell-\log2|\le\frac{\delta}{2(S+1)}. $$
This can be done in polynomial time by truncating
$$ \log2 = 2\sum_{r=0}^{\infty}\frac{1}{(2r+1)3^{2r+1}}. $$
The tail after $N$ terms is at most $3^{-2N}$, so polynomially many terms suffice.

Choose an integer degree $d_0$ with
$$ 2^{-d_0}\le\frac{\delta}{2}. $$
Then $d_0$ is polynomial in $L$.

On $I_s$, define
$$ f_s(v)=s\ell-\sum_{r=1}^{d_0}\frac{(1-v/2^s)^r}{r}. $$
If $v\in I_s$, then $\eta=1-v/2^s$ belongs to $[0,1/2]$, and
$$ \log v=s\log2-\sum_{r=1}^{\infty}\frac{\eta^r}{r}. $$
The omitted tail is at most $2^{-d_0}$. Hence
$$ |f_s(v)-\log v| \le |s|\,|\ell-\log2|+2^{-d_0} \le\delta. $$

These polynomials are concave on their respective intervals, because
$$ f_s''(v) = -\frac{1}{2^{2s}} \sum_{r=2}^{d_0}(r-1)(1-v/2^s)^{r-2} \le0. $$
Therefore $z\mapsto f_s(u_t\cdot z)$ is concave on the slab
$$ 2^{s-1}\le u_t\cdot z\le2^s. $$

For each $t,s$, introduce columns indexed by the integral bundles in $\mathcal S_t$ whose utility lies in $I_s$, and give them surrogate cost
$$ \widehat c_{t,s,z}=f_s(u_t\cdot z). $$
A bundle at an interval boundary may occur twice. These are separate bookkeeping columns with identical resource consumption. Their true costs are both $\log(u_t\cdot z)$, so duplicating them does not change the true allocation problem.

Lemma 2 continues to apply to this duplicated matrix, and every surrogate cost is within $\delta$ of its true cost. Thus Lemma 4 applies.

The expanded polynomials have polynomial representation length. Their degree is polynomial, the number of variables is seven, and the number of monomials is at most
$$ \binom{d_0+7}{7}. $$
Their rational coefficient lengths are polynomial as well: expansion uses only polynomially many rational operations on input coefficients, powers of two, $\ell$, and the integers through $d_0$.

5. Solving the surrogate linear program

The surrogate primal linear program has exponentially many columns. Its dual has only $\tau+7$ variables:
$$ \min_{\alpha,p} \left( \sum_t\mu_t\alpha_t+\sum_jb_jp_j \right), $$
subject to
$$ p_j\ge0, \qquad \alpha_t+p\cdot z\ge f_s(u_t\cdot z) $$
for every indexed type–slab–bundle column. The variables $\alpha_t$ are unrestricted.

We now provide an exact polynomial-time separation oracle.

Given rational $(\alpha,p)$, a negative coordinate of $p$ immediately supplies a violated constraint. Otherwise, for each $t,s$, seek an integral $z$ satisfying the bundle and slab constraints and
$$ F_{t,s}(z):= f_s(u_t\cdot z)-\alpha_t-p\cdot z>0. $$

Clear the rational coefficients of $F_{t,s}$ using a positive common denominator $D_{t,s}$, and write
$$ G_{t,s}=D_{t,s}F_{t,s}\in\mathbb Z[z_1,\ldots,z_7]. $$
At integral $z$, a strict violation is equivalent to
$$ G_{t,s}(z)\ge1. $$

The witness set is therefore defined by
$$ 0\le z_j\le K,\qquad z_j=0\text{ if }u_{t,j}=0, $$
$$ u_t\cdot z\le C_t,\qquad 2^{s-1}\le u_t\cdot z\le2^s,\qquad G_{t,s}(z)\ge1. $$

This real set is bounded and convex. Its linear constraints define a convex domain contained in the slab, and $F_{t,s}$ is concave there. Its superlevel set is consequently convex. It is described by polynomial inequalities of polynomial degree and coefficient length.

We apply the following fixed-dimensional theorem: integer feasibility in a convex semialgebraic set described by polynomial inequalities is polynomial-time decidable when the dimension is fixed; a feasible integer point can also be returned. This is the quantifier-free feasibility case of [Khachiyan–Porkolab, Theorem 1.2](https://link.springer.com/content/pdf/10.1007/PL00009496.pdf). The theorem permits lower-dimensional sets. Here the dimension is seven, convexity has been verified, and every defining polynomial has polynomial representation length.

Thus each witness search is polynomial-time. There are only $\tau\,O(L)$ type–slab pairs. A witness supplies its violated dual inequality; absence of witnesses certifies dual feasibility.

We use the standard rational oracle linear-programming theorem with dual-certificate recovery: a rational linear program of polynomial dimension and bounded inequality encoding length can be solved exactly using a polynomial-time strong separation oracle, with an optimal dual certificate supported on polynomially many oracle inequalities. The bounded encoding requirement for this recovery is discussed in [Dadush–Végh–Zambelli, Section 7](https://arxiv.org/html/2606.11820).

Its hypotheses hold here:

• The dual dimension is $\tau+7$.
• Every defining inequality has polynomial encoding length, independent of the query.
• The oracle returns a defining inequality.
• The primal is feasible and compact, so the dual has a finite attained optimum.
• If a recession-cone oracle is needed, the same witness construction supplies it after replacing the surrogate costs by zero.

Applying the theorem to the displayed dual recovers an optimal surrogate primal solution on polynomially many bundle columns. The certificate multipliers are precisely bundle masses and supply slacks.

On those recovered columns, solve the explicit rational linear program and return an optimal vertex. Its positively used columns are linearly independent, so at most $\tau+7$ variables are positive. Cramer’s rule bounds their encoding lengths polynomially: an integer submatrix of order $r\le\tau+7$ has determinant bounded by
$$ r!K^r, $$
and the right-hand side is rational with polynomial encoding length.

By Lemma 4, this surrogate optimum is also an exact optimum for the true logarithmic objective. Merge any duplicated bundle columns to obtain an assignment in the original model.

We have proved:

Theorem 5. For $m=7$, a deterministic polynomial-time algorithm either determines that positive welfare is impossible or returns a global welfare-maximizing assignment with at most $\tau+7$ positive masses, all rational and of polynomial encoding length.

This theorem computes the maximizing assignment without performing arbitrary-factor product-of-powers comparison.

6. Reduction to one exact product comparison

Run the algorithm of Theorem 5.

If positive welfare is impossible, output the fixed rejecting $\mathrm{PoE}_{\ge}$ instance
$$ 1^1\ge2^1. $$

Otherwise, let the positive assignment masses be $w_\ell$, and write their utilities and the threshold as
$$ v_\ell=\frac{A_\ell}{B_\ell}>0, \qquad R=\frac{P}{Q}>0. $$
All these rationals have polynomial encoding length.

Take a positive common denominator $D$ of the masses, for example the product of their denominators, and put
$$ e_\ell=Dw_\ell. $$
Every $e_\ell$ is a positive integer. Since the returned assignment is optimal,
$$ \exists x:\ W(x)\ge R \quad\Longleftrightarrow\quad \prod_\ell v_\ell^{w_\ell}\ge R. $$
Raising both positive sides to $D$ gives the equivalent comparison
$$ \left(\prod_\ell A_\ell^{e_\ell}\right)Q^D \ge \left(\prod_\ell B_\ell^{e_\ell}\right)P^D. $$

The resulting bases, exponents, and number of factors all have polynomial encoding length. Zero masses were omitted, so no zero exponent is introduced.

This proves
$$ \mathrm{MassNSW}_7\le_{\mathrm m}^{p}\mathrm{PoE}_{\ge}. $$

7. Reverse reduction, already with one usable item

For completeness, the reverse reduction from the notes is proved here.

Given a $\mathrm{PoE}_{\ge}$ instance, set
$$ S=\sum_i p_i+\sum_jq_j, $$
and choose a power of two $D>S$.

Construct a society with seven item types, supply
$$ b=(1,0,0,0,0,0,0), $$
and threshold $R=1$. Introduce:

• For each left factor, mass $p_i/D$ with utility vector $(a_i,0,\ldots,0)$.
• For each right factor, mass $q_j/D$ with utility vector $(1/c_j,0,\ldots,0)$.
• A filler mass $(D-S)/D$ with utility vector $(1,0,\ldots,0)$.

All masses are positive dyadic rationals and sum to one. Merge identical utility vectors if necessary. This preserves the relevant mass-weighted logarithms. The construction has polynomial encoding length.

In any positive-welfare assignment, zero supplies force all bundle coordinates except the first to vanish. Positive utility forces the first coordinate to be at least one. Therefore
$$ 1=\sum_{t,z}x_{t,z} \le \sum_{t,z}z_1x_{t,z} \le1. $$
It follows that every positively assigned bundle has $z_1=1$.

Assigning $e_1$ to every type is feasible and has positive welfare. Thus the positive-welfare assignment is forced, and its welfare satisfies
$$ W^D= \frac{\prod_i a_i^{p_i}}{\prod_jc_j^{q_j}}. $$
Consequently,
$$ W\ge1 \quad\Longleftrightarrow\quad \prod_i a_i^{p_i}\ge\prod_jc_j^{q_j}. $$
This proves
$$ \mathrm{PoE}_{\ge}\le_{\mathrm m}^{p}\mathrm{MassNSW}_7. $$

8. What remains unresolved

Combining the two reductions gives the proved equivalence
$$ \boxed{\mathrm{MassNSW}_7\equiv_{\mathrm m}^{p}\mathrm{PoE}_{\ge}.} $$

Hence:

• $\mathrm{MassNSW}_7$ is polynomial-time solvable if and only if $\mathrm{PoE}_{\ge}$ is polynomial-time solvable.
• $\mathrm{MassNSW}_7$ is $\mathrm{NP}$-hard under polynomial-time many-one reductions if and only if $\mathrm{PoE}_{\ge}$ is.

The fixed-factor logarithmic separation bound was sufficient for finding an optimal assignment because circuits involve at most sixteen variables. It does not settle the final comparison: the number of factors there grows with $\tau$.

Thus the combinatorial optimization gap from the previous round is closed. Neither requested unconditional complexity classification is proved here; the remaining question is the classification of arbitrary-factor exact product-of-powers comparison.

⟨structured verdict parsed — rendered above⟩

The output gives a sound partial characterization: the mass-assignment decision problem is polynomial-time many-one equivalent to exact product-of-powers comparison. It does not establish either complexity classification requested in USER_TASK. I found no mathematical error or substantive gap in the characterization.

• Positive-welfare feasibility is correctly characterized.

A feasible solution of the displayed linear system assigns each positive mass a positively valued unit bundle. Conversely, every positive-utility integral bundle contains at least one positively valued item. Selecting one such item for each supported bundle preserves type masses and weakly decreases consumption.

The finite-support requirement makes this selection immediate. Types with identically zero utilities, and instances with insufficient usable supplies, are correctly rejected. Because $R>0$, rejecting all instances without positive-welfare feasibility is valid.

• Lemma 1 correctly bounds the bundle domain.

After zero-valued coordinates are removed, the domain with utility at most $V_t$ is finite. The optimization preserving a type’s mass and resource totals therefore occurs over a nonempty compact polytope.

The proposed transfer remains within that domain: both new utilities are positive and at most $V_t$. It preserves resource totals and changes the objective by
$$ \varepsilon\log\frac{(A-v)(B+v)}{AB}>0. $$
The strict inequality follows from the displayed identity and $0<v<A-B$.

Thus supported utilities differ by at most $M_t$. The maximum is consequently bounded by the conditional mean plus $M_t$, giving precisely $C_t$.

The numerical bounds
$$ C_t\le 8\cdot 2^{3L}, \qquad z_j\le 8\cdot 2^{4L} $$
are valid under the stated binary encoding. Every division by $u_{t,j}$ is restricted to positive utility coordinates.

The resulting finite allocation polytope is nonempty and compact. Lemma 1 shows that its optimum dominates every finite positive-welfare assignment in the original domain. Since positive welfare is feasible, zero-welfare assignments cannot improve that optimum. The claimed global maximum therefore exists.

• Lemma 2 correctly bounds circuit support and coefficients.

Every touched type contributes at least two supported bundle columns. The reference-column operations are invertible, and the resulting block matrix has rank
$$ r+\operatorname{rank}D. $$
Minimal dependence gives restricted rank $k-1$, so
$$ q=k-r\le m+1, \qquad r\le q, \qquad k\le 2m+2. $$

The signed maximal-minor construction produces a nonzero integer kernel vector because the selected rows have rank $q-1$. The remaining rows impose no additional independent equation. Recovering reference coefficients by summation gives the stated bound $H$.

Slack-only supports and duplicated columns do not invalidate the argument. The empty-determinant convention handles $q=1$ correctly.

• Lemma 3 and the surrogate-optimality argument are valid.

If the restricted kernel on a minimally supported conformal vector had dimension greater than one, an independent perturbation could reach the boundary of its sign orthant while remaining nonzero. This would contradict minimality. Hence the selected vector is a circuit.

Subtracting the stated multiple of its conformally oriented representative preserves conformity and removes at least one coordinate. Finite-dimensionality ensures termination.

In Lemma 4, the perturbation bound is correctly calculated:
$$ |(\widehat c-c)\cdot g|\le 16H\delta=\frac{\gamma}{4}. $$
Every strictly improving true circuit remains strictly improving for the surrogate. If a surrogate optimum were not a true optimum, conformal decomposition would supply such a circuit with a feasible sufficiently small positive step. This gives the asserted contradiction.

Preserving zero circuit improvements is unnecessary, including for circuits created by duplicated bundle columns.

• The logarithmic separation bound is correctly applied.

Each circuit objective involves at most sixteen rational utilities, hence at most thirty-two integer logarithms after numerator–denominator expansion. The utility numerator and denominator bounds are sufficient, and the claimed estimate
$$ \log H\le 72(L+1) $$
holds for the displayed $H$ and $K$.

The stated Baker–Wüstholz specialization matches [Etessami–Stewart–Yannakakis, Theorem 3.1](https://arxiv.org/html/1304.5429). Its hypotheses are satisfied after omitting bases equal to one. Repeated bases and logarithmic dependencies are permitted; the lower bound is used only when the resulting form is nonzero.

The choices of $Q(L)$, $\gamma$, and $\delta$ have polynomial encoding length. The conversion
$$ e^{-Q(L)}\ge 2^{-2Q(L)} $$
is correct.

• The polynomial surrogate construction and separation oracle are valid.

The intervals cover the full candidate-utility range. On each interval, the logarithmic series has argument in $[0,1/2]$, so the stated truncation bound holds. The approximation to $\log 2$ provides the remaining error budget, including for negative interval indices.

The second derivative is nonpositive throughout the slab. Consequently, the witness set defined by $G_{t,s}(z)\ge 1$ and the linear restrictions is convex. Clearing denominators preserves the sign, and at integral points strict violation is exactly equivalent to that integer inequality.

[Khachiyan–Porkolab, Theorem 1.2](https://link.springer.com/content/pdf/10.1007/PL00009496.pdf) supports the claimed feasibility procedure: in fixed dimension, its running time is polynomial in coefficient length, degree, and number of predicates. It also covers lower-dimensional convex sets. Thus polynomially growing degree does not break this application.

• Exact surrogate optimization and assignment recovery are justified.

The dual has polynomial dimension, and its defining inequalities have uniformly polynomial encoding length. The oracle returns actual defining inequalities. The primal is feasible and compact, giving a finite attained dual optimum. Replacing surrogate costs by zero supplies the asserted recession-cone oracle.

The standard rational oracle LP theorem with recovery of certificates using oracle inequalities applies under these conditions. The bounded-encoding qualification is essential and is satisfied here. The cited [Dadush–Végh–Zambelli discussion in Section 7](https://arxiv.org/html/2606.11820) supports this qualification through the classical rational oracle results. Its arithmetic-operation corollary alone would not establish binary Turing complexity, but the prover explicitly invokes the standard rational theorem.

Solving the recovered explicit LP and taking an optimal vertex gives at most $\tau+7$ positive variables. The determinant bound and rational right-hand side give polynomial encoding lengths. Lemma 4 then establishes true optimality, and merging duplicates preserves welfare and feasibility.

• Both reductions are correct.

For the forward reduction, the product of mass denominators has polynomial bit length. Raising the positive welfare comparison to that denominator preserves the inequality and yields exactly the displayed product comparison. All bases and exponents have polynomial encoding length.

For the reverse reduction, the masses are positive, sum to one, and have polynomial encoding length. Zero supplies eliminate the other six coordinates. Positive welfare requires $z_1\ge 1$ for every positive mass, while total mass and supply both equal one. Therefore every positive mass must receive $z_1=1$. This proves the displayed formula for $W^D$ and the threshold equivalence. Merging identical types preserves it.

The genuine progress is the exact optimizing-assignment algorithm and the two reductions. The unresolved part is the original classification: equivalence to $\mathrm{PoE}_{\ge}$ supplies neither an unconditional polynomial-time decision algorithm nor an $\mathrm{NP}$-hardness proof. No repair to the established characterization is needed; completing the assignment requires an additional complexity result.

⟨structured verdict parsed — rendered above⟩