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.|
- Subscribe to the ics feed.
- No Events