Seminars & Meetings | Abstracts

Wednesday, June 29, 2011

Levine 315, 1:30 p.m. - 3:00 p.m.

Dominik Wojtczak
Computer Science Department
University of Liverpool
The Complexity of Nash Equilibria in Stochastic Games


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 next state of the game. In this way, an infinite sequence of states is generated which can be mapped to an infinite sequence of rewards for each player. Each player has its own objective and the ones we consider include qualitative ones like reachability or Büchi 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 specified given interval. Furthermore, we study this problem in a setting where we impose certain natural restrictions on the model, 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, i.e. cannot use randomisation, or a stationary strategy, i.e. cannot use memory. This gives rise to many distinct decision problems with their 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.)