Abstract | We focus on the problem of computing an epsilon (Porson)-Nash equilibrium of a bimatrix game, when epsilon (Porson) is an absolute constant. We present a simple algorithm for computing a View the MathML source-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 View the MathML source-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. |