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.
|Date of creation:||01 Sep 2011|
|Date of revision:|
|Contact details of provider:|| Postal: |
Web page: http://www.economics.ox.ac.uk/
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Sergiu Hart & Yishay Mansour, 2013.
"How Long To Equilibrium? The Communication Complexity Of Uncoupled Equilibrium Procedures,"
World Scientific Book Chapters,
in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 10, pages 215-249
World Scientific Publishing Co. Pte. Ltd..
- Hart, Sergiu & Mansour, Yishay, 2010. "How long to equilibrium? The communication complexity of uncoupled equilibrium procedures," Games and Economic Behavior, Elsevier, vol. 69(1), pages 107-126, May.
- Germano, Fabrizio & Lugosi, Gabor, 2007.
"Global Nash convergence of Foster and Young's regret testing,"
Games and Economic Behavior,
Elsevier, vol. 60(1), pages 135-154, July.
- Fabrizio Germano & Gábor Lugosi, 2004. "Global Nash convergence of Foster and Young's regret testing," Economics Working Papers 788, Department of Economics and Business, Universitat Pompeu Fabra.
- Sandholm, William H. & Hofbauer, Josef, 2011. "Survival of dominated strategies under evolutionary dynamics," Theoretical Economics, Econometric Society, vol. 6(3), September.
- Peyton Young, 2002.
"Learning Hypothesis Testing and Nash Equilibrium,"
Economics Working Paper Archive
474, The Johns Hopkins University,Department of Economics.
- Foster, Dean P. & Young, H. Peyton, 2003. "Learning, hypothesis testing, and Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 45(1), pages 73-96, October.
- Hart, Sergiu & Mas-Colell, Andreu, 2006.
"Stochastic uncoupled dynamics and Nash equilibrium,"
Games and Economic Behavior,
Elsevier, vol. 57(2), pages 286-303, November.
- Sergiu Hart & Andreu Mas-Colell, 2004. "Stochastic uncoupled dynamics and Nash equilibrium," Economics Working Papers 783, Department of Economics and Business, Universitat Pompeu Fabra.
- Sergiu Hart & Andreu Mas-Colell, 2004. "Stochastic Uncoupled Dynamics and Nash Equilibrium," Discussion Paper Series dp371, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
- Sergiu Hart & Andreu Mas-Colell, 2015. "Stochastic Uncoupled Dynamics and Nash Equilibrium," Working Papers 174, Barcelona Graduate School of Economics.
- Sergiu Hart & Andreu Mas-Colell, 2004. "Stochastic Uncoupled Dynamics and Nash Equilibrium," Levine's Bibliography 122247000000000466, UCLA Department of Economics.
- Hofbauer, Josef & Sandholm, William H., 2007.
"Evolution in games with randomly disturbed payoffs,"
Journal of Economic Theory,
Elsevier, vol. 132(1), pages 47-69, January.
- Hofbauer,J. & Sandholm,W.H., 2003. "Evolution in games with randomly disturbed payoffs," Working papers 20, Wisconsin Madison - Social Systems.
- Foster, Dean P. & Young, H. Peyton, 2006. "Regret testing: learning to play Nash equilibrium without knowing you have an opponent," Theoretical Economics, Econometric Society, vol. 1(3), pages 341-367, September.
- Sergiu Hart & Andreu Mas-Colell, 2003. "Uncoupled Dynamics Do Not Lead to Nash Equilibrium," American Economic Review, American Economic Association, vol. 93(5), pages 1830-1836, December.
When requesting a correction, please mention this item's handle: RePEc:oxf:wpaper:570. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Monica Birds)
If references are entirely missing, you can add them using this form.