On the impossibility of achieving no regrets in repeated games
AbstractRegret-minimizing strategies for repeated games have been receiving increasing attention in the literature. These are simple adaptive behavior rules that lead to no regrets and, if followed by all players, exhibit nice convergence properties: the average play converges to correlated equilibrium, or even to Nash equilibrium in certain classes of games. However, the no-regret property relies on a strong assumption that each player treats her opponents as unresponsive and fully ignores the opponents’ possible reactions to her actions. We show that if at least one player is slightly responsive, it is impossible to achieve no regrets, and convergence results for regret minimization with responsive opponents are unknown.
Download InfoIf 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.
Bibliographic InfoArticle provided by Elsevier in its journal Journal of Economic Behavior & Organization.
Volume (Year): 81 (2012)
Issue (Month): 1 ()
Contact details of provider:
Web page: http://www.elsevier.com/locate/jebo
C73; D81; D83; Adaptive strategies; Regret minimization; Regret matching;
Find related papers by JEL classification:
- 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
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.:
- 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.
- Sergiu Hart, 2005.
Econometric Society, vol. 73(5), pages 1401-1430, 09.
- Lehrer, Ehud & Solan, Eilon, 2009. "Approachability with bounded memory," Games and Economic Behavior, Elsevier, vol. 66(2), pages 995-1004, July.
- Fudenberg, Drew & Levine, David, 1995.
"Consistency and Cautious Fictitious Play,"
3198694, Harvard University Department of Economics.
- S. Hart & A. Mas-Collel, 2010.
"A Simple Adaptive Procedure Leading to Correlated Equilibrium,"
Levine's Working Paper Archive
572, David K. Levine.
- Sergiu Hart & Andreu Mas-Colell, 2000. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Econometrica, Econometric Society, vol. 68(5), pages 1127-1150, September.
- Sergiu Hart & Andreu Mas-Colell, 1997. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Game Theory and Information 9703006, EconWPA, revised 24 Mar 1997.
- Sergiu Hart & Andreu Mas-Colell, 1996. "A simple adaptive procedure leading to correlated equilibrium," Economics Working Papers 200, Department of Economics and Business, Universitat Pompeu Fabra, revised Dec 1996.
- 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.
- Young, H. Peyton, 2004. "Strategic Learning and its Limits," OUP Catalogue, Oxford University Press, number 9780199269181.
- Lehrer, Ehud, 2003.
"A wide range no-regret theorem,"
Games and Economic Behavior,
Elsevier, vol. 42(1), pages 101-115, January.
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.