Polymatrix Game 是一类重要的多人博弈模型。这一模型最主要的特点是能拆成多对双人博弈，如下图所示。每人的收益为所有他参与的二人博弈的收益和。另外值得强调的一点是每人在所有的二人博弈中都只能使用同一个策略。整个游戏可以用一个2n×2n的收益矩阵表示下来。

本文研究了纳什均衡计算在一类非常特殊的 Polymatrix Game 下的计算复杂度。我们定义了(a,b) -Sparse Win-Lose Polymatrix Game (SWLP)，其中：

  • (a,b) -Sparse 表示收益矩阵每行最多有a个非零元素，每列最多有b个非零元素；
    • Win-Lose 表示收益矩阵每个元素为 0 或 1。

本文的主要结论为： 1. 求解 -SWLP 的多项式近似纳什均衡点是 PPAD-Complete 的； 2. 给出了求解 -SWLP 或 -SWLP 的精确纳什均衡解的高效（多项式）算法。

本文的主要结论通过改进前人证明框架得到，由于需要较多预备知识，请感兴趣的读者阅读原论文。

论文名称：On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games

内容中包含的图片若涉及版权问题，请及时与我们联系删除