Mixed Strategies & the Minimax Theorem
Mixed Strategies & the Minimax Theorem
Mixed strategies extend the strategy space by allowing players to randomize. A mixed strategy $\sigma_i\in\Delta(S_i)$ is a probability distribution over pure strategies. The expected payoff under mixed profile $(\sigma_1,\ldots,\sigma_n)$ is $u_i(\sigma)=\sum_{s\in S}u_i(s)\prod_j\sigma_j(s_j)$. Von Neumann's 1928 minimax theorem — arguably the first theorem of game theory — shows that zero-sum games have a well-defined value, solved by linear programming.
Von Neumann Minimax Theorem
For any finite two-player zero-sum game with matrix $A$ (player 1's payoffs, player 2 pays), $$\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^\top Ay = \min_{y\in\Delta_n}\max_{x\in\Delta_m}x^\top Ay = V$$ where $V$ is the value of the game. The optimal strategies $(x^*,y^*)$ form a saddle point of the bilinear form $x^\top Ay$. Any Nash equilibrium of a zero-sum game achieves this minimax value.
Minimax Strategies via Linear Programming
The optimal mixed strategy $x^*$ for player 1 in the game with matrix $A$ solves: maximize $V$ subject to $A^\top x\geq V\mathbf{1}$, $\mathbf{1}^\top x=1$, $x\geq 0$. This is a linear program. Player 2's optimal $y^*$ solves the dual LP. The LP duality theorem implies von Neumann's minimax theorem: strong duality equals the minimax equality. Any $m\times n$ zero-sum game can be solved in polynomial time.
Example 1
Find the mixed Nash equilibrium of Matching Pennies: (H,H)=(1,-1),(H,T)=(-1,1),(T,H)=(-1,1),(T,T)=(1,-1).
Solution: Player 1 randomizes $p=P(H)$ to make player 2 indifferent: $p\cdot(-1)+(1-p)\cdot 1=p\cdot 1+(1-p)\cdot(-1)$, giving $1-2p=2p-1$, so $p=\frac{1}{2}$. Similarly $q=\frac{1}{2}$. The unique Nash equilibrium is $(\frac{1}{2},\frac{1}{2};\frac{1}{2},\frac{1}{2})$ with value $V=0$. In the unique equilibrium of any zero-sum game, each player's strategy makes the opponent indifferent over all best responses.
Example 2
Solve the zero-sum game with matrix $A=\begin{pmatrix}3&1\\2&4\end{pmatrix}$.
Solution: Check for saddle point: $\min_j\max_i a_{ij}=\min(3,4)=3$; $\max_i\min_j a_{ij}=\max(1,2)=2$. No saddle point (pure equilibrium). For mixed: player 1 plays $(p,1-p)$: $3p+(1-p)\cdot 2=p+(1-p)\cdot 4\Rightarrow 2p+2=3-3p\Rightarrow p=1/5$. Value $V=3(1/5)+2(4/5)=3/5+8/5=11/5$. Player 2 plays $(q,1-q)$: $3q+1-q=2q+4-4q\Rightarrow 2q+1=-2q+4\Rightarrow q=3/4$. Equilibrium: $(1/5,4/5;3/4,1/4)$, $V=11/5$.
Practice
- Find all Nash equilibria of Rock-Paper-Scissors (payoff matrix is the cyclic $3\times 3$ zero-sum game).
- Prove that in any Nash equilibrium of a two-player zero-sum game, both players achieve the minimax value.
- A $2\times 2$ zero-sum game has matrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}$. Derive the mixed equilibrium formula $p^*=(d-c)/(a-b-c+d)$ when no saddle point exists.
- Formulate player 2's optimal strategy in a zero-sum game as a linear program and identify it as the dual of player 1's LP.
Show Answer Key
1. RPS has no pure NE (each strategy is beaten by exactly one other). The unique mixed NE is $(1/3,1/3,1/3)$ for both players, with expected payoff 0 for each.
2. In a NE of a zero-sum game, player 1's payoff $\ge$ his maximin value (best guarantee). Player 2's payoff $\ge$ her maximin $=$ $-$(player 1's minimax). Since payoffs sum to 0, both equal the minimax value. This is the minimax theorem.
3. Player 1 mixes with prob $p$ on row 1. Player 2's expected payoffs must be equal: $ap+(1-p)c=bp+(1-p)d$. Solving: $p^*=(d-c)/(a-b-c+d)$. Similarly $q^*=(d-b)/(a-b-c+d)$ for player 2. Valid when no saddle point (pure NE) exists.
4. Player 1's LP: $\max v$ s.t. $\sum_j A_{ij}x_j\ge v$ for all $i$, $\sum x_j=1$, $x_j\ge0$. Player 2's LP (dual): $\min w$ s.t. $\sum_i A_{ij}y_i\le w$ for all $j$, $\sum y_i=1$, $y_i\ge0$. By strong duality, $v^*=w^*$ (the game value).