EconCS Whiteboard Talk Series
Bill Sandholm (University of Wisconsin-Madison)
Calvin Lab Room 116
Large Deviations and Stochastic Stability in Evolutionary Game Theory
Population games are a basic model of strategic interactions among large numbers of small, anonymous agents. One can model the dynamics of behavior in these games by introducing revision protocols, which specify how agents myopically decide whether and when to switch strategies. Together these objects define a Markov chain on the set of population states. This stochastic process is parameterized by the size of the population and the level of noise in agents' choices.
While analyzing this process directly is not computationally feasible, one can obtain more tractable descriptions of aggregate behavior by taking the population size and noise level to their limiting values. This talk focuses on the large deviations properties of these stochastic processes, which describe the rates at which the processes move between locally stable equilibrium states. These properties can be used in turn to characterize the asymptotic behavior of the processes' stationary distributions, and hence their stochastically stable states, which are the states whose stationary distribution weights do not vanish as the parameters are taken to their limits.
The work I will describe can be summarized as follows: If one takes either one of the parameters to its limit, one can obtain an analytical characterization of large deviations properties and stochastic stability in terms of certain control problems, but these problems can only be solved explicitly in special cases. But if one looks at double limits - following the small noise limit by the large population limit, or vice versa - then these control problems become tractable, allowing one to solve examples to their very end.
The first part of the talk will focus on small noise limits. Taking just the small noise limit allows one to describe large deviations properties in terms of discrete path cost minimization problems. I show that if this limit is followed by the large population limit, then these discrete problems converge to continuous but nonsmooth optimal control problems. I then show that these problems can be solved explicitly using dynamic programming methods.
The second part of the talk will consider the more difficult problem of large population limits. Establishing a new result in the theory of sample path large deviations, I show how large deviations properties for the large population limit can be characterized in terms of smooth optimal control problems. These problems only admit analytical solutions in special cases. I then propose that if one follows with the small noise limit, then these control problems converge, and that their limits are the same problems obtained from the reverse order of limits. This suggests that large deviations properties and their consequences do not depend on which parameter is emphasized - that is, taken to its limit first - in the asymptotic analysis.
The work I’ll present during the first part is already forthcoming; here’s the link: http://econtheory.org/
