In odds and evens there is no good move. If you always show one finger, your opponent learns and starts winning every time. The only defence is not to be predictable: to play at random, one half of the time, two the other half. Then, whatever your opponent does, you win half the games.

In 1928, in a paper called On the theory of parlour games, von Neumann showed that this idea holds for every two-person zero-sum game, in which what one wins the other loses. And that it always leads to an exact number, the value of the game.

A small game

Row chooses A or B; Column chooses C or D, at the same time. The table says how much Row receives (and Column pays):

C D
A $3$ $-1$
B $-2$ $1$

There is no obvious choice. If Row always plays A, Column replies with D and Row loses $1$. If Row always plays B, Column replies with C and Row loses $2$. So suppose Row randomises: plays A with probability $p$ and B with probability $1 - p$. Row’s expected gain is

$$\text{against C: } 3p - 2(1-p) = 5p - 2, \qquad \text{against D: } -p + (1-p) = 1 - 2p.$$

Column will choose the reply that gives Row less. So Row can count only on the smaller of the two values, and wants to choose $p$ so that this minimum is as large as possible. That happens where the lines cross:

$$5p - 2 = 1 - 2p \;\Longrightarrow\; p = \frac{3}{7}, \qquad \text{guaranteed gain} = 5 \cdot \frac{3}{7} - 2 = \frac{1}{7}.$$

The value of the game

Now Column’s reasoning: playing C with probability $q$, Column pays Row $4q - 1$ if Row plays A and $1 - 3q$ if Row plays B. The best for Column is to make the two equal: $q = \frac{2}{7}$, and then Column pays at most $\frac17$.

The two numbers coincide. Row can guarantee at least $\frac17$; Column can guarantee to pay at most $\frac17$. This is the minimax theorem:

$$\max_{p}\,\min_{q}\; G(p, q) \;=\; \min_{q}\,\max_{p}\; G(p, q),$$

where $G$ is Row’s expected gain. The left side is the best Row can guarantee alone; the right side, the best Column can guarantee alone. Von Neumann proved that they are always equal, for any finite table, provided the players may randomise.

No, no, chess is not a game. Chess is a well-defined form of computation. […] Real games are not like that at all. Real life consists of bluffing, of little tactics of deception, of asking yourself what is the other man going to think I mean to do. And that is what games are about in my theory.

— John von Neumann, in a taxi conversation in London reported by Jacob Bronowski in The Ascent of Man (1973)

From the parlour to economics

In 1944 von Neumann and the Austrian economist Oskar Morgenstern published Theory of Games and Economic Behavior, a book of more than six hundred pages that took minimax into markets, auctions and negotiations, and defined expected utility in a way economists still use today. Six years later a young man at Princeton called John Nash showed how to extend the idea to games that are not zero-sum, with the equilibrium that bears his name.

Exercise: odds and evens

In odds and evens, whoever guesses the parity of the sum wins $1$ and the other loses $1$. Show that playing 1 or 2 fingers with probability $\frac12$ each guarantees an expected gain of $0$, whatever the opponent does.

If I play 1 with probability $\frac12$ and the opponent plays 1, the sum is even or odd with probability $\frac12$ each: expected gain $\frac12 \cdot 1 + \frac12 \cdot (-1) = 0$. The same holds if they play 2. The value of the game is $0$: neither player has an advantage, but only the one who randomises is protected.

Exercise: Column's strategy

Check that with $q = \frac{2}{7}$ Column pays exactly $\frac17$ both against A and against B.

Against A: $3 \cdot \frac27 + (-1) \cdot \frac57 = \frac{6 - 5}{7} = \frac17$. Against B: $-2 \cdot \frac27 + 1 \cdot \frac57 = \frac{-4 + 5}{7} = \frac17$. Since Column pays the same in both cases, Row has no way of exploiting Column’s choice.

Sources: John von Neumann, “Zur Theorie der Gesellschaftsspiele”, Mathematische Annalen (1928) · John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior (1944) · Jacob Bronowski, The Ascent of Man (1973).

All topics on John von Neumann · ← Ordinals: numbers made of empty sets · Quantum mechanics in a Hilbert space →

Image credits.