2. Normal-form games
2.3 Best Response and Rationalizability (Chapter 6 & 7)
Best Response
Question: What is the tightest prediction that we can make on the basis of rationality?
Answer: Rational players not only avoid dominated strategies but also avoid strategies that are never a best response
Applying this idea iteratively, we obtain the set of rationalizable strategies
DEFINITION 2.7. Suppose player i has a belief \(\theta_{i} \in \Delta S_{j}\) about player j’s behavior.
Strategy \(s_{i}\) is a best response to belief \(\theta_{i}\) if
\(u_{i}(s_{i}, \theta_{i})\) ≥ \(u_{i}(s_{i}^{\prime}, \theta_{i})\) for every \(s_{i}^{\prime}\ \in S_{i}\).
For any belief \(\theta_{i}\) of player i, we denote by \(BR_{i}(\theta_{i})\) the set of best responses.
Observe that the set of best response is a function of the player’s belief
EXAMPLE 2.12. Suppose player 1 forms a belief \(\theta_{1}\) = (1/3, 1/2, 1/6) on player 2’s behavior in the following game:
1 \ 2 | L | C | R |
U | 2, 6 | 0, 4 | 4, 4 |
M | 3, 3 | 0, 0 | 1, 5 |
D | 1, 1 | 3, 5 | 2, 3 |
Under the belief \(\theta_{1}\), player 1’s expected payoff from each action is
\(u_{1}(U, \theta_{1})\) = \(2 \cdot \frac{1}{3} + 0 \cdot \frac{1}{2} + 4 \cdot \frac{1}{6} = \frac{2}{3} + \frac{2}{3} = \frac{4}{3}\)
\(u_{1}(M, \theta_{1})\) = \(3 \cdot \frac{1}{3} + 0 \cdot \frac{1}{2} + 1 \cdot \frac{1}{6} = 1 \cdot \frac{1}{6} = \frac{7}{6}\)
\(u_{1}(D, \theta_{1})\) = \(1 \cdot \frac{1}{3} + 3 \cdot \frac{1}{2} + 2 \cdot \frac{1}{6} = \frac{1}{3} + \frac{3}{2} + \frac{1}{3} = \frac{13}{6}\)
Hence player 1’s set of best responses is \(BR_{1}(\theta_{1})\) = {D}
Given \(\theta_{2}\) = (1/2, 1/4, 1/4), what is player 2’s best response?
\(u_{2}(L, \theta_{2})\) = \(6 \cdot \frac{1}{2} + 3 \cdot \frac{1}{4} + 1 \cdot \frac{1}{4} = 3 + 1 = 4\)
\(u_{2}(C, \theta_{2})\) = \(4 \cdot \frac{1}{2} + 0 \cdot \frac{1}{4} + 5 \cdot \frac{1}{4} = 2 + \frac{5}{4} = \frac{13}{4}\)
\(u_{2}(R, \theta_{2})\) = \(4 \cdot \frac{1}{2} + 5 \cdot \frac{1}{4} + 3 \cdot \frac{1}{4} = \frac{8+5+3}{4} = \frac{16}{4} = 4\)
Best Responses and Beliefs
Observe that a player’s set of best responses relies upon the player’s beliefs
Playing a best response is not in itself a strategic act
It is formation of beliefs that captures the important strategic component in games
- Success in games often hinges on whether you understand your opponent better than he understands you: you need “outfox” him
- Thus the key question boils down to “What is a reasonable belief for your opponent’s behaviors?”
- One possible answer is that you anticipate him to choose neither strictly dominated strategies nor never best responses
Dominance and Best Response
There is a close relations between dominance and best response. To see this, let
\(B_{i}\) = {\(s_{i} \in S_{i}\) | there exists a belief \(\theta_{i}\) such that \(s_{i} \in BR_{i}(\theta_{i})\)}
\(UD_{i}\) = {\(s_{i} \in S_{i}\) | \(s_{i}\) is not strictly dominated}.
1 \ 2 | L (p) | R (1-p) |
U | 6, 3 | 0, 1 |
M | 2, 1 | 5, 0 |
D | 3, 2 | 3, 1 |
\(u_{1}(U, p)\) = 6p + 0(1-p) = 6p
\(u_{1}(M, p)\) = 2p + 5(1-p) = -3p + 5
\(u_{1}(D, p)\) = 3p + 3(1-p) = 3
f(p) = 6p, f(p) = -3p+5, f(p) = 3, p=(0,1)
x-axis: p, y-axis: u1
6p = 5 – 3p ⇔ 9p = 5 ⇔ p = 5/9
p > \(\frac{5}{9}\) → \(BR_{1}(p)\) = {U}
p < \(\frac{5}{9}\) → \(BR_{1}(p)\) = {M}
p = \(\frac{5}{9}\) → \(BR_{1}(p)\) = {U, M}
P1’s belief \(\theta_{1}\) can be represented by a scalar variable p ∈ [0, 1]
Strategy D is never a best response to player 1 for all p. So \(B_{1}\) = {U, M}.
One can easily see that U and M are undominated. What about strategy D?
To examine if there is a mixed strategy strictly better than D, let \(\sigma_{1}\) = (x, 1-x, 0)
and compute P1’s expected payoff from \(\sigma_{1}\) given his belief p:
xU + (1-x)M = \(\sigma_{1}\)
\(u_{1}(\sigma_{1}, p)\) = x ∙ \(u_{1}\)(U, p) + (1-x)\(u_{1}\)(M, p)
= x ∙ 6p + (1-x)(5-3p)
= 5(1-x) – 3p + 9xp
When x = 1/3, \(u_{1}(\sigma_{1}, p)\) = 10/3, which is greater than 3, the payoff of \(u_{1}\)(D, p)
so strategy D is strictly dominated by mixed strategies U and M.
Strategies that are not dominated by player 1 \(UD_{1}\) = {U, M} = \(B_{1}\)
Rationalizability**
Observe that if a strategy is strictly dominated, then it is never a best response:
\(B_{i} \subseteq UD_{i}\) for all i
The converse is not true in general, but it turns out that the converse is also true at least in 2-player games
Therefore,
strictly dominated ⇔ never a best response in 2-player games.
DEFINITION 2.8. Rationalizable strategies are those that remain after we iteratively remove all strategy that are never a best response to allowable beliefs.
THEOREM 2.9 (BERNHEIM (1984), PEARCE (1984)). In two-player games, a strategies is rationalizable if and only if it survives ISD.
Rationalizability in 3-player games
In games with more than two-players,
the set of rationalizable strategies ⊂ the set of strategies that survives ISD.
To see this relation, consider the following example:
W | E | W | E | W | E | |||
T | 9, 9, 5 | 0, 8, 2 | T | 9, 9, 4 | 0, 8, 0 | T | 9, 9, 1 | 0, 8, 2 |
B | 8, 0, 2 | 7, 7, 1 | B | 8, 0, 0 | 7, 7, 4 | B | 8, 0, 2 | 7, 7, 5 |
L | C | R |
P3’s strategy C (the middle matrix) is not strictly dominated so survives ISD
On the other hand, C is never a best response to any beliefs \(\theta_{3}\), implying that the strategy is not rationalizable
- Reference: Chang-Koo Chi, (6/50) Game Theory and Applications 2 – Rationalizability, Jul 1, 2020, https://youtu.be/Xv21qzNkuXQ