×

Generalized backward induction: justification for a folk algorithm. (English) Zbl 1435.91027

Summary: 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.

MSC:

91A20 Multistage and repeated games
91A18 Games in extensive form
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zermelo, E.; Über Eine Anwendung Der Mengenlehre Auf Die Theorie Des Schachspiels; Proceedings of the Fifth International Congress of Mathematicians: Cambridge, UK 1913; Volume Volume 2 ,501-504. · JFM 44.0092.04
[2] Schwalbe, U.; Walker, P.; Zermelo and the Early History of Game Theory; Games Econ. Behav.: 2001; Volume 34 ,123-137. · Zbl 0978.91002
[3] Von Stackelberg, H.; ; Market Structure and Equilibrium (Marktform Und Gleichgewicht): New York, NY, USA 2011; . · Zbl 1405.91003
[4] Von Neumann, J.; Morgenstern, O.; ; Theory of Games and Economic Behavior: Princeton, NJ, USA 1944; . · Zbl 0063.05930
[5] Von Neumann, J.; Zür Theorie Der Gesellschaftsspiele; Math. Ann.: 1928; Volume 100 ,295-320. · JFM 54.0543.02
[6] Kuhn, H.; Extensive Games and the Problem of Information; Contributions to the Theory of Games I: Princeton, NJ, USA 1953; ,193-216. · Zbl 0050.14303
[7] Schelling, T.C.; ; The Strategy of Conflict: Cambridge, MA, USA 1960; . · Zbl 1110.91001
[8] Selten, R.; Spieltheoretische Behandlung Eines Oligopolmodells Mit Nachfrageträgheit: Teil i: Bestimmung Des Dynamischen Preisgleichgewichts. Zeitschrift für die gesamte Staatswissenschaft; J. Inst. Theor. Econ.: 1965; Volume 2 ,301-324.
[9] Rosenthal, R.W.; Games of Perfect Information, Predatory Pricing and the Chain-Store Paradox; J. Econ. Theory: 1981; Volume 25 ,92-100. · Zbl 0467.90084
[10] Selten, R.; The Chain Store Paradox; Theory Decis.: 1978; Volume 9 ,127-159. · Zbl 0374.90085
[11] Selten, R.; Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games; Int. J. Game Theory: 1975; Volume 4 ,25-55. · Zbl 0312.90072
[12] Kreps, D.M.; Wilson, R.; Sequential Equilibria; Econometrica: 1982; Volume 50 ,863-894. · Zbl 0483.90092
[13] Kohlberg, E.; Mertens, J.-F.; On the Strategic Stability of Equilibria; Econometrica: 1986; Volume 54 ,1003-1037. · Zbl 0616.90103
[14] Basu, K.; Strategic Irrationality in Extensive Games; Math. Soc. Sci.: 1988; Volume 15 ,247-260. · Zbl 0658.90110
[15] Basu, K.; On the Non-Existence of a Rationality Definition for Extensive Games; Int. J. Game Theory: 1990; Volume 19 ,33-44. · Zbl 0708.90093
[16] Bicchieri, C.; Self-Refuting Theories of Strategic Interaction: A Paradox of Common Knowledge; Philosophy of Economics: New York, NY, USA 1989; ,69-85.
[17] Binmore, K.; Modeling Rational Players: Part I; Econ. Philos.: 1987; Volume 3 ,179-214.
[18] Binmore, K.; Modeling Rational Players: Part II; Econ. Philos.: 1988; Volume 4 ,9-55.
[19] Bonanno, G.; The Logic of Rational Play in Games of Perfect Information; Econ. Philos.: 1991; Volume 7 ,37-65.
[20] Fudenberg, D.; Kreps, D.M.; Levine, D.K.; On the Robustness of Equilibrium Refinements; J. Econ. Theory: 1988; Volume 44 ,354-380. · Zbl 0659.90097
[21] Pettit, P.; Sugden, R.; The Backward Induction Paradox; J. Philos.: 1989; Volume 86 ,169-182.
[22] Reny, P.; ; Rationality, Common Knowledge and the Theory of Games: Princeton, NJ, USA 1988; .
[23] Aliprantis, C.D.; On the Backward Induction Method; Econ. Lett.: 1999; Volume 64 ,125-131. · Zbl 1016.91003
[24] Schelling, T.C.; ; Personal communication: 2008; .
[25] Fudenberg, D.; Tirole, J.; ; Game Theory: Cambridge, MA, USA 1991; . · Zbl 1339.91001
[26] Myerson, R.B.; ; Game Theory: Cambridge, MA, USA 2013; .
[27] Osborne, M.J.; Rubinstein, A.; ; A Course in Game Theory: Cambridge, MA, USA 1994; . · Zbl 1194.91003
[28] Escardò, M.H.; Oliva, P.; Computing Nash Equilibria of Unbounded Games; Turing-100: 2012; Volume 10 ,53-65.
[29] Neyman, A.; Sorin, S.; ; Stochastic Games and Applications: Dordrecht, The Netherlands 2003; . · Zbl 1027.00040
[30] Aumann, R.J.; ; Mixed and Behavior Strategies in Infinite Extensive Games: Princeton, NJ, USA 1961; . · Zbl 0189.20302
[31] Nash, J.; Non-Cooperative Games; Ann. Math.: 1951; Volume 54 ,286-295. · Zbl 0045.08202
[32] Bendor, J.; Swistak, P.; Evolutionary Equilibria: Characterization Theorems and Their Implications; Theory Decis.: 1998; Volume 45 ,99-159. · Zbl 0912.90281
[33] Flood, M.M.; ; Some Experimental Games: Santa Monica, CA, USA 1952; . · Zbl 0995.91505
[34] Brams, S.J.; Taylor, A.D.; ; Fair Division: From Cake-Cutting to Dispute Resolution: Cambridge, UK 1996; . · Zbl 0991.91019
[35] Steinhaus, H.; The Problem of Fair Division; Econometrica: 1948; Volume 16 ,101-104.
[36] Romer, T.; Rosenthal, H.; Political Resource Allocation, Controlled Agendas, and the Status Quo; Public Choice: 1978; Volume 33 ,27-43.
[37] Kaminski, M.M.; Nalepa, M.; A Model of Strategic Preemption: Why Do Post-Communists Hurt Themselves?; Decisions: 2014; Volume 21 ,31-65.
[38] Kaminski, M.M.; Lissowski, G.; Swistak, P.; The “Revival of Communism” or the Effect of Institutions? The 1993 Polish Parliamentary Elections; Public Choice: 1998; Volume 97 ,429-449.
[39] Farquharson, R.; ; Theory of Voting: Hoboken, NJ, USA 1969; .
[40] Riker, W.H.; ; The Art of Political Manipulation: New Haven, CT, USA 1986; .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.