Matching Pennies has no pure Nash equilibrium: any deterministic play can be exploited. The way out, foreshadowed by the practice of every poker player and penalty-kick taker, is to randomize.
Mixed strategies and expected payoffs
Mixed strategymixedstrategy A mixed strategy for player \(i\) is a probability distribution \(\sigma_i \in \Delta(A_i)\) over her pure actions. The support of \(\sigma_i\), written \(\supp(\sigma_i)\), is the set of actions played with positive probability. A profile \(\sigma = (\sigma_1, \dots, \sigma_n)\) induces, via independent randomization, expected payoffs \[u_i(\sigma) \;=\; \sum_{a \in A} \Big( \prod_{j \in N} \sigma_j(a_j) \Big)\, u_i(a).\]
By Theorem [thm:vnm] (expected utility), players evaluate mixed profiles by these expectations. A mixed-strategy Nash equilibrium is defined exactly as before: \(\sigma^*\) such that \(u_i(\sigma_i^*, \sigma_{-i}^*) \ge u_i(\sigma_i, \sigma_{-i}^*)\) for every player \(i\) and every mixed strategy \(\sigma_i\).
The indifference principle
The single most useful tool for computing mixed equilibria:
Indifference principleindifference \(\sigma^*\) is a Nash equilibrium if and only if, for every player \(i\):
every action in \(\supp(\sigma_i^*)\) yields the same expected payoff against \(\sigma_{-i}^*\); and
no action outside the support yields a higher expected payoff against \(\sigma_{-i}^*\).
Proof. If some action in the support were worse than another, shifting its probability to the better action would raise \(u_i\)—contradicting equilibrium. Conversely, if all support actions are equally good and no outside action is better, every mixture over the support is a best response, including \(\sigma_i^*\) itself. ◻
In equilibrium, a player’s mixing probabilities are determined by the requirement of keeping the other player indifferent—not herself well-off. This is counterintuitive and powerful: your equilibrium mixture depends on your opponent’s payoffs, not your own.
Matching Pennies solvedmpsolved Let player 1 play \(H\) with probability \(p\) and player 2 play \(H\) with probability \(q\). Player 1 is willing to mix only if \(H\) and \(T\) give her equal expected payoffs: \[\underbrace{q(1) + (1-q)(-1)}_{u_1(H)} = \underbrace{q(-1) + (1-q)(1)}_{u_1(T)} \implies 2q - 1 = 1 - 2q \implies q = \tfrac12 .\] Symmetrically \(p = \tfrac12\). The unique equilibrium is both mixing 50–50, with value \(0\) each.
Battle of the Sexes: the mixed equilibriumbosmixed In Example [exa:bos], besides the two pure equilibria there is a mixed one. Let row play \(B\) with probability \(p\); column mixes only if indifferent: \(u_2(B) = p \cdot 1\), \(u_2(F) = (1-p)\cdot 3\), so \(p = \tfrac34\). Symmetrically column plays \(B\) with probability \(q = \tfrac14\). Expected payoffs are \(\tfrac34\) each—worse for both than either pure equilibrium (\(3\) and \(1\)): the players miscoordinate with probability \(1 - \left(\tfrac34\cdot\tfrac14 + \tfrac14\cdot\tfrac34\right) = \tfrac{5}{8}\).
Hawk–Dove and mixing in populationshawkdove
| Hawk | Dove | |
|---|---|---|
| Hawk | \(\tfrac{V-C}{2}, \tfrac{V-C}{2}\) | \(V, 0\) |
| Dove | \(0, V\) | \(\tfrac{V}{2}, \tfrac{V}{2}\) |
Two animals contest a resource of value \(V\); fighting costs \(C > V\). The symmetric mixed equilibrium has each playing Hawk with probability \(p^* = V/C\). In biology this is reinterpreted: a stable population contains a fraction \(V/C\) of aggressive types. This reinterpretation of mixed equilibrium as population frequencies is the gateway to evolutionary game theory (Chapter [ch:evolutionary]).
Interpreting mixed strategies
Do people literally roll dice? Four standard interpretations:
Deliberate randomization: in strictly competitive settings (poker bluffs, soccer penalties, tax audits, military tactics), unpredictability is genuinely valuable and players consciously randomize.
Population frequencies: the mixture describes proportions of a population playing each pure action (Example [exa:hawkdove]).
Beliefs: \(\sigma_i\) is not what \(i\) does but what others believe \(i\) will do; equilibrium is a consistency condition on beliefs.
Purification (Harsanyi 1973): each player has tiny private payoff perturbations and plays a pure best response to her realized type; to outsiders this looks exactly like the mixed equilibrium. The mixed equilibrium is the limit of pure equilibria of nearby incomplete-information games.
Professional soccer penalty kicks are a celebrated test: kickers and goalkeepers choose sides with frequencies closely matching the mixed equilibrium computed from scoring rates, and their choices are serially independent, as theory requires (Palacios-Huerta 2003). Novices in labs, by contrast, alternate too much—true randomness is hard for humans.
Computing equilibria in larger games
For \(2 \times n\) and small games, a practical algorithm:
Find all pure equilibria by best-response marking.
For each candidate support profile (subset of actions for each player), impose indifference within supports, solve the linear equations, and check: probabilities in \([0,1]\), and no profitable deviation outside the support.
The number of support profiles grows exponentially—a first hint that computing Nash equilibria is genuinely hard (formalized in Chapter [ch:algorithmic]).
A \(2\times 3\) gametwobythree
| \(L\) | \(M\) | \(R\) | |
|---|---|---|---|
| \(T\) | \(2,2\) | \(0,3\) | \(1,0\) |
| \(B\) | \(1,0\) | \(2,1\) | \(0,2\) |
No pure equilibrium (check by marking). Suppose player 1 mixes \(pT + (1-p)B\) with \(p \in (0,1)\). Player 2’s expected payoffs: \(u_2(L) = 2p\), \(u_2(M) = 3p + (1-p) = 2p+1\), \(u_2(R) = 2(1-p)\). Since \(u_2(M) > u_2(L)\) always, \(L\) is never in player 2’s best responses when 1 mixes; try support \(\{M, R\}\): indifference \(2p + 1 = 2 - 2p\) gives \(p = \tfrac14\). Player 1’s indifference between \(T\) and \(B\) against \(qM + (1-q)R\): \(0 \cdot q + 1(1-q) = 2q + 0(1-q)\), so \(q = \tfrac13\). Check deviations: player 2’s payoff from \(L\) is \(2p = \tfrac12 < u_2(M) = \tfrac32\). Equilibrium: \(\sigma_1 = (\tfrac14, \tfrac34)\), \(\sigma_2 = (0, \tfrac13, \tfrac23)\).
Oddness (Wilson 1971)oddness Almost every finite game (all games outside a closed set of measure zero in payoff space) has a finite and odd number of Nash equilibria.
This explains a pattern you may have noticed: Battle of the Sexes has \(2\) pure \(+ 1\) mixed \(= 3\); coordination games likewise; Matching Pennies has exactly \(1\).
Exercises
Penalty kickspenalty A kicker chooses Left or Right; so does the goalkeeper. Scoring probabilities for the kicker: \(0.6\) if both choose the same side (keeper guesses right), \(0.95\) if kicker goes Left and keeper Right, \(0.9\) if kicker Right and keeper Left. Model as a zero-sum game (kicker maximizes scoring probability), find the mixed equilibrium, and compute the equilibrium scoring probability.
Rock–Paper–Scissorsrps Show that uniform randomization by both players is the unique Nash equilibrium of Rock–Paper–Scissors (win \(=1\), loss \(=-1\), tie \(=0\)). Then modify the game so a win with Rock pays \(2\) instead of \(1\) (for both players’ Rock wins) and recompute the equilibrium. Which action’s probability falls? Explain the intuition.
Volunteer’s dilemmavolunteer Each of \(n\) neighbors can call the police (cost \(c\)) or not. If at least one calls, every neighbor gets benefit \(v > c\); if nobody calls, all get \(0\). Find the symmetric mixed equilibrium probability of calling, and show that the probability that nobody calls increases with \(n\). Discuss the connection to the bystander effect.
Support checkingsupport
| \(L\) | \(R\) | |
|---|---|---|
| \(T\) | \(6,2\) | \(0,6\) |
| \(M\) | \(2,4\) | \(4,2\) |
| \(B\) | \(3,3\) | \(3,3\) |
Find all Nash equilibria (pure and mixed), checking every possible support profile for player 1.