This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

Limit Behavior of No-regret Dynamics

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Andriy Zapechelnyuk () (University of Bonn and Kyiv School of Economics)

Additional information is available for the following registered author(s):

Abstract

Consider a repeated game where all players follow no-regret strategies by reinforcing the actions that they regret not having played enough in the past. We show that a resulting no-regret dynamic approaches in the long run a best-response dynamic and leads to its invariant sets: rest points (Nash equilibria) or periodic orbits. The convergence results for best-response dynamics known in the literature immediately apply to no-regret dynamics. Thus, every no-regret dynamic leads to Nash equilibrium in zero-sum games, weighted potential and two-player ordinal potential games, supermodular games with diminishing returns, and some other special classes.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. 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.

File URL: http://www.kse.org.ua/RePEc/pdf/KSE_dp21.pdf
File Format: application/pdf
File Function: First version, October 2009
Download Restriction: no

Publisher Info
Paper provided by Kyiv School of Economics in its series Discussion Papers with number 21.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: Oct 2009
Date of revision:
Handle: RePEc:kse:dpaper:21

Note: Under review in Journal of Economic Theory
Contact details of provider:
Postal: 13 Yakira Str, 04119 Kyiv
Phone: (38-044)492-8012
Fax: (38-044)492-8011
Email:
Web page: http://www.kse.org.ua/
More information through EDIRC

For technical questions regarding this item, or to correct its listing, contact: (Andriy Zapechelnyuk).

Related research
Keywords: Regret minimization; no-regret strategy; best-response dynamic; Nash equilibrium; Shapley polygon; curb set;

Other versions of this item:

Find related papers by JEL classification:
C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Statistical Decision Theory; Operations Research
D81 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Criteria for Decision-Making under Risk and Uncertainty
D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search, Learning, and Information

This paper has been announced in the following NEP Reports:

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.:
  1. Basu, Kaushik & Weibull, Jorgen W., 1991. "Strategy subsets closed under rational behavior," Economics Letters, Elsevier, vol. 36(2), pages 141-146, June. [Downloadable!] (restricted)
    Other versions:
  2. Milgrom, Paul & Roberts, John, 1991. "Adaptive and sophisticated learning in normal form games," Games and Economic Behavior, Elsevier, vol. 3(1), pages 82-100, February. [Downloadable!] (restricted)
  3. Berger, Ulrich, 2005. "Fictitious play in 2 x n games," Journal of Economic Theory, Elsevier, vol. 120(2), pages 139-154, February. [Downloadable!] (restricted)
  4. Berger, Ulrich, 2007. "Two more classes of games with the continuous-time fictitious play property," Games and Economic Behavior, Elsevier, vol. 60(2), pages 247-261, August. [Downloadable!] (restricted)
  5. Ritzberger, Klaus & Weibull, Jorgen W, 1995. "Evolutionary Selection in Normal-Form Games," Econometrica, Econometric Society, vol. 63(6), pages 1371-99, November. [Downloadable!] (restricted)
  6. Blume Lawrence E., 1993. "The Statistical Mechanics of Strategic Interaction," Games and Economic Behavior, Elsevier, vol. 5(3), pages 387-424, July. [Downloadable!] (restricted)
  7. Lehrer, Ehud, 2003. "A wide range no-regret theorem," Games and Economic Behavior, Elsevier, vol. 42(1), pages 101-115, January. [Downloadable!] (restricted)
    Other versions:
  8. Hurkens Sjaak, 1995. "Learning by Forgetful Players," Games and Economic Behavior, Elsevier, vol. 11(2), pages 304-329, November. [Downloadable!] (restricted)
  9. Sparrow, Colin & van Strien, Sebastian & Harris, Christopher, 2008. "Fictitious play in 3x3 games: The transition between periodic and chaotic behaviour," Games and Economic Behavior, Elsevier, vol. 63(1), pages 259-291, May. [Downloadable!] (restricted)
  10. Freund, Yoav & Schapire, Robert E., 1999. "Adaptive Game Playing Using Multiplicative Weights," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 79-103, October. [Downloadable!] (restricted)
  11. Ed Hopkins, 2002. "Two Competing Models of How People Learn in Games," Econometrica, Econometric Society, vol. 70(6), pages 2141-2166, November. [Downloadable!] (restricted)
    Other versions:
  12. Sela, Aner, 2000. "Fictitious Play in 2 x 3 Games," Games and Economic Behavior, Elsevier, vol. 31(1), pages 152-162, April. [Downloadable!] (restricted)
  13. Fudenberg Drew & Kreps David M., 1993. "Learning Mixed Equilibria," Games and Economic Behavior, Elsevier, vol. 5(3), pages 320-367, July. [Downloadable!] (restricted)
    Other versions:
  14. Matros, Alexander, 2003. "Clever agents in adaptive learning," Journal of Economic Theory, Elsevier, vol. 111(1), pages 110-124, July. [Downloadable!] (restricted)
  15. Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January. [Downloadable!] (restricted)
  16. Matsui, Akihiko, 1992. "Best response dynamics and socially stable strategies," Journal of Economic Theory, Elsevier, vol. 57(2), pages 343-362, August. [Downloadable!] (restricted)
  17. Josef Hofbauer & William H. Sandholm, 2002. "On the Global Convergence of Stochastic Fictitious Play," Econometrica, Econometric Society, vol. 70(6), pages 2265-2294, November. [Downloadable!] (restricted)
  18. Monderer, Dov & Shapley, Lloyd S., 1996. "Fictitious Play Property for Games with Identical Interests," Journal of Economic Theory, Elsevier, vol. 68(1), pages 258-265, January. [Downloadable!] (restricted)
  19. Harris, Christopher, 1998. "On the Rate of Convergence of Continuous-Time Fictitious Play," Games and Economic Behavior, Elsevier, vol. 22(2), pages 238-259, February. [Downloadable!] (restricted)
  20. Lehrer, Ehud & Solan, Eilon, 2009. "Approachability with bounded memory," Games and Economic Behavior, Elsevier, vol. 66(2), pages 995-1004, July. [Downloadable!] (restricted)
  21. 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. [Downloadable!] (restricted)
    Other versions:
  22. Sergiu Hart & Andreu Mas-Colell, 2000. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Econometrica, Econometric Society, vol. 68(5), pages 1127-1150, September.
    Other versions:
  23. Gaunersdorfer Andrea & Hofbauer Josef, 1995. "Fictitious Play, Shapley Polygons, and the Replicator Equation," Games and Economic Behavior, Elsevier, vol. 11(2), pages 279-303, November. [Downloadable!] (restricted)
  24. Hofbauer, Josef & Hopkins, Ed, 2005. "Learning in perturbed asymmetric games," Games and Economic Behavior, Elsevier, vol. 52(1), pages 133-152, July. [Downloadable!] (restricted)
    Other versions:
  25. Hopkins, Ed, 1999. "A Note on Best Response Dynamics," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 138-150, October. [Downloadable!] (restricted)
    Other versions:
  26. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July. [Downloadable!] (restricted)
Full references

Statistics
Access and download statistics

Did you know? About five million pdf files are downloaded through RePEc every year.

This page was last updated on 2009-11-22.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.