Name
Abstract | ||
|---|---|---|
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 ε-approximate equilibrium, forεr-1/rin the additive case, andε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 computeε-equilibria with ε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 εε-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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-79309-0_24 | SAGT |
Keywords | Field | DocType |
approximate nash equilibrium,rm ln,additive case weshow,approximate nash equilibria,additive andmultiplicative sense,additive case,multi-player games,multiplicative case,rthe support size,additive approximation,approximate equilibriumwith support size,approximate equilibrium,lower bound,nash equilibrium,nash equilibria | Quadratic growth,Mathematical economics,Combinatorics,Mathematical optimization,Multiplicative function,Upper and lower bounds,Time complexity,Nash equilibrium,Mathematics | Conference |
Volume | ISSN | Citations |
4997 | 0302-9743 | 16 |
PageRank | References | Authors |
0.84 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sébastien Hémon | 1 | 16 | 1.18 |
| Michel de Rougemont | 2 | 16 | 0.84 |
| Miklos Santha | 3 | 728 | 92.42 |