Finding approximate Nash equilibria in n x n bimatrix games is currently one
of the main open problems in algorithmic game theory. Motivated in part by the
lack of progress on worst case instances, Awasthi et. al [2] recently proposed
the question of finding approximate Nash equilibria in games that satisfy a
natural (epsilon, Delta) stability to approximation condition. This condition
states that all epsilon approximate equilibria are contained inside a small
ball of radius Delta around a true equilibrium. Awasthi et. al [2] gave a
polynomial time algorithm for the case Delta \leq (2 - o(1))epsilon and a
central question remaining is whether such a result can be extended to the case
Delta = poly(epsilon), i.e. Delta = O(epsilon^{1/c}), for constant c. In this
paper, we show that, surprisingly, up to polynomial factors such games are not
easier than the general case. Specifically, our first main result states that
computing an epsilon-equilibrium in a game satisfying the (epsilon,
Theta(epsilon^{1/4})) approximation stability condition is as hard as computing
an Theta(epsilon^{1/4})-equilibrium in a general game. We also show that the
main upper bound of Awasthi et. al [2] applies to a strict generalization of
the approximate stability condition which only requires that the well supported
approximate equilibria are contained inside a small ball around a true
equilibrium. Interestingly, this turns out to be equivalent to a stability to
perturbations condition, stating that any Nash equilibrium in a slightly
perturbed game is close to a fixed Nash equilibrium in the original game. This
is exactly the notion of stability analyzed by Bilu and Linial in the context
of maxcut clustering problems [9], and clearly a desirable condition, since in
many cases of interest the game analyzed is only an approximation of the real
game being played.