Approximate Equilibria in Games with Few Players
Approximate Equilibria in Games with Few Players
复制标题
少数玩家博弈中的近似均衡
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Heiko Röglin
中科院分区：
文献类型：
--
作者：
Patrick Briest;P. Goldberg;Heiko Röglin
我们研究的问题，计算近似纳什均衡（ε-纳什均衡）的正常形式的游戏，其中的球员人数是一个小常数。我们考虑的方法，寻找解决方案的支持大小不变。从最近的工作中可以知道，在2人的情况下，可以很容易地找到1/2纳什均衡，但一般来说，不能实现比1/2更小的值。在本文中，我们将这些结果推广到k-局中人的情况，并发现k = 1-1/k是可行的，但不能被改进。我们展示了如何更强的结果为2-玩家的情况下，可以使用，以稍微改善后，在k-玩家的情况下获得的k = 1-1/k。
We study the problem of computing approximate Nash equilibria (epsilon-Nash equilibria) in normal form games, where the number of players is a small constant. We consider the approach of looking for solutions with constant support size. It is known from recent work that in the 2-player case, a 1/2-Nash equilibrium can be easily found, but in general one cannot achieve a smaller value of epsilon than 1/2. In this paper we extend those results to the k-player case, and find that epsilon = 1-1/k is feasible, but cannot be improved upon. We show how stronger results for the 2-player case may be used in order to slightly improve upon the epsilon = 1-1/k obtained in the k-player case.