IDEAS home Printed from https://ideas.repec.org/p/wpa/wuwpga/0312004.html
   My bibliography  Save this paper

A Wide Range No-Regret Theorem

Author

Listed:
  • Ehud Lehrer

    (Tel Aviv U.)

  • Dinah Rosenberg

    (U. Paris Nord)

Abstract

In a sequential decision problem at any stage a decision maker, based on the history, takes a decision and receives a payoff which depends also on the realized state of nature. A strategy, f, is said to be as good as an alternative strategy g at a sequence of states, if in the long run f does, on average, at least as well as g does. It is shown that for any distribution, P, over the alternative strategies there is a strategy f which is, at any sequence of states, as good as P-almost any alternative g.

Suggested Citation

  • Ehud Lehrer & Dinah Rosenberg, 2003. "A Wide Range No-Regret Theorem," Game Theory and Information 0312004, University Library of Munich, Germany.
  • Handle: RePEc:wpa:wuwpga:0312004
    Note: Type of Document - pdf
    as

    Download full text from publisher

    File URL: https://econwpa.ub.uni-muenchen.de/econ-wp/game/papers/0312/0312004.pdf
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    as
    1. 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.
    2. Fudenberg, Drew & Levine, David K., 1999. "Conditional Universal Consistency," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 104-130, October.
    3. Sergiu Hart & Andreu Mas-Colell, 2000. "A Simple Adaptive Procedure Leading to Correlated Equilibrium," Econometrica, Econometric Society, vol. 68(5), pages 1127-1150, September.
    4. Nau, Robert F. & McCardle, Kevin F., 1990. "Coherent behavior in noncooperative games," Journal of Economic Theory, Elsevier, vol. 50(2), pages 424-444, April.
    5. Lehrer, E, 1989. "Lower Equilibrium Payoffs in Two-Player Repeated Games with Non-observable Actions," International Journal of Game Theory, Springer;Game Theory Society, vol. 18(1), pages 57-89.
    6. Ehud Lehrer, 2003. "Approachability in infinite dimensional spaces," International Journal of Game Theory, Springer;Game Theory Society, vol. 31(2), pages 253-268.
    7. Rustichini, Aldo, 1999. "Minimizing Regret: The General Case," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 224-243, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    2. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    3. repec:hal:wpaper:hal-00713871 is not listed on IDEAS
    4. repec:eee:jetheo:v:169:y:2017:i:c:p:145-169 is not listed on IDEAS
    5. Stoltz, Gilles & Lugosi, Gabor, 2007. "Learning correlated equilibria in games with compact sets of strategies," Games and Economic Behavior, Elsevier, vol. 59(1), pages 187-208, April.
    6. Schlag, Karl H. & Zapechelnyuk, Andriy, 2017. "Dynamic benchmark targeting," Journal of Economic Theory, Elsevier, vol. 169(C), pages 145-169.
    7. Karl Schlag & Andriy Zapechelnyuk, 2010. "On the Impossibility of Regret Minimization in Repeated Games," Working Papers 676, Queen Mary University of London, School of Economics and Finance.
    8. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    9. Dario Bauso & Hamidou Tembine & Tamer Ba┼čar, 2016. "Robust Mean Field Games," Dynamic Games and Applications, Springer, vol. 6(3), pages 277-303, September.
    10. Yuichi Noguchi, 2009. "Note on universal conditional consistency," International Journal of Game Theory, Springer;Game Theory Society, vol. 38(2), pages 193-207, June.
    11. Hu, Tai Wei & Shmaya, Eran, 2013. "Expressible inspections," Theoretical Economics, Econometric Society, vol. 8(2), May.
    12. Lehrer, Ehud & Solan, Eilon, 2009. "Approachability with bounded memory," Games and Economic Behavior, Elsevier, vol. 66(2), pages 995-1004, July.
    13. Ehud Lehrer & Eilon Solan, 2003. "No-Regret with Bounded Computational Capacity," Discussion Papers 1373, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    14. Mannor, Shie & Shimkin, Nahum, 2008. "Regret minimization in repeated matrix games with variable stage duration," Games and Economic Behavior, Elsevier, vol. 63(1), pages 227-258, May.
    15. Schlag, Karl & Zapechelnyuk, Andriy, 2012. "On the impossibility of achieving no regrets in repeated games," Journal of Economic Behavior & Organization, Elsevier, vol. 81(1), pages 153-158.

    More about this item

    Keywords

    No-regret; Approachability; large spaces;

    JEL classification:

    • C7 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory
    • D8 - Microeconomics - - Information, Knowledge, and Uncertainty

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wpa:wuwpga:0312004. 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: (EconWPA). General contact details of provider: https://econwpa.ub.uni-muenchen.de .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.