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)
https://www.sciencedirect.com/science/article/pii/089054019290048K
- The Complexity of Solving Stochastic Games on Graphs, Daniel Andersson & Peter Bro Miltersen (2009)
https://link.springer.com/chapter/10.1007/978-3-642-10631-6_13
