Fictitious play and empirical mixtures

What you will learn

Derive count-based fictitious-play updates, separate complete tied response sets from tie selection, quantify seed-strength inertia and certify nonmonotone empirical checkpoints without confusing finite accuracy with asymptotic convergence.

Prerequisites: Best-response dynamics and cycles · Mixed supports and saddle certificates · Best responses

Beliefs are accumulated counts, not the latest move

Fictitious play replaces a last-action response with a response to an empirical distribution. Assume a fixed, fully known, finite two-player zero-sum stage game. Row maximizes net chips and Column minimizes that same transfer. Actions are simultaneous, all past actions are observed, payoffs are linear in mixed strategies, and there are no fees, hidden types, changing matrices or discounted objectives. These are algorithmic assumptions for a small solver, not a claim that poker opponents follow this rule. Each new response uses the counts available before either player appends the current action.

Our original matrix has rows A=(3,−1), B=(−2,2), C=(0,1), with columns L,R. Maintain row counts (a,b,c) and column counts (l,r). Each side starts with five fictitious observations. They initialize beliefs and need not come from paired games. Initially use (1,1,3) and (2,3). After t actual updates each total is n=5+t. The empirical row mixture is (a,b,c)/n and the column mixture is (l,r)/n. The seed contributes to these denominators even though it is not a record of realized joint payoffs.

Keeping only the newest pair loses the sufficient information for this update rule. For example, two histories can both end A,L while their column counts are (3,2) and (1,4). Row then faces q=3/5 and q=1/5 on L, respectively. The first makes A best; the second makes B best. Conversely, histories with identical marginal counts produce identical next response sets even if their chronological order differs. This compression is valid only because the stipulated rule reads cumulative marginal frequencies, not recency, joint pairing or conditional responses.

Construct every cumulative best response before resolving ties

Given column counts (l,r), multiply every row by those counts. The three cumulative scores are S_A=3l−r, S_B=−2l+2r and S_C=r. Dividing each by the same positive n gives expected payoffs, so maximizing the integers gives exactly the same response set. Against row counts, the two column scores are T_L=3a−2b and T_R=−a+2b+c. Column selects all minima because its own gain is the negative of Row’s transfer. Integer score comparisons avoid rounding a true equality into an invented strict preference.

At the five-observation seed, row scores are (3,2,3) and column scores are (1,4). Thus Row’s entire best-response set is {A,C}; Column’s is {L}. There is no requirement that an action with a zero current count be excluded from a response set. Counts summarize beliefs, whereas all legal actions remain candidates. Nor does the presence of C in the row tie mean that Row must actually randomize between A and C. A deterministic tie convention can choose either pure action while preserving the definition of fictitious play.

The workshop first asks for the complete sets and only then applies the selected first or last alphabetical convention. First chooses A,L at this seed; last chooses C,L. This separates a mathematical set-valued response from an implementation’s choice inside that set. A missing tied action is a faulty set construction even when the submitted single action would be a permissible play. Both players’ sets must be calculated from the old counts: updating Row’s count before choosing Column would instead define an alternating variant.

Derive the shrinking update and the effect of fictitious history

Let x be a current empirical vector with n total observations and let e_i put all mass on the newly appended action i. The next vector is x′=(nx+e_i)/(n+1)=x+(e_i−x)/(n+1). Every coordinate remains nonnegative and the coordinates still sum to one. The weight of the new observation is α=1/(n+1), while all old mass receives weight n/(n+1). This is neither replacing the current distribution with the response nor averaging two distributions with equal weight. A frequently repeated action can move its frequency only a little when the historical count is large.

With first tie resolution, append A,L to the seed. Row counts become (2,1,3), giving x_A′=2/6=1/3; Column counts become (3,3), giving q′=1/2. Independently use the vector update: 1/5+(1−1/5)/6=1/3 and 2/5+(1−2/5)/6=1/2. The increments are 2/15 and 1/10. At the next step, α becomes 1/7. Thus the denominator changes after every observation, even if the same pure pair is appended twice.

Double only the seed counts to (2,2,6) and (4,6). The current mixtures and response sets remain identical, because every score doubles. Appending the same A,L now gives A frequency 3/11 and L frequency 5/11. A seed therefore has both a composition and a strength. Equal normalized beliefs do not imply equal next beliefs under a one-record update unless their total weights also match. The seeds are fixed finite initialization, so their fraction of total mass is n₀/(n₀+t), which tends to zero; this algebra alone supplies no finite-time accuracy rate for the game solver.

Use a finite certificate without demanding monotone improvement

At any checkpoint define G=min(T_L,T_R)/n and H=max(S_A,S_B,S_C)/n. If the empirical row mixture is used against any independent column mixture it guarantees at least G. If the empirical column mixture is used against any independent row mixture it permits at most H. For their product payoff u, G≤u≤H. Therefore the two unilateral gains sum to (H−u)+(u−G)=H−G. This is a finite certificate for the current marginal pair. Set an inclusive stopping tolerance ε in chips and accept that pair when H−G≤ε.

Initially G=1/5 and H=3/5, so the gap is 2/5. After first-rule A,L, the new row scores are (6,0,3), column scores are (4,3) and n=6. Hence G=1/2, H=1 and gap=1/2. The gap increased, despite both appended actions being exact best responses to their respective old empirical beliefs. A tolerance of one half accepts both checkpoints; a tolerance of one quarter accepts neither. Passing once does not prove every later checkpoint passes. With last-rule C,L instead, the gap becomes 5/6, showing an additional finite-path sensitivity to a legitimate tie choice.

Continue the first-rule path once more. Against column counts (3,3), A is uniquely best; against row counts (2,1,3), R is uniquely minimizing. Append A,R to obtain row counts (3,1,3) and column counts (3,4). Scores are now (5,2,4) and (7,2), with n=7. The interval is [2/7,5/7] and the gap is 3/7. This up-then-down witness refutes a monotone-gap assertion. The correct audit recalculates the full extrema rather than treating the most recently chosen actions as automatically optimal against the newly updated beliefs.

State the convergence claim at the correct level

The institutional sources describe fictitious play as history-based belief learning and state the zero-sum time-average convergence result. In a fixed finite two-player zero-sum game, exact fictitious-play empirical strategies approach equilibrium in the relevant asymptotic sense. This lesson does not prove that theorem or claim a particular convergence rate. Our finite workshop establishes its count recurrence and current bounds directly. Pure responses can keep changing even while empirical strategies improve asymptotically; a deterministic next response is not a fresh draw from the empirical mixture.

For an independent target check in our matrix, take row mixture (1/5,0,4/5) and column mixture (2/5,3/5). Both column values are 3/5. The three row values are (3/5,2/5,3/5), so the maximum is also 3/5. This gives a zero-gap certificate without relying on any simulated trajectory. It does not assert that a finite count path lands there exactly, or that B’s positive seed count can become zero after finitely many append-only updates. A seed count can remain positive while its normalized weight tends to zero.

In the activity, move conserved seed tickets to change composition, double their strength to preserve composition, construct all tied responses and retain certificates from different checkpoints. Changing a seed or tie convention restarts the trajectory and invalidates inputs; appending an update also clears the old audit. Saved certificates identify their seeds, rule and count state and remain visit-local. Report an accepted empirical pair and tolerance explicitly. Neither a smooth-looking trace, a small observation weight nor one correct next response establishes the required payoff guarantee. The finite certificate, the asymptotic theorem and the model’s suitability for a real decision are separate claims.

Hands-on: Construct empirical response sets

Transfer fictitious observation tickets, vary seed strength and tie resolution, append complete cumulative response sets and retain finite stopping certificates.

Common mistakes

• Responding only to the latest pair or counting fictitious observations as realized joint outcomes.
• Selecting one tied action when asked to construct the whole response set.
• Using new row counts for Column in the simultaneous algorithm.
• Dropping seed mass from the denominator or using 1/n as the next observation weight.
• Inferring monotonicity, a pure-action equilibrium or a convergence rate from one passing empirical checkpoint.

Keep these ideas

• Normalize cumulative counts, including fixed fictitious history.
• Construct all maximizing and minimizing actions before resolving ties.
• One observation moves a mixture by (response−mixture)/(n+1).
• Scaling seeds preserves current beliefs but changes update inertia.
• Audit current bounds and inclusive tolerance separately from an asymptotic theorem.

Further reading

• MIT 6.254 Lecture 11: Fictitious play, slides 3–6, 10–16 ↗

  Read count initialization, normalized beliefs, set-valued pure responses, empirical-update formula, time-average definition and zero-sum convergence statement. The asymptotic result is stated, not proved here; no rate or monotone discrete gap is imported. Original three-by-two matrix, seed-strength comparison, tie branches, exact arithmetic and diagnostics. No quotation, source exercise or video reused. Checked 2026-10-25.

• CMU 15-888: Fictitious play, slides 13–14 ↗

  Read response-to-average definition, zero-sum convergence context, rate caution and predictability question on PDF pages 12–13. Text was accessible; screenshot retrieval failed. Used to scope claims, not as proof of our discrete recurrence. Our count workshop and nonmonotone checkpoint example are original. No video reviewed. Checked 2026-10-25.