I am sort of confused by the notion of approximate Nash equilibrium. I will try to express my confusion in the following exercise.

Problem. Is it true that for every two player game where every player has $n$ available actions and all payoffs $\in [0,1]$, there exists approximate $\epsilon$- Nash equilibrium where all players probabilities are integer multiples of $Ω(\epsilon/n)$, for all $\epsilon$.

$\sigma$ is $\epsilon$-Nash equlilbrim if $\forall$ player $i$ and $\forall j$ action of $i, u_i(\sigma_{-i},\sigma_{j}) - u_i(\sigma) \leq \epsilon$. In another words by deviating to any other action every player can't gain more than $\epsilon$.

The problems is to prove that for every 2 player game with $n$ action, exists $\epsilon$-nash equilibrium where all probabilities bounded below by $\frac{\epsilon \cdot k}{n}$, for some positive $k>0$, so there is no probability that equals to $0$.

First of all every game has at least one mixed Nash equilibrium, therefore the problem reduced to show that there exists some strategy for players with probability of actions is bounded below by $\frac{\epsilon \cdot k}{n}$ and difference between payoff of Nash equilibrium and the payoff of strategy is at most $\epsilon$.

Let's assume the worst case when the given game has pure Nash equilibrium, such that the single action has probability $1$ and $n-1$ others are $0$, therefore in $\epsilon$-Nash equilibrium it's required to increase every probability by $\frac{\epsilon}{n}$ and there are $n-1$ such actions and the maximum payoff of the action is 1. Therefore we change the payoff at most by $\frac{\epsilon}{n} \cdot (n-1) \cdot 1 < \epsilon$.

It looks like a right reasoning regarding the problem, but still it feels like not enough rigorous proof, in addition the same is applied to the second player and then we have the difference $>\epsilon$.

If you have any idea how to proceed with the proof please share it with us.


I think you proved it nicely. As you say, Nash equilibrium in mixed strategies always exists. Without loss of generality you can check only games where the Nash equlibria are joint strategies where some players play pure strategy, that is give weight $1$ to one strategy and give weight $0$ to all other strategies.

Now, a joint strategy is $\epsilon$-Nash equilibrium if for every player holds that when he deviates to another strategy his payoff increases at most $\epsilon$.

We are claiming that joint strategy $s$ where:

  1. You put weight $\frac{\epsilon}{n}$ to strategies where a player that played pure strategy had weight $0$.

  2. You put weight $\frac{\epsilon}{n}$ to all strategies in mixed strategy of a player who had weight less than $\frac{\epsilon}{n}$ in Nash equilibrium.

is indeed $\epsilon$-Nash equilibrium.

  1. From deviating he gained at most $\frac{\epsilon}{n} \cdot (n-1) < \epsilon$. But that holds for every player that played worst case scenario strategy, i.e. pure strategy.

  2. From deviating he can gain even less than players from 1.

Therefore no player can gain more than $\epsilon$ and you have it.


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.