There are two equivalent ways to understand the best response property of a Nash Equilibrium strategy. First, we can say that the player plays a mixed strategy whose expected payoff is maximal among all possible mixed strategies. Second, we can say that the player randomly chooses a pure strategy from the set of pure strategies whose expected payoff is maximal among all possible pure strategies.

So far so good, and every student of game theory is aware of this equivalence. What I think is less known is that the two perspectives are not identical for {\epsilon}-best response and {\epsilon}-equilibrium: A mixed strategy whose expected payoff is almost optimal might put some positive (though small) probability on a pure strategy which gives a horrible payoff. In this post I am going to explain why I used to think the difference between the two perspectives is inconsequential, and why, following a conversation with Ayala Mashiah-Yaakovi about her work on subgame perfect equilibrium in Borel games, I changed my mind.

A (two player) normal form game is given by Borel sets {A,B} of pure strategies of Alice and Bob and Borel functions {f^A,f^B:A\times B\rightarrow [0,1]}, the payoff functions of Alice and Bob. Elements of {\Delta(A)} and {\Delta(B)} are called mixed strategies. As usual, we extend the domain of the payoff functions to mixed strategies and identify the pure strategy {a\in A} with the mixed strategy that plays {a} with probability {1}.

Let {\beta\in\Delta(B)} be a mixed strategy of Bob and let {\epsilon>0}. A mixed strategy {\alpha\in\Delta(A)} of Alice is {\epsilon}-best response to {\beta} if {f^A(\alpha,\beta)+\epsilon\geq f^A(\alpha',\beta)} for every {\alpha'\in \Delta(A)}. A mixed strategy {\alpha\in\Delta(A)} of Alice is strong {\epsilon}-best response to {\beta} if

\displaystyle \alpha\bigl(\left\{a\in A|a\text { is }\epsilon\text{-best response to }\beta\right\}\bigr)=1.

The first definition is standard, and the second is a definition that I invented for this post. We can now distinguish between {\epsilon}-equilibrium (a mixed strategy profile under which every player {\epsilon}-best respond to the opponent) and strong {\epsilon}-equilibrium (a mixed strategy profile under which every player strongly {\epsilon}-best respond to the opponent). Every strong {\epsilon}-equilibrium is in particular an {\epsilon}-equilibrium, but the converse is not true.

Personally, I strongly prefer strong {\epsilon}-equilibrium. As I explained in another blog, I don’t care much for the idea that players toss coins to decide which action to play. The way I prefer to interpret mixed strategies in Nash Equilibrium follows Harsany’s purification idea: the game is replaced with a game of incomplete information in which each type of Alice plays a pure best response. The mixture is not a product of an a randomization performed by Alice, but of the fact that Nature randomly chooses some type of Alice. Now if we assume that each type {\epsilon}-best responds, we arrive at the concept of strong {\epsilon}-equilibrium.

How could I live in harmony with all the game theorists who use the standard definition of {\epsilon}-equilibrium in their papers ? Well, I console myself with the following proposition

Proposition 1 The following conditions are equivalent for every normal form game

  1. The game admits an {\epsilon}-equilibrium for every {\epsilon>0}.
  2. The game admits a strong {\epsilon}-equilibrium for every {\epsilon>0}.

I never actually wrote down a proof for this proposition, so let’s agree that the proposition is easy to verify. So up to now, when I read and wrote papers that prove existence of {\epsilon}-equilibrium I always interpreted them as papers that prove existence of strong {\epsilon}-equilibrium. But as I said, I now think that things get more subtle when we look at extensive form games.

The following gem was discovered by Eilon Solan and Nicolas Vieille (pdf, Example 3): A perfect information game between two players is played in periods. At even periods {n=0,2,\dots} Alice can quit the game or continue. At odd periods {1,3,5,\dots} Bob can quit or continue. If at some period Alice quits the game terminates with payoffs {(-1,2)} (that is, {-1} to Alice and {2} to Bob). If at some period Bob quits the game terminates with payoffs {(-2,1)}. If nobody ever quits the final payoff is {(0,0)}.

A pure strategy of a player tells them at every period whether to quit or continue. The game has a Nash equilibrium according to which both players quit at every period. This Nash equilibrium is, however, not subgame perfect: If the unthinkable happens and Alice does not quit at period {0} then Bob’s strategy tells him to quit at period {1}, but in fact it is better for him to continue and let Alice quit at period {2}. On the other hand, Bob must threaten to quit, or Alice will just continue forever.

What are we left with ? This game has no pure strategy subgame perfect equilibrium, nor even pure strategy subgame perfect {\epsilon}-equilibrium (again, easy to verify). However Eilon and Nicolas prove that the game has subgame perfect {\epsilon}-equilibrium in mixed strategies! Alice quits at every period and Bob quits with probability {\epsilon} at every period.

If you are still reading and managed to convince yourself that this is indeed a subgame perfect {\epsilon}-equilbrium then you might feel a bit uncomfortable with the concept of subgame perfect {\epsilon}-equilibrium. If not, put yourself in Bob’s shoes in the game that starts at period 1: Eilon and Nicolas have just stopped by, recommending that both you and Alice follow their {\epsilon}-equilibrium strategy profile. So you are supposed to toss a coin with probability {\epsilon} for Heads and quit if the outcome is Heads. As Nash Equilibrium goes, you ask yourself whether it makes sense to follow the recommendation given that Alice follows it. Ex ante, before you tosses the coin, the recommendation seems reasonable. You don’t mind promising to quit if your coin turns on Heads given that this is unlikely to happen anyway. But, in the interim stage, after the coin turns out to be Heads, you are asked to quit even though Alice will quit at the next round, so by quitting you will lose much more than {\epsilon}. I would shirk, but then again, I voted for strong {\epsilon}-equilibrium.

So what I would like to have is a subgame perfect stronge {\epsilon}-equilibrium. I am not sure what’s the best way to define this concept, but I am pretty sure Solan-Vieille’s game doesn’t admit such a thing. In particular, I believe my beloved proposition has no good analogue for subgame perfect equilibrium.