Approximate Well-supported Nash Equilibria Below Two-thirds
Approximate Well-supported Nash Equilibria Below Two-thirds
复制标题
有充分支持的纳什均衡近似低于三分之二
DOI：
10.1007/s00453-015-0029-3
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Fearnley J
中科院分区：
文献类型：
--
作者：
Fearnley J
在纳什均衡中，一个参与者最多可以通过改变他的行为来获益。最近的工作已经解决了如何最好地计算纳什均衡的问题，以及对于多项式时间算法存在什么值。一个好的纳什均衡（-WSNE）有额外的要求，任何策略，是由一个球员使用非零概率必须有回报最多小于最佳对策。最近Kontogiannis和Spirakis的算法展示了如何在多项式时间内计算2/3-WSNE，用于双矩阵游戏。在这里，我们介绍了一种新的技术，导致最坏情况下的近似保证的改善。
In an-Nash equilibrium, a player can gain at mostby changing his behaviour. Recent work has addressed the question of how best to compute-Nash equilibria, and for what values ofa polynomial-time algorithm exists. An-well-supportedNash equilibrium (-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at mostless than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.
登录
查看更多内容
线性规划中的敏感性分析：小心！
影响因子：
6.4
作者：
B. Jansen;J. Jong;C. Roos;T. Terlaky
通讯作者：
T. Terlaky
Bimatrix 博弈中恒定良好支持的近似均衡的高效算法
DOI：
10.1007/978-3-540-73420-8_52
发表时间：
2007
期刊：
ArXiv
影响因子：
--
作者：
S. Kontogiannis;P. Spirakis
通讯作者：
P. Spirakis
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
影响因子：
1
作者：
Barany, Irnre;Vempala, Santosh;Vetta, Adrian
通讯作者：
Vetta, Adrian
Bmatrix博弈中寻找近似均衡的实证研究
DOI：
--
发表时间：
2015
期刊：
The Sea
影响因子：
--
作者：
John Fearnley;Tobenna Peter Igwe;Rahul Savani
通讯作者：
Rahul Savani