On the communication complexity of approximate Nash equilibria

We study the problem of computing approximate Nash equilibria of bimatrix games, in a setting where players initially know their own payoffs but not the other player's. In order to find a solution of reasonable quality, some amount of communication is required. We study algorithms where the communication is substantially less than the size of the game. When the communication is polylogarithmic in the number of strategies, we show how to obtain ϵ-approximate Nash equilibrium for ϵ≈0.438, and for well-supported approximate equilibria we obtain ϵ≈0.732. For one-way communication we show that ϵ=12 is the best approximation quality achievable, while for well-supported equilibria, no value of ϵ<1 is achievable. When the players do not communicate at all, ϵ-Nash equilibria can be obtained for ϵ=34; we also provide a corresponding lower bound of slightly more than 12 on the smallest constant ϵ achievable.