2006 | OriginalPaper | Buchkapitel
Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games
Autoren: Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis
Verlag: Springer Berlin Heidelberg
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
$\frac{3}{4}$
-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
$\frac{2+\lambda}{4}$
-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.
