Abstract | 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 -Nash equilibrium for any bimatrix game in
4
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+ë -Nash equilibrium,
4
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. |