# Communication complexity of approximate Nash equilibria

 Computer Science/Discrete Mathematics Seminar I Topic: Communication complexity of approximate Nash equilibria Speaker: Aviad Rubinstein Affiliation: University of California, Berkeley Date: Monday, October 31 Time/Room: 11:15am - 12:15pm/West Building Lecture Hall Video Link: https://video.ias.edu/csdm/2016/1031-AviadRubinstein

For a constant $\epsilon$, we prove a $\mathrm{poly}(N)$ lower bound on the communication complexity of $\epsilon$-Nash equilibrium in two-player $N \times N$ games. For $n$-player binary-action games we prove an $\exp(n)$ lower bound for the communication complexity of $(\epsilon,\epsilon)$-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least $(1-\epsilon)$-fraction of the players are $\epsilon$-best replying. https://arxiv.org/abs/1608.06580 Joint work with Yakov Babichenko.