Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Decision Problems for Nash Equilibria in Stochastic Games
Authors: Michael Ummels ; Dominik Wojtczak
Date:Apr 2009
Publication Type:Journal Article Publication Status:Pre-print
We analyse the computational complexity of finding Nash equilibria in stochastic multiplayer games with $\omega$-regular objectives. While the existence of an equilibrium whose payoff falls into a certain interval may be undecidable, we single out several decidable restrictions of the problem. First, restricting the search space to stationary, or pure stationary, equilibria results in problems that are contained in PSPACE and NP, respectively. Second, we show that the existence of an equilibrium with a binary payoff (i.e. an equilibrium where each player either wins or loses with probability 1) is decidable. We also establish that the existence of a Nash equilibrium with a certain binary payoff entails the existence of an equilibrium with the same payoff in pure, finite-state strategies.
Links To Paper
1st Link
Bibtex format
author = { Michael Ummels and Dominik Wojtczak },
title = {Decision Problems for Nash Equilibria in Stochastic Games},
journal = {},
year = 2009,
month = {Apr},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh