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! ]

Global Nash Convergence of Foster and Young's Regret Testing

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Fabrizio Germano ()
Gábor Lugosi ()

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

Abstract

We construct an uncoupled randomized strategy of repeated play such that, if every player follows such a strategy, then the joint mixed strategy profiles converge, almost surely, to a Nash equilibrium of the one-shot game. The procedure requires very little in terms of players' information about the game. In fact, players' actions are based only on their own past payoffs and, in a variant of the strategy, players need not even know that their payoffs are determined through other players' actions. The procedure works for general finite games and is based on appropriate modifications of a simple stochastic learning rule introduced by Foster and Young.

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.econ.upf.edu/docs/papers/downloads/788.pdf
File Format: application/pdf
File Function: Whole Paper
Download Restriction: no

Publisher Info
Paper provided by Department of Economics and Business, Universitat Pompeu Fabra in its series Economics Working Papers with number 788.

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 2004
Date of revision:
Handle: RePEc:upf:upfgen:788

Contact details of provider:
Web page: http://www.econ.upf.edu/

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

Related research
Keywords: Regret testing; regret based learning; random search; stochastic dynamics; uncoupled dynamics; global convergence to Nash equilibria;

Other versions of this item:

Find related papers by JEL classification:
C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games
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. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May. [Downloadable!] (restricted)
  2. Hart, Sergiu & Mas-Colell, Andreu, 2006. "Stochastic uncoupled dynamics and Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 57(2), pages 286-303, November. [Downloadable!] (restricted)
    Other versions:
  3. 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. [Downloadable!] (restricted)
    Other versions:
  4. Kalai, Ehud & Lehrer, Ehud, 1993. "Rational Learning Leads to Nash Equilibrium," Econometrica, Econometric Society, vol. 61(5), pages 1019-45, September. [Downloadable!] (restricted)
    Other versions:
  5. Dekel, Eddie & Fudenberg, Drew & Levine, David K., 2004. "Learning to play Bayesian games," Games and Economic Behavior, Elsevier, vol. 46(2), pages 282-303, February. [Downloadable!] (restricted)
    Other versions:
  6. Drew Fudenberg & David K. Levine, 1993. "Steady State Learning and Nash Equilibrium," Levine's Working Paper Archive 373, David K. Levine. [Downloadable!]
    Other versions:
  7. Hart, Sergiu & Mas-Colell, Andreu, 2001. "A General Class of Adaptive Strategies," Journal of Economic Theory, Elsevier, vol. 98(1), pages 26-54, May. [Downloadable!] (restricted)
    Other versions:
  8. Amotz Cahn, 2004. "General procedures leading to correlated equilibria," International Journal of Game Theory, Springer, vol. 33(1), pages 21-40, January. [Downloadable!] (restricted)
  9. Sergiu Hart, 2004. "Adaptive Heuristics," Levine's Bibliography 122247000000000471, UCLA Department of Economics. [Downloadable!]
    Other versions:
  10. Foster, Dean P. & Vohra, Rakesh V., 1997. "Calibrated Learning and Correlated Equilibrium," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 40-55, October. [Downloadable!] (restricted)
  11. Jordan J. S., 1995. "Bayesian Learning in Repeated Games," Games and Economic Behavior, Elsevier, vol. 9(1), pages 8-20, April. [Downloadable!] (restricted)
  12. Jordan, J. S., 1991. "Bayesian learning in normal form games," Games and Economic Behavior, Elsevier, vol. 3(1), pages 60-81, February. [Downloadable!] (restricted)
  13. Ritzberger, Klaus, 1994. "The Theory of Normal Form Games form the Differentiable Viewpoint," International Journal of Game Theory, Springer, vol. 23(3), pages 207-36.
  14. Drew Fudenberg & David K. Levine, 1996. "Consistency and Cautious Fictitious Play," Levine's Working Paper Archive 470, David K. Levine. [Downloadable!]
    Other versions:
  15. 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. [Downloadable!]
  16. 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:
  17. Blume, Lawrence E & Zame, William R, 1994. "The Algebraic Geometry of Perfect and Sequential Equilibrium," Econometrica, Econometric Society, vol. 62(4), pages 783-94, July. [Downloadable!] (restricted)
    Other versions:
  18. Hart, Sergiu & Mas-Colell, Andreu, 2003. "Regret-based continuous-time dynamics," Games and Economic Behavior, Elsevier, vol. 45(2), pages 375-394, November. [Downloadable!] (restricted)
    Other versions:
  19. Foster, Dean P. & Vohra, Rakesh, 1999. "Regret in the On-Line Decision Problem," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 7-35, October. [Downloadable!] (restricted)
Full references

Cited by:
(explanations, 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. Sergiu Hart & Andreu Mas-Colell, 2004. "Stochastic Uncoupled Dynamics and Nash Equilibrium," Economics Working Papers 783, Department of Economics and Business, Universitat Pompeu Fabra. [Downloadable!]
    Other versions:
  2. H. Peyton Young, 2007. "The Possible and the Impossible in Multi-Agent Learning," Economics Series Working Papers 304, University of Oxford, Department of Economics. [Downloadable!]
  3. H. Peyton Young, 2008. "Learning by Trial and Error," Economics Series Working Papers 384, University of Oxford, Department of Economics. [Downloadable!]
    Other versions:
  4. Vivaldo M. Mendes & Diana A. Mendes & Orlando Gomes, 2008. "Learning to Play Nash in Deterministic Uncoupled Dynamics," Working Papers ercwp1808, ISCTE, UNIDE, Economics Research Centre. [Downloadable!]
  5. Dean P Foster & Peyton Young, 2006. "Regret Testing Leads to Nash Equilibrium," Levine's Working Paper Archive 784828000000000676, David K. Levine. [Downloadable!]
  6. Sergiu Hart & Yishay Mansour, 2006. "The Communication Complexity of Uncoupled Nash Equilibrium Procedures," Levine's Bibliography 122247000000001299, UCLA Department of Economics. [Downloadable!]
    Other versions:
Statistics
Access and download statistics

Did you know? You can include your works in the database easily by uploading them on the Munich Personal RePEc Archive (MPRA) if you do not have access to an institutional RePEc archive.

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

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.