When do $\epsilon$-Nash equilibrium strategies converge to Nash Equilibrium strategies?

Question

Nash Equilibria are uncomputable in general. An $\epsilon$-Nash equilibrium is a set of strategies where, given the opponents' strategies, each player obtains within $\epsilon$ of the maximum possible expected payoff. Finding an $\epsilon$-Nash equilibrium, given $\epsilon$ and a game, is $\mathsf{PPAD}$-complete.

Going strictly by the definitions, there seems to be no particular reason to believe that the strategies of a given $\epsilon$-Nash equilibrium are anywhere close to the strategies of any Nash equilibrium. However, we often see the literature somewhat sloppily use a phrase like "approximately compute a Nash equilibrium" when it means to say "compute an approximate-Nash equilibrium".

So, I'm wondering when the second implies the first; that is, for what games might we expect $\epsilon$-Nash equilibria to be "close" to Nash equilibria?

---

More formally, suppose I have a game on $n$ players and a sequence of strategy profiles $(s_1^{(1)},\dots,s_n^{(1)}), (s_1^{(2)},\dots,s_n^{(2)}), (s_1^{(3)},\dots,s_n^{(3)}), \dots$.

Each $(s_1^{(i)},\dots,s_n^{(i)})$ is a $\epsilon_i$-Nash equilibrium, and the sequence $\epsilon_1,\epsilon_2,\epsilon_3,\dots$ converges to zero.

My questions:

1. When (under what conditions/assumptions) do all the strategies converge? That is, for each player $j$, $s_j^{(1)},s_j^{(2)},s_j^{(3)},\dots$ necessarily converges.

2. Under what further conditions is the limit of this sequence actually a Nash equilibrium of the game? (It seems to me that no further assumptions should be needed; i.e., if all the strategies converge, the limit should be a NE.)

3. When does an algorithm for computing $\epsilon$-Nash equilibria necessarily imply an algorithm for approximately computing strategies of a Nash equilibrium? Are the above conditions sufficient?

Thanks very much!

---

Edit 2014-03-19

After reading the reference in Rahul's answer, it seems more reasonable to think in terms of $\ell_1$ distances between distributions rather than convergent sequences. So I'll try to rephrase the questions and also put some recent thoughts.

1. (Well, this is too algorithm-dependent to really have an answer. Without restrictions on the algorithm, you could have two distinct Nash equilibria and then, as you plug in smaller and smaller $\epsilon$ into the algorithm, the $\ell_1$ distance between successive outputs could still be large because the outputs oscillate between equilibria.)

2. Suppose $p$ is a strategy profile, i.e. product distribution over the players' strategies. For what games can we say that $p$ is an $\epsilon$-Nash equilibrium implies $\|p - q\|_1 \leq \delta$ for some Nash equilibrium $q$, where $\delta \to 0$ as $\epsilon \to 0$? (Note that the converse holds if payoffs are bounded by $1$.)

   This is actually tricky because we in the complexity setting what we call a "game" is actually a sequence of games parameterized by $n$, the number of pure strategies ("actions"). So $n \to \infty$ as $\epsilon \to 0$, and the relative rates matter. Here is a simple counterexample to show the answer is not "all games". Suppose we fix a sequence of decreasing $\epsilon_1,\epsilon_2,\dots$. Then for each $\epsilon_n$, construct the two-player game on $n$ actions where, if a player plays the first action, they get a payoff of $1$ regardless of what the other player plays; if a player plays the second action, they get a payoff of $1-\epsilon_n$ regardless of what the other player plays; and if a player plays any other action, they get a payoff of $0$ regardless of what the other player plays.

   Thus each game $n$ has an $\epsilon_n$-equilibrium (both play the second action) that is maximally far in $\ell_1$ distance from its only Nash equilibrium (both play the first action).

   So, two interesting sub-questions:

   1. For a fixed game and fixed $n$, whether for "small enough" $\epsilon$ the above condition holds (all $\epsilon$-equilibria are close to Nash equilibria).
   2. Perhaps the same question essentially, but whether the condition holds if differences in payoffs are bounded by a constant as $n \to \infty$.

3. Same question as (2), but relating to the actual equilibria computed by algorithms. I guess probably we will either get algorithmic/constructive answers or none at all, so the distinction doesn't matter much.

Answer 1

The following paper at least formalizes the notion of approximate equilibria being close to exact equilibria, and proves some related structural results.

Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, and Santosh Vempala (2010). On Nash equilibria of approximation-stable games. In Proceedings of the Third international conference on Algorithmic game theory (SAGT'10), 78-89.

In particular, the paper gives an example of a class of games for question 3.