Polynomial-time solution of simple stochastic games
Let $G = (V, E)$ be a finite directed simple graph with $V = V_{\max} \sqcup V_{\min} \sqcup V_{\mathrm{rand}} \sqcup \{0, 1\}$, where $0$ and $1$ are sinks, every other vertex has exactly two outgoing edges, and every vertex has a directed path to a sink; let $o$ be a nonsink start vertex. A token moves along the edges: player Max chooses the next edge at vertices of $V_{\max}$, player Min at vertices of $V_{\min}$, and an independent fair coin at vertices of $V_{\mathrm{rand}}$. Max wins if the token reaches the sink $1$ and loses otherwise, including when play goes on forever. Let $$v(o) = \max_\sigma \min_\tau \mathbb{P}_o^{\sigma,\tau}(\text{the token reaches } 1),$$ over pure positional strategies $\sigma$ of Max and $\tau$ of Min; optimal strategies exist among these (see Gimbert and Horn). Condon proved that deciding whether $v(o) > 1/2$ is in NP $\cap$ coNP. Ludwig and Halman gave randomized algorithms of subexponential expected running time, Gimbert and Horn an algorithm that runs in polynomial time when the number of random vertices is fixed, and Gärtner, Haslebacher and Hoang a polynomial-time algorithm for stopping games on ladders.
Problem. Is there a deterministic algorithm, and constants $C, c > 0$ independent of the input, that decides whether $v(o) > 1/2$ for every such game within $C(L+1)^c$ steps, where $L$ is the bit length of the explicit adjacency-list encoding of the graph, the vertex types and the start vertex? The game need not be stopping: under some strategies the token may avoid the sinks forever with positive probability.
Source: Condon (1992), who introduced simple stochastic games and showed that deciding whether a vertex has value greater than 1/2 is in NP ∩ coNP; in this form, without a stopping assumption, Gärtner, Haslebacher and Hoang (2026), §2.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO, PR
- Keywords
- AIM Open Applied Problems, computational complexity, simple stochastic games, stochastic games
References
@article{condon1992,
author = {Condon, Anne},
title = {The complexity of stochastic games},
journal = {Inform. and Comput.},
volume = {96},
number = {2},
year = {1992},
pages = {203--224},
doi = {10.1016/0890-5401(92)90048-K},
}
@inproceedings{gartner2026,
author = {G{\"a}rtner, Bernd and Haslebacher, Sebastian and Hoang, Hung P.},
title = {Sinks and Ladders: {ARRIVAL} and {SSG} with Two Vertices per Level},
booktitle = {Fun with Algorithms (FUN 2026)},
series = {LIPIcs},
volume = {366},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2026},
pages = {19:1--19:16},
doi = {10.4230/LIPIcs.FUN.2026.19},
}
@article{gimbert2009,
author = {Gimbert, Hugo and Horn, Florian},
title = {Solving simple stochastic games with few random vertices},
journal = {Log. Methods Comput. Sci.},
volume = {5},
number = {2},
year = {2009},
pages = {Paper 9, 1--17},
doi = {10.2168/LMCS-5(2:9)2009},
}
@article{ludwig1995,
author = {Ludwig, Walter},
title = {A subexponential randomized algorithm for the simple stochastic game problem},
journal = {Inform. and Comput.},
volume = {117},
number = {1},
year = {1995},
pages = {151--155},
doi = {10.1006/inco.1995.1035},
}
@article{halman2007,
author = {Halman, Nir},
title = {Simple stochastic games, parity games, mean payoff games and discounted payoff games are all {LP}-type problems},
journal = {Algorithmica},
volume = {49},
number = {1},
year = {2007},
pages = {37--50},
doi = {10.1007/s00453-007-0175-3},
}
@misc{aim-simple-stochastic-games-polynomial-time,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-time solution of simple stochastic games}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/491-simple-stochastic-games-polynomial-time.md},
note = {Entry 491 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00558, "Polynomial-time solution of simple stochastic games", clopen.solutions.