On the Impossibility of Regret Minimization in Repeated Games
Regret 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.
|Date of creation:||Dec 2010|
|Contact details of provider:|| Postal: London E1 4NS|
Phone: +44 (0) 20 7882 5096
Fax: +44 (0) 20 8983 3580
Web page: http://www.econ.qmul.ac.uk
More information through EDIRC
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.:
- Sergiu Hart, 2013.
World Scientific Book Chapters,in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 11, pages 253-287
World Scientific Publishing Co. Pte. Ltd..
- Sergiu Hart, 2005. "Adaptive Heuristics," Econometrica, Econometric Society, vol. 73(5), pages 1401-1430, 09.
- Sergiu Hart, 2004. "Adaptive Heuristics," Discussion Paper Series dp372, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
- Sergiu Hart, 2004. "Adaptive Heuristics," Levine's Bibliography 122247000000000471, UCLA Department of Economics.
- 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 & 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.
- Sergiu Hart & Andreu Mas-Colell, 1997. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Game Theory and Information 9703006, EconWPA, revised 24 Mar 1997.
- Young, H. Peyton, 2004. "Strategic Learning and its Limits," OUP Catalogue, Oxford University Press, number 9780199269181, April.
- 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 adaptative strategies," Economics Working Papers 373, Department of Economics and Business, Universitat Pompeu Fabra.
- Sergiu Hart & Andreu Mas-Colell, 1999. "A General Class of Adaptive Strategies," Game Theory and Information 9904001, EconWPA, revised 23 Mar 2000.
- Lehrer, Ehud, 2003. "A wide range no-regret theorem," Games and Economic Behavior, Elsevier, vol. 42(1), pages 101-115, January.
- Ehud Lehrer & Dinah Rosenberg, 2003. "A Wide Range No-Regret Theorem," Game Theory and Information 0312004, EconWPA.
- Lehrer, Ehud & Solan, Eilon, 2009. "Approachability with bounded memory," Games and Economic Behavior, Elsevier, vol. 66(2), pages 995-1004, July.
- N. Littlestone & M. Warmuth, 2010. "The Weighted Majority Algorithm," Levine's Working Paper Archive 575, 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.
- D. Foster & R. Vohra, 2010. "Asymptotic Calibration," Levine's Working Paper Archive 468, David K. Levine. Full references (including those not matched with items on IDEAS)
When requesting a correction, please mention this item's handle: RePEc:qmw:qmwecw:wp676. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Nicholas Owen)
If references are entirely missing, you can add them using this form.