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


We investigate the computational complexity of approximate Nash equilibria in anonymous games. Our main algorithmic result is the following: For any n-player 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 polynomial-time 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.


Yu Cheng is a postdoc in Computer Science at Duke University.