On Pure Nash Equilibria in Stochastic Games
On Pure Nash Equilibria in Stochastic Games
复制标题
随机博弈中的纯纳什均衡
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
D. Wojtczak
中科院分区：
文献类型：
--
作者：
Ankush Das;S. Krishna;L. Manasa;Ashutosh Trivedi;D. Wojtczak
Ummels和Wojtczak开创了在满足特定边界的简单随机多人博弈中寻找纳什均衡的研究。他们表明，对于有9个玩家的博弈而言，决定是否存在纯策略纳什均衡(PureNE)是不可决定的，其中固定玩家几乎肯定会赢。他们还表明，对于有14个玩家的有限策略纳什均衡(Finne)来说，这个问题仍然是不可决定的。在这篇文章中，我们证明了对于(5)个或更多的玩家，纯NE和Finne问题仍然是不可判定的，从而改进了他们的不可判定结果。
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.