Communication complexity of approximate Nash equilibria

Abstract

For a constant $ε$, we prove a poly(N) lower bound on the (randomized) communication complexity of $ε$-Nash equilibrium in two-player NxN games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of $(ε,ε)$-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least $(1-ε)$-fraction of the players are $ε$-best replying.

Second revision extends the lower bounds to randomized communication