Zero-Sum Games and Minimax

Look at a game where one player's gain is exactly the other's loss. Edit the payoff numbers yourself.

I try to make my worst case as good as possible. My rival tries to make my gains as small as possible. When the two calculations agree, a saddle point appears and the equilibrium is pure. When they disagree, both players must mix, and the game gets a value as in the formula below.

For example, bet one 🍬 candy on guessing heads or tails of a coin. Guess right and the candy is yours. Guess wrong and your 🧑 friend takes it. Whatever you win, your friend loses. So both of you mix to stay unreadable.

max⁡rmin⁡curc≤min⁡cmax⁡rurc\max_r \min_c u_{rc} \le \min_c \max_r u_{rc}
v=ad−bca−b−c+d,p∗=d−ca−b−c+dv = \frac{ad-bc}{a-b-c+d}, \quad p^* = \frac{d-c}{a-b-c+d}

Examples & Exercises

View Matching Pennies as a zero-sum game: compute maximin and minimax, confirm there is no saddle point, then find the mixed equilibrium and the value of the game.

max⁡rmin⁡curc=max⁡(−1,−1)=−1,min⁡cmax⁡rurc=min⁡(1,1)=1\max_r \min_c u_{rc} = \max(-1, -1) = -1, \qquad \min_c \max_r u_{rc} = \min(1, 1) = 1
Matching Pennies — maximin −1<1=-1 < 1 = minimax, no saddle point.
Show proof

  1. Both row minima are −1-1, so maximin =−1{}= -1; both column maxima are 11, so minimax =1= 1. Since −1<1-1 < 1, no saddle point exists — no cell is simultaneously a row minimum and a column maximum.

  2. The fully mixed formulas give p∗=d−ca−b−c+d=24=12p^* = \frac{d-c}{a-b-c+d} = \frac{2}{4} = \frac12, q∗=12q^* = \frac12, value v=ad−bca−b−c+d=0v = \frac{ad-bc}{a-b-c+d} = 0. As von Neumann's minimax theorem promises, allowing mixing makes maximin and minimax coincide at 00.

For the zero-sum game with the payoff matrix below, find maximin and minimax; with no saddle point, compute the mixed equilibrium (p∗,q∗)(p^*, q^*) and the value.

(4123)\begin{pmatrix}4 & 1 \\ 2 & 3\end{pmatrix}
p∗=d−ca−b−c+d,q∗=d−ba−b−c+d,v=ad−bca−b−c+dp^* = \frac{d-c}{a-b-c+d}, \quad q^* = \frac{d-b}{a-b-c+d}, \quad v = \frac{ad-bc}{a-b-c+d}
(4123)\begin{pmatrix}4 & 1 \\ 2 & 3\end{pmatrix} — mixed equilibrium p∗=1/4p^* = 1/4, q∗=1/2q^* = 1/2, v=2.5v = 2.5.
Show proof

  1. Row minima: min⁡(4,1)=1\min(4,1) = 1, min⁡(2,3)=2\min(2,3) = 2, so maximin =2= 2 (bottom row).

    Column maxima: max⁡(4,2)=4\max(4,2) = 4, max⁡(1,3)=3\max(1,3) = 3, so minimax =3= 3 (right column).

    Since 2≠32 \ne 3, there is no saddle point.

  2. With a−b−c+d=4a - b - c + d = 4: p∗=3−24=14p^* = \frac{3-2}{4} = \frac14, q∗=3−14=12q^* = \frac{3-1}{4} = \frac12, v=12−24=2.5v = \frac{12-2}{4} = 2.5. Check: at q∗q^*, player 1's expected payoffs are 4⋅12+1⋅12=2.5=2⋅12+3⋅124 \cdot \frac12 + 1 \cdot \frac12 = 2.5 = 2 \cdot \frac12 + 3 \cdot \frac12 — equal, as indifference requires.

8. Game Theory