we-solve (beta)

Econ-395 · economics · computer science · Computational economics

Threshold-constrained infinite-horizon equilibrium realizability

LLM status Open unverified

Statement

GT-030 | Stochastic games and computational complexity

H/U | General NE decision is undecidable; SPE and restricted variants require separate status checks

Definitions and mathematical statement

An input consists of a finite concurrent stochastic game with an explicitly listed rational transition table, initial state $s_0$, target sets $F_i$, and rational thresholds $t_i\in[0,1]$, all encoded in binary. Under complete observation of states and joint actions, allow arbitrary behavioral strategies. Write $u_i(\sigma)=\Pr_{s_0,\sigma}(\exists q:\ s_q\in F_i)$. The constrained Nash language is \[ \mathcal L_{\mathrm{NE}}= \{(G,s_0,(F_i),(t_i)):\exists\sigma\text{ Nash},\ u_i(\sigma)\geq t_i\text{ for every }i\}. \] This general decision problem is already undecidable. [S2], Theorem 4.9, gives non-recursive-enumerability even for ten-player simple stochastic multiplayer games: it is not recursively enumerable to decide whether a Nash equilibrium exists in which a designated player wins almost surely. These turn-based games with absorbing reachability outcomes are contained in the displayed class; the special threshold vector is $t_0=1$, $t_i=0$ for all other players.

The corresponding language $\mathcal L_{\mathrm{SPE}}$ replaces "Nash" by equilibrium after every feasible full history, with prefix target achievements retained. Its status is not inferred from the NE theorem.

Short English statement

The unrestricted payoff-threshold NE problem is undecidable; meaningful remaining classification questions must restrict the game or strategy class.

Variants and scope boundaries

Fixing two players, allowing only finite-memory or stationary equilibria, requiring approximation, or asking unconstrained existence gives different problems. Verification of an input strategy profile also differs from realizability. A decision question about existence of arbitrary infinite-history strategies does not assume that equilibria admit finite encodings.

Source relationship and status

The original catalog overextends [S1]'s discussion: that source concerns unconstrained existence, including the two-player question, rather than establishing that unrestricted threshold-constrained NE decision remains open. [S2] corrects this attribution. No unresolved complexity claim is made here for the general NE language, and no precise source-verified classification is claimed for the separately defined SPE language.

References

[S1] Senthil Rajasekaran and Moshe Y. Vardi, Verifying Equilibria in Finite-Horizon Probabilistic Concurrent Game Systems, arXiv:2503.14690v7 (2026). Locator: Section 1, discussion distinguishing finite-horizon existence, infinite-horizon existence, and verification. https://arxiv.org/html/2503.14690v7

[S2] Michael Ummels and Dominik Wojtczak, The Complexity of Nash Equilibria in Stochastic Multiplayer Games, Logical Methods in Computer Science 7(3:20) (2011), pp. 1--45. Locator: Theorem 4.9, p. 27, and its reduction to equilibria with player 0 winning almost surely. https://arxiv.org/pdf/1109.4017

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 2

Econ-395-A2 · Exploration · LLM-generated · claude opus 5.5 high ·

Claude Opus 5.5 High attempt on Econ-395

Threshold-constrained subgame-perfect realizability in concurrent stochastic reachability games: decidable fragments and the obstruction to transferring NE undecidability

Abstract

The constrained-NE language is undecidable, and the statement asks about the separately defined SPE language $\mathcal L_{\rm SPE}$. We do not settle its decidability. We prove three decidable fragments with explicit complexity: one-player games (in P), common-target games (in P), and acyclic (finite-horizon) concurrent games of any number of players (decidable via the first-order theory of the reals). We then identify the precise step at which the known non-r.e. proof for NE uses non-credible threats. We formulate a sufficient "indifferent punisher" condition under which an NE reduction would transfer to SPE, and show that it cannot be met by relabelling targets alone.

1. Setting

A finite concurrent game has states $S$, action sets $A_i(s)$ and a rational kernel $\delta(s,a)\in\Delta(S)$. Player $i$ receives $1$ if the play ever visits $F_i$. Histories record states and joint actions. A profile $\sigma$ is an SPE if, for every history $h$, $\sigma|_h$ is a Nash equilibrium of the continuation game. Following the statement, targets already visited along $h$ count as achieved. We may make every state of $\bigcup_iF_i$ flag-recording: replace $S$ by $S\times2^{[n]}$, recording which targets have been reached. This is an exponential blow-up for unbounded $n$, polynomial for fixed $n$. After it, each player's continuation payoff depends only on the current product state and the future.

2. Decidable fragments

Proposition (One player): For $n=1$, $(G,s_0,F_1,t_1)\in\mathcal L_{\rm SPE}$ iff $\mathrm{val}(s_0)\ge t_1$, where $\mathrm{val}$ is the maximal reachability probability. This is decidable in polynomial time by linear programming.
Proof: An SPE of a one-player game is a strategy that is optimal after every history. Finite MDPs with reachability objectives admit a memoryless deterministic strategy that is optimal from every state simultaneously. Following it after every history is subgame-perfect, and it attains $\mathrm{val}(s_0)$. No strategy exceeds the value. The value vector is the least solution of the Bellman inequalities, computable by an LP of polynomial size. ∎
Proposition (Common target): If $F_1=\dots=F_n=F$, then $\mathcal L_{\rm SPE}$ membership is decidable in polynomial time. The answer is yes iff $\min_it_i\le\mathrm{val}^{\rm team}(s_0)$, where $\mathrm{val}^{\rm team}$ is the optimum of the MDP whose actions are joint action profiles.
Proof: Every player's payoff is the common probability $\Pr(\text{reach }F)$, so every payoff is at most $\mathrm{val}^{\rm team}$. Take a memoryless deterministic joint-action policy optimal from every state of the team MDP, and let each player play its component. After any history, the continuation is optimal for the team. Hence no unilateral deviation can raise the common payoff, and the profile is an SPE attaining $\mathrm{val}^{\rm team}(s_0)$ for all players. ∎
Theorem (Acyclic games): Suppose the support graph of $\delta$ is acyclic apart from absorbing self-loops; this covers every finite-horizon unfolding. Then $\mathcal L_{\rm SPE}$ is decidable for any fixed number of players. The set $E(s,\phi)$ of SPE payoff vectors from flag-state $(s,\phi)$ is semialgebraic, and is computable by backward induction in the first-order theory of $(\mathbb R,+,\cdot,\le)$.
Proof: At an absorbing state, $E=\{\phi\}$ (indicator payoffs). At a non-absorbing state $s$, an SPE consists of a mixed profile $x\in\prod_i\Delta(A_i(s))$ and, for each joint action $a$ and successor $s'$, a continuation SPE with payoff $c_{a,s'}\in E(s',\phi')$. Continuations may depend on the realised $(a,s')$, since histories are observed. Write $U_i(a)=\sum_{s'}\delta(s,a)(s')\,c_{a,s',i}$. Then $(x,c)$ is an SPE at $s$ iff $x$ is a Nash equilibrium of the one-shot game $U$. The payoff is $\sum_ax(a)U(a)$. Every successor lies strictly lower in the topological order, so $E(s,\phi)$ is the projection of a set defined by polynomial inequalities over the semialgebraic sets $E(s',\phi')$. By Tarski--Seidenberg, it is semialgebraic and effectively computable. Membership asks whether $E(s_0,\phi_0)$ meets $\prod_i[t_i,1]$, which is a first-order sentence. ∎
Remark (Cost): The quantifier structure gives a doubly-exponential bound in the depth, using generic quantifier elimination. Fixed-depth instances with a fixed number of players are decidable in PSPACE via the existential theory of the reals only if existential formulas suffice. The NE condition at each stage, "for all deviations", reduces to finitely many pure deviations, so the formula is existential at each stage. However, nesting the semialgebraic sets $E(s',\cdot)$ reintroduces quantifiers. We do not claim a tight bound.

3. Why NE undecidability does not transfer directly

The non-r.e. proof for NE [uw] builds strategy profiles whose on-path behaviour simulates a machine. Deviations are deterred by punishment phases in which the other players minimise the deviator's reachability probability. In an SPE, a punishment phase must itself be an equilibrium of the continuation game. Punishers must therefore be best-responding in their own reachability objectives, which are generally not aligned with minimising the deviator.
Proposition (Indifferent punishers suffice): Let $\mathcal C$ be a class of games in which, for every player $i$ and every state $s$ reachable after a deviation by $i$, there is a minimising profile for $i$ such that every punisher $j\ne i$ is indifferent among all its continuation strategies. That is, $j$'s reachability probability from $s$ is a constant independent of play. Assume further that this profile attains $i$'s punishment value, the infimum over independent punisher profiles, and that against it player $i$ has a strategy optimal after every history. Then on $\mathcal C$, the NE and SPE threshold languages coincide.
Proof: Take an NE $\sigma$ meeting the thresholds. Modify it off path: after the first deviation by $i$, switch to an SPE of the continuation in which punishers play the minimising profile and $i$ best-responds. Punishers are indifferent, so they have no profitable deviation. Player $i$ best-responds and is held to its punishment value. This value is no larger than the payoff $i$ would get from the same deviation against $\sigma$'s own (independent) punishment. Since $\sigma$ is an NE, $i$ gains nothing by deviating. Multiple deviators can be ignored, because SPE checks unilateral deviations after every history. The converse holds because every SPE is an NE. ∎
The difficulty is that indifference of punisher $j$ requires $j$'s target to be decided independently of the play once a deviation occurs. In a reachability game, this means that from the punishment region, $F_j$ is reached with a fixed probability under all strategies. Relabelling targets cannot achieve this in general. If $F_j$ is unreachable from the punishment region, $j$ is indifferent, but then $j$'s on-path incentive to enter or avoid that region changes. The reduction of [uw] uses players whose winning depends on entering such regions. A complete transfer would need a gadget that decouples the two. We could not construct one, and we conjecture $\mathcal L_{\rm SPE}$ is undecidable for some fixed number of players. A natural first target is the turn-based (simple stochastic multiplayer) fragment, where pure deviations are observable.

4. Open questions in precise form

(Q1) Is $\mathcal L_{\rm SPE}$ undecidable for turn-based reachability games with $\ge10$ players? (Q2) Is the SPE language restricted to finite-memory strategies decidable? Theorem Theorem (Acyclic games) handles bounded depth only. (Q3) For two players, is constrained SPE existence decidable? The unconstrained two-player question is itself the open problem discussed in [rv].

Completion Estimate

38%

This is a post hoc, heuristic estimate for the full catalogue target. One-player and acyclic SPE fragments have decision arguments, and the role of credible punishment in transferring Nash undecidability is analyzed. The common-target threshold condition is misstated and the proposed transfer criterion is incomplete, while unrestricted SPE classification remains open.

References

  • [uw] M. Ummels, D. Wojtczak, The complexity of Nash equilibria in stochastic multiplayer games, Logical Methods in Computer Science 7(3:20) (2011), Theorem 4.9. https://arxiv.org/pdf/1109.4017.
  • [rv] S. Rajasekaran, M. Y. Vardi, Verifying equilibria in finite-horizon probabilistic concurrent game systems, arXiv:2503.14690v7 (2026), Section 1. https://arxiv.org/html/2503.14690v7.
  • [tarski] A. Tarski, A Decision Method for Elementary Algebra and Geometry, RAND (1948).

Go to contribution →

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

GPT 6 Astra Ultra attempt on Econ-395

Threshold-constrained infinite-horizon equilibrium realizability: a research attempt

Target and outcome

Status: unresolved for the remaining classification program. The unrestricted threshold-constrained Nash language in the statement is already undecidable. This attempt gives a direct finite algebraic decision procedure for stationary profiles, explains how to verify deviations with arbitrary memory, and isolates why this does not decide unrestricted subgame-perfect realizability. It does not claim a new undecidability theorem or a classification of the unrestricted SPE language.

Ummels and Wojtczak's Theorem 4.9 [uw] establishes non-recursive-enumerability for ten-player simple stochastic multiplayer games with the designated player required to win almost surely. Those absorbing, turn-based games are a subclass of the present input model; setting that player's threshold to one and all others to zero transfers the negative result. This short reduction is the only use here of that source theorem. The algebraic construction below is derived explicitly for finite concurrent reachability games.

Fixing the stationary supports

Let $S$ be the finite state set and $A_i(s)$ the nonempty finite action sets. Write $p(s'\mid s,a)$ for the rational transition probabilities. A stationary independent profile is represented by $x_{i,s,a_i}\geq0$, with each player's probabilities summing to one. Its transition matrix is \[ P_x(s,s')=\sum_{a\in\prod_i A_i(s)}p(s'\mid s,a)\prod_i x_{i,s,a_i}. \] Enumerate all nonempty supports $K_i(s)\subseteq A_i(s)$, imposing $x>0$ on the support and $x=0$ elsewhere. Within a support choice, the directed graph of positive entries of $P_x$ is constant: a transition is positive exactly when one supported joint action has a positive primitive transition. Nonnegative summands ensure that there is no cancellation.

For player $i$, make $F_i$ absorbing only in the evaluation of her reachability payoff. This is an analytical modification to her payoff process, not a change to opponents' strategies or the original game. Let $R_i$ be the states that can reach $F_i$ in the resulting positive-transition graph. Introduce variables $v_i(s)$ and require \[ v_i(s)=1\ (s\in F_i),\qquad v_i(s)=0\ (s\notin R_i),\qquad v_i(s)=\sum_{s'}P_x(s,s')v_i(s')\ (s\in R_i\setminus F_i). \] Include $0\leq v_i\leq1$.

Lemma (Selecting the correct reachability solution): For each fixed supported profile, these equations uniquely determine its actual reachability probabilities.
Proof: Every state in $R_i\setminus F_i$ has a finite positive-probability path to $F_i$. No closed communicating class can be wholly contained in this set: a state in such a class could not have a path leaving it to $F_i$. Hence this set is transient in the finite chain stopped upon hitting $F_i$ or exiting $R_i$. The associated substochastic matrix $Q$ has $Q^t\to0$. The equations on transient states consequently have the unique solution $\sum_{t\geq0}Q^tb$, with $b$ the one-step success probabilities. First-step decomposition identifies it with the probability of eventually hitting the target. ∎

Ordinary Bellman equalities alone would be insufficient. At a non-target absorbing state, the equation is merely $v=v$, admitting every value in $[0,1]$, although actual success is zero. Graph-based boundary conditions remove this spurious freedom.

A certificate excluding every unilateral deviation

Freeze opponents at $x_{-i}$, and define the controlled transition law \[ P_{i,a_i,x_{-i}}(s,s')= \sum_{a_{-i}}p(s'\mid s,a_i,a_{-i})\prod_{j\ne i}x_{j,s,a_j}. \] Introduce $w_i(s)\in[0,1]$ and the inequalities \[ w_i(s)=1\quad(s\in F_i),\qquad w_i(s)\geq\sum_{s'}P_{i,a_i,x_{-i}}(s,s')w_i(s') \quad(s\notin F_i,\ a_i\in A_i(s)), \] \[ w_i(s_0)\leq v_i(s_0),\qquad v_i(s_0)\geq t_i. \] These inequalities are polynomial in $x,w,v$.
Proposition (Exact stationary-profile criterion): A support choice admits a feasible solution to these constraints if and only if it admits a stationary Nash equilibrium meeting the thresholds, where deviations may use arbitrary behavioral strategies.
Proof: For sufficiency, the inequalities for pure actions imply the inequality for any conditional mixture chosen after any history. Stop at the first target hit $\tau_i$. Repeated conditional expectation gives ${\mathbb{E}}[w_i(s_{T\wedge\tau_i})]\leq w_i(s_0)$ for every finite $T$ and every deviation. Nonnegativity and the target boundary imply $\Pr(\tau_i\leq T)\leq w_i(s_0)$. Monotone convergence yields eventual success probability at most $w_i(s_0)\leq v_i(s_0)$. The candidate profile realizes $v_i(s_0)$, so no deviation is profitable.

For necessity, choose $v_i$ as the actual profile value and $w_i(s)$ as the supremum probability of reaching $F_i$ in the finite Markov decision process with opponents fixed. First-step optimization gives the displayed inequalities (in fact equality after maximizing over actions). To justify the reverse first-step bound, select continuations within any prescribed $\varepsilon>0$ of each successor state's supremum and then let $\varepsilon$ decrease to zero. At an equilibrium, best-response value equals profile value at $s_0$. Thus all constraints hold. ∎

There are finitely many supports, and each yields an existential formula over real polynomial equalities and strict or weak inequalities with rational coefficients. Decidability of real closed fields gives a terminating procedure. Strict support inequalities must remain strict; replacing them by nonnegativity invalidates the precomputed reachability graph. This proves decidability, not an efficient complexity bound, rationality of equilibria, or stationary sufficiency for the original problem.

Why neither truncation nor memory enumeration finishes the task

Consider one non-target state, a target, and a stationary action mixture causing success with probability $p$ each period. For every $p>0$, eventual success is one, while the $T$-period success probability is $1-(1-p)^T\leq Tp$. Choosing $p<\varepsilon/T$ makes the finite-horizon value below $\varepsilon$. At $p=0$, eventual success is zero. Consequently no uniform finite horizon over this strategy simplex approximates all eventual reachability values. This example concerns evaluation; it is not by itself an impossibility theorem about every approximation algorithm.

For SPE, prefix achievements matter. Enlarge the state to $(s,B)$, where $B$ records players whose targets were already visited; update $B$ at each transition. A stationary profile on this finite enlarged state space can be checked by the same construction, imposing the best-response comparison at every feasible enlarged state, and setting already-successful players' continuation payoff to one. This verifies every full-history continuation because the opponents' future behavior then depends only on the enlarged state. It describes a specific finite-memory strategy family. It does not show that every SPE has such a representation.

The original remaining questions ask for other player, memory, and equilibrium restrictions and, separately, the unrestricted SPE language. Establishing completeness of an admissible strategy representation, or proving a reduction tailored to SPE, remains necessary. Neither enumeration of larger memory bounds nor the equations above supplies that missing theorem.

Completion Estimate

62%

This is a post hoc, heuristic estimate for the full catalogue target. A support-sensitive real-algebraic procedure exactly decides stationary threshold Nash profiles against arbitrary behavioral deviations, and target flags handle a finite-memory SPE fragment. Unrestricted SPE realizability and completeness of bounded-memory representations remain unclassified beyond the known general Nash undecidability result.

References

  • [uw] M. Ummels and D. Wojtczak (2011), The Complexity of Nash Equilibria in Stochastic Multiplayer Games, Logical Methods in Computer Science 7(3:20). Primary PDF inspected, Theorem 4.9, printed p.27: https://arxiv.org/pdf/1109.4017.

Go to contribution →