PaperlayerView exact revision on arXiv

Source-linked AI summary

Arbitrarily Slow Polynomial Convergence of Fictitious Play

Jacob Abernethy, John Lazarsfeld, Andre Wibisono

arXiv:2610.08768v1cs.GT

TL;DR

Fictitious play’s convergence rate in two-player zero-sum games remains a central question, particularly when best responses are unique. This paper recursively constructs games with arbitrarily slow polynomial convergence after a prescribed common initial action. For every order k ≥2, the duality gap decays as Θ(t−1/k), ruling out a universal polynomial exponent for the specified trajectories.

  • Problem

    The true convergence rate of fictitious play in two-player zero-sum games remains unresolved, including whether tie-free play can be slower than Wang’s Θ(t−1/3) construction.

    Source: §1 · p. 2

  • Method

    The paper recursively extends a rock-paper-scissors-based game family, prescribing a common first action and ensuring unique best responses thereafter.

    Source: §1 · p. 2, §1.2 · p. 4

  • Results

    For every integer k ≥2, games with (k + 1)^2 −5 actions per player achieve duality gap Θ(t−1/k) after the prescribed common first action, with unique subsequent best responses.

    Source: §1 · p. 2, §1.2 · p. 4

  • Takeaways & Limitations

    No constant γ > 0 bounds the duality gap by O(t−γ) across all finite zero-sum games and trajectories with a prescribed common first action and unique subsequent best responses.

    Source: §1.2 · p. 4

    The presented family has dimension Θ(k²) and is not claimed to be smallest possible.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer $k \ge 2$, we construct a payoff matrix with $(k+1)^2 - 5$ actions per player for which the duality gap of the empirical strategies decays as $\Theta(t^{-1/k})$ after $t$ steps. The family starts from the standard rock-paper-scissors matrix, with each higher-order game constructed recursively from the preceding one. After a prescribed common initial action, every subsequent best response under fictitious play is unique. For $k \ge 3$, these games give counterexamples to Karlin's conjectured $O(t^{-1/2})$ convergence rate, and they extend the recent $\Theta(t^{-1/3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.

1 Introduction

Fictitious play is known to converge in two-player zero-sum games, but its true convergence rate—especially without best-response ties—has remained contested. This paper constructs a recursively growing family with arbitrarily slow polynomial rates and unique best responses after a prescribed common first action.

1.1 Fictitious play and duality gap

  • Fictitious play best responds to opponents’ empirical past actions; the duality gap is zero exactly at Nash equilibrium.Robinson proved convergence, with an upper bound of O(t−1/(m+n−2)) on m-by-n payoff matrices.Source: §1 · p. 2, §1.1 · p. 3

1 Introduction

  • Karlin conjectured an O(t−1/2) rate, while fixed tie-breaking results established that rate for positive diagonal games and generalized RPS games under symmetric initialization.Daskalakis and Pan disproved the strong conjecture using adversarial tie-breaking; Wang (2025) later obtained a tie-free Θ(t−1/3) construction after a prescribed common initial action.Source: §1 · p. 2

1.2 Main result

  • For every integer k ≥2, the construction uses (k + 1)^2 −5 actions per player and achieves a duality gap of Θ(t−1/k), with unique best responses after the prescribed common first action.For k ≥3, the rates are slower than Karlin’s conjectured O(t−1/2) rate; for k ≥4, the exponents extend to arbitrarily small positive values.Source: §1 · p. 2, §1.2 · p. 4
  • The inductive construction retains one parent game and adds 2k + 3 actions per step, yielding quadratic action growth in k.An alternative 7 × 7 cubic-rate base gives a family smaller by a constant, while the presented RPS-base construction is simpler.Source: §1.2 · p. 5
  • The authors do not claim their construction is smallest possible, and its dimension is Θ(k²) for rate Θ(t−1/k).A 7 × 7 cubic-rate base yields a family smaller by a constant, still with Θ(k²) dimension growth.Source: §1.2 · p. 5

1.3 Related work

  • Wang (2025) coupled three RPS blocks to obtain a cubic slowdown; this paper’s lift retains one parent block and adds linearly many actions at each order.Recursively using multiple parent copies would incur exponential growth in the order.Source: §1.3 · p. 5

2 How the construction works

This section explains how the construction recursively lifts a parent fictitious-play clock by bundling phases, detecting bundle endpoints, and resetting scores. Shifting phase boundaries makes the lift repeatable, while fixed polynomial coefficient tables encode the required transitions as finite matrix equations.

2 How the construction works

  • Each lift retains the order-k payoff matrix as a principal block and adds actions that extend its best-response sequence and restore score differences without resetting cumulative counts.Source: §2 · p. 6

2.1 Why order-k phases give a t−1/k gap

  • Θ(t^-1/k) gaps follow when phase length and entry height are Θ(σ^(k-1)), making elapsed time Θ(σ^k) and height divided by time Θ(t^-1/k).The clock starts at a fixed phase threshold; the cited passage says a later lemma converts the estimate to all integer times after bias and setup.Source: §2.1 · p. 8

2.2 Polynomial score and count data

  • Fixed score and count coefficient tables encode phase data polynomially, reducing infinitely many score-transition requirements to finite matrix identities such as AC = RN_k.The tables are independent of the phase index; the binomial basis and shift matrices express phase changes through fixed operations.Source: §2.2 · pp. 8, 10

2.3 From the RPS clock to the first slower rate

  • Bundling q consecutive RPS phases gives a Θ(q^2)-length segment, but added endpoint and reset actions detect its end and return scores to the next outer phase’s prescribed entry state.The RPS matrix remains the top-left block of a 10 × 10 recurrent matrix; adding an initial setup action yields the complete 11 × 11 game.Source: §2.3 · pp. 10–12

2.4 Retaining the parent block and adding actions

  • For an order-k to order-(k + 1) lift, outer phase q bundles τq consecutive parent phases, then added actions adjust scores for the next bundle while past action counts remain unchanged.The bundle advances parent scores from index τq to 2τq; the reset block raises the maximum by a rational constant c in (0, 1).Source: §2.4 · pp. 12–13
  • Each lift bundles τq parent phases and adds an endpoint action plus 2(k+1) reset actions, producing degree-k bundle lengths and outer heights.The endpoint action detects the bundle’s end, and the reset runs restore parent scores for the next outer phase.Source: §2.4 · pp. 13–14

2.5 Detecting the endpoint of a parent bundle

  • The endpoint counter keeps g below the parent maximum at every proper bundle prefix, then makes it the unique maximizer at the exact endpoint.The detector combines the parent’s lead over b with a weighted count of remaining parent plays; its positive margin persists until the final play.Source: §2.5 · pp. 15–16

2.6 How the added actions wait and restore the scores

  • Early and late reset runs move old scores down and then up while reset actions take turns at ceiling ζ(q), with b winning the handoff by priority.The fixed coupling P must satisfy both the required old-score change and reset-score change; the boundary ties are later removed by a small initial score bias without changing the play sequence.Source: §2.6 · p. 18

2.7 Making the recursion repeatable

  • Regrouping the unchanged trajectory as Wk+1(q) = B(q)A(q+1) gives each lifted clock entry leader a0, endpoint counter g, and nk = (k+1)^2−5 total actions.The lift preserves a positive-weight condition for the next recursion; at k=3 it has 10 recurrent actions and 11 including setup, with quadratic phase length and entry height and cubic elapsed time.Source: §2.7 · pp. 19–20

3 Proof of the main theorem

This section proves Theorem 1.1 by recursively building higher-order clocks from the RPS trajectory and converting them into strict fictitious play from zero counts. It establishes the Θ(t^-1/k) duality-gap rate at every integer time and maps the proof’s dependencies and locations.

3.1 Definition of a clock and the bundle height bound

  • An order-k clock specifies an exact polynomial-phase trajectory, endpoint detection, and a bound on remaining height gain.The bundle lemma shows that the same additive height constant suffices across an entire parent bundle, once its starting phase is large enough.Source: §3.1 · pp. 20–21

3.2 The quantitative effect of one step

  • Starting from the RPS order-2 clock, each lift adds 2k+3 actions and retains the parent matrix as a principal block.The lifted phase word is B(q)A(q+1), and the construction can be iterated because it preserves the required algebraic data.Source: §3.2 · p. 23

3.3.1 A fixed bias removes ties

  • A rational bias preserves strict score comparisons while resolving ties according to the fixed priority rule, yielding unique maximizers throughout the trajectory.The biased process follows exactly the original priority trajectory.Source: §3.3.1 · p. 24

3.3.2 One initial action produces the required scores

  • One common first-round setup action realizes the desired initial scores from zero counts and is never selected again.The recurrent actions then have the same unique best response for both players at each subsequent time.Source: §3.3.2 · p. 25

3.4 The duality gap at every integer time

  • For the order-k game, the gap satisfies Gap_b A_k(z_t/t,z_t/t) = c_k t^-1/k(1+o(1)), where c_k > 0, as t tends to infinity over all integer times.The relative error obtained here is O(t^-1/k).Source: §3.4 · pp. 25–26, §3.5 · p. 26

3.5 Proof of the main theorem

  • The construction uses (k+1)^2-5 actions, with every best response after the common first round unique.It starts at a fixed clock phase, removes ties with a rational bias, and realizes the biased scores from zero counts using one setup action.Source: §3.5 · p. 26
  • A positive constant c_k in the bound yields the claimed Θ(t^-1/k) convergence rate.Appendix A supplies bounds for choosing the reset-count scale and computes the leading gap constant.Source: §3.5 · p. 26

3.6 Remaining proof map

  • Theorem 5.1 is the induction bridge, its five proof steps are in Sections 5–9, and Table 2 separates statement locations from proof locations.The table presents dependencies in the proof of Theorem 1.1.Source: §3.6 · p. 27, Table 2 · p. 27

4 The base case k = 2: rock–paper–scissors

The three-action rock–paper–scissors game supplies the order-2 clock that starts the induction. Its trajectory has unique best responses and a duality gap of Θ(t^-1/2) at all integer times.

4 The base case k = 2: rock–paper–scissors

  • The three-action RPS game defines an order-2 clock, with one additional setup action when play starts from zero counts.The clock uses entry action b = 0 and counter v = (0, −1, 1).Source: §4 · p. 27
  • Every best response in the RPS phase words is unique.Across the three runs, each next action overtakes the current leader by 1/3 exactly at its stated handoff, proving the infinite strict word.Source: §4 · pp. 27–28
  • The three runs have lengths 3σ + 2, 3σ + 3, and 3σ + 4, and end at r_RPS(σ + 1).The handoffs follow score margins that keep the next action below the leader until the exact transition.Source: §4 · pp. 27–28
  • Θ(t^-1/2) is the duality-gap rate at all integer times for this trajectory.Summing phase lengths gives elapsed time (9/2)q^2 + O(q) at height q + O(1); monotonicity extends the rate between phase boundaries.Source: §4 · p. 28
  • A two-action synchronized skew-symmetric game cannot provide a nontrivial recurrent clock, whereas RPS does so within the skew-symmetric setting.With two actions, the score difference changes by a fixed amount each update, so the maximizing action changes at most once or scores remain constant.Source: §4 · p. 29

5 The one-step theorem and the endpoint/reset equations

This section develops the one-step lift from an order-k clock to an order-(k+1) clock and analyzes the coupling equations for restoring the old and reset score blocks. It also characterizes when one coupling matrix satisfies both equations, while noting that the resulting coefficient-table identity alone does not establish that the prescribed word is played.

5 The one-step theorem and the endpoint/reset equations

  • Each admissible order-k clock on m actions lifts to order-(k+1) on m+2k+3 actions, retaining the parent matrix as a principal block and the same lift-ready data.The new clock has endpoint counter e_g^T, prefix margin 1, remaining-height constant A_{k+1}=A_k+1, and reference gain 1/2.Source: §5 · p. 29

5.1 Parent and reference tables for the one-step theorem

  • The parent and old-action tables track bundled counts, scores, intermediate scores, and the required reset change, with D(q)=s(q+1)−smid(q).The reset word must supply exactly the score difference between the next phase's entry scores and the scores after the old-action word.Source: §5.1 · p. 31

5.2 The additional data required by the one-step theorem

  • The lift requires an integer scale, rational reference gain, integer correction satisfying compatibility tests, and strictly positive parent weights representing the target height polynomial.These conditions accompany the parent clock data so the constructed clock retains the additional data needed for another lift.Source: §5.2 · pp. 32–33

5.3 Verifying the endpoint action

  • The endpoint action loses at each proper parent-bundle prefix by at least δ0−δ>0, wins at the exact endpoint by δ>0, and its required score change has no degree-k term.After its single play, the parent maximum is ζ(q)−c and the endpoint score is ζ(q)−c+δ; the score-change table D is independent of δ.Source: §5.3 · p. 34

5.4 Restoring both score blocks with one coupling matrix

  • Both old-action and reset-action scores must be restored to their next-entry values simultaneously, using one coupling matrix P whose transpose sets the reverse interactions by skew symmetry.Source: §5.4 · p. 35
  • The lift uses n = 2(k + 1) reset actions, with positive lower-triangular interactions making earlier reset actions raise later scores and later actions lower earlier scores.These signs, positive run counts, and coupling bounds support the prescribed handoffs; Proposition 9.1 verifies best responses, including competition from old actions.Source: §5.4 · p. 35
  • The coupling equations hold exactly when the combined word changes the full score table U to its next-entry table UT.This is an identity of coefficient tables; whether the word is actually played is a separate best-response question.Source: §5.4 · p. 36
  • With full-column-rank count tables X and M, the two coupling equations are solvable for P exactly when their compatibility identity holds.The lemma also provides an explicit solution using one-sided inverses and a reference matrix.Source: §5.4 · p. 36
  • Under the full-rank hypotheses, compatibility reduces to a w × w linear matrix equation involving total reset counts, aggregate interactions, and the height-polynomial change.Solving it makes the required score changes agree with skew symmetry; the later construction supplies solutions with positive reset interactions.Source: §5.4 · p. 37

6 Compatibility tests and the integer correction

Section 6 characterizes when the score-restoration equation is solvable, constructs integer scale and correction data for its higher-index tests, and treats the remaining RPS obstruction through a gain adjustment.

6 Compatibility tests and the integer correction

  • The section addresses algebraic compatibility first; payoff signs and best-response validity are handled later.The construction uses the tests above k to choose the integer correction, leaving at most the lowest-index test for the gain adjustment.Source: §6 · p. 38

6.1 Why the listed linear tests characterize solvability

  • L(E) = F is solvable over Q exactly when its inner product with each test matrix Z(h) vanishes for even h in [k, 2k].These matrices form a basis of the adjoint kernel.Source: §6.1 · p. 38

6.2 Choosing the integer scale and correction for tests indexed above k

  • An integer scale τ ≥ 1 and integer correction row ℓ∗ can be computed in finitely many steps using exact rational arithmetic to satisfy the higher-index tests.Their choice is independent of row 0 of R⊤C and the constant coefficient χ0.Source: §6.2 · p. 40

6.3 Verifying the additional data for the RPS base

  • For the RPS clock, τ = 1, cref = 1/2, ℓ∗ = (0, 0, 0), and aP = (2, 2, 2)⊤/27 satisfy the additional-data requirements.The positive weights are all 2/27, and the sole higher-index test for k = 2 vanishes automatically.Source: §6.3 · p. 42

6.3.1 Adjusting the gain to remove the lowest RPS compatibility obstruction

  • At k = 2, the lowest compatibility test is −81/2 at the reference gain, so retaining c = 1/2 leaves the reset equations inconsistent.For every integer T1 ≥ 5, the adjusted gain lies in (0, 1) and cancels this algebraic obstruction; additional lower bounds on T1 are needed for coupling signs and waiting margins.Source: §6.3.1 · pp. 42–43

7 Constructing the reset actions with the required signs

This section constructs reset counts, interactions, and old-action couplings satisfying the compatibility and reset equations, and establishes uniform sign and waiting bounds. It also shows that a sufficiently large $T_1$ preserves the required reset signs and margins uniformly over permitted $T_2$ once both reset equations are solved.

7.1 Choosing the total counts and satisfying the lowest compatibility test

  • For sufficiently large T1, the gain c lies in (0, 1) and a rational E solves the compatibility equation exactly, with an O(1) correction to its T1-leading term.For odd k, c = cref; for even k, the gain is adjusted to satisfy the remaining h = k test. T2 changes lower-degree count coefficients while preserving total counts and leading coefficients.Source: §7.1 · pp. 44–45

7.2 Constructing the reset interactions and the old-action coupling

  • The two reset groups realize E through M^TJM = E, and the resulting coupling P satisfies PM = D and P^T X = Q exactly.The early group lowers old-action scores, while the late group restores them.Source: §7.1 · p. 45, §7.2 · p. 47

7.3 Bounds that preserve the reset interaction and coupling signs

  • Uniformly for all allowed T2 and sufficiently large T1, J is positive below its diagonal, P has negative early and positive late columns, and early actions meet the waiting margins.The bounds hold before T2 is selected; cancellations remove the growing count tables from the error estimates, making the sign and margin guarantees uniform.Source: §7.3 · p. 47
  • The sign conditions give C× > 0 entrywise, positive remaining below-diagonal entries of J, and PE < 0 < PL.Source: §7.3 · p. 49
  • −Pij ≥ ai − KP/T1 > 3amin/4 > ϵ for i < m, while −Pgj − c > ag − KP/T1 − 1 > Ak for 0 ≤ j < r.The early and late columns differ from −a and a, respectively, by at most KP/T1 entrywise, uniformly in T2.Source: §7.3 · p. 49
  • For every sufficiently large T1, 0 < c < 1, ν < 1/2, υk + ℓ∗,k > 0, and Pγ = (PM):,k = D:,k = 0, uniformly over permitted T2.This permits fixing T1 before choosing T2.Source: §7.3 · p. 49
  • For every integer T2 ≥ max{T1, υk}, both reset equations PM = D and P⊤X = Q hold, and the signs and margins of Lemma 7.2 are satisfied.The remaining freedom in T2 is used in Section 8 to obtain the positive weights required at the next order.Source: §7.3 · p. 49

8 Preserving the additional data for the next order

Section 8 uses the remaining parameter freedom to make the next-order weights positive without undoing the reset conditions established earlier. The next scale and correction are determined independently of T2, which is chosen afterward to secure positive weights.

8 Preserving the additional data for the next order

  • The next scale factor and correction row can be computed independently of T2, leaving that parameter free to make the late-reset weights positive.Uniform estimates ensure the later choice preserves reset signs and margins.Source: §8 · p. 50, §8.1 · pp. 50–51

8.1 Choosing the remaining parameter and preserving positive weights

  • A sufficiently large T2 gives the rotated order-(k + 1) tables positive weights while preserving the reset equations, signs, and margins.This supplies the positive-weight data needed for the next lift.Source: §8.1 · p. 50
  • The construction assigns a common positive weight to old and early-reset rows, then chooses T2 so the late-reset weights are positive.The resulting data include the next scale factor, correction row, reference gain 1/2, and strictly positive weights.Source: §8.1 · p. 51

9 Best-response verification and proof of the one-step theorem

The authors verify that the constructed game follows the prescribed best-response trajectory, then rotate its phase boundary to establish the clock conditions needed for another lift. This completes the one-step construction, which adds 2k + 3 actions while retaining the parent matrix as a principal block.

9.1 Checking every proposed run against every action

  • For every sufficiently large phase index, best responses follow the exact word A(q)B(q), with the reset actions played in order and the maximum score fixed at ζ(q) throughout the reset block.The sequence ends at u(q + 1), allowing the comparisons to extend by induction to later phases.Source: §9.1 · pp. 52, 55

9.2 Starting the new phase at the first reset action

  • Rotating the phase to begin at the first reset action yields an order-(k + 1) clock with entry action a0, counter e_g, and Ak+1 = Ak + 1.The rotated tables also satisfy the additional data required for a further lift.Source: §9.2 · pp. 56–57

9.3 Proof of the one-step construction theorem

  • The one-step construction adds exactly 2k + 3 actions and leaves the original game unchanged as a principal block.The proof combines compatibility, reset equations, sign and margin bounds, positive weights, and best-response verification.Source: §9.3 · p. 57

A Explicit reset-scale bounds and rate constants

Appendix A gives sufficient reset-scale bounds and the leading gap constant.

A Explicit reset-scale bounds and rate constants

A.1 Sufficient bounds for the reset-count scale

The construction supplies explicit sufficient bounds for choosing the reset-count scale T1. Compatibility equations are already solved; the remaining checks establish signs and waiting margins.

A.1 Sufficient bounds for the reset-count scale

  • A sufficiently large T1 satisfies every required sign and waiting-margin condition uniformly over later choices of T2.Lemma 7.2 provides explicit bounds from the parent coefficient tables.Source: §A.1 · p. 58
  • The compatibility equations are already solved, leaving only the sign inequalities to verify.One can test successive integer values or double T1 from 1 until all requirements pass.Source: §A.1 · p. 58
  • The T1 checks require 0 < c < 1, υk + ℓ*,k > 0, and ν < 1, with the bounds involving bE defined only after ν < 1/2 is verified.For even k, discard a candidate T1 if the denominator in (47) is nonpositive.Source: §A.1 · p. 58

A.2 The leading constant and payoff normalization

The duality gap has a positive leading constant multiplying the t^-1/k rate. The constant can be computed from the construction, while early trajectories may exhibit long transients.

A.2 The leading constant and payoff normalization

  • Gap = c_k t^-1/k(1 + o(1)), with c_k > 0, giving the asymptotically sharp rate for each fixed game.Lemma 3.8 proves this sharper rate form.Source: §A.2 · p. 58
  • The normalized matrix bA_k/M_k has leading constant c_k/M_k, so payoff normalization changes the constant but not the stated exponent.The fixed bias, common score translation, and starting phase do not change c_k, though they can change M_k.Source: §A.2 · pp. 58–59
  • The leading constant is computed from the exact coefficient tables and payoff matrix, including setup.The displayed order-two game has c_2 = 2.Source: §A.2 · pp. 58–59
  • Long transients can make t^-1/k inaccurate near the trajectory's start, although the stated law holds for each fixed game asymptotically.The rounded normalized constants describe particular games and depend on the chosen matrices.Source: §A.2 · p. 59

B Explicit matrices for orders two and three

Explicit order-two and order-three matrices illustrate an application of the lift. Both include a setup action, after which best responses are unique.

B Explicit matrices for orders two and three

B.1 Order two: rock–paper–scissors with setup

The order-two game adds a setup action to the three-action RPS clock. Its setup play establishes the initial recurrent scores, while normalization rescales the displayed matrix.

B.1 Order two: rock–paper–scissors with setup

  • The setup play gives recurrent scores (313/36, 1, 299/36)ᵀ and starts the recurrent word with 0819210.The word then follows successive RPS phases.Source: §B.1 · p. 59
  • Three RPS actions generate the square-root clock, and a fourth setup action produces its initial scores from zero counts.Source: §B.1 · p. 59
  • Replacing the displayed matrix's denominator 36 with 313 normalizes it to [−1, 1].Source: §B.1 · p. 59

B.2 Order three: the first application of the general construction

The order-three game combines old actions with early and late reset blocks, and adds a setup action to establish the initial score state. The section specifies the matrix through its block structure and tables, while noting that the displayed higher-order examples use conservative parameter choices.

Order-three matrix construction

  • The order-three matrix combines old actions with paired early and late reset blocks, plus one setup action.The old/early/late block sizes are 4, 3, and 3, with the setup row and column bringing the total to eleven.Source: §B.2 · p. 60

Matrix specification

  • Tables and the displayed block signs and transposes completely specify F3, while Γ3 clears the rational construction coefficients.Every actual payoff is the corresponding entry of F3 divided by Γ3.Source: §B.2 · p. 60

Setup scores

  • After setup, a0 is the unique maximizer of the score vector encoded by the setup column.The setup column already includes the bias and common score translation; no additional bias is applied.Source: §B.2 · p. 61, Table 4 · p. 61

Higher-order examples

  • Conservative parameter choices produce 20 × 20 and 31 × 31 order-four and order-five games, but the resulting large numerators are not claimed necessary.The largest numerators in these outputs have 320 and 1914 decimal digits, respectively.Source: §B.2 · p. 62

C Exact event-driven empirical simulations

The simulations group rounds into batches only after verifying the decisions exactly, making long constructed trajectories computationally tractable. They track integer score and count states, use exact arithmetic for choices, and certify grouped runs with score-margin checks.

C Exact event-driven empirical simulations

  • Exact event-driven simulation groups rounds whose best responses can be verified, avoiding impractical one-round updates while preserving the fictitious-play trajectory.The first outer phase alone takes about 10^67, 10^351, and 10^742 rounds for k = 4, 5, and 6.Source: C Exact event-driven empirical… · p. 63

C.1 Simulation state, exact arithmetic, and payoff scaling

  • After both players take the prescribed setup action, the simulation updates a common integer count and score state using the unique shared best response.The state satisfies u = B_k z and t = 1^T z; only the actual setup round is included in elapsed time.Source: §C.1 · p. 63
  • Exact integer-ratio arithmetic determines run lengths, score comparisons, polynomial minima, and state updates; floating point is reserved for display and reporting horizons.The paper warns that fixed-precision arithmetic would quickly lose the small score differences needed to follow the trajectory.Source: §C.1 · p. 63
  • Payoff normalization changes displayed units but leaves best responses and elapsed time unchanged; dividing counts by t instead forms empirical strategies.The trajectory is computed using the exact integer matrix, while normalization is used for plotting gaps.Source: §C.1 · pp. 63–64

C.2 Skipping rounds while preserving the exact trajectory

  • Constant-action runs and inherited RPS cycles are batched only after strict score-margin checks cover all decisions and competing actions.For proposed cycle batches, first- and last-decision margins are quadratic in the cycle index and are checked at every integer index in the batch.Source: §C.2 · p. 64

C.3 How far the computations ran

The computations certify long but nonuniform horizons across orders, using different grouping methods and phase lengths. The observed gaps are compared with each game's own theoretical law, whose leading constant is not fitted to the data.

C.3 How far the computations ran

  • For k = 4, 5, and 6, the runs are certified through phase 4096Q_k, comprising 4095Q_k complete phases after setup.Table 7 reports each run's last completed round and number of complete outer phases, rather than equal-time horizons across games.Source: §C.3 · p. 65, Table 7 · p. 65
  • The k = 3 run uses two million run-or-cycle events, while the k = 4, 5, and 6 runs verify whole nested phase words.Their differing horizons reflect the grouping methods, phase lengths, and starting labels; event budgets are not elapsed fictitious-play times.Source: §C.3 · p. 65
  • The reported gap-to-law ratios compare each run with its own theoretical asymptote, using the exact positive leading constant rather than a fitted value.Payoff normalization divides both the gap and its constant by the same maximum-entry scale, leaving the displayed ratio unchanged.Source: §C.3 · p. 65

C.4 Observed rates for orders two and three

  • A smaller exponent need not mean a larger gap at fixed finite time because the scaled leading constants differ greatly across games.Figure 6 compares each game with its own predicted law, including after scaling by the setup-inclusive maximum entry.Source: §C.4 · p. 65

C.5 Checking complete nested phase words for orders four through six

For orders four through six, the simulation proposes nested phase words and advances only after exact checks certify their action choices. Polynomial sign tests over a unit cube verify the required margins, and the resulting gap samples approach the predicted rates.

C.5 Checking complete nested phase words for orders four through six

  • A higher-order batch proposes reset runs, nested parent phases, and an endpoint action, then recomputes count polynomials from that word.The reset-count table and lift-specific scales specify the word; the supplied full-phase count table is not used to advance the trajectory.Source: §C.5 · pp. 65, 67
  • The simulation checks integer run lengths and strict leader-minus-rival margins at the first and last decision of every nested run.Because each within-run score difference is affine, positive margins at both ends certify every decision in that run.Source: §C.5 · p. 67
  • Nested integer offsets are mapped into a unit cube so polynomial margins cover every required index while retaining dependence on ancestor indices.The continuous cube contains all integer indices used by the batch.Source: §C.5 · p. 67
  • Positive tensor Bernstein coefficients certify strict positivity on the cube; the simulation advances only after every required test passes.This sufficient certificate is used for the simulations, not the proof of Theorem 1.1; a negative coefficient means only that the test did not certify the batch.Source: §C.5 · p. 67
  • For k = 4, 5, and 6, phase-start gap samples approach the predicted t^-1/k laws, while exact certificates cover intervening decisions.Figure 7 samples outer-phase starts and therefore does not display the gap's shape inside a phase.Source: §C.5 · p. 67, Figure 7 · p. 68
Loading 2610.08768v1…