In this paper we propose a new methodology for determining approximate
Nash equilibria of noncooperative bimatrix games, and based on
that, we provide an efficient algorithm that computes
$0.3393$-approximate equilibria, the best approximation to date.
The methodology is based on the formulation of
an appropriate function of pairs of mixed strategies reflecting the
maximum deviation of the players' payoffs from the best payoff each
player could achieve given the strategy chosen by the other. We then
seek to minimize such a function using descent procedures. Because it is
unlikely to be able to find global minima in polynomial time, given
the recently proven intractability of the problem, we concentrate on
the computation of stationary points and prove that they can be
approximated arbitrarily closely in polynomial time and that they have
the above-mentioned approximation property. Our result provides the
best $\epsilon$ to date for polynomially computable
$\epsilon$-approximate Nash equilibria of bimatrix games. Furthermore,
our methodology for computing approximate Nash equilibria has not been used by others.