Answer: \(\mathrm{polynomial\text{-}time\ solvable}\)
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing a Nash optimal matching is NP-complete even when each firm has capacity 2, all valuations are in {0, 1, 2}, and each agent has degree at most 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite worker types \(i\) with rational masses \(\mu_i\) and finite firm types \(j\) with rational masses \(\nu_j\), capacity 2, and two-sided valuation matrices (restricted to \(\{0,1,2\}\) and type-degree at most 3), choose masses \(y_{j,b}\) of firm type \(j\) receiving each integral worker-type bundle \(b\) with \(|b| \le 2\), satisfying \(\sum_b y_{j,b} = \nu_j\) and \(\sum_{j,b} b_i y_{j,b} = \mu_i\), to maximize the normalized sum of worker and firm log utilities, excluding zero-utility assignments.
Definitions. An instance has finite worker types \(A\), firm types \(B\), rational type masses \(M_W\mu_a\) and \(M_F\nu_b\), valuations \(v^W_{ab},v^F_{ba}\in\{0,1,2\}\), and capacity \(2\) per firm. Each type positively values at most three counterpart types.
For each \(b\), let \(\mathcal S\) be the multisets of worker types of cardinality at most \(2\). Choose \(y_{b,S}\ge0\), set \(x_{ab}=\sum_{S\in\mathcal S}n_a(S)y_{b,S}\), and require \(\sum_Sy_{b,S}=M_F\nu_b\) and \(\sum_{b,S}n_a(S)y_{b,S}=M_W\mu_a\).
The objective is to maximize \(L=\sum_{a,b}x_{ab}\log v^W_{ab}+\sum_{b,S}y_{b,S}\log\!\left(\sum_an_a(S)v^F_{ba}\right)\), with zero-valued terms infeasible whenever assigned positive mass.
Target. Is this continuous maximum-Nash-welfare problem solvable in polynomial time, or is it NP-hard?
Nearest known results. For the discrete problem with individual workers and firms, computing a Nash-optimal many-to-one matching is NP-complete even with capacity \(2\), valuations in \(\{0,1,2\}\), and at most three positively valued counterparts per agent.
No verified result for exactly the mass-formulated problem above is used here.
Under the standard binary Turing model for the rational masses, the stated continuous maximum-Nash-welfare problem is polynomial-time solvable.
More precisely, one can return either:
The sparsity assumption that every type positively values at most three counterpart types is not needed for this result.
Write \(r_a=M_W\mu_a\) and \(f_b=M_F\nu_b\). For each firm type \(b\), call a multiset \(S\) admissible if:
Any nonadmissible configuration must have \(y_{b,S}=0\). Thus it may be deleted. This is exactly the zero-value convention in the question. If the intended convention additionally forbids assigning a worker with \(v^F_{ba}=0\) inside an otherwise positive firm bundle, deleting those configurations as well does not affect the argument.
For an admissible configuration, substitute
\[ x_{ab}=\sum_S n_a(S)y_{b,S}. \]
Interchanging the finite sums gives
\[ L=\sum_{b,S}c_{b,S}y_{b,S}, \]
where
\[ c_{b,S} = \sum_a n_a(S)\log v^W_{ab} + \log U_{b,S}. \]
Consequently, the apparently logarithmic optimization problem is a linear optimization problem over the configuration variables.
The number of worker-type multisets of cardinality at most \(2\) is
\[ 1+|A|+\frac{|A|(|A|+1)}2. \]
Hence the number of variables is \(O(|B||A|^2)\), which is polynomial in the explicit input length.
After deleting inadmissible configurations, the feasible region is
\[ \mathcal P= \left\{ y\geq 0: \sum_S y_{b,S}=f_b\ \text{for every }b,\quad \sum_{b,S}n_a(S)y_{b,S}=r_a\ \text{for every }a \right\}. \]
Its constraint matrix has entries only in \(\{0,1,2\}\). It is bounded because
\[ 0\leq y_{b,S}\leq f_b \]
for every variable. Feasibility is therefore decidable by an ordinary rational linear program in polynomial time.
For every admissible configuration, each positive worker valuation is \(1\) or \(2\), while
\[ U_{b,S}\in\{1,2,3,4\}. \]
Define
\[ p_{b,S} = \sum_a n_a(S)\mathbf 1[v^W_{ab}=2] +\mathbf 1[U_{b,S}=2] +2\mathbf 1[U_{b,S}=4] \]
and
\[ q_{b,S}=\mathbf 1[U_{b,S}=3]. \]
Then \(p_{b,S}\in\{0,1,2,3,4\}\), \(q_{b,S}\in\{0,1\}\), and
\[ c_{b,S}=p_{b,S}\log 2+q_{b,S}\log 3. \]
Put
\[ P(y)=\sum_{b,S}p_{b,S}y_{b,S}, \qquad Q(y)=\sum_{b,S}q_{b,S}y_{b,S}, \qquad \rho=\frac{\log 3}{\log 2}. \]
Since \(\log 2>0\), maximizing \(L\) is equivalent to maximizing
\[ P(y)+\rho Q(y). \]
The number \(\rho\) is irrational: if \(\rho=m/n\in\mathbb Q\), then \(2^m=3^n\) after clearing signs and denominators, contradicting unique prime factorization.
Let \(N\) denote the binary input length. Every vertex of \(\mathcal P\) has polynomial encoding length.
Indeed, if a vertex has \(s\) positive components, their columns in the equality-constraint matrix must be linearly independent. Otherwise, a nonzero kernel direction supported on those positive components would permit sufficiently small perturbations in both directions, contradicting extremality. Thus \(s\leq |A|+|B|\).
Choose \(s\) independent rows and let \(G\) be the resulting nonsingular \(s\times s\) submatrix. Its entries lie in \(\{0,1,2\}\). The positive vertex coordinates solve \(Gz=d\), where \(d\) is a subvector of the rational mass vector. Cramer's rule and Hadamard's inequality give
\[ |\det G|\leq (2\sqrt{s})^s. \]
After clearing the denominators of \(d\), the same bound applied to the replaced-column determinants shows that every numerator and denominator in \(z\) has bit length polynomial in \(N\).
It follows that there is an explicitly computable polynomial \(K(N)\) such that, for every pair of vertices \(y,z\), both \(P(y)-P(z)\) and \(Q(y)-Q(z)\) are rationals whose numerators and denominators have at most \(K(N)\) bits.
A numerical approximation to \(\rho\) is not by itself sufficient: one must prove that the chosen precision preserves the ordering of all vertices.
We use the following fixed-base consequence of an effective lower bound for linear forms in logarithms.
Two-logarithm separation lemma. There is an effectively computable constant \(C_0>0\), depending only on \(2\) and \(3\), such that for all integers \(u,v\), not both zero, with \(H=\max\{3,|u|,|v|\}\),
\[ |u\log 2+v\log 3|>H^{-C_0}. \]
This is a direct specialization of the explicit bounds for homogeneous rational linear forms in logarithms of algebraic numbers; the relevant hypotheses hold because \(2\) and \(3\) are algebraic and multiplicatively independent. See [Matveev’s explicit lower-bound theorem](https://www.mathnet.ru/eng/im190).
Now consider two vertices \(y,z\), and set
\[ \Delta_P=P(y)-P(z), \qquad \Delta_Q=Q(y)-Q(z). \]
If \((\Delta_P,\Delta_Q)\neq(0,0)\), clear their denominators to obtain integers \(u,v\), of \(O(K(N))\) bits, and a positive integer \(D\), also of \(O(K(N))\) bits, such that
\[ \Delta_P+\rho\Delta_Q = \frac{u\log 2+v\log 3}{D\log 2}. \]
The numerator is nonzero by multiplicative independence. The separation lemma therefore yields a computable constant \(C_1\) such that
\[ |\Delta_P+\rho\Delta_Q|>2^{-C_1K(N)}. \]
Thus distinct vertex objective values have an inverse-exponential gap whose exponent is polynomial in the input length.
Furthermore,
\[ 0\leq Q(y)\leq \sum_b f_b \]
for every feasible \(y\). Let \(R\) be an easily computed binary bound satisfying
\[ |Q(y)-Q(z)|\leq R \]
for all feasible \(y,z\). The bit length of \(R\) is polynomial in \(N\).
Choose a rational number \(\widehat\rho\) satisfying
\[ |\widehat\rho-\rho| < \frac{2^{-C_1K(N)}}{2R}. \]
Such an approximation has polynomially many bits and is computable in polynomial time. For example, rational upper and lower bounds for \(\log 2\) and \(\log 3\) can be computed using the geometrically convergent series
\[ \log z = 2\sum_{j\geq 0} \frac{1}{2j+1} \left(\frac{z-1}{z+1}\right)^{2j+1}. \]
For any pair of vertices with different true objective values,
\[ \left| (\Delta_P+\widehat\rho\Delta_Q) - (\Delta_P+\rho\Delta_Q) \right| < \frac12|\Delta_P+\rho\Delta_Q|. \]
Therefore \(P+\widehat\rho Q\) and \(P+\rho Q\) order every pair of vertices in exactly the same way. If two vertices tie under the true objective, irrationality of \(\rho\) implies \(\Delta_P=\Delta_Q=0\), so they also tie under the approximating objective.
The complete algorithm is:
\[ \max_{y\in\mathcal P} \sum_{b,S} \bigl(p_{b,S}+\widehat\rho q_{b,S}\bigr)y_{b,S}. \]
\[ L^*=P(y^*)\log 2+Q(y^*)\log 3. \]
All coefficients in Step \(6\) have polynomial encoding length. Exact rational linear programming therefore runs in polynomial time.
Because every nonempty bounded polytope has an optimal vertex for a linear objective, and because the rational approximate objective has exactly the same vertex ordering as the true objective, the returned solution is exactly optimal for the original logarithmic objective.
The discrete problem requires each individual firm to select one integral bundle. In the mass formulation, \(y_{b,S}\) may split a firm type continuously among several configurations. This is precisely a configuration-LP relaxation of the individual allocation requirement, and its constraint matrix need not force integral vertices.
Consequently, even replacing every individual by a separate type does not reproduce the discrete problem: the corresponding unit mass may still be divided fractionally. The discrete NP-completeness result therefore does not contradict the polynomial-time algorithm above.
The stated continuous mass-formulated maximum-Nash-welfare problem is exactly polynomial-time solvable. The decisive features are the fixed capacity \(2\), which makes the configuration set polynomial, and the fact that every objective coefficient is a fixed rational linear combination of \(\log 2\) and \(\log 3\). Effective separation for these two logarithms completes the exact bit-complexity argument.
⟨structured verdict parsed — rendered above⟩
The prover’s central classification is correct in substance: the continuous mass formulation reduces to a polynomial-size rational polytope with a linear objective whose coefficients lie in the fixed span of \(\log 2\) and \(\log 3\). The vertex-separation argument then permits replacement of the irrational coefficient by a polynomial-bit rational approximation without changing the optimal vertex.
No false central step or counterexample was found. Several details need tightening before the write-up is fully rigorous.
This step is correct.
This step is correct.
The number of multisets of size at most \(2\) is exactly \(1+|A|+|A|(|A|+1)/2\). Thus there are polynomially many variables. The constraints are rational equalities with coefficients in \(\{0,1,2\}\), and \(0\le y_{b,S}\le f_b\) follows from nonnegativity and \(\sum_Sy_{b,S}=f_b\). Standard rational LP feasibility is therefore polynomial-time decidable.
The coefficient calculation is correct.
Because an admissible bundle contains at most two workers and every valuation belongs to \(\{0,1,2\}\), one has \(U_{b,S}\in\{1,2,3,4\}\). The definitions of \(p_{b,S}\) and \(q_{b,S}\) correctly encode every coefficient as \(p_{b,S}\log 2+q_{b,S}\log 3\). The stated ranges for \(p_{b,S}\) and \(q_{b,S}\) are also correct.
The proof that \(\rho=\log 3/\log 2\) is irrational is valid.
The support-independence argument is correct: a linear dependence among columns indexed by positive coordinates would yield a two-sided feasible perturbation and contradict extremality.
There is, however, a minor gap in the determinant estimate. After clearing denominators in the mass vector, a replaced-column determinant no longer has all entries bounded by \(2\), so the displayed Hadamard bound cannot literally be reused unchanged. The required conclusion—polynomial numerator and denominator lengths—still follows routinely from the input bit bounds, but the write-up should explicitly bound the cleared right-hand-side entries and then the corresponding replaced-column determinants. It should also exhibit or define the claimed computable polynomial \(K(N)\).
The stated two-logarithm separation lemma has the right strength. The cited Matveev result gives a lower bound polynomial in the coefficient height when the algebraic logarithms are fixed, which yields the claimed inverse-exponential gap. The cited paper does concern bounds of this form ([Matveev’s paper](https://www.mathnet.ru/eng/im190)).
For strict verifiability, the citation should identify the precise theorem or corollary and explicitly check its applicable independence/Kummer hypotheses for \(2\) and \(3\). The current assertion that the “relevant hypotheses hold” is too compressed, although the specialized separation statement itself is valid.
The denominator-clearing calculation and the deduction of a bound \(2^{-C_1K(N)}\) are otherwise correct. Irrationality correctly implies that a true tie between two vertices requires both \(\Delta_P=0\) and \(\Delta_Q=0\).
The perturbation estimate using \(\widehat\rho\) is correct provided \(R\) is chosen strictly positive. The text only calls \(R\) a bound; it should explicitly choose a positive bound to avoid division by zero in degenerate instances where \(Q\equiv0\).
The logarithm series converges geometrically for \(z=2,3\), but the write-up omits an explicit truncation-error bound and the interval calculation needed to turn bounds on \(\log 2\) and \(\log 3\) into a certified bound on their ratio. This is a routine computational detail, not a substantive mathematical gap.
Given the preceding separation bound, the rational LP in Step 6 has polynomial-bit coefficients and exactly the same ordering on vertices as the true objective. Since the polytope is bounded, an optimal vertex exists. Returning an optimal basic feasible solution therefore gives an exact optimum for the original objective.
The theorem initially promises “a proof” of infeasibility, whereas the algorithm merely says to test feasibility. If a certificate is part of the output specification, the prover should state that a rational Farkas certificate is returned and note its polynomial encoding bound. This omission does not affect the complexity classification.
This explanation is correct. Unit type mass remains divisible in the continuous formulation, so replacing individuals by distinct types does not impose integrality. Consequently, the cited discrete hardness result does not transfer directly.
The polynomial-time classification is established in substance. The remaining issues concern explicit bit-bound bookkeeping, precise certification of the logarithmic-separation theorem’s hypotheses, certified approximation details, and the promised infeasibility certificate. All are routine expositional repairs and do not require a new algorithm or new mathematical idea.
⟨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.