An Empirical Study of Finding Approximate Equilibria in Bimatrix Games
An Empirical Study of Finding Approximate Equilibria in Bimatrix Games
复制标题
Bmatrix博弈中寻找近似均衡的实证研究
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Rahul Savani
中科院分区：
文献类型：
--
作者：
John Fearnley;Tobenna Peter Igwe;Rahul Savani
虽然已经有许多关于在双矩阵博弈中寻找精确纳什均衡的方法的有效性的研究，但关于寻找近似纳什均衡的实证工作却很少。在这里，我们提供了这样一项研究，比较了许多近似方法和精确方法。特别是，我们探索了近似均衡的质量和找到近似均衡所需的运行时间之间的权衡。我们发现现有的库 GAMUT（已用于测试精确方法的事实上的标准）不足以作为近似方法的测试平台，因为它的许多游戏都具有纯均衡或其他易于找到的良好近似均衡。我们通过纳入新的有趣的 bimatrix 游戏系列，并研究规模高达 $$2000 \times 2000$$ 的 bimatrix 游戏，扩展了研究的广度和深度。最后，我们为寻找近似纳什均衡的最佳算法提供了新的接近最坏情况的示例。
While there have been a number of studies about the efficacy of methods to find exact Nash equilibria in bimatrix games, there has been little empirical work on finding approximate Nash equilibria. Here we provide such a study that compares a number of approximation methods and exact methods. In particular, we explore the trade-off between the quality of approximate equilibrium and the required running time to find one. We found that the existing library GAMUT, which has been the de facto standard that has been used to test exact methods, is insufficient as a test bed for approximation methods since many of its games have pure equilibria or other easy-to-find good approximate equilibria. We extend the breadth and depth of our study by including new interesting families of bimatrix games, and studying bimatrix games upto size $$2000 \times 2000$$. Finally, we provide new close-to-worst-case examples for the best-performing algorithms for finding approximate Nash equilibria.
有充分支持的纳什均衡近似低于三分之二
影响因子：
1.1
作者：
Fearnley J
通讯作者：
Fearnley J