Decision Problems for Nash Equilibria in Stochastic Games

Speaker

Michael Ummels, Research Group Computer Science 7
Title Decision Problems for Nash Equilibria in Stochastic Games
When 03.12.2008, 15.00 Uhr
Where Lecture Room Informatik 11
Abstract We study the complexity of Nash equilibria in stochastic games. While deciding the existence of an equilibrium whose payoff falls into a certain interval might be undecidable, we single out two decidable restrictions of the general problem: First, we show that it is possible to decide the existence of an equilibrium where each player either wins or loses almost surely. Second, we show that one can decide the existence of an equilibrium where all but one player wins with probability 1 and the remaining player wins with probability at least p. The latter problem occurs naturally in controller synthesis.
Slides download