  We present a new, distributed method to compute approximate Nash equilibria
in bimatrix games. In contrast to previous approaches that analyze the two
payoff matrices at the same time (for example, by solving a single LP that
combines the two players payoffs), our algorithm first solves two independent
LPs, each of which is derived from one of the two payoff matrices, and then
compute approximate Nash equilibria using only limited communication between
the players.
  Our method has several applications for improved bounds for efficient
computations of approximate Nash equilibria in bimatrix games. First, it yields
a best polynomial-time algorithm for computing \emph{approximate well-supported
Nash equilibria (WSNE)}, which guarantees to find a 0.6528-WSNE in polynomial
time. Furthermore, since our algorithm solves the two LPs separately, it can be
used to improve upon the best known algorithms in the limited communication
setting: the algorithm can be implemented to obtain a randomized
expected-polynomial-time algorithm that uses poly-logarithmic communication and
finds a 0.6528-WSNE. The algorithm can also be carried out to beat the best
known bound in the query complexity setting, requiring $O(n \log n)$ payoff
queries to compute a 0.6528-WSNE. Finally, our approach can also be adapted to
provide the best known communication efficient algorithm for computing
\emph{approximate Nash equilibria}: it uses poly-logarithmic communication to
find a 0.382-approximate Nash equilibrium.
