IDEAS home Printed from https://ideas.repec.org/a/spr/dyngam/v10y2020i1d10.1007_s13235-019-00301-7.html
   My bibliography  Save this article

A Semi-Potential for Finite and Infinite Games in Extensive Form

Author

Listed:
  • Stéphane Le Roux

    (Université Paris-Saclay)

  • Arno Pauly

    (Swansea University)

Abstract

We consider a dynamic approach to games in extensive forms. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite sequential games the corresponding restriction of better-response dynamics will converge to a Nash equilibrium in quadratic time. Convergence happens on a per-player basis, and even in the presence of players with cyclic preferences, the players with acyclic preferences will stabilize. Thus, we obtain a candidate notion for rationality in the presence of irrational agents. Moreover, the restriction of convertibility can be justified by a conservative updating of beliefs about the other players strategies. For infinite games in extensive form we can retain convergence to a Nash equilibrium (in some sense), if the preferences are given by continuous payoff functions; or obtain a transfinite convergence if the outcome sets of the game are $$\Delta ^0_2$$Δ20-sets.

Suggested Citation

  • Stéphane Le Roux & Arno Pauly, 2020. "A Semi-Potential for Finite and Infinite Games in Extensive Form," Dynamic Games and Applications, Springer, vol. 10(1), pages 120-144, March.
    • Handle: RePEc:spr:dyngam:v:10:y:2020:i:1:d:10.1007_s13235-019-00301-7
    DOI: 10.1007/s13235-019-00301-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13235-019-00301-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13235-019-00301-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Solan, Eilon & Vieille, Nicolas, 2003. "Deterministic multi-player Dynkin games," Journal of Mathematical Economics, Elsevier, vol. 39(8), pages 911-929, November.
    2. Fudenberg, Drew & Levine, David K, 1993. "Self-Confirming Equilibrium," Econometrica, Econometric Society, vol. 61(3), pages 523-545, May.
    3. MERTENS, Jean-François, 1987. "Repeated games. Proceedings of the International Congress of Mathematicians," LIDAM Reprints CORE 788, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. 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..
    5. Roth, Alvin E. & Erev, Ido, 1995. "Learning in extensive-form games: Experimental data and simple dynamic models in the intermediate term," Games and Economic Behavior, Elsevier, vol. 8(1), pages 164-212.
    6. Xu, Zibo, 2013. "Convergence of best response dynamics in extensive-form games," SSE/EFI Working Paper Series in Economics and Finance 745, Stockholm School of Economics, revised 28 Jun 2013.
    7. Nikolai Kukushkin, 2011. "Acyclicity of improvements in finite game forms," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(1), pages 147-177, February.
    8. Kukushkin, Nikolai S., 2002. "Perfect Information and Potential Games," Games and Economic Behavior, Elsevier, vol. 38(2), pages 306-317, February.
    9. Cressman, R. & Schlag, K. H., 1998. "The Dynamic (In)Stability of Backwards Induction," Journal of Economic Theory, Elsevier, vol. 83(2), pages 260-285, December.
    10. Aumann, Robert J., 1995. "Backward induction and common knowledge of rationality," Games and Economic Behavior, Elsevier, vol. 8(1), pages 6-19.
    11. Robert Aumann & Adam Brandenburger, 2014. "Epistemic Conditions for Nash Equilibrium," World Scientific Book Chapters, in: The Language of Game Theory Putting Epistemics into the Mathematics of Games, chapter 5, pages 113-136, World Scientific Publishing Co. Pte. Ltd..
    12. Ross Cressman, 2003. "Evolutionary Dynamics and Extensive Form Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262033054, December.
    13. Nikolai Kukushkin, 2011. "Nash equilibrium in compact-continuous games with a potential," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(2), pages 387-392, May.
    Full references (including those not matched with items on IDEAS)

    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. Zibo Xu, 2013. "The instability of backward induction in evolutionary dynamics," Discussion Paper Series dp633, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    2. Dekel, Eddie & Siniscalchi, Marciano, 2015. "Epistemic Game Theory," Handbook of Game Theory with Economic Applications,, Elsevier.
    3. Xiao Luo & Ben Wang, 2022. "An epistemic characterization of MACA," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 73(4), pages 995-1024, June.
    4. Lindgren, Kristian & Verendel, Vilhelm, 2013. "Evolutionary Exploration of the Finitely Repeated Prisoners' Dilemma--The Effect of Out-of-Equilibrium Play," MPRA Paper 43662, University Library of Munich, Germany.
    5. Jehiel, Philippe & Samet, Dov, 2005. "Learning to play games in extensive form by valuation," Journal of Economic Theory, Elsevier, vol. 124(2), pages 129-148, October.
    6. Weibull, Jörgen W., 1997. "What have we learned from Evolutionary Game Theory so far?," Working Paper Series 487, Research Institute of Industrial Economics, revised 26 Oct 1998.
    7. Kristian Lindgren & Vilhelm Verendel, 2013. "Evolutionary Exploration of the Finitely Repeated Prisoners’ Dilemma—The Effect of Out-of-Equilibrium Play," Games, MDPI, vol. 4(1), pages 1-20, January.
    8. Battigalli, Pierpaolo & Siniscalchi, Marciano, 2002. "Strong Belief and Forward Induction Reasoning," Journal of Economic Theory, Elsevier, vol. 106(2), pages 356-391, October.
    9. Ponti, Giovanni, 2000. "Cycles of Learning in the Centipede Game," Games and Economic Behavior, Elsevier, vol. 30(1), pages 115-141, January.
    10. Fudenberg, Drew & Levine, David K., 1999. "Conditional Universal Consistency," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 104-130, October.
    11. Kalai, Ehud & Lehrer, Ehud & Smorodinsky, Rann, 1999. "Calibrated Forecasting and Merging," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 151-169, October.
    12. Asheim, G.B. & Dufwenberg, M., 1996. "Admissibility and Common Knowledge," Discussion Paper 1996-16, Tilburg University, Center for Economic Research.
    13. Timothy Cason & Tridib Sharma, 2007. "Recommended play and correlated equilibria: an experimental study," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 33(1), pages 11-27, October.
    14. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    15. J. Kuipers & J. Flesch & G. Schoenmakers & K. Vrieze, 2016. "Subgame-perfection in recursive perfect information games, where each player controls one state," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 205-237, March.
    16. János Flesch & Arkadi Predtetchinski, 2020. "Parameterized games of perfect information," Annals of Operations Research, Springer, vol. 287(2), pages 683-699, April.
    17. Fudenberg, Drew & Takahashi, Satoru, 2011. "Heterogeneous beliefs and local information in stochastic fictitious play," Games and Economic Behavior, Elsevier, vol. 71(1), pages 100-120, January.
    18. Christoph Kuzmics & Daniel Rodenburger, 2020. "A case of evolutionarily stable attainable equilibrium in the laboratory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(3), pages 685-721, October.
    19. Joseph Y. Halpern & Rafael Pass, 2018. "Game theory with translucent players," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(3), pages 949-976, September.
    20. Funai, Naoki, 2022. "Reinforcement learning with foregone payoff information in normal form games," Journal of Economic Behavior & Organization, Elsevier, vol. 200(C), pages 638-660.

    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:spr:dyngam:v:10:y:2020:i:1:d:10.1007_s13235-019-00301-7. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.