Efficient algorithms for constant well supported approximate equilibria in bimatrix games

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 phi-SuppNE for win lose games, where phi = 2/root 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 epsilon-SuppNE of normalized or win lose bimatrix games, for some nontrivial constant epsilon is an element of [0, 1), bounded away from 1.