Arbitrarily Slow Polynomial Convergence of Fictitious Play

arXiv:2610.08768 · cs.GT · Submitted 2026-10-06 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Arbitrarily Slow Polynomial Convergence of Fictitious Play".

Jane: Here's the gist of the paper. As a fastidious AI researcher, I have meticulously reviewed these excerpts from "Arbitrarily Slow Polynomial Convergence of Fictitious Play." The core contribution is highly technical, focusing on constructing specific game matrices that exhibit arbitrarily slow polynomial convergence rates under fictitious play.

Tom: Here is the detailed synthesis: This paper demonstrates that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games.

Jane: The central achievement is the recursive construction of a family of payoff matrices, Ab k, where for every integer k at least 2, the game has (k+1) squared - 5 actions per player.

Tom: These games are built inductively, starting from the standard rock-paper-scissors matrix and recursively generating higher-order games.

Paper summary: Tom: To recap what we just heard about "Arbitrarily Slow Polynomial Convergence of Fictitious Play," they're showing fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games.

Jane: The main thesis is that for every integer k greater than or equal to two, they construct a payoff matrix with k plus one squared minus five actions per player for which the duality gap of the empirical strategies decays as theta of t to minus one over k after t steps.

Lu: They start this family of games from the standard rock paper scissors matrix and then recursively generate each higher-order game from the preceding one.

Meng: The construction specifies a designated setup action in round zero, and after that, every subsequent best response under fictitious play is unique for both players.

Lalam: This means that their common empirical strategy count vector z t satisfies the duality gap condition of being theta of t to minus one over k.

Tom: For three or greater k, these constructed games are used as counterexamples to Karlin’s conjectured O of one over two convergence rate.

Jane: They also extend a construction by Wang from two thousand twenty-five that showed a theta of t to minus one over three convergence rate to these arbitrarily slow polynomial rates <ref:2610.08768#pg1>.

Lu: The proof involves defining a clock for the game, lifting it to an order k plus one clock while preserving the parent matrix structure and adding only two to k plus three new actions.

Meng: They show that for every integer time t, the gap is exactly big c of k t to minus one over k times one plus a small term that goes to zero as t gets bigger.

Lalam: The construction relies on solving compatibility equations between different matrices and vectors to determine the coupling matrix P, with existence guaranteed by Lemma five point five.

Tom: And they have auxiliary results showing positive leading coefficients for h k plus one and L k plus one to make sure the recursive construction is valid at each step.

Conclusion: Jane: So, to wrap up on "Arbitrarily Slow Polynomial Convergence of Fictitious Play," it’s about creating games where fictitious play converges at rates that can be made arbitrarily slow by choosing a higher order k.

Tom: The title itself points to this idea—arbitrarily slow polynomial convergence—which means we aren't just talking about a fixed rate like O of one over two or O of one over three.

Lu: What this means for the field is that it shows we can systematically engineer games where the learning process is intentionally dragged out by increasing complexity.

Meng: It suggests that if you need a specific type of convergence behavior in an AI system, like one that takes longer to settle but maybe more stable, you can design the game structure to achieve it.

Lalam: This work provides a recursive method for generating these matrices where the convergence rate is exactly big c of t to minus one over k.

Jane: It opens up a new frontier in understanding what limits fictitious play can actually achieve in zero-sum games, moving beyond the standard conjectures we've seen for decades.

Georgia Institute of Technology · Yale University · Google Research

cs.GT

Submitted: 2026-10-06

Updated: 2026-11-03

Code: https://github.com/awibisono/fictitious-play-experiments

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 95/100

The gist: As a fastidious AI researcher, I have meticulously reviewed these excerpts from "Arbitrarily Slow Polynomial Convergence of Fictitious Play." The core contribution is highly technical…

Key concepts

Fictitious Play
A learning strategy where players choose their next move based on the historical frequency of past moves made by both players. The goal is to find a Nash Equilibrium, but it can converge very slowly in certain games.
Convergence Rate
This measures how quickly fictitious play approaches the optimal strategy. A faster rate means convergence happens quicker; here, the paper proves the rate can be arbitrarily slow, specifically $O(1/k)$.
Payoff Matrix $ ext{Ab}_k$
These are specific zero-sum game matrices constructed inductively. Each matrix $ ext{Ab}_k$ has a unique setup action and is designed to force players into a state where their best responses align, leading to the slow convergence observed.
Duality Gap Condition
A mathematical condition used to quantify the error in fictitious play. The paper proves that for these constructed games, this gap scales as $ ext{Gap} = ext{Theta}(t^{-1/k})$, directly linking the game structure to the slow convergence rate.

Terminology

Summary

As a fastidious AI researcher, I have meticulously reviewed these excerpts from Arbitrarily Slow Polynomial Convergence of Fictitious Play. The core contribution is highly technical, focusing on constructing specific game matrices that exhibit arbitrarily slow polynomial convergence rates under fictitious play.

Here is the detailed synthesis:

This paper demonstrates that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. The central achievement is the recursive construction of a family of payoff matrices, Ab k, where for every integer k at least 2, the game has (k+1) squared - 5 actions per player. p. 0 These games are built inductively, starting from the standard rock-paper-scissors matrix and recursively generating higher-order games. p. 0

Key Findings and Theorem:

The main result is stated in Theorem 1.1 (Arbitrarily slow polynomial convergence). For any fixed integer k at least 2, there exists a skew-symmetric matrix Ab k of size n k times n k, where n k = (k+1) squared - 5. p. 3 The construction specifies a designated setup action in round 0, and the theorem states that after this initial move, both players will have the same unique best response at every decision time t at least 1. Crucially, their common empirical strategy count vector z t satisfies the duality gap condition:

Gap Ab k(z t/t, z t/t) = theta(t-1/k)

This implies that fictitious play converges at a rate of O(1/k), which is arbitrarily slow polynomial convergence.

Significance and Context:

The contribution is significant because for k at least 3, these constructed games serve as counterexamples to Karlin’s conjecture regarding the O(t-1/2) convergence rate. Furthermore, this work extends previous results (like Wang (2025)'s theta(t-1/3) construction) to arbitrarily slow polynomial rates. The construction is based on an inductive process where an order- k game is retained as a principal block, and 2k+3 new actions are added to generate the order- (k+1) game. p. 5

Proof Structure:

The proof of Theorem 1.1 is structured in three main steps:

  1. Constructing the Clock: Defining an order- k clock for the game.

  2. Obtaining a Strict Trajectory: Using a one-step theorem (Theorem 5.1) to lift this clock to an order- (k+1) clock while preserving the parent matrix structure and adding only 2k+3 new actions. p. 4

  3. Computing the Gap: Showing that for every integer time t, the gap is exactly Gap Ab k(z t/t, z t/t) = c k t-1/k(1 + o(1)) with a positive constant c.

The final result establishes that the relative error obtained via this process is O(t-1/k). p. 5

Technical Details and Auxiliary Results:

The construction relies on solving a system of compatibility equations (PM = D and P X = Q) to determine the coupling matrix P. The existence of a solution is guaranteed by Lemma 5. p. 25, which requires proving the compatibility identity D X = M Q in Sections 6 and 7. p. 0

Further technical components involve:

  • Coefficient Analysis: Corollary 3.5 provides explicit formulas for the leading coefficients of the extended family, showing that h k+1 and L k+1 are positive, ensuring a valid construction at each step. p. 4

  • Compatibility Verification: Proposition 7.1 confirms that the scalar compatibility tests are satisfied, leading to a rational solution for the error equation. p. 0

  • Phase Preservation: The analysis involving T 1 and T 2 (as seen in Lemma 7.2 and Proposition 8. p. 71) ensures that required sign conditions (like positive weights) are maintained uniformly over large scales, allowing the construction to proceed reliably to order k+1.

In summary, the paper provides a powerful, recursive method for generating game matrices where fictitious play exhibits convergence rates arbitrarily close to t-1/k, establishing a new frontier in understanding convergence limits for this type of learning process. p. 1

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Arbitrarily Slow Convergence for Zero-Sum Games: AI systems can converge to Nash equilibria in zero-sum games at arbitrarily slow polynomial rates of time t minus 1 over k, specifically Θ(t - 1/k), by employing fictitious play dynamics on constructed payoff matrices.

  2. Construction of Complex Game Dynamics: The paper provides a recursive method to build payoff matrices with a specific number of actions, starting from the standard rock-paper-scissors matrix, allowing AI models to explore games with a controlled increase in complexity (up to n = (k+1)2 - 5 actions per player).

  3. Guaranteed Unique Best Response: For every integer k greater than or equal to 2, the constructed games ensure that after a prescribed common initial action, every subsequent best response under fictitious play is unique, which stabilizes the trajectory for analysis.

  4. Precision in Game State Tracking: The system can track the game state through a sequence of phases defined by words Wk(q), where each phase has precisely controlled length and height gain, enabling precise control over score trajectories even when facing complex, non-equilibrium dynamics.

  5. Robustness to Tie-Breaking Rules: The framework demonstrates that these slow convergence rates hold even in the absence of best-response ties, meaning the AI system's performance bound is not dependent on arbitrary tie-breaking mechanisms like those found in some prior research.

Sources

Related papers