New algorithms for approximate Nash equilibria in bimatrix games

AbstractWe 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. We first provide a simpler algorithm, that achieves a 0.38197-approximation, which is exactly the same factor as the algorithm of Daskalakis, Mehta and Papadimitriou. This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast and simple, as it requires solving only one linear program and it is based on using the solution of an auxiliary zero-sum game as a starting point. Finally we also exhibit a simple reduction that allows us to compute approximate equilibria for multi-player games by using algorithms for two-player games