Simple algorithmic techniques to approximate nash equilibria

We study the problem of computing approximate Nash equilibria in symmetric bimatrix games. We first give an approximation scheme for Nash equilibria in such games. Even though this scheme is not polynomial-time, it gives an interesting performance guarantee that depends on structural properties of the (exact) Nash equilibria of the game.