IDEAS home Printed from https://ideas.repec.org/a/gam/jgames/v10y2019i3p34-d262532.html
   My bibliography  Save this article

Generalized Backward Induction: Justification for a Folk Algorithm

Author

Listed:
  • Marek Mikolaj Kaminski

    (Department of Political Science and Mathematical Behavioral Sciences, University of California, 3151 Social Science Plaza, Irvine, CA 92697-5100, USA)

Abstract

I introduce axiomatically infinite sequential games that extend Kuhn’s classical framework. Infinite games allow for (a) imperfect information, (b) an infinite horizon, and (c) infinite action sets. A generalized backward induction (GBI) procedure is defined for all such games over the roots of subgames. A strategy profile that survives backward pruning is called a backward induction solution (BIS). The main result of this paper finds that, similar to finite games of perfect information, the sets of BIS and subgame perfect equilibria (SPE) coincide for both pure strategies and for behavioral strategies that satisfy the conditions of finite support and finite crossing. Additionally, I discuss five examples of well-known games and political economy models that can be solved with GBI but not classic backward induction (BI). The contributions of this paper include (a) the axiomatization of a class of infinite games, (b) the extension of backward induction to infinite games, and (c) the proof that BIS and SPEs are identical for infinite games.

Suggested Citation

  • Marek Mikolaj Kaminski, 2019. "Generalized Backward Induction: Justification for a Folk Algorithm," Games, MDPI, vol. 10(3), pages 1-25, August.
    • Handle: RePEc:gam:jgames:v:10:y:2019:i:3:p:34-:d:262532
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2073-4336/10/3/34/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2073-4336/10/3/34/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Kaminski, Marek M & Lissowski, Grzegorz & Swistak, Piotr, 1998. "The "Revival of Communism" or the Effect of Institutions?: The 1993 Polish Parliamentary Elections," Public Choice, Springer, vol. 97(3), pages 429-449, December.
    2. Bonanno, Giacomo, 1991. "The Logic of Rational Play in Games of Perfect Information," Economics and Philosophy, Cambridge University Press, vol. 7(1), pages 37-65, April.
    3. Thomas Romer & Howard Rosenthal, 1978. "Political resource allocation, controlled agendas, and the status quo," Public Choice, Springer, vol. 33(4), pages 27-43, December.
    4. Binmore, Ken, 1988. "Modeling Rational Players: Part II," Economics and Philosophy, Cambridge University Press, vol. 4(1), pages 9-55, April.
    5. Drew Fudenberg & David M. Kreps & David K. Levine, 2008. "On the Robustness of Equilibrium Refinements," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 5, pages 67-93, World Scientific Publishing Co. Pte. Ltd..
    6. Kohlberg, Elon & Mertens, Jean-Francois, 1986. "On the Strategic Stability of Equilibria," Econometrica, Econometric Society, vol. 54(5), pages 1003-1037, September.
    7. Schwalbe, Ulrich & Walker, Paul, 2001. "Zermelo and the Early History of Game Theory," Games and Economic Behavior, Elsevier, vol. 34(1), pages 123-137, January.
    8. Basu, Kaushik, 1988. "Strategic irrationality in extensive games," Mathematical Social Sciences, Elsevier, vol. 15(3), pages 247-260, June.
    9. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, April.
    10. Aliprantis, Charalambos D., 1999. "On the backward induction method," Economics Letters, Elsevier, vol. 64(2), pages 125-131, August.
    11. Basu, Kaushik, 1990. "On the Non-existence of a Rationality Definition for Extensive Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(1), pages 33-44.
    12. Binmore, Ken, 1987. "Modeling Rational Players: Part I," Economics and Philosophy, Cambridge University Press, vol. 3(2), pages 179-214, October.
    13. Jonathan Bendor & Piotr Swistak, 1998. "Evolutionary Equilibria: Characterization Theorems and Their Implications," Theory and Decision, Springer, vol. 45(2), pages 99-159, October.
    14. Heinrich von Stackelberg, 2011. "Market Structure and Equilibrium," Springer Books, Springer, number 978-3-642-12586-7, December.
    15. Rosenthal, Robert W., 1981. "Games of perfect information, predatory pricing and the chain-store paradox," Journal of Economic Theory, Elsevier, vol. 25(1), pages 92-100, August.
    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. Peter A. Streufert, 2023. "Dynamic Programming for Pure-Strategy Subgame Perfection in an Arbitrary Game," Papers 2302.03855, arXiv.org, revised Mar 2023.

    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. Battigalli, Pierpaolo, 1997. "On Rationalizability in Extensive Games," Journal of Economic Theory, Elsevier, vol. 74(1), pages 40-61, May.
    2. Weibull, Jörgen W., 1992. "An Introduction to Evolutionary Game Theory," Working Paper Series 347, Research Institute of Industrial Economics.
    3. Van Damme, Eric, 2002. "Strategic equilibrium," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 3, chapter 41, pages 1521-1596, Elsevier.
    4. Abhijit Banerjee & Jörgen W. Weibull & Ken Binmore, 1996. "Evolution and Rationality: Some Recent Game-Theoretic Results," International Economic Association Series, in: Beth Allen (ed.), Economics in a Changing World, chapter 4, pages 90-117, Palgrave Macmillan.
    5. John Hillas & Elon Kohlberg, 1996. "Foundations of Strategic Equilibrium," Game Theory and Information 9606002, University Library of Munich, Germany, revised 18 Sep 1996.
    6. Antonio Quesada, 2002. "Belief system foundations of backward induction," Theory and Decision, Springer, vol. 53(4), pages 393-403, December.
    7. 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.
    8. Graciela Kuechle, 2009. "What Happened To The Three‐Legged Centipede Game?," Journal of Economic Surveys, Wiley Blackwell, vol. 23(3), pages 562-585, July.
    9. Sent, Esther-Mirjam, 2004. "The legacy of Herbert Simon in game theory," Journal of Economic Behavior & Organization, Elsevier, vol. 53(3), pages 303-317, March.
    10. Asheim, G.B. & Dufwenberg, M., 1996. "Admissibility and Common Knowledge," Discussion Paper 1996-16, Tilburg University, Center for Economic Research.
    11. Asheim, Geir B., 2002. "On the epistemic foundation for backward induction," Mathematical Social Sciences, Elsevier, vol. 44(2), pages 121-144, November.
    12. Hubie Chen, 2013. "Bounded rationality, strategy simplification, and equilibrium," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 593-611, August.
    13. Takahashi, Satoru & Tercieux, Olivier, 2020. "Robust equilibrium outcomes in sequential games under almost common certainty of payoffs," Journal of Economic Theory, Elsevier, vol. 188(C).
    14. Velu, C. & Iyer, S., 2008. "The Rationality of Irrationality for Managers: Returns- Based Beliefs and the Traveller’s Dilemma," Cambridge Working Papers in Economics 0826, Faculty of Economics, University of Cambridge.
    15. Jean-Pierre Dupuy, 1989. "Convention et Common knowledge," Revue Économique, Programme National Persée, vol. 40(2), pages 361-400.
    16. Sexton, Richard J., 1991. "Game Theory: A Review With Applications To Vertical Control In Agricultural Markets," Working Papers 225865, University of California, Davis, Department of Agricultural and Resource Economics.
    17. Spenkuch, Jörg, 2014. "Backward Induction in the Wild: Evidence from the U.S. Senate," MPRA Paper 58766, University Library of Munich, Germany.
    18. Burkhard C. Schipper & Hang Zhou, 2022. "Level-k Thinking in the Extensive Form," Working Papers 352, University of California, Davis, Department of Economics.
    19. Dekel, Eddie & Siniscalchi, Marciano, 2015. "Epistemic Game Theory," Handbook of Game Theory with Economic Applications,, Elsevier.
    20. Gagen, Michael, 2013. "Isomorphic Strategy Spaces in Game Theory," MPRA Paper 46176, University Library of Munich, Germany.

    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:gam:jgames:v:10:y:2019:i:3:p:34-:d:262532. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.