GPT 6 Astra Pro attempt on Econ-1, version 3
economicsEconomics cataloguecontributionexplorationClaim: exploration
Reported by the author as unresolved.
Manuscript
Contents
- Research attempt: C73-1 Equilibrium existence in finite multiplayer stochastic games
- FORMAL RESTATEMENT
- Hygiene and corrections.
- QUICK LITERATURE/CONTEXT CHECK
- ATTACK PLAN
- Proof strategies.
- Disproof strategies.
- Landscape and tools.
- WORK
- Cesàro and discounted existence have the same quantifiers
- Two further valid implications.
- A stationary gain-and-bias certificate
- Finite-deviation selection: a proved finite version and its exact limit gap
- Why the compactness step fails.
- Two explicit adversarial counterexamples to stronger claims
- Expectation and liminf cannot be interchanged.
- VERIFICATION
- FINAL
- Solved subclaims and strongest partial results.
- Exact first gap.
- Three next moves.
- Likely obstruction structure.
- References
- Completion Estimate
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)$.For the discount weights, telescoping the bias terms gives \[ \sum_{t\geq1}\lambda q^{t-1}{\mathbb{E}}[h(s_t)-h(s_{t+1})] =\lambda h(s_1)-\lambda^2\sum_{t\geq2}q^{t-2}{\mathbb{E}} h(s_t). \] The coefficients in the last sum add to $\lambda$. The expected discounted average of $v(s_t)$ is at most $v(s_1)$ under a deviation and equals it under $x$. The same cancellation and span bound prove both discounted estimates.
For pathwise evaluation, define $D_t=g_i(s_t,a_t)+h(s_{t+1})-h(s_t)-v(s_t)$. Conditional on the public history before stage $t$, its conditional expectation is nonpositive, and is zero under $x$. The centered terms $D_t-{\mathbb{E}}[D_t\mid\mathcal H_t]$ are uniformly bounded martingale differences. Their average converges almost surely to zero: if their absolute bound is $C$, the exponential martingale bound gives $\Pr(|\sum_{t\leq N}(D_t-{\mathbb{E}}[D_t\mid\mathcal H_t])|>N\delta) \leq2e^{-N\delta^2/(2C^2)}$. This is the conditional bounded-sampling inequality, obtained by multiplying its conditional moment-generating-function bounds. Summability and Borel--Cantelli, first for rational $\delta>0$, give the assertion; $C=0$ is immediate.
The bounded supermartingale $v(s_t)$ converges almost surely to $v_\infty$ and in $L^1$, with ${\mathbb{E}} v_\infty\leq v(s_1)$. Summing $D_t$, dividing by $N$, and using boundedness of $h$ now gives \[ \limsup_N\frac1N\sum_{t\leq N}g_i(s_t,a_t)\leq v_\infty \quad\text{almost surely under every deviation}. \] Under $x$ equality holds and the averages converge to $v_\infty$; $v(s_t)$ is then a bounded martingale, so ${\mathbb{E}} v_\infty=v(s_1)$. These statements prove the pathwise equilibrium assertion. The expected-average assertion also follows from the already proved horizon bounds. Restarting the same argument after any finite history proves subgame perfection. This does not assert that every deviating expected average converges; it bounds deviations with a limsup and hence any of the weaker well-defined evaluations. ∎
For the finite stochastic matrix $P$, the Cesàro limit $\Pi=\lim_NN^{-1}\sum_{t=0}^{N-1}P^t$ exists. Here is the required linear-algebra justification. Stochasticity gives $\|P^t\|_\infty=1$, so all eigenvalues have modulus at most one and all Jordan blocks at unit-modulus eigenvalues have size one (a larger block would make powers unbounded). Cesàro averages on eigenvalues other than 1 tend to zero; on eigenvalue 1 they remain the identity. Thus $\Pi$ is the projection onto the fixed subspace, and $I-P$ is invertible on the complementary invariant subspace. Set $v_i=\Pi w_i$ and choose $h_i$ solving $(I-P)h_i=w_i-v_i$ there. Then $Pv_i=v_i$ and $w_i+Ph_i=v_i+h_i$. Action independence and the statewise Nash inequalities verify both parts of the certificate, including equalities on $x$. ∎
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.
Conversely, choose a first-stage product of opponent mixed actions within $\delta$ of the displayed infimum. For each possible successor history, choose a product continuation of the opponents whose best-response supremum is at most $m_i(s')+\delta$, possible by the definition of minmax and prefix invariance. Patch these finitely many continuations after the observed first-stage history. They remain independent behavioral strategies. Every first action and every continuation of player $i$ then gives at most the right-hand side plus $2\delta$. Let $\delta\downarrow0$ in the two bounds. No minimax interchange or correlated opponent lottery is used. ∎
Let $v_i(h)$ be its induced continuation payoff. At a prefix node with current state $s$, assume each child's payoff is at least $m_i(s')-\eta$. The local equilibrium condition and the recursion give \begin{align*} v_i(h)&\geq\max_{a_i}{\mathbb{E}}[v_i(h,a_i,a_{-i},s')\mid h,a_i,x_{-i}(h)]\\ &\geq\max_{a_i}\sum_{s'}P(s'\mid s,a_i,x_{-i}(h))m_i(s')-\eta \geq m_i(s)-\eta. \end{align*} Induction gives the acceptability bound at all prefix nodes; the attached profiles give it thereafter. Perform this construction at all finitely many initial states, so it covers all histories in $A$. A deviation through $N\leq H$ followed by a return is among the deviations allowed in the finite game with fixed terminal continuations. It has nonpositive gain, while not deviating has zero gain. Thus $R_N=0$ for every indicated $N$. ∎
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.If $p>0$, absorption occurs almost surely and the row's long-run expected payoff is $q$. The column can play $R$ forever and lower it to zero, gaining $q$. The row can instead play $B$ forever, giving long-run payoff $1-q$ and gain $1-2q$. Thus regret is at least $\max\{q,1-2q\}\geq1/3$: for $q\geq1/3$ the first term suffices, and otherwise the second exceeds $1/3$.
If $p=0$, the row's long-run payoff is $1-q$. The column can play $L$ forever and gain $1-q$; the row can choose $T$ immediately and gain $q-(1-q)=2q-1$. Hence regret is at least $\max\{1-q,2q-1\}\geq1/3$, by splitting at $q=2/3$. The payoffs used here converge almost surely and in expectation: they are either eventually constant after geometric absorption or averages of independent bounded column actions. The bounded-sampling estimate proves convergence in the latter case. Discounted expected payoffs have the same limits, either by the Abel identity or direct geometric summation. Therefore a stationary profile satisfying a uniform bound below $1/3$ would contradict these limiting deviations. Additional zero-payoff dummy players embed the example into any larger player count. ∎
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.