Answer: \(\mathrm{NP}\text{-hard}\), even with exact affine resource-payoffs, one supported type, and inverse-polynomial accuracy. A general singly exponential computational upper bound uses one learner call at accuracy \(\epsilon/[4(1+2\Lambda)]\) and failure probability \(\delta\), with no additional samples.
Theorem 3.5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume W : 𝑺× (𝑺→R|𝑃|) →R is a 𝜆W-Lipschitz property. It holds that MDΛ(𝒖) is 𝜆W + 2Λ-Lipschitz, which immediately implies that |MDΛ(𝒖) −MDΛ(𝒖′)| ≤(𝜆W + 2Λ)𝜀. Likewise, for MCΛ(𝒖). It also holds that MD∗ Λ(𝒖) is 𝜆W + 4Λ-Lipschitz, which immediately implies that MD∗ Λ(𝒖) −MDΛ(𝒖′) ≤(𝜆W + 4Λ)𝜀.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type and action sets \(\Theta\) and \(A\), rational masses \(\mu\), rational \(\Lambda\), \(\varepsilon\), and \(\delta\), and a succinct continuous anonymous congestion payoff representation \(U_\theta(a,x)\) with a simulator producing \(\hat U\) satisfying \(\sup_{\theta,a,x}|\widehat U_\theta(a,x)-U_\theta(a,x)| \le \eta\) with probability \(1-\delta\), compute \(x \in X_\mu=\{x \ge 0:\Sigma_a x_{\theta,a}=\mu_\theta\}\) and \(z\) such that \(W_\mu(x)+\Lambda R_\mu(x) \le \inf_{y \in X_\mu}(W_\mu(y)+\Lambda R_\mu(y))+\varepsilon\) and \(|z-\inf_{y \in X_\mu}(W_\mu(y)+\Lambda R_\mu(y))| \le \varepsilon\), with time and sample complexity as the targets.
A society is given by its support: the list \(\Theta\) of \(\tau\) types with positive binary-rational masses \(\mu_\theta\), with \(\sum_\theta\mu_\theta=1\); \(\tau\) is the support size, not the number of possible types. Let \(A\) be a nonempty list of \(m\) actions and \(X_\mu=\{x\geq0:\sum_{a\in A}x_{\theta,a}=\mu_\theta\}\).
There are \(r\) resources, and each action specifies a resource subset \(E_a\). Write \(\ell_e(x)=\sum_{\theta,a:e\in E_a}x_{\theta,a}\) and \(U_\theta(a,x)=\sum_{e\in E_a}g_{\theta,e}(\ell_e(x))\), where the unknown resource-payoff functions are continuous and utilities lie in \([-1,1]\); no monotonicity is assumed.
An individual is nonatomic: changing action leaves loads fixed. Define \(W_\mu(x)=\sum_{\theta,a}x_{\theta,a}U_\theta(a,x)\) and \(R_\mu(x)=\max_{\theta,a:x_{\theta,a}>0}\bigl(\max_{b\in A}U_\theta(b,x)-U_\theta(a,x)\bigr)\). Ties are allowed, and the current action is an allowed deviation.
The supplied learning routine, requested at rational accuracy \(\eta>0\) and failure probability \(\beta\in(0,1)\), returns resource-payoff circuits using rational constants and \(+, -, \times, \min, \max\), inducing \(\widehat U\) with \(\sup_{\theta,a,x\in X_\mu}|\widehat U_\theta(a,x)-U_\theta(a,x)|\leq\eta\) with probability at least \(1-\beta\). Denote its time and sample costs by \(T_{\rm learn}(\eta,\beta)\) and \(N_{\rm learn}(\eta,\beta)\); \(L\) includes input and returned-circuit encoding lengths.
Given rational \(\Lambda\geq0\), \(\epsilon>0\), and \(\delta\in(0,1)\), compute rational \(x\in X_\mu\) and \(z\) such that, with probability at least \(1-\delta\), \(F(x)\leq v+\epsilon\) and \(|z-v|\leq\epsilon\), where \(F=W_\mu+\Lambda R_\mu\) and \(v=\inf_{y\in X_\mu}F(y)\).
Is this additive-approximation problem solvable with additional computation polynomial in \(m,\tau,r,L,1/\epsilon,1+\Lambda,\log(1/\delta)\), or is it NP-hard even for exact utilities and inverse-polynomial \(\epsilon\)?
What are its total time and sample complexities in these parameters and the supplied learning costs \(T_{\rm learn}\) and \(N_{\rm learn}\)?
For finite normal-form games, the penalized minimum with utilitarian welfare is \((1+2\Lambda)\)-Lipschitz in utilities; this establishes estimation stability, not a polynomial-time optimizer. [Source](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p272.pdf)
No result settling this precise nonatomic computational problem was located in the literature search.
The problem is NP-hard even with exact affine resource-payoffs, one supported type, and inverse-polynomial accuracy. Thus estimation stability does not yield a polynomial-time optimizer.
A general algorithm using the supplied learner and existential real feasibility has the following upper bounds. Set \(\eta=\epsilon/[4(1+2\Lambda)]\). Then
\[ \text{Time}\ \leq\ T_{\rm learn}(\eta,\delta) + 2^{\operatorname{poly}(m,\tau,r,L,\log(2+1/\epsilon),\log(2+\Lambda))}, \]
\[ \text{Samples}\ =\ N_{\rm learn}(\eta,\delta). \]
These are upper bounds, not claims of optimal running time. Under the standard explicit binary encoding of the returned rationals, succinct circuits can also force superpolynomial output length, independently of complexity-class assumptions.
Let \(G=(V,E)\) be a simple undirected graph with \(n\) vertices. Construct a society with one type of mass \(1\), and one action for each vertex. Write \(x_i\) for the mass choosing vertex \(i\); thus \(x_i\geq 0\) and \(\sum_i x_i=1\).
For each edge \(\{i,j\}\), introduce a resource used by actions \(i\) and \(j\), with payoff \(g_{\{i,j\}}(t)=-t\). For each vertex \(i\), introduce a private resource used only by action \(i\), with payoff \(g_i(t)=d_i t\), where \(d_i\) is its degree.
All payoffs are affine with integer coefficients. The resulting action utility is
\[ U(i,x) = d_i x_i-\sum_{j:\{i,j\}\in E}(x_i+x_j) = -\sum_{j:\{i,j\}\in E}x_j. \]
Consequently, every action utility lies in \([-1,0]\), as required. The construction has \(m=n\), \(\tau=1\), and \(r=n+|E|\), with polynomial encoding length.
Take \(\Lambda=0\). Then
\[ F(x)=W(x)=-2\sum_{\{i,j\}\in E}x_i x_j. \]
We now prove its minimum exactly.
Let \(\omega(G)\) denote the maximum clique size, and define \(Q(x)=2\sum_{\{i,j\}\in E}x_i x_j\). Then
\[ \max_{x\geq0,\ \sum_i x_i=1}Q(x)=1-\frac1{\omega(G)}. \]
To prove the upper bound, suppose two nonadjacent vertices \(i,j\) both have positive mass. With all other coordinates fixed, write
\[ Q(x)=Q_{\rm rest}+2x_i A_i+2x_j A_j, \qquad A_i=\sum_{h:\{i,h\}\in E}x_h, \quad A_j=\sum_{h:\{j,h\}\in E}x_h. \]
Because \(i,j\) are nonadjacent, neither \(A_i\) nor \(A_j\) depends on \(x_i,x_j\). Moving their combined mass to whichever vertex has the larger \(A\)-value cannot decrease \(Q\), and removes a positive coordinate.
Repeating this operation produces a distribution supported on a clique of some size \(k\leq\omega(G)\). On that support,
\[ Q(x)=1-\sum_i x_i^2 \leq 1-\frac1k \leq 1-\frac1{\omega(G)}, \]
where the first inequality follows from \((\sum_i x_i)^2\leq k\sum_i x_i^2\). Since the merging operations never decrease \(Q\), this bounds the original distribution as well.
Conversely, the uniform distribution on a maximum clique achieves \(1-1/\omega(G)\). Hence
\[ v=-1+\frac1{\omega(G)}. \]
Consider CLIQUE with threshold \(2\leq k\leq n\). In a yes-instance,
\[ v\leq a:=-1+\frac1k; \]
in a no-instance,
\[ v\geq b:=-1+\frac1{k-1}. \]
The separation is
\[ b-a=\frac1{k(k-1)}\geq\frac1{n^2}. \]
Choose \(\epsilon=1/(8n^2)\). Any output satisfying \(|z-v|\leq\epsilon\) distinguishes the cases by comparison with \((a+b)/2\).
The restricted CLIQUE problem used here is NP-hard: the usual reduction from a formula with \(q\) clauses creates vertices for literal occurrences and joins occurrences from different clauses exactly when they are not complementary. A clique of size \(q\) selects mutually consistent literals satisfying every clause; a satisfying assignment supplies such a selection.
Thus the requested approximation problem is NP-hard.
This reduction also works with the strictly positive choice \(\Lambda=1/(8n^2)\). Indeed, the constructed utilities give \(0\leq R(x)\leq1\), so its penalized value satisfies
\[ v_0\leq v_\Lambda\leq v_0+\Lambda. \]
The yes/no value intervals remain disjoint after allowing the stated approximation error.
For randomized algorithms, the usual qualification matters. A polynomial-time algorithm satisfying the requested probability guarantee would imply \(\mathrm{NP}\subseteq\mathrm{RP}\): run it with \(\delta=1/4\), validate feasibility of \(x\), and accept exactly when its affine-instance welfare is below \((a+b)/2\). No-instance distributions can never pass this test, while a successful output on a yes-instance does pass.
Define the occupied support by \(S(x)=\{(\theta,a):x_{\theta,a}>0\}\). Since every type has positive mass and the action list is nonempty, \(S(x)\) is nonempty.
Although regret need not be continuous, it is lower semicontinuous. To see this, let \(x^{(j)}\to x\). Every coordinate positive at \(x\) is eventually positive at \(x^{(j)}\). Therefore, eventually,
\[ R_\mu(x^{(j)}) \geq \max_{\substack{(\theta,a)\in S(x)\\b\in A}} \bigl(U_\theta(b,x^{(j)})-U_\theta(a,x^{(j)})\bigr). \]
The right-hand side converges to \(R_\mu(x)\), because it is a finite maximum of continuous functions. Welfare is continuous, so \(F\) is lower semicontinuous for \(\Lambda\geq0\). The feasible set is compact; consequently, the infimum \(v\) is attained.
Next, suppose two utility systems \(U,V\) differ uniformly by at most \(\eta\). Their welfare values at a fixed distribution differ by at most
\[ \sum_{\theta,a}x_{\theta,a}\eta=\eta. \]
Every deviation difference changes by at most \(2\eta\). Taking maxima over the same occupied support therefore gives \(|R_U(x)-R_V(x)|\leq2\eta\). Writing \(C=1+2\Lambda\), we obtain
\[ |F_U(x)-F_V(x)|\leq C\eta, \qquad |v_U-v_V|\leq C\eta. \]
The second inequality follows by taking infima in both directions. This directly proves stability for the stated nonatomic objective. The [supplied paper](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p272.pdf) studies the related utility-stability principle for finite games.
If an optimizer for the estimated objective returns \(x\) with \(F_V(x)\leq v_V+\gamma\), then
\[ F_U(x)\leq v_U+\gamma+2C\eta. \]
The factor \(2C\eta\) accounts separately for estimation at the returned distribution and estimation of the optimal value.
Call the learner once at accuracy \(\eta=\epsilon/(4C)\) and failure probability \(\delta\). Clip each returned action utility to obtain
\[ \widetilde U_\theta(a,x) = \max\{-1,\min\{1,\widehat U_\theta(a,x)\}\}. \]
Clipping preserves the uniform error guarantee because the true utilities lie in \([-1,1]\). It also ensures bounded estimated utilities on every learner outcome. Let \(\widetilde F\) and \(\widetilde v\) denote the corresponding objective and minimum.
We construct rational \(y,z\) satisfying
\[ \widetilde F(y)\leq\widetilde v+\frac{\epsilon}{2}, \qquad |z-\widetilde v|\leq\frac{\epsilon}{4}. \]
For rational \(t\), consider the question whether some \(x\in X_\mu\) satisfies \(\widetilde F(x)\leq t\).
Introduce variables for loads, circuit gates, utilities \(u_{\theta,a}\), and a regret bound \(\rho\). A multiplication gate is represented by an equation of degree two. A maximum gate \(h=\max(p,q)\) is represented by
\[ h\geq p,\qquad h\geq q,\qquad (h=p\ \text{or}\ h=q), \]
and a minimum gate is represented analogously.
Add feasibility constraints, \(0\leq\rho\leq2\), and, for every \(\theta,a,b\),
\[ x_{\theta,a}=0 \quad\text{or}\quad u_{\theta,b}-u_{\theta,a}\leq\rho. \]
Finally add
\[ \sum_{\theta,a}x_{\theta,a}u_{\theta,a}+\Lambda\rho\leq t. \]
This existential formula is equivalent to the threshold question. In one direction, its constraints imply \(\rho\geq\widetilde R(x)\), and \(\Lambda\geq0\). In the other direction, choose \(\rho=\widetilde R(x)\).
The formula has polynomially many variables and polynomial predicates, all of degree at most two. Circuit intermediate values remain variables, so expanding high-degree circuit polynomials is unnecessary.
We use the standard existential real decision theorem: a Boolean formula involving \(s\) integer polynomials of degree at most \(d\) in \(k\) variables can be decided in \((sd)^{O(k)}\operatorname{poly}(B)\) bit operations, where \(B\) bounds coefficient bit lengths. Rational coefficients are cleared first. These arithmetic and bit bounds follow from the one-block case of Theorem 2.18 in [Basu’s survey](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf).
All hypotheses hold here: there is one existential block, rational coefficients, and bounded polynomial degree.
Because clipped utilities lie in \([-1,1]\),
\[ -1\leq\widetilde F(x)\leq1+2\Lambda. \]
Use threshold feasibility to bisect this interval. Maintain endpoints \(a,b\) with \(a\leq\widetilde v\leq b\) and with the upper threshold \(b\) feasible. A feasible midpoint replaces \(b\); an infeasible midpoint replaces \(a\).
Stop when \(b-a\leq\epsilon/4\). Then
\[ \widetilde v\leq b\leq\widetilde v+\frac{\epsilon}{4}, \]
and the formula \(\widetilde F(x)\leq b\) remains feasible. Set \(z=b\).
The returned circuits admit an effectively computable common constant \(K\) such that
\[ |\widetilde U_\theta(a,x)-\widetilde U_\theta(a,y)| \leq K\|x-y\|_1. \]
Here is an explicit way to compute it. For each resource circuit on load interval \([0,1]\), propagate an absolute-value bound \(M\) and a Lipschitz bound \(K_g\). Constants have Lipschitz bound zero; the input load has bounds \(M=K_g=1\). Addition and subtraction use sums of bounds. Multiplication uses
\[ M=M_1M_2, \qquad K_g=M_1K_2+M_2K_1. \]
For minimum and maximum gates, use \(M=\max(M_1,M_2)\) and \(K_g=\max(K_1,K_2)\). Loads change by at most \(\|x-y\|_1\); summing the resource bounds for each action and then clipping establishes the claimed \(K\).
These bounds can be large, but their bit lengths are at most singly exponential in circuit encoding length. Indeed, each gate increases the logarithm of the combined magnitude and Lipschitz bound by at most a constant plus twice the preceding maximum.
Let \(H=1+CK\). Whenever \(S(y)\subseteq S(x)\), we have
\[ \widetilde F(y)\leq\widetilde F(x)+H\|y-x\|_1. \]
For welfare, the absolute change is at most \((1+K)\|y-x\|_1\), by splitting the change into distribution weights and utility values. For regret, support containment ensures that every occupied action at \(y\) is also available in the regret maximum at \(x\). Its deviation difference changes by at most \(2K\|y-x\|_1\). Combining these bounds proves the inequality.
Start with the feasible formula \(\widetilde F(x)\leq b\). For each coordinate, test whether adding \(x_{\theta,a}=0\) preserves feasibility. If so, retain that equality; otherwise retain \(x_{\theta,a}>0\). Each step preserves feasibility. At the end, every feasible point of the retained formula has the same occupied support.
If \(m=1\), the distribution is uniquely determined by the masses, and no rounding is needed. Otherwise let \(D=\tau(m-1)\), and choose a positive rational \(h\) with
\[ h\leq\frac{\epsilon}{8DH}. \]
For each positive coordinate, use feasibility queries to bisect its interval \([0,\mu_\theta]\) until the retained interval has width at most \(h\). Always retain a half for which the current formula remains feasible. Thus all final intervals have a common feasible point \(w\), although the algorithm need not calculate it.
For each type, choose an action \(a_\theta^\ast\) in the retained positive support. For every other action, set \(y_{\theta,a}\) to its interval’s rational lower endpoint, using zero for inactive actions. Set the remaining coordinate to
\[ y_{\theta,a_\theta^\ast} = \mu_\theta-\sum_{a\ne a_\theta^\ast}y_{\theta,a}. \]
Each lower endpoint is nonnegative and at most the corresponding coordinate of \(w\). Hence \(y\) is feasible, and its occupied support is contained in that of \(w\).
For each type, the increase in the remaining coordinate equals the sum of decreases in the other coordinates. Therefore
\[ \|y-w\|_1\leq2\tau(m-1)h=2Dh. \]
The preceding support-sensitive bound now gives
\[ \widetilde F(y) \leq\widetilde F(w)+2DHh \leq b+\frac{\epsilon}{4} \leq\widetilde v+\frac{\epsilon}{2}. \]
This proves the claimed estimated-objective guarantees with rational outputs.
On the learner’s uniform-accuracy event,
\[ F(y) \leq \widetilde v+\frac{\epsilon}{2}+C\eta \leq v+\frac{\epsilon}{2}+2C\eta = v+\epsilon. \]
Also,
\[ |z-v| \leq |z-\widetilde v|+|\widetilde v-v| \leq\frac{\epsilon}{4}+C\eta =\frac{\epsilon}{2}. \]
Thus both requested conclusions hold with probability at least \(1-\delta\).
Let \(S=1+L+\tau m^2+\tau mr\). The existential formulas above have \(O(S)\) variables and predicates of degree at most two.
The computed continuity bounds have bit lengths at most \(2^{O(S)}\). Consequently, the coordinate bisections require at most singly exponentially many queries and produce endpoints with at most singly exponential bit length. Each query is decidable in singly exponential time by the stated existential real theorem, whose dependence on coefficient bit length is polynomial.
This establishes the general bounds
\[ T_{\rm total} \leq T_{\rm learn}\!\left(\frac{\epsilon}{4(1+2\Lambda)},\delta\right) + 2^{\operatorname{poly}(m,\tau,r,L,\log(2+1/\epsilon),\log(2+\Lambda))}, \]
\[ N_{\rm total} = N_{\rm learn}\!\left(\frac{\epsilon}{4(1+2\Lambda)},\delta\right). \]
The additional computation is deterministic and uses no further samples. The NP-hardness construction itself uses exact circuits and requires no learning samples.
There is also an unconditional obstruction to polynomial total time under explicit binary rational output.
Take one type of mass \(1\), two actions, and two private resources. For an integer \(s\geq2\), circuits of size \(O(s)\) gates generate
\[ C=2^{2^s}, \qquad a=2^{-2^s}, \]
by repeated squaring of \(2\) and \(1/2\). Let action one have utility zero, and let action two’s resource payoff be
\[ g(t)=-\max\{0,\ 1-2C|t-(1-a)|\}, \]
where absolute value is implemented by a maximum. These utilities lie in \([-1,0]\).
Write \(x\) for action one’s mass and put
\[ h(x)=\max\{0,\ 1-2C|x-a|\}. \]
With the fixed choice \(\Lambda=1/2\), the objective is
\[ F(x)=(x-\tfrac12)h(x). \]
For interior distributions this follows because action two has regret \(h(x)\) and action one has regret zero. At both endpoints \(h(x)=0\), so the formula holds there as well.
At \(x=a\), we obtain \(F(a)=a-1/2\leq-7/16\). Choose inverse-polynomial accuracy \(\epsilon=1/(s+8)\). Every successful output must have negative objective, hence \(h(x)>0\). Therefore
\[ \frac a2<x<\frac{3a}{2}. \]
If the returned rational is \(x=p/q>0\), with positive integers \(p,q\), then \(x\geq1/q\). Consequently,
\[ q>\frac{2}{3a}=\frac23\,2^{2^s}. \]
Its denominator requires more than \(2^s-1\) binary digits. The circuit input has encoding length \(O(s\log s)\), while \(1/\epsilon=O(s)\). Thus successful explicit rational outputs can require superpolynomial length even with fixed \(m,\tau,r,\Lambda\).
The NP-hardness proof already applies to simple affine circuits; this separate construction explains why arbitrary succinct circuits introduce an additional output-size obstruction.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The NP-hardness reduction is correct, the learning guarantee transfers correctly to the true objective, and the rational-output algorithm supports the stated singly exponential upper bound. I found no major or minor mathematical issues requiring repair.
1. Scope and admissibility of the hardness construction
The construction satisfies the task’s input restrictions:
The cancellation of the private-resource contribution against the edge-resource contributions is correct. Summing action utilities with weights \(x_i\) counts each undirected edge twice, giving \(W(x)=-2\sum_{\{i,j\}\in E}x_ix_j\).
Choosing \(\Lambda=0\) is expressly permitted by the task. The hardness argument therefore addresses the intended problem without relying on an unintended interpretation.
2. Verification of the clique identity
The support-merging argument is valid.
For nonadjacent occupied vertices \(i,j\), the displayed quantities \(A_i,A_j\) are independent of both coordinates being merged. Consequently, assigning their combined mass to the vertex with the larger coefficient cannot decrease \(Q\).
Each operation removes one positive coordinate. Thus the procedure terminates, and termination means that every pair of remaining occupied vertices is adjacent. The resulting support is a clique.
On a clique of size \(k\), the identity \(Q(x)=1-\sum_i x_i^2\) is correct. The stated inequality gives \(Q(x)\leq1-1/k\), and \(k\leq\omega(G)\) implies \(1-1/k\leq1-1/\omega(G)\). Because the merging operations increase or preserve \(Q\), this also bounds the original distribution.
The uniform distribution on a maximum clique attains the bound. Hence the stated optimum \(v=-1+1/\omega(G)\) follows exactly.
This also covers edgeless nonempty graphs: their maximum clique size is \(1\), and the optimum is \(0\).
3. Approximation gap and complexity consequence
For \(2\leq k\leq n\), the yes/no bounds and their separation are correct:
\(b-a=1/[k(k-1)]\geq1/n^2\).
The chosen accuracy \(\epsilon=1/(8n^2)\) is strictly smaller than half this separation. Therefore a successful value estimate distinguishes the cases using the stated midpoint.
The described clause-to-clique reduction correctly explains the restricted CLIQUE problem’s hardness: a clique selecting one occurrence from every clause corresponds to mutually consistent satisfying literals, and conversely.
The extension to strictly positive \(\Lambda=1/(8n^2)\) is also sound. Since \(0\leq R(x)\leq1\), the penalized optimum lies between \(v_0\) and \(v_0+\Lambda\). Allowing both this shift and the approximation error still leaves disjoint yes/no intervals.
The randomized qualification is appropriately stronger than a two-sided-error conclusion. On a no-instance, every feasible distribution has welfare at least \(b\), so none can pass the proposed acceptance test. On a successful yes-instance run, the returned welfare lies below the midpoint. Feasibility and welfare can be checked exactly for these affine instances. Thus the stated implication \(\mathrm{NP}\subseteq\mathrm{RP}\) is justified.
4. Attainment and estimation stability
The lower-semicontinuity argument handles the discontinuity caused by occupied support correctly.
Every coordinate positive at a limit point remains positive eventually along a convergent sequence. Since there are finitely many such coordinates, one eventual index works for all of them. The resulting finite maximum of continuous deviation differences converges to the limit point’s regret, establishing the required lower-semicontinuity inequality.
The feasible set is nonempty and compact. Welfare is continuous, and multiplication of regret by \(\Lambda\geq0\) preserves lower semicontinuity. Therefore the infimum is attained, including when \(\Lambda=0\).
The utility-error constants are correct:
Thus both the objective and its infimum change by at most \(C\eta\), where \(C=1+2\Lambda\). The optimizer-transfer inequality correctly includes two separate estimation errors, totaling \(2C\eta\).
The cited finite-game paper is used only for context. It does discuss utility stability and penalized welfare, while the nonatomic stability assertion is proved independently in this output. [Learning Properties in Simulation-Based Games](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p272.pdf)
5. Existential-real threshold formulation
Clipping preserves the approximation guarantee and ensures utility bounds on every learner outcome. Its implementation uses allowed circuit operations.
The threshold formula correctly represents the clipped objective:
Conversely, choosing \(\rho\) equal to actual regret supplies the necessary witness. The threshold equivalence therefore holds, including when \(\Lambda=0\).
All predicates have degree at most two. Introducing gate variables avoids expanding circuit polynomials.
The cited Theorem 2.18 provides singly exponential arithmetic complexity for one quantified block and bounds intermediate integer bit lengths. Together these support the stated bit-operation bound. Clearing rational denominators is legitimate; the formulas here have polynomial description size and fixed degree, and strict support inequalities are allowed Boolean polynomial predicates. [Basu, Theorem 2.18](https://www.math.purdue.edu/~sbasu/raag_survey2011_final.pdf)
6. Value bisection and rational distribution output
The initial value interval is valid because welfare lies in \([-1,1]\) and regret lies in \([0,2]\). Its upper endpoint is feasible. Threshold bisection preserves the stated invariants, including when a midpoint equals the optimum.
The circuit-bound propagation rules are correct for addition, subtraction, multiplication, minimum, and maximum. Resource loads belong to \([0,1]\), and their changes are bounded by the distribution’s \(1\)-norm difference. Summation and clipping therefore yield the claimed common utility Lipschitz bound.
The welfare estimate uses the bounded utilities and their Lipschitz constant correctly. The regret estimate requires only \(S(y)\subseteq S(x)\): dropping occupied actions cannot introduce a larger support maximum, and changes to deviation differences are bounded by \(2K\|y-x\|_1\). The resulting constant \(H=1+(1+2\Lambda)K\) is correct.
The support-selection queries preserve feasibility at every stage. If adding a zero-coordinate equality is infeasible, nonnegativity means every remaining witness has that coordinate strictly positive.
Coordinate bisection retains a single jointly feasible formula, so the final intervals share a feasible witness. Their lower endpoints do not exceed that witness’s coordinates. Assigning the remaining mass to one retained positive action consequently produces a feasible rational distribution with contained support.
The distance bound \(\|y-w\|_1\leq2\tau(m-1)h\) is correct: each type’s residual-coordinate increase equals the sum of the other decreases. The chosen bound on \(h\) gives exactly the required additional objective error. The separate \(m=1\) case avoids division by zero and has a uniquely determined rational distribution.
7. Probability, time, and sample accounting
With \(\eta=\epsilon/[4(1+2\Lambda)]\), the final objective error is at most \(\epsilon\). The value-estimation error is at most \(\epsilon/2\), which is stronger than requested.
Both conclusions hold on the same learner event. One call with failure probability \(\delta\) therefore suffices; no union bound or additional learning calls are needed.
The continuity bounds can have singly exponential bit length. This yields singly exponentially many coordinate queries and singly exponential endpoint bit lengths. Polynomial dependence on coefficient bit length in each feasibility query preserves the overall singly exponential bound.
The stated total time and sample expressions consequently follow. They are valid upper bounds; the output explicitly avoids claiming optimality.
8. Explicit-output length obstruction
The repeated-squaring circuits generate the stated reciprocal constants with the claimed succinct encoding. The tent payoff is continuous and stays in \([-1,0]\).
For interior distributions, the welfare and regret expressions give \(F(x)=(x-\tfrac12)h(x)\). At both endpoints the tent value is zero, so the same expression remains valid there.
For \(s\geq2\), \(a\leq1/16\), hence \(F(a)\leq-7/16\). The chosen accuracy is at most \(1/10\), so every successful output must have negative objective. This forces positive tent value and thus \(a/2<x<3a/2\).
The denominator estimate follows correctly from \(p\geq1\): any explicit positive rational \(p/q\) in this interval requires \(q>(2/3)2^{2^s}\). The claimed binary-length lower bound and superpolynomial comparison with the circuit encoding length are valid.
No additional clarification is necessary to verify the conclusions.
⟨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.