Well supported approximate equilibria in bimatrix games: A graph theoretic approach

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 ε ∈ (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 Nash Dynamics 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 Nash Dynamics 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.