Nash equilibria in graphical games on trees revisited
Nash equilibria in graphical games on trees revisited
复制标题
DOI：
10.1145/1134707.1134719
复制
发表时间：
2006-06
期刊：
影响因子：
--
通讯作者：
Edith Elkind;L. A. Goldberg;P. Goldberg
中科院分区：
文献类型：
--
作者：
Edith Elkind;L. A. Goldberg;P. Goldberg
图形游戏已被提出作为一个游戏理论模型的大规模分布式网络的非合作代理。当参与人数量较大，底层图的度较低时，它们提供了一种简洁的方式来表示参与人的收益。最近的研究表明，在一个一般的3度图形游戏中，每个玩家有两个动作的纳什均衡问题对于复杂性类PPAD是完全的，这表明这个问题不太可能有任何多项式时间算法。在本文中，我们研究了有界度树上每个玩家有两个动作的图形游戏的复杂性。这种设置首先由Kearns，Littman和Singh考虑，他们提出了一种基于动态规划的算法，可以计算此类游戏的所有纳什均衡。他们的算法的运行时间是指数级的，尽管近似平衡可以有效地计算。后来，Littman，Kearns和Singh提出了一个改进的算法，可以在多项式时间内找到一个纳什均衡。我们表明，这种修改后的算法是不正确的输出并不总是一个纳什均衡。然后，我们提出了一个新的算法，该算法是基于Kearns等人的思想。如果输入图是一条路径，则在二次时间内计算所有纳什均衡，如果它是一个最大度为2的任意图，则在多项式时间内计算所有纳什均衡。此外，我们的算法可以用来计算任意树上的图形游戏的纳什均衡，但运行时间可以是指数，即使树有界度。我们证明了这是不可避免的--任何这种类型的算法都需要指数时间，即使是在路径宽度为2的有界度树上。这是一个悬而未决的问题，我们的算法是否在多项式时间内运行的路径宽度为1的图，但我们发现，找到一个纳什均衡的2-动作图形游戏，其中底层图具有最大程度3和恒定的路径宽度是PPAD-完全的（所以是不太可能是听话的）。
Graphical games have been proposed as a game-theoretic model of large-scale distributed networks of non-cooperative agents. When the number of players is large, and the underlying graph has low degree, they provide a concise way to represent the players' payoffs. It has recently been shown that the problem of finding Nash equilibria in a general degree-3 graphical game with two actions per player is complete for the complexity class PPAD, indicating that it is unlikely that there is any polynomial-time algorithm for this problem. In this paper, we study the complexity of graphical games with two actions per player on bounded-degree trees. This setting was first considered by Kearns, Littman and Singh, who proposed a dynamic programming-based algorithm that computes all Nash equilibria of such games. The running time of their algorithm is exponential, though approximate equilibria can be computed efficiently. Later, Littman, Kearns and Singh proposed a modification to this algorithm that can find a single Nash equilibrium in polynomial time. We show that this modified algorithm is incorrect-the output is not always a Nash equilibrium. We then propose a new algorithm that is based on the ideas of Kearns et al. and computes all Nash equilibria in quadratic time if the input graph is a path, and in polynomial time if it is an arbitrary graph of maximum degree 2. Moreover, our algorithm can be used to compute Nash equilibria of graphical games on arbitrary trees, but the running time can be exponential, even when the tree has bounded degree. We show that this is inevitable -- any algorithm of this type will take exponential time, even on bounded-degree trees with pathwidth 2. It is an open question whether our algorithm runs in polynomial time on graphs with pathwidth 1, but we show that finding a Nash equilibrium for a 2-action graphical game in which the underlying graph has maximum degree 3 and constant pathwidth is PPAD-complete (so is unlikely to be tractable).