Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
复制标题
通过支付查询找到 Bimatrix 博弈的近似纳什均衡
DOI：
10.1145/2956579
复制
发表时间：
2016
影响因子：
1.2
通讯作者：
Fearnley J
中科院分区：
文献类型：
--
作者：
Fearnley J
研究了在AK×kbimatrix博弈中寻找近似均衡的确定性和随机化查询复杂性。我们证明了即使在零一常和博弈中，当ϵ<；1/2是ϵ(K2)时，寻找Ω-Nash均衡的确定性查询复杂性也是成立的。结合以前的结果[Fearnley et al.2013]，这完整地刻画了近似纳什均衡的确定性查询复杂性。我们还研究了随机查询算法。我们给出了一个求解(3-√5/2+ϵ)-纳什均衡的随机化算法，它使用O(k.logk/ϵ2)个支付查询，这表明随机化可以打破确定性算法的1/2障碍。对于支持良好的纳什均衡，我们首先给出了一个使用O(k.logk/ϵ4)个支付查询来寻找零和双阵对策的ϵ-⅔+ϵ均衡的随机化算法，然后利用这个算法得到了一个使用O(k.logk/ϵ4)个支付查询来寻找一般双矩阵对策的(K.logk)-WSNE的随机算法。最后，我们通过证明随机算法需要Ω(K2)支付查询才能找到与ϵ<；1/4k的ϵ-Nash均衡，甚至在零一常和博弈中，我们开始了对双矩阵博弈背景下的随机算法下界的研究。特别是，这排除了查询效率高的随机算法来寻找精确的纳什均衡。
We study the deterministic and randomized query complexity of finding approximate equilibria in ak×kbimatrix game. We show that the deterministic query complexity of finding an ϵ-Nash equilibrium when ϵ < ½ is Ω(k2), even in zero-one constant-sum games. In combination with previous results [Fearnley et al. 2013], this provides a complete characterization of the deterministic query complexity of approximate Nash equilibria. We also study randomized querying algorithms. We give a randomized algorithm for finding a (3-√5/2 + ϵ)-Nash equilibrium usingO(k.logk/ϵ2) payoff queries, which shows that the ½ barrier for deterministic algorithms can be broken by randomization. For well-supported Nash equilibria (WSNE), we first give a randomized algorithm for finding an ϵ-WSNE of a zero-sum bimatrix game usingO(k.logk/ϵ4) payoff queries, and we then use this to obtain a randomized algorithm for finding a (⅔ + ϵ)-WSNE in a general bimatrix game usingO(k.logk/ϵ4) payoff queries. Finally, we initiate the study of lower bounds against randomized algorithms in the context of bimatrix games, by showing that randomized algorithms require Ω(k2) payoff queries in order to find an ϵ-Nash equilibrium with ϵ < 1/4k, even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.
登录
查看更多内容
DOI：
--
发表时间：
2013
期刊：
Games Econ. Behav.
影响因子：
--
作者：
S. Hart;N. Nisan
通讯作者：
N. Nisan
匿名博弈中近似均衡的查询复杂度
DOI：
--
发表时间：
2014
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
P. Goldberg;S. Turchetta
通讯作者：
S. Turchetta
DOI：
10.1145/2482540.2482558
发表时间：
2013-02
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
John Fearnley;Martin Gairing;P. Goldberg;Rahul Savani
通讯作者：
John Fearnley;Martin Gairing;P. Goldberg;Rahul Savani
影响因子：
1.1
作者：
Czumaj A
通讯作者：
Czumaj A
有充分支持的纳什均衡近似低于三分之二
影响因子：
1.1
作者：
Fearnley J
通讯作者：
Fearnley J