A single-file HTML note for core concepts in normal-form games: beliefs, mixed and correlated strategies, dominance, iterated deletion, best responses, and rationalizability.
A normal-form game is written as
\[ G = (N, (S_i)_{i \in N}, (u_i)_{i \in N}) \]where:
| Player 1 \ Player 2 | C | D |
|---|---|---|
| C | (3,3) | (0,4) |
| D | (4,0) | (1,1) |
This is a static, complete-information normal-form game. Each player chooses \(C\) or \(D\) without observing the other's move.
For player \(i\), let
\[ S_{-i} = \prod_{j \neq i} S_j \]A belief of player \(i\) is a probability distribution over opponents' strategy profiles:
\[ \mu_i \in \Delta(S_{-i}) \]So \(\mu_i(s_{-i})\) is the probability that player \(i\) assigns to opponents choosing \(s_{-i}\).
The belief is independent if it factorizes as
\[ \mu_i(s_{-i}) = \prod_{j \neq i} \mu_{ij}(s_j) \]That is, player \(i\) thinks opponents randomize independently.
The belief is correlated if it is any distribution in \(\Delta(S_{-i})\), not necessarily factorizable.
\[ \mu_i \in \Delta(S_{-i}) \quad \text{with no product restriction} \]Suppose player 1 believes players 2 and 3 either both play Left or both play Right:
\[ \mu_1(L,L)=\tfrac12, \qquad \mu_1(R,R)=\tfrac12, \qquad \mu_1(L,R)=\mu_1(R,L)=0 \]This is correlated because the actions of players 2 and 3 move together.
Given a belief \(\mu_i \in \Delta(S_{-i})\), player \(i\)'s expected payoff from strategy \(s_i\) is
\[ U_i(s_i,\mu_i)=\sum_{s_{-i}\in S_{-i}} \mu_i(s_{-i})\,u_i(s_i,s_{-i}) \]A strategy \(s_i\) is a best response to \(\mu_i\) if it maximizes this expected payoff:
\[ s_i \in BR_i(\mu_i) \iff U_i(s_i,\mu_i) \ge U_i(s_i',\mu_i) \quad \forall s_i' \in S_i \]If opponents are believed to choose a specific profile \(s_{-i}\), then
\[ BR_i(s_{-i}) = \arg\max_{s_i \in S_i} u_i(s_i,s_{-i}) \]| Player 1 \ Player 2 | L | R |
|---|---|---|
| U | (2,1) | (0,0) |
| D | (1,2) | (3,1) |
If player 1 believes player 2 will choose \(L\) with probability \(p\), then
\[ U_1(U,\mu_1)=2p, \qquad U_1(D,\mu_1)=p+3(1-p)=3-2p \]Hence \(U\) is a best response when \(2p \ge 3-2p\), i.e.
\[ p \ge \tfrac34 \]A mixed strategy of player \(i\) is a probability distribution over \(S_i\):
\[ \sigma_i \in \Delta(S_i) \]The profile of mixed strategies is \(\sigma=(\sigma_1,\dots,\sigma_n)\in \prod_i \Delta(S_i)\).
This formula uses independence across players' randomizations.
| Player 1 \ Player 2 | H | T |
|---|---|---|
| H | (1,-1) | (-1,1) |
| T | (-1,1) | (1,-1) |
No pure strategy profile is stable, but there is a mixed equilibrium where each player chooses \(H\) and \(T\) with probability \(\tfrac12\).
A correlated strategy is a probability distribution over the full set of action profiles:
\[ \pi \in \Delta(S) \]Unlike mixed strategies, \(\pi\) need not factorize into independent components.
Suppose two players both choose \(A\) or \(B\), and a public coin recommends the same action to both:
\[ \pi(A,A)=\tfrac12, \qquad \pi(B,B)=\tfrac12 \]Then players' actions are perfectly correlated. This cannot generally be represented as independent mixing unless the marginal probabilities happen to match a product form.
A strategy \(s_i \in S_i\) is strictly dominated by another strategy \(s_i'\) if
\[ u_i(s_i',s_{-i}) > u_i(s_i,s_{-i}) \quad \forall s_{-i}\in S_{-i} \]That means \(s_i\) is always worse, no matter what opponents do.
In the payoff matrix from Section 1, for each player, \(D\) strictly dominates \(C\), because
\[ u_i(D,C) = 4 > 3 = u_i(C,C), \qquad u_i(D,D) = 1 > 0 = u_i(C,D) \]So cooperation \(C\) is strictly dominated by defection \(D\).
Start from the original strategy sets \(S_i^0 = S_i\). At each round \(k\), remove all strategies that are strictly dominated in the reduced game. This defines a sequence
\[ S_i^0 \supseteq S_i^1 \supseteq S_i^2 \supseteq \cdots \]where
\[ S_i^{k+1} = \Big\{ s_i \in S_i^k : s_i \text{ is not strictly dominated on } S_{-i}^k \Big\} \]The strategies that survive all rounds are the strategies surviving IDSDS.
| Player 1 \ Player 2 | L | M | R |
|---|---|---|---|
| U | (3,2) | (2,1) | (1,0) |
| D | (2,1) | (1,0) | (0,2) |
For player 2, \(M\) is strictly dominated by \(L\) because \(2>1\) and \(1>0\). Delete \(M\). In the reduced game with columns \(L,R\), player 1 still prefers \(U\) to \(D\) against both columns, so \(D\) is strictly dominated by \(U\). After deleting \(D\), player 2 prefers \(L\) to \(R\). The unique surviving profile is \((U,L)\).
A strategy \(s_i\) is a never best response if there is no belief under which it is optimal:
\[ \nexists\, \mu_i \in \Delta(S_{-i}) \text{ such that } s_i \in BR_i(\mu_i) \]Equivalently, no matter what the player believes about others, that strategy is never optimal.
A strategy \(s_i\) is rationalizable if it is a best response to some belief over opponents' strategies that themselves survive similar reasoning.
Define sets \(R_i^0 = S_i\), and inductively
\[ R_i^{k+1} = \left\{ s_i \in R_i^k : \exists \mu_i \in \Delta(R_{-i}^k) \text{ with } s_i \in BR_i(\mu_i) \right\} \]The strategies that survive all rounds are the rationalizable strategies.
Rationalizable strategies are exactly those that can still be chosen when everyone is rational, everyone knows everyone is rational, everyone knows that everyone knows everyone is rational, and so on.
| Player 1 \ Player 2 | L | R |
|---|---|---|
| U | (2,2) | (0,0) |
| D | (0,0) | (1,1) |
For player 1, \(U\) is a best response to belief "player 2 chooses \(L\)" and \(D\) is a best response to belief "player 2 chooses \(R\)". So both \(U\) and \(D\) are rationalizable. The same holds for player 2.
These ideas are closely related but not identical in wording:
In finite games, a central theorem states:
\[ \text{Rationalizable strategies} = \text{strategies surviving iterated deletion of never-best-responses} \]And equivalently, in finite games:
\[ \text{Rationalizable strategies} = \text{strategies surviving iterated deletion of strategies strictly dominated by mixed strategies} \]Each entry below is a self-contained expanded note. New entries are appended chronologically.
This note gives a concrete example showing a strategy can be a never best response without being strictly dominated by any pure strategy — but it is always dominated by some mixed strategy.
Player 1 chooses among \(\{T,M,B\}\), player 2 chooses among \(\{L,R\}\). The payoff matrix for player 1 is:
\[ \begin{array}{c|cc} & L & R \\\hline T & 1 & 1 \\ M & 3 & 0 \\ B & 0 & 3 \end{array} \]Compare \(T\) with \(M\):
So \(M\) does not strictly dominate \(T\).
Compare \(T\) with \(B\):
So \(B\) also does not strictly dominate \(T\).
Suppose player 1 believes player 2 plays \(L\) with probability \(p\) and \(R\) with probability \(1-p\). The expected payoffs are:
\[ u(T) = 1, \qquad u(M) = 3p, \qquad u(B) = 3(1-p) \]For \(T\) to be a best response we need simultaneously:
\[ 1 \ge 3p \quad\Longrightarrow\quad p \le \tfrac{1}{3} \] \[ 1 \ge 3(1-p) \quad\Longrightarrow\quad p \ge \tfrac{2}{3} \]Therefore, \(T\) is a never best response.
Consider the mixed strategy \(\sigma = \tfrac{1}{2}M + \tfrac{1}{2}B\):
\[ u(\sigma, L) = \tfrac{1}{2}\cdot 3 + \tfrac{1}{2}\cdot 0 = 1.5 > 1 = u(T,L) \] \[ u(\sigma, R) = \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}\cdot 3 = 1.5 > 1 = u(T,R) \]In this game, \(T\) is:
This illustrates the general theorem for finite games:
\[ \text{never best response} \;\iff\; \text{strictly dominated by some mixed strategy} \] \[ \text{never best response} \;\not\Leftarrow\; \text{strictly dominated by a pure strategy} \]