Finding Pure Strategy Nash Equilibria

Introduction

Welcome back! In our previous lesson, we established a crucial tool: the best response correspondence. We learned how to compute a player's optimal strategy for any given choice—pure or mixed—made by their opponents. We saw that for 2-player games, this can be visualized as a graph on a unit square.

Today, we'll use this concept to find the most fundamental solution concept in game theory: the Nash Equilibrium. A Nash Equilibrium represents a stable outcome of a game where no player has an incentive to unilaterally change their strategy. Our learning outcome is to determine pure strategy Nash equilibria by intersecting best response correspondences.

For the pure strategy case we are focusing on today, this "intersection" takes a very simple and practical form. By the end of this lesson, you will be able to systematically identify all pure strategy Nash equilibria in any finite normal-form game.

What is a Nash Equilibrium?

Intuitively, a Nash equilibrium is a strategy profile with a "no regrets" property. After the game is played, if the outcome is a Nash Equilibrium, no player will look back and say, "Given what my opponents did, I wish I had chosen a different strategy."

Let's watch a short segment from a Yale University course where Professor Ben Polak provides both a formal definition and this powerful intuition.

As the video explained, a strategy profile $s^{\ast }=(s_1^{\ast },s_2^{\ast },\dots ,s_N^{\ast })$ is a Nash Equilibrium (NE) if, for every player $i$, their chosen strategy $s_i^{\ast }$ is a best response to the strategies of all other players, $s_{-i}^{\ast }$.

Formally, for every player $i$:

This definition directly connects to our previous lesson. A Nash Equilibrium is simply a point where everyone is playing a best response to everyone else simultaneously. If we were to draw the best response correspondence graphs for all players, a Nash Equilibrium is a point where all those graphs intersect.

Finding Pure Strategy Nash Equilibria (PSNE)

For pure strategies, we don't need to draw complex graphs. We can find the equilibria directly within the payoff matrix using a simple, mechanical procedure. Since you already know how to find a player's best response to an opponent's pure strategy, this process will be straightforward.

The "Underlining" Method:

1. For each column (i.e., for each of Player 2's pure strategies), find the highest payoff for Player 1 and underline it. If there's a tie, underline all of them.
2. For each row (i.e., for each of Player 1's pure strategies), find the highest payoff for Player 2 and underline it. Again, underline all ties.
3. Any cell in the matrix where all payoffs are underlined is a Pure Strategy Nash Equilibrium (PSNE).

This works because a cell with all payoffs underlined is, by definition, a strategy profile where Player 1's choice is a best response to Player 2's choice, and Player 2's choice is a best response to Player 1's choice. It's a mutual best response.

Example 1: Finding a Unique PSNE

Let's see this method in action. The following video segment demonstrates this exact process on a 3x3 game. The professor uses circles and squares instead of underlining, but the logic is identical.

The unique PSNE in this game is (Down, Right). At this outcome, Player 1's payoff of 6 is the best they can do given Player 2 is playing Right. Player 2's payoff of 6 is the best they can do given Player 1 is playing Down. Neither has an incentive to deviate.

Example 2: Another Walkthrough

Let's watch one more quick example to solidify the method. This video applies the same logic to a 2x2 game.

As you saw, this game has two PSNE: (Up, Left) and (Down, Right). It's common for games to have multiple equilibria.

Example 3: Multiple Equilibria in the Stag Hunt Game

Let's try one yourself. The Stag Hunt game is a classic example of a coordination game. Two hunters can choose to hunt a stag or a hare. Hunting a stag requires cooperation for a big reward, but if one hunter tries for the stag alone, they fail. Hunting a hare can be done alone for a smaller reward.

Apply the underlining method to this game matrix to find all the Pure Strategy Nash Equilibria.

Click for the solution

1. Player 1's Best Responses:

   • If Hunter 2 chooses Stag, Hunter 1's best response is Stag (payoff 4 > 2). Underline the 4 in the (Stag, Stag) cell.
   • If Hunter 2 chooses Hare, Hunter 1's best response is Hare (payoff 1 > 0). Underline the 1 in the (Hare, Hare) cell.

2. Player 2's Best Responses:

   • If Hunter 1 chooses Stag, Hunter 2's best response is Stag (payoff 4 > 2). Underline the second 4 in the (Stag, Stag) cell.
   • If Hunter 1 chooses Hare, Hunter 2's best response is Hare (payoff 1 > 0). Underline the second 1 in the (Hare, Hare) cell.

3. Find Mutual Best Responses:

   • The cell (Stag, Stag) has both payoffs underlined.
   • The cell (Hare, Hare) has both payoffs underlined.

Therefore, there are two Pure Strategy Nash Equilibria: (Stag, Stag) and (Hare, Hare). This makes intuitive sense: either they coordinate on the high-reward strategy or they coordinate on the low-reward (but safe) strategy.

Here is an image that provides a complete summary of the process, from definition to final identification.

Connection to Dominated Strategies

In our first lesson, we learned about eliminating strictly dominated strategies. How does that concept relate to Nash Equilibrium?

The connection is simple and powerful: A strictly dominated strategy can never be played in a Nash Equilibrium.

Why? By definition, a strictly dominated strategy is never a best response to anything your opponents might do. Since a Nash Equilibrium requires every player's strategy to be a best response, a strictly dominated strategy can't be part of one. Iteratively eliminating strictly dominated strategies is therefore a safe way to simplify a game without losing any potential Nash equilibria.

The following video segment explains this relationship clearly.

5. Nash equilibrium: bad fashion and bank runs

This clip discusses the relationship between Nash Equilibrium and the concept of dominance we covered earlier.

Watch from 23:15 to 27:27. The professor uses the Prisoner's Dilemma to show how the Nash Equilibrium is the same outcome arrived at by eliminating dominated strategies and then formally proves why a strictly dominated strategy can't be part of a Nash Equilibrium.

It's important to note, as the video alludes to, that this guarantee does not hold for weakly dominated strategies. A strategy that is only weakly dominated can sometimes be part of a Nash equilibrium.

Conclusion

In this lesson, we formalized the concept of a Nash Equilibrium as a stable outcome where all players are simultaneously playing a best response.

Key Takeaways:

• A Nash Equilibrium is a strategy profile where no player has a unilateral incentive to deviate. It represents a state of "no regrets."
• We can find Pure Strategy Nash Equilibria (PSNE) by identifying cells in the payoff matrix that are a mutual best response.
• A simple and effective method is to go through the matrix and underline the best payoff for each player in response to each of their opponent's pure strategies. Any cell where all payoffs are underlined is a PSNE.
• Games can have one, multiple, or zero pure strategy Nash equilibria.
• A strategy that is strictly dominated can never be part of any Nash Equilibrium.

Preview of the Next Lesson:
We've seen that some games, like Rock-Paper-Scissors or Matching Pennies, have no pure strategy Nash equilibria. If Player 1 knows Player 2 will play Rock, Player 1's best response is Paper. But if Player 2 anticipates that, their best response is Scissors, and so on. There is no stable pure strategy pair. This raises a question: Do such games have any equilibrium at all?

The answer is yes, but to find it, we need to allow players to randomize their choices. In our next lesson, we will define a mixed strategy as a probability distribution over pure strategies, setting the stage to compute mixed strategy Nash equilibria.