On the Impossibility of Regret Minimization in Repeated Games
AbstractRegret minimizing strategies for repeated games have been receiving increasing attention in the literature. These are simple adaptive behavior rules that exhibit nice convergence properties. If all players follow regret minimizing strategies, their average joint play converges to the set of correlated equilibria or to the Hannan set (depending on the notion of regret in use), or even to Nash equilibrium on certain classes of games. In this note we raise the question of validity of the regret minimization objective. By example we show that regret minimization can lead to unrealistic behavior, since it fails to take into account the effect of one's actions on subsequent behavior of the opponents. An amended notion of regret that corrects this defect is not very useful either, since achieving a no-regret objective is not guaranteed in that case.
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 InfoPaper provided by Queen Mary, University of London, School of Economics and Finance in its series Working Papers with number 676.
Date of creation: Dec 2010
Date of revision:
Repeated games; Regret minimization; No-regret strategy;
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
This paper has been announced in the following NEP Reports:
- NEP-ALL-2011-01-16 (All new papers)
- NEP-GTH-2011-01-16 (Game Theory)
- NEP-HPE-2011-01-16 (History & Philosophy of Economics)
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.:
- Lehrer, Ehud, 2003.
"A wide range no-regret theorem,"
Games and Economic Behavior,
Elsevier, vol. 42(1), pages 101-115, January.
- Sergiu Hart, 2005.
Econometric Society, vol. 73(5), pages 1401-1430, 09.
- N. Littlestone & M. Warmuth, 2010. "The Weighted Majority Algorithm," Levine's Working Paper Archive 575, David K. Levine.
- Lehrer, Ehud & Solan, Eilon, 2009. "Approachability with bounded memory," Games and Economic Behavior, Elsevier, vol. 66(2), pages 995-1004, July.
- Sergiu Hart & Andreu Mas-Colell, 2000.
"A Simple Adaptive Procedure Leading to Correlated Equilibrium,"
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.
- Sergiu Hart & Andreu Mas-Colell, 1997. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Game Theory and Information 9703006, EconWPA, revised 24 Mar 1997.
- S. Hart & A. Mas-Collel, 2010. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Levine's Working Paper Archive 572, David K. Levine.
- 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.
- Hart, Sergiu & Mas-Colell, Andreu, 2001.
"A General Class of Adaptive Strategies,"
Journal of Economic Theory,
Elsevier, vol. 98(1), pages 26-54, May.
- Sergiu Hart & Andreu Mas-Colell, 1999. "A General Class of Adaptive Strategies," Game Theory and Information 9904001, EconWPA, revised 23 Mar 2000.
- Sergiu Hart & Andreu Mas-Colell, 1999. "A general class of adaptative strategies," Economics Working Papers 373, Department of Economics and Business, Universitat Pompeu Fabra.
- D. Foster & R. Vohra, 2010. "Asymptotic Calibration," Levine's Working Paper Archive 468, David K. Levine.
- Young, H. Peyton, 2004. "Strategic Learning and its Limits," OUP Catalogue, Oxford University Press, number 9780199269181, September.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Nick Vriend).
If references are entirely missing, you can add them using this form.