Nobody sits down and solves for a mixed equilibrium before playing. They watch what worked, adjust, and watch again. Remarkably, that simple habit can drag a whole population to the equilibrium a theorist would have computed, without anyone doing the math.
Learning in games
Equilibrium is usually justified by assuming players are hyper-rational. Learning offers a humbler story: players track what opponents have done and best-respond to the record. In zero-sum and potential games, this fictitious play converges, and no-regret learning reaches equilibrium concepts more generally.
The mixed equilibrium of Matching Pennies has each player choosing...
A best response is optimal given a belief about...
Predict, then play
Play Matching Pennies against a bot that learns by fictitious play: it tracks how often you play Heads and best-responds to that record. Try to beat it.
Why did that happen?
Take a guess, then reveal the reason
The bot is not clever, just observant: it counts your moves and flees the one you favour. So any lean you develop gets exploited, and the only long-run frequency it cannot exploit is an even mix. In this game only the bot is using fictitious play; your frequency depends on the choices you make. The two-player convergence result below concerns a separate model in which both players update this way.
The math
In fictitious play, each player forms a belief equal to the empirical frequency of the opponent’s past moves and best-responds to it. In zero-sum games and in potential games, the empirical frequencies of play converge to a Nash equilibrium. No-regret learning is more general: if each player’s average regret for not having played any fixed action goes to zero, the empirical joint distribution converges to the set of coarse correlated equilibria. Hart and Mas-Colell’s regret matching meets the stronger no-swap-regret condition, and its empirical distribution converges to the set of correlated equilibria.
In Matching Pennies the matcher wants to match, the mismatcher to differ. Each best-responds to the other’s running Heads frequency. The per-round beliefs cycle, but the time-average of each player’s own play converges to , the mixed equilibrium. So a player who never heard of mixed strategies nonetheless plays one on average.
Fictitious play does not converge in every game (it can cycle in some), but it does in the two big classes above. No-regret dynamics guarantee, in any game, average play within of the best fixed action over rounds with actions, which pins the long-run behaviour to equilibrium sets even when full convergence fails.
Work it out
Why an even mix is the only safe play
Suppose you have played Heads 6 times and Tails 4. The bot believes you play Heads with frequency and, as the mismatcher, plays Tails to avoid you, so you lose when you play Heads. Lean the other way and it flips to Heads. Any imbalance in your record hands the bot a profitable response.
The only frequency it cannot exploit is : at an even, patternless mix, its Heads and Tails responses both break even against you. If you generate that mix, the bot’s empirical belief converges to it. The interactive does not simulate both players learning, so it demonstrates the best-response pressure behind the theorem rather than the theorem’s full two-sided dynamics.
Key idea
Simple learners who best-respond to the past can converge on equilibrium without computing it: fictitious play reaches Nash in zero-sum and potential games, and regret matching reaches correlated equilibrium in any game.
Check yourself
Sources
- Brown, G. W. (1951). Iterative solution of games by fictitious play. In Activity Analysis of Production and Allocation. Wiley.
- Hart, S., and Mas-Colell, A. (2000). A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5), 1127-1150.