It is known that Nash equilibria and approximate Nash equilibria not necessarily optimize social optima of bimatrix games. In this paper, we show that for every fixed e > 0, every bimatrix game (with values in [0; 1]) has an e-approximate Nash equilibrium with the total payoff of the players at least a constant factor, (1 - √1 - e)2, of the optimum. Furthermore, our result can be made algorithmic in the following sense: for every fixed 0 ≤ e* < e, if we can find an e*-approximate Nash equilibrium in polynomial time, then we can find in polynomial time an e-approximate Nash equilibrium with the total payoff of the players at least a constant factor of the optimum.#R##N##R##N#Our analysis is especially tight in the case when e ≥ 1/2. In this case, we show that for any bimatrix game there is an e-approximate Nash equilibrium with constant size support whose social welfare is at least 2√e - e ≥ 0:914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight, that is, for every e ≥ 1/2 there is a bimatrix game for which every e-approximate Nash equilibrium has social welfare at most 2√e - e times the optimal social welfare.
['Artur Czumaj', 'Michail Fasoulakis', 'Marcin Jurdzinski']
Approximate Nash Equilibria with near optimal social welfare