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
4 -Nash equilibrium 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+¸
4 -Nash equilibrium,
where ¸ is the minimum, among all Nash equilibria, expected payoff of
either player. The suggested algorithm runs in time polynomial in the
number of strategies available to the players.