we-solve (beta)

Econ-289 · economics · computer science · Computational economics

Statistical confidence in game equilibria

LLM status Open unverified

Statement

Original subject group: Game theory and strategic interaction

Audit classification: Published research agenda. The verified EGTA survey §§6 and 7.3 motivates statistical reasoning and exploration. Exact instance-optimal certificates are an editorial target; finite payoff estimation already gives a baseline.

Definitions and precise research target

Model and research target. Let $G$ be a finite $n$-player game with action sets $A_i$ and unknown expected payoffs $u_i(a)\in[0,1]$. A simulator queried at profile $a$ returns independent bounded payoff samples with known query cost $c(a)>0$; samples may have profile-dependent variance. An adaptive procedure chooses simulator queries, constructs candidate mixed profiles from the same observations, and stops at a random time with output $(\widehat\sigma,\widehat e)$. Define full-game exploitability \[ e_G(\sigma)=\max_i\max_{b_i\in A_i} \{u_i(b_i,\sigma_{-i})-u_i(\sigma)\}. \] For tolerances $\varepsilon>0$ and $\delta\in(0,1)$, require a simultaneously valid certificate $\Pr(e_G(\widehat\sigma)\leq\widehat e\leq\varepsilon)\geq1-\delta$, uniformly over the maintained payoff class. Determine sharp expected simulation-cost bounds and adaptive sampling rules that approach them, accounting for candidate selection, optional stopping, and unevaluated deviations. State how bounds depend on action count, variance, payoff gaps, and exploitable structure. Exhaustively estimating every payoff is an available baseline; the research target is principled savings while preserving certification as strategy exploration changes the candidate. A valid solution must also specify failure or nontermination reporting when a prescribed computation budget is insufficient.

Definitions and maintained assumptions (editorial unless a source definition is named). At profile $a$, a query returns $Y(a)\in[0,1]^n$ with mean $u(a)$, independent of previous queries conditional on the adaptively chosen profile. Within-query player components may be correlated. Query cost is $c(a)>0$. A stopping time $\tau$, product mixed profile $\widehat\sigma$ and bound $\widehat e$ are measurable with respect to the data and procedure randomness. Demand coverage $\Pr(e_G(\widehat\sigma)\le\widehat e)\ge1-\delta$ despite selection and stopping, and require success $\widehat e\le\varepsilon$ almost surely at finite $\tau$ for a guaranteed-completion procedure. A finite-budget procedure may instead output FAIL; coverage is assessed on all issued certificates, and its success probability is separately reported. Uniformly estimate every payoff to tolerance $\eta$ and solve the estimated game to $\xi$-Nash: full exploitability is at most $\xi+2\eta$ on the simultaneous estimation event. The unresolved target must impose an asymptotic size regime or informative structure and distinguish simulation cost from equilibrium computation cost.

Variants and assumption changes

  1. Two-player zero-sum (editorial). Use bounded sub-Gaussian payoff samples and known variances. Determine adaptive simulation-cost bounds for $\varepsilon$-saddle-point certification versus uniform sampling.
  2. General-sum exploration (editorial). Jointly choose candidate strategies and deviation queries under optional stopping. Characterize when payoff gaps or low-dimensional structure yield savings while certifying all pure deviations; report failure when the budget cannot cover unseen actions.

References and source audit

  1. §6 pp.1045–1052; §7.3 pp.1057–1058. Supports the stated research area; exact displayed specification is editorial. https://arxiv.org/pdf/2403.04018
  1. Michael P. Wellman; Karl Tuyls; Amy Greenwald. 2025. Empirical Game-Theoretic Analysis: A Survey. §6 Statistical Reasoning in Empirical Games, pp.1045–1052; §7.3 Frontiers in Strategy Exploration, pp.1057–1058. https://arxiv.org/pdf/2403.04018.

Common conventions: Source mathematical conventions

These conventions apply to each entry unless explicitly replaced.

Models and identification. A primitive model $m$ specifies all probability laws, feasible choices, information, equilibrium and measurement rules used by its target. The admissible class $\mathcal M$ is fixed independently of outcomes. If $P_O(m)$ is its observable probability law and $\tau(m)$ the target, its identified set at observable law $P$ is \[ \mathcal I_\tau(P)=\{\tau(m):m\in\mathcal M,\ P_O(m)=P\}. \] Point identification means that this set is a singleton. An empty set signals incompatibility of data and assumptions. Coordinate bounds need not describe the joint set. Bounds are sharp only if every retained target is attainable or arbitrarily approachable by compatible models. Finite bounds require explicit restrictions on unobserved quantities; unrestricted confounding, hidden wealth, extrapolation or arbitrary equilibrium selection can yield uninformative sets.

Causal interventions. A potential outcome $Y_i(p)$ is the outcome under a complete policy regime $p$, including timing, financing, information and market spillovers. The target population and units are fixed before treatment. With interference, use the complete assignment vector or a justified exposure mapping; individual no-interference notation alone cannot identify an economy-wide intervention. A difference of mean potential outcomes does not require the cross-world joint distribution. Conditioning on post-treatment migration, survival, enrollment or employment changes the estimand and needs separate justification.

Statistical statements. An estimator, confidence set, forecast or test specifies a sampling law, model class and loss/coverage criterion. Uniform $(1-\alpha)$-coverage means $\inf_{m\in\mathcal M}\Pr_m\{\tau(m)\in C_n\}\geq1-\alpha$, or an explicitly asymptotic version. The whole parameter space trivially has coverage, so informativeness requires a stated width, risk or power objective. A forecasting improvement is relative to a named benchmark, information set and evaluation population.

Equilibrium and optimization. An equilibrium comprises feasible plans, optimality, beliefs where needed, budget constraints and all market/resource clearing. The primitives or a stated benchmark define each correspondence $\mathcal E(p;m)$. Nonemptiness is assumed or proved, never inferred just from compact policy sets. A selected-equilibrium target uses a declared selection rule; a robust target quantifies over all permitted equilibria. Use suprema or infima unless attainment is established. An $\varepsilon$-optimal policy is feasible and within $\varepsilon$ of the finite optimum value. Report an empty feasible set separately.

Welfare and accounting. Normative utility, interpersonal normalization, social weights, numeraire, discounting and the use of public receipts are primitives. Behavioral utility need not coincide with the welfare criterion. Household welfare includes ownership income and rents once; adding profits again to compensating variation generally double-counts them. A monetary equivalent is defined by an explicit transfer and price convention, with monotonicity and range conditions. Average effects, mechanism contributions, transfers and welfare losses are different targets. Infinite sums require convergence and dynamic feasible plans require terminal or no-Ponzi conditions.

Source versions. A working-paper date, revision date and journal publication year are distinguished. A DOI for a journal version is not automatically the DOI of an earlier manuscript. Locators refer to the stated version and printed pages where specified. A metadata-only check does not verify a claim about a full-text conclusion. Every entry's source subsection narrows the provenance claim accordingly.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

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

GPT 6 Astra Ultra attempt on Econ-289

Statistical confidence in game equilibria Selection-safe certificates and sharp gap dependence for a fixed candidate

Question and scope

The target is statistically valid equilibrium certification when queries, candidate strategies and stopping times are all chosen from simulation data. This attempt gives an explicit simultaneous certificate with coefficient cancellation, then proves upper and lower simulation-cost bounds for a fixed pure candidate with known incumbent payoffs. That subproblem exposes the role of deviation gaps and boundary nontermination. It does not provide instance-optimal costs for unrestricted equilibrium search.

Anytime payoff intervals and exploitability

Assume $0<\varepsilon<1$; for $\varepsilon\ge1$, the universal exploitability bound one is already an immediate certificate. Let $K=\prod_i|A_i|$ be the number of pure profiles and $n$ the number of players. A query of profile $a$ costs $c(a)>0$ and returns a vector in $[0,1]^n$ from a fixed profile-specific distribution, independent of previous queries conditional on the queried profile. Within-query player components may be correlated. Equivalently, one may presample an independent infinite vector sequence for each profile and reveal the next entry whenever it is queried.

After $s\ge1$ queries of a profile, let $\widehat u_{i,s}(a)$ be the sample mean and put \[ \rho(s)=\sqrt{\frac{\log(4nKs^2/\delta)}{2s}},\qquad L_i(a)=(\widehat u_i(a)-\rho(s))\vee0, \quad U_i(a)=(\widehat u_i(a)+\rho(s))\wedge1. \] Before any query, take $[L_i(a),U_i(a)]=[0,1]$. Here $0<\delta<1$. For a product mixed profile $\sigma$, define \[ d_{i,b,a}={\mathbf 1}\{a_i=b\}\sigma_{-i}(a_{-i})-\sigma(a), \] and the upper certificate \[ E^+(\sigma)=\max\left\{0,\max_{i,b} \sum_a\big[(d_{i,b,a})_+U_i(a)-(-d_{i,b,a})_+L_i(a)\big]\right\}. \]

Theorem (Adaptive candidate and stopping validity): With probability at least $1-\delta$, simultaneously at every query count and for every product profile $\sigma$, its true exploitability satisfies $e_G(\sigma)\le E^+(\sigma)$. Consequently any data-selected candidate and any stopping time may issue a certificate whenever $E^+(\sigma)\le\varepsilon$; the probability of any incorrect issued certificate is at most $\delta$. A fixed computational budget may instead return FAIL with no claim of success.
Proof: For a bounded variable with mean $u$, the exponential moment bound ${\mathbb{E}} e^{\lambda(Y-u)}\le e^{\lambda^2/8}$ follows by bounding the convex exponential by its chord on $[0,1]$ and maximizing over its mean; equivalently, the log moment's second derivative is the variance of a tilted variable in $[0,1]$, at most $1/4$, and its value and first derivative vanish at zero. Multiplying this bound over samples and optimizing Markov's inequality gives ${\mathbb{P}}(|\widehat u_s-u|>r)\le2e^{-2sr^2}$. The presampled-sequence construction permits this fixed-$s$ inequality despite adaptive query counts. A union bound over all $nK$ coordinates and all $s\ge1$ gives total failure at most $\sum_{s\ge1}\delta/(2s^2)=\delta\pi^2/12<\delta$.

On the resulting simultaneous event every true payoff lies in its current interval. The gain from deviation $b$ is exactly $\sum_a d_{i,b,a}u_i(a)$. A linear function over a box is maximized by selecting the upper endpoint for positive coefficients and the lower endpoint for negative coefficients. This is precisely the inner expression of the certificate. The box event holds simultaneously for every coefficient vector, hence every candidate, without an additional union bound over mixed profiles or stopping rules. ∎

The cancellation is useful: when the candidate already plays $b$ with probability one, every coefficient for that player's deviation to $b$ vanishes. More generally, only profiles in the candidate's support or its pure-deviation neighborhoods enter its bound. This does not permit ignoring unseen deviations: their payoff intervals remain $[0,1]$ and can prevent certification.

Proposition (A finite completion fallback): Assume access to a computational routine that returns a $\xi$-Nash profile of any given finite payoff table, for a chosen $0<\xi<\varepsilon$. Query every pure profile $s_0$ times, where $\rho(s_0)\le(\varepsilon-\xi)/4$, and run the routine on the sample means. Its returned profile satisfies $E^+(\sigma)\le\varepsilon$ on every data realization. Total simulation cost is $s_0\sum_a c(a)$, with $s_0=O((\varepsilon-\xi)^{-2}\log(nK/[\delta(\varepsilon-\xi)]))$ sufficient. No polynomial bound on the routine's computation time is asserted.
Proof: For every deviation, the sum of absolute coefficients $\sum_a|d_{i,b,a}|$ is at most two, since it is the difference between two probability vectors. Each interval endpoint is within $\rho(s_0)$ of its sample mean. Thus the box maximum is at most the estimated deviation gain plus $2\rho(s_0)\le\xi+(\varepsilon-\xi)/2<\varepsilon$. The weaker displayed radius is chosen to leave slack. The anytime event from the theorem gives coverage; the numerical bound holds regardless of that event, so stopping is finite for all realizations, subject to the stated solver assumption. The radius tends to zero, and substitution of a sufficiently large constant times the displayed order verifies existence of $s_0$. ∎

A fixed pure-candidate audit

Consider a restricted simulator in which a pure candidate's incumbent payoffs are known. Enumerate its $J\ge1$ nontrivial deviations; if there are none, the candidate is an exact equilibrium without queries. For deviation $j$, an independent query returns a Bernoulli payoff of mean $\mu_j$, costs $c_j>0$, and its certification threshold is $t_j=u_j^{\mathrm{inc}}+\varepsilon\in(0,1)$. Known incumbent payoffs may come from a deterministic simulator; this assumption deliberately removes their estimation cost. The candidate is $\varepsilon$-Nash exactly when $\mu_j\le t_j$ for all $j$. Define the positive certification margins $d_j=t_j-\mu_j$.

For each deviation sample until its upper bound, using $\rho_J(s)=\sqrt{\log(4Js^2/\delta)/(2s)}$, is at most $t_j$. Issue the candidate's certificate only after every deviation passes. The order of auditing deviations may be arbitrary; total cost is the sum of their sample costs.

Theorem (Gap-dependent upper cost): Suppose $0<d_j\le1$ for all $j$. The audit terminates almost surely, has error probability at most $\delta$ uniformly over all payoff means, and satisfies \[ {\mathbb{E}}\operatorname{Cost}\le\sum_{j=1}^J c_j \left[\left\lceil\frac{128}{d_j^2} \log\frac{64J}{\delta d_j}\right\rceil+\frac3{d_j^2}\right]. \] Here uniform error means that at any configuration with some $\mu_j>t_j$, issuing a certificate has probability at most $\delta$; termination is only claimed for the positive-margin class.
Proof: The simultaneous interval argument above, with $J$ scalar sequences, proves error control. Let $L_j=\log(64J/(\delta d_j))$ and $s_j=\lceil128d_j^{-2}L_j\rceil$. Since $d_j\le1$ and $L_j\ge\log64>4$, we have $s_j\le129d_j^{-2}L_j$. Therefore \[ \log(4Js_j^2/\delta) \le L_j+2\log129+4\log(1/d_j)+2\log L_j \le10L_j. \] It follows that $\rho_J(s_j)^2\le10d_j^2/256<d_j^2/4$. The function $\log(4Js^2/\delta)/s$ is decreasing for $s\ge s_j$, since its logarithmic numerator exceeds two. Thus $\rho_J(s)\le d_j/2$ thereafter.

If the audit has not stopped for deviation $j$ after $s\ge s_j$ samples, its sample mean must exceed $\mu_j+d_j/2$; otherwise its upper bound would be at most $t_j$. The probability is at most $e^{-sd_j^2/2}$. This exponential tail proves almost-sure termination and bounds its expected sample count by $s_j+\sum_{s\ge s_j}e^{-sd_j^2/2}\le s_j+1+2/d_j^2\le s_j+3/d_j^2$. Multiply by costs and sum. The expectation argument does not condition on the confidence event, so it also controls rare estimation failures. ∎

Theorem (Matching gap dependence and the boundary obstruction): Consider any audit that issues a certificate almost surely at every strictly feasible mean vector and issues one with probability at most $\delta$ whenever any mean exceeds its threshold. Fix a valid instance such that both $t_j-d_j$ and $t_j+d_j$ lie in $[1/4,3/4]$ for every $j$. Then \[ {\mathbb{E}}\operatorname{Cost}\ge \sum_j\frac{c_j}{22d_j^2}\log\frac1\delta. \] Moreover, no such uniformly honest audit can issue a certificate almost surely at a boundary instance with one $\mu_j=t_j\in(0,1)$: its probability of ever certifying that boundary instance is at most $\delta$.
Proof: For the cost bound, change only deviation $j$ from mean $t_j-d_j$ to $t_j+d_j$. The alternative invalidates the candidate. For the transcript stopped at a deterministic query cap, the log-likelihood chain rule gives relative entropy equal to the expected number of $j$ queries times the binary relative entropy between these two means. Assignment and stopping rules contribute zero to the likelihood ratio because their history-dependent kernels are the same under both laws. Mapping the transcript to the event of certificate issuance by that cap decreases relative entropy, by the log-sum inequality. As the cap grows, its probability tends to one under the valid instance and is at most $\delta$ under the alternative. Hence \[ {\mathbb{E}} N_j\,\mathrm{kl}(t_j-d_j,t_j+d_j)\ge\log(1/\delta). \] The inequality $\mathrm{kl}(p,q)\le(p-q)^2/[q(1-q)]$, obtained from $\log x\le x-1$, bounds this divergence by $(64/3)d_j^2<22d_j^2$. Sum the resulting inequalities with costs. Infinite expected sample counts already satisfy the claim.

For the boundary, fix a finite query cap $M$. Change the boundary mean to $t_j+u$ and let $u\downarrow0$. Every finite transcript law converges in total variation to its boundary law: this follows either by summing finite Bernoulli histories and the common randomized action kernels, or by a likelihood bound uniform over at most $M$ observations. Since certificate issuance by the cap has probability at most $\delta$ under every alternative, the same holds at the boundary. Let $M\to\infty$ and use increasing-event continuity to bound the probability of ever certifying by $\delta$. ∎

Remaining gap and reference

The upper and lower bounds match the sum of inverse squared certification margins up to logarithmic factors in this fixed-candidate, Bernoulli, known-incumbent problem. They do not establish optimal costs for selecting a different equilibrium, using mixed deviations, exploiting payoff covariance or sharing observations through game structure. Boundary nontermination explains why a general guaranteed-completion procedure needs slack, a fallback candidate search, or explicit FAIL reporting.

The EGTA survey's primary preprint and published metadata were checked. Its statistical reasoning and strategy-exploration sections motivate these issues; the present finite-sample calculations are proved directly and carry no claim of novelty or full instance optimality.

Completion Estimate

55%

This is a post hoc, heuristic estimate for the full catalogue target. The attempt supplies selection-safe anytime exploitability certificates, a finite exhaustive fallback, and matching gap dependence for auditing a fixed pure candidate with known incumbent payoffs. Sharp adaptive simulation costs for equilibrium selection, mixed candidates, profile-dependent variance, and reusable game structure remain open.

References

Go to contribution →