Approximate Nash Equilibria for Multi-player Games
Approximate Nash Equilibria for Multi-player Games
复制标题
多人游戏的近似纳什均衡
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Santha
中科院分区：
文献类型：
--
作者：
Sébastien Hémon;M. D. Rougemont;M. Santha
We consider games of complete information with r≥ 2players, and study approximate Nash equilibria in the additive andmultiplicative sense, where the number of pure strategies of theplayers is n. We establish a lower bound of$\sqrt[r-1]{\frac{{\rm ln} n - 2 {\rm ln} {\rm ln} n - {\rm ln}r}{{\rm ln} r}} $ on the size of the support of strategy profileswhich achieve an e-approximate equilibrium, fore< r-1/rin the additive case, ande< r- 1 in the multiplicative case. Weexhibit polynomial time algorithms for additive approximation whichrespectively compute an $\frac{r-1}{r}$-approximate equilibriumwith support sizes at most 2, and which extend the algorithms for 2players with better than $\frac{1}{2}$-approximations to computee-equilibria with e<r-1/r. Finally, we investigate the sampling basedtechnique for computing approximate equilibria of Lipton et al.[12] with a new analysis, that instead of Hoeffding's bound usesthe more general McDiarmid's inequality. In the additive case weshow that for 0 < e< 1, ane-approximate Nash equilibrium with support size$\frac{2r {\rm ln} (nr+r)}{\varepsilon^2}$ can be obtained,improving by a factor of rthe support size of [12]. Wederive an analogous result in the multiplicative case where thesupport size depends also quadratically on g-1,for any lower bound gon the payoffs of the players at somegiven Nash equilibrium.
We consider games of complete information with r≥ 2players, and study approximate Nash equilibria in the additive andmultiplicative sense, where the number of pure strategies of theplayers is n. We establish a lower bound of$\sqrt[r-1]{\frac{{\rm ln} n - 2 {\rm ln} {\rm ln} n - {\rm ln}r}{{\rm ln} r}} $ on the size of the support of strategy profileswhich achieve an e-approximate equilibrium, fore< r-1/rin the additive case, ande< r- 1 in the multiplicative case. Weexhibit polynomial time algorithms for additive approximation whichrespectively compute an $\frac{r-1}{r}$-approximate equilibriumwith support sizes at most 2, and which extend the algorithms for 2players with better than $\frac{1}{2}$-approximations to computee-equilibria with e<r-1/r. Finally, we investigate the sampling basedtechnique for computing approximate equilibria of Lipton et al.[12] with a new analysis, that instead of Hoeffding's bound usesthe more general McDiarmid's inequality. In the additive case weshow that for 0 < e< 1, ane-approximate Nash equilibrium with support size$\frac{2r {\rm ln} (nr+r)}{\varepsilon^2}$ can be obtained,improving by a factor of rthe support size of [12]. Wederive an analogous result in the multiplicative case where thesupport size depends also quadratically on g-1,for any lower bound gon the payoffs of the players at somegiven Nash equilibrium.