Abstract
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 ? > 0, every bimatrix game (with values in [0, 1]) has an ?-approximate Nash equilibrium with the total payoff ? of the players at least a constant factor, (1 ? 1 ? ?)2 , of the optimum. Furthermore, our result can be made algorithmic in the following sense: for every fixed 0 ? ?? < ?, if we can find an ?? -approximate Nash equilibrium in polynomial time, then we can find in polynomial time an ?-approximate Nash equilibrium with the total payoff of the players at least a constant factor of the optimum. Our analysis is especially tight in the case when ? ? 12 . In this case, we show that for any bimatrix game there is an ?-approximate Nash equilibrium with constant ? size support whose social welfare is at least 2 ? ? ? ? 0.914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight, that is, for every ? ? 21 there is a bimatrix game for which every ?-approximate ? Nash equilibrium has social welfare at most 2 ? ? ? times the optimal social welfare.