Uniform epsilon-equilibrium in finite multiplayer stochastic games

Uniform epsilon-equilibrium in finite multiplayer stochastic games

Definitions and mathematical statement

A finite stochastic game has finitely many players, states, and available actions, bounded stage payoffs $r_i(s,a)$, and transition probabilities $q(s'\mid s,a)$. A behavioral strategy assigns a probability distribution on the current player's actions to each observed finite history, with the information convention of the game. Given initial state $s_0$ and strategy profile $\sigma$, write \[ \gamma_i^n(s_0,\sigma)={\mathbb{E}}_{s_0,\sigma} \left[\frac1n\sum_{t=1}^n r_i(s_t,a_t)\right]. \] The requested uniform equilibrium property is \[ \forall{\varepsilon}>0\ \forall s_0\ \exists\sigma\ \exists N\ \forall n\ge N\ \forall i\ \forall\tau_i:\quad \gamma_i^n(s_0,\tau_i,\sigma_{-i}) \le\gamma_i^n(s_0,\sigma)+{\varepsilon}. \] A deviation $\tau_i$ may itself depend on the horizon. Crucially, the same $\sigma$ works for every sufficiently long horizon. Separate finite-horizon equilibria whose strategies change with $n$ do not provide this conclusion.

Formulation and concept references: [S1].

Short English statement

Does every finite stochastic game admit strategies that are approximate equilibria simultaneously for all sufficiently long average-payoff horizons?

Research attempt

Scope, information, and source audit (27 September 2026).

The displayed quantifiers require one strategy profile for all sufficiently large horizons. They do not merely require convergence of finite-horizon equilibrium payoffs. The deviating strategy is allowed to change with the horizon, so a bound proved separately for each fixed deviation is not automatically uniform over deviations.

The catalogue phrase "with the information convention of the game" does not itself specify a monitoring structure. The classical finite stochastic-game problem discussed by the audited sources has publicly observed states and past actions. The concrete subcases and certificates below use that convention, with simultaneous independent behavioral randomizations at a stage. They are not silently extended to hidden-state or arbitrary private-monitoring models. Specifying a different information structure would require a separate formulation audit.

The source [S1] and the primary-author account [E1] distinguish uniform equilibria from discounted, limiting-payoff, and correlated notions. The stationary discounted existence theorem is proved in the author chapter [E2]. A recent paper [E3], revised in January 2026, concerns a promise problem for stationary equilibria in turn-based graph games; its abstract expressly imposes those restrictions. It is not a theorem giving the horizon-uniform behavioral equilibria required here. No inspected source resolves this general selected problem.

The approach is to search for a finite potential-function certificate whose telescoping error is $O(1/n)$ uniformly over all deviations. This works for a substantive class and arises from discounted equilibria if their normalized value differences remain bounded. An explicit Big Match calculation then shows why a naive stationary-limit argument fails.

A complete subcase: transitions independent of the actions.

Suppose $q(s'\mid s,a)=q(s'\mid s)$ for every action profile $a$. At each state $s$, choose a mixed Nash equilibrium $\pi(s)$ of its finite one-stage game. Such equilibria exist by the finite-game Nash theorem. Let each player use this distribution whenever the current state is $s$, independently of the earlier history.

This stationary profile is an exact equilibrium for every finite horizon and every initial state. To prove it, fix a player and any history-dependent deviation. At each reached history with state $s$, opponents' current actions have the fixed product distribution $\pi_{-i}(s)$; the Nash inequality bounds the deviator's conditional expected payoff by the equilibrium stage payoff at $s$. The distribution of the state at each time is independent of all players' actions, so it is the same under the deviation and under $\pi$. Summing the conditional inequalities and taking expectations proves the finite-horizon Nash inequality with zero error. This proof covers horizon-dependent deviations as well.

No mixing or irreducibility of the state chain was used. It may have several absorbing classes. The reason this subcase is simple is that a deviation cannot sacrifice current reward to improve future state visits. That tradeoff returns as soon as the transition kernel depends on actions.

Lemma 451.1: a bias certificate yields a uniform equilibrium.

Let $\pi$ be a stationary mixed profile. Suppose that for each player $i$ there are a real constant $g_i$ and a real function $b_i$ on the finite state set such that for every state $s$ and pure action $a_i$, \begin{equation}\label{wsref-0-61-34-35-31-3a-62-69-61-73-69-6e-65-71} \mathbb E_{a_{-i}\sim\pi_{-i}(s)} \left[r_i(s,a)+\sum_{s'}q(s'\mid s,a)b_i(s')\right] \le g_i+b_i(s), \end{equation} and equality holds after also averaging $a_i\sim\pi_i(s)$. Then, for every initial state, every $n$, and every deviation $\tau_i$, \begin{equation}\label{wsref-0-61-34-35-31-3a-75-6e-69-66-6f-72-6d} \gamma_i^n(s_0,\tau_i,\pi_{-i})-\gamma_i^n(s_0,\pi) \le\frac{\operatorname{osc}(b_i)}n, \quad\operatorname{osc}(b_i)=\max_s b_i(s)-\min_s b_i(s). \end{equation} Thus the same $\pi$ is a uniform $\varepsilon$-equilibrium once $n\ge\max_i\operatorname{osc}(b_i)/\varepsilon$.

Proof. Conditional on any finite history ending at $s_t$, the deviator's randomized action is a mixture of the pure actions in (a451:biasineq). The inequality therefore remains valid for an arbitrary behavioral deviation. Take expectations and sum over $t=1$ through $n$; the bias terms telescope to give \[ n\gamma_i^n(s_0,\tau_i,\pi_{-i}) \le ng_i+b_i(s_0)-\mathbb E_{\tau_i,\pi_{-i}}b_i(s_{n+1}). \] Under $\pi$ the corresponding expression is an equality. Subtracting that equality from the inequality cancels both $ng_i$ and $b_i(s_0)$. The difference of the two terminal expectations is at most $\max b_i-\min b_i$. Divide by $n$ to obtain (a451:uniform). $\square$

The bound is uniform in the entire deviating strategy, including its dependence on $n$. The same argument allows a numerical tolerance: if the upper inequalities have error at most $\delta$ and the prescribed profile's averaged equalities have absolute error at most $\delta$, then the deviation gain is at most $2\delta+\operatorname{osc}(b_i)/n$. This gives a useful certificate for an explicitly specified game. It does not prove that every game has such a stationary certificate.

A concrete two-state certificate.

Let the states be $0,1$. At state $0$, one player chooses either "wait" or "move"; wait keeps the state at zero and pays zero, while move pays zero and moves to state one. At state one there is only one action, which pays one and keeps the state at one. Other players may be added with singleton action sets and identically zero payoffs.

Choose the profile that moves immediately. For the active player set $g=1$, $b(0)=-1$, $b(1)=0$. At state zero the move expression in (a451:biasineq) is zero, equal to $g+b(0)$; the wait expression is $-1$, which is smaller. At state one both sides equal one. Thus the certificate holds and its oscillation is one. In fact moving immediately is exactly optimal in every finite horizon; the certificate gives the weaker but sufficient bound $1/n$ without needing to analyze all stopping rules individually. This example checks the sign of the terminal bias and the normalization of average payoffs.

Lemma 451.2: a sufficient bounded-span route from discounting.

Normalize discounted payoffs as $\lambda\mathbb E\sum_{t\ge1}(1-\lambda)^{t-1}r_i(s_t,a_t)$, where $0<\lambda<1$. For each $\lambda$, choose a stationary discounted equilibrium $\pi^\lambda$ valid from every state, with value vector $v_i^\lambda(s)$. The existence theorem used here is [E2]. Fix a reference state $s_*$ and suppose, along a sequence $\lambda\downarrow0$, the functions \begin{equation}\label{wsref-0-61-34-35-31-3a-6e-6f-72-6d-61-6c-69-7a-65-64-62-69-61-73} b_i^\lambda(s)= \frac{v_i^\lambda(s)-v_i^\lambda(s_*)}{\lambda} \end{equation} are uniformly bounded for every player and state. Then the game has a stationary profile satisfying Lemma 451.1.

Proof. Against fixed stationary opponents, a discounted best response has the Bellman optimality inequalities. At the equilibrium, for every pure $a_i$, \[ v_i^\lambda(s)\ge \mathbb E_{\pi_{-i}^\lambda(s)} \left[\lambda r_i(s,a)+(1-\lambda) \sum_{s'}q(s'\mid s,a)v_i^\lambda(s')\right], \] with equality when also averaging the equilibrium action. Write $g_i^\lambda=v_i^\lambda(s_*)$ and substitute $v_i^\lambda(s)=g_i^\lambda+\lambda b_i^\lambda(s)$. Cancel $g_i^\lambda$, divide by $\lambda$, and rearrange to obtain \[ g_i^\lambda+b_i^\lambda(s)\ge \mathbb E_{\pi_{-i}^\lambda(s)} \left[r_i(s,a)+(1-\lambda)\sum_{s'}q(s'\mid s,a)b_i^\lambda(s')\right]. \] The payoffs are bounded, hence so are the $g_i^\lambda$. The strategy simplices are compact, and the normalized biases are bounded by hypothesis. Take a common convergent subsequence of all finitely many coordinates. Continuity of the finite sums and products gives (a451:biasineq) and its averaged equalities at the limit. $\square$

Boundedness of $v_i^\lambda$ alone does not give the hypothesis: division by $\lambda$ in (a451:normalizedbias) matters. For example two absorbing states paying zero and one have respective normalized values zero and one for every $\lambda$, so the bias difference grows like $1/\lambda$. That game trivially has a uniform equilibrium, showing that the bounded-span condition is a sufficient route, not a necessary condition for the catalogue conclusion. A general proof cannot simply assume all states have one common limiting gain $g_i$.

The Big Match: an exact obstruction to stationary limits.

Consider a two-player zero-sum game with one active state. Player 1 maximizes the displayed payoff and chooses $T$ or $B$; player 2 minimizes it and chooses $L$ or $R$. The transitions and stage payoffs are \[ \begin{array}{c|cc} &L&R\\\hline T&1\text{, absorb forever at }1&0\text{, absorb forever at }0\\ B&0\text{, remain active}&1\text{, remain active}. \end{array} \] Absorbing payoffs apply from the current stage onward. This is the classical Big Match mechanism discussed in [E1]; the finite-horizon calculation below is explicit.

Let $V_n$ be its $n$-stage total-payoff value from the active state and $V_0=0$. At the first stage, followed by optimal play, the matrix is \[ \begin{pmatrix}n&0\\V_{n-1}&V_{n-1}+1\end{pmatrix}. \] If player 1 selects $T$ with probability $1/(n+1)$, both column payoffs are $n(V_{n-1}+1)/(n+1)$. Conversely the minimizing mixture equalizes the two rows. Induction yields \begin{equation}\label{wsref-0-61-34-35-31-3a-62-69-67-6d-61-74-63-68-76-61-6c-75-65} V_n=n/2, \qquad\Pr(T\mid n\text{ stages remain})=\frac1{n+1}, \qquad\Pr(L)=\frac12. \end{equation} The row equalization is valid with $V_{n-1}=(n-1)/2$ and gives $\Pr(L)=(V_{n-1}+1)/(n+1)=1/2$. These mixtures establish both inequalities needed for the value, rather than only a lower bound.

Now fix a stationary strategy of player 1, quitting with probability $q$ whenever active. If $q=0$, player 2 always chooses $L$, and every payoff is zero. If $q>0$, player 2 always chooses $R$. Payoff is then one only on stages before the first quit; its expected total up to time $n$ is at most $1/q$. Hence the expected average is at most $1/(nq)$ and tends to zero. Thus no stationary maximizing strategy guarantees even a fixed positive average for all large horizons, although every finite-horizon value is $1/2$.

This gives an equilibrium obstruction too. In a zero-sum $\varepsilon$-equilibrium of the $n$-stage game, the profile payoff $u_n$ satisfies $u_n\ge V_n/n-\varepsilon$, since a maximizing best response to the given opponent guarantees at least the value. The minimizer's equilibrium inequality then forces the given maximizing strategy to guarantee at least $u_n-\varepsilon\ge1/2-2\varepsilon$. For $\varepsilon<1/4$, the stationary strategy test contradicts this requirement at sufficiently large $n$. General history dependence is therefore essential to a general existence argument.

A compact strategy space does not repair that example.

Extend the finite-horizon equilibrium strategies in (a451:bigmatchvalue) arbitrarily beyond their specified horizon. For any fixed finite history in the active state, the number of stages remaining tends to infinity as the original horizon grows. Thus the maximizer's probability of quitting tends to zero at every such history. The minimizing strategy remains the fair $L/R$ mixture. The profiles converge coordinatewise to "always continue" against "mix fairly".

That limit gives average payoff $1/2$ at every horizon, but the minimizing player can switch to always $L$ and reduce it to zero. It is not an $\varepsilon$-equilibrium for any $\varepsilon<1/2$. This is a concrete failure of the argument "choose finite-horizon equilibria, take a compact subsequence, and pass the equilibrium inequalities to the limit." Payoffs on a fixed prefix are continuous in those coordinates; the unbounded-horizon objective is not controlled uniformly by any fixed prefix. The example is not a counterexample to the catalogue problem: it belongs to a class with known history-dependent uniform strategies.

A uniform average guarantee does imply a patient discounted one.

There is a valid implication in the other direction, with the same strategy profile. For any bounded expected reward sequence, write $A_n=n^{-1}\sum_{t=1}^n r_t$. An absolutely convergent rearrangement gives \begin{equation}\label{wsref-0-61-34-35-31-3a-61-62-65-6c} \lambda\sum_{t\ge1}(1-\lambda)^{t-1}r_t =\sum_{n\ge1}\lambda^2n(1-\lambda)^{n-1}A_n. \end{equation} The coefficients on the right are nonnegative and sum to one. If a profile's average-payoff deviation gains are at most $\varepsilon$ for every $n\ge N$, and stage payoffs have absolute value at most $R$, then every discounted deviation gain is at most \[ \varepsilon+2R\sum_{n<N}\lambda^2n(1-\lambda)^{n-1} \le\varepsilon+R\lambda^2N(N-1). \] The bound holds uniformly over all deviations. Thus the same profile works for all sufficiently small discount parameters with an arbitrarily small additional error. This calculation does not reverse the implication for a family of discounted equilibria whose strategies change with $\lambda$. Lemma 451.2 gives one explicit extra condition under which such a limit argument is valid.

Verification and outcome.

The companion exact-arithmetic script verifies the Big Match recursion and equalizing mixtures for a range of horizons, its stationary-strategy adversarial bounds, the two-state bias certificate, and the Abel weights. It also checks a finite-profile example of the telescoping cancellation. The computations do not infer a uniform equilibrium from convergence of finitely many equilibrium values.

Outcome: UNRESOLVED. The attempt proves the action-independent transition subcase, a finite bias certificate giving a quantitative uniform bound, and a conditional discounted-limit theorem. It explicitly refutes a naive stationary or compactness shortcut. The first missing general step is to construct suitable history-dependent strategies, or an equally strong uniform deviation certificate, when action-dependent transitions and several strategic players defeat the bounded-bias route.

Sources

• S1 Math Conjectures, GAME-001, catalog snapshot 31 July 2026. https://mathconjectures.com/conjectures/GAME-001. Formulation source.
• E1 Eilon Solan and Nicolas Vieille, Stochastic games, Proceedings of the National Academy of Sciences 112 $2015$, 13743--13746, Sections 1 and 3--4. https://pmc.ncbi.nlm.nih.gov/articles/PMC4653174/. Primary-author account inspected 27 September 2026 for information conventions and distinctions among equilibrium concepts.
• E2 Sylvain Sorin, Discounted stochastic games: the finite case, in Stochastic Games and Applications $2003$, Theorem 2. https://perso.imj-prg.fr/sylvain-sorin/wp-content/uploads/sorin-pub/03.Stoc05.pdf. Author-hosted proof of stationary discounted existence inspected 27 September 2026; discounting is not replaced by a uniform-horizon claim.
• E3 Ali Asadi, Léonard Brice, Krishnendu Chatterjee, and K. S. Thejaswini, $\varepsilon$-Stationary Nash Equilibria in Multi-player Stochastic Graph Games, arXiv:2508.15356v2, 26 January 2026. https://arxiv.org/abs/2508.15356. Primary abstract and version history inspected 27 September 2026; turn-based, stationary, and promise hypotheses retained.