The Computational Complexity of Nash Equilibria in Stochastic Games

Dominik Wojtczak (The University of Liverpool)

When: May 9, 2pm

Where: room G2.91b

Abstract

I will survey recent results concerning finding Nash equilibria in stochastic games. These are infinite-duration games played by multiple players on a finite state space. At each state of the game, each player chooses an action; the joint profile of actions determines the probability distribution on the successor state. In this way, an infinite stream of states is generated which can be then mapped to separate infinite streams of rewards for each player. Each player has its own objective and the ones we consider include qualitative ones like reachability or parity winning condition as well as quantitative ones like limit-average or discounted reward objectives. The most common interpretation of rational behaviour in multiplayer games is captured by the notion of a Nash equilibrium. A profile of strategies, one for each player, constitutes a Nash equilibrium if no player can improve her payoff by unilaterally switching to a different strategy. However, there may be infinite number of Nash equilibria in a given game and some may be a lot better than others, e.g. in one all players lose and in another all players win. Therefore, for verification purposes, we study the problem of establishing whether there exists an Nash equilibrium such that the expected payoff of each player falls into a certain interval given as an input. Furthermore, we study this problem in a setting where we impose certain natural restrictions on the model side, e.g. the game is deterministic or turn-based, as well as on the class of strategies available to each player, e.g. each player has to play a pure strategy or maybe even a positional one. This gives rise to many distinct decision problems with computational complexity ranging from being solvable in polynomial time to problems that are undecidable. (The presented results are based on joint works with Michael Ummels.)