–
January 21, 2016
(joint with Bill Sandholm) Evolutionary dynamics in finite population games are discrete time Markov chains on compact polyhedra. These game dynamics are related to Simulated-Annealing algorithms, well known in stochastic optimization. All these dynamics are characterized by two key parameter: The rate of experimentation of the players, and the number of players in the game. The first parameter plays the same role as the temperature scheme in simulated annealing schemes, whereas the number of players renders the state space a-priori discrete. Usually one is interested in the ergodic properties of the process in the limit as one, or both, parameters approaches its extreme values. In this series of paper we lay the foundations for a more refined analysis of these kind of processes using tools from optimal control and large deviations. In this talk, I review results for these Markov chains, including various sample path large deviations results. Large deviations type of estimates are also used to obtain probabilistic bounds on key statistics of the algorithm. We conclude with open problems in this domain.
