Computing good nash equilibria in graphical games
Computing good nash equilibria in graphical games
复制标题
DOI：
10.1145/1250910.1250935
复制
发表时间：
2007-03
期刊：
影响因子：
--
通讯作者：
Edith Elkind;L. A. Goldberg;P. Goldberg
中科院分区：
文献类型：
--
作者：
Edith Elkind;L. A. Goldberg;P. Goldberg
本文研究了图解博弈中的公平均衡选择问题。我们的方法基于Kearns等人提出的最佳响应策略的数据结构。[13]作为表示图解博弈的所有纳什均衡的一种方式。文献[9]证明了，只要基础图是路径，则最优响应策略是多项式大小的。在本文中，我们证明了如果基础图是富度树，并且最佳响应策略是多项式大小的，那么存在一个有效的算法，它构造了一个纳什均衡，保证所有参与者都有一定的收益。另一个有吸引力的解决方案概念是最大化社会福利的纳什均衡。我们证明了，虽然精确地计算后者是不可行的(我们证明了解决这个问题可能涉及任意高次的代数数)，但是只要最优响应策略是多项式大小的，就存在找到这样一个均衡的FPTAS。这两种算法可以组合在一起，以产生满足各种公平标准的纳什均衡。
This paper addresses the problem of fair equilibrium selection in graphical games. Our approach is based on the data structure called the best response policy, which was proposed by Kearns et al. [13] as a way to represent all Nash equilibria of a graphical game. In [9], it was shown that the best response policy has polynomial size as long as the underlying graph is a path. In this paper, we show that if the underlying graph is abounded-degree tree and the best response policy has polynomial size then there is an efficient algorithm which constructs a Nash equilibrium that guarantees certain payoffs to all participants. Another attractive solution concept is a Nash equilibrium that maximizes the social welfare. We show that, while exactly computing the latter is infeasible (we prove that solving this problem may involve algebraic numbers of an arbitrarily high degree), there exists an FPTAS for finding such an equilibrium as long as the best response policy has polynomial size. These two algorithms can be combined to produce Nash equilibria that satisfy various fairness criteria.