Stochastic Learning Dynamics and Speed of Convergence in Population Games
Consider a finite, normal form game G in which each player position is occupied by a population of N individuals, and the payoff to any given individual is the expected payoff from playing against a group drawn at random from the other positions. Assume that individuals adjust their behavior asynchronously via a stochastic better reply dynamic. We show that when G is weakly acyclic, convergence occurs with probability one, but the expected waiting time to come close to Nash equilibrium can grow exponentially in N. Unlike previous results in the literature our results show that Nash convergence can be exponentially slow even in games with very simple payoff structures. We then show that the introduction of aggregate shocks to players' information and/or payoffs can greatly accelerate the learning process. In fact, if G is weakly acyclic and the payoffs are generic, the expected waiting time to come e-close to Nash equilibrium is bounded by a function that is polynomial e-1, exponential in the number of strategies, and independent of the population size N.
Year of publication: |
2011-09-01
|
---|---|
Authors: | Arieli, Itai ; Young, H Peyton |
Institutions: | Department of Economics, Oxford University |
Saved in:
freely available
Saved in favorites
Similar items by person
-
How Likely is Contagion in Financial Networks?
Young, H Peyton, (2013)
-
Rapid Innovation Diffusion in Social Networks
Young, H Peyton, (2012)
-
Young, H Peyton, (2014)
- More ...