Answer: Exact maximization is \(\mathrm{NP\text{-}hard}\).
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a 1.33-approximation algorithm for Capacitated Two-Sided NSW under subadditive valuations. The algorithm runs in poly(𝑛,𝑚) time and makes poly(𝑛,𝑚) number of value queries.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite firm types \(\mathcal F\), worker types \(\mathcal W\), rational masses \(\phi_f,\psi_w\), capacities \(\c_f\), type-symmetric monotone normalized subadditive valuations \(V_f(b)\) for integral bundles \(b\in\mathbb Z_{\ge0}^{\mathcal W}\) with \(\lVert b\rVert_1\le c_f\), and worker values \(\omega_w(f)\), choose firm-mass variables \(z_{f,b}\) satisfying \(\sum_b z_{f,b}=\phi_f\) and \(\sum_{f,b}b_wz_{f,b}=\psi_w\) to maximize population Nash welfare \(\exp((\sum_{f,b}z_{f,b}\log V_f(b)+\sum_{f,b,w}b_wz_{f,b}\log\omega_w(f))/(\sum_f\phi_f+\sum_w\psi_w))\), or compute a specified-factor approximation.
Definitions. A continuous uncapacitated two-sided instance has finite type sets \(P,Q\), rational distributions \((\phi_p)_{p\in P}\), \((\psi_q)_{q\in Q}\), rational \(\rho>0\), and additive values \(v_{pq},w_{qp}\in\mathbb{Q}_{\ge0}\), with \(\sum_p\phi_p=\sum_q\psi_q=1\). For \(B\in\mathbb{Z}_{\ge0}^{Q}\), let \(v_p(B)=\sum_q v_{pq}B_q\).
Choose configuration masses \(\eta_p(B)\ge0\) and flows \(z_{pq}\ge0\) satisfying \(\sum_B\eta_p(B)=\phi_p\), \(\sum_B B_q\eta_p(B)=z_{pq}\), and \(\sum_p z_{pq}=\rho\psi_q\). Maximize \(L=\frac{1}{1+\rho}\left(\sum_{p,B}\eta_p(B)\log v_p(B)+\sum_{p,q}z_{pq}\log w_{qp}\right)\), with \(\log 0=-\infty\).
Target. Is maximizing \(L\) for this continuous uncapacitated two-sided NSW problem solvable in polynomial time, or is it NP-hard?
Nearest known results. The discrete uncapacitated two-sided NSW problem is APX-hard: unless \(P=NP\), it admits no polynomial-time \(1.0000759\)-approximation, even with additive firm values.
No result for the continuous distributional formulation above is asserted here.
Under the standard exact-optimization interpretation, maximizing \(L\) is \(\mathrm{NP\text{-}hard}\). More precisely, the induced decision problem
“given a rational threshold \(\tau\), is \(L^\star\geq\tau\)?”
is \(\mathrm{NP\text{-}hard}\), even with only two types on the \(P\)-side.
This is a direct hardness result for the continuous formulation; it does not follow merely from the discrete APX-hardness theorem.
We reduce from Unbounded Subset Sum:
Given positive integers \(a_1,\ldots,a_n,T\), decide whether there exists \(B\in\mathbb Z_{\geq0}^n\) such that
\(\sum_{j=1}^n a_jB_j=T\).
Its decision version is NP-complete; see [Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime](https://arxiv.org/abs/2407.05435).
We may remove every \(a_j>T\), so assume \(1\leq a_j\leq T\). We also assume \(T\geq2\), since smaller instances are trivial.
Set
\(\delta=\frac{1}{64T^3}\).
For every \(j\), we construct a rational number \(R_j>1\) satisfying
\(0\leq\log R_j-\frac{a_j}{T}\leq\delta\).
This construction has polynomial encoding length. Indeed, choose \(N\) so that \(3\cdot2^{-N}\leq\delta\), let
\(S_N(x)=\sum_{k=0}^N\frac{x^k}{k!}\),
and define
\(R_j=S_N\!\left(\frac{a_j}{T}\right)+\frac{3}{2^N}\).
For \(0\leq x\leq1\), Taylor’s remainder bound, \(e<3\), and \((N+1)!\geq2^N\) give
\(0\leq e^x-S_N(x)\leq\frac{3}{(N+1)!}\leq\frac{3}{2^N}\).
Consequently \(e^x\leq R_j\leq e^x+\delta\), and hence
\(0\leq\log R_j-x\leq\delta\).
Since \(N=O(\log T)\), all \(R_j\) are rationals of polynomial bit length.
For \(B\in\mathbb Z_{\geq0}^n\) with \(V(B)=\sum_j a_jB_j>0\), define
\(f(B)=\log V(B)-\sum_{j=1}^nB_j\log R_j\).
Writing \(\varepsilon_j=\log R_j-a_j/T\), we have
\(f(B)=h(V(B))-\sum_jB_j\varepsilon_j\),
where
\(h(x)=\log x-\frac{x}{T}\)
and \(0\leq\varepsilon_j\leq\delta\).
The function \(h\) is strictly increasing on \((0,T)\) and strictly decreasing on \((T,\infty)\). For every positive integer \(V\neq T\),
\(h(T)-h(V)\geq\frac{1}{4T^2}\).
It suffices to check \(V=T+1\) and \(V=T-1\). For \(x=1/T\),
\(h(T)-h(T+1)=x-\log(1+x)=\int_0^x\frac{t}{1+t}\,dt\geq\frac{x^2}{4}\),
and
\(h(T)-h(T-1)=-\log(1-x)-x=\int_0^x\frac{t}{1-t}\,dt\geq\frac{x^2}{2}\).
If \(V(B)=T\), then \(\sum_jB_j\leq T\), and therefore
\(f(B)\geq h(T)-T\delta=h(T)-\frac{1}{64T^2}\).
If \(V(B)\neq T\), then
\(f(B)\leq h(V(B))\leq h(T)-\frac{1}{4T^2}\).
Thus:
Let \(K=4T^2\). Every maximizer of \(f\) satisfies \(B_j<K\) for every \(j\).
Indeed, if \(V\geq K\), then
\(f(B)\leq h(V)\leq h(K)=\log(4T^2)-4T<-2\).
On the other hand, for any singleton bundle \(e_j\),
\(f(e_j)\geq\log a_j-\frac{a_j}{T}-\delta\geq-1-\delta\).
Hence no bundle with \(V\geq K\) is optimal. Since \(a_j\geq1\), \(B_j\leq V(B)<K\) for every maximizer.
Let
\(P=\{s,d\}\), \(\phi_s=\phi_d=\frac12\),
where \(s\) is the signal type and \(d\) is a dummy type. Let
\(Q=\{0,1,\ldots,n\}\),
where \(0\) is an anchor type.
Set
\(\rho=\frac{1+nK}{2}\),
\(\psi_0=\frac{1}{1+nK}\),
and, for \(j\geq1\),
\(\psi_j=\frac{K}{1+nK}\).
Thus the supplied masses are
\(\rho\psi_0=\frac12\)
and
\(\rho\psi_j=\frac K2\).
Define the firm-side values by
\(v_{s0}=0,\quad v_{sj}=a_j\),
\(v_{d0}=1,\quad v_{dj}=0\).
Define the worker-side values by
\(w_{0s}=w_{0d}=1\),
\(w_{js}=\frac{1}{R_j},\quad w_{jd}=1\)
for \(j\geq1\). All input numbers are nonnegative rationals of polynomial encoding length.
Consider any feasible solution of finite objective value.
Every dummy configuration of positive mass must contain at least one anchor, since the dummy’s utility equals its anchor count. The total dummy mass and total anchor supply are both \(1/2\). Therefore every dummy configuration in the support contains exactly one anchor, and no anchor is assigned to \(s\).
Normalize the signal configuration masses to a probability distribution
\(\mu(B)=2\eta_s(B)\).
For item \(j\), feasibility gives
\(\mathbb E_\mu[B_j]=2z_{sj}\leq K\).
The dummy firm contribution is zero because its utility is always \(1\). All worker contributions are zero except those from items assigned to \(s\). Therefore
\((1+\rho)L=\frac12\,\mathbb E_\mu\!\left[\log V(B)-\sum_jB_j\log R_j\right]\)
and hence
\((1+\rho)L=\frac12\,\mathbb E_\mu[f(B)]\leq\frac12\max_B f(B)\).
Conversely, let \(B^\star\) maximize \(f\). By Lemma 2, \(B_j^\star<K\). Give every signal agent bundle \(B^\star\), and give every dummy agent one anchor together with \(K-B_j^\star\) copies of item \(j\). The aggregate supply of item \(j\) is then
\(\frac12B_j^\star+\frac12(K-B_j^\star)=\frac K2\),
so this is feasible. It attains \(\frac12f(B^\star)\). Consequently,
\(L^\star=\frac{\max_B f(B)}{2(1+\rho)}\).
If the Unbounded Subset Sum instance is positive, then
\(L^\star\geq\frac{h(T)-1/(64T^2)}{2(1+\rho)}\).
If it is negative, then
\(L^\star\leq\frac{h(T)-1/(4T^2)}{2(1+\rho)}\).
Compute in polynomial time a rational \(r\) satisfying
\(\left|r-h(T)\right|\leq\frac{1}{64T^2}\).
Such an approximation exists with polynomially many bits by the standard Taylor-series algorithm for \(\log T\). Define the rational threshold
\(\tau=\frac{r-1/(8T^2)}{2(1+\rho)}\).
The preceding gaps imply
\(L^\star>\tau\)
for positive source instances, and
\(L^\star<\tau\)
for negative source instances. Thus deciding whether \(L^\star\geq\tau\) decides Unbounded Subset Sum.
The reduction is polynomial, so exact maximization of \(L\) is \(\mathrm{NP\text{-}hard\).
The hardness is weak because the reduction starts from Unbounded Subset Sum. Its distinguishing objective gap is inverse-polynomial in the numerical value \(T\), not necessarily in the binary input length. Therefore this proof does not establish APX-hardness, constant-factor inapproximability, or hardness of computing a coarse approximation.
The source of hardness is the integer bundle-pricing problem that remains inside the continuous configuration program. Fractional configuration masses do not eliminate this integer subproblem.
⟨structured verdict parsed — rendered above⟩
The reduction is mathematically sound in substance and establishes weak NP-hardness of the exact threshold problem. The logarithmic gadget, configuration-program evaluation, and threshold separation all check out. The remaining issues are routine but should be stated explicitly for a fully rigorous write-up.
The selected source problem is the standard Unbounded Subset Sum problem with positive integer coefficients. It is NP-hard; the cited paper describes precisely this formulation as NP-hard ([arXiv:2407.05435](https://arxiv.org/abs/2407.05435)).
Membership in NP is not demonstrated in the output, despite the stronger assertion “NP-complete.” This omission does not affect the reduction, which only requires NP-hardness.
Removing coefficients \(a_j>T\) is valid because all coefficients and multiplicities are nonnegative. However, the proof does not explicitly handle the possibility that this removes every item. Similarly, it assumes \(T\geq2\) because smaller cases are trivial without specifying the fixed instance to which those cases are mapped. These are routine preprocessing branches but should be stated.
The approximation argument is correct.
For \(x=a_j/T\in(0,1]\), Taylor’s remainder gives
\[ 0\leq e^x-S_N(x)\leq \frac{e}{(N+1)!} <\frac{3}{(N+1)!}\leq\frac{3}{2^N}. \]
Consequently,
\[ e^x\leq S_N(x)+\frac{3}{2^N}=R_j \leq e^x+\frac{3}{2^N} \leq e^x+\delta. \]
It then follows from \(\log(1+u)\leq u\) and \(e^{-x}\leq1\) that
\[ 0\leq\log R_j-x \leq\log(1+\delta e^{-x}) \leq\delta. \]
That final elementary inequality is omitted, but the conclusion is correct.
The encoding-length claim is also correct: \(N=O(\log T)\), and the numerators and denominators appearing in the truncated exponential have polynomial bit length.
The derivative \(h'(x)=1/x-1/T\) has the asserted sign, so \(h\) is strictly increasing below \(T\) and strictly decreasing above \(T\).
For positive integral \(V\neq T\), monotonicity reduces the comparison to \(T-1\) and \(T+1\). With \(x=1/T\leq1/2\),
\[ x-\log(1+x) =\int_0^x\frac{t}{1+t}\,dt \geq\int_0^x\frac{t}{2}\,dt =\frac{x^2}{4}, \]
and
\[ -\log(1-x)-x =\int_0^x\frac{t}{1-t}\,dt \geq\int_0^x t\,dt =\frac{x^2}{2}. \]
Thus the claimed gap \(1/(4T^2)\) is valid.
If \(V(B)=T\), positivity of every \(a_j\) implies \(\sum_jB_j\leq T\). Hence the lower bound on \(f(B)\) is correct. The separation between bundles with \(V(B)=T\) and all other bundles is strict and has the stated constants.
The comparison is correct. For \(T\geq2\),
\[ h(4T^2)=\log(4T^2)-4T<-2. \]
For every singleton,
\[ f(e_j)\geq\log a_j-\frac{a_j}{T}-\delta\geq-1-\delta>-2. \]
Therefore no bundle with \(V(B)\geq K\) can maximize \(f\), and \(a_j\geq1\) gives \(B_j\leq V(B)<K\).
The write-up does not explicitly conclude that a maximizer exists. The displayed comparison supplies the missing routine justification: all candidates with \(V\geq K\) are dominated by a singleton, while only finitely many integer bundles satisfy \(V<K\). This should be stated before selecting \(B^\star\).
The distributions sum to one, and the induced supplies are correctly calculated:
\[ \rho\psi_0=\frac12,\qquad \rho\psi_j=\frac K2. \]
All constructed inputs are nonnegative rationals with polynomial encoding length.
The worker-value indices are consistent with the intended convention \(w_{qp}\), despite changing between numeric and named indices.
The anchor argument is correct. A positive-mass dummy configuration must contain at least one anchor to avoid utility zero. Since dummy mass and total anchor supply both equal \(1/2\), the expected number of anchors per dummy is exactly one. Therefore every positive-mass dummy configuration has exactly one anchor and the signal receives no anchors.
With \(\mu(B)=2\eta_s(B)\),
\[ z_{sj}=\frac12\mathbb E_\mu[B_j]. \]
The signal-firm term is \(\frac12\mathbb E_\mu[\log V(B)]\), and the only nonzero worker terms are
\[ -\frac12\mathbb E_\mu[B_j]\log R_j. \]
Thus
\[ (1+\rho)L=\frac12\mathbb E_\mu[f(B)] \]
is correct.
Because configurations form a countably infinite set, the write-up should explicitly justify that this expectation is well-defined. Supply constraints give finite first moments, while \(\log V(B)\leq V(B)\) for positive integral \(V(B)\); hence both the positive and negative components are integrable. This is a routine analytic clarification.
The converse deterministic allocation is feasible because \(B_j^\star<K\), so \(K-B_j^\star\) is a nonnegative integer. It uses exactly the prescribed anchor and item supplies. Therefore
\[ L^\star=\frac{\max_B f(B)}{2(1+\rho)} \]
follows.
The constants are correct. Writing all errors in units of \(1/(64T^2)\):
Hence the two cases lie strictly on opposite sides of the rational threshold.
The claim that \(h(T)=\log T-1\) can be approximated to additive error \(1/(64T^2)\) in polynomial time is true, but “the standard Taylor-series algorithm” is insufficiently specified for a formal complexity reduction. A direct Taylor expansion about \(1\) is not suitable for arbitrary \(T\); the write-up should name the range-reduction method and state its bit-complexity guarantee. This is an expositional gap rather than a new mathematical obstacle.
The prover genuinely resolves the target under the exact threshold-decision interpretation: the continuous formulation remains NP-hard despite allowing fractional configuration masses. The proof establishes weak NP-hardness only, as correctly acknowledged.
The required repairs are limited to explicit preprocessing branches, attainment and integrability justifications, and a precise polynomial-time procedure for approximating \(\log T\).
⟨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.