GPT 6 Astra Ultra attempt on Econ-145
economicscomputer scienceEconomics cataloguecontributionexplorationClaim: exploration
Reported by the author as unresolved.
Manuscript
Contents
Exact equilibria on tree potentials and the limits of payoff residuals
Status: Unresolved. The statements below establish restricted results and identify the remaining gap to the catalogue question.Abstract
We solve strong equilibrium approximation exactly for potentials supplied as sums of pairwise terms on a tree, and extend the argument to a supplied bounded-width tree decomposition. A separate quantitative lemma converts residual to distance under uniform dominance. A one-player example shows why an unqualified residual guarantee does not solve the catalogue's general strong-approximation problem. No completeness classification is obtained.Short target and representation
The catalogue asks whether strong approximation of a Nash equilibrium in a general concise potential game is $\mathsf{FIXP}_a\cap\mathsf{PLS}$-complete under its specified reductions. Strong approximation asks for distance to an actual equilibrium. Here players have finite explicit action sets $A_i$, and a rational exact potential satisfies \[ u_i(b_i,a_{-i})-u_i(a_i,a_{-i}) =\Phi(b_i,a_{-i})-\Phi(a_i,a_{-i}). \] Our algorithmic subcase supplies a tree $T$ and rational tables \[ \Phi(a)=\sum_i f_i(a_i)+\sum_{\{i,j\}\in T}f_{ij}(a_i,a_j). \] The input is these tables, not an arbitrary multilinear circuit. A pure profile maximizing $\Phi$ is an exact Nash equilibrium because no unilateral deviation can increase the potential or the corresponding payoff.A polynomial exact algorithm on trees
Root the tree at $r$. For each child $i$ of $j$ define a message for every $a_j\in A_j$ by \[ M_{i\to j}(a_j)=\max_{a_i\in A_i} \left[f_i(a_i)+f_{ij}(a_i,a_j) +\sum_{k\text{ child of }i}M_{k\to i}(a_i)\right]. \] Store an attaining action for each message entry. At the root maximize $f_r(a_r)+\sum_{k\text{ child of }r}M_{k\to r}(a_r)$, and recover child choices recursively from the stored maximizers.Theorem (Exact strong approximation on a tree): This procedure returns a global maximizer of $\Phi$ and hence an exact pure Nash equilibrium. With precomputed child sums, it takes \[
O\left(\sum_i|A_i|+\sum_{\{i,j\}\in T}|A_i||A_j|\right)
\] arithmetic operations and polynomial bit complexity in the table encoding. It therefore solves strong approximation for every positive binary-encoded $\varepsilon$, without dependence on $1/\varepsilon$.
Proof: Condition on the parent's action. Removing the parent edge separates the descendant subtrees, and their only shared variable is the current node's action. Induction from leaves proves that each message is exactly the best sum of all unary and edge terms below that edge, including the edge itself. At the root the same decomposition gives the global optimum. Stored maximizers attain each conditional optimum, so backtracking yields a profile with that value. The exact-potential identity proves Nash optimality.
Each edge table is scanned once after computing the child sums. Computing all such sums takes at most $\sum_{\{i,j\}\in T}(|A_i|+|A_j|)$ additions, which is bounded by a constant times the displayed expression. A dynamic-programming value is a sum of at most $2n-1$ input entries. If input numerators and denominators have at most $L$ bits, a common denominator can be their product, giving $O(nL+\log n)$ bits for these sums, up to the table-wide encoding bound. Comparisons and additions consequently have polynomial bit cost. The output probabilities are zeros and ones, and their distance to the equilibrium set is zero. ∎
Corollary (A supplied tree decomposition): Suppose $\Phi$ is a sum of explicit finite-scope rational factors, with a supplied tree decomposition of width $w$ containing every factor scope in some bag, and let $a=\max_i|A_i|$. Global maximization, and hence exact pure equilibrium, takes $O(Ba^{w+1})$ table operations after factors are assigned to bags, with an additional polynomial factor for input summation. Here $B$ is the number of bags.
Proof: Assign each factor to one containing bag. A message across a tree edge records the optimum on the child side conditional on the separator assignment. For each child bag, enumerate its at most $a^{w+1}$ assignments, add its assigned factors and child messages, and maximize over the variables absent from its parent separator. The running-intersection property makes the separated descendant interiors disjoint and forbids a factor from linking them without passing through the separator. The preceding induction therefore applies. Backtracking gives the maximizing assignment. Rational sums have the same polynomial bit bound in the full input size. ∎
The width or factorization is extra input structure. Nothing here extracts such a decomposition from a general concise potential circuit, and the bound is exponential in unbounded $w$. When residual does control distance
For a mixed profile $x$, let $r_i(x)=\max_{a_i}u_i(a_i,x_{-i})-u_i(x)$. Distance is the maximum absolute difference between action probabilities over all players and actions.Proposition (A sharp dominance conversion): Suppose each player has an action $a_i^*$ and a number $\gamma_i>0$ such that \[
u_i(a_i^*,a_{-i})-u_i(b_i,a_{-i})\ge\gamma_i
\quad\text{for all }b_i\ne a_i^*,\ a_{-i}.
\] Then the unique Nash equilibrium is the pure profile $a^*$. If $r_i(x)\le\delta$ for all $i$, then \[
\|x-a^*\|_\infty\le
\min\{1,\delta/\min_i\gamma_i\}.
\] The coefficient $1/\gamma_i$ cannot be improved uniformly.
Proof: Averaging the dominance inequality over opponents preserves the gap. Every best response is therefore the single action $a_i^*$, proving uniqueness. The payoff gain from replacing $x_i$ by $a_i^*$ is at least $\gamma_i\sum_{b_i\ne a_i^*}x_i(b_i)=\gamma_i(1-x_i(a_i^*))$. This gain is bounded by $r_i(x)$. Each nonpreferred coordinate is at most their sum, proving the distance bound. In a one-player two-action game with payoff gap exactly $\gamma$, assigning probability $q$ to the inferior action gives residual $\gamma q$ and distance $q$, attaining equality. ∎
Proposition (No scale-free residual-to-distance rule): For every integer $L\ge1$ there is a rational exact potential game with payoffs in $[0,1]$ and encoding length $O(L)$, and a profile with residual $2^{-L}$ but distance one from every equilibrium.
Proof: Use one player with payoffs $2^{-L}$ and zero, and choose the zero-payoff action. The first action is the unique equilibrium, so the probability-coordinate distance is one. The potential is the payoff itself. ∎
This example proves only the stated lack of a bound uniform in payoff scale. It does not rule out a game-dependent modulus or establish any hardness result at a given input precision. Remaining complexity question
Tree factorization gives a useful exact subcase and dominance gives a verifiable quantitative bridge, but neither addresses hardness for arbitrary concise potentials. Establishing membership or completeness under the source's unusual PLS verification convention requires a reduction for the full representation. The existence of a finite pure local maximum alone is not such a reduction. No claim about the unresolved general classification follows from these restricted algorithms.References
- [ABF] I. Anagnostides, M.-F. Balcan, K. Fragkia, T. Sandholm, E. Tewolde, and B. H. Zhang, The Complexity of Equilibrium Refinements in Potential Games, arXiv:2511.03968v2 (2026). https://arxiv.org/html/2511.03968v2. Section 3.1 and Question 6.1, including the PLS convention, specify the general target. The dynamic program above is for an explicit restricted representation.