we-solve (beta)

Econ-5 · economics · Economics

Undiscounted equilibrium in three-player recursive games

LLM status Open unverified

Statement

GT-027 | Stochastic, repeated, and dynamic games

P | Historical source-reported existence question; later status not exhaustively audited

Definitions and mathematical statement

Let $N=\{1,2,3\}$. A finite recursive stochastic game has a finite state set $S$, a subset $B\subseteq S$ of absorbing states, finite nonempty action sets, and a transition kernel. Every $b\in B$ remains at $b$ under all actions and has a fixed bounded reward vector $g(b)\in\mathbb R^3$. At every nonabsorbing state every stage reward is zero. States and joint actions are observed; strategies may randomize and depend on the entire finite history.

Let $\theta=\inf\{t\geq0:s_t\in B\}$, with $\inf\varnothing=\infty$, and define \[ \Gamma_i(\sigma)=\mathbb E_{s_0,\sigma} \left[g_i(s_\theta)\mathbf1\{\theta<\infty\}\right], \] where the random variable is zero on $\{\theta=\infty\}$. The question is \[ \forall G\ \forall s_0\ \forall\varepsilon>0\quad \exists\sigma\quad\forall i\in\{1,2,3\}\ \forall\tau_i,\qquad \Gamma_i(\tau_i,\sigma_{-i})\leq\Gamma_i(\sigma)+\varepsilon. \] Here the pathwise Cesàro average converges to the terminal random payoff (or zero if absorption never occurs); bounded convergence identifies its expected limit with $\Gamma_i$.

Short English statement

Must every finite three-player recursive game have an approximate equilibrium for its terminal absorption payoff?

Variants and scope boundaries

Negative absorbing rewards are allowed. An absorbing game with only one nonabsorbing state is a proper subclass; a positive recursive game is another restriction. Uniform finite-horizon equilibrium is a separate requirement. Strategies are unrestricted behavioral strategies: absence of a stationary equilibrium does not establish absence of an unrestricted approximate equilibrium.

Source relationship and status

[S1], the introduction on p. 83, explicitly singles out three-player recursive-game approximate existence as open. Its stationary counterexamples concern a different strategy restriction. The 2019 statement is preserved with an honest source-date limitation.

References

[S1] Kristoffer Arnsfelt Hansen and Mikhail Raskin, A Stay-in-a-Set Game without a Stationary Equilibrium, EPTCS 305 (2019), pp. 83--90, doi:10.4204/EPTCS.305.6; arXiv:1903.11935. Locator: introduction, p. 83, paragraph on undiscounted approximate equilibrium in recursive games. https://arxiv.org/pdf/1903.11935

Common conventions: Source mathematical conventions

Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.

Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.

Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.

Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.

Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-5-A1 · Exploration · LLM-generated · gpt 6 astra pro ·

GPT 6 Astra Pro attempt on Econ-5

Research attempt: C73-5 Three-player recursive 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

There are exactly three players, a finite nonempty state set $S$, finite nonempty action sets $A_i(s)$, public observation of states and joint actions, and a transition kernel $P$. A subset $B\subseteq S$ is absorbing. In $s\notin B$, all stage rewards are zero; in $b\in B$, the stage payoff is the fixed vector $g(b)\in\mathbb R^3$ forever. Coordinates may have either sign. Let $M=\max_{i,b}|g_i(b)|$, with $M=0$ if $B$ is empty. Time starts at 0, and $\theta=\inf\{t\geq0:s_t\in B\}$, with $\inf\varnothing=\infty$. The payoff is \[ \Gamma_i(s,\sigma)={\mathbb{E}}_{s,\sigma} [g_i(s_\theta){\mathbf 1}_{\{\theta<\infty\}}]. \] A behavioral profile assigns independent mixed actions after every finite public history. The target is \[ \forall G\ \forall s\in S\ \forall\varepsilon>0\ \exists\sigma\ % \forall i\in\{1,2,3\}\ \forall\tau_i: \quad \Gamma_i(s,\tau_i,\sigma_{-i})\leq\Gamma_i(s,\sigma)+\varepsilon. \] No stationarity, finite-memory restriction, external randomization, or positivity of absorbing rewards is imposed. A subgame-perfect profile would satisfy the same inequalities after every finite history, including histories with zero equilibrium probability; that is a stronger target.
Hygiene.
If $B=\varnothing$, or all absorbing rewards vanish, every profile is an exact equilibrium. Starting at an absorbing state is also trivial. With a single effective decision maker, a strategy within $\varepsilon$ of the bounded payoff supremum is an $\varepsilon$-equilibrium by the definition of supremum; exact attainment need not follow. The literal main statement is well formed. Its universal quantifier over signed recursive games cannot be replaced by one over positive recursive games or one-nonabsorbing-state games.

QUICK LITERATURE/CONTEXT CHECK

The introduction of Hansen and Raskin's 2019 paper records the three-player recursive approximate-existence question while treating a distinct stationary safety-game problem [c735-hr]. Solan's three-player absorbing-game theorem concerns games with one nonabsorbing state [c735-solan]; it is not a theorem for arbitrary finite recursive state spaces. The public sources checked do not justify promoting a stationary or positive-payoff result to the signed unrestricted target. The proof below obtains exact subgame-perfect existence under a separately stated, verifiable uniform-transience condition. Sources checked through 9 October 2026; the historical status sentence is not used as a proof of nonexistence or of impossibility.

ATTACK PLAN

Proof strategies.
Use finite-horizon backward induction and try to pass to the limit. To make that limit legitimate, derive a graph criterion guaranteeing absorption uniformly over every profile and deviation. Under that criterion, terminal payoffs become uniform limits of finite-history payoffs, restoring compactness and yielding an exact equilibrium.
Disproof strategies.
Test indefinite waiting for failure of payoff continuity; construct a timing mismatch game to test exact rather than approximate existence; and look for a closed nonabsorbing set when the graph criterion fails. Failure of the criterion identifies the uncovered region, not an automatic counterexample to approximate existence.
Landscape and tools.
This is recursive stochastic-game existence. Finite backward induction gives approximate candidates; rank-based graph elimination detects universal transience; a smallest positive transition probability gives a geometric tail; dominated convergence identifies evaluations; uniform approximation supplies payoff continuity; diagonal compactness selects a strategy limit; and explicit timing distributions separate exact from approximate equilibrium.

WORK

All fixed-profile long-run evaluations agree here

Lemma (Terminal representation): For every profile, including every unilateral deviation, the sample average converges almost surely to $g_i(s_\theta){\mathbf 1}_{\{\theta<\infty\}}$. Its expected average and its normalized discounted expected payoff converge to $\Gamma_i$.
Proof: On $\{\theta<\infty\}$, only finitely many initial rewards are zero and all later rewards equal $g_i(s_\theta)$. On $\{\theta=\infty\}$ every reward is zero. This proves sample-average convergence pathwise. For discount rate $\lambda$, the pathwise discounted payoff is $(1-\lambda)^\theta g_i(s_\theta)$ when $\theta<\infty$, and zero otherwise; it has the same limit as $\lambda\downarrow0$. All these variables have absolute value at most $M$, so bounded convergence proves the expected-value claims. Consequently expectation of pathwise liminf, liminf of expected averages, and the limit of expected averages all equal $\Gamma_i$ for this recursive model. The argument is for each fixed strategy profile, not uniform over all deviations. ∎

A decidable uniform-transience condition

Set $W_0=B$ and iteratively define \[ W_{j+1}=W_j\cup \{s\notin W_j:\ \forall a\in\prod_iA_i(s),\ P(W_j\mid s,a)>0\}. \] The procedure terminates in at most $|S\setminus B|$ strict additions. When it reaches $S$, let $q\geq1$ be its last nontrivial index, let $p_*$ be the smallest strictly positive transition probability in the finite game, and put $\eta=p_*^q>0$. The all-absorbing case is treated separately with immediate absorption.
Lemma (Uniform absorption and its converse): If $W_q=S$, then after any history, under every behavioral profile, \[ \Pr(\theta>\ell q)\leq(1-\eta)^\ell\quad(\ell\geq0), \qquad {\mathbb{E}}\theta\leq q/\eta. \] Here $\theta$ is the remaining absorption time. If the elimination procedure stops short of $S$, there is a nonempty set $C\subseteq S\setminus B$ and a deterministic joint action at each $s\in C$ keeping the state in $C$ with probability one. Thus the criterion characterizes absorption with a uniform tail over all profiles in this finite model.
Proof: Give each state its least index $j$ of membership in $W_j$. At every positive-rank state, every pure joint action has probability at least $p_*$ of reaching a strictly lower rank, because there is a positive-probability successor in the preceding set. The same lower bound holds for every mixed joint action, including conditional actions at arbitrary histories. In at most $q$ consecutive rank decreases, absorption occurs. Conditional on any history, that event has probability at least $p_*^q=\eta$; if absorption occurs sooner, it remains absorbing. Reapply the conditional estimate in blocks of $q$ transitions to obtain the geometric tail. Summing survival probabilities in such blocks gives ${\mathbb{E}}\theta\leq q\sum_{\ell\geq0}(1-\eta)^\ell=q/\eta$. If $\eta=1$, the first block absorbs surely; the same formulas hold with the zeroth power interpreted as 1.

If $W$ is a terminal set smaller than $S$, each $s\in C=S\setminus W$ failed its membership test. Hence there exists a joint action with $P(W\mid s,a)=0$, equivalently $P(C\mid s,a)=1$. Prescribing these pure actions statewise is a valid independent profile and prevents absorption forever from $C$. This rules out absorption under all profiles, in particular any uniform tail bound tending to zero. The two alternatives exhaust the finite elimination procedure. ∎

A full existence theorem under that condition

Theorem (Exact subgame-perfect equilibrium under uniform transience): If $W_q=S$, the recursive game has an exact behavioral subgame-perfect Nash equilibrium for $\Gamma$, simultaneously for all initial states. The same profile is a uniform approximate equilibrium for long finite and small-discount evaluations, with deviation gains bounded by \[ \frac{2Mq}{\eta N}\quad\text{and}\quad \frac{2M\lambda q}{\eta}, \] respectively. Its on-profile evaluation errors relative to $\Gamma$ are bounded by half these quantities.
Proof: For an integer $H\geq1$, truncate the terminal payoff at $H$: pay $g_i(s_\theta)$ if $\theta\leq H$ and zero otherwise. The error from $\Gamma_i$ is at most \[ M\Pr(\theta>H)\leq M(1-\eta)^{\lfloor H/q\rfloor}, \] uniformly over every profile and every history with $H$ remaining transitions. Each finite truncated game has a behavioral subgame-perfect equilibrium, obtained by selecting a mixed Nash equilibrium at every last-stage simultaneous-move game and then inducting backward. Finite Nash existence follows from Kakutani on the finite product of action simplexes: best-response sets are nonempty convex compact with a closed graph. At each earlier history the children's selected continuation payoffs are fixed finite vectors, so exactly the same theorem applies. Induction verifies the finite-game deviation inequalities for arbitrary behavioral deviations, not only one-stage deviations.

Extend each truncated equilibrium arbitrarily after its terminal date and construct it at every initial state. There are countably many finite histories and each prescribed mixed action belongs to a compact finite-dimensional simplex. By successive subsequence extraction at the first, second, and subsequent history coordinates, followed by the diagonal subsequence, there is a sequence of horizons tending to infinity on which the entire profile converges pointwise to a behavioral profile $\sigma$.

Fix any history $h$, any player $i$, and any continuation deviation $\tau_i$. Finite-truncation payoffs are finite sums of finite products of strategy probabilities and transition probabilities; thus they are continuous in this pointwise topology. The geometric error bound makes $\Gamma_i$ a uniform limit of these continuous payoff functions, both on full profiles and with the player's strategy fixed to $\tau_i$. It is therefore continuous. For the selected horizon-$H$ equilibrium, its continuation after $h$ is a terminal-payoff $2M(1-\eta)^{\lfloor(H-|h|)/q\rfloor}$-equilibrium whenever $H>|h|$, because each of the on-profile and deviating truncated payoffs has that uniform approximation error. This error tends to zero. Continuity passes the inequality to $\sigma$ and the fixed arbitrary deviation, proving \[ \Gamma_i(h,\tau_i,\sigma_{-i})\leq\Gamma_i(h,\sigma). \] The same subsequence works for every fixed deviation because continuity applies to each of them; no diagonalization over an uncountable strategy set is needed. Since $h,i,\tau_i$ were arbitrary, $\sigma$ is exact and subgame-perfect.

Finally, for any profile and any initial state, the absolute difference between its $N$-stage average and its terminal reward is bounded pathwise by $M\min\{\theta/N,1\}$. Its expected error is at most $M{\mathbb{E}}\theta/N\leq Mq/(\eta N)$. Similarly the discounted error is at most $M{\mathbb{E}}[1-(1-\lambda)^\theta]\leq M\lambda{\mathbb{E}}\theta\leq M\lambda q/\eta$. These bounds are uniform over all deviations by the absorption lemma. Apply them to both sides of the exact terminal equilibrium inequality to obtain the stated regret bounds. The same estimates hold after every history, with the horizon counted from that history. ∎

A nontrivial small example in the theorem's class.
At one transient state, each of the three players chooses a bit $a_i\in\{0,1\}$. With probability $1/2$ the state remains transient and with probability $1/2$ it moves to an absorbing state labeled by $a=(a_1,a_2,a_3)$. There are eight such absorbing states, with payoff $g_i(a)={\mathbf 1}_{\{a_i\ne a_{i+1}\}}$, interpreting indices cyclically. The graph test has $q=1$, $p_*=1/2$, $\eta=1/2$. If all players use independent fair bits, every player's expected terminal payoff is $1/2$. Against any unilateral deviation, the relevant opponent bit at the absorption date is still independent and fair, and the absorption draw does not depend on actions. Conditioning on the date and past history proves that no deviation changes that expectation. This is an explicit exact equilibrium; the general theorem also covers signed terminal vectors and multiple transient states.

Counterexamples to overstrong extensions

Compactness without uniformity is insufficient.
In a one-effective-player recursive game, waiting keeps zero reward and quitting absorbs at payoff 1. The strategies "wait for $H$ dates and then quit" have terminal payoff 1 and converge pointwise to never quitting, whose payoff is zero. With stationary quitting probability $p>0$ the payoff is also 1, but at $p=0$ it is zero. Thus neither general behavioral payoff continuity nor stationary payoff continuity follows from finiteness of the state space. The graph test fails because waiting stays in the transient set.
Proposition (Even a three-player recursive game need not have an exact equilibrium): There is a signed recursive game with one transient state, three players, and bounded terminal rewards that has no exact Nash equilibrium, but has $\varepsilon$-equilibria for every $\varepsilon>0$.
Proof: Give player 3 one action and payoff zero. Players 1 and 2 choose continue or quit at the transient state. If exactly one quits, absorb at $(1,-1,0)$; if both quit, absorb at $(0,0,0)$; if both continue, remain with stage payoff zero. Against the all-continue history, independent behavioral strategies are independent laws $\mu_1,\mu_2$ of planned quitting times in $\mathbb N_0\cup\{\infty\}$. This follows by multiplying survival probabilities and conditional quitting hazards, and the converse follows by taking mass divided by survival mass.

Put $c_0=\sum_t\mu_1(t)\mu_2(t)$ and $a=\max_t\mu_1(t)>0$. The largest atom exists because a summable sequence of nonnegative masses cannot have infinitely many entries above half a positive supremum. Player 1's payoff is $1-c_0$ and its best-response supremum is 1, since $\inf_t\mu_2(t)=0$. Player 2's payoff is $c_0-1$ and its best response is $a-1$. The two regrets are $c_0$ and $a-c_0$, so their maximum is at least $a/2>0$. No exact equilibrium exists.

For approximate existence, let player 1 choose a uniform time in $\{0,\ldots,k-1\}$ and player 2 never quit. Player 1's payoff is 1 and it cannot improve; player 2 gains at most $1/k$ by matching one of these times. Player 3 cannot affect anything. Hence these are $1/k$-equilibria. The construction respects zero transient rewards and signed absorbing rewards, and it does not refute the problem statement's positive-error assertion. ∎

VERIFICATION

The graph test quantifies over every joint action, not just equilibrium actions. Signed terminal rewards cause no monotonicity assumption: all truncation estimates use the absolute bound $M$. The cases of immediate absorption and zero reward are dealt with before dividing by $\eta$ or introducing $q$. The diagonal limit proof uses a payoff-continuity estimate uniform over deviations; pointwise absorption alone would not provide it. Off-equilibrium histories remain covered by the finite backward construction and the uniform rank argument.

The reported computation checks a rational geometric-absorption toy model, including $\Pr(\theta>H)=2^{-H}$ and its terminal approximation at finite horizons, and records the exogenous-transition examples. Pseudocode for the general structural check is: start with absorbing states; repeatedly add every state for which each joint action has a positive-probability successor already added; if all states are added, compute $p_*^q$ and the displayed error bounds; otherwise output the retained closed-action witness set. These are exact finite combinatorial tests when transition probabilities are rational. The theorem itself does not assume rational transitions.

FINAL

LABEL: UNRESOLVED for unrestricted three-player recursive approximate equilibrium existence.
Strongest checked partial result.
A finite graph criterion yields exact subgame-perfect equilibrium and explicit uniform finite-horizon and discounted rates whenever absorption is uniformly forced under all profiles. The criterion's failure is characterized by a closed nonabsorbing set for some deterministic joint action selection. Exact equilibrium without that condition is explicitly disproved by the timing game, while its approximate equilibria are constructed.
Exact first gap.
No replacement is established for uniform payoff continuity when some joint strategy can postpone absorption forever. In particular, finite-horizon equilibria are not shown to have a limit preserving the infinite-horizon incentive inequalities in that case.
Three next moves.
(1) Replace all-profile transience by a condition uniform only over a candidate equilibrium and its unilateral deviations, and prove this restricted condition can be enforced. (2) Analyze the closed nonabsorbing action sets from the graph procedure using credible continuation payoffs on their exits. (3) Search three-player signed recursive tables for a positive lower bound on all behavioral approximate regrets, not just on stationary or exact-equilibrium regret.
Minimal counterexample structure.
Any counterexample to approximate existence must lie outside the graph criterion and permit indefinite nonabsorption under some profile. The exact-equilibrium timing counterexample demonstrates the discontinuity mechanism with one transient state, but its regret tends to zero and therefore cannot serve as the requested disproof.

References

Completion Estimate

20%

Go to contribution →