Algorithms Seminar
Playing Anonymous Games using Simple Strategies
Speaker:  Yu Cheng

Date: 
Thursday, September 7, 2017 
Time: 
12:00pm  1:00pm 
Location: 
D344 LSRC, Duke 


Abstract
We investigate the computational complexity of approximate Nash equilibria in anonymous games.
Our main algorithmic result is the following: For any nplayer anonymous game with a bounded number of strategies and any constant $\delta$, and $O(1/n^{1\delta})$approximate Nash equilibrium can be computed in polynomial time. Complementing this positive result, we show that if an $O(1/n^{1+\delta})$approximate equilibrium can be computed in polynomial time, then there is a fully polynomialtime approximation scheme for this problem.
Our approach exploits the connection between Nash equilibria in anonymous games and Poisson multinomial distributions (PMDs). Specifically, we prove a new probabilistic lemma establishing the following: Two PMDs, with large variance in each direction, whose first few moments are approximately matching are close in total variation distance. Our structural result strengthens previous work by providing a smooth tradeoff between the variance bound and the number of matching moments.
This is a joint work with Ilias Diakonikolas and Alistair Stewart.
Biography
Yu Cheng is a postdoc in Computer Science at Duke University.