Two-Person Zero-Sum Games

Decision analysis pits you against an indifferent world — the market doesn't care what you pick. But some opponents care very much, and choose to hurt you: a rival pricing against you, a defender and an attacker, two players of rock-paper-scissors. When one side's gain is exactly the other side's loss, the game is zero-sum, and it has a gorgeous, complete mathematical theory — the founding result of game theory, and the place where optimisation and strategy turn out to be the same subject.

The payoff matrix

List one player's strategies as rows, the other's as columns, and fill each cell with the row player's payoff. Because the game is zero-sum, that number is automatically the column player's loss — one matrix holds everything. The row player (call her Rose) wants big numbers; the column player (Colin) wants small ones. Here Rose picks a row, Colin picks a column, and the entry is what Colin pays Rose:

	Colin C₁	Colin C₂	Colin C₃	row min
Rose R₁	3	5	2 ◀ saddle	2
Rose R₂	1	4	0	0
Rose R₃	6	2	1	1
col max	6	5	2

Notice already that R₁ beats R₂ in every column (3>1, 5>4, 2>0), so Rose would never play R₂ — it is dominated and can be deleted. Stripping dominated rows and columns shrinks a game before you even start solving it.

Maximin, minimax, and the saddle point

Rose reasons pessimistically: whichever row she picks, Colin will drive her to the row's smallest entry. So she picks the row whose minimum is largest — the maximin. The row minima are 2, 0, 1, so her guarantee is \max(2,0,1) = 2, achieved by R₁.

Colin reasons the same way in reverse: each column, Rose will push to its largest entry, so he picks the column whose maximum is smallest — the minimax. The column maxima are 6, 5, 2, so his guarantee is \min(6,5,2) = 2, at C₃. The two guarantees coincide:

When \text{maximin} = \text{minimax}, that common value is a saddle point — an entry that is simultaneously the smallest in its row and the largest in its column.
Both players have an optimal pure strategy (here R₁ and C₃), and neither can do better by deviating. The shared number is the value of the game — here v = 2.

It is called a saddle because, like the seat of a saddle, the point curves up away from it in one direction (down the column) and down in the other (along the row).

When there's no saddle: mix it up

Not every game is so obliging. The classic troublemaker is matching pennies: both reveal a coin; Rose wins if they match, Colin wins if they differ.

	Colin: Heads	Colin: Tails	row min
Rose: Heads	+1	−1	−1
Rose: Tails	−1	+1	−1
col max	+1	+1

Here maximin = -1 but minimax = +1 — they don't meet, so there is no saddle and no good pure strategy. Any fixed choice can be exploited the moment the opponent reads it. The escape is a mixed strategy: choose randomly, by a probability. For a 2\times 2 game \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} with no saddle, the value is

v = \frac{ad - bc}{a + d - b - c}.

For matching pennies (a,b,c,d) = (1,-1,-1,1), giving v = (1-1)/(1+1+1+1) = 0: a fair game, each player flipping a fair coin (50/50). Change the game to \begin{smallmatrix} 4 & 0 \\ 1 & 3 \end{smallmatrix} and the same formula gives v = 12/6 = 2, with Rose mixing R₁ one-third of the time — a definite edge, extracted purely by randomising.

Seeing the mix: the value is the peak of the lower envelope

Here is matching pennies as a picture. Let Rose play Heads with probability p. The two faint lines are her expected payoff when Colin plays Heads (2p-1) and when he plays Tails (1-2p). A shrewd Colin always leaves her the lower of the two, so Rose picks p to lift that thick lower envelope as high as it will go — to its peak. Drag the slider:

The peak sits at p = 0.5, where the two threats balance and the guaranteed payoff is 0 — exactly the value the formula gave. Lean either way and a watchful opponent drags Rose below zero. Balancing on that peak is what "play 50/50" really means, and it is the picture behind every mixed-strategy solution: maximise the lower envelope.

The minimax theorem — and why it's really an LP

Does a value always exist, even with mixing? John von Neumann proved in 1928 that it does:

Every finite two-person zero-sum game has a value v and optimal mixed strategies for both players.
At the optimum, \max_{\text{Rose}} \min_{\text{Colin}} = \min_{\text{Colin}} \max_{\text{Rose}} = v — the order of "I move, you respond" stops mattering.

The astonishing part for an OR course is how you compute it. Finding the optimal mixed strategy is exactly a linear program: Rose maximises her guaranteed value subject to "beat every column," Colin minimises subject to "survive every row" — and these two LPs are duals of each other. The minimax theorem is, at heart, LP duality in disguise; the equality of the two guarantees is the equality of a primal and its dual optimum. Solving a game and solving a linear program are the same act.

In matching pennies, any pattern you fall into — "I favour heads," "I alternate" — is a gift to your opponent, who simply exploits it. The only unexploitable play is genuine randomness at exactly 50/50: it leaves nothing to read. This is why tennis servers deliberately randomise placement, why penalty-takers mix corners, and why a poker player bluffs at a calculated rate. Optimal play in a game without a saddle is not a clever fixed move — it is a probability distribution you sample from and refuse to explain.

The tempting mistake is to hunt for the "best" pure strategy even when none exists. In matching pennies every pure strategy has the same dismal guarantee (-1), and picking one and sticking to it is the worst thing you can do — a watching opponent beats it every time. When maximin \ne minimax there is no saddle, and the whole point is that you must mix, unpredictably, at the probabilities the theory prescribes. "I'll just always play my strongest option" is precisely the plan a zero-sum opponent prays for.