Search Search

Equilibria Via Samples and Testing Equilibrium Behavior

Friday, October 4, 2013
12:00 PM - 1:00 PM
Location: Baxter 127
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.

Series: Linde Institute/Social and Information Sciences Laboratory Seminar Series (SISL)
For more information, please phone Ext. 6010 or email jenny@hss.caltech.edu

Upcoming events

Event archive