On Pure Nash Equilibria in Stochastic Games

被引：1

作者：

Das, Ankush ^{[1
]}

Krishna, Shankara Narayanan ^{[1
]}

Manasa, Lakshmi ^{[1
]}

Trivedi, Ashutosh ^{[1
]}

Wojtczak, Dominik ^{[2
]}

机构：

[1] Indian Inst Technol, Dept Comp Sci & Engn, Mumbai, Maharashtra, India

[2] Univ Liverpool, Dept Comp Sci, Liverpool, Merseyside, England

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015) | 2015年 / 9076卷

基金：

英国工程与自然科学研究理事会;

关键词：

Stochastic games; Nash equilibrium; Pure strategy; Finite-state strategy; COMPLEXITY;

D O I：

10.1007/978-3-319-17142-5_31

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：359 / 371

页数：13

共 50 条

[1] Pure Stationary Nash Equilibria for Discounted Stochastic Positional Games
Lozovanu, Dmitrii
Pickl, Stefan
CONTRIBUTIONS TO GAME THEORY AND MANAGEMENT, VOL XII, 2019, 12 : 246 - 260
[2] On Nash equilibria in stochastic games
Chatterjee, K
Majumdar, R
Jurdzinski, M
COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2004, 3210 : 26 - 40
[3] Nash equilibria of stochastic differential games
Zhang, Zhuokui
Chen, Huichan
Xi'an Dianzi Keji Daxue Xuebao/Journal of Xidian University, 2000, 27 (05): : 635 - 637
[4] Pure Nash Equilibria in Restricted Budget Games
Drees, Maximilian
Feldotto, Matthias
Riechers, Soeren
Skopalik, Alexander
COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 175 - 187
[5] Constrained pure Nash equilibria in graphical games
Greco, G
Scarcello, F
ECAI 2004: 16TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2004, 110 : 181 - 185
[6] Pure nash equilibria: Hard and easy games
Gottlob, G. (GOTTLOB@DBAI.TUWIEN.AC.AT), 1600, American Association for Artificial Intelligence (24):
[7] Pure nash equilibria in resource graph games
Harks T.
Klimm M.
Matuschke J.
Journal of Artificial Intelligence Research, 2021, 72 : 185 - 213
[8] Pure Nash Equilibria in Resource Graph Games
Harks, Tobias
Klimm, Max
Matuschke, Jannik
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2021, 72 : 185 - 213
[9] Pure Nash equilibria of coordination matrix games
Roberts, DP
ECONOMICS LETTERS, 2005, 89 (01) : 7 - 11
[10] Constrained Pure Nash Equilibria in Polymatrix Games
Simon, Sunil
Wojtczak, Dominik
THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2017, : 691 - 697

← 1 2 3 4 5 →