On Pure Nash Equilibria in Stochastic Games
Ankush Das, Shankara Narayanan Krishna, Lakshmi Manasa, Ashutosh Trivedi, Dominik Wojtczak.
TAMC 2015 : 359-371
Abstract
Ummels and Wojtczak initiated the study of finding Nash equilibria in simple stochastic multi-player games satisfying specific bounds. They showed that deciding the existence of pure-strategy Nash equilibria (pure NE) where a fixed player wins almost surely is undecidable for games with 9 players. They also showed that the problem remains undecidable for the finite-strategy Nash equilibrium (fin NE) with 14 players. In this paper we improve their undecidability results by showing that pure NE and fin NE problems remain undecidable for 5 or more players.