  We prove communication complexity lower bounds for (possibly mixed) Nash
equilibrium in potential games. In particular, we show that finding a Nash
equilibrium requires $poly(N)$ communication in two-player $N \times N$
potential games, and $2^{poly(n)}$ communication in $n$-player two-action
games. To the best of our knowledge, these are the first results to demonstrate
hardness in any model of (possibly mixed) Nash equilibrium in potential games.
