The Complexity of Nash Equilibria in Stochastic Multiplayer Games

Michael Ummels, Dominik Wojtczak

Logical Methods in Computer Science 7(3) (2011)

Used by the Cassting project

This paper analyses the computational complexity of finding Nash equilibria in turn-based stochastic multiplayer games with omega-regular objectives. It shows that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, it is proved that the following problem is undecidable: Given a game G, does there exist a Nash equilibrium of G where Player 0 wins with probability 1? Moreover, this problem remains undecidable when restricted to pure strategies or (pure) strategies with finite memory. One way to obtain a decidable variant of the problem is to restrict the strategies to be positional or stationary. For the complexity of these two problems, the authors obtain a common lower bound of NP and upper bounds of NP and PSPACE respectively.