Zero-Sum Game Techniques for Approximate Nash Equilibria

We apply existing, and develop new, zero-sum game techniques for designing polynomial-time algorithms to compute additive approximate Nash equilibria in bimatrix games. In particular, we give a polynomial-time algorithm that given an arbitrary bimatrix game as an input, outputs either an additive 1 3-Nash equilibrium or an additive 1 2-well-supported Nash equilibrium; and we give a polynomialtime algorithm that given a bimatrix game in which both payoff matrices are symmetric as an input, computes an additive 1 2-wellsupported Nash equilibrium. The former result is unusual: the obvious weakness is that the algorithm does not guarantee which of the two kinds of approximate equilibria it will output, but on the other hand each of the two approximation guarantees it gives are better than the best unconditional bounds known to be computable in polynomial time: 0.3393 for Nash equilibria and 0.6528 for wellsupported Nash equilibria. In the latter case, we motivate the interest in computing additive approximate Nash equilibria efficiently for bimatrix games with symmetric payoff matrices by proving that computing Nash equilibria in bimatrix games is PPAD-complete even if both of the payoff matrices are symmetric. * Research partially supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and by the EPSRC awards EP/D063191/1 and EP/G069034/1.