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

Abstract

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/\sqrt{t})$ with the number of steps $t$. We disprove this conjecture showing that, when the payoff matrix of the row player is the $n\times n$ identity matrix, fictitious play may converge with rate as slow as $\Omega (t^{-1/n})$.

55th IEEE Symposium on Foundations of Computer Science

Cited by in corpus (5)

• Efficient Exploration via State Marginal Matching
• Learning to Play No-Press Diplomacy with Best Response Policy Iteration
• Near-Optimal No-Regret Learning in General Games
• Complexity Theory, Game Theory, and Economics: The Barbados Lectures
• Automated Construction of Bounded-Loss Imperfect-Recall Abstractions in Extensive-Form Games