Best-response dynamics and cycles

What you will learn

Derive simultaneous and Row-first best-response trajectories, construct a persistent cycle whose empirical marginals are exploitable, and distinguish observed joint-history payoffs from independently resampled average-strategy payoffs.

Prerequisites: Mixed supports and saddle certificates · Linear programs and dual game values · Best responses

Specify a clock before calling a response an improvement

A best response solves a static problem against a specified opponent strategy. Repeatedly computing such responses adds a new object: an update rule. Its timing is part of the mathematics. Assume a known, finite, two-player zero-sum stage game with linear net chip payoffs. Row maximizes the displayed transfer and Column minimizes it. There are no fees, private types, discounting, changing payoffs or uncertainty about observed past actions. We study a deterministic calculation over pure action profiles, not a behavioral prediction about poker players and not an equilibrium strategy for a repeated game with punishments.

Our original asymmetric transfer matrix has rows A=(4,−2), B=(−1,3), with columns L,R. A profile names one row and one column. Against L, Row chooses A because four exceeds minus one. Against R, Row chooses B because three exceeds minus two. Against A, Column chooses R because minus two is smaller than four. Against B, Column chooses L because minus one is smaller than three. Every relevant pure response is strict, so no hidden tie-breaking convention determines the trajectories below.

Under the simultaneous clock, both players replace their action with a best response to the OLD opponent action. Neither sees the other replacement first. Under the Row-first clock, Row responds to the old column and then Column responds to the NEW row. One completed update records the resulting pair after both replacements. We exclude the seed from all empirical counts. Intermediate Row-first pairs are deliberately not sampled. Including them would define a different observation clock and a different joint distribution.

Derive a cycle and explain why local improvement does not accumulate

Start at (A,L). Simultaneous replacement gives (A,R): Row keeps A against the old L while Column switches to R against the old A. From (A,R), Row changes to B but Column still responds to old A with R, yielding (B,R). From there both responses yield (B,L), then (A,L). Thus the four completed profiles are (A,R), (B,R), (B,L), (A,L), after which the same deterministic state recurs. Because the entire next state depends only on the current pair, returning to the same pair proves exact repetition forever under this unchanged rule. It is stronger evidence than merely seeing similar payoffs twice.

The four recorded Row payoffs are −2,3,−1,4. They do not improve monotonically. A unilateral best response would improve or preserve its owner’s payoff if the opponent remained fixed, but simultaneous replacements change that reference. Zero-sum players also disagree about which direction counts as improvement. There is no common increasing objective supplied by this rule. Each pure profile has a profitable deviation by someone, so every latest-profile two-sided gap remains positive. Existence of a mixed equilibrium does not make this pure update rule settle at that equilibrium.

Now run the Row-first clock from the same seed. Row keeps A and Column chooses R, giving (A,R). Next Row chooses B and Column immediately answers B with L, giving (B,L). These two completed profiles repeat. The unrecorded intermediate (B,R) is not the second completed update. This two-state loop differs from the four-state loop even though both use exactly the same payoff matrix and pure response maps. An implementation that accidentally uses the new row in a supposedly simultaneous update has changed the algorithm, not merely optimized its code.

Audit empirical marginals instead of trusting a balanced-looking history

After four simultaneous completed updates, each of the four joint cells occurs once. Row’s empirical A frequency p is 1/2 and Column’s empirical L frequency q is 1/2. Those frequencies describe a time summary. They are not a statement that either player independently tossed a fair coin at each stage, nor that the deterministic next move is unpredictable. To test the static strategy pair formed from these marginals, evaluate all deviations against the averages rather than averaging the latest-profile gaps.

Against a Column mixture q, pure A earns 6q−2 and pure B earns 3−4q. Against a Row mixture p, choosing L gives Row 5p−1 while choosing R gives Row 3−5p. Define H(q)=max(6q−2,3−4q) and G(p)=min(5p−1,3−5p). The two-sided gap H−G is nonnegative and equals the sum of the players’ unilateral improvement opportunities from their independent product profile. At p=q=1/2, row values are (1,1), column values are (3/2,1/2), hence H=1, G=1/2 and gap=1/2. Balanced action counts therefore fail the equilibrium audit.

Independently derive the true equilibrium by equalizing the two column values: 5p−1=3−5p gives p=2/5. Equalizing the row values gives 6q−2=3−4q, hence q=1/2. Both bounds then equal one. A cell-level check uses joint probabilities (1/5,1/5,3/10,3/10): 4/5−2/5−3/10+9/10=1. This reconciles the value without relying on the indifference equations alone. The cycling pure rule visits A half the time instead of two fifths. More repetitions of the complete loop cannot repair that discrepancy.

Separate a joint history from independent resampling

For any nonempty completed history of length n, let cAL,cAR,cBL,cBR be its four joint counts. The observed mean transfer is (4cAL−2cAR−cBL+3cBR)/n. Set a=cAL+cAR and l=cAL+cBL. Independent resampling instead chooses a row from the row history and a column from the column history using separate random draws. Its expected transfer is [4al−2a(n−l)−(n−a)l+3(n−a)(n−l)]/n². The denominator is n squared because there are n choices of a row record and n independent choices of a column record. Pairing only records from the same time index computes the first experiment.

After four Row-first updates, the counts are (0,2,2,0). Observed mean is (−4−2)/4=−3/2. Marginals are still p=q=1/2, so independent product payoff is one and the average-strategy gap remains 1/2. The product gives positive mass to (A,L) and (B,R), although neither occurs in the recorded completed history. This is not an arithmetic contradiction. Dependence across players at the sampled times changes the joint law while preserving its marginals. The difference between observed and product payoffs is −5/2 here.

At the four-update simultaneous checkpoint the joint counts happen to factor, and both means equal one. That equality does not prove the marginal pair is equilibrium: Column can still lower Row’s independent payoff from one to one half. Conversely, a difference between observed and product means alone does not establish how exploitable the marginal strategies are. One number describes realized pairings, another describes a counterfactual resampling experiment, and the deviation gap tests unilateral incentives. Keep all three labels in a solver report.

Stress the payoff and state exactly what was established

Change only the A,L transfer from four to eight. Every strict pure response above remains the same, so both deterministic cycles and their action counts persist. For the general first transfer k in this two-setting workshop, L pays (k+1)p−1 and R pays 3−5p; A earns (k+2)q−2 and B earns 3−4q. Equalization gives p=4/(k+6), q=5/(k+6) and value (3k−2)/(k+6). At k=8, these are 2/7,5/14 and 11/7. Substitution checks both row values and both column values at 11/7. Identical action traces across two matrices therefore need not imply identical equilibrium strategies or values.

At the balanced four-update checkpoint with k=8, the independent product payoff is two. The column values are (7/2,1/2) and the row values are (3,1), giving gap 5/2. The simultaneous observed mean is two; Row-first remains −3/2 because neither recorded cell uses the changed payoff. This sensitivity construction distinguishes a dynamically unchanged response map from a quantitatively changed static error. The activity asks you to build and retain both histories, then change k and repair your arithmetic. Every model change restarts counts; every update invalidates the previous inputs and feedback.

A finite checkpoint certifies its counts and calculated static gap, not asymptotic convergence. In our last-action dynamics, exact state recurrence plus the deterministic update formula proves perpetual cycling; the balanced full-cycle marginal error is persistent. Fictitious play is a different rule that responds to accumulated empirical opponent frequencies rather than only the latest opponent action. Its results cannot be borrowed for this experiment. Likewise, a deterministic public cycle can be exploited by someone conditioning on time or history, even if its marginal summary were an equilibrium mixture. The static gap here permits a fixed independent deviation against the marginal pair, not a history-dependent repeated-game strategy. Choose the guarantee you need before choosing a stopping criterion.

Hands-on: Construct a response-clock history

Predict completed best responses, compare two update clocks and build joint versus product payoff certificates under a payoff perturbation.

Common mistakes

• Using a newly updated row in a simultaneous response calculation.
• Counting the seed or intermediate pairs without changing the declared sampling clock.
• Equating a deterministic frequency table with independent randomization.
• Calling a matching product payoff proof of equilibrium.
• Treating a finite history or another algorithm’s theorem as a convergence proof.

Keep these ideas

• Specify whose action is visible at each update.
• A strict local response can belong to a persistent cycle.
• Audit marginal strategies with all pure deviations.
• Observed joint means and independent product means answer different experiments.
• Recurrence proves this deterministic loop; a finite numerical checkpoint alone proves no general convergence claim.

Further reading

• CMU 15-888: Equilibrium Computation, slides 10–14 ↗

  Read slides 10–14 on iterative best responses, failure to settle, averages and the distinction from fictitious play. PDF text was readable; screenshot retrieval failed. Original asymmetric two-action matrix, clock comparison, recurrence proof, sensitivity, joint/product derivations and checks are ours. No source numerical example, quotation or video reused. Checked 2026-10-25.

• MIT 6.254 Lecture 11: Learning in Games, slides 3–6 and 9–16 ↗

  Read history-based beliefs and pure responses (slides 3–6), pure versus time-average convergence and conditional zero-sum result (slides 9–16); visually checked PDF pages 5 and 11. Supports terminology and distinction from last-action rules only. We do not import its example or prove the fictitious-play theorem here. Our histories, arithmetic and activity are original; no video reviewed. Checked 2026-10-25.