We study the complexity of computing a uniform Nash equilibrium on a bimatrix game. In general, it is known that such a problem is NP-complete even if a game is a win-lose bimatrix game [BIL08]. However, if the bipartite digraph defined by a win-lose bimatrix game is planar, then there is a polynomial-time algorithm to find a uniform Nash equilibrium [AOV07]. It is still open how hard it is to compute a uniform Nash equilibrium on a bimatrix game that is planar but not win-lose. This paper presents the NP-hardness for the problem of deciding whether a given planar bimatrix game has uniform Nash equilibria even if every component of both players' payoff matrices consists of three types of non-zero elements.
翻译：我们研究了在双马基游戏上计算统一的纳什平衡的复杂性。 一般来说, 即使游戏是双赢双马基游戏, 这个问题也已经是NP了。 但是, 如果双马基游戏所定义的两边分界线是平坦的, 那么就有一个多元时间算法可以找到统一的纳什平衡 [AOV07] 。 在双马基游戏上计算统一的纳什平衡是多么困难, 双马基游戏是平滑的, 但不是双赢的。 本文展示了NP在决定某个特定的平板双马基游戏是否具有统一的纳什平衡问题上的强硬性, 即使两个玩家的支付矩阵的每一个组成部分都包含三种非零元素。
相关内容
微信扫码咨询专知VIP会员