New Algorithms for Approximate Nash Equilibria in Bimatrix Games

We consider the problem of computing additively approximate Nash equilibria in non-cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. Our work improves the previously best known (0.38197 + Ɛ)-approximation algorithm of Daskalakis, Mehta and Papadimitriou [6]. First, we provide a simpler algorithm, which also achieves 0.38197. This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast, as it requires solving only one linear program and it is based on using the solution of an auxiliary zerosum game as a starting point.