The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games
The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games
复制标题
输赢博弈纳什均衡决策问题的复杂性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Mavronicolas
中科院分区：
文献类型：
--
作者：
Vittorio Bilò;M. Mavronicolas
我们重新考虑了决定的复杂性，给定一个（有限）战略博弈，是否存在具有某些自然属性的纳什均衡;这样的决策问题是众所周知的$cal NP$-完全[2，6，10]。我们表明，这种复杂性保持不变时，所有的效用被限制为0或1，因此，输赢游戏是复杂的一般游戏，这样的决策问题。
We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist; such decision problems are well-known to be $cal NP$-complete [2, 6, 10] . We show that this complexity remains unchanged when all utilities are restricted to be 0 or 1; thus, win-lose games are as complex as general games with respect to such decision problems.