论文标题
完美信息随机游戏中固定纳什平衡的真实完整性的存在理论
Existential Theory of the Reals Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games
论文作者
论文摘要
我们表明，在多玩家完美信息递归游戏（即带终端奖励的随机游戏）中确定是否存在固定的NASH平衡，确保每个玩家的某些回报是真实的存在理论。我们的结果适用于无环游戏，在该游戏中，可以通过向后诱导有效地计算NASH平衡，甚至针对具有非负终端奖励的确定性无环游戏。我们将结果进一步扩展到了纳什均衡的存在，其中一个球员肯定会赢得胜利。将我们的结果与已知的小工具游戏相结合，而没有任何固定的NASH平衡，我们就可以获得循环游戏，只是决定存在任何固定的NASH平衡的存在是真实的存在理论。这适用于Reach-A-stet游戏，停留的游戏以及确定性的递归游戏。
We show that the problem of deciding whether in a multi-player perfect information recursive game (i.e. a stochastic game with terminal rewards) there exists a stationary Nash equilibrium ensuring each player a certain payoff is Existential Theory of the Reals complete. Our result holds for acyclic games, where a Nash equilibrium may be computed efficiently by backward induction, and even for deterministic acyclic games with non-negative terminal rewards. We further extend our results to the existence of Nash equilibria where a single player is surely winning. Combining our result with known gadget games without any stationary Nash equilibrium, we obtain that for cyclic games, just deciding existence of any stationary Nash equilibrium is Existential Theory of the Reals complete. This holds for reach-a-set games, stay-in-a-set games, and for deterministic recursive games.
