The Complexity of Nash Equilibria in Stochastic Multiplayer Games
The Complexity of Nash Equilibria in Stochastic Multiplayer Games
复制标题
随机多人博弈中纳什均衡的复杂性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
D. Wojtczak
中科院分区：
文献类型：
--
作者：
M. Ummels;D. Wojtczak
本文分析了具有$\omega$-正则目标的随机多人博弈中求纳什均衡的计算复杂性。我们表明，限制搜索空间的均衡，其收益落入一定的区间可能会导致不可判定性。特别地，我们证明了以下问题是不可判定的：给定一个博弈~$\mathcal{G}$，是否存在纯策略纳什均衡~$\mathcal{G}$，其中参与人0以概率~$1$获胜。此外，如果该问题仅限于具有（无界）有限记忆的策略，则该问题仍然是不可判定的。然而，如果允许随机策略，可判定性仍然是一个开放的问题;在这种情况下，我们只能证明NP-困难。获得问题的可证明可判定变体的一种方法是将策略限制为位置或静止。由于这两个问题的复杂性，我们分别得到了NP问题的一个公共下界以及NP问题和PSPACE问题的上界。最后，我们挑出一般问题的一个特殊情况，在许多情况下，承认一个有效的解决方案。特别是，我们证明，决定存在的平衡，每个玩家要么赢或输的概率~$1$可以在多项式时间的游戏，例如，每个玩家的目标是由奇偶条件与有限数量的优先级。
textabstractWe analyse the computational complexity of finding Nash equilibria in stochastic multiplayer games with $\omega$-regular objectives. We show that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given a game~$\mathcal{G}$, does there exist a pure-strategy Nash equilibrium of~$\mathcal{G}$ where player 0 wins with probability~$1$. Moreover, this problem remains undecidable if it is restricted to strategies with (unbounded) finite memory. However, if randomised strategies are allowed, decidability remains an open problem; we can only prove NP-hardness in this case. One way to obtain a provably decidable variant of the problem is to restrict the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and PSPACE respectively. Finally, we single out a special case of the general problem that, in many cases, admits an efficient solution. In particular, we prove that deciding the existence of an equilibrium in which each player either wins or loses with probability~$1$ can be done in polynomial time for games where, for instance, the objective of each player is given by a parity condition with a bounded number of priorities.