↑ ↓ to move · enter to open

026 · Game theory · Mixed Nash equilibrium, minimax

mixed strategies

Some games have no stable pure choice: whatever you settle on, the other side can punish it. The fix is to randomize with the right weights. In a zero-sum game the right weights are the ones that leave your opponent indifferent among the moves they use. John von Neumann proved in 1928 that this always works for two-player zero-sum games (the minimax theorem), and John Nash showed in 1950 that every finite game has an equilibrium once mixing is allowed.

LAB 1

rock, paper, scissors against a pattern hunter

The pattern bot counts what you threw after each recent sequence of your own moves, predicts your next throw from those counts and plays the best reply. The equilibrium bot throws each option with probability 1/3 and ignores you. Play a few rounds yourself, or autoplay 100 rounds as a scripted player. The first 120 rounds on the chart are a demo player that cycles rock, paper, scissors.

your net score
Opponent
Memory
Autoplay 100 rounds as

How to read this: the green line climbs when you win a round and drops when you lose, so above zero means you are ahead of the bot. The shaded background shows which bot you were facing in those rounds.

  • your wins minus losses
  • red background: vs pattern bot
  • gold background: vs equilibrium bot
—
You vs pattern bot · W–D–L
—
You vs equilibrium bot · W–D–L
—
Your overall mix
—
Best reply to your mix earns

The bot's model of youmemory 1

CodePython

Why only 1/3 each is safe

EV(Paper) = qR − qS EV(Scissors) = qP − qR EV(Rock) = qS − qP

If you throw rock, paper and scissors with probabilities qR, qP, qS, those are the bot's expected winnings per round for each reply. The three always add to zero, so unless all three are zero, at least one reply wins on average. They are all zero only at 1/3 each. The game's value is 0: neither side can guarantee more.

The mix also has to be fresh every round. The cycler throws each option exactly 1/3 of the time, yet a bot with memory 1 beats it almost every round, because each throw is predictable from the one before. Against the equilibrium bot every way of playing averages zero, including the cycler.

The pattern bot is predictable too. Its table is on screen: find the row it will use next and beat its reply. Compare 022 · Prisoner's dilemma, where a pure equilibrium exists and nobody needs to randomize.

LAB 2

the penalty kick, solved by indifference

A kicker picks a side and the keeper dives at the same moment. Each cell holds the kicker's scoring probability, and the keeper's payoff is one minus it, so the game is zero-sum. Edit any cell. The numbers in the presets are illustrative, chosen to show the effect; they are not measured data.

kicker's view
  • dotted vertical: the mix set by the slider (drawn in the other player's color)
  • gold dot: equilibrium (q* = the other side's best mix, then the scoring rate)
30%
Scoring probability · kicker first, keeper second
kicker's best reply to that divekeeper's best reply to that kickgold = both (pure equilibrium)dashed cells = average score against the other side's equilibrium mix
—
Kicker: P(kick left)
—
Keeper: P(dive left)
—
Scoring rate at equilibrium
—
Kicker's best reply at slider

Now

CodePython

Two indifference equations

keeper indifferent: p·sLL + (1−p)·sRL = p·sLR + (1−p)·sRR
kicker indifferent: q·sLL + (1−q)·sLR = q·sRL + (1−q)·sRR

Each player's mix comes from the other player's equation. The kicker's p is whatever makes the keeper's two dives equally good, and the keeper's q is whatever makes the kicker's two sides equally good. If either player could gain by switching, the other one's mix would be wrong.

On the chart, the kicker scores along the higher line, so the keeper wants the lowest point of that upper edge. That point is the crossing. This is von Neumann's minimax: the keeper's best worst case equals the kicker's best guaranteed rate. With a symmetric table both mixes are exactly 50/50. Ignacio Palacios-Huerta (2003) studied penalty kicks by professional players and found choices and scoring rates close to what the mixed equilibrium predicts.

LAB 3

three options and fictitious play

Add the center. Now each side mixes over three options and there is no closed form worth memorizing, so the page solves the game as a linear program with the simplex method. Then it runs fictitious play: each round, each side best-responds to the other's empirical frequencies so far. The triangles show those frequencies moving toward the solution. A point's distance from a corner falls as that option's share rises; the center of each triangle is 1/3 each.

fictitious play
  • + cross: 1/3 each
  • gold ring: the solution
Speed
Scoring probability · kicker first, keeper second · dashed = expected value at the LP solution
kicker's best reply to that divekeeper's best reply to that kickshaded row/column = fictitious play's current best replies
—
LP: kicker L · C · R
—
LP: keeper L · C · R
—
Value (scoring rate)
—
1/3 each?
—
Fictitious play · rounds
—
FP bounds on the value

Now

CodePython

The linear program

maximize Σ yj subject to Σj (sij+1)·yj ≤ 1 for every kick i, y ≥ 0
value = 1/Σy − 1, keeper's mix = y/Σy, kicker's mix = dual prices

Adding 1 to every cell keeps the entries positive and shifts the value by exactly 1. The keeper's mix and the kicker's mix come out of one simplex run: one as the primal solution and one as the dual. The Node tests for this page check the solver against brute-force support enumeration, which tries every pair of supports and solves the indifference equations on each.

A strategy gets zero weight when it does worse than the value against the opponent's mix; "Weak center" shows this. Exactly 1/3 each needs every row of the table to sum to the same total and every column too, and the symmetric preset is the simplest case. Fictitious play was proposed by George W. Brown in 1951, and Julia Robinson proved the same year that its frequencies converge to equilibrium in every two-player zero-sum game. The bounds tighten slowly: each side keeps overshooting, so the trail circles in toward the solution. For more on the randomness itself, see 006 · Probability.