Minimax Theorem
Every finite zero-sum game has a value — and a mixed strategy achieves it.
The idea
Theorem (Minimax theorem).
Let $A$ be the payoff matrix of a finite two-player zero-sum game, let $x$ range over probability distributions on the rows and $y$ over probability distributions on the columns. Then $\max_{x} \min_{y} \; x^{\top} A y \;=\; \min_{y} \max_{x} \; x^{\top} A y.$ The common value $v$ is the value of the game.
The theorem, proved by von Neumann, concerns zero-sum games, in which one player's gain is exactly the other's loss. A single payoff matrix $A$ then describes the game: Row chooses a row, Column chooses a column, and Column pays Row the selected entry, so Row wants it large and Column wants it small. A mixed strategy is a probability distribution — $x$ over the rows, $y$ over the columns — and the expected payment is $x^{\top} A y$.
The left side of the equation is the most Row can guarantee to receive when Row commits to a mix first and Column answers it; the right side is the least Column can guarantee to pay when Column commits first. Committing first can only help the opponent, so the left side never exceeds the right. The theorem says the two are equal: a player who announces an optimal mixed strategy loses nothing, because an opponent who knows the mix still cannot push the payoff past $v$. Restricted to single rows and columns the two guarantees can differ; randomization is what closes the gap.
The figure shows the computation behind an optimal mix: plotted against Row's mixing probability $p$, Row's expected payoff under each of Column's two pure responses is a straight line, and the crossing at $p^{*}$ — where the two responses pay the same — is the mix that secures the value $v$.
Ways to work on it
- Walkthrough. Compute a game's maximin and minimax values and see when they pin down a saddle point.
- Practice. Compute a game's mixed equilibrium and verify its value.
- Hardest. Random 2 × 2 game without a pure saddle — find the mixing probability and the game value.
Not sure where to start? Take the ten-question placement test.