Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games
Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games
复制标题
切分、政党归属和可满足性博弈中的近似纯纳什均衡
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Khanna
中科院分区：
文献类型：
--
作者：
Anand Bhalgat;T. Chakraborty;S. Khanna
切分游戏和党派关系游戏是众所周知的潜在游戏类别。Schaffer和Yannakakis证明了在这些博弈中计算纯Nash均衡是最小二乘完全的。在一般势对策中，即使是计算对纯均衡的任何有限近似的问题也是最小二乘完全的。我们证明了对于任意的∈>；0，我们设计了一个算法来在多项式时间内计算切割博弈和党派隶属博弈的(3+∈)-近似纯纳什均衡。在我们的工作之前，对于这些博弈，只知道一个平凡的多项式因子近似。我们的方法超越了Cut和党派关系游戏，扩展到更一般的可满足性游戏。
我们方法中的一个关键思想是在玩家身上创建偏序的预处理阶段。然后，我们将纳什动力学应用于从这个偏序得到的一系列受限对策。利用偏序的性质，我们证明了这个过程在多项式时间内收敛到一个近似的纳什均衡。这与其他一些类型的潜在博弈的早期结果形成了强烈的对比，这些潜在博弈通过直接应用纳什动力学来计算原始博弈的近似均衡。事实上，我们还表明，这样的技术不能产生FPTA，用于计算CUT和政党联盟博弈中的均衡。
Cut games and party affiliation games are well-known classes of potential games. Schaffer and Yannakakis showed that computing pure Nash equilibrium in these games is PLS-complete. In general potential games, even the problem of computing any finite approximation to a pure equilibrium is also PLS-complete. We show that for any ∈ > 0, we design an algorithm to compute in polynomial time a (3+∈)-approximate pure Nash equilibrium for cut and party affiliation games. Prior to our work, only a trivial polynomial factor approximation was known for these games. Our approach extends beyond cut and party affiliation games to a more general class of satisfiability games.
A key idea in our approach is a pre-processing phase that creates a partial order on the players. We then apply Nash dynamics to a sequence of restricted games derived from this partial order. We show that this process converges in polynomial-time to an approximate Nash equilibrium by strongly utilizing the properties of the partial order. This is in strong contrast to earlier results for some other classes of potential games that compute an approximate equilibrium by a direct application of Nash dynamics on the original game. In fact, we also show that such a technique cannot yield FPTAS for computing equilibria in cut and party affiliation games.