Zero-sum games and minimax

The multiplicity problem left by coordination games disappears entirely in games of pure conflict, and that is why pure conflict was solved twenty years before anything else.

Pure opposition

A two-player game is zero-sum when $u_1(s)+u_2(s)=0$ at every cell, so one player's gain is exactly the other's loss. It is constant-sum when the two payoffs add to the same constant everywhere, which is the same thing for strategic purposes: subtracting half the constant from each player's payoffs is a positive affine transformation, and the first lesson established that those change nothing.

Only one table is needed for such a game. By convention it holds the row player's payoffs, the row player is the maximiser, and the column player, whose payoffs are the negatives, is the minimiser. The phrase "player 2 wants to minimise the number in the cell" is the entire specification of their preferences.

Genuinely zero-sum situations are less common than the phrase's popularity suggests. Most trade, most negotiation and most politics contain gains from agreement, which is precisely what makes them not zero-sum, and treating them as though they were is one of the more expensive errors in public reasoning. But games and sports are built to be zero-sum, and so are the tactical layers inside larger conflicts: which side of the goal, which route for the convoy, which taxpayer to audit.

What you can guarantee yourself

Set equilibrium aside and ask a more defensive question: what can a player guarantee, whatever the opponent does?

For each of the row player's strategies, look at the worst payoff in that row. The best of those worsts is the most the row player can guarantee, called the maximin or the row player's security level. Symmetrically, for each column, look at the largest payoff in it, since that is the worst case from the minimiser's point of view, and take the smallest of those. That is the minimax, the most the column player can be forced to concede.

Two facts follow immediately. First, maximin is always less than or equal to minimax. The row player, moving in the dark, cannot guarantee more than the column player can hold them to. Second, when the two are equal, the cell where they meet is special: its payoff is simultaneously the smallest in its row and the largest in its column, so neither player can gain by moving alone. It is a saddle point, and it is a Nash equilibrium in pure strategies.

The row minima are 4, 1 and 1, so the maximin is 4, achieved by playing T. The column maxima are 5, 4 and 6, so the minimax is 4, achieved by playing C. They agree, the game has a value of 4, and (T, C) is a saddle point: the row player cannot do better than 4 against C, and the column player cannot do better than conceding 4 against T. Neither player needs to conceal anything. The row player could announce T in advance and lose nothing, which is the signature of a game solved in pure strategies.

Example. Find the maximin, the minimax and any saddle point of this zero-sum game.

The row minima are -1 and -2, so the maximin is -1, from playing T. The column maxima are 3 and 2, so the minimax is 2, from playing C. Since $-1<2$ there is no saddle point, and the gap of 3 between what the row player can guarantee and what the column player can be held to is unresolved. No cell is simultaneously a row minimum and a column maximum, and following best responses round the four cells produces a cycle.

Now you. Find the maximin and minimax of this game, and say whether it has a saddle point.

The minimax theorem

The gap between what a player can guarantee and what they can be held to is a gap about predictability, so mixing closes it. That is von Neumann's theorem, proved in the 1928 paper "Zur Theorie der Gesellschaftsspiele" and the foundation of the whole subject:

In any finite two-player zero-sum game, the maximin over mixed strategies equals the minimax over mixed strategies. The common number is the value of the game, and each player has a mixed strategy that guarantees it.

The maximiser has a mixture that yields at least $v$ against every column, and the minimiser has one that concedes at most $v$ against every row. Von Neumann considered this the founding theorem of game theory, and remarked that as far as he could see there could be no theory of games without it.

Computing the value in a two-by-two game with no saddle point uses the indifference method from the earlier lesson, remembering that in a zero-sum game one table serves both players. Take the game above with entries 3 and -1 in the top row, -2 and 2 in the bottom.

Let $p$ be the probability of T. The column player's payoff from L is $-3p+2(1-p)=2-5p$, and from C it is $p-2(1-p)=3p-2$. Equal when $8p=4$, so $p=0.5$. Let $q$ be the probability of L. The row player's payoff from T is $3q-(1-q)=4q-1$, and from B it is $-2q+2(1-q)=2-4q$. Equal when $8q=3$, so $q=0.375$. The value is $4(0.375)-1=0.5$.

That number is the point of the exercise. Playing T and B evenly guarantees the row player an expected 0.5 whatever the column player does, up from the -1 they could guarantee without mixing, and the column player playing L three-eighths of the time holds them to exactly that, down from the 2 they would otherwise concede. The 3-wide gap has closed to a single number.

Example. Solve this zero-sum game: 4 and -2 in the top row, -1 and 1 in the bottom.

Let $p$ be the probability of T. The column player gets $-4p+(1-p)=1-5p$ from L and $2p-(1-p)=3p-1$ from C, equal when $8p=2$, so $p=0.25$. Let $q$ be the probability of L. The row player gets $4q-2(1-q)=6q-2$ from T and $-q+(1-q)=1-2q$ from B, equal when $8q=3$, so $q=0.375$. The value is $6(0.375)-2=0.25$. Check it the other way: $1-2(0.375)=0.25$, as it must be.

Now you. Solve the game with 2 and 5 in the top row, 6 and 1 in the bottom.

Why the prediction is unique

Zero-sum games have three properties that no other class has, and together they are what make the theory unambiguous.

Every equilibrium has the same value. If $({\sigma }_1,{\sigma }_2)$ and $({\tau }_1,{\tau }_2)$ are both equilibria, both pay the row player exactly $v$, because both must simultaneously guarantee at least $v$ and concede at most $v$. There is no equivalent of the battle of the sexes, where one equilibrium pays 3 and another pays 1.

Equilibrium strategies are interchangeable. If those two profiles are equilibria, so are the crossed pairs $({\sigma }_1,{\tau }_2)$ and $({\tau }_1,{\sigma }_2)$. A player therefore does not need to know which equilibrium the opponent has in mind, because any equilibrium strategy of theirs works against any equilibrium strategy of yours. The coordination problem that dominated the previous lesson simply cannot arise.

And the equilibrium strategy is exactly the security strategy. In general games these are different things: the maximin strategy is paranoid and the equilibrium strategy is best-responding, and they usually disagree. In zero-sum games they coincide, so playing for equilibrium and playing safe are the same act. This is why "play the equilibrium strategy" is genuinely good advice in poker or in a penalty shootout, and only conditionally good advice anywhere else.

One more connection is worth naming. Finding the value of a zero-sum game is a linear program, and the two players' problems are dual to each other, with the minimax theorem corresponding exactly to the duality theorem. The link was noticed by von Neumann in conversation with George Dantzig in 1947, and it means that any zero-sum game, however large, can be solved by a standard algorithm rather than by cleverness.

Do professionals actually play minimax?

The theory is sharp enough to test, and it has been. The best-known test is Ignacio Palacios-Huerta's 2003 study of 1,417 penalty kicks from professional league play in Spain, Italy and England between 1995 and 2000. A penalty is close to a genuine zero-sum game: the kicker wants to score, the goalkeeper wants a save, and both commit before seeing the other, since a shot struck at 100 km/h crosses the 11 metres in about four tenths of a second.

Grouping directions into two sides and estimating the scoring probability in each of the four combinations gives this table, as percentages, with the kicker as the maximiser:

There is no saddle point: whichever way the keeper goes, the kicker wants to go the other way, and the keeper wants to follow. Solve it. The keeper is indifferent when $58.30p+92.91(1-p)=94.97p+69.92(1-p)$, where $p$ is the probability the kicker goes left. That gives $22.99=59.66p$, so $p=0.385$. The kicker is indifferent when $58.30q+94.97(1-q)=92.91q+69.92(1-q)$, giving $25.05=59.66q$, so $q=0.420$. The value of the game is a scoring probability of 79.6 per cent.

The frequencies actually observed in the data were close to 0.40 for the kicker and 0.42 for the keeper, within a couple of percentage points of the predicted 0.385 and 0.420. That is a strong result, and it is not the strongest part of the study. Equilibrium also requires the choices to be serially independent, meaning that a kicker who went left last time is no more or less likely to go left this time, and this is where amateurs reliably fail: people asked to produce random sequences alternate too much. In the professional data the sequences pass that test too. Barry O'Neill had found the same in a 1987 laboratory card game, and Mark Walker and John Wooders found it in the serve directions of top tennis players in 2001.

Example. In the penalty table, suppose better goalkeeper coaching raises the save rate when the keeper dives left against a left-footed shot, so that the top-left entry falls from 58.30 to 50.00. What happens to the kicker's equilibrium probability of going left?

The kicker's probability is fixed by the keeper's indifference, which now reads $50.00p+92.91(1-p)=94.97p+69.92(1-p)$. That gives $92.91-42.91p=69.92+25.05p$, so $22.99=67.96p$ and $p=0.338$. Improving the keeper's left-side save rate makes the kicker go left less often, from 38.5 per cent to 33.8 per cent, exactly the pattern from the audit game: your own payoffs move the other player.

Now you. With the original table, what would the kicker's expected scoring rate be if they went left every time against a keeper still playing $q=0.420$?

The limits of a beautiful result

Everything in this lesson depends on the interests being exactly opposed, and that assumption is fragile in a specific way: it is not preserved by adding anything the players care about jointly. Two firms in a price war are close to zero-sum over market share and not at all zero-sum over whether the war happens. A penalty kick is zero-sum; the match around it, in which a draw may suit both teams, is not.

The theorem also says nothing about how a value is divided when there is a surplus to divide, because in a zero-sum game there is no surplus by construction. Everything from here on is about games where there is one: firms choosing quantities, players moving in sequence, partners deciding whether to cooperate, and bargainers splitting a pie.

The immediate next step is smaller and more concrete. Every game so far has had a strategy set that could be listed as rows and columns, and real economic choices are numbers on a continuum: a price, a quantity, a bid, a level of effort. Best responses then become functions rather than table entries, and the equilibrium is found by solving equations. That is the next lesson.