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 ö = √5−1
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.