Distributed Methods for Computing Approximate Equilibria
Distributed Methods for Computing Approximate Equilibria
复制标题
计算近似平衡的分布式方法
DOI：
10.1007/s00453-018-0465-y
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
Czumaj A
中科院分区：
文献类型：
--
作者：
Czumaj A
我们提出了一个新的分布式方法来计算近似纳什均衡的双矩阵游戏。与以前同时分析两个支付矩阵的方法（例如，通过求解结合两个玩家的支付的单个LP）相比，我们的算法首先求解两个独立的LP，每个LP都来自两个支付矩阵中的一个，然后仅使用玩家之间的有限通信来计算近似纳什均衡。我们的方法给出了改进的边界上的计算近似纳什均衡在一些不同的设置的复杂性。首先，它给出了一个多项式时间算法来计算近似的良好支持纳什均衡（WSNE），总是找到一个0.6528-WSNE，击败了以前的最佳保证0.6608。其次，由于我们的算法分别解决了两个LP，它可以应用于在有限的通信设置中给出一个改进的界限，给出一个随机的期望多项式时间算法，该算法使用多对数通信，并找到一个0.6528-WSNE，这击败了以前最好的已知保证0.732。它也可以应用于近似纳什均衡的情况下，我们得到一个随机的预期多项式时间算法，使用多对数通信，总是找到一个0.382近似纳什均衡，这提高了以前的最佳保证0.438。最后，该方法也可以应用于查询复杂度设置，以给出一个算法，使得支付查询，并始终找到一个0.6528-WSNE，这提高了以前的最佳已知的保证2/3。
We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players’ payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then computes an approximate Nash equilibrium using only limited communication between the players. Our method gives improved bounds on the complexity of computing approximate Nash equilibria in a number of different settings. Firstly, it gives a polynomial-time algorithm for computingapproximate well supported Nash equilibria (WSNE)that always finds a 0.6528-WSNE, beating the previous best guarantee of 0.6608. Secondly, since our algorithm solves the two LPs separately, it can be applied to give an improved bound in the limited communication setting, giving a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE, which beats the previous best known guarantee of 0.732. It can also be applied to the case ofapproximate Nash equilibria, where we obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and always finds a 0.382-approximate Nash equilibrium, which improves the previous best guarantee of 0.438. Finally, the method can also be applied in the query complexity setting to give an algorithm that makespayoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3.
登录
查看更多内容
Bimatrix 游戏中得到良好支持的近似均衡：图论方法
DOI：
10.1007/978-3-540-74456-6_53
发表时间：
2007
期刊：
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
影响因子：
--
作者：
S. Kontogiannis;P. Spirakis
通讯作者：
P. Spirakis
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
Bmatrix博弈中寻找近似均衡的实证研究
DOI：
--
发表时间：
2015
期刊：
The Sea
影响因子：
--
作者：
John Fearnley;Tobenna Peter Igwe;Rahul Savani
通讯作者：
Rahul Savani
DOI：
--
发表时间：
2012
期刊：
Games Econ. Behav.
影响因子：
--
作者：
P. Goldberg;A. Pastink
通讯作者：
A. Pastink
DOI：
10.1145/1015330.1015351
发表时间：
2004
期刊：
Proceedings of the twenty-first international conference on Machine learning
影响因子：
--
作者：
Vincent Conitzer;T. Sandholm
通讯作者：
T. Sandholm