On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games
On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games
复制标题
稀疏输赢多人博弈中纳什均衡的逼近
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Xiaotie Deng
中科院分区：
文献类型：
--
作者：
Zhengyang Liu;Jiawei Li;Xiaotie Deng
多矩阵博弈是n个参与人的多人博弈，每个参与人从自己的纯策略列表中选择一个纯策略。每个参与人的效用是在其选择的策略和其邻居的策略下，它从所有邻居的两个参与人博弈中获得的收益之和。作为两人游戏的自然延伸（又名）。双矩阵游戏），多矩阵游戏被广泛用于真实的世界场景中的多代理游戏。
在本文中，我们证明了在多项式精度内逼近多矩阵博弈的纳什均衡的问题是PPAD困难的，即使在稀疏和输赢的。这一结果进一步挑战了纳什均衡作为多智能体环境中的解决方案概念的可预测性。当博弈进一步受限时，我们还提出了一个简单有效的算法.我们一起建立了这类博弈的一个新的二分法定理。它也是独立的利益，探索纳什均衡的计算和结构特性。
A polymatrix game is a multi-player game over n players, where each player chooses a pure strategy from a list of its own pure strategies. The utility of each player is a sum of payoffs it gains from the two player's game from all its neighbors, under its chosen strategy and that of its neighbor. As a natural extension to two-player games (a.k.a. bimatrix games), polymatrix games are widely used for multi-agent games in real world scenarios.
In this paper we show that the problem of approximating a Nash equilibrium in a polymatrix game within the polynomial precision is PPAD-hard, even in sparse and win-lose ones. This result further challenges the predictability of Nash equilibria as a solution concept in the multi-agent setting. We also propose a simple and efficient algorithm, when the game is further restricted. Together, we establish a new dichotomy theorem for this class of games. It is also of independent interest for exploring the computational and structural properties in Nash equilibria.