IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v66y2009i2p995-1004.html
   My bibliography  Save this article

Approachability with bounded memory

Author

Listed:
  • Lehrer, Ehud
  • Solan, Eilon

Abstract

We study Blackwell's approachability in repeated games with vector payoffs when the approaching player is restricted to use strategies with bounded memory: either strategies with bounded recall, or strategies that can be implemented by finite automata. Our main finding is that the following three statements are equivalent for closed sets. (i) The set is approachable with bounded recall strategies. (ii) The set is approachable with strategies that can be implemented with finite automata. (iii) The set contains a convex approachable set. Using our results we show that (i) there are almost-regret-free strategies with bounded memory, (ii) there is a strategy with bounded memory to choose the best among several experts, and (iii) Hart and Mas-Colell's adaptive learning procedure can be achieved using strategies with bounded memory.

Suggested Citation

  • Lehrer, Ehud & Solan, Eilon, 2009. "Approachability with bounded memory," Games and Economic Behavior, Elsevier, vol. 66(2), pages 995-1004, July.
    • Handle: RePEc:eee:gamebe:v:66:y:2009:i:2:p:995-1004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00181-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ben-porath, Elchanan, 1990. "The complexity of computing a best response automaton in repeated games with mixed strategies," Games and Economic Behavior, Elsevier, vol. 2(1), pages 1-12, March.
    2. Neyman, Abraham, 1985. "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters, Elsevier, vol. 19(3), pages 227-229.
    3. Xavier Spinat, 2002. "A Necessary and Sufficient Condition for Approachability," Mathematics of Operations Research, INFORMS, vol. 27(1), pages 31-44, February.
    4. 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.
    5. Kalai, Ehud & Stanford, William, 1988. "Finite Rationality and Interpersonal Complexity in Repeated Games," Econometrica, Econometric Society, vol. 56(2), pages 397-410, March.
    6. Fudenberg, Drew & Levine, David K., 1999. "Conditional Universal Consistency," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 104-130, October.
    7. Lehrer, Ehud, 2003. "A wide range no-regret theorem," Games and Economic Behavior, Elsevier, vol. 42(1), pages 101-115, January.
    8. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    9. Ehud Lehrer & Eilon Solan, 2006. "Excludability and Bounded Computational Capacity," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 637-648, August.
    10. Watson Joel, 1994. "Cooperation in the Infinitely Repeated Prisoners' Dilemma with Perturbations," Games and Economic Behavior, Elsevier, vol. 7(2), pages 260-285, September.
    11. Lehrer, Ehud, 1988. "Repeated games with stationary bounded recall strategies," Journal of Economic Theory, Elsevier, vol. 46(1), pages 130-144, October.
    12. Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
    13. Ehud Lehrer & Eilon Solan, 2003. "Excludability and Bounded Computational Capacity Strategies," Discussion Papers 1374, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    14. Rustichini, Aldo, 1999. "Minimizing Regret: The General Case," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 224-243, October.
    15. Jeheil Phillippe, 1995. "Limited Horizon Forecast in Repeated Alternate Games," Journal of Economic Theory, Elsevier, vol. 67(2), pages 497-519, December.
    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. Fournier, Gaëtan & Kuperwasser, Eden & Munk, Orin & Solan, Eilon & Weinbaum, Avishay, 2021. "Approachability with constraints," European Journal of Operational Research, Elsevier, vol. 292(2), pages 687-695.
    2. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    3. Bavly, Gilad & Peretz, Ron, 2019. "Limits of correlation in repeated games with bounded memory," Games and Economic Behavior, Elsevier, vol. 115(C), pages 131-145.
    4. Lagziel, David & Lehrer, Ehud, 2015. "Approachability with delayed information," Journal of Economic Theory, Elsevier, vol. 157(C), pages 425-444.
    5. Carmona, G. & Sabourian, H., 2021. "Approachability with Discounting," Cambridge Working Papers in Economics 2124, Faculty of Economics, University of Cambridge.
    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, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    8. Rene Saran & Roberto Serrano, 2012. "Regret Matching with Finite Memory," Dynamic Games and Applications, Springer, vol. 2(1), pages 160-175, March.
    9. Du, Ye & Lehrer, Ehud, 2020. "Constrained no-regret learning," Journal of Mathematical Economics, Elsevier, vol. 88(C), pages 16-24.
    10. 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.
    11. Foster, Dean P. & Hart, Sergiu, 2018. "Smooth calibration, leaky forecasts, finite recall, and Nash dynamics," Games and Economic Behavior, Elsevier, vol. 109(C), pages 271-293.
    12. 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.
    13. Dario Bauso & Hamidou Tembine & Tamer Başar, 2016. "Robust Mean Field Games," Dynamic Games and Applications, Springer, vol. 6(3), pages 277-303, September.
    14. Andrey Bernstein & Shie Mannor & Nahum Shimkin, 2014. "Opportunistic Approachability and Generalized No-Regret Problems," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1057-1083, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. 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.
    2. 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.
    3. Ueda, Masahiko, 2023. "Memory-two strategies forming symmetric mutual reinforcement learning equilibrium in repeated prisoners’ dilemma game," Applied Mathematics and Computation, Elsevier, vol. 444(C).
    4. Aumann, Robert J., 1997. "Rationality and Bounded Rationality," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 2-14, October.
    5. Renault, Jérôme & Scarsini, Marco & Tomala, Tristan, 2008. "Playing off-line games with bounded rationality," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 207-223, September.
    6. Jehiel, Philippe, 1998. "Learning to Play Limited Forecast Equilibria," Games and Economic Behavior, Elsevier, vol. 22(2), pages 274-298, February.
    7. Sandroni, Alvaro & Smorodinsky, Rann, 2004. "Belief-based equilibrium," Games and Economic Behavior, Elsevier, vol. 47(1), pages 157-171, April.
    8. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    9. Andriy Zapechelnyuk, 2008. "Better-Reply Dynamics with Bounded Recall," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 869-879, November.
    10. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    11. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    12. Schlag, Karl H. & Zapechelnyuk, Andriy, 2017. "Dynamic benchmark targeting," Journal of Economic Theory, Elsevier, vol. 169(C), pages 145-169.
    13. Ehud Lehrer & Eilon Solan, 2016. "A General Internal Regret-Free Strategy," Dynamic Games and Applications, Springer, vol. 6(1), pages 112-138, March.
    14. Lehrer, Ehud, 2003. "A wide range no-regret theorem," Games and Economic Behavior, Elsevier, vol. 42(1), pages 101-115, January.
    15. Foster, Dean P. & Young, H. Peyton, 2003. "Learning, hypothesis testing, and Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 45(1), pages 73-96, October.
    16. 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.
    17. Compte, Olivier & Postlewaite, Andrew, 2015. "Plausible cooperation," Games and Economic Behavior, Elsevier, vol. 91(C), pages 45-59.
    18. Daniel Monte & Maher Said, 2014. "The value of (bounded) memory in a changing world," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(1), pages 59-82, May.
    19. Ehud Lehrer & Eilon Solan, 2006. "Excludability and Bounded Computational Capacity," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 637-648, August.
    20. Olivier Gossner & Penélope Hernández, 2003. "On the Complexity of Coordination," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 127-140, February.

    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:eee:gamebe:v:66:y:2009:i:2:p:995-1004. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.