The complexity of solving simple stochastic games

Pranshu Gaba
Varun Ramanathan
Friday, 16 Feb 2024, 17:30 to 18:30
A-201 (STCS Seminar Room)

Simple stochastic games (SSG) are zero-sum games played by two players on a directed graph with a designated target vertex. The players take turns moving a token along the edges of the game graph. The objective of player 1 is to eventually reach the target vertex, whereas the objective of player 2 is to never reach the target vertex. The SSG problem is to find the maximum probability with which player 1 wins the game. We will see that this problem is in NP ∩ coNP.
We will also see 3 more problems that are polynomial-time equivalent to SSG, and thus also in NP ∩ coNP. Showing that any of these problems are in P would be a major breakthrough.

You can read the following papers for more details.
- The complexity of stochastic games, Anne Condon (1992)

- The Complexity of Solving Stochastic Games on Graphs, Daniel Andersson & Peter Bro Miltersen (2009)