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:

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. Joint work with Yakov Babichenko.