How fast is fast fictitious play?

Abstract

We present a modification of the fictitious play algorithm for matrix games by aggregating trivial original steps. The resulting new algorithm consists of comparable simple steps but has a much better rate of convergence. Modifications for solving large scale LP-programs, numerical results and some conjecture concerning the total effort of elementary steps for esuring an error $ < \varepsilon$ will be discussed.