9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is always a limit point $(s_1^* ... s_n^*)$ to which a sub-sequence of the epsilon-equilibria converge, and this limit would be an exact Nash equilibrium. This is implied by the compactness of the space of mixed strategy profiles and the continuity of the utility functions as a function of the mixed strategy probabilities. $\endgroup$ – Noam Mar 19 '14 at 19:11
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I guess this is the state of the art. I will add some thoughts in my question as well. $\endgroup$ – usul Mar 19 '14 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.