A counter-example to Karlin's strong conjecture for fictitious play

[摘要] Fictitious play is a natural dynamic for equilibrium play in zero-sum games, proposed by Brown , and shown to converge by Robinson . 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 x n identity matrix, fictitious play may converge (for some tie-breaking) at rate as slow as [Omega](t- 1/n).

[发布机构] Massachusetts Institute of Technology