**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

*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 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.)