skip to main content
Caltech

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

Friday, October 4, 2013
12:00pm to 1:00pm
Add to Cal
Baxter 127
Equilibria Via Samples and Testing Equilibrium Behavior
Yakov Babichenko, Wally Baer and Jeri Weiss Postdoctoral Scholar in Computing & Mathematical Sciences, Caltech,

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.

For more information, please contact Jenny Niese by phone at Ext. 6010 or by email at [email protected].