we-solve (beta)

Econ-593 · economics · computer science · Computational economics

Average-case analysis of specified search-and-mix algorithms

LLM status Open unverified

Statement

GT-004 | Algorithmic equilibrium and complexity
R | Parameterized average-case research target.

Definitions and mathematical statement

Specify a sequence $(\mathcal D_n)_{n\geq1}$ of distributions on rational $n\times n$ bimatrix games with payoffs in $[0,1]$, a sampling and bit-encoding convention, and a particular search-and-mix algorithm $\mathcal A$, including its tolerances and internal randomization. Let $\xi$ denote the algorithm's random seed, independent of the sampled game. For its rational output $Z_n=\mathcal A(G,\xi)$, let $r_G(Z_n)$ be the largest unilateral payoff gain and $T_{\mathcal A}(G,\xi)$ its bit-operation count. Define \[ e_n=\mathbb E_{G\sim\mathcal D_n,\xi}[r_G(Z_n)],\qquad \tau_n=\mathbb E_{G\sim\mathcal D_n,\xi}[T_{\mathcal A}(G,\xi)]. \] For each fully specified pair $(\mathcal D,\mathcal A)$, determine asymptotic equivalents, or matching upper and lower asymptotic orders, for $e_n$ and $\tau_n$. A finite-encoding benchmark is independent uniform entries in $\{0,2^{-b(n)},\ldots,1\}$ for a declared integer function $b(n)$, using a declared initialization law and tolerance sequence.

Short English statement

Explain rigorously how accurate and how fast a particular Nash algorithm is on a particular random-game distribution.

Variants and scope boundaries

Both the distribution and the algorithm are essential data. Existence of some unspecified "natural" distribution would be vacuous. Uniformly bounded worst-case residuals immediately give bounded $e_n$; the substantive target is sharp distribution-sensitive behavior. Arithmetic-operation counts and bit-operation counts need not have identical asymptotics.

Source relationship and status

[S1] proposes average-case approximation analysis without selecting a universal distribution or asymptotic law. The displayed expectations are editorial definitions; the finite grid is an explicit optional benchmark rather than a model asserted to occur in the source.

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: concluding "Open problems and future directions," theoretical item 3; Section 4 for experimental distributions. 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-593-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-593

Average-case analysis of specified search-and-mix algorithms: A sharp Bernoulli search-and-uniform-mix benchmark

A fully specified pair of distribution and algorithm

For rational $n\times n$ bimatrix games, the targets are expected maximum unilateral gain and expected bit running time, \[ e_n=E[r_G(\mathcal A(G))],\qquad \tau_n=E[T_{\mathcal A}(G)]. \] The survey's average-case agenda [survey, Section 5] leaves the distribution and algorithm as essential choices. We choose the allowed finite-grid benchmark with $b(n)=0$: all $2n^2$ payoffs are independent Bernoulli$(1/2)$ variables. The following elementary search-and-mix algorithm is specified here; it is not an asserted analysis of the Tsaknakis--Spirakis or another named local-search algorithm.

Read payoff pairs $(A_{ij},B_{ij})$ in row-major order. On the first pair $(1,1)$, output the corresponding pure profile. If no such pair exists, output independent uniform mixtures on all $n$ actions. There are no tolerances or internal random seeds. A found pair is an exact Nash equilibrium, since neither player can exceed payoff one. The algorithm need not find every pure equilibrium before its fallback.

Input is a binary encoding of $n$, followed by the promised binary payoff pairs on a sequential tape. Reading the entire input is not required to certify a found maximum-payoff pair. Output uses a sparse list of nonzero probabilities, with fixed-width $\lceil\log_2(n+1)\rceil$ action indices and ordinary binary rational values. The uniform fallback writes all $2n$ nonzero entries. Sampling the input is not included in algorithmic running time. These conventions matter to the time result.

The rare fallback and its residual

Let $F$ be the event that no pair equals $(1,1)$. Then \[ \Pr(F)=(3/4)^{n^2}. \] Conditional on $F$, cells remain independent and each pair is uniform on $(0,0),(1,0),(0,1)$. Hence every $A$ entry and every $B$ entry has Bernoulli parameter $p=1/3$, though the two entries in a cell are negatively dependent. Define row means $R_i=n^{-1}\sum_jA_{ij}$, column means $C_j=n^{-1}\sum_iB_{ij}$, and grand means $\overline A=n^{-2}\sum_{ij}A_{ij}$ and similarly $\overline B$. The uniform profile's residual is exactly \[ r=\max\{\max_i R_i-\overline A, \max_j C_j-\overline B\}. \tag{1} \]
Lemma: Under this conditional law, \[ E[r\mid F]\sim\frac23\sqrt{\frac{\log n}{n}}. \tag{2} \]
Proof: Put $v=p(1-p)=2/9$ and $M=\max(\max_i(R_i-p),\max_j(C_j-p))$. The maximum function is Lipschitz in the sup norm, so \[ |r-M|\le\max(|\overline A-p|,|\overline B-p|). \] Each grand mean has variance $v/n^2$; thus the expectation of the right side is at most $2\sqrt v/n$, negligible at the proposed scale.

For the upper bound, if $S$ is a mean of $n$ independent Bernoulli$(p)$ variables, expansion of its moment-generating function gives \[ \log E[e^{\lambda(S-p)}] =\frac{v\lambda^2}{2n}+O(\lambda^3/n^2) \] uniformly when $\lambda/n\to0$ and $\lambda\ge0$. Indeed, this is $n$ times the Taylor expansion at zero of $\log(1-p+pe^t)-pt$, whose third derivative is bounded on a fixed neighborhood of zero. Since the maximum of exponentials is at most their sum, Jensen's inequality yields \[ E[M]\le\frac{\log(2n)}{\lambda} +\frac{v\lambda}{2n}+O(\lambda^2/n^2). \] Choose $\lambda=\sqrt{2n\log(2n)/v}$. This bounds $E[M]$ by $\sqrt{2v\log n/n}(1+o(1))$ without assuming independence between the row and column families.

For the lower bound fix $0<a<\sqrt{2v}$. For $X\sim\operatorname{Bin}(n,p)$, Stirling's factorial formula implies \[ \Pr\{X\ge np+a\sqrt{n\log n}\} \ge n^{-a^2/(2v)+o(1)}. \tag{3} \] Here is the relevant moderate-deviation step. Sum the point masses for integers between $np+a\sqrt{n\log n}$ and that value plus $\lfloor\sqrt n/\sqrt{\log n}\rfloor$. Uniformly on this range, the logarithm of a point mass is $-nD(k/n\Vert p)-\frac12\log n+O(1)$ by Stirling, where $D(q\Vert p)=q\log(q/p)+(1-q)\log((1-q)/(1-p))$. Its Taylor expansion gives $nD(k/n\Vert p)=\frac{a^2}{2v}\log n+o(\log n)$. The number of summands is $n^{1/2+o(1)}$, proving (3). The $n$ row sums are mutually independent. Because $a^2/(2v)<1$, the probability that all fall below this threshold tends to zero. Consequently $M\ge a\sqrt{\log n/n}$ with probability tending to one. Finally $M\ge\overline A-p$, so the expectation of its negative part is at most $\sqrt v/n$. This gives the matching lower bound on $E[M]$ as $a\uparrow\sqrt{2v}$. Restoring the negligible grand-mean error proves (2), since $\sqrt{2v}=2/3$. ∎

Theorem: For the specified Bernoulli distribution and algorithm, \[ e_n\sim(3/4)^{n^2}\frac23\sqrt{\frac{\log n}{n}}, \qquad \tau_n=\Theta(\log(n+1)). \tag{4} \] The expected number of inspected payoff pairs is exactly $4\{1-(3/4)^{n^2}\}$.
Proof: The residual is zero outside $F$, and (2) gives its conditional expectation on $F$, proving the first assertion. Let $K$ be the number of inspected pairs. For $1\le k\le n^2$, $\Pr(K\ge k)=(3/4)^{k-1}$, so summing these survival probabilities gives the displayed expectation. Binary row and column counters require at most $O(\log(n+1))$ work per inspected pair, including carries and row resets. Initialization and pure-index output have the same bound. On $F$ the rational uniform lists cost $O(n\log(n+1))$ additional bit operations. Thus expected work is $O((1+E[K])\log(n+1)+\Pr(F)n\log(n+1))=O(\log(n+1))$. Writing even the two pure-action indices in the declared fixed-width format requires $\Omega(\log(n+1))$ bits; reading the dimension does too. This proves the lower time bound and completes (4). ∎

What this benchmark does and does not answer

The small expected residual is driven by the atom at the maximum payoff, not by typical performance of uniform mixing. Conditional on failing to find that atom, the error is only of order $\sqrt{\log n/n}$, with the constant in (2). On a continuous payoff distribution the exact pair $(1,1)$ has probability zero, so this same algorithm always takes the fallback; increasing grid resolution changes the search probability as well. Mandatory full-input validation or dense output would also change the time order. These facts prevent transplanting (4) to another encoding or algorithm.

The note completely determines one nontrivial specified benchmark, including its exponentially rare contribution to expected error. Sharp average-case laws for other search-and-mix procedures, especially local search with accuracy-dependent stopping and growing grid precision, remain outside the result and unresolved here.

Completion Estimate

71%

This is a post hoc, heuristic estimate for the full catalogue target. The attempt obtains a sharp expected-residual equivalent and matching bit-time order for a fully specified Bernoulli search-and-uniform-mix algorithm, including its rare fallback event. The original distribution-sensitive research family remains open for other search-and-mix procedures, growing payoff precision, tolerance-dependent local search, and different required input or output encodings.

References

  • [survey] H. Li, W. Huang, Z. Duan, D. H. Mguni, K. Shao, J. Wang, and X. Deng (2023), A survey on algorithms for Nash equilibria in finite normal-form games, arXiv:2312.11063v1. https://arxiv.org/pdf/2312.11063.

Go to contribution →