Polynomial Algorithms for Approximating Nash Equilibria Of Bimatrix Games

We focus on the problem of computing an ɛ-Nash equilibrium of a bimatrix game, when ɛ is an absolute constant. We present a simple algorithm for computing a 3-Nash equilib-4 rium for any bimatrix game in strongly polynomial time and we next show how to extend this algorithm so as to obtain a (potentially stronger) parameterized approximation. Namely, we present an algorithm that computes a 2+λ+ɛ-Nash equilibrium for any ɛ, where λ is the min-4 imum, among all Nash equilibria, expected payoff of either player. The suggested algorithm and the number of strategies available to the players. runs in time polynomial in 1