Answer: —
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo polynomial-time algorithm computes an al- location with optimal NSW for 2-value instances, for any coprime integers q > p ≥3, unless P=NP. We provide a reduction from Exact-p-Dimensional- Matching (Ex-p-DM): Given a graph G consisting of p dis- joint vertex sets V1, . . . , Vp, each of size n, and a set E ⊆ V1 × . . . × Vp of m edges, it is NP-hard to decide whether there exists a p-dimensional perfect matching in G or not. Note that for p = 3 the problem is Ex-3-DM and thus NP- hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given good kinds \(G\) with \(K_g\) indivisible copies, population scale \(N\), valuation types \(T\) with masses \(\mu_t\), and \(a_{tg}\in\{1,p/q\}\) for coprime \(q>p\ge3\), choose masses \(x_{t,b}\ge0\) over integer bundles \(b\) with \(0\le b_g\le K_g\), satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_gx_{t,b}\le K_g/N\), to maximize \(\exp\!\left(\sum_{t,b}x_{t,b}\log\!\left(\sum_ga_{tg}b_g\right)\right)\).
Fix coprime integers \(q>p\ge3\). An instance gives good kinds \(G\) with \(K_g\in\mathbb Z_{\ge0}\), \(N\in\mathbb Z_{>0}\), valuation types \(T\) with rational masses \(\mu_t\ge0\) satisfying \(\sum_t\mu_t=1\), and \(a_{tg}\in\{1,p/q\}\), all binary encoded.
Let \(\mathcal B=\{b\in\mathbb Z_{\ge0}^{G}:0\le b_g\le K_g\}\) and \(u_t(b)=\sum_{g\in G}a_{tg}b_g\). Choose \(x_{t,b}\ge0\) with \(\sum_{b\in\mathcal B}x_{t,b}=\mu_t\) and \(\sum_{t,b}b_gx_{t,b}\le K_g/N\) for every \(g\), to maximize \(\exp(\sum_{t,b}x_{t,b}\log u_t(b))\), with \(\log0=-\infty\).
Is computing an optimal allocation for this continuous two-value Nash-social-welfare problem polynomial-time solvable, or is it NP-hard?
For finite agents and indivisible goods with additive values in \(\{p,q\}\), maximizing Nash social welfare is NP-hard for every coprime \(q>p\ge3\).
No result for exactly the distribution-over-types formulation above was verified here.
The exact standard-Turing-model dichotomy is not resolved here. The finite-agent hardness theorem does not transfer directly because the continuous formulation is a fractional configuration LP.
The following substantial conclusions are proved:
Thus there is no verified \(\mathrm{NP}\)-hardness transfer. The remaining issue for an unconditional exact polynomial-time classification is arithmetic, rather than the configuration-pricing problem.
Let \(K_{\mathrm{tot}}=\sum_{g\in G}K_g\), and ignore types of mass \(0\).
A finite logarithmic objective is achievable if and only if \(K_{\mathrm{tot}}\ge N\).
Indeed, every nonzero bundle contains at least one good. Hence, for any allocation having no positive mass on the zero bundle,
\[ \sum_{t,b}\left(\sum_g b_g\right)x_{t,b}\ge\sum_{t,b}x_{t,b}=1. \]
On the other hand, feasibility gives
\[ \sum_{t,b}\left(\sum_g b_g\right)x_{t,b} \le \sum_g\frac{K_g}{N} =\frac{K_{\mathrm{tot}}}{N}. \]
Consequently \(K_{\mathrm{tot}}<N\) forces positive mass on the zero bundle, so every allocation has logarithmic objective \(-\infty\) and Nash welfare \(0\). In this case \(x_{t,0}=\mu_t\) is optimal.
Conversely, suppose \(K_{\mathrm{tot}}\ge N\). Choose rational numbers \(\lambda_g\) satisfying \(0\le\lambda_g\le K_g/N\) and \(\sum_g\lambda_g=1\). Setting \(x_{t,e_g}=\mu_t\lambda_g\), where \(e_g\) is the singleton bundle of kind \(g\), gives
\[ \sum_t x_{t,e_g}=\lambda_g\le\frac{K_g}{N}. \]
Every supported bundle has positive utility. Thus the finite case is exactly \(K_{\mathrm{tot}}\ge N\). Only this case is considered below.
Because the exponential function is strictly increasing, maximizing Nash welfare is equivalent to maximizing the logarithmic objective.
Put \(\mathcal B^+=\mathcal B\setminus\{0\}\) and \(c_{t,b}=\log u_t(b)\). The problem is the finite, though succinctly represented, linear program
\[ \max\left\{ \sum_{t\in T}\sum_{b\in\mathcal B^+}c_{t,b}x_{t,b}: \sum_bx_{t,b}=\mu_t,\ \sum_{t,b}b_gx_{t,b}\le\frac{K_g}{N},\ x\ge0 \right\}. \]
Its dual is
\[ \min\left\{ \sum_t\mu_t\alpha_t+\sum_g\frac{K_g}{N}y_g: \alpha_t+\sum_g y_gb_g\ge c_{t,b}\ \text{for all }t,b,\ y_g\ge0 \right\}, \]
where the variables \(\alpha_t\) are unrestricted.
Thus dual separation reduces, for every type \(t\), to computing
\[ M_t(y)=\max_{b\in\mathcal B^+} \left(\log u_t(b)-\sum_g y_gb_g\right). \]
Fix \(t\) and define
\[ H_t=\{g:a_{tg}=1\},\qquad L_t=\{g:a_{tg}=p/q\}. \]
For a bundle \(b\), put
\[ h=\sum_{g\in H_t}b_g,\qquad \ell=\sum_{g\in L_t}b_g. \]
Then
\[ u_t(b)=\frac{qh+p\ell}{q}. \]
For fixed \(h\), the minimum possible price paid for high-valued goods is
\[ C_H(h)=\min\left\{\sum_{g\in H_t}y_gb_g: \sum_{g\in H_t}b_g=h,\ 0\le b_g\le K_g\right\}. \]
Sorting the goods in \(H_t\) by nondecreasing \(y_g\) computes \(C_H\): one takes copies from the cheapest kind until its capacity is exhausted, then continues with the next kind. Consequently \(C_H\) is a convex piecewise-affine function with at most \(|H_t|\) pieces and integer breakpoints given by prefix sums of the capacities. The analogous function \(C_L(\ell)\) has at most \(|L_t|\) pieces.
Pricing therefore reduces to
\[ \max_{h,\ell\in\mathbb Z_{\ge0},\ (h,\ell)\ne(0,0)} \left[ \log\left(\frac{qh+p\ell}{q}\right)-C_H(h)-C_L(\ell) \right]. \]
Consider one rectangle \([A,B]\times[C,D]\) on which
\[ C_H(h)=ch+\gamma,\qquad C_L(\ell)=d\ell+\delta. \]
Ignoring the constant terms, the objective is
\[ f(h,\ell)=\log(qh+p\ell)-ch-d\ell. \]
Suppose first that \(c/q\le d/p\). If \(h+p\le B\) and \(\ell-q\ge C\), the move
\[ (h,\ell)\longmapsto(h+p,\ell-q) \]
preserves \(qh+p\ell\), while its price change is
\[ cp-dq=pq\left(\frac cq-\frac dp\right)\le0. \]
Therefore some optimum in the rectangle satisfies either \(h>B-p\) or \(\ell<C+q\). Since \(p,q\) are fixed, this is a union of at most \(p+q\) one-dimensional integer lines.
If \(c/q>d/p\), the reverse move shows that some optimum satisfies either \(h<A+p\) or \(\ell>D-q\). Again only \(p+q\) boundary lines need be considered.
On a line with fixed \(h=h_0\), the remaining function is
\[ \ell\longmapsto\log(qh_0+p\ell)-d\ell. \]
If \(d=0\), it is increasing. If \(d>0\), its continuous stationary point is
\[ \ell^*=\frac1d-\frac{qh_0}{p}. \]
Its integer maximum is therefore attained at an endpoint or at one of the two integers bracketing \(\ell^*\). The argument for a fixed-\(\ell\) line is identical.
There are at most \(O(|G|^2)\) affine rectangles, and each produces only \(O(p+q)\) candidates. Their associated bundles are recovered by the greedy sorted-prefix construction. Every count and bundle coordinate is manipulated in binary.
Hence, for fixed \(p,q\), an additive-\(\eta\) approximation of \(M_t(y)\) can be computed in time polynomial in the input length and \(\log(1/\eta)\), because logarithms of positive rationals admit certified approximations to that accuracy in polynomial time.
For every rational \(\varepsilon>0\), one can compute a rational feasible allocation \(x\), represented by at most \(|T|+|G|\) positive variables, such that
\[ \sum_{t,b}x_{t,b}\log u_t(b) \ge \mathrm{OPT}_{\log}-\varepsilon \]
in time polynomial in the input length and \(\log(1/\varepsilon)\).
Equivalently,
\[ \operatorname{NSW}(x)\ge e^{-\varepsilon}\operatorname{NSW}^*. \]
The dual has \(|T|+|G|\) variables and exponentially many constraints. The preceding pricing algorithm is a polynomial-time weak separation oracle for those constraints.
Apply the weak separation–weak optimization equivalence for bounded convex optimization; see [Grötschel, Lovász, and Schrijver](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf). Standard determinant bounds give a dual solution of magnitude at most \(2^{\operatorname{poly}(L)}\), where \(L\) is the binary input length, so the necessary bounding ball has polynomially encoded radius.
For completeness, the column-generation optimality certificate is especially simple. Suppose a restricted set of columns has dual solution \((\alpha,y)\) and satisfies
\[ M_t(y)\le\alpha_t+\delta \]
for every type. Then replacing every \(\alpha_t\) by \(\alpha_t+\delta\) gives a feasible dual solution for the full configuration LP. Since \(\sum_t\mu_t=1\), its objective exceeds the restricted dual objective by exactly \(\delta\). Therefore the restricted primal optimum is within \(\delta\) of the full optimum.
Certified logarithm approximations, approximate pricing, and the restricted primal–dual gap can each be assigned error at most \(\varepsilon/3\). This produces an \(\varepsilon\)-optimal feasible allocation.
Finally, a basic feasible solution of a restricted primal has at most \(|T|+|G|\) positive configuration variables. Its positive columns remain linearly independent in the full LP, so it is also a basic feasible solution of the full feasible polytope. This gives the claimed sparse representation.
Let \(x\) be an exact optimum with finite logarithmic objective. If \(x_{t,b}>0\) and \(x_{t,c}>0\), then
\[ |u_t(b)-u_t(c)|\le1. \]
Suppose without loss of generality that \(u_t(c)>u_t(b)+1\). Since \(u_t(c)>u_t(b)\), some good kind \(g\) satisfies \(c_g>b_g\). Hence both bundles
\[ b'=b+e_g,\qquad c'=c-e_g \]
belong to \(\mathcal B\). Put \(a=a_{tg}\), so \(0<a\le1\).
For sufficiently small \(\delta>0\), replace mass \(\delta\) on each of \(b,c\) by mass \(\delta\) on each of \(b',c'\). Type mass and every expected good consumption are unchanged.
The product of the two affected utilities changes by
\[ (u_t(b)+a)(u_t(c)-a)-u_t(b)u_t(c) =a\bigl(u_t(c)-u_t(b)-a\bigr)>0, \]
because \(u_t(c)-u_t(b)>1\ge a\). Hence the sum of their logarithms strictly increases, contradicting optimality.
Since \(qu_t(b)\) is an integer, the lemma implies that one type uses at most \(q+1\) distinct utility values in an exact optimum. This is a genuine consequence of continuous splitting that is absent from a direct discrete-agent reduction.
Consider the auxiliary problem of comparing the Nash welfare of two explicitly given sparse feasible allocations.
For two such allocations \(x,x'\), choose a common denominator \(D\) for their rational masses. Then
\[ D\bigl(\ell(x)-\ell(x')\bigr) =\sum_i z_i\log r_i =\log\left(\prod_i r_i^{z_i}\right), \]
where the \(z_i\) are binary-encoded integers and the \(r_i\) are positive rationals of polynomial encoding length. Thus allocation comparison reduces to product-of-exponentials inequality testing.
The converse reduction also holds.
Take a product-of-exponentials instance
\[ \prod_{i=1}^n a_i^{b_i} \mathrel{\mathop{\ge}^{?}} \prod_{j=1}^m c_j^{d_j}, \]
with positive binary-encoded integers. Let
\[ S=\sum_i b_i+\sum_jd_j. \]
Create one type of mass \(b_i/S\) for every left-hand term and one type of mass \(d_j/S\) for every right-hand term. Use one good kind, valued \(1\) by every type, let \(N=1\), and set
\[ K=\max\{1,a_1,\ldots,a_n,c_1,\ldots,c_m\}. \]
Define allocation \(X\) by giving bundle size \(a_i\) to the type corresponding to \(a_i^{b_i}\), and bundle size \(1\) to every right-hand type. Define \(X'\) symmetrically, giving size \(1\) to each left-hand type and size \(c_j\) to the type corresponding to \(c_j^{d_j}\).
Both allocations are feasible because their expected bundle sizes are convex combinations of integers in \([1,K]\), and hence do not exceed the per-capita supply \(K\). Moreover,
\[ \ell(X)-\ell(X') =\frac1S\left(\sum_i b_i\log a_i-\sum_jd_j\log c_j\right). \]
Therefore exact sparse-allocation comparison is polynomial-time equivalent to product-of-exponentials comparison.
For variable numbers of bases, unconditional polynomial-time product-of-exponentials inequality testing is a recognized open arithmetic problem. Equality is polynomial-time decidable, while inequality is known to be polynomial-time decidable for a fixed number of bases and conditionally under Lang–Waldschmidt-type conjectures; see [Etessami, Stewart, and Yannakakis](https://arxiv.org/abs/1304.5429).
This equivalence is not, by itself, a reduction from product-of-exponentials comparison to optimal-allocation computation. It therefore does not prove hardness of the target problem. It does show why merely saying “approximate the logarithms sufficiently accurately” does not establish unconditional exact polynomial time.
Let \(m_0=|T|+|G|\). Every basic feasible allocation has at most \(m_0\) positive variables. After clearing the rational right-hand sides, Cramer’s rule and Hadamard’s determinant bound show that every coordinate of every basic feasible allocation has polynomially many bits.
For two basic feasible allocations \(x,x'\), their objective difference can consequently be written as
\[ \ell(x)-\ell(x') =\frac1D\sum_{i=1}^r z_i\log r_i, \]
where \(r\le2m_0+1\), and \(D,z_i,r_i\) all have polynomial encoding length.
If \(m_0\) is a fixed constant, the Baker–Wüstholz or Matveev lower bounds imply that every nonzero such difference has magnitude at least \(2^{-\operatorname{poly}(L)}\). Running the approximation algorithm below half this bound and returning a basic feasible solution therefore returns an exact optimum.
The same conclusion holds for unrestricted \(m_0\) under the Lang–Waldschmidt-type lower bound
\[ \left|\sum_i z_i\log r_i\right| \ge 2^{-\operatorname{poly}(L)} \]
for every nonzero form arising above.
Thus exact optimization is:
The continuous formulation does not inherit the known finite-agent \(\mathrm{NP}\)-hardness proof. Its exponentially many configurations admit polynomial-time pricing, so all inverse-exponential-accuracy optimization is polynomial-time solvable.
What remains unresolved is exact recovery in the unrestricted standard Turing model. The natural recovery argument requires a polynomial lower bound on nonzero variable-dimensional linear forms in logarithms. No direct \(\mathrm{NP}\)-hardness reduction for the exact optimum has been established here, and no unconditional method avoiding this arithmetic comparison has been proved.
⟨structured verdict parsed — rendered above⟩
The prover does not resolve the requested exact complexity classification. It explicitly acknowledges that neither an unconditional polynomial-time algorithm nor an NP-hardness reduction has been established.
There is nevertheless genuine progress: the zero-utility characterization, configuration-LP formulation, approximate pricing construction, balancing lemma, and reduction for comparing two explicit sparse allocations are substantially correct. The claimed polynomial-time approximation theorem and the exact-recovery conclusions, however, rely on an incompletely justified application of weak optimization/separation machinery.
This argument is correct.
For kinds with \(K_g=0\), one necessarily has \(\lambda_g=0\), so the formal appearance of \(e_g\notin\mathcal B\) causes no positive allocation variable. This could be stated explicitly but is not a substantive gap.
The formulation and dual are correct.
Removing the zero configuration is legitimate after restricting to finite-objective allocations. The dual variables and signs match the primal equality and capacity constraints, and separation reduces to maximizing
\[ \log u_t(b)-\sum_g y_gb_g. \]
Because the primal is a finite feasible bounded LP, ordinary finite-dimensional LP duality applies despite the exponentially large explicit configuration set.
The structural pricing argument is correct for additive approximation.
However, the opening status claims a “polynomial-time bundle-pricing oracle,” while the proof establishes only an additive approximate pricing oracle. Selecting the exact best candidate requires exact sign comparisons involving logarithms and rational price terms; no such algorithm or separation bound is provided. This is a material overstatement.
This theorem is potentially correct, but the proof as written is not rigorous enough to verify it.
The cited weak separation–weak optimization equivalence has geometric and oracle hypotheses that are not stated. In particular, the prover does not specify:
The standard Grötschel–Lovász–Schrijver results require explicit control of these conditions; merely bounding the magnitude of one optimal dual solution is not the complete hypothesis of weak optimization from weak separation. See the cited [Grötschel–Lovász–Schrijver source](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).
The column-generation paragraph supplies only a conditional certificate: if a restricted dual satisfying the displayed inequalities has already been obtained, then the restricted primal value is close to the full value. It does not prove that the proposed weak-oracle algorithm constructs such a polynomial-size restricted column set, nor that the accumulated numerical errors give the asserted certificate.
Similarly, assigning three errors “at most \(\varepsilon/3\)” is not an error analysis. The required directions of approximation and the accumulated effects on feasibility and objective value must be stated.
The sparsity conclusion is correct once an appropriate restricted primal basic feasible solution has been produced. A restricted standard-form basis remains a valid basis after the omitted columns are restored as nonbasic zero variables. The prover’s explanation using only independence of positive columns is incomplete, but the conclusion itself is routine.
The balancing lemma is correct.
If \(c_g>b_g\), then \(b+e_g\) and \(c-e_g\) remain within their coordinate bounds. Taking \(\delta\) no larger than the two positive masses preserves nonnegativity. Type mass and every expected consumption coordinate remain unchanged.
The logarithmic improvement is correctly reduced to
\[ (u_t(b)+a)(u_t(c)-a)>u_t(b)u_t(c), \]
which follows from \(u_t(c)-u_t(b)>1\geq a\). The modified utilities remain positive under the assumed inequality.
Because every utility lies in \((1/q)\mathbb Z\), an interval of length at most \(1\) contains at most \(q+1\) possible utility values. That consequence is also correct.
The two reductions are correct.
For explicit sparse rational allocations, clearing mass denominators produces a signed integer linear form in logarithms of positive rationals. Rational bases and signed exponents can be converted into the usual product-of-integer-powers formulation with polynomial encoding growth.
Conversely, the constructed one-kind instance is valid:
The cited Etessami–Stewart–Yannakakis paper confirms polynomial-time equality testing, conditional polynomial-time inequality testing, and unconditional polynomial time for a fixed number of bases [in its abstract and complexity results](https://arxiv.org/html/1304.5429v3).
The prover correctly warns that this is not a reduction to optimal-allocation computation. Consequently, it supplies neither hardness nor a lower bound for the target optimization problem.
The assertion that variable-base inequality testing remains a currently recognized open problem is supported only by a 2014 reference. This does not invalidate the reduction, but a current complexity-status assertion should have a current source or be qualified as the status established by that reference.
The arithmetic outline is plausible but not fully verified as written.
Nevertheless, the prover does not state the Baker–Wüstholz or Matveev bound precisely or perform the necessary encoding calculation showing that the resulting lower bound is \(2^{-\operatorname{poly}(L)}\) after division by \(D\). Under the verifier’s standard, this is an unverified invocation of a cited theorem.
More importantly, exact recovery depends on the Section 4 algorithm returning an exactly feasible basic solution whose true logarithmic objective is within the requested tolerance. Since that algorithmic claim is not established rigorously, the unconditional fixed-dimensional and conditional variable-dimensional exact-optimization conclusions are not yet fully proved by this write-up.
The following parts stand independently:
The exact target classification remains unresolved. The claimed approximation and exact-recovery theorems require another round focused on the precise weak-oracle theorem, its geometric hypotheses, certified cuts, primal recovery, and the explicit logarithmic separation bound.
⟨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.