Game Theory 101: Best Responses & Nash Equilibrium

November 30, 2023

In the previous post of this series, we discussed about strategy dominance as a way to analyse games to aid us in playing the right strategy. To recap, it is never rationalizable to play strategies that are strictly dominated by others. We now explore another concept, the best response and how it plays a role in a game's Nash Equilibrium.

Best Responses

Suppose that the strategies that our opponents play are fixed as $s_{-i}$ . Intuitively, we know that given a fixed strategy profile of our opponents, there must exist at least 1 strategy in our set of strategy that performs the best against $s_{-i}$ . This is our best response to $s_{-i}$ .

More formally, player i's strategy $s_{i}^*$ is a best response to a particular $s_{-i}$ if:

u_i(s_{i}^*, s_{-i}) \geq u_i(s_{i}{'}, s_{-i}) \text{ for all } s_{i}{'} \in S_i

Where $s_i{'} \neq s_{i}^*$ , and $S_i$ is the set of all strategies that are available to player i.

For example, in the game Rock Paper Scissors, if $s_{-i} = \text{Paper}$ , then our best response would be $s_{i}^* = Scissors$ .

Why are best responses useful?

Best responses can guide us into making the optimal choice based on certain beliefs about what others will play. Of course, our beliefs may or may not be correct in the end, so why can't we make a decision using strict dominance and iterative elimination? The answer is simple: There simply may not be any strict dominance relation between our strategies. Consider the following game:

Player 1

Player 2

	M	S
M	3,1	0,0
S	0,0	1,3

What is the dominance relationship between M and S here? The utility of Player 1 for playing M or S would be as follows:

u_1(M, M) = 3\\ u_1(M, S) = 0\\ u_1(S, M) = 0\\ u_1(S, S) = 1\\

Notice that $u_1(M, M) > u_1(S, M)$ , but $u_1(M, S) < u_1(S, S)$ . Therefore M does not strictly (or weakly) dominate S and vice versa. How do we make our decision now?

If we hold the belief that Player 2 is going to play $S$ , then our best response would be $S$ . If we hold the belief that Player 2 is going to play $M$ , our best reponse to that would be $M$ . The same holds true for Player 2 in response to what Player 1 plays. We note that the ideal outcome would be either $(M, M)$ or $(S, S)$ . They are the Nash Equilibrium of this game.

Nash Equilibrium

Informally, a Nash Equilibrium is a state of the game where every player's chosen strategy is a best response to every other player. In our game of two players, this would mean that both players are playing strategies such that their strategies are best responses to each other. Nash Equilibrium (NE) exhibits the following properties:

NE always exists (in a finite game)
No regrets: Each player's choice is what they would have chosen if they knew about what the others would play beforehand. If others' strategies were fixed, no player has any incentive to deviate.
Self-enforcing: Once a Nash Equilibrium is reached, no player can unilaterally deviate their strategy from the NE state and hope to profit (it is not possbile). If the game state is not in NE, it is possible.

We define the Nash Equilibrium of a game with $n$ players as a state/strategy profile of the game, as follows:

s^* = \{s_1^*, s_2^*, \dots , s_n^*\}\\ s^* \text{is a NE if for every player i,}\ s_i^*\ \text{is a best response to}\ s_{-i}^*\\

Equivalently,

s^* \text{is a NE if for every player i,}\ u_i(s_i^*, s_{-i}^*) \geq u_i(s_i{'}, s_{-i}^*)\ \text{for every}\ s_i{'}

Note that strictly dominated strategies can never be part of a NE, simply due to the fact a SD'ed strategy cannot be a best response. A weakly dominated strategy, however, can be a best response and thus be part of a NE.

A Nash Equilibrium can be considered as a "desirable" state of the game for all players, as it ensures that they are playing the best response possible to the current game state, and hence maximizing their utility.

Mixed Strategies & Mixed Strategy Nash Equilibrium

However, even a "Pure" Strategy Nash Equilibrium may not exist, which is to say an equilibrium where we are playing discrete strategies. For example, let us consider the game of Rock Scissors Papers:

Player 1

Player 2

	R	P	S
R	0,0	-1,1	1,-1
P	1,-1	0,0	-1,1
S	-1,1	1,-1	0,0

Where is the Nash Equilibrium? We need both players to be playing the best reponse to each other's strategies. $R$ is a best response to $S$ , but $P$ is a best response to $R$ , and $S$ is a best response to $P$ . There is no scenario where each player plays the best response to each other's strategy, at least in terms of pure (discrete) strategies.

Note that a tie is not a NE, since if the game state is $(R,R)$ , the best response of each player would have been to play $P$ in response to $R$ . This brings us to the concept of mixed strategies.

Mixed Strategies

A mixed strategy can be defined as a probability distribution over a set of pure strategies. That is, every strategy in our set of pure strategy has a certain probability of being played when we use a mixed strategy, and the sum of all probabilities for the strategies should be 1. We can denote a mixed strategy for player i who has n strategies as:

\mu_i = (p_{s_1}, p_{s_2}, \dots p_{s_n})\\ \text{Where $p_{s_i}$ represents the probability of playing $s_i$, and } \sum_{i=1}^n p_{s_i} = 1

We also denote the probability of playing a single strategy $s_i$ under a given mixed strategy $\mu_i$ as follows:

\mu_i(s_i) = p_{s_i}

Note that pure (discrete) strategies are just a special case of mixed strategies, where $\mu_i(s_i) = 1$ for a single $s_i$ and $\mu_i(s_i{'}) = 0$ for all $s_i{'} \neq s_i$ .

Mixed Strategy Nash Equilibrium

We define the mixed strategy Nash Equilibrium as follows:

\text{A mixed strategy profile}\ \mu_i^* = (\mu_1^*, \mu_2^*, \dots , \mu_n^*)\\ \text{is a Mixed Strategy Nash Equilibrium if for each player i,}\\ \mu_i^*\ \text{is a best response to $\mu_{-i}^*$}

Note that for every $s_i$ such that $\mu_i(s_i) > 0$ , $s_i$ is also a best reponse to $\mu_{-i}^*$ . This is due to the indifference condition which we will discuss in the next section.

Finding the Mixed Equilibrium

In order to find the mixed equilibrium, we want to play a mixed strategy with a probability distribution such that one or both players in the game are indifferent.

That is, we play a particular probability distribution such that no mattter what strategy the opponent chooses, the opponent's expected payoff of playing the pure strategies are equal.

In our game of Rock Paper Scissors, we want to play a mixed strategy such that playing Rock, Paper or Scissors all have equal payoff for the opponent in order to find the mixed equilibrium.

We can calculate the probability distribution for our mixed strategy with simple algebraic manipulation:

\begin{gather*} \begin{align*} &\mu_1^* = (p_{Rock}, p_{Paper}, p_{Scissors})\nonumber \\ &p_{Rock} + p_{Paper} + p_{Scissors} = 1\nonumber \\ &p_{Scissors} = 1 - p_{Rock} - p_{Paper} \tag{1}\\~\nonumber \\ E(u_2(Rock, \mu_1^*)) &= (0)\times p_{Rock} + (-1)\times p_{Paper} + (1)\times p_{Scissors}\nonumber \\ &= p_{Scissors} - p_{Paper}\nonumber \\ E(u_2(Paper, \mu_1^*)) &= (1)\times p_{Rock} + (0)\times p_{Paper} + (-1)\times p_{Scissors}\nonumber \\ &= p_{Rock} - p_{Scissors}\nonumber \\ E(u_2(Scissors, \mu_1^*)) &= (-1)\times p_{Rock} + (1)\times p_{Paper} + (0)\times p_{Scissors}\nonumber \\ &= p_{Paper} - p_{Rock}\nonumber \\ \end{align*}\nonumber \\ \text{Note that the above 3 values are \textbf{expected payoffs} of player 2}\nonumber \\ \text{when playing Rock/Paper/Scissors as a pure strategy against $\mu_1^*$.}\nonumber \\~\nonumber \\ \text{In order to make player 2 indifferent, the statement}\nonumber \\ E(u_2(Rock, \mu_1^*)) = E(u_2(Paper, \mu_1^*)) = E(u_2(Scissors, \mu_1^*))\nonumber \\ \text{must be true.}\nonumber \\~\nonumber \\ \text{Consider }E(u_2(Rock, \mu_1^*)) = E(u_2(Paper, \mu_1^*)):\nonumber \\ \begin{align*} p_{Scissors} - p_{Paper} &= p_{Rock} - p_{Scissors}\nonumber \\ 2p_{Scissors} &= p_{Rock} + p_{Paper}\nonumber \\ \end{align*}\\ \text{From (1),}\nonumber \\ \begin{align*} 2(1 - p_{Rock} - p_{Paper}) &= p_{Rock} + p_{Paper}\nonumber \\ 2 &= 3p_{Rock} + 3p_{Paper}\nonumber \\ p_{Rock} + p_{Paper} &= \frac{2}{3} \tag{2}\\~\nonumber \\ \end{align*}\nonumber \\ \text{(1) + (2):}\nonumber \\ \begin{align*} p_{Scissors} &= 1 - (p_{Rock} + p_{Scissors}) \nonumber \\ p_{Scissors} &= 1 - \frac{2}{3} = \frac{1}{3} \tag{3}\\~\nonumber\\ \end{align*}\\ \text{Consider }E(u_2(Paper, \mu_1^*)) = E(u_2(Scissors, \mu_1^*)):\nonumber \\ p_{Rock} - p_{Scissors} = p_{Paper} - p_{Rock}\nonumber \\ \text{From (1),}\nonumber \\ \begin{align*} p_{Rock} - (1 - p_{Rock} - p_{Paper}) &= p_{Paper} - p_{Rock}\nonumber \\ 2p_{Rock} -1 + p_{Paper} &= p_{Paper} - p_{Rock}\nonumber \\ 3p_{Rock} &= 1 \nonumber \\ p_{Rock} &= \frac{1}{3} \tag{4} \\~\nonumber\\ \end{align*}\\ \text{(1) + (3) + (4):}\nonumber \\ p_{Paper} = 1 - \frac{1}{3} - \frac{1}{3} = \frac{1}{3} \nonumber \\ \therefore \mu_1^* = (\frac{1}{3},\frac{1}{3},\frac{1}{3}) \nonumber \end{gather*}

We have now found the mixed strategy for player 1 that will make player 2 indifferent! Unsurprisingly, player 2 is indifferent when player 1 plays all 3 strategies with equal probability $\frac{1}{3}$ . In a game of Rock Paper Scissors where all payoffs for winning/losing with any strategy is equivalent, this makes sense.

One important intuition to take away here is that if a player is indifferent between his pure strategies, i.e. the payoffs are the same, then any mix of those strategies will also have the same payoff. This also means that every possible mix of those pure strategies are also best responses!

Recall that in a Nash Equilibrium, both players must play best responses to each other's strategies. Therefore, player 2 can nowalso play $\mu_2^* = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ such that any strategy played by player 1 is a best response, which includes $\mu_1^*$ .

Therefore, our Mixed Strategy Nash Equilibrium for the game of Rock Scissors Paper is $\mu^* = (\mu_1^*, \mu_2^*)$ , where $\mu_1^* = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ and $\mu_2^* = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ .

Conclusion

In this post we have learnt about another way to analyse games using best responses and Nash Equilibrium. In particular, we discussed the properties of a Nash Equilibrium and delved into both Pure Strategy Nash Equilibria and Mixed Strategy Nash Equilibia.

Mixed Strategies open up a new method of playing the game by using a probability distribution over our pure strategies, and also reveal the existence of the Mixed Strategy Nash Equilibrium, which is very useful for games where the pure Nash Equilibrium does not exist.