we-solve (beta)

Econ-203 · economics · computer science · Computational economics

Improving search-and-mix approximation guarantees

LLM status Open unverified

Statement

GT-002 | Algorithmic equilibrium and complexity
R | Precise algorithm-design target; the source's framework is not an axiomatized complexity class.

Definitions and mathematical statement

Let $A,B\in\mathbb Q^{m\times n}\cap[0,1]^{m\times n}$ be explicitly encoded, and let $r_{A,B}$ denote the maximum unilateral payoff gain, as displayed in GT-001. A search-and-mix algorithm first computes finite lists $X=(x^1,\ldots,x^s)\subset\Delta_m$ and $Y=(y^1,\ldots,y^t)\subset\Delta_n$, then outputs \[ x=\sum_{a=1}^{s}\lambda_ax^a,\qquad y=\sum_{b=1}^{t}\mu_by^b,\qquad \lambda\in\Delta_s,\quad\mu\in\Delta_t. \] An admissible template specifies the search subroutines, candidate lists, accuracy tolerances, and mixing rule; all must have polynomial bit complexity. The quantitative design target is to exhibit such a fully specified template, an algorithm $\mathcal A$, and a constant $\eta\in(0,1/3)$ satisfying \[ \forall A,B,\qquad r_{A,B}\left(\mathcal A(A,B)\right)\leq \frac13-\eta. \] For a specified family $\mathfrak S$ of templates, its optimal guarantee can instead be defined by $\alpha(\mathfrak S)=\inf_{\mathcal A\in\mathfrak S}\sup_{A,B}r_{A,B}(\mathcal A(A,B))$.

Short English statement

Improve the worst-case additive error of a concrete search-and-mix algorithm below one third.

Variants and scope boundaries

The decomposition alone imposes no meaningful restriction: any algorithm fits it by returning its final answer as a singleton candidate list. Consequently an impossibility theorem for "the framework" needs additional restrictions on $\mathfrak S$. The historical benchmark is $1/3+\delta$ for arbitrary $\delta>0$, with runtime polynomial in $1/\delta$, rather than an automatically attained exact $1/3$ guarantee.

Source relationship and status

[S1] explicitly requests an improvement using search-and-mix methods. The displayed constant-gap target is an editorial mathematical specification of that request. No unverified claim that $1/3$ remains the best bound on the document date is made.

References

[S1] Hanyu Li, Wenhan Huang, Zhijian Duan, David Henry Mguni, Kun Shao, Jun Wang, and Xiaotie Deng (2023). A survey on algorithms for Nash equilibria in finite normal-form games. Locator: Section 3.4, including the DFM22 algorithm; concluding "Open problems and future directions," theoretical item 1. https://arxiv.org/pdf/2312.11063

Common conventions: Source mathematical conventions

Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.

Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.

Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.

Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.

Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-203-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-203

Strategically centered zero-sum certificates for search-and-mix

Problem ID: C72-199. Status: unresolved.

Target and outcome

The target is a fully specified polynomial-time search-and-mix algorithm with a fixed worst-case additive regret below one third for all rational bimatrix games in $[0,1]$. The survey [Survey, Section 3.4 and open-problem item 1] records the $1/3+\delta$ benchmark and the improvement question. We give a complete algorithm with a computable structural certificate that beats one third on a declared class, and a polynomial mixing optimization for fixed candidate-list sizes. Neither result yields a uniform sub-third guarantee over all games.

For $x\in\Delta_m$, $y\in\Delta_n$, define \[ r(x,y)=\max\left\{\max_i e_i^TAy-x^TAy, \max_j x^TBe_j-x^TBy\right\}. \] The two terms are nonnegative because a best response is at least the current mixed payoff. All algorithms below operate on exactly encoded rational input.

Centering out strategically irrelevant terms

Let $M=A+B$. Solve the linear program \begin{equation}\label{wsref-0-63-65-6e-74-65-72-69-6e-67} \epsilon_* =\min_{c\in{\mathbb{R}}^m,d\in{\mathbb{R}}^n,\epsilon\ge0}\epsilon \quad\text{subject to}\quad |M_{ij}-c_i-d_j|\le\epsilon\quad\text{for all }i,j. \end{equation} An arbitrary constant can be transferred between $c$ and $d$, so impose $c_1=0$ as a gauge. Write $C_{ij}=M_{ij}-c_i-d_j$ for an optimal residual, and form \[ A'_{ij}=A_{ij}-d_j,\quad B'_{ij}=B_{ij}-c_i, \quad H=(A'-B')/2. \] Then $A'=H+C/2$ and $B'=-H+C/2$. Subtracting $d_j$ from the row player's payoff does not change a unilateral row deviation at a fixed opponent strategy. Subtracting $c_i$ from the column player's payoff likewise preserves all column deviations.
Theorem (An exact structural regret certificate): The centering program and a Nash equilibrium $(x^H,y^H)$ of the zero-sum game $(H,-H)$ can be computed in polynomial bit complexity. Their output satisfies \[ r(x^H,y^H)\le\epsilon_*. \] More precisely its two regrets are bounded respectively by \[ \frac12\left(\max_i e_i^TCy^H-(x^H)^TCy^H\right),\qquad \frac12\left(\max_j(x^H)^TCe_j-(x^H)^TCy^H\right). \] In particular, for any fixed $\eta\in(0,1/3)$, all inputs with $\epsilon_*\le1/3-\eta$ admit the requested sub-third output by this algorithm. When $M_{ij}=c_i+d_j$ exactly, the output is an exact Nash equilibrium of the original game.
Proof: The centering program has a feasible point with $\epsilon=1$: choose $c_i=0$ and $d_j=1$, since $0\le M_{ij}\le2$. Under the gauge and $\epsilon\le1$, the row $i=1$ constraints imply $d_j\in[-1,3]$. Then column $j=1$ implies $c_i\in[-4,4]$. Thus imposing these compact rational bounds loses no optimal solution. A rational optimum of polynomial bit length can be computed by a polynomial-time rational linear-programming algorithm. The zero-sum equilibrium is obtained from the primal and dual minimax linear programs for $H$, also rational and of polynomial size. Finite zero-sum minimax, equivalently linear-program duality, ensures their solutions satisfy \[ (e_i-x^H)^THy^H\le0,\qquad (x^H)^T(-H)(e_j-y^H)\le0 \] for every pure deviation. This is the standard LP algorithm for finite zero-sum games; no real-algebraic output is required.

Strategic invariance and the decomposition give \[ (e_i-x^H)^TAy^H =(e_i-x^H)^THy^H+\tfrac12(e_i-x^H)^TCy^H \le\tfrac12(e_i-x^H)^TCy^H. \] Take the maximum over $i$ for the first detailed certificate. The second follows identically from $B'=-H+C/2$. Every entry of $C$ is between $-\epsilon_*$ and $\epsilon_*$, so every displayed difference of its averages is at most $2\epsilon_*$. Dividing by two proves the uniform certificate. The exact and sub-third specializations follow immediately. ∎

The use of the symmetric surrogate $H$ matters: approximating only one player's matrix by a zero-sum game loses the factor one half in the residual oscillation. Removing row and column shifts further avoids charging for payoff terms that never affect that player's deviations.

A fully specified general search-and-mix template

The structural subroutine can be incorporated in a template that is defined on every input, not merely on the favorable class. Choose the first row $i_0$. Let $j_0$ be a pure best response of the column player to it, and let $i_1$ be a pure best response of the row player to $j_0$. Break ties by smallest index. Put \[ x^0=\tfrac12(e_{i_0}+e_{i_1}),\qquad y^0=e_{j_0}. \] Compute $(x^H,y^H)$ as above. The candidate lists are \[ X=(e_{i_0},e_{i_1},x^H),\qquad Y=(e_{j_0},y^H). \] Evaluate regrets exactly at $(x^0,y^0)$ and $(x^H,y^H)$ and return the better of the two, with a fixed tie rule. Each is a specified convex combination from these lists.
Proposition (A global guarantee with a structural improvement): This deterministic template has polynomial bit complexity and, for every input, returns a profile with \[ r(x,y)\le\min\{1/2,\epsilon_*\}. \]
Proof: At $y^0$, row $i_1$ is a best response, so the row regret of $x^0$ is $\tfrac12(A_{i_1j_0}-A_{i_0j_0})\le1/2$. For any column deviation $j$, \[ (x^0)^TB(e_j-e_{j_0}) =\tfrac12(B_{i_0j}-B_{i_0j_0}) +\tfrac12(B_{i_1j}-B_{i_1j_0})\le1/2, \] since the first parenthesis is nonpositive by the choice of $j_0$ and the second is at most one. Thus the fallback has regret at most $1/2$. Theorem Theorem (An exact structural regret certificate) bounds the other profile. Exact comparison of the two computed regrets proves the bound. Best-response scans and rational linear programs have the claimed polynomial complexity. ∎
The fallback proof is the elementary best-response mixing construction, not an improvement on the survey's general $1/3+\delta$ algorithm. Its role here is to make the new certificate part of a complete, independently specified template without invoking an unexpanded subroutine.

Optimizing mixing for constant-size candidate lists

The next result applies to arbitrary rational candidate lists, including the three-by-two lists above. Candidate generation and mixing optimization are separate issues in the target.
Lemma (Regret continuity): For all probability vectors $x,x',y,y'$, \[ |r(x,y)-r(x',y')|\le2\left(\|x-x'\|_1+\|y-y'\|_1\right). \]
Proof: For entries of $A$ in $[0,1]$, changing $y$ changes each pure-row payoff by at most $\|y-y'\|_1$, and hence changes their maximum by at most that amount. The current payoff changes by at most $\|x-x'\|_1+\|y-y'\|_1$, by adding and subtracting $(x')^TAy$. The row regret therefore changes by at most $\|x-x'\|_1+2\|y-y'\|_1$. The column argument interchanges the two coefficients. The absolute difference of maxima of two numbers is at most the larger absolute difference of the two entries, yielding the stated convenient bound. ∎
Theorem (Polynomial approximate mixing at fixed list size): Fix positive constants $s,t$. Given lists $X=(x^1,\ldots,x^s)$ and $Y=(y^1,\ldots,y^t)$ of rational strategies and rational $\tau>0$, one can compute mixtures with regret at most \[ \min_{\lambda\in\Delta_s,\mu\in\Delta_t} r\left(\sum_a\lambda_ax^a,\sum_b\mu_by^b\right)+\tau \] in time polynomial in input bit length and $1/\tau$. If specified additional mixture pairs are also evaluated, the output is no worse than any of them.
Proof: If $s=t=1$, there is only one mixture. Otherwise choose an integer $K\ge4(s+t-2)/\tau$ and enumerate probability vectors whose coordinates are integer multiples of $1/K$. For any $\lambda\in\Delta_s$, round its first $s-1$ coordinates downward and put the remaining probability in the last coordinate. The resulting $\widehat\lambda$ obeys $\|\lambda-\widehat\lambda\|_1\le2(s-1)/K$. The same procedure gives $\|\mu-\widehat\mu\|_1\le2(t-1)/K$. Taking convex combinations of probability vectors contracts this bound: for example \[ \left\|\sum_a(\lambda_a-\widehat\lambda_a)x^a\right\|_1 \le\sum_a|\lambda_a-\widehat\lambda_a|\|x^a\|_1 =\|\lambda-\widehat\lambda\|_1. \] A minimizing pair exists by continuity on compact simplices. Lemma Lemma (Regret continuity) shows that a grid pair within the above rounding distances has regret at most its optimum plus $4(s+t-2)/K\le\tau$.

There are $\binom{K+s-1}{s-1}\binom{K+t-1}{t-1}$ grid pairs. For fixed $s,t$ this is polynomial in $K$, hence in $1/\tau$. Their regrets are exactly evaluated by scanning the original pure actions and performing rational arithmetic of polynomial bit length. Return a minimum, including any extra specified pairs in the same comparison. This proves both assertions. ∎

Applied to Proposition Proposition (A global guarantee with a structural improvement), including its two output candidates among the evaluated pairs retains the bound $\min\{1/2,\epsilon_*\}$ while approaching the best possible mixture from the chosen lists. The exponent in the grid size depends on $s+t$, so this is not a polynomial algorithm for lists of unrestricted length.

Remaining universal gap

The centering residual is not uniformly below one third. For example, $A=B=\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\right)$ has $\epsilon_*=1$: its alternating sum $M_{11}+M_{22}-M_{12}-M_{21}=4$ is unchanged by row/column shifts, while four residual entries of magnitude at most $\epsilon$ have alternating sum at most $4\epsilon$; $\epsilon=1$ is attainable. This game itself is easy, but it proves that the certificate alone cannot imply the desired universal constant.

The unresolved task is a candidate-generation argument guaranteeing a sub-third mixture for every game, together with polynomial complexity. Theorem Theorem (Polynomial approximate mixing at fixed list size) addresses only fixed-list mixing once such candidates are given. The survey HTML was checked on 9 October 2026, including the $1/3+\delta$ running-time statement and the explicit improvement question. No numerical experiment or claim about the current best universal bound is needed for these restricted results.

References

  • [Survey] H. Li, W. Huang, Z. Duan, D. H. Mguni, K. Shao, J. Wang, and X. Deng, A survey on algorithms for Nash equilibria in finite normal-form games, arXiv:2312.11063, 2023. Section 3.4 and "Open problems and future directions," item 1. https://arxiv.org/html/2312.11063.

Completion Estimate

20%

Go to contribution →