The complexity of stochastic games (Q1187025)

We consider the complexity of a natural combinatorial problem, that of deciding the outcome of a special kind of stochastic game. We show that the problem of deciding which player has the greatest chance of winning the game is in the class \(NP\cap co-NP\). A simple stochastic game is a directed graph composed of max, min and average vertices. There is a special start vertex and two special sink vertices, called the 0-sink and the 1-sink. The graph models a game between two players, 0 and 1. Initially, a token is placed on the start vertex, and at each step, the token is moved from a vertex to one of its neighbors, according to the following rules. At a max (min) vertex, player 1 (0) chooses the neighbor to which the token is moved. At an average vertex, the token is moved to each neighbor of the average vertex with equal probability. The game ends when the token reaches a sink vertex; player 1 wins if it reaches the 1-sink vertex and player 0 wins otherwise. Informally, a strategy for player 0 (1) is a rule that defines what move the player takes whenever the token is at a min (max) vertex. We consider the question: does player 1 win the game with probability \(>1/2\), if both players use their best strategies? Although many algorithms have been proposed for this problem, since the introduction of the model by Shapley in 1953, none are known to run in polynomial time. We show that this decision problem is in \(NP\cap co-NP\).