Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar

Note: This seminar has been moved from October 11, 2013

We show that in an n-player m-action strategic form game, one can obtain an approximate equilibrium by sampling an extremely small number of realization from any given mixed-action equilibrium. We study three notions of equilibrium: Nash, correlated and coarse correlated. For each one of them we obtain upper and lower bounds on the asymptotic worst-case number k of samples needed in order for the empirical frequency of the realized action profiles to form an approximate equilibrium with probability close to one.

Our results include a substantial improvement over the previously known upper bounds on the existence of a k-uniform approximate equilibrium in games with many players. We show that k is poly-logarithmic in m and n, whereas the best previously known results were polynomial in n.

The results induce simple algorithms for testing whether players are playing according to an equilibrium (Nash, correlated and coarse correlated). The algorithms requires extremely small number of samples.