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

By Constantinos Daskalakis, Qinxuan Pan. 2014

50 citations recorded by the source corpus.

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

Subfields: Economics and Econometrics, Management Science and Operations Research, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

In Game & Decision Theory

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “Interestingly, Daskalakis and Pan (2014) recently showed that Shapiro’s rate is also a lower bound if the tie breaking rule gets the worst pick an inﬁnite number of times.”
Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017, background): “The disadvantage is that Fictitious Play is only known to converge to equilibrium in the limit Robinson [1951], rather than in a polynomial number of rounds (though it is conjectured to converge quickly under rather general circumstances; see Daskalakis and Pan [2014] for a recent discussion).”
Efficient Exploration via State Marginal Matching (2019, background): “A slight variant, fictitious play (Brown, 1951) does converge to a Nash equilibrium in finite time (Robinson, 1951; Daskalakis & Pan, 2014).”
Introduction to Multi-Armed Bandits (2019, background): “This convergence rate is the best possible (Daskalakis and Pan, 2014).”