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 (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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-319-17142-5_31 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Stochastic games,Nash equilibrium,Pure strategy,Finite-state strategy | Correlated equilibrium,Mathematical economics,Combinatorics,Risk dominance,Epsilon-equilibrium,Strategy,Computer science,Price of stability,Best response,Almost surely,Nash equilibrium | Conference |
Volume | ISSN | Citations |
9076 | 0302-9743 | 1 |
PageRank | References | Authors |
0.37 | 5 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ankush Das | 1 | 17 | 4.34 |
Shankara Narayanan Krishna | 2 | 243 | 42.57 |
Lakshmi Manasa | 3 | 30 | 5.03 |
Ashutosh Trivedi | 4 | 149 | 28.08 |
Dominik Wojtczak | 5 | 151 | 17.50 |