Josef Hofbauer and Bill Sandholm:
On the global convergence of stochastic fictitious play.
Econometrica 70 (Nov 2002) 2265-2294.
Click here for a preprint (final version)
or a reprint .
Download from the Econometric Society site.
We establish global convergence results for stochastic fictitious play for four
classes of games: games with an interior ESS, zero sum games, potential games,
and supermodular games. We do so by appealing to techniques from stochastic
approximation theory, which relate the limit behavior of a stochastic process to
the limit behavior of a differential equation defined by the expected motion of
the process. The key result in our analysis of supermodular games is that the
relevant differential equation defines a strongly monotone dynamical system. Our
analyses of the other cases combine Lyapunov function arguments with a discrete
choice theory result: that the choice probabilities generated by any additive
random utility model can be derived from a deterministic model based on payoff
perturbations that depend nonlinearly on the vector of choice probabilities.