Mixed Strategies and Zero-Sum Games

What you’re seeing

Mixed strategies

A mixed strategy is a probability distribution over a player’s actions: “Rock with probability 1/2, Paper 1/4, Scissors 1/4.” Playing one action for sure, a pure strategy, is the special case of probability 1. When the other players mix, your payoff is uncertain, so we compare strategies by their expected payoff: the average payoff, weighting each action profile by how likely it is. With two players mixing independently,

Here payoffs must mean more than a ranking. Comparing a sure 2 with a fifty-fifty chance of 0 or 3 needs numbers that measure how much a player likes each outcome, so that averages make sense. Von Neumann and Morgenstern showed in 1944 that if a person’s choices among gambles obey a few consistency rules, there are such numbers; they are called von Neumann–Morgenstern utilities or Bernoulli payoffs.

A mixed strategy Nash equilibrium is a profile of mixed strategies in which each player’s mix is a best response to the others’ mixes. And here is the key fact for finding one.

Why? If one action in your mix paid more than another, you could shift probability toward it and do better, so your mix wasn’t a best response. So at equilibrium, every action you mix must pay exactly the same. That gives equations you can solve.

Solving any 2×2 game: the indifference principle at work

Let player 1 play the top row with probability p, and player 2 the left column with probability q. Player 2 is willing to mix only if both columns give the same expected payoff, and that pins down p. Player 1 is willing to mix only if both rows give the same payoff, and that pins down q:

A surprise hides in that formula: each player’s equilibrium mix is set by the other player’s payoffs. Your mix is not chosen to help you (you are indifferent anyway); it is whatever leaves your opponent with no action worth exploiting. Slide p and q below, or drag on the charts, and watch the lines cross.

Zero-sum games and minimax

In a zero-sum (or strictly competitive) game, one player’s gain is the other’s loss: rock, paper, scissors, matching pennies, chess, a penalty kick. We write only the row player’s payoffs; the column player gets the negative (or, when the payoff is a probability of winning, one minus it). A cautious row player might ask: whatever I choose, what is the worst that can happen, and which mix makes that worst case as good as possible? That is the maxmin. The column player asks the mirror question, the minmax.

Von Neumann’s minimax theorem (1928) says the two are always equal once mixing is allowed. The row player can guarantee v, the column player can hold the row player to v, and the mixes that do it form a Nash equilibrium. In zero-sum games, playing it safe and playing the equilibrium are the same thing. Sometimes no mixing is needed: if some cell is the smallest in its row and the largest in its column, it is a saddle point and its payoff is the value.

A penalty kick in soccer is a small zero-sum game. The kicker shoots to his natural side (for a right-footer, the goalkeeper’s right) or the other side; the keeper must dive before he sees the ball. The probabilities below are illustrative, but they have the shape studies report: most penalties go in, and a keeper who guesses right saves many of them.

What the data say. Pierre-André Chiappori, Steven Levitt and Timothy Groseclose (American Economic Review, 2002) studied 459 penalty kicks from the top French and Italian leagues, and Ignacio Palacios-Huerta (Review of Economic Studies, 2003) studied a larger sample of professional kicks. Both found that the patterns fit minimax remarkably well: kickers scored at about the same rate whichever side they chose, and keepers saved about the same share whichever way they dove, which is exactly the indifference that equilibrium predicts. Palacios-Huerta also found that professionals’ choices were close to serially independent: they did not fall into the patterns that the Reader feeds on. Mark Walker and John Wooders (2001) found similar results for where top players serve at Wimbledon, though servers switched sides a little too often to be truly random.

What does it mean to mix?

Penalty takers and poker players randomize on purpose. But firms don’t roll dice to set prices, so what does a mixed equilibrium mean there? Game theorists offer three readings.

A short history

The French mathematician Émile Borel wrote about randomized strategies in a series of notes from 1921 to 1927 and solved small cases, but doubted that a general minimax result held. John von Neumann proved it in “Zur Theorie der Gesellschaftsspiele” (1928). With Oskar Morgenstern he built the expected-utility foundations in 1944. John Nash extended equilibrium in mixed strategies to all finite games in 1950. John Harsanyi explained in 1973 why mixed equilibria make sense even when nobody flips coins.

The field tests came much later. Mark Walker and John Wooders’ study of Wimbledon serves (2001), and the penalty-kick studies of Chiappori, Levitt and Groseclose (2002) and Palacios-Huerta (2003), showed professionals behaving much as minimax predicts.

Where you see it

• Sports: penalty kicks, tennis serves, pitch selection in baseball, run or pass in football, which way to go on a fast break. The best players are hard to read, not because they never favor anything, but because they keep opponents indifferent.
• Business: stores run sales at irregular times. Hal Varian’s “A model of sales” (American Economic Review, 1980) explains this as a mixed strategy: if a store’s discount days were predictable, rivals could undercut it on exactly those days. Audits, mystery shoppers and quality inspections are randomized for the same reason as in the inspection game.
• Security: airport screening, patrol routes and ticket inspections on trains are randomized so that they can’t be timed. Some agencies use game-theory software to choose the mix.
• Daily life: a parent who checks homework on random days, a poker player who sometimes bluffs, a cat that hunts in different places. Predictability is an invitation to be exploited.

Nothing here is financial or investment advice.

Practice

1. A first mixed equilibrium. Find the mixed equilibrium of this game (it has no pure one; see Chapter 3, Practice 2).

   	Column
   Row	Left	Right
   Up	5, 1	1, 4
   Down	4, 3	2, 2

   Show the answer

   Column indifferent: 1 · p + 3(1 − p) = 4p + 2(1 − p), so 3 − 2p = 2 + 2p and p* = 1/4 (Row plays Up 1/4 of the time). Row indifferent: 5q + (1 − q) = 4q + 2(1 − q), so 1 + 4q = 2 + 2q and q* = 1/2. Row’s expected payoff is 1 + 4 × 1/2 = 3, Column’s is 3 − 2 × 1/4 = 2.5. Check it with “Up or down” in the lab above.

2. Chicken, mixed. In Chicken (Swerve–Swerve 2, 2; Swerve–Straight 1, 3; Straight–Swerve 3, 1; Straight–Straight 0, 0), find the mixed equilibrium, each player’s expected payoff, and the probability of a crash.

   Show the answer

   If the other swerves with probability q: Swerve pays 2q + (1 − q) = 1 + q, Straight pays 3q. Equal at q = 1/2. By symmetry each swerves with probability 1/2. Each expects 1 + 1/2 = 1.5, and they crash (both go straight) with probability 1/4.

3. Rock, paper, scissors with a bonus. Suppose a win with Rock pays 2 instead of 1 (losses still cost 1, the game stays zero-sum: the loser pays the winner). Without solving fully, which move should the opponent play more often in equilibrium: the one that beats Rock, or the one that Rock beats?

   Show the answer

   Rock got better for you, so to keep you indifferent the opponent must make Rock less attractive: play more Paper (which beats Rock) and less Scissors (which Rock beats). Solving it: against the mix (r, p, s), Rock pays 2s − p, Paper r − s, Scissors p − 2r. The game is symmetric and zero-sum, so its value is 0 and all three must equal 0: p = 2s and r = s, giving Rock 1/4, Paper 1/2, Scissors 1/4 for both players. The twist: the move with the bonus, Rock, is itself played less than before.

4. A saddle point. In this zero-sum game (Row’s payoffs shown; Column pays them), find each player’s guaranteed payoff with pure strategies. Is there a saddle point?

   Row 1: 4, 2, 5    Row 2: 1, 0, 3   (columns 1, 2, 3)
   Show the answer

   Row 1’s worst case is 2; Row 2’s is 0; so Row can guarantee 2 by playing Row 1. Column’s worst cases (largest payment) are 4, 2 and 5 for the three columns, so Column can hold Row to 2 by playing column 2. The maxmin equals the minmax: the cell (Row 1, column 2), with payoff 2, is a saddle point and the value is 2. No mixing needed.

5. Minimax in a 2×3 game. Row’s payoffs: Row 1: 3, −1, 2; Row 2: −2, 4, 1. Find Row’s maxmin mix and the value.

   Show the answer

   If Row plays Row 1 with probability p, the three columns give 5p − 2, 4 − 5p and 1 + p. The lowest of these is highest where the first two cross: 5p − 2 = 4 − 5p, so p = 0.6, where both equal 1 (the third gives 1.6, so it doesn’t bind). The value is 1. Column’s minimax mix uses only the first two columns, half and half: 0.5 × 3 + 0.5 × (−1) = 1 = 0.5 × (−2) + 0.5 × 4.

6. The fine and the inspector. In the inspection game, the inspector’s cost of an inspection rises from 1 to 1.5 (inspecting a worker who works now pays −1.5). What happens to the cheating rate and to the inspection rate?

   Show the answer

   The inspection rate is set by the worker’s payoffs, which didn’t change: still 40%. The cheating rate is set by the inspector’s indifference: 2q − 1.5(1 − q) = −4q, so 7.5q = 1.5 and q* = 0.2. Costlier inspections mean more cheating (20% instead of 14%), not fewer inspections.

7. Why the indifference principle holds. Suppose in some equilibrium player 1 mixes actions T and B with positive probabilities, and against player 2’s strategy T pays more than B. Show that this can’t be an equilibrium.

   Show the answer

   Player 1’s expected payoff is a weighted average of the payoffs of the actions in the mix. Moving all of B’s probability onto T raises the average, because T pays strictly more and B had positive weight. So player 1 has a profitable deviation and the profile isn’t an equilibrium. Hence all actions used with positive probability must pay the same, and that common payoff must be at least that of any unused action.

How the interactives work

The Reader keeps counts of what you played next in each situation, for five theories: overall, after your last move, after your last two moves, after your last move and whether it won or lost, and after the Reader’s own last move. Each theory forecasts your next move from its counts (with half a count added to each move, so that new situations start near even). A theory’s score goes up by 1 when its most likely move is what you actually play and fades by 20% a round, so the Reader follows whichever theory has worked lately. It then plays the move with the highest expected payoff against that forecast. The Equilibrium bot draws each move with probability 1/3.

The indifference lab computes all equilibria of the 2×2 game exactly: the four pure profiles are checked as best responses, and the mixed one comes from the two indifference equations. Degenerate games, where a player is indifferent over a whole range, are reported as a continuum. The penalty lab uses the illustrative probabilities in the table; the “reads your kicks” keeper dives wherever your observed kicking frequency makes the kicker less likely to score.

Checks (node). Over 200 simulated matches of 60 rounds each, the Reader averaged a 59-point win against a player who always plays Rock, 54 points against a fixed cycle, 55 against a player who always plays what beats the Reader’s last move, and 54 against win-stay, lose-shift, with forecasts right 93% to 100% of the time. Against uniform random play its average result was a 0.3-point loss and its forecasts were right 33% of the time. Against the Equilibrium bot, “always Rock” averaged +0.6 over 300 matches of 60 rounds, close to the expected 0. In every named 2×2 game both players are exactly indifferent at the computed mixed equilibrium. In 500 random 2×2 zero-sum games, maxmin and minmax agreed to within 0.007 on a grid of 1,000 mixes, as von Neumann’s theorem says. In the penalty game the kicker’s minimax mix is 57.6% natural, the keeper’s 62.7% natural, and the value 79.3%.

Check yourself

1. In a mixed-strategy Nash equilibrium, a player who mixes between two actions …

   • gets a higher payoff from one of them
   • is choosing the mix that maximizes their own payoff, which is unique
   • gets the same expected payoff from both, given the other player’s strategy
   Show the answer

   That is the indifference principle. If one action paid more, the player would play it for sure.

2. In a 2×2 game, player 1’s equilibrium mix is determined by …

   • player 2’s payoffs, since it must make player 2 indifferent
   • player 1’s own payoffs
   • the sum of both players’ payoffs
   Show the answer

   Player 1 mixes to keep player 2 indifferent, so the formula for p* uses only u₂.

3. Against an opponent who plays rock, paper and scissors with probability 1/3 each, what is your expected score if you always play Rock?

   • Positive: you’ll win most rounds
   • Zero
   • Negative: always Rock is a bad strategy
   Show the answer

   You win 1/3, draw 1/3 and lose 1/3 of the time: 0. Against the equilibrium mix every strategy earns the same. Your predictability only costs you against an opponent who exploits it.

4. Von Neumann’s minimax theorem says that in a two-player zero-sum game with finitely many actions …

   • there is always a saddle point in pure strategies
   • the first player always wins
   • once mixing is allowed, the most the row player can guarantee equals the least the column player can hold them to
   Show the answer

   max min = min max = the value. Pure saddle points exist only sometimes, as matching pennies shows.

5. Studies of professional penalty kicks found that …

   • kickers always shoot to their natural side
   • scoring rates were about the same whichever side kickers chose, as minimax predicts
   • keepers who stay in the middle save most penalties
   Show the answer

   Equal success rates across sides are the signature of an equilibrium mix: if one side scored more often, kickers should go there more, and keepers would adjust.

Sources

• M. J. Osborne, An Introduction to Game Theory (Oxford University Press, 2004), chapter 4 (mixed strategy equilibrium) and chapter 11 (strictly competitive games and maxminimization).
• J. von Neumann, “Zur Theorie der Gesellschaftsspiele”, Mathematische Annalen 100, 1928, 295–320.
• P.-A. Chiappori, S. Levitt and T. Groseclose, “Testing mixed-strategy equilibria when players are heterogeneous: the case of penalty kicks in soccer”, American Economic Review 92(4), 2002, 1138–1151.
• I. Palacios-Huerta, “Professionals play minimax”, Review of Economic Studies 70(2), 2003, 395–415.
• M. Walker and J. Wooders, “Minimax play at Wimbledon”, American Economic Review 91(5), 2001, 1521–1538.
• K. Kovash and S. D. Levitt, “Professionals do not play minimax: evidence from Major League Baseball and the National Football League” (NBER Working Paper 15347, 2009; copy at UC Berkeley), for a summary of the field evidence and the 459-kick sample.
• H. R. Varian, “A model of sales”, American Economic Review 70(4), 1980, 651–659. G. Tsebelis, “The abuse of probability in political analysis: the Robinson Crusoe fallacy”, American Political Science Review 83(1), 1989, 77–91.
• J. C. Harsanyi, “Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points”, International Journal of Game Theory 2, 1973, 1–23.
• Ben Polak, Yale ECON 159, Lecture 9: Mixed Strategies in Theory and Tennis.