Nash Equilibrium: Definition and Pure-Strategy Identification

1. What is a Nash Equilibrium?

In the last lesson, we asked: "Given my opponent plays $s_{-i}$, what is my best response?" A Nash Equilibrium arises when we find a strategy profile where the answer for every player is "to play the strategy prescribed by that very profile." It's a point of mutual best response.

A strategy profile is a Nash Equilibrium if no player can improve their payoff by unilaterally changing their strategy. This leads to two powerful interpretations:

• No Regrets: After the game, if the outcome was a Nash Equilibrium, no player will look back and say, "Given what everyone else did, I wish I had chosen a different strategy."
• Self-Fulfilling Beliefs: If all players believe that a certain Nash Equilibrium will be played, then it becomes rational for every single player to play their part in that equilibrium, thus confirming the initial beliefs.

The following video provides a formal definition and discusses these core ideas.

To state it formally, let's crystallize the definition.

Definition: Nash Equilibrium (NE)
A strategy profile $s^{\ast }=(s_1^{\ast },\dots ,s_n^{\ast })$ is a Nash Equilibrium if for every player $i$, their strategy $s_i^{\ast }$ is a best response to the other players' strategies $s_{-i}^{\ast }$. That is, for every player $i$, the following condition must hold:
$u_i(s_i^{\ast },s_{-i}^{\ast })\ge u_i(s_i,s_{-i}^{\ast })\text{for all }{s}_i\in S_i$
In simple terms, at a Nash Equilibrium, no player can do strictly better by changing their strategy alone.

2. Finding Pure-Strategy Nash Equilibria

While the definition is clear, how do we find these equilibria in practice? For pure strategies in a matrix game, we can use a straightforward inspection method. A pure-strategy NE is a cell in the payoff matrix where each player's payoff is the maximum they could get in that row or column.

There's a systematic way to do this, which the video you just watched introduces next. We'll formalize it here:

The Best Response Inspection Method:

1. For Player 1 (the row player), go through each column one by one. In each column, find the highest payoff for Player 1 and mark it (e.g., by underlining it or circling it). This identifies Player 1's best response to each of Player 2's pure strategies. If there's a tie, mark all tied payoffs.
2. For Player 2 (the column player), go through each row one by one. In each row, find the highest payoff for Player 2 and mark it. This identifies Player 2's best response to each of Player 1's pure strategies.
3. Any cell in the matrix where both payoffs are marked is a pure-strategy Nash Equilibrium. At these points, each player is playing a best response to the other.

Now, let's see this method in action.

Here is an image summarizing the result of such a process. The strategy profile {D,C} with payoffs (3,5) is a Nash Equilibrium because given Player 1 plays D, Player 2's best response is C (5 > 3 > -2), and given Player 2 plays C, Player 1's best response is D (3 > 2 > 1).

3. Nash Equilibrium and Dominated Strategies

You've now learned two solution concepts: IESDS and Nash Equilibrium. How do they relate? Given your interest in the theoretical underpinnings, let's formalize this connection.

A crucial theorem states that a strictly dominated strategy can never be played in a Nash Equilibrium.

The proof is direct and follows from the definitions.

• Proof by contradiction:
  1. Assume a strategy profile $s^{\ast }=(s_i^{\ast },s_{-i}^{\ast })$ is a Nash Equilibrium.
  2. Further assume that player $i$'s strategy, $s_i^{\ast }$, is strictly dominated by another strategy, $s_i^{\prime }$.
  3. By the definition of a strictly dominated strategy, it must be that $u_i(s_i^{\prime },s_{-i}^{\ast })>u_i(s_i^{\ast },s_{-i}^{\ast })$. This inequality must hold for any strategy profile of the opponents, so it must hold for $s_{-i}^{\ast }$.
  4. However, the definition of Nash Equilibrium requires that $s_i^{\ast }$ is a best response to $s_{-i}^{\ast }$, meaning $u_i(s_i^{\ast },s_{-i}^{\ast })\ge u_i(s_i,s_{-i}^{\ast })$ for all other strategies $s_i$, including $s_i^{\prime }$.
  5. This leads to a contradiction: statement (3) says Player $i$ could do strictly better by playing $s_i^{\prime }$, while statement (4) says they cannot.
  6. Therefore, our initial assumption that a strictly dominated strategy could be part of a Nash Equilibrium must be false.

This proves that any strategy that survives IESDS is a candidate for a Nash Equilibrium, and any strategy that is part of a Nash Equilibrium must also survive IESDS.

The following reading from MIT OpenCourseWare formalizes these relationships and proves two important theorems.

This establishes a clear hierarchy: dominant strategy equilibria are a subset of Nash equilibria, which are themselves a subset of the outcomes that survive iterated elimination.

Conclusion

Today we've introduced the central solution concept in non-cooperative game theory. It provides a powerful and general way to predict outcomes in strategic interactions.

Key Takeaways:

• A Nash Equilibrium is a strategy profile where every player is playing a best response to the strategies of all other players.
• It can be intuitively understood as a "no regrets" outcome or a set of "self-fulfilling beliefs."
• Pure-strategy Nash Equilibria can be found methodically by identifying points of mutual best response in a game's payoff matrix.
• The set of Nash Equilibria is a refinement of the strategies that survive IESDS; no NE can ever involve a strictly dominated strategy.

Preview of the next lesson:
The method we learned today works beautifully for finding pure-strategy equilibria. But what about games like Matching Pennies, where there are no such equilibria? To solve these, we need to allow players to randomize. In the next lesson, we will extend our analysis to mixed-strategy Nash Equilibria and learn how to compute them for 2x2 games using the indifference principle.