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.
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.:
- Drew Fudenberg & David K. Levine, 1996.
"Consistency and Cautious Fictitious Play,"
Levine's Working Paper Archive
470, David K. Levine.
- Sergiu Hart, 2004.
122247000000000471, UCLA Department of Economics.
- 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.
- 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, 2000. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Econometrica, Econometric Society, vol. 68(5), pages 1127-1150, September.
- 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.
- S. Hart & A. Mas-Collel, 2010. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Levine's Working Paper Archive 572, David K. Levine.
- 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.
- Lehrer, Ehud & Solan, Eilon, 2009. "Approachability with bounded memory," Games and Economic Behavior, Elsevier, vol. 66(2), pages 995-1004, July.
- Lehrer, Ehud, 2003.
"A wide range no-regret theorem,"
Games and Economic Behavior,
Elsevier, vol. 42(1), pages 101-115, January.
- Young, H. Peyton, 2004. "Strategic Learning and its Limits," OUP Catalogue, Oxford University Press, number 9780199269181.
If references are entirely missing, you can add them using this form.