19  Nash Equilibrium

A solution concept is a systematic description of the outcomes (i.e., the strategy profiles) that may emerge in a family of games. Solution concepts are the main tools used to analyze strategic situations and are intended to embody different notions of rational behavior.

A best response for player \(i\) to a specific combination of other players’ actions is the action that maximizes player \(i\)’s utility, assuming the other players follow their specified actions.

Consider the following game:

Column
\(l\) \(r\)
Row \(u\) 2, 1 0, 0
\(d\) 0, 0 1, 2

Row’s best responses:

Column’s best responses:

A Nash equilibrium is a strategy profile where every player’s action is a best response to the other players’ actions. At a Nash equilibrium, no player can improve their utility by unilaterally changing their strategy.

In the game above, there are two Nash equilibria:

19.1 Additional Examples

19.1.1 Example 1: Two Nash Equilibria

Column
\(l\) \(r\)
Row \(u\) 2, 2 2, 1
\(d\) 1, 2 3, 3

There are two Nash equilibria: \((u, l)\) and \((d, r)\). Even though \((d, r)\) gives both players their best possible payoffs, \((u, l)\) is also a Nash equilibrium. This illustrates that players could be stuck at an inferior equilibrium when a mutually beneficial one exists.

19.1.2 Example 2: Unique Nash Equilibrium

Column
\(l\) \(r\)
Row \(u\) 2, 2 2, 1
\(d\) 1, 3 10, 2

The unique Nash equilibrium is \((u, l)\). Despite the large payoff of 10 at \((d, r)\), Row cannot achieve it because Column would deviate to \(l\).

19.1.3 Example 3: Nash Equilibria with Indifference

Column
\(l\) \(r\)
Row \(u\) 0, 1 2, 1
\(d\) 2, 0 2, 2

Nash equilibria: \((u, r)\) and \((d, r)\). When Column plays \(r\), Row receives payoff 2 from either \(u\) or \(d\)—Row is indifferent between these strategies. Both \((u, r)\) and \((d, r)\) are Nash equilibria because Row has no incentive to deviate (being indifferent) and Column strictly prefers \(r\) to \(l\) in both cases.

19.1.4 Example 4: No Nash Equilibrium in Pure Strategies

Not all games have Nash equilibria in pure strategies. The classic “Matching Pennies” game illustrates this:

Column
\(H\) \(T\)
Row \(H\) 1, -1 -1, 1
\(T\) -1, 1 1, -1

In this zero-sum game, one player wins when the coins match and the other wins when they differ. No strategy profile forms a Nash equilibrium because one player always has an incentive to deviate.

19.2 Mixed Strategies

A mixed strategy is a probability distribution—i.e., a lottery (Definition 1)—over a player’s available actions. Instead of choosing a single action, a player randomizes their choice according to the probabilities specified in their mixed strategy.

19.2.1 Mixed Strategy Nash Equilibrium

Recall the Matching Pennies game, which has no pure strategy Nash equilibrium:

Column
\(H\) \(T\)
Row \(H\) 1, -1 -1, 1
\(T\) -1, 1 1, -1

This game has a mixed strategy Nash equilibrium: \[ (1/2 \cdot H + 1/2 \cdot T, 1/2 \cdot H + 1/2 \cdot T). \] Each player randomizes with equal probability between their two actions.

Games can have both pure and mixed strategy equilibria. Consider our earlier example:

Column
\(l\) \(r\)
Row \(u\) 2, 1 0, 0
\(d\) 0, 0 1, 2

This game has three Nash equilibria:

  • Pure strategy equilibria: \((u, l)\) and \((d, r)\)
  • Mixed strategy equilibrium: \((2/3 \cdot u + 1/3 \cdot d, 1/3 \cdot l + 2/3 \cdot r)\)

19.2.2 Interpreting Mixed Strategies

The concept of randomized play challenges our intuition about decision-making. As Ariel Rubinstein (1991) notes: “We are reluctant to believe that our decisions are made at random. We prefer to be able to point to a reason for each action we take. Outside of Las Vegas we do not spin roulettes.”

What does it mean to play a mixed strategy? There are several interpretations that are used in game theory:

  1. Strategic uncertainty: Players use mixed strategies to make themselves unpredictable, preventing opponents from exploiting predictable behavior (particularly relevant in zero-sum games like Matching Pennies).

  2. Beliefs about opponents: A player’s mixed strategy represents other players’ beliefs about what that player will do, rather than deliberate randomization.

  3. Long-run frequencies: Mixed strategies describe the distribution of actions in repeated play of the game over time.

  4. Population interpretation: In a large population where players are randomly matched to play the game, a mixed strategy represents the proportion of players choosing each pure strategy.

Each interpretation offers insight into why mixed strategies emerge in strategic situations, even when deliberate randomization seems counterintuitive.

19.3 Existence of Nash Equilibria

A fundamental result in game theory is that every finite game has at least one Nash equilibrium when mixed strategies are allowed. This was proven by John Nash in his seminal 1950 paper (Nash 1950), establishing the existence of equilibria in a broad class of games.

A mixed strategy Nash equilibrium is a profile of mixed strategies where each player’s mixed strategy is a best response to the other players’ mixed strategies. Formally, for a two-player game, a mixed strategy profile \((\sigma_1, \sigma_2)\) is a Nash equilibrium if:

  • Player 1’s expected utility from playing \(\sigma_1\) against \(\sigma_2\) is at least as high as the expected utility from any other strategy against \(\sigma_2\)
  • Player 2’s expected utility from playing \(\sigma_2\) against \(\sigma_1\) is at least as high as the expected utility from any other strategy against \(\sigma_1\)

To see how this works, consider the Matching Pennies game. Suppose Row plays \(H\) with probability \(p\) and Column plays \(H\) with probability \(q\). Row’s expected utility from playing pure strategy \(H\) is: \[EU_{Row}(H) = q \cdot 1 + (1-q) \cdot (-1) = 2q - 1\]

Row’s expected utility from playing pure strategy \(T\) is: \[EU_{Row}(T) = q \cdot (-1) + (1-q) \cdot 1 = 1 - 2q\]

For Row to be willing to mix between \(H\) and \(T\), these expected utilities must be equal: \[2q - 1 = 1 - 2q\] \[4q = 2\] \[q = 1/2\]

By symmetry, Column must also play each action with probability \(1/2\) for Row to be indifferent. When both players randomize equally, neither player can improve their expected utility by changing strategies—this is the unique mixed strategy Nash equilibrium \((1/2 \cdot H + 1/2 \cdot T, 1/2 \cdot H + 1/2 \cdot T)\).

Nash’s existence theorem guarantees that while a game may lack pure strategy equilibria (as in Matching Pennies), there will always be at least one equilibrium when players can randomize.