2007 | OriginalPaper | Chapter
Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
Authors : Spyros C. Kontogiannis, Paul G. Spirakis
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this work we study the tractability of well supported approximate Nash Equilibria (SuppNE in short) in bimatrix games. In view of the apparent intractability of constructing Nash Equilibria (NE in short) in polynomial time, even for bimatrix games, understanding the limitations of the approximability of the problem is of great importance.
We initially prove that SuppNE are immune to the addition of arbitrary real vectors to the rows (columns) of the row (column) player’s payoff matrix. Consequently we propose a polynomial time algorithm (based on linear programming) that constructs a 0.5 −SuppNE for arbitrary win lose games.
We then parameterize our technique for win lose games, in order to apply it to arbitrary (normalized) bimatrix games. Indeed, this new technique leads to a
weaker
φ
−SuppNE for win lose games, where
$\phi=\frac{\sqrt{5}-1}{2}$
is the
golden ratio
. Nevertheless, this parameterized technique extends nicely to a technique for arbitrary [0,1] −bimatrix games, which assures a 0.658 −SuppNE in polynomial time.
To our knowledge, these are the
first
polynomial time algorithms providing
ε
−SuppNE of normalized or win lose bimatrix games, for some nontrivial
constant
ε
∈ [0,1), bounded away from 1.