Best Response Correspondence in Finite Games

Recommended resources

The freely available resources this lesson will direct you to.

Introduction

In our last lesson, we focused on a "negative" solution concept: eliminating strategies that a rational player would never play. By iteratively removing strictly dominated strategies (IESDS), we simplified the game without losing any potential Nash equilibria. This is like pruning the branches of a search tree that you know won't lead to a solution.

Today, we shift to a "positive" solution concept. Instead of asking "what shouldn't a player do?", we'll ask "what should a player do?". We will define and compute the best response for each player. This concept captures the optimal choice for a player, given a fixed set of strategies played by their opponents.

Our learning outcome is to compute best response correspondences for each player in a finite game. This is a fundamental tool. Mastering it is the direct prerequisite for our next lesson, where we will find Nash equilibria by identifying strategy profiles where every player is simultaneously playing a best response to everyone else.

What is a Best Response?

A player's best response is the strategy (or set of strategies) that yields the highest possible payoff, given what the other players are doing. It is a direct consequence of assuming players are rational payoff-maximizers.

Formally, for player $i$ , a strategy $s_{i}^{*} \in S_{i}$ is a best response to the opponents' strategy profile $s_{- i} \in S_{- i}$ if:

u_{i} (s_{i}^{*}, s_{- i}) \geq u_{i} (s_{i}^{'}, s_{- i}) for all s_{i}^{'} \in S_{i}

The set of all such best responses for player $i$ to $s_{- i}$ is denoted $B R_{i} (s_{- i})$ . Notice that this is a set, which could contain one or more strategies. When there are multiple strategies that yield the same maximum payoff, the player is indifferent between them, and they are all best responses. The mapping from opponent strategies to this set of best responses is called the best response correspondence.

Computing Best Responses to Pure Strategies

Let's start with the simplest case: finding a player's best response to their opponents' pure strategies. There is a simple and effective method for this.

Fix one player, say Player 1.
Consider the first pure strategy of Player 2. Look down that column in the payoff matrix and find the highest payoff for Player 1. The corresponding row strategy is Player 1's best response to that specific strategy of Player 2.
Repeat this for all of Player 2's pure strategies.
Now, switch roles. Fix Player 1's strategies one by one, and find Player 2's best response in each corresponding row.

This "underlining" or "asterisk" method is a quick way to map out all pure-strategy best responses in a game.

Game Theory 101 (#6): Best Responses

This video from William Spaniel provides a very clear walkthrough of this mechanical process. It's an efficient way to find best responses in a normal-form game.

Watch the segment from 01:57 to 06:22. The key is to see how you isolate one player's decision at a time, holding the other player's strategy fixed. Notice that a best response can sometimes be more than one strategy (when payoffs are tied).

The video concludes by noting that cells where all payoffs are marked (e.g., with asterisks) are mutual best responses. This is the definition of a Pure Strategy Nash Equilibrium, a topic we will formalize in our next lesson.

From Best Response to Best Response Correspondence

The "underlining" method works for pure strategies, but what if your opponent plays a mixed strategy? For example, in a 2x2 game, what is Player 1's best response if Player 2 plays Left with probability $q$ and Right with probability $1 - q$ ?

To answer this, we need to calculate Player 1's expected utility for each of their pure strategies, given Player 2's mixed strategy $σ_{2}$ . Player 1 will then choose the pure strategy (or mix of pure strategies) that maximizes this expected utility.

The function that maps the opponent's mixed strategy (e.g., $q$ ) to the player's set of optimal strategies (e.g., which probability $p$ to use) is the best response correspondence. Let's work through the computation.

[PDF] Chapter 6 - Princeton University

This section from a Princeton University Press textbook chapter on mixed strategies provides a rigorous and clear derivation of the best response correspondence for the classic 'Matching Pennies' game. This is the core computational skill for this lesson.

Please read Section 6.2.1, 'Example: Matching Pennies' (pages 108-111). Focus on the following steps: How the expected payoffs for Player 1, v1(H, q) and v1(T, q), are calculated as functions of q. How comparing these two expected payoffs (v1(H, q) > v1(T, q)) leads to a condition on q (e.g., q > 1/2). How this leads to the piecewise definition of BR1(q), which defines Player 1's optimal probability p for every possible q. How the same logic is applied to find BR2(p).

The crucial insight from this reading is that a player is only willing to mix their strategies if they are indifferent between the pure strategies in their mix. For Player 1 to be willing to play both Heads and Tails (i.e., use some $p \in (0, 1)$ ), it must be that their expected payoff from Heads is equal to their expected payoff from Tails. This indifference condition, $v_{1} (H, q) = v_{1} (T, q)$ , is what determines the specific mixing probability $q = 1/2$ from Player 2 that makes Player 1 willing to mix.

Visualizing Best Response Correspondences

Graphing these correspondences makes the concept much more intuitive. For a 2x2 game with probabilities $p$ and $q$ , we can draw the graphs of $B R_{1} (q)$ and $B R_{2} (p)$ on a unit square.

Best Response Correspondence Graph — This graph illustrates the best response correspondences for two players. The horizontal axis is the Kicker's probability `p` of shooting Left, and the vertical axis is the Goalie's probability `q` of diving Left. The Kicker's best response `BR_K(q)` is in green, and the Goalie's `BR_G(p)` is in red. The points on the lines represent the optimal strategy for one player given the other's strategy.

As you can see, each player's correspondence shows their optimal probability jumping from 0 to 1 at the indifference point of their opponent. At that exact point, any probability between 0 and 1 is a best response.

Let's look at another example to solidify the calculation and see how it applies to a game with multiple equilibria.

[PDF] Weeks 4-5: Mixed Strategies - University of Warwick

The game in this example has two pure strategy equilibria and one mixed strategy equilibrium. The reading walks through deriving the best response correspondences for both players and then plots them.

Please read the two sections 'Finding All Nash Equilibria' and 'Graphs of Best Responses' on pages 43 and 44. Observe how the expected utility functions u1(U, σ2) and u1(D, σ2) are used to derive BR1(σ2) in its piecewise form, and similarly for Player 2. Then, examine the resulting graph and see how the two correspondences are plotted.

This second example reinforces the procedure and visually demonstrates how the intersections of the best response curves will reveal all Nash equilibria in the game, a topic we will formally cover next.

Practice Problem

Let's compute the best response correspondences for the "Battle of the Sexes" game.

Player 2

	Ballet	Football
Player 1
Ballet	2, 1	0, 0
Football	0, 0	1, 2

Your task is to compute $B R_{1} (σ_{2})$ and $B R_{2} (σ_{1})$ .

Let $p$ be the probability that Player 1 chooses Ballet.
Let $q$ be the probability that Player 2 chooses Ballet.
Calculate Player 1's expected utility for choosing Ballet and for choosing Football, as functions of $q$ .
Use these to define $B R_{1} (q)$ as a piecewise function.
Repeat the process for Player 2 to find $B R_{2} (p)$ .

Click here for the solution.

1. Player 1's Best Response Correspondence: $B R_{1} (q)$

Player 1's expected utility from choosing Ballet, given Player 2 plays Ballet with probability $q$ :
$E_{1} (Ballet, q) = q \cdot 2 + (1 - q) \cdot 0 = 2 q$
Player 1's expected utility from choosing Football:
$E_{1} (Football, q) = q \cdot 0 + (1 - q) \cdot 1 = 1 - q$

Player 1 prefers Ballet if $E_{1} (Ballet, q) > E_{1} (Football, q)$ :

2 q > 1 - q ⟹ 3 q > 1 ⟹ q > 1/3

Player 1 is indifferent if $2 q = 1 - q ⟹ q = 1/3$ .
Player 1 prefers Football if $q < 1/3$ .

So, Player 1's best response correspondence (where $p$ is the probability of playing Ballet) is:

B R_{1} (q) = ⎩ ⎨ ⎧ p = 0 p \in [0, 1] p = 1 if q < 1/3 if q = 1/3 if q > 1/3

2. Player 2's Best Response Correspondence: $B R_{2} (p)$

Player 2's expected utility from choosing Ballet, given Player 1 plays Ballet with probability $p$ :
$E_{2} (p, Ballet) = p \cdot 1 + (1 - p) \cdot 0 = p$
Player 2's expected utility from choosing Football:
$E_{2} (p, Football) = p \cdot 0 + (1 - p) \cdot 2 = 2 - 2 p$

Player 2 prefers Ballet if $E_{2} (p, Ballet) > E_{2} (p, Football)$ :

p > 2 - 2 p ⟹ 3 p > 2 ⟹ p > 2/3

Player 2 is indifferent if $p = 2/3$ .
Player 2 prefers Football if $p < 2/3$ .

So, Player 2's best response correspondence (where $q$ is the probability of playing Ballet) is:

B R_{2} (p) = ⎩ ⎨ ⎧ q = 0 q \in [0, 1] q = 1 if p < 2/3 if p = 2/3 if p > 2/3

Conclusion

In this lesson, we moved from eliminating bad strategies to identifying optimal ones. We have established a rigorous method for determining a player's best course of action for any given strategy—pure or mixed—of their opponents.

Key Takeaways:

A best response is a strategy that yields the maximum possible payoff given the opponents' actions.
The best response correspondence is a mapping from the opponents' strategy profile to the set of a player's best responses.
For 2-player, 2-strategy games, we can compute the best response correspondence by defining opponent strategies as a probability distribution (e.g., using $p$ and $q$ ) and calculating the expected utility for each of our pure strategies.
A player is only willing to play a mixed strategy if they are indifferent between the pure strategies involved in the mix. This indifference condition is what allows us to solve for the specific opponent mixture that makes mixing a best response.

In our next lesson, we will put this tool to its ultimate use. We will formally define a Nash Equilibrium as a profile of strategies where every player's strategy is a best response to the strategies of the others. Using the correspondences we learned to compute today, we will find these equilibria by simply finding the points where the best response graphs intersect.