Why does bluffing have to be random to work?
Topic 23 keeps one decision-maker but gives them several objectives that genuinely conflict, so “optimal” stops being a point and becomes a curve. Game theory (topics 11 to 15) drops the other assumption: when another party is also choosing in response to you, your best plan depends on theirs and there is no single answer to compute, only an equilibrium to find. It underwrites markets that clear through auctions, security proofs written as games between an adversary and a defender, and populations that settle into stable mixes of strategy.
Topic 11's Prisoner's Dilemma had a stable outcome. Matching Pennies has none, not because it is more complicated, but because it is zero-sum: every point one player gains, the other loses, exactly. That structure guarantees the two players' interests never align on a resting point.
Say A always plays heads. B, knowing this, always plays tails and wins forever. So A cannot commit to any single pure choice without being exploited: the only way to stop being predictable is to genuinely randomise, and the only randomisation an opponent cannot exploit is fifty-fifty. This is the honest reason poker players, penalty takers and cryptographers all reach for randomness on purpose: not for variety, but because any predictable rule is a rule your opponent can play against.
Von Neumann's minimax theorem (1928) (years before Nash generalised equilibrium to games where interests are not purely opposed) says every finite zero-sum game has a well-defined value: the amount the best defensive play guarantees you, whichever side you defend. Matching Pennies' value is exactly 0. Neither player can do better against a competent opponent, and neither has to accept doing worse.
For a finite two-player zero-sum game with payoff matrix M (to the row player; the column player receives −M), von Neumann's theorem states:
max over row strategies p min over column strategies q pᵀMq
=
min over column strategies q max over row strategies p pᵀMq
= v (the value of the game)
Guaranteeing yourself at least v by defending first, and guaranteeing your opponent no more than v by attacking first, land on the exact same number. There is no advantage to moving first or second once both play optimally.
This is topic 03, again. Finding a zero-sum game's optimal mixed strategy is a linear program (maximise the guaranteed value subject to the strategy being a valid probability distribution) and von Neumann's minimax theorem is exactly LP strong duality applied to that program: the row player's LP and the column player's LP are duals of each other, and strong duality is precisely the claim that their optimal values coincide. Dantzig, who built the simplex method, credited conversations with von Neumann for recognising the connection. Two fields that look unrelated turn out to share a proof.
Solved on the figure's own game: by symmetry the value is 0, achieved at p = q = (½, ½). Perturb either player off one-half in either direction and the opponent has a pure best response that beats 0, which is exactly why one-half is the unique equilibrium, not merely a reasonable choice.
Penalty kicks, tested on real data A striker and goalkeeper choosing sides simultaneously is Matching Pennies with unequal payoffs. Chiappori, Levitt & Groseclose (American Economic Review 92(4), 1138–1151 (2002)) tested professional penalty-kick data against the mixed-strategy prediction and found it a good fit: real, high-stakes, adversarial behaviour matching what the theorem says a genuinely unexploitable strategy must look like.
And in security proofs Modern cryptography, including the post-quantum schemes covered on this site's PQC pages, states its guarantees as a game between a challenger and an adversary: the scheme is secure if no adversary's winning probability can be pushed above a negligible bound, whatever strategy they run. It is the same minimax vocabulary: the defender wants to minimise the adversary's advantage, the adversary wants to maximise it: used in earnest rather than for sport.
Check yourself
In Matching Pennies, why must the equilibrium strategy be random?
The game has no pure equilibrium: from every cell someone wants to move. The only equilibrium is each player choosing heads or tails with probability exactly one half.