2011 | OriginalPaper | Buchkapitel
Approximability of Symmetric Bimatrix Games and Related Experiments
verfasst von : Spyros Kontogiannis, Paul Spirakis
Erschienen in: Experimental Algorithms
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
In this work we present a simple quadratic formulation for the problem of computing Nash equilibria in
symmetric
bimatrix games, inspired by the well-known formulation of Mangasarian and Stone [26]. We exploit our formulation to shed light to the approximability of NE points. First we observe that any KKT point of this formulation (and indeed, any quadratic program) is also a stationary point, and vice versa. We then prove that
any
KKT point of the proposed formulation (is not necessarily itself, but) indicates a
$\left(<\frac{1}{3}\right)-$
NE point, which is polynomially tractable, given as input the KKT point. We continue by proposing an algorithm for constructing an
$\left(\frac{1}{3}+\delta\right)-$
NE point for any
δ
> 0, in time polynomial in the size of the game and quasi-linear in
$\frac{1}{\delta}$
, exploiting Ye’s algorithm for approximating KKT points of QPs [34]. This is (to our knowledge) the first polynomial time algorithm that constructs
ε
−NE points for symmetric bimatrix games for any
ε
close to
$\frac{1}{3}$
. We extend our main result to (asymmetric) win lose games, as well as to games with maximum aggregate payoff either at most 1, or at least
$\frac{5}{3}$
. To achieve this, we use a generalization of the Brown & von Neumann symmetrization technique [6] to the case of non-zero-sum games, which we prove that is approximation preserving. Finally, we present our experimental analysis of the proposed approximation and other quite interesting approximations for NE points in symmetric bimatrix games.