Equilibrium payoffs in finite multiplayer stochastic games

Research attempt: C73-1 Equilibrium existence in finite multiplayer stochastic games

Scope of this report. The main target remains UNRESOLVED. Fully proved subclaims and counterexamples are identified locally. Computational checks reported here are supplementary to the proofs. Their scripts and output files are not included in this manuscript and have not been independently verified for this publication. No novelty or priority claim is made.

FORMAL RESTATEMENT

A game $G$ has a finite nonempty player set $I$, a finite nonempty state set $S$, finite nonempty action sets $A_i(s)$, transition probabilities $P(s'\mid s,a)$, and rewards $g_i(s,a)$ with $|g_i(s,a)|\leq M<\infty$. States and joint actions are public. Behavioral strategies assign independent mixed actions at each finite public history; no mediator is present. Starting at $s$, write \[ \gamma_i^N(s,\sigma)={\mathbb{E}}_{s,\sigma}\frac1N\sum_{t=1}^Ng_i(s_t,a_t),\qquad \gamma_i^\lambda(s,\sigma)={\mathbb{E}}_{s,\sigma}\sum_{t\geq1}\lambda(1-\lambda)^{t-1}g_i(s_t,a_t). \] Let $u_i^{\rm path}={\mathbb{E}}[\liminf_N N^{-1}\sum_{t\leq N}g_i]$ and $u_i^{\rm exp}=\liminf_N\gamma_i^N$. These are bounded but distinct. The mean evaluation $\lim_N\gamma_i^N$ is defined only when that limit exists.

The main Cesàro assertion is \[ \forall G\ \exists v\in\mathbb R^{I\times S}\ \forall\varepsilon>0\ % \exists\sigma^\varepsilon,N_\varepsilon\ \forall s\in S,\ i\in I,\ N\geq N_\varepsilon,\ \forall\tau_i: \] \[ |\gamma_i^N(s,\sigma^\varepsilon)-v_i(s)|\leq\varepsilon, \quad \gamma_i^N(s,\tau_i,\sigma_{-i}^\varepsilon) -\gamma_i^N(s,\sigma^\varepsilon)\leq\varepsilon. \] The joint version additionally requires a $\lambda_\varepsilon>0$ and the same two inequalities with $\gamma^\lambda$ for all $0<\lambda\leq\lambda_\varepsilon$, using the same profile and vector. Analogous approximate-equilibrium-payoff assertions for $u^{\rm path}$ and $u^{\rm exp}$ must be distinguished. For the mean version, a minimally precise convention requires convergence on the proposed profile and on all deviations against which its equilibrium inequality is asserted; alternatively one can explicitly replace the deviating criterion by a limsup. These conventions are not automatically interchangeable.

For the separate finite-deviation selection question, define \begin{align*} m_i(s)&=\inf_{\rho_{-i}}\sup_{\tau_i}u_i^{\rm path}(s,\tau_i,\rho_{-i}),\\ V_i^\sigma(h)&=u_i^{\rm path}(s_h,\sigma\text{ continued after }h),\\ A(\sigma)&=\sup_{i,h}[m_i(s_h)-V_i^\sigma(h)]_+,\\ R_N(\sigma)&=\max_i\sup_{\tau_i} \left[u_i^{\rm path}(s_0,\tau_i\star_N\sigma_i,\sigma_{-i}) -u_i^{\rm path}(s_0,\sigma)\right]. \end{align*} Here $\star_N$ permits a deviation for the first $N$ stages and then returns to the prescribed strategy at the actually reached history. The target is $\forall G,s_0,\eta>0\ \exists\sigma$ with $A(\sigma)\leq\eta$ and $\sup_NR_N(\sigma)\leq\eta$.

Hygiene and corrections.

Finite histories include off-equilibrium histories with possible transitions. Ordinary initial-state equilibrium is different from subgame perfection. A stationary strategy depends only on the current state; a time-dependent Markov strategy may also depend on the date; a finite-memory strategy uses a specified finite internal state. No finite-memory bound is assumed. The problem statement describes joint Cesàro--discounted existence as stronger; below it is proved equivalent to Cesàro existence under these bounded-payoff quantifiers.

QUICK LITERATURE/CONTEXT CHECK

Flesch and Solan's general bounded-Borel stochastic-game theorem gives minmax-acceptable profiles in every subgame, extensive-form correlated approximate equilibria, and an approximate equilibrium in some subgame [c731-fs]. These are not ordinary equilibrium from an arbitrary prescribed state. Their Theorem 4.4, used explicitly below, concerns independent behavioral profiles and the same minmax order as in the problem statement. Theorem 4.9's favorable subgame may depend on the accuracy. No claim that those results solve the main uniform problem is made. Sources checked through 9 October 2026.

ATTACK PLAN

Proof strategies.

First, eliminate an unnecessary evaluation distinction through an exact Abel mixture. Second, prove a stationary gain-and-bias certificate and identify a class where it is always feasible. Third, combine subgame acceptability with finite backward induction and test the infinite-selection step.

Disproof strategies.

Test expectation/liminf interchange with random long blocks; test stationary sufficiency with an explicit absorbing game; and test compactness of acceptable profiles by delaying absorption. These give genuine counterexamples to intermediate claims without purporting to disprove unrestricted approximate existence.

Landscape and tools.

This is dynamic non-zero-sum game theory. Abel summation converts evaluations; finite-state gluing handles initial states; gain/bias inequalities telescope arbitrary deviations; bounded supermartingale convergence controls long-run state values; martingale concentration controls sample averages; finite Markov-chain linear algebra constructs bias functions; Nash's theorem solves each finite continuation game; and product-topology compactness reveals the precise missing continuity property.

WORK

Cesàro and discounted existence have the same quantifiers

Two further valid implications.

The Cesàro assertion implies its $u^{\rm exp}$ counterpart: take a liminf of the eventual on-payoff and incentive inequalities for the same profile. Specifically, eventual $\gamma^N(\tau_i,\sigma_{-i})\leq\gamma^N(\sigma)+\varepsilon$ implies the corresponding liminf inequality. Separately, ordinary existence for each individual initial state implies ordinary existence with a common profile for all states: select one profile for each of the finitely many initial states, follow the selected profile on histories bearing that initial state, and take the largest finite threshold and smallest positive discount threshold. This construction remembers the initial state; it proves neither stationary existence nor subgame perfection.

A stationary gain-and-bias certificate

For a stationary independent profile $x$, write $P^{a_i,x_{-i}}$ for the transition matrix with player $i$ using $a_i$ in the current state and the others using their prescribed mixed actions. For a state vector $h$, let $\operatorname{sp}(h)=\max_sh(s)-\min_sh(s)$.

Finite-deviation selection: a proved finite version and its exact limit gap

We explicitly use the following published theorem, rather than claiming to reprove its Borel determinacy ingredients.

Imported theorem (Flesch--Solan, Theorem 4.4). In a stochastic game with finitely many players and actions, a finite or countable state space, and bounded Borel payoffs, for each $\eta>0$ there is an independent behavioral profile whose continuation payoff in every subgame is at least each player's minmax in that subgame minus $\eta$.

The present finite-state game meets those hypotheses. The path-liminf payoff is Borel, as a liminf of cylinder functions, bounded by $M$, and invariant under removal of a finite prefix. Consequently its subgame minmax is $m_i(s_h)$. Thus the imported theorem supplies profiles with $A\leq\eta$, without an equilibrium guarantee.

Why the compactness step fails.

Consider one effective player, with dummy players added if desired, in a state where waiting yields zero and quitting moves to an absorbing payoff of 1. Let $\sigma^H$ wait until absolute date $H$ and quit at every surviving history of date at least $H$. Every continuation eventually receives terminal and path-average payoff 1, so $A(\sigma^H)=0$ and no deviation improves it. In the product topology of behavioral strategies, $\sigma^H$ converges to never quitting as $H\to\infty$: at every fixed finite history it eventually prescribes wait. The limit has payoff zero and $A=1$. Hence even these exact-equilibrium acceptable profiles need not form a closed set. Sequential compactness of strategy space does not preserve the needed inequalities.

Two explicit adversarial counterexamples to stronger claims

Expectation and liminf cannot be interchanged.

In a one-state, one-player game with rewards equal to its action in $\{0,1\}$, partition time into deterministic blocks of lengths $L_k=2^{2^k}$, $k\geq1$. At the beginning of each block draw an independent fair bit and use that action throughout the block. This is a behavioral strategy using only the player's own recorded action. Every stage has expected payoff $1/2$, so $u^{\rm exp}=1/2$. Independently chosen zero bits occur in infinitely many blocks almost surely; at the end of such blocks the average is at most $\sum_{j<k}L_j/\sum_{j\leq k}L_j$, which tends to zero. Rewards are nonnegative, so the pathwise liminf is zero and $u^{\rm path}=0$. One bits similarly force limsup one. This is a counterexample to an evaluation identity, not to equilibrium existence.

VERIFICATION

The reported computation checks 36 rational Abel identities for finite reward strings followed by a constant tail, as well as elementary exogenous-transition and geometric-absorption examples. Pseudocode forms the discounted sum and its Cesàro mixture with the infinite constant tail summed exactly, and compares rational expressions. The independent block example and stationary counterexample above are proved analytically, not inferred from simulation.

The certificate requires two separate inequalities; omitting the gain inequality permits a deviator to move to more valuable states and breaks telescoping. Finite-state gluing retains the initial state in the history and must not be called stationary. The finite-prefix theorem proves $\forall H\,\exists\sigma^H$, not $\exists\sigma\,\forall H$. It treats all finite deviations up to a fixed length simultaneously, but the waiting example prevents a naive closed-set argument. Conditional and unconditional expectations were not interchanged with pathwise liminf. The imported acceptable-profile theorem is explicitly identified; all other reductions are proved in this report.

FINAL

LABEL: UNRESOLVED for unrestricted ordinary uniform existence, the unrestricted path-liminf target, and the all-prefix selection assertion. The report does not claim that every refinement remains an open question in the literature.

Solved subclaims and strongest partial results.

Cesàro existence is equivalent to joint Cesàro--discounted existence. Exogenous-transition games admit the stationary certificate, yielding uniform and exact long-run subgame-perfect equilibria. For every fixed $H$, acceptability can be combined with zero gain from every deviation of length at most $H$. The universal stationary restrictions are disproved by the explicit $1/3$-regret game; the general history-dependent assertions are not disproved by it.

Exact first gap.

For the finite-deviation route, the missing statement is: for each $\eta>0$, one can choose a single acceptable profile with $R_N\leq\eta$ for every $N$. The finite-prefix theorem and strategy compactness do not prove this. For unrestricted uniform existence, no argument establishes the gain-and-bias certificate or a valid substitute in an arbitrary action-dependent game. These are separate gaps, not asserted equivalent reformulations.

Three next moves.

(1) Seek a closed compact family of acceptable continuation payoff systems with an explicit no-loss-at-infinity condition. (2) Develop an action-dependent, history-dependent replacement for the gain/bias certificate whose telescoping error is uniform over all deviations. (3) Test finite action-dependent examples with deliberately delayed absorption for a certified positive lower bound on unrestricted regret, rather than merely stationary regret.

Likely obstruction structure.

Any counterexample to the certificate-covered class must have strategically relevant transitions. A counterexample to unrestricted existence would also have to resist arbitrary history dependence; the small absorbing stationary counterexample does not do so. A failed infinite-selection construction can already exhibit escape of absorption times to infinity in a one-effective-player model.

References

• [c731-fs] J. Flesch and E. Solan. Stochastic Games with General Payoff Functions. Mathematics of Operations Research 49 (2024), 1349--1371. arXiv:2208.12096, Theorems 4.4 and 4.9. https://arxiv.org/html/2208.12096v1. https://doi.org/10.1287/moor.2023.1385.

Completion Estimate

35%

Problem ID: C73-1 Model: GPT 6 Astra Pro Version: 2

Status: Unresolved for the complete catalogue problem; this manuscript records partial results and research attempts.

Uniform Equilibrium in Finite Stochastic Games Partial Results, a Four-Player Quitting-Game Audit, and Obstructions to General Proof Strategies

Abstract

Does every stochastic game with finitely many players, states, and actions admit a uniform Nash equilibrium payoff? This note consolidates a sequence of proof and counterexample attempts, but does not settle that open question. It records two sufficient verification devices: a survival-weighted Bellman-defect criterion for quitting games and a continuation-potential certificate for general finite stochastic games. It proves a local-degree sufficient condition yielding stationary uniform approximate equilibria for a class of quitting games, and applies it to disqualify a previously proposed four-player counterexample matrix for every completion of its simultaneous-quitting payoffs. The matrix audit includes exact complementary-support calculations and an explicit rational stationary equilibrium for one completion. Two unsuccessful general approaches are explained rigorously: predetermined schedules of stationary discounted equilibria fail even in the Big Match, and minmax-acceptable profiles cannot in general be enforced merely by post-deviation punishments. Continuous absorption-path screening and the remaining index-one regime are clearly identified as unresolved, not as proofs of nonexistence. The arguments collected here have not undergone independent peer review; no originality or priority claim is asserted for them.

Status and scope. As of the date above, neither a proof of universal uniform-equilibrium existence nor a finite counterexample is presented here. Statements explicitly marked as a theorem, proposition or lemma are proved in this note; externally established results are cited; computational and heuristic observations are labelled separately.

The open problem and precise definitions

A finite stochastic game consists of a finite player set $I=\{1,\dots,n\}$, a finite state set $S$, finite nonempty action sets $A_i(s)$, bounded stage payoff functions $g_i(s,a)$, and a transition kernel $P(\cdot\mid s,a)\in\Delta(S)$. Stages are simultaneous move; states and past action profiles are publicly observed (perfect monitoring). A behavioral strategy $\sigma_i$ maps every finite public history ending in state $s$ to $\Delta(A_i(s))$. Under initial state $s$ and profile $\sigma$, let \[ \gamma_i^N(s,\sigma)={\mathbb{E}}_{s,\sigma}\left[\frac1N\sum_{t=1}^{N}g_i(s_t,a_t)\right]. \]

The main question is whether every game of this kind has such a vector $v$. It is important not to conflate this statement with existence of Nash equilibria for each fixed discount factor, a single limiting-average Nash equilibrium, exact ($\varepsilon=0$) equilibrium, subgame-perfect equilibrium, or a correlated/sunspot equilibrium. Two-player finite stochastic games and a range of structured multiplayer cases have positive results; the unrestricted multiplayer question remains unresolved in the sources consulted [sv2001,akrs2024,aps2026,sv2025]. Two- and three-player quitting games have positive results, whereas the corresponding general existence question for four or more players is expressly discussed as unresolved in [aps2026].

Quitting games and the payoff convention

A standard $n$-player quitting game has a single nonabsorbing state, with actions $C_i$ (continue) and $Q_i$ (quit) for every player. If the first nonempty set of quitters is $T\subseteq I$, the state becomes absorbing with perpetual stage payoff $r(T)\in{\mathbb{R}}^n$; prior to absorption the common stage-payoff vector is $b\in{\mathbb{R}}^n$. If nobody ever quits, the stage payoff remains $b$. All $2^n-1$ nonempty quitting sets have separate terminal payoff vectors. Write $\theta$ for the absorption stage, with $\theta=\infty$ if no quit ever occurs.

The terminal-payoff functional is \begin{equation}\label{wsref-0-65-71-3a-74-65-72-6d-69-6e-61-6c-2d-66-75-6e-63-74-69-6f-6e-61-6c} \Gamma_i^\infty(\sigma)={\mathbb{E}}_\sigma\left[r_i(T_\theta){\mathbf{1}}_{\{\theta<\infty\}}+b_i{\mathbf{1}}_{\{\theta=\infty\}}\right]. \end{equation} An approximate equilibrium for (eq:terminal-functional) is not, without additional tail control, automatically a uniform equilibrium for the $N$-stage averages. Sections sec:weighted and sec:index establish the required tail estimates explicitly. Whenever singleton quits are under discussion, subtracting the constant $r_i(\{i\})$ from every payoff of player $i$ permits the normalization \begin{equation}\label{wsref-0-65-71-3a-6e-6f-72-6d-61-6c-69-7a-65} r_i(\{i\})=0,\qquad M_{ij}:=r_i(\{j\}). \end{equation} Here the $j$th column of $M$ is the payoff vector when player $j$ quits alone. If these four vectors are displayed as rows of a matrix $R$, then $M=R^{\mathsf T}$.

Established approaches and the small unresolved core

The equilibrium-existence theory for two-player stochastic games, zero-sum stochastic games, and many special classes is extensive; see the bibliography of [akrs2024,sv2025]. We rely here on the following narrower assertions, with references tied to each statement.

• Solan and Vieille [sv2001] obtain uniform approximate equilibria for quitting games satisfying additional assumptions, and [sv2002example] exhibits a four-player game whose simplest equilibrium uses a two-stage cycle.
• Solan and Solan [solansolan2020] prove that every quitting game has sunspot approximate equilibria; they also establish uniform ordinary approximate equilibria under a non-$Q$-matrix condition on the relevant complementarity matrix.
• Ashkenazi-Golan, Krasikov, Rainer, and Solan [akrs2024] compactify quitting strategies by absorption paths, which allow both continuous small-hazard segments and discrete jumps. Sequentially perfect absorption paths characterize approximate terminal equilibria in the precise formulation of their article.
• The APS paper [aps2026] studies a restricted family of paths (SFAPs) and its associated successor graph and operators; emptiness of that subclass does not establish absence of all equilibria.
• Solan and Vieille [sv2025] prove an existence theorem for positive recursive absorbing games subject to an explicitly nonrectangular absorption structure, rather than for all finite stochastic games.
• Solan and Vieille [solanvieille2002corr] establish uniform correlated equilibrium payoffs with an autonomous correlating device. Correlation and public sunspots are stronger information resources than the independent randomization permitted in the original Nash problem.

A negative example among four-player quitting games would settle the original problem negatively, but a proof for quitting games alone would not settle arbitrary finite stochastic games positively. This distinction guides both the matrix and the general-game approaches below.

A survival-weighted Bellman-defect criterion

The first attempt replaced a global fixed point by small one-stage incentive defects accumulated along surviving paths. This section states a precise sufficient criterion; it is not an unconditional construction.

For this section only, assume the nonabsorbing payoff is $b=0$ and $|r_i(T)|\le L$ for every $i$ and nonempty $T$. A strategy in a standard quitting game, conditional on survival to stage $t$, is a vector $p_t=(p_{1,t},\dots,p_{n,t})\in[0,1]^n$. For any player $i$ put \[ \mu_{-i,t}(T)=\prod_{j\in T}p_{j,t} \prod_{\substack{j\notin T\\j\ne i}}(1-p_{j,t}),\quad T\subseteq I\setminus\{i\}. \] Assume the eventual absorbing payoff is well defined under the prescribed profile, and let $u_{i,t}$ be its conditional expectation given survival to $t$. Define the values of quitting now and of continuing for exactly one stage followed by the prescribed strategy: \begin{align} Q_{i,t}&=\sum_{T\subseteq I\setminus\{i\}}\mu_{-i,t}(T)r_i(T\cup\{i\}),\label{wsref-0-65-71-3a-71-2d-73-74-61-67-65}\\ C_{i,t}&=\sum_{\varnothing\ne T\subseteq I\setminus\{i\}}\mu_{-i,t}(T)r_i(T) +\mu_{-i,t}(\varnothing)u_{i,t+1}.\label{wsref-0-65-71-3a-63-2d-73-74-61-67-65} \end{align} By the prescribed mixing rule, \[ u_{i,t}=p_{i,t}Q_{i,t}+(1-p_{i,t})C_{i,t}. \] Set \begin{equation}\label{wsref-0-65-71-3a-64-65-66-65-63-74} d_{i,t}=\max\{Q_{i,t},C_{i,t}\}-u_{i,t}\ge0,\quad \rho_{i,1}=1,\quad \rho_{i,t}=\prod_{k<t}\mu_{-i,k}(\varnothing). \end{equation} The number $\rho_{i,t}$ is the chance that all opponents of $i$ have continued through stage $t-1$, independent of what $i$ does.

If $d_{i,t}=0$, the stagewise complementary-slackness conditions are \[ \begin{array}{ccl} p_{i,t}=0&\Longrightarrow&C_{i,t}\ge Q_{i,t},\\ 0<p_{i,t}<1&\Longrightarrow&C_{i,t}=Q_{i,t},\\ p_{i,t}=1&\Longrightarrow&Q_{i,t}\ge C_{i,t}. \end{array} \] The missing implication is universal existence of sequences satisfying arbitrarily small $D_i$ and the tail condition. The criterion should be treated as a verification tool, not as a solution of the open problem.

Four-player counterexample search: unsuccessful candidates

Empty restricted path classes do not show nonexistence

A four-player singleton-payoff matrix occurring in the precursor discussion of the APS method [apslecture, Example 3.5] is \begin{equation}\label{wsref-0-65-71-3a-52-7a-65-72-6f} R_0=\begin{pmatrix} 0&4&-\frac12&-1\\ -1&0&3&1\\ -\frac18&-1&0&4\\ 4&\frac12&-1&0 \end{pmatrix}. \end{equation} That source establishes emptiness of a restricted path-payoff class, not nonexistence of ordinary uniform equilibrium. The initial search overlooked this logical distinction. As a further finite calculation, for $M_0=R_0^{\mathsf T}$, the LCP with \[ q=(-4,-4,-4,-1)^{\mathsf T} \] has no solution: on each of its sixteen possible positive supports, the complementary equations are either inconsistent or fail nonnegativity. Therefore $M_0$ is not a $Q$-matrix. The non-$Q$ theorem of [solansolan2020], with its associated normal-player reduction, supplies a positive existence result in this setting. In particular, a restricted-path obstruction cannot be presented as a four-player counterexample.

A stronger proposed matrix and its heuristic continuous-path test

The subsequent search proposed \begin{equation}\label{wsref-0-65-71-3a-52-64-61-67} R^\dagger=\begin{pmatrix} 0&6&-3&-5\\ 6&0&3&-4\\ -2&4&0&3\\ 4&-2&3&0 \end{pmatrix},\qquad M^\dagger=(R^\dagger)^{\mathsf T}. \end{equation} Its singleton sign graph frustrates various one-quitter-at-a-time constructions. There was also a tentative continuous-path calculation: for a nonnegative absolutely continuous curve \[ X(u)=\int_0^u\alpha(t)R^\dagger\,dt, \quad \alpha(t)\in\Delta(I), \quad \alpha_i(t)>0\ \Longrightarrow\ X_i(t)=0\ \text{a.e.}, \] absolute continuity implies $X_i'(t)=0$ for almost every $t$ at which $X_i(t)=0$. Writing $A(t)={\operatorname{supp}}\alpha(t)$ then forces \[ \alpha_{A(t)}(t)^{\mathsf T}R^\dagger_{A(t),A(t)}=0\quad\text{a.e.} \] Since all principal submatrices of order at least two are nonsingular, $\alpha(t)$ must be concentrated on at most one player almost everywhere.

Scope warning: these hypotheses describe a simplified absolutely continuous part of an absorption-path model, not the full definition of a sequentially perfect absorption path. Switching on accumulation sets and especially discrete absorption jumps are not excluded by this calculation. The earlier claim of an almost-complete counterexample proof was unjustified. In fact, the next section gives a stronger, decisive positive result: the entire $R^\dagger$ family has uniform equilibrium payoffs, regardless of its completion.

A local-degree theorem ruling out the proposed matrix

This is the principal positive contribution of the audit. The argument is elementary apart from standard properties of Brouwer degree [gowda2016]. The theorem concerns all numbers of players; the worked certificate concerns four players.

The complementarity map and global projected degree

For a normalized singleton matrix $M\in{\mathbb{R}}^{n\times n}$ let \[ \phi_M(z):=\min\{z,Mz\} \] coordinatewise. We call $M$ an $R_0$-matrix when $\phi_M^{-1}(0)=\{0\}$. By positive homogeneity, the local degree \[ d(M):=\deg(\phi_M,B_\rho(0),0) \] is defined and independent of $\rho>0$.

Exact four-player index certificate

For $M^\dagger=(R^\dagger)^{\mathsf T}$, all principal determinants of orders two, three, and four are nonzero: An $R_0$-violating homogeneous LCP solution supported on $S$ with $|S|\ge2$ would give $M^\dagger_{SS}z_S=0$, contradicting nonsingularity. A singleton support is impossible because every column of $M^\dagger$ has a negative entry. Thus $M^\dagger$ is $R_0$.

For $q=(1,1,1,1)^{\mathsf T}$, exact enumeration of all sixteen complementary supports yields precisely the following strictly complementary solutions of $z\ge0$, $w=M^\dagger z+q\ge0$, $z_iw_i=0$:

The signs are those of $\det M^\dagger_{SS}$. Homotopy from $q$ to $0$ has bounded zeros by the $R_0$ property, hence \begin{equation}\label{wsref-0-65-71-3a-6e-65-67-64-65-67-72-65-65} d(M^\dagger)=1-1-1=-1. \end{equation} Players $1,2,3,4$ receive negative singleton payoffs, respectively, from opponents $3,4,1,1$, with values $-2,-2,-3,-5$. We conclude:

In particular the earlier conjectured counterexample was not a counterexample. A simpler special-case oversight is worth recording: if $b=0$ and $r_i(\{i\})=0$, always continuing is an exact equilibrium at every finite horizon, since any sole quitter receives zero.

A complete rational equilibrium for one completion

One proposed join-incentive matrix was \[ A=\begin{pmatrix} 0&-3&-2&1\\3&0&3&-3\\-2&-2&0&-3\\-2&3&2&0 \end{pmatrix}. \] It does not, without an additional rule, define the eleven simultaneous-quit payoffs. A concrete completion is \begin{equation}\label{wsref-0-65-71-3a-63-6f-6d-70-6c-65-74-69-6f-6e} r_i(T)=\sum_{j\in T\setminus\{i\}} \left(R^\dagger_{ji}+{\mathbf{1}}_{\{i\in T\}}A_{ij}\right),\qquad \varnothing\ne T\subseteq I, \qquad b=(-1,-1,-1,-1). \end{equation} For this game, \[ x=\left(\frac57,0,0,\frac45\right) \] is an exact stationary Nash equilibrium of the terminal-payoff game. Conditional on absorption, the quit sets $\{1\}$, $\{4\}$, $\{1,4\}$ have probabilities $5/33$, $8/33$, $20/33$. Their payoff vectors are $(0,6,-3,-5)$, $(4,-2,3,0)$, $(5,4,0,-7)$, giving \begin{equation}\label{wsref-0-65-71-3a-65-78-70-6c-69-63-69-74-70-61-79-6f-66-66} V(x)=\left(4,\frac{94}{33},\frac3{11},-5\right). \end{equation} All unilateral stopping incentives can be checked exactly: The minimum opponent hazard is $a_*=5/7$, and one may take $L=16$. Equation (eq:uniformbound) therefore gives the explicit bound \[ \sup_{\tau_i}\left[\gamma_i^N(\tau_i,x_{-i})-\gamma_i^N(x)\right]\le\frac{448}{5N}. \] Thus the same stationary profile is a uniform $\varepsilon$-equilibrium whenever $N\ge\lceil448/(5\varepsilon)\rceil$. The finite-horizon inequalities are approximate, not a claim of exact Nash equilibrium for every finite horizon.

Where the degree argument stops

Within the $R_0$ and negative-incoming class of Theorem Theorem (Degree-based sufficient condition), a counterexample must satisfy \[ \boxed{d(M)=1.} \] This condition is necessary only within that class, not for all quitting games. A concrete degree-one example is \begin{equation}\label{wsref-0-65-71-3a-4d-6f-6e-65} M_1=\begin{pmatrix} 0&3&-1&-1\\3&0&-1&-1\\-1&-1&0&3\\-1&-1&3&0 \end{pmatrix}. \end{equation} It is $R_0$; at $q=(1,1,1,1)$ its exact LCP index sum is $1-4+4=1$. This is the singleton matrix associated with the Solan--Vieille four-player period-two example [sv2002example]. Its existence of a nonstationary equilibrium makes the central point: failure of stationary methods is not failure of uniform equilibrium. Degree one offers no nonzero-root conclusion by the present global-local index comparison.

A general-game verification theorem using continuation potentials

We next abandon quitting-game structure. A public history $h_t$ includes its stage and current state. For a prescribed profile $\sigma$, let $r_i(h,a_i,\sigma_{-i}(h))$ denote the expected current stage payoff if player $i$ uses pure action $a_i$ while opponents follow $\sigma$, and let $h^+$ be the random next public history. (Expectations below include transition and opponents' randomization.)

This supplies a sufficient certificate for a uniform equilibrium when $\eta\downarrow0$, with initial targets $G_i(h_1)$ converging to one payoff vector for all states. The hard unsolved step is jointly constructing the same independent strategy profile and the supermartingale/sublinear-correction functions for every player. The existence of such objects is not a consequence of discounted Nash equilibrium alone.

An exact Big Match obstruction to discount scheduling

For each discount parameter $\lambda\in(0,1]$, consider the zero-sum Big Match with Player 1's payoff table \[ \begin{array}{c|cc} &L&R\\\hline T&1^*&0^*\\ B&0&1 \end{array} \] where $*$ denotes immediate absorption at the indicated payoff. Player 1 maximizes; Player 2 minimizes. The discounted stationary value is $1/2$, and the effective current-stage discounted game at that value is \[ \begin{pmatrix}1&0\$1-\lambda)/2&(1+\lambda)/2\end{pmatrix}. \] Its unique stationary equilibrium is \begin{equation}\label{wsref-0-65-71-3a-64-69-73-63-6f-75-6e-74-2d-61-63-74-69-6f-6e-73} \Pr_\lambda(T)=p_\lambda=\frac{\lambda}{1+\lambda}, \qquad\Pr_\lambda(L)=q_\lambda=\frac12. \end{equation} These probabilities are smooth rational functions of $\lambda$, and the value is constant. Nevertheless their predetermined scheduling fails.

In the language of Theorem Theorem (Potential--correction verification), Player 2's discounted continuation targets are $G_2(s)=-1/2$, $G_2(1^*)=-1$, and $G_2(0^*)=0$. If Player 2 chooses $R$ in the live state, then \[ {\mathbb{E}}[G_2(h^+)]-G_2(h)=\frac{p_t}{2}>0. \] Thus the crucial supermartingale condition (eq:Gsuper) is not inherited from the discounted Bellman inequalities. These positive drifts can accumulate. This example is not a counterexample to uniform-equilibrium existence: the Big Match has uniform value, but successful strategies depend on the history and cannot be obtained by a fixed, calendar-only schedule of the stationary discounted equilibria.

Why minmax acceptability alone cannot enforce incentives

Flesch and Solan [fleschsolan2023] establish several positive results for stochastic games with general bounded Borel payoff functionals, including approximately minmax-acceptable strategy profiles in every subgame and extensive-form correlated approximate equilibria. These are important, but the logical implication "an individually rational profile can always be enforced by threats" fails without more structure.

A two-player game chooses an absorbing payoff at the first stage: \[ \begin{array}{c|cc} & C&D\\\hline C&(3,3)^*&(0,5)^*\\ D&(5,0)^*&(1,1)^* \end{array}. \] Each player's minmax value is $1$. The profile $(C,C)$ gives both players $3$, strictly above that bound; every subsequently absorbing subgame trivially meets its own minmax benchmark. Nonetheless either player can change only their first action from $C$ to $D$ and raise their payoff to $5$. Because the game has already absorbed, no continuation punishment is available.

The game itself does have a uniform equilibrium, namely $(D,D)$. The point of the example is limited and precise: subgamewise acceptable payoffs do not automatically supply the off-path incentive inequalities required in Definition Definition (Uniform equilibrium payoff).

What remains open and actionable

The attempts above delimit three distinct unsolved constructions.

1. Quitting games, index-one regime. The degree argument excludes $R_0$ matrices of degree other than one with negative incoming entries. It gives no conclusion for degree-one matrices such as (eq:Mone), matrices outside $R_0$, or cases lacking the negative-incoming property. A counterexample would require a complete simultaneous-quitting payoff table and a proof excluding all strategy profiles, including paths with discrete jumps and accumulation phenomena. Failure of stationarity or of SFAPs is insufficient.
2. Small Bellman defects. Proposition Proposition (Weighted-defect verification) would yield uniform approximate equilibria from profiles whose opponent-survival-weighted defects tend to zero with controlled tails. No universal selection theorem producing such profiles has been established here.
3. Arbitrary finite-state games. Theorem Theorem (Potential--correction verification) yields uniform equilibrium from common independent strategies and playerwise continuation-potential certificates, but neither vanishing-discount limits nor minmax acceptable profiles alone construct the required certificates. History-dependent deviation control remains the missing step.

Final conclusion. The unrestricted existence problem remains unsolved in this note. The genuine achievements are the two verification lemmas, an explicit degree-based sufficient class and its exact four-player certificate, and precise counterexamples to two natural methods of proof. None is a counterexample to existence of uniform equilibrium in finite stochastic games.

Complete absorbing payoff table for the explicit completion

The completion (eq:completion) with $b=(-1,-1,-1,-1)$ has the following fifteen absorbing vectors: This table is included so the example is completely specified without any auxiliary file.

Reproducibility and limitations of the arithmetic audit

The matrix arithmetic in Sections sec:search and sec:index is rational. For the proposed matrix (eq:Rdag), the complete sixteen-support enumeration, all principal minors, the terminal equilibrium, the payoff table, and the uniform-regret constant were checked with exact SymPy arithmetic in the earlier research audit. The diagnostic code is not included with this manuscript; the key numerical certificates are fully displayed above. The analytic degree and strategy arguments are mathematical proofs, not formally machine-verified proofs. Before an external research claim is made, an independent mathematical audit is appropriate.

References

• [sv2001] E. Solan and N. Vieille, "Quitting games," Mathematics of Operations Research 26(2), 265--285 (2001). doi:10.1287/moor.26.2.265.10549.
• [sv2002example] E. Solan and N. Vieille, "Quitting games---an example," International Journal of Game Theory 31, 365--381 (2002). doi:10.1007/s001820200125.
• [solansolan2020] E. Solan and O. N. Solan, "Quitting games and linear complementarity problems," Mathematics of Operations Research 45(2), 434--454 (2020). doi:10.1287/moor.2019.0996.
• [akrs2024] G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan, "Absorption paths and equilibria in quitting games," Mathematical Programming 203, 735--762 (2024; online 2022). doi:10.1007/s10107-022-01807-6.
• [aps2026] G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan, "The APS approach for undiscounted quitting games," International Journal of Game Theory 55, article 19 (2026). doi:10.1007/s00182-026-00982-6.
• [apslecture] G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan, discussion of the APS approach to quitting games, presentation notes, Example 3.5. https://www.tse-fr.eu/sites/default/files/TSE/documents/sem2022/madstat/rainer.pdf. (A precursor source; not a claim about the unrestricted equilibrium set.)
• [sv2025] E. Solan and N. Vieille, "Undiscounted equilibrium in positive recursive absorbing games with non-rectangular absorption structure," preprint (December 2025), arXiv:2512.04306.
• [solanvieille2002corr] E. Solan and N. Vieille, "Correlated equilibrium in stochastic games," Games and Economic Behavior 38(2), 362--399 (2002). doi:10.1006/game.2001.0887.
• [gowda2016] M. S. Gowda, "Polynomial complementarity problems," preprint (2016), arXiv:1609.05267. Used for standard complementarity-degree terminology; the particular index argument is proved here.
• [fleschsolan2023] J. Flesch and E. Solan, "Stochastic games with general payoff functions," Mathematics of Operations Research 49(3), 1349--1371 (2024; online 2023). doi:10.1287/moor.2023.1385.
• [grandclementvieille2025] J. Grand-Clément and N. Vieille, "Playing against a stationary opponent," preprint (2025), arXiv:2503.15346. Additional context for the Big Match; all calculations in Section sec:bigmatch are self-contained.

Completion Estimate

25%

Problem ID: C73-1 Model: GPT 6 Astra Pro Version: 1

Status: Unresolved for the complete catalogue problem; this manuscript records partial results and research attempts.

On Equilibrium Payoffs in Finite Multiplayer Stochastic Games Partial Results, Explicit Obstructions, and a Conditional Reduction

Abstract

The existence of uniform, limiting-average, or liminf-average Nash equilibrium payoffs in arbitrary finite multiplayer stochastic games remains an open problem. This note collects and critically audits several attempts to address it. We prove a sufficient condition based on a state-independent vanishing-discount equilibrium payoff; exhibit elementary counterexamples to a proposed additive-eigenpair criterion and to naive concatenation of exact finite-horizon equilibria; and formulate a history-dependent finite-deviation criterion. Using a finite-prefix deviator-identification theorem, we prove a conditional conversion from approximate acceptability and small finite-deviation regret to approximate liminf-average Nash equilibrium. For each fixed finite deviation horizon we establish the two required properties simultaneously. The missing step is to produce one profile satisfying the deviation inequalities for every finite horizon. An example shows why pointwise compactness of strategies cannot supply this step automatically. No general existence proof or counterexample is claimed. Statements proved in this note are distinguished from unproved candidate principles and unsuccessful approaches.

Status. Research-progress note; not a solution of the general open problem.

The question and precise payoff conventions

A finite stochastic game is a tuple \[ \Gamma=(I,S,(A_i(s))_{i\in I,s\in S},q,(g_i)_{i\in I}), \] where $I=\{1,\ldots,m\}$ and $S$ are nonempty finite sets, each action set $A_i(s)$ is finite and nonempty, $q(\cdot\mid s,a)$ is a probability distribution on $S$, and $g_i(s,a)\in\mathbb R$ is a bounded stage payoff. At stage $t$ the current state $s_t$ is publicly observed, the players independently randomize their actions $a_{i,t}$ conditional on the publicly observed history, receive $g_i(s_t,a_t)$, and the next state is sampled from $q(\cdot\mid s_t,a_t)$. Actions and states are publicly observed after the stage. Unless stated otherwise, strategies are arbitrary behavioral strategies with perfect recall and no external mediator.

Write \[ \bar g_{i,n}=\frac1n\sum_{t=1}^n g_i(s_t,a_t),\qquad f_i^-(\omega)=\liminf_{n\to\infty}\bar g_{i,n}(\omega),\qquad f_i^+(\omega)=\limsup_{n\to\infty}\bar g_{i,n}(\omega). \] We use the expected liminf payoff $u_i^-(s,{\sigma})={\mathbb{E}}_{s,{\sigma}}f_i^-$, with analogous notation $u_i^+$. One also encounters $\liminf_n{\mathbb{E}}_{s,{\sigma}}\bar g_{i,n}$ and $\lim_n{\mathbb{E}}_{s,{\sigma}}\bar g_{i,n}$ (when the latter exists). The expected liminf and liminf of expectations are different: interchanging expectation and liminf is not justified in general. A behavioral profile ${\sigma}$ is an ${\varepsilon}$-equilibrium for $u^-$ from state $s$ when \begin{equation}\label{wsref-0-65-71-3a-6c-69-6d-69-6e-66-65-71} u_i^-(s,\tau_i,{\sigma}_{-i})\le u_i^-(s,{\sigma})+{\varepsilon} \quad\text{for every player }i\text{ and every behavioral }\tau_i. \end{equation} A liminf-average equilibrium payoff is a vector $c$ such that for every ${\varepsilon}>0$ there is an ${\varepsilon}$-equilibrium (from the specified initial state) with payoff within ${\varepsilon}$ of $c$. This is an approximate equilibrium-payoff concept, not an assertion that a zero-error equilibrium exists.

A profile is a uniform ${\varepsilon}$-equilibrium when, for every sufficiently large finite horizon $n$, its expected $n$-stage average admits no unilateral gain above ${\varepsilon}$, and its payoff is also nearly constant across all sufficiently large horizons; one may additionally require the analogous inequality for every sufficiently small normalized discount factor $\lambda$, where \[ \gamma_i^\lambda(s,{\sigma}) ={\mathbb{E}}_{s,{\sigma}}\sum_{t=1}^\infty \lambda(1-\lambda)^{t-1}g_i(s_t,a_t). \] A uniform equilibrium payoff $c$ is realized asymptotically by uniform approximate equilibria with their finite-horizon and discounted payoffs converging to $c$. The formulations above are made precise in the statement and proof of Theorem Theorem (State-flat sufficient condition). We distinguish these concepts rather than silently identifying them.

Two-player finite stochastic games have uniform equilibrium payoffs by work of Vieille; corresponding assertions for arbitrary finite numbers of players are not established by the references reviewed here [vieille2002,fleschsolan2023,solanvieille2025,aps2026].

Established background and a map of the attempts

For each $\lambda\in(0,1]$, finite discounted stochastic games have stationary Nash equilibria [fink1964]. Their payoff vectors generally depend on the starting state, and a discounted equilibrium need not remain approximately optimal under a limiting-average criterion. In the general-payoff framework, Flesch and Solan prove the existence of minmax-acceptable profiles in all subgames and of approximate equilibria in at least one subgame, not necessarily at an arbitrarily prescribed initial state [fleschsolan2023]. Deviator identification for nearly certain target events is available by Alon, Gunby, He, Shmaya, and Solan [alon2024].

A valid conditional vanishing-discount theorem

Choose a semialgebraic branch $\lambda\mapsto(x^\lambda,v^\lambda)$ of stationary discounted Nash equilibria for all sufficiently small $\lambda>0$. Such a branch can be selected because the finite-dimensional discounted stationary equilibrium correspondence has a semialgebraic graph; a stationary equilibrium exists for every positive $\lambda$. At finitely many other discount parameters, choose arbitrary stationary equilibria. Assume $|g_i|\le M$.

Two false generalizations of the discounted argument

A state-independent additive eigenpair need not exist

An earlier attempt asked for a constant $c\in\mathbb R^m$, a potential $\Phi:S\to\mathbb R^m$, a length $N$, and Nash equilibrium payoffs $y(s)$ in the $N$-stage game with terminal payment $\Phi(S_{N+1})$ such that \begin{equation}\label{wsref-0-65-71-3a-41-45} \max_{s\in S}\norm{y(s)-\Phi(s)-Nc}_\infty\le N\eta. \tag{AE} \end{equation} If valid, the terminal potentials would telescope across blocks. But the assertion that (eq:AE) holds for every finite stochastic game and arbitrarily small $\eta$ is false.

Exact countdown blocks fail in the Big Match

Consider the two-player constant-sum Big Match, with player 1's reward shown below and player 2's reward equal to $1-g_1$. A star denotes permanent absorption at the indicated payoff: \begin{equation}\label{wsref-0-65-71-3a-42-4d} \begin{array}{c|cc} & L&R\\\hline T&1^{*}&0^{*}\\ B&0&1 \end{array}. \end{equation} At $r$ remaining stages, if the value of the continuation with $r-1$ stages is $(r-1)/2$, the matrix of total continuation rewards is \[ \begin{array}{c|cc} &L&R\\\hline T&r&0\\ B&(r-1)/2&(r+1)/2 \end{array}. \] Player 1 plays $T$ with probability $p_r=1/(r+1)$ and player 2 mixes $L,R$ equally. Direct indifference checks and induction show that this is an exact equilibrium of the $N$-stage game with value $N/2$. It agrees with the countdown $x^{1/r}$ of stationary discounted equilibria: \[ v^\lambda=\tfrac12\quad\text{at the nonabsorbing state}, \qquad p^\lambda=\frac{\lambda}{1+\lambda}. \] The state-flat hypothesis fails: the two absorbing states have discounted payoffs $0$ and $1$. A quantitative finite-horizon version makes the failure especially clear. Against the deviation $R$ forever, player 1's expected total reward in each reached block equals $N/2$. By (eq:survival), the expected total reward over all time is $(N/2)\sum_{k\ge0}(N+1)^{-k}=(N+1)/2$. Therefore ${\mathbb{E}}\bar g_{1,n}\le(N+1)/(2n)$, whereas the prescribed profile yields expected average $1/2$. Exact block Nash optimality does not prevent deviations with effects that persist after the nominal block. The Big Match itself has approximate long-run equilibria; the propositions refute time-only implementations, not its equilibrium existence [bigmatchspace].

Discounted equilibrium limits need not be uniform payoffs

Even without the block-concatenation error, a direct assertion that every vanishing-discount Nash payoff limit is uniform is false: Sorin's example, discussed by Renault and Ziliotto, has a nonempty discounted equilibrium payoff limit set disjoint from the set of uniform equilibrium payoffs [renaultziliotto]. This is a distinct reason why a universal vanishing-discount proof needs additional hypotheses or a different target.

A history-dependent, finite-deviation conversion theorem

The previous failures suggest avoiding one state-independent payoff target at every intermediate date. We now let the continuation benchmark be an actual payoff conditional on the entire finite public history. Normalize rewards in this and the remaining sections to $[0,1]$.

For a profile ${\sigma}$, history $h$, and player $i$, put \begin{equation}\label{wsref-0-65-71-3a-56} V_i^{\sigma}(h)={\mathbb{E}}_{h,{\sigma}}f_i^-. \end{equation} Let \begin{equation}\label{wsref-0-65-71-3a-6d-69-6e-6d-61-78} v_i(s)=\inf_{\rho_{-i}}\sup_{\tau_i} {\mathbb{E}}_{s,\tau_i,\rho_{-i}}f_i^- \end{equation} be the individual minmax level. Opponents in $\rho_{-i}$ use an ordinary joint profile of independently randomized behavioral strategies, rather than a mediator. Since $f_i^-$ is shift-invariant, the minmax level after a finite history depends only on the current state. By the definition of the infimum, for every $\zeta>0$ there is a joint-profile punishment against $i$ yielding at most $v_i(s)+\zeta$ against any strategy of $i$.

Let $\tau_i\star_N{\sigma}_i$ be a strategy that may differ from ${\sigma}_i$ through stage $N$ and equals ${\sigma}_i$ at all subsequent histories. Define \begin{align} A({\sigma})&=\sup_{i,h}[v_i(s_h)-V_i^{\sigma}(h)]_+,\label{wsref-0-65-71-3a-41}\\ R_N({\sigma})&=\max_i\sup_{\tau_i}\left[ u_i^-(s_0,\tau_i\star_N{\sigma}_i,{\sigma}_{-i}) -u_i^-(s_0,{\sigma})\right],\label{wsref-0-65-71-3a-52-4e}\\ R_{\mathrm{fin}}({\sigma})&=\sup_{N\ge1}R_N({\sigma}).\label{wsref-0-65-71-3a-52-66-69-6e} \end{align} These $R_N$ use infinite-horizon tail payoffs; only the length of the deviation is bounded. This is not an $N$-stage expected-payoff test.

The Big Match passes the finite-deviation test

In (eq:BM), prescribe player 1 to play $B$ forever and player 2 to choose independent fair $L/R$ forever. At every unabsorbed history, \[ V^{\sigma}(h)=(1/2,1/2), \] and at absorbing histories $V^{\sigma}$ is the absorbing reward vector. The minmax value to each player is $1/2$ in the nonabsorbing state and the fixed terminal reward after absorption; hence $A({\sigma})=0$. Every bounded-duration deviation of player 1 either leads to an absorption whose expected payoff is $1/2$, or returns to continuation payoff $1/2$. Every bounded-duration deviation of player 2 affects only finitely many rewards, because player 1 never stops. Thus \begin{equation}\label{wsref-0-65-71-3a-42-4d-63-72-69-74-65-72-69-61} A({\sigma})=R_{\mathrm{fin}}({\sigma})=0. \end{equation} Yet this ${\sigma}$ is not itself an equilibrium: player 2 can play $L$ forever to obtain payoff $1$. Theorem Theorem (Finite-deviation conversion; conditional on a starting profile) yields approximate equilibria by testing deviations and assigning punishment. This is a consistency check on the conditional conversion theorem, not a new solution of the Big Match.

A fixed-cutoff construction in every finite game

The following is the strongest unconditional step from the finite-deviation approach.

The remaining quantifier gap and a compactness warning

By Theorem Theorem (Finite-deviation conversion; conditional on a starting profile), the following unproved selection principle would settle the liminf-average part of Question Question (General multiplayer existence problem): If (eq:missing) held for arbitrarily small $\eta$, the conversion theorem would give approximate liminf-average equilibria. Compactness of the numerical payoff vectors (not of their strategy realizations) would then yield a liminf-average equilibrium payoff in the approximate sense defined in Section sec:model.

Theorem Theorem (Finite-prefix construction) proves \begin{equation}\label{wsref-0-65-71-3a-71-75-61-6e-74-69-66-69-65-72-73} \forall\eta>0\ \forall N\ \exists{\sigma}^{(N)}: \quad A({\sigma}^{(N)})\le\eta,\ R_N({\sigma}^{(N)})=0, \end{equation} whereas (eq:missing) asks for \[ \forall\eta>0\ \exists{\sigma}\ \forall N: \quad A({\sigma})\le\eta,\ R_N({\sigma})\le\eta. \] The quantifier interchange is not justified.

This example does not disprove (eq:missing): choosing stop immediately satisfies it. It proves only that an arbitrary strategy-limit argument fails. The key requirement is to construct a profile for which actual realized tail payoffs and all finite-deviation incentive inequalities survive simultaneously.

Research directions and boundaries of the present note

1. History-dependent selection. Find a direct construction or a compactness theorem tailored to actual continuation payoffs $V_i^{\sigma}(h)$ and the entire sequence $(R_N)_{N\ge1}$. A mere subsequence of behavior profiles does not suffice by Proposition Proposition (Tail payoffs need not survive pointwise strategy limits).
2. Tests before profitable steering. Develop a deviation test that limits the probability of reaching higher individual minmax levels before the player receives effective punishment. This is the central state-dependent continuation obstruction highlighted in [fleschsolan2023].
3. Do not conflate solution concepts. Correlated equilibrium, existence from some initial state, and existence at every initial state are different assertions. A general correlated-existence theorem does not supply the desired ordinary Nash profile.
4. Restricted positive results. Specialized approaches for absorbing and quitting games are informative but do not answer the arbitrary finite-state multiplayer question. Recent examples include [solanvieille2025,aps2026].

References and source notes

References

• [fink1964] A. M. Fink, Equilibrium in a stochastic $n$-person game, Journal of Science of the Hiroshima University, Series A-I Mathematics 28 (1964), 89--93.
• [vieille2002] N. Vieille, Stochastic games: Recent results, Handbook of Game Theory with Economic Applications, Vol. 3 (2002), 1833--1850. DOI: 10.1016/S1574-0005$02$03011-4.
• [fleschsolan2023] J. Flesch and E. Solan, Stochastic Games with General Payoff Functions, Mathematics of Operations Research 49 (2024), 1349--1371, published online 2023. DOI: 10.1287/moor.2023.1385. Preprint: https://arxiv.org/abs/2208.12096.
• [alon2024] N. Alon, B. Gunby, X. He, E. Shmaya, and E. Solan, Identifying the Deviator, arXiv:2203.03744, revised 2024. https://arxiv.org/abs/2203.03744. In particular, Theorem 2.6 and the finite-prefix construction in Section 4.
• [bigmatchspace] K. A. Hansen, R. Ibsen-Jensen, and M. Koucký, The Big Match in Small Space, arXiv:1604.07634. https://arxiv.org/abs/1604.07634.
• [renaultziliotto] J. Renault and B. Ziliotto, Hidden Stochastic Games and Limit Equilibrium Payoffs, arXiv:1407.3028. https://arxiv.org/abs/1407.3028. The introduction discusses Sorin's example separating discounted-equilibrium payoff limits from uniform equilibrium payoffs in an ordinary stochastic game; the paper also studies hidden stochastic games, which must not be confused with the finite perfect-monitoring model in Question Question (General multiplayer existence problem).
• [solanvieille2025] E. Solan and N. Vieille, Undiscounted Equilibrium in Positive Recursive Absorbing Games with Non-Rectangular Absorption Structure, arXiv:2512.04306 (2025). https://arxiv.org/abs/2512.04306.
• [aps2026] G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan, The APS approach for undiscounted quitting games, International Journal of Game Theory 55 (2026), article 19. DOI: 10.1007/s00182-026-00982-6.

Completion Estimate

25%