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.