Tie-breaking Agnostic Lower Bound for Fictitious Play
By: Yuanhao Wang
Potential Business Impact:
Makes game learning slower than thought.
Fictitious play (FP) is a natural learning dynamic in two-player zero-sum games. Samuel Karlin conjectured in 1959 that FP converges at a rate of $O(t^{-1/2})$ to Nash equilibrium, where $t$ is the number of steps played. However, Daskalakis and Pan disproved the stronger form of this conjecture in 2014, where \emph{adversarial} tie-breaking is allowed. This paper disproves Karlin's conjecture in its weaker form. In particular, there exists a 10-by-10 zero-sum matrix game, in which FP converges at a rate of $\Omega(t^{-1/3})$, and no ties occur except for the first step.
Similar Papers
Aggregate Fictitious Play for Learning in Anonymous Polymatrix Games (Extended Version)
CS and Game Theory
Helps computer players learn faster in games.
DiffFP: Learning Behaviors from Scratch via Diffusion-based Fictitious Play
Machine Learning (CS)
Teaches game players to beat any opponent.
Fictitious Play in Extensive-Form Games of Imperfect Information
CS and Game Theory
Helps games learn fair play over time.