  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
payoffs of the other player. In order for a solution of reasonable quality to
be found, some amount of communication needs to take place between the players.
We are interested in algorithms where the communication is substantially less
than the contents of a payoff matrix, for example logarithmic in the size of
the matrix. When the communication is polylogarithmic in the number of
strategies n, we show how to obtain epsilon-approximate Nash equilibria for
epsilon approximately 0.438, and for well-supported approximate equilibria we
obtain epsilon approximately 0.732. For one-way communication we show that
epsilon=1/2 is achievable, but no constant improvement over 1/2 is possible,
even with unlimited one-way communication. For well-supported equilibria, no
value of epsilon less than 1 is achievable with one-way communication. When the
players do not communicate at all, epsilon-Nash equilibria can be obtained for
epsilon=3/4, and we also give a lower bound of slightly more than 1/2 on the
lowest constant epsilon achievable.
