Computing Exact and Approximate Nash Equilibria in 2-Player Games

The problem of computing a Nash equilibrium in a normal form 2-player game (or bimatrix games) is PPAD-complete in general, while it can be efficiently solved in a special subclass which we call regular bimatrix games. The current best approximation algorithm, proposed in [19], achieves a guarantee of 0.3393. In this paper we design a polynomial time algorithm for computing exact and approximate Nash equilibria for bimatrix games. The novelty of this contribution is twofold. For regular bimatrix games, it allows to compute equilibria whose payoffs optimize any objective function and meet any set of constraints which can be expressed through linear programming, while, in the general case, it computes a-approximate Nash equilibria, where a is the maximum difference between any two payoffs in the same strategy of any player. Hence, our algorithm improves the best know approximation guarantee for the bimatrices in which alpha < 0.3393.