# A Counter-Example to Karlin's Strong Conjecture for Fictitious Play

arXiv: https://arxiv.org/abs/1412.4840 · HTML: https://mlsanity.com/paper/1412.4840/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2014.

## Built on by (most cited first, 10 of 10)

- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces](https://mlsanity.com/paper/2502.11828/) (2025)
- [Taming the Exponential Action Set: Sublinear Regret and Fast Convergence to Nash Equilibrium in Online Congestion Games](https://mlsanity.com/paper/2306.13673/) (2023)
- [Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Games](https://mlsanity.com/paper/2407.20128/) (2024)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [Online Learning and Equilibrium Computation with Ranking Feedback](https://mlsanity.com/paper/2603.19221/) (2026)
- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play](https://mlsanity.com/paper/2309.03084/) (2023)
- [Perturbing Best Responses in Zero-Sum Games](https://mlsanity.com/paper/2511.12523/) (2025)

## Abstract (arXiv)

Fictitious play is a natural dynamic for equilibrium play in zero-sum games, proposed by [Brown 1949], and shown to converge by [Robinson 1951]. Samuel Karlin conjectured in 1959 that fictitious play converges at rate O(1/√t) with the number of steps t. We disprove this conjecture showing that, when the payoff matrix of the row player is the n × n identity matrix, fictitious play may converge with rate as slow as Omega(t-1/n).