Communication complexity of approximate Nash equilibria

Yakov Babichenko, Aviad Rubinstein

For a constant $\epsilon$, we prove a poly(N) lower bound on the (randomized) communication complexity of $\epsilon$-Nash equilibrium in two-player NxN games. For n-player binary-action games we…