Best-reply dynamics in large binary-choice anonymous games
We consider small-influence anonymous games with a large number of players n where every player has two actions. For this class of games we present a best-reply dynamic with the following two properties. First, the dynamic reaches Nash approximate equilibria fast (in at most cnlogn steps for some constant c>0). Second, Nash approximate equilibria are played by the dynamic with a limit frequency of at least 1−e−c′n for some constant c′>0.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
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.:
- Ely, Jeffrey C. & Sandholm, William H., 2005. "Evolution in Bayesian games I: Theory," Games and Economic Behavior, Elsevier, vol. 53(1), pages 83-109, October.
- Itai Arieli & H Peyton Young, 2011. "Stochastic Learning Dynamics and Speed of Convergence in Population Games," Economics Series Working Papers 570, University of Oxford, Department of Economics.
- 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.
- Milgrom, Paul & Roberts, John, 1990. "Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities," Econometrica, Econometric Society, vol. 58(6), pages 1255-77, November.
- Blonski, Matthias, 1999. "Anonymous Games with Binary Actions," Games and Economic Behavior, Elsevier, vol. 28(2), pages 171-180, August.
- Rashid, Salim, 1983. "Equilibrium points of non-atomic games : Asymptotic results," Economics Letters, Elsevier, vol. 12(1), pages 7-10.
- Benaim, Michel & Weibull, Jörgen W., 2000.
"Deterministic Approximation of Stochastic Evolution in Games,"
Working Paper Series
534, Research Institute of Industrial Economics, revised 30 Oct 2001.
- Michel BenaÔm & J–rgen W. Weibull, 2003. "Deterministic Approximation of Stochastic Evolution in Games," Econometrica, Econometric Society, vol. 71(3), pages 873-903, 05.
When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:81:y:2013:i:c:p:130-144. 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: (Zhang, Lei)
If references are entirely missing, you can add them using this form.