On Pure Nash Equilibria in Stochastic Games

Das, Ankush, Krishna, Shankara Narayanan, Manasa, Lakshmi, Trivedi, Ashutosh and Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (2015) On Pure Nash Equilibria in Stochastic Games. In: Theory and Applications of Models of Computation.

Text lata2015.pdf - Author Accepted Manuscript Download (237kB)

Abstract

Ummels andWojtczak 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 (pureNE) 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 (finNE) with 14 players. In this paper we improve their undecidability results by showing that pureNE and finNE problems remain undecidable for 5 or more players.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Stochastic games, Nash equilibrium, Pure strategy, Finite-state strategy
Depositing User:	Symplectic Admin
Date Deposited:	31 Jan 2017 13:58
Last Modified:	19 Jan 2023 07:19
DOI:	10.1007/978-3-319-17142-5_31
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005457