Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games
verfasst von : Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis
Erschienen in: Internet and Network Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.