How fast is fast fictitious play?

Bernd Kummer

Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976),

MSC 2000

90C06 Large-scale problems

91A05 2-person games

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.