Answer: \(\text{NP-hard}\)
Lemma 5.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet $f$ be a convex function and let $\mathcal{X}$ be a convex set. Consider the program $\min_{x \in \mathcal{X}} f(x)$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) divisible goods, \(\rho\in(0,1]\), a common homogeneity degree \(r\), and \(\tau\) valuation types with positive rational masses \(\mu_t\) summing to \(1\), compute an \(\varepsilon\)-optimal allocation and an \(\varepsilon\)-accurate dual certificate for maximizing \(\frac{1}{\rho}\sum_t\mu_t v_t(x_t)^\rho\), subject to \(x_t\ge 0\) and \(\sum_t\mu_t x_{tj}\le 1\) for every good \(j\), assuming each valuation has an efficient finite-precision gradient-oracle representation.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) divisible goods, each of supply \(1\), and binary-rational parameters \(r,\rho\in(0,1]\) and \(\varepsilon\in(0,1)\).
Each valuation \(v_t:\mathbb R_{\geq0}^m\to\mathbb R_{\geq0}\) is continuous, nonzero, coordinatewise nondecreasing, concave, normalized by \(v_t(0)=0\), homogeneous of common degree \(r\), and differentiable on \(\mathbb R_{>0}^m\).
Its finite description provides a gradient oracle: at any positive rational bundle \(z\) and precision \(k\), it returns a rational vector within \(2^{-k}\) of \(\nabla v_t(z)\) in maximum norm, in time polynomial in the description length, the query bit length, and \(k\), with a uniform polynomial bound.
An allocation assigns a common per-capita bundle \(x_t\geq0\) to each type, with \(\sum_t\mu_t x_{tj}\leq1\) for every good; bundles have no additional individual upper bound.
Write \(F(x)=\rho^{-1}\sum_t\mu_t v_t(x_t)^\rho\) and let \(F^*\) be its feasible maximum. Define the resource-price dual by \(D(q)=\sum_jq_j+\sum_t\mu_t\sup_{z\geq0}\{\rho^{-1}v_t(z)^\rho-q\cdot z\}\), for \(q\geq0\).
The computational problem is to return rational feasible \(x\) and rational \(q\geq0\) satisfying \(F^*-F(x)\leq\varepsilon\) and \(D(q)-F^*\leq\varepsilon\).
Is this problem solvable in polynomial time in \(m,\tau,L,\log(1/\varepsilon)\), or is it NP-hard, where \(L\) is the total binary description length of the masses, valuation representations, \(r\), and \(\rho\)?
For a finite list of agents, Goel and Plaut establish polynomial-time optimization using valuation-gradient queries and recovery of optimal resource multipliers from an exact optimum ([source](https://arxiv.org/html/2009.09351)).
The later thesis retains these ideal-oracle claims but does not specify finite-precision guarantees for the mass formulation and its approximate dual certificate ([source](https://cs.stanford.edu/people/bplaut/BenPlautThesisFinal.pdf)).
The problem is \(\text{NP-hard}\) under the stated assumptions on valuation representations, even with one good, two distinct linear valuation types, equal masses, and fixed accuracy \(\varepsilon=1/4096\).
Here a valuation representation may be any finite description satisfying the uniform polynomial-time gradient-oracle promise. The reduction below uses a fixed representation scheme satisfying that promise. Its coefficients have succinct descriptions; writing them explicitly as binary rationals would require exponentially many bits.
The hardness already holds for returning the approximate primal allocation, so requiring the dual certificate cannot remove it.
Let \(\varphi\) be an instance of Boolean satisfiability. Put
\[ N=\max\{2,|\varphi|\},\qquad B=2^N. \]
Construct a society with
\[ m=1,\qquad \tau=2,\qquad \mu_1=\mu_2=\frac12,\qquad r=1,\qquad \rho=\frac1B,\qquad \varepsilon=\frac1{4096}. \]
Define linear valuations \(v_t(z)=a_tz\), where
\[ a_1= \begin{cases} 2^{-B},&\varphi\text{ is satisfiable},\\ 2^{-2B},&\varphi\text{ is unsatisfiable}, \end{cases} \qquad a_2=2^{-(B+1)}. \]
The first representation consists of \(\varphi\) and a fixed algorithm described below. The second consists of \(N\) and another fixed algorithm. Constructing these descriptions does not require deciding satisfiability.
Both coefficients are strictly positive and, since \(B\geq4\), distinct. Thus the support genuinely contains two distinct valuation types. Both valuations are continuous, nonzero, nondecreasing, concave, normalized at zero, homogeneous of common degree \(1\), and differentiable on the positive domain.
The binary encoding of \(\rho=2^{-N}\) has length \(O(N)\). Consequently, the total instance length is \(L=O(N)\).
For these valuations, \(\nabla v_t(z)=a_t\), independently of the positive rational query \(z\).
The first oracle operates as follows:
In the first case,
\[ |0-a_1|\leq2^{-B}\leq2^{-k}, \]
so the answer has the required accuracy.
In the second case, \(\varphi\) has at most \(N\) variables. Exhaustive satisfiability testing therefore takes time at most \(2^N\operatorname{poly}(N)=B\operatorname{poly}(N)\). Since \(k\geq B\), this is polynomial in \(N\) and \(k\). The exact coefficient has binary length at most \(2B+O(1)\leq2k+O(1)\), so producing the output also takes polynomial time.
The second oracle returns \(0\) when \(k<B\) and returns \(2^{-(B+1)}\) exactly otherwise. Its error and runtime satisfy the same bounds.
Comparing \(k\) with \(B\) only requires constructing the \(N+1\)-bit binary representation of \(B\). Hence both oracles have a uniform runtime bound polynomial in the description length, query bit length, and \(k\), exactly as required.
Write
\[ c_t=a_t^\rho. \]
Then
\[ c_1= \begin{cases} \frac12,&\varphi\text{ is satisfiable},\\ \frac14,&\varphi\text{ is unsatisfiable}, \end{cases} \qquad c_2=2^{-1-\rho}. \]
In particular, \(c_1,c_2\geq1/4\) and \(0<\rho\leq1/4\).
Feasibility means \(x_1+x_2\leq2\). Since both valuations are strictly increasing, an optimum exhausts supply. On allocations exhausting supply, define
\[ H(s)=F(s,2-s) =\frac{c_1s^\rho+c_2(2-s)^\rho}{2\rho}, \qquad 0\leq s\leq2. \]
For \(0<s<2\),
\[ H'(s)=\frac12\left(c_1s^{\rho-1}-c_2(2-s)^{\rho-1}\right). \]
This derivative tends to positive infinity at the left endpoint and negative infinity at the right endpoint. Moreover, \(H\) is strictly concave. Its unique maximizer \(s^*\) is therefore interior and satisfies
\[ s^*=\frac{2}{1+(c_2/c_1)^{1/(1-\rho)}}. \]
If \(\varphi\) is satisfiable, \(c_2/c_1=2^{-\rho}<1\), giving
\[ s^*>1. \]
If \(\varphi\) is unsatisfiable, \(c_2/c_1=2^{1-\rho}\), giving the exact value
\[ s^*=\frac{2}{1+2}=\frac23. \]
Thus the two cases have a constant separation in their optimal first-type allocations.
We next prove that the specified additive accuracy preserves this separation.
For \(0<s<2\),
\[ -H''(s) =\frac{1-\rho}{2} \left(c_1s^{\rho-2}+c_2(2-s)^{\rho-2}\right). \]
Because \(\rho-2<0\) and both arguments lie in \((0,2)\),
\[ s^{\rho-2}\geq2^{\rho-2}\geq\frac14, \qquad (2-s)^{\rho-2}\geq\frac14. \]
Together with \(c_1,c_2\geq1/4\) and \(1-\rho\geq3/4\), this yields
\[ -H''(s)\geq \frac{3}{8}\left(\frac1{16}+\frac1{16}\right) =\frac3{64}. \]
Consequently,
\[ H(s^*)-H(s)\geq\frac3{128}(s-s^*)^2 \qquad\text{for every }s\in[0,2]. \]
To justify this inequality, the function \(H(s)+(3/128)s^2\) is concave on the interior. Its supporting-tangent inequality at \(s^*\), together with \(H'(s^*)=0\), gives the stated bound. Continuity extends it to the endpoints.
Now let \(x\) be any feasible output satisfying \(F^*-F(x)\leq\varepsilon\). Set \(s=x_1\). Feasibility gives \(x_2\leq2-s\), so monotonicity implies
\[ F(x)\leq H(s). \]
Since \(F^*=H(s^*)\), we obtain
\[ H(s^*)-H(s)\leq\varepsilon. \]
If \(|s-s^*|\geq1/6\), however, the curvature bound gives
\[ H(s^*)-H(s)\geq \frac3{128}\left(\frac16\right)^2 =\frac1{1536} >\frac1{4096}. \]
Therefore every valid output satisfies \(|x_1-s^*|<1/6\). It follows that:
Comparing the returned rational coordinate with \(5/6\) decides satisfiability.
The constructed instances also admit rational approximate dual certificates.
Define
\[ q^*=c_1(s^*)^{\rho-1} =c_2(2-s^*)^{\rho-1}>0. \]
The equality follows from \(H'(s^*)=0\). For each type, the function
\[ z\longmapsto \frac{c_tz^\rho}{\rho}-q^*z \]
is strictly concave, and its derivative vanishes at the corresponding optimal bundle. Those bundles therefore attain the suprema defining \(D(q^*)\). As their weighted sum is \(1\), substitution gives \(D(q^*)=F^*\).
For any \(q>0\), direct maximization gives
\[ D(q)=q+\frac{1-\rho}{2\rho} \left(c_1^{1/(1-\rho)}+c_2^{1/(1-\rho)}\right) q^{-\rho/(1-\rho)}. \]
This expression is continuous on the positive domain. Rational positive prices sufficiently close to \(q^*\) therefore satisfy \(D(q)-F^*\leq\varepsilon\). Likewise, continuity of \(H\) gives rational feasible allocations with the required primal accuracy. Thus the reduction uses valid instances with nonempty sets of acceptable outputs.
A polynomial-time solver for the requested problem would decide satisfiability by constructing this instance, making one solver call, and comparing \(x_1\) with \(5/6\). All construction and decoding steps take polynomial time, while \(m,\tau,\log(1/\varepsilon)\) are constant and \(L=O(N)\). This proves \(\text{NP-hardness}\). In particular, a general polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The exact-gradient calculations in [Goel and Plaut, Section 5](https://arxiv.org/html/2009.09351#S5), also presented in [Plaut’s thesis, Section 4.5](https://cs.stanford.edu/people/bplaut/BenPlautThesisFinal.pdf#page=105), recover objective information from valuation gradients. They do not provide the finite-precision guarantee needed here. In this construction, exponentially small coefficients become constant-sized welfare coefficients after taking the input-dependent power \(\rho\). The absolute-error gradient promise permits precisely this obstruction.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the task: the stated representation model permits an \(\mathrm{NP}\)-hard family. No major or minor mathematical issues were found.
The reduction constructs descriptions of the valuations without deciding satisfiability. The first description contains the formula and a fixed oracle algorithm; its mathematical definition may depend on satisfiability because the supplied algorithm computes the required approximations.
The parameters satisfy all specified restrictions:
Positive linear valuations satisfy every required analytical property, including nonzeroness, normalization, and differentiability.
The input-length claim is correct. The coefficients are supplied through succinct valuation descriptions, rather than explicit binary expansions. The binary-rational encoding of \(\rho\) requires \(O(N)\) bits, and the remaining descriptions also have length \(O(N)\). Thus \(L=O(N)\).
Finding: Valid construction under the representation model explicitly allowed by the task.
For \(k<B\), returning zero has error at most \(2^{-B}\leq2^{-k}\) for either valuation. The second coefficient is even smaller than this upper bound.
For \(k\geq B\), the first oracle enumerates at most \(2^N=B\) assignments. Its runtime is \(B\operatorname{poly}(N)\), which is polynomial in \(N\) and the numerical precision parameter \(k\), as the task requires.
The exact output lengths are also correctly bounded:
Both are \(O(k)\) in this branch. Comparing \(k\) with \(B\) does not require constructing a string of length \(B\): the binary representation of \(B\) has only \(N+1\) bits.
The oracle is independent of the queried bundle, so the guarantee applies to every positive rational query. The algorithms have a uniform polynomial bound across all constructed descriptions.
Finding: The oracle promise is fully verified. Exhaustive satisfiability testing does not violate it, because that branch is entered only at exponentially large requested precision.
The transformed coefficients are correct:
\(c_1=1/2\) in the satisfiable case, \(c_1=1/4\) in the unsatisfiable case, and \(c_2=2^{-1-\rho}\).
Consequently, \(c_1,c_2\geq1/4\).
Feasibility is exactly \(x_1+x_2\leq2\). Strict monotonicity ensures that every optimum exhausts supply, so maximizing \(H(s)=F(s,2-s)\) over \([0,2]\) correctly represents the original optimum.
The derivative and second derivative are correct. Since \(0<\rho<1\), the derivative has the claimed endpoint limits and the second derivative is strictly negative throughout the interior. The unique maximizer is therefore interior.
Solving the displayed stationarity equation gives exactly the stated expression for \(s^*\). Its consequences are correct:
Finding: The optimal allocation separates the two cases as claimed.
Every inequality in the curvature estimate has the correct direction. For an argument in \((0,2)\), the negative exponent \(\rho-2\) gives a value at least \(2^{\rho-2}\geq1/4\). Together with the coefficient and parameter bounds, this yields \(-H''(s)\geq3/64\).
The supporting-tangent argument is valid: adding \((3/128)s^2\) makes the second derivative nonpositive, and its tangent inequality at the interior maximizer produces the stated quadratic loss bound. Continuity legitimately extends that bound to both endpoints.
For a feasible allocation that leaves supply unused, monotonicity correctly gives \(F(x)\leq H(x_1)\). Thus the proof covers every valid output, including boundary allocations and allocations with slack.
The critical arithmetic is correct:
\((3/128)(1/6)^2=1/1536>1/4096\).
Therefore every acceptable output satisfies \(|x_1-s^*|<1/6\). The resulting strict inequalities \(x_1>5/6\) and \(x_1<5/6\) are correct in their respective cases. Equality at the decoding threshold cannot occur for a valid output.
Finding: Every sufficiently accurate primal output determines satisfiability.
The proposed price \(q^*\) is positive, and the equality between its two expressions follows directly from stationarity.
For each type, the corresponding optimal bundle is a global maximizer of the individual dual objective: the function is strictly concave, and its derivative vanishes at that positive bundle. Substitution into the dual correctly cancels the resource-price terms because weighted consumption equals \(1\), giving \(D(q^*)=F^*\).
The explicit expression for \(D(q)\) has the correct coefficient and exponents. It is finite and continuous for every \(q>0\). Consequently, positive rational prices sufficiently close to \(q^*\) meet the dual accuracy requirement. Continuity of \(H\) likewise supplies rational feasible primal allocations with the required accuracy.
This section establishes nonempty sets of acceptable rational outputs. It does not claim polynomial output-length bounds, and such bounds are unnecessary for the hardness implication being proved.
Finding: The reduction uses valid instances for the full primal-and-dual task.
The construction and rational threshold comparison take polynomial time. A polynomial-time solver would return its rational output within polynomial time, allowing the stated decoding procedure to decide satisfiability. Since every acceptable output reveals the answer, the reduction does not depend on how the solver chooses among acceptable outputs.
The resulting hardness is for the representation model in the task, with input-dependent \(\rho\). The proof does not claim hardness for explicitly encoded linear coefficients or fixed \(\rho\).
The literature comparison is accurate. The cited sections reconstruct objective information from valuation gradients and recover multipliers from an optimal allocation; they do not supply the finite-precision guarantee required here. The reduction does not invoke their optimization claims as a theorem supporting its own argument. [Goel and Plaut, Section 5](https://arxiv.org/html/2009.09351#S5), [Plaut’s thesis, Section 4.5](https://cs.stanford.edu/people/bplaut/BenPlautThesisFinal.pdf#page=105).
Repair feedback: None required. The reduction, oracle verification, numerical separation, and dual existence argument are sufficient as written.
⟨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.