Abstract: We study the existence and tractability of a notion of approximate
equilibria in bimatrix games, called well supported approximate
Nash Equilibria (SuppNE in short).We prove existence of "−SuppNE for
any constant " 2 (0, 1), with only logarithmic support sizes for both players.
Also we propose a polynomial–time construction of SuppNE, both
for win lose and for arbitrary (normalized) bimatrix games. The quality
of these SuppNE depends on the girth of the NashDynamics graph in
the win lose game, or a (rounded–off) win lose image of the original normalized
game. Our constructions are very successful in sparse win lose
games (ie, having a constant number of (0, 1)−elements in the bimatrix)
with large girth in the NashDynamics graph. The same holds also for
normalized games whose win lose image is sparse with large girth.
Finally we prove the simplicity of constructing SuppNE both in random
normalized games and in random win lose games. In the former case we
prove that the uniform full mix is an o(1)−SuppNE, while in the case
of win lose games, we show that (with high probability) there is either a
PNE or a 0.5-SuppNE with support sizes only 2.
