Math Conjectures

Simple Stochastic Games in Polynomial Time

OPENLandmarkOpen problemProposed 1992 · Standard version

Canonical statement

A simple stochastic game is a finite directed graph whose vertices are partitioned into MAX, MIN, random, and two absorbing sink vertices labeled 00 and 11. Every nonsink vertex has exactly two outgoing arcs. At a MAX or MIN vertex the corresponding player chooses the next vertex; at a random vertex each outgoing arc is chosen with probability 1/21/2. Starting from a specified vertex ss, MAX receives payoff 11 exactly when play eventually reaches sink 11, and payoff 00 otherwise. If
val⁡(s)=sup⁡σinf⁡τPr⁡σ,τ[reach sink 1], \operatorname{val}(s)=\sup_\sigma\inf_\tau \Pr_{\sigma,\tau}[\text{reach sink }1],
where σ\sigma and τ\tau range over strategies of MAX and MIN, is there a deterministic polynomial-time algorithm deciding whether val⁡(s)>12\operatorname{val}(s)>\tfrac12?
View source LaTeX
A simple stochastic game is a finite directed graph whose
vertices are partitioned into MAX, MIN, random, and two absorbing sink
vertices labeled \(0\) and \(1\). Every nonsink vertex has exactly two
outgoing arcs. At a MAX or MIN vertex the corresponding player chooses
the next vertex; at a random vertex each outgoing arc is chosen with
probability \(1/2\). Starting from a specified vertex \(s\), MAX receives
payoff \(1\) exactly when play eventually reaches sink \(1\), and payoff
\(0\) otherwise. If
\[
  \operatorname{val}(s)=\sup_\sigma\inf_\tau
  \Pr_{\sigma,\tau}[\text{reach sink }1],
\]
where \(\sigma\) and \(\tau\) range over strategies of MAX and MIN, is
there a deterministic polynomial-time algorithm deciding whether
\(\operatorname{val}(s)>\tfrac12\)?
TCS-026:[Condon1992StochasticGames][Ludwig1995SSG][GartnerHaslebacherHoang2026SSG]
Theoretical computer scienceGame theory and mathematical economics

Notes

The value-decision problem lies in NP∩coNPNP\cap coNP, and pseudopolynomial, subexponential, and efficient special-case algorithms are known. No polynomial-time algorithm or standard hardness classification is known.
The threshold value-decision problem is a standard polynomial-time-equivalent formulation of solving simple stochastic games.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.