The Complexity of Nash Equilibria in Stochastic Multiplayer Games

Michael Ummels, Dominik Wojtczak

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

http://arxiv.org/pdf/1109.4017

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.