Answer: \(\text{Polynomial-time solvable}\)
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet $C\in\profiles_{>0}$ and $\delta^0\in\Delta(\csum)$ be a distribution with full support. Denote by $(\delta^k)_{k\in\mathbb N}$ its induced sequence. Then, $(F(\delta^k))_{k\in\mathbb N}$ converges to the optimum Nash product. If the Nash distribution is unique, $(\delta^k)_{k\in\mathbb N}$ converges to \nash.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite project set \(A\), finite type set \(T\), rational masses \(\mu_\theta\ge 0\) with \(\sum_{\theta\in T}\mu_\theta=1\), per-agent contributions \(c_\theta>0\), and utility vectors \(u_\theta:A\to\mathbb{Q}_{\ge 0}\), let \(V=\sum_{\theta\in T}\mu_\theta c_\theta\) and \(U_\theta(\delta)=\sum_{a\in A}u_\theta(a)\delta(a)\). Compute \(\widehat{\delta}\in\Delta(V)\) such that \(\sum_{\theta\in T}\mu_\theta c_\theta\log U_\theta(\widehat{\delta})\ge\max_{\delta\in\Delta(V)}\sum_{\theta\in T}\mu_\theta c_\theta\log U_\theta(\delta)-\varepsilon\).
Let \(A\) contain \(m\ge 1\) projects. A society is given by its support: a list \(T\) of \(\tau\ge 1\) types with positive binary rational masses \(\mu_\theta\), summing to \(1\); \(\tau\) counts supported types, not all possible types.
Each type has a binary rational contribution \(c_\theta>0\) and utilities \(u_\theta:A\to\mathbb Q_{\ge 0}\), with \(\max_{a\in A}u_\theta(a)>0\). Set \(V=\sum_{\theta\in T}\mu_\theta c_\theta\), \(\Delta(V)=\{\delta\in\mathbb R_{\ge 0}^{A}:\sum_{a\in A}\delta(a)=V\}\), and \(U_\theta(\delta)=\sum_{a\in A}u_\theta(a)\delta(a)\).
Define \(F(\delta)=\sum_{\theta\in T}\mu_\theta c_\theta\log U_\theta(\delta)\), using natural logarithms and \(F(\delta)=-\infty\) if any supported type has zero utility. Given a binary rational \(\varepsilon>0\), the approximation task is to compute a rational \(\widehat\delta\in\Delta(V)\) satisfying \(F(\widehat\delta)\ge\max_{\delta\in\Delta(V)}F(\delta)-\varepsilon\). Any allocation satisfying this inequality is allowed. Let \(L\) be the total input bit length, including \(\varepsilon\).
Can this additive approximation task be solved in time polynomial in \(m,\tau,L\), or is it NP-hard?
For a finite list of positively contributing agents, repeatedly reallocating each contribution among projects in proportion to the utility received from each project converges in objective value to the optimum from every initial allocation positive on every project; allocations also converge when the optimum is unique. [Brandl et al.](https://brandlf.com/docs/donate.pdf)
Arbitrary-precision computation by convex programming is also stated for that finite-agent problem, whose exact optima can be irrational; these statements give no explicit bound in input bit length and requested accuracy. [Brandl et al.](https://brandlf.com/docs/donate.pdf)
The additive approximation task is solvable in deterministic time polynomial in \(m,\tau,L\). The algorithm returns a rational allocation satisfying the budget constraint exactly.
The proof uses a rational restriction of the feasible region that contains every optimum and avoids all logarithmic singularities, followed by the finite-precision ellipsoid method.
Write \(A=\{1,\ldots,m\}\). Define
\(w_\theta=\mu_\theta c_\theta,\qquad p_\theta=w_\theta/V,\qquad M_\theta=\max_a u_\theta(a),\qquad b_{\theta a}=u_\theta(a)/M_\theta.\)
These are rational numbers of polynomial encoding length. The assumptions imply
\(p_\theta>0,\qquad \sum_\theta p_\theta=1,\qquad 0\le b_{\theta a}\le1,\qquad \max_a b_{\theta a}=1.\)
For an allocation, put \(x_a=\delta(a)/V\). Thus \(x\) belongs to the simplex
\(S=\{x\in\mathbb R_{\ge0}^m:\sum_a x_a=1\}.\)
Define
\(s_\theta(x)=\sum_a b_{\theta a}x_a,\qquad f(x)=\sum_\theta p_\theta\log s_\theta(x),\)
with \(f(x)=-\infty\) when some \(s_\theta(x)=0\). Whenever all utilities are positive,
\(F(Vx)=C+Vf(x),\qquad C=\sum_\theta w_\theta\log(VM_\theta).\)
Consequently, objective differences are multiplied by \(V\); the algorithm need not compute \(C\).
If \(m=1\), the unique allocation \(\delta(1)=V\) is optimal. Henceforth assume \(m\ge2\).
First, a finite optimum exists. The uniform point \(e=(1/m,\ldots,1/m)\) satisfies \(s_\theta(e)\ge1/m\), so \(f(e)\) is finite. The function \(f\) is upper semicontinuous on the compact simplex and is bounded above by zero. It therefore attains a finite maximum, and every maximizer has positive utility for every supported type.
Lemma. Every maximizer \(x^*\) satisfies \(s_\theta(x^*)\ge p_\theta\) for every \(\theta\).
Proof. Because all \(s_\theta(x^*)\) are positive, \(f\) is differentiable in a neighborhood of \(x^*\). Set
\(g_a=\sum_\theta p_\theta\,\frac{b_{\theta a}}{s_\theta(x^*)}.\)
For each project \(a\), the segment \((1-t)x^*+t e_a\), for \(0\le t\le1\), is feasible. Optimality implies that its right derivative at zero is nonpositive. This derivative equals
\(g_a-\sum_j x_j^*g_j=g_a-1,\)
where the last equality follows from
\(\sum_j x_j^*g_j=\sum_\theta p_\theta\,\frac{\sum_j b_{\theta j}x_j^*}{s_\theta(x^*)}=\sum_\theta p_\theta=1.\)
Thus \(g_a\le1\) for every \(a\). For a fixed type \(\theta\), choose \(a_\theta\) with \(b_{\theta a_\theta}=1\). Every summand defining \(g_{a_\theta}\) is nonnegative, so
\(\frac{p_\theta}{s_\theta(x^*)}\le g_{a_\theta}\le1.\)
This proves the lemma. \(\square\)
It follows that restricting optimization to the rational polytope
\(K=\{x\in S:s_\theta(x)\ge p_\theta/2\text{ for every }\theta\}\)
preserves every optimum.
Use \(d=m-1\) independent coordinates \(y=(x_1,\ldots,x_d)\), with \(x_m=1-\sum_{i=1}^d y_i\). Denote the corresponding polytope by \(K_y\). Its constraints are
\(y_i\ge0,\qquad \sum_{i=1}^d y_i\le1,\qquad b_{\theta m}+\sum_{i=1}^d(b_{\theta i}-b_{\theta m})y_i\ge p_\theta/2.\)
In particular, \(K_y\) is contained in the Euclidean unit ball centered at zero.
An interior point can be constructed explicitly. Using the projects \(a_\theta\) chosen above, let
\(x^0=\sum_\theta p_\theta e_{a_\theta},\qquad z=\tfrac12x^0+\tfrac12e.\)
Nonnegativity gives \(s_\theta(x^0)\ge p_\theta\). Hence
\(z_a\ge1/(2m),\qquad s_\theta(z)\ge p_\theta/2+1/(2m).\)
Let \(z_y\) be the first \(d\) coordinates of \(z\), and set
\(r_0=\frac{1}{4md}.\)
Then the closed Euclidean ball of radius \(r_0\) around \(z_y\) is contained in \(K_y\). Indeed, a perturbation of norm at most \(r_0\):
All these changes are at most \(1/(4m)\), smaller than the corresponding slacks above. Thus both the outer radius and an interior radius are explicit rational numbers of polynomial encoding length.
Write \(f_y(y)=f(x(y))\). On \(K_y\), this function is concave and differentiable, with
\(\frac{\partial f_y}{\partial y_i}(y)=\sum_\theta p_\theta\,\frac{b_{\theta i}-b_{\theta m}}{s_\theta(x(y))}.\)
At a rational feasible point, its gradient is exactly rational and computable in polynomial time.
Furthermore, \(s_\theta(x(y))\ge p_\theta/2\), so
\(\left|\frac{\partial f_y}{\partial y_i}(y)\right|\le\sum_\theta\frac{p_\theta}{s_\theta(x(y))}\le2\tau.\)
Therefore a valid Euclidean Lipschitz bound on \(K_y\) is
\(G=2d\tau.\)
This follows by integrating the gradient along any segment in the convex set \(K_y\). In particular, exponentially small masses do not cause an exponentially large Lipschitz bound.
The objective can also be evaluated to any positive rational absolute error \(\nu\) in time polynomial in the point’s encoding length, the input length, and \(\log(1/\nu)\). Here is an explicit justification.
For each positive rational argument \(q=s_\theta(x(y))\le1\), choose an integer \(k\ge0\) such that \(z'=2^kq\in[1,2)\). Then
\(\log q=\log z'-k\log2.\)
For \(1\le z'\le2\), put \(t=(z'-1)/(z'+1)\). The identity
\(\log z'=2\sum_{j=0}^{\infty}\frac{t^{2j+1}}{2j+1}\)
has \(0\le t\le1/3\). Truncating after \(N\) terms incurs error at most
\(2\sum_{j=N}^{\infty}(1/3)^{2j+1}=\tfrac34\,9^{-N}.\)
The same series computes \(\log2\), using \(t=1/3\). Thus polynomially many rational arithmetic operations suffice to approximate \(\log q\) within \(\nu\); the necessary number of terms is \(O(\log(1/\nu)+\log(k+1))\). All intermediate rational numbers have polynomial encoding length.
Approximating each logarithm within \(\nu\) and taking the exact weighted sum approximates \(f_y\) within \(\nu\), because \(\sum_\theta p_\theta=1\).
Finally, membership in \(K_y\), and separation when membership fails, use only its explicit rational linear inequalities.
We use the standard finite-precision central-cut ellipsoid theorem: starting with a containing ball, rational cuts through the queried centers can be processed while keeping centers and matrices of polynomial encoding length. Every fixed set retained by all cuts remains enclosed, and volume decreases by a factor at most \(\exp(-1/(5d))\) per step. Thus \(O(d^2\log(1/r))\) steps suffice to reduce volume below that of a radius-\(r\) ball. This is the rational implementation, including rounding, established in [Grötschel–Lovász–Schrijver, Chapter 3, Section 3.2](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf). For \(d=1\), exact interval bisection gives the corresponding statement.
Set
\(\eta=\min\{1,\varepsilon/V\},\qquad h=\eta/2.\)
Starting with the unit ball, process each rational ellipsoid center \(y\) as follows:
The last cut retains every point with objective at least \(f_y(y)\). Indeed, concavity gives
\(f_y(v)\le f_y(y)+\nabla f_y(y)^{\mathsf T}(v-y).\)
Nonzero cut vectors can be normalized to have infinity norm one using exact rational arithmetic.
We now prove that polynomially many such steps must record a point with objective at least \(f_y^*-h\), where \(f_y^*=\max_{K_y}f_y\).
Let \(y^*\) be a maximizer, and define
\(\lambda=\frac{h}{6G},\qquad \bar y=(1-\lambda)y^*+\lambda z_y,\qquad r=\lambda r_0=\frac{\eta}{96md^2\tau}.\)
Because \(0<\lambda<1\), convexity and the interior-ball property imply that the radius-\(r\) ball around \(\bar y\) lies in \(K_y\). More explicitly, any point in this ball has the form
\((1-\lambda)y^*+\lambda(z_y+v),\qquad \|v\|_2\le r_0.\)
Both \(z_y\) and \(y^*\) lie in the unit ball. Consequently, every point \(y'\) in this smaller ball satisfies
\(\|y'-y^*\|_2\le\lambda(2+r_0)\le3\lambda.\)
The Lipschitz bound therefore gives
\(f_y(y')\ge f_y^*-3G\lambda=f_y^*-h/2.\)
Suppose every recorded feasible center had objective strictly below \(f_y^*-h\). Every feasibility cut would retain this entire smaller ball. Every objective cut would also retain it, since its points have strictly higher objective than the queried center.
The ellipsoid theorem would then keep that ball enclosed throughout. After \(O(d^2\log(1/r))\) steps, however, the enclosing ellipsoid has smaller volume than the ball—a contradiction. Thus some recorded feasible center \(y_{\mathrm{good}}\) satisfies
\(f_y(y_{\mathrm{good}})\ge f_y^*-h.\)
The algorithm does not need to know \(f_y^*\); it uses only the prescribed number of steps and the stated oracles.
Evaluate the objective at every recorded feasible center within absolute error \(\eta/4\), and choose one, \(\widehat y\), with largest approximate value. Comparing it with \(y_{\mathrm{good}}\) yields
\(f_y(\widehat y)\ge f_y(y_{\mathrm{good}})-2(\eta/4)\ge f_y^*-\eta.\)
Reconstruct
\(\widehat x_i=\widehat y_i\text{ for }i\le d,\qquad \widehat x_m=1-\sum_{i=1}^d\widehat y_i,\qquad \widehat\delta(a)=V\widehat x_a.\)
Membership in \(K_y\) was checked exactly. Hence \(\widehat\delta\) is rational, nonnegative, and sums exactly to \(V\). Since restriction to \(K_y\) preserves the optimum,
\(\max_{\delta\in\Delta(V)}F(\delta)-F(\widehat\delta)=V\bigl(f_y^*-f_y(\widehat y)\bigr)\le V\eta\le\varepsilon.\)
All derived rational input data have polynomial encoding length. Moreover,
\(\log(1/r)=O\bigl(\log m+\log\tau+\log(1/\eta)\bigr),\)
and \(\log(1/\eta)\) is polynomially bounded by \(L\), because \(V\) and \(\varepsilon\) are positive rationals of polynomial encoding length. The ellipsoid method consequently makes polynomially many queries at rational points of polynomial encoding length. Each separation, gradient computation, and approximate objective evaluation takes polynomial time, and the output has polynomial encoding length.
All sums and constraints range over the \(\tau\) explicitly supported types. No expansion of rational masses into individual agents is used.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes a deterministic polynomial-time algorithm for the stated additive approximation task. The returned allocation is rational and satisfies the budget constraint exactly. I found no major or minor issues requiring repair.
The definitions of \(w_\theta\), \(p_\theta\), \(M_\theta\), and \(b_{\theta a}\) are valid: all denominators are positive by the task’s assumptions. Their rational encoding lengths are polynomial in the input length, including the encoding length of the sum defining \(V\).
The substitution \(\delta=Vx\) bijectively maps the simplex \(S\) to \(\Delta(V)\). Since \(U_\theta(Vx)=VM_\theta s_\theta(x)\), the identity \(F(Vx)=C+Vf(x)\) is correct whenever all supported utilities are positive. Thus the normalized accuracy must be scaled by \(V\), as the proof subsequently does.
The case \(m=1\) is correctly handled: the unique feasible allocation gives every supported type positive utility and is optimal.
The uniform allocation satisfies \(s_\theta(e)\ge 1/m\), because every normalized utility row contains an entry equal to one. Consequently, its objective is finite.
On the simplex, \(s_\theta(x)\le1\), so every logarithmic summand is nonpositive. The extended objective is upper semicontinuous, including at points where a supported utility vanishes. Compactness therefore gives an attained, finite maximum. No maximizer can have a zero supported utility.
The lemma’s derivative argument is valid even when a maximizer lies on the boundary of the simplex. Positive supported utilities provide a neighborhood where the objective is differentiable, and each segment toward a project vertex is feasible.
The calculation \(\sum_jx_j^*g_j=1\) is exact. Optimality along each such segment gives \(g_a\le1\). Choosing a project with \(b_{\theta a_\theta}=1\), and using nonnegativity of the other summands, correctly yields \(p_\theta/s_\theta(x^*)\le1\).
Hence every maximizer belongs to \(K\). Restricting to \(K\) preserves the maximum and every maximizer.
The coordinate representation of \(K_y\) is correct. Its coordinates are nonnegative and sum to at most one, so it lies in the Euclidean unit ball.
The proposed point \(x^0\) satisfies \(s_\theta(x^0)\ge p_\theta\): the contribution indexed by that same type already supplies \(p_\theta\), regardless of whether several types select the same project.
The resulting slack bounds for \(z\) are correct. For a perturbation of norm at most \(r_0=1/(4md)\):
These bounds are smaller than the stated coordinate and utility slacks. Thus the entire closed ball lies in \(K_y\). This establishes full dimensionality in the independent coordinates without assuming that an optimum itself is interior.
The gradient formula is correct. At rational feasible points, every utility denominator is positive, and exact rational gradient computation has polynomial bit complexity.
The component bound \(\left|\partial f_y/\partial y_i\right|\le2\tau\) follows from \(s_\theta\ge p_\theta/2\). Consequently, the Euclidean gradient norm is at most \(2\tau\sqrt d\le2d\tau=G\). Integrating along feasible segments justifies the stated Lipschitz bound.
The logarithm computation also checks out:
The rational series arithmetic has polynomial encoding length for the required number of terms. Since the positive weights sum to one, individual logarithm errors bounded by \(\nu\) produce total objective error bounded by \(\nu\).
Membership and separation use explicit rational inequalities and are exact.
The cited source supports the guarantees used. Its Section 3.2 establishes polynomial encoding lengths, preservation of the retained set, and the contraction factor \(\exp(-1/(5d))\); see Theorem 3.2.1 and Lemmas 3.2.8–3.2.10. [Grötschel–Lovász–Schrijver, Chapter 3](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf)
The application meets the relevant conditions: the initial unit ball contains the feasible region, cuts have rational nonzero normals that can be normalized, and the oracles run in polynomial time. The contradiction uses a fixed ball retained by every cut under the stated supposition. It does not incorrectly require objective cuts to retain all of \(K_y\). Exact interval bisection correctly covers \(d=1\).
A violated feasibility inequality supplies a central halfspace containing \(K_y\). For objective cuts, the concavity inequality has the correct orientation: every point with objective at least that of the queried center lies in the retained halfspace.
A zero gradient at a feasible center correctly certifies global optimality on \(K_y\).
The parameters satisfy \(0<\eta\le1\), \(h=\eta/2\), and \(0<\lambda=h/(6G)<1\).
The radius calculation is correct: \(r=\lambda r_0=\eta/(96md^2\tau)\). Convexity places the entire smaller ball inside \(K_y\).
Its points are at distance at most \(3\lambda\) from \(y^*\), so the Lipschitz estimate gives objective at least \(f_y^*-h/2\).
If every recorded center had objective strictly below \(f_y^*-h\), both feasibility and objective cuts would retain this entire ball. The stated ellipsoid contraction would eventually make the enclosing volume smaller than the ball’s volume, a contradiction. Therefore a recorded center achieves objective at least \(f_y^*-h\). This argument also ensures that the list of recorded feasible centers is nonempty.
The algorithm needs neither the optimum value nor the location of the ball to carry out its prescribed iterations.
Selecting the largest approximate objective, with each evaluation error at most \(\eta/4\), loses at most \(\eta/2\) relative to the good recorded center. Combined with \(h=\eta/2\), this gives normalized error at most \(\eta\).
Exact membership ensures that the reconstructed allocation is nonnegative and sums exactly to \(V\). Scaling the objective gap yields \(V\eta\le\varepsilon\), including the case \(\varepsilon\ge V\).
The iteration bound depends polynomially on \(d\) and \(\log(1/r)\). Both \(V\) and \(\varepsilon\) have polynomial encoding length, so \(\log(1/\eta)\) is polynomially bounded by \(L\). The cited rational ellipsoid implementation and the verified oracles therefore give polynomial total running time and output length.
All computations use only the explicitly supported types. No expansion into individual agents is required.
No additional lemma, correction, or clarification is needed to verify the claimed result.
⟨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.