## 1. Introduction

- (1)
- Prune (remove) any subset of disjoint subgames instead of a single subgame, which would have only one decision node followed by terminal nodes.
- (2)
- Substitute all selected subgames with the SPE payoffs instead of the payoffs for best moves.
- (3)
- Concatenate all partial strategy profiles obtained in the previous step; if at any point one gets an empty set, this would mean that there is no SPE in the game.

## 2. Preliminaries

- AT1 (partial anti-reflexivity): For all $x\in T,$ $(x,x)\in \mathsf{\Psi}$ iff $x=\tau $;
- AT2 (symmetry): For all $x,y\in T$ $(x,y)\in \mathsf{\Psi}$ iff $(y,x)\in \mathsf{\Psi}$;
- AT3 (unique path): For every $x\in T$, there is exactly one path ${e}_{x}$ to x.

**Definition**

**1.**

- Game tree: $\mathsf{\Psi}$ is a rooted tree with a set of nodes T, a set of decision nodes ${T}_{D}$, a set of endnodes ${T}_{E}$, and the root $\tau $;
- Players: For a positive integer n, ${N}^{0}=\{0,1,\dots ,n\}$ consists of players $N=\{1,\dots ,n\}$ and nature—a random or pseudorandom mechanism, labeled with 0;
- Player partition:${\left\{{T}_{i}\right\}}_{i\in {N}^{0}}$ is the partition of ${T}_{D}$ into (possibly empty) subses ${T}_{i}$ and a (possibly empty) subset ${T}_{0}$ for nature. The following assumptions are made regarding ${T}_{0}$:
- (i)
- There is no path that includes an infinite number of nodes from ${T}_{0}$; 1‘
- (ii)
- For every $x\in {T}_{0}$, the number of alternatives at x is greater or equal two and finite.

- Information:$I={\left\{{I}_{i}\right\}}_{i=0}^{n}$ is such that every ${I}_{i}={\left\{{I}_{i}^{k}\right\}}_{k\in {K}_{i}}$ is a partition of i’s set ${T}_{i}$. We assume the following:
- (i)
- All elements of ${I}_{0}$ are singletons;
- (ii)
- For all $i\in N$, every element of ${I}_{i}$ includes only nodes with equal numbers (or cardinalities) of alternatives and does not include two nodes that are in the same path;
- (iii)
- (Perfect Recall): If ${x}_{i}$ is a successor of ${x}_{j}$ and ${x}_{k}$ is in the same information set with ${x}_{i}$, then ${x}_{i}$ and ${x}_{k}$ must be immediate successors of either ${x}_{j}$ or some other node ${x}_{l}$ that is a successor of ${x}_{j}$.For every $i\in {N}^{0}$, a set ${I}_{i}^{k}\in {I}_{i}$ is called i’s information set. A node y originates from the information set ${I}_{i}^{k}$ if y originates at a node $x\in {I}_{i}^{k}$.

- Moves (actions): $A={\left\{{A}_{i}^{k}\right\}}_{i\in N,k\in {K}_{i}}$ is a collection of partitions, one for every information set ${I}_{i}^{k}$ of every player i, of all alternatives originating at ${I}_{i}^{k}$, such that for any node $x\in {I}_{i}^{k}$, every member of ${A}_{i}^{k}$ includes exactly one alternative that originates at x. The elements $a\in {A}_{i}^{k}$ are called the moves (or actions) of i at ${I}_{i}^{k}.$ For any ${I}_{0}^{k}$, the moves at ${I}_{0}^{k}$ are singletons, including branches originating at ${I}_{0}^{k}$. By definition, since every branch y belongs to precisely one move, for $y\in T-\left\{\tau \right\}$ the move a such that $y\in a$ is denoted by ${A}_{i}^{k}\left(y\right)$.
- Random moves: h is a function that assigns to every information set of the random mechanism ${I}_{0}^{k}=\left\{x\right\}$ a probability distribution $\left\{{h}^{k}\right\}$ over the alternatives at x, with all probabilities being positive. If ${T}_{0}=\varnothing ,$ h is not defined.
- Payoffs (associated with terminal paths): The payoff function $P=({P}_{1},\dots ,$ ${P}_{n}):N\times {T}_{t}\to \mathbb{R}$ assigns to every terminal path $e\in {T}_{t}$ a payoff vector at e equal to $P\left(e\right)=({P}_{1}\left(e\right),\dots ,$ ${P}_{n}\left(e\right))$. The component ${P}_{i}\left(e\right)$ is called the payoff of player i at e. Function ${P}_{i}$ is called the payoff function of player i.

- (i)
- ${\mathsf{\Psi}}^{\prime}$ is a subtree of $\mathsf{\Psi}$, i.e., for some ${\tau}^{\prime}\in T$, ${T}^{\prime}=\{x\in T:x={\tau}^{\prime}$ or $x\in SU\left({\tau}^{\prime}\right)\}$ and ${\mathsf{\Psi}}^{\prime}=(\mathsf{\Psi}\cap [{T}^{\prime}\times {T}^{\prime}])\cup \left\{({\tau}^{\prime},{\tau}^{\prime})\right\}$;
- (ii)
- If ${x}_{1},{x}_{2}\in {I}_{i}^{k}$ for some ${I}_{i}^{k}$ in G, then either $\{{x}_{1},{x}_{2}\}\subset {T}^{\prime}$ or $\{{x}_{1},{x}_{2}\}\cap {T}^{\prime}=\varnothing $ (either both ${x}_{1}$ and ${x}_{2}$ are in ${T}^{\prime}$ or neither is);
- (iii)
- The sets of players are identical (${N}^{0}$) and ${\left\{{T}_{i}^{\prime}\right\}}_{i\in {N}^{0}},$ ${I}^{\prime},$ ${A}^{\prime},$ ${h}^{\prime},$ ${P}^{\prime}$ are restrictions of ${\left\{{T}_{i}\right\}}_{i\in {N}^{0}},$ $I,$ $A,$ $h,$ P to ${T}^{\prime}$, respectively.

**Lemma**

**1.**

- (a)
- the set of all terminal paths in H included in ${\mathit{\beta}}^{H}$, ${T}_{{\beta}^{H}}$, is non-empty and finite;
- (b)
- for every ${e}^{H}\in {T}_{t}^{H}$, ${p}_{\beta}^{H}\left({e}^{H}\right)>0$ iff ${e}^{H}\in {T}_{{\beta}^{H}}$;
- (c)
- ${\mathsf{\Sigma}}_{e\in {T}_{{\beta}^{H}}}{p}_{{\beta}^{H}}\left(e\right)=1$.

- ${\mathit{\beta}}^{H}$ is $\mathit{\beta}$ reduced to H if ${\mathit{\beta}}^{H}={\cup}_{i=1}^{n}{\beta}_{i}^{H}$;
- ${\mathit{\beta}}_{i}^{-H}$ is a complement of ${\mathit{\beta}}_{i}$ with respect to H if ${\beta}_{i}^{-H}={\beta}_{i}-{\beta}_{i}^{H}$;
- ${\mathit{\beta}}^{-H}={\cup}_{i=1}^{n}{\beta}_{i}^{-H}$ is a complement of $\mathit{\beta}$ with respect to $H;$
- ${B}_{i}^{-H}$ is the set of all ${\beta}_{i}^{-H}$ for all ${\beta}_{i}\in {B}_{i}$;
- ${B}^{-H}={\times}_{i=1}^{n}{B}_{i}^{-H}$.

**Lemma**

**2.**

- Nash equilibrium (NE): For every $i\in N$, ${\beta}_{i}\in ArgMa{x}_{{t}_{i}\in {B}_{i}}{P}_{i}({\mathit{\beta}}_{-i},{t}_{i})$;
- Subgame perfect equilibrium (SPE): For every subgame H, ${\mathit{\beta}}^{H}$ is an NE in H.

## 3. Decomposition of Strategies

- ${T}_{s(G-H)}=\{e\in {T}_{s}$ such that $\varphi \notin e\}$;
- ${T}_{s\left(H\right)}=\{e\in {T}_{s}$ such that $\varphi \in e\}$.

**Lemma**

**3.**

**Lemma**

**4.**

**Theorem**

**1.**

- (a)
- $\mathbf{s}$is an SPE for G;
- (b)
- ${\mathbf{s}}^{H}$is an SPE for H, and ${\mathbf{s}}^{-H}$ is an SPE for F.

**Lemma**

**5.**

**Theorem**

**2.**

- (a)
- $\mathbf{s}$is an SPE for G;
- (b)
- ${\mathbf{s}}^{F}$is an SPE for F, and for all $\theta \in \mathsf{\Theta}$, ${\mathbf{s}}^{{H}_{\theta}}$ is an SPE for ${H}_{\theta}$.

## 4. Generalized backward Induction (GBI) Algorithm

**Corollary**

**1.**

- (i)
- ${\mathbf{s}}^{{\mathsf{\Theta}}_{j+1}}$ is an SPE for all ${\left\{{H}_{\theta}\right\}}_{\theta \in {\mathsf{\Theta}}_{j+1}}$. In such a case, include ${\mathbf{s}}_{j}^{k}\cup $ ${\mathbf{s}}^{{\mathsf{\Theta}}_{j+1}}$ in ${S}_{j+1}^{SPE}$;
- (ii)
- ${\mathbf{s}}^{{\mathsf{\Theta}}_{j+1}}$ is not an SPE for at least one of ${\left\{{H}_{\theta}\right\}}_{\theta \in {\mathsf{\Theta}}_{j+1}}$. In such a case, discard ${\mathbf{s}}_{j}^{k}\cup {\mathbf{s}}^{{\mathsf{\Theta}}_{j+1}}$.

## 5. Examples

#### 5.1. Complex Finite Games with Perfect Information

**Example**

**1.**

#### 5.2. Continuum of Actions and Perfect Information

**Example**

**2.**

#### 5.3. Finitely Repeated Games

**Corollary**

**2.**

**Example**

**3.**

#### 5.4. Parametrized Games in Political Economy

**Example**

**4.**

- Period 1: P is the ruling party and can choose between the status quo of no lustration (0) and a moderate amount of lustration, m, which is the ideal point of M;
- Period 2: Parliamentary elections take place and a new parliamentary median is elected with the following probabilities (for the extreme parties A and P, being a median is the equivalent of winning the majority):
- A: ${p}_{1}$;
- M: ${p}_{2}$;
- P: $(1-{p}_{1}-{p}_{2})$.

- Period 3: If P is the new median, then they do not introduce any new legislation, since any change, including reverting to 0, would result in an unacceptable loss of credibility in the eyes of their electorate.
- If A is the new median, then they can choose any law.
- If M is the new median, they coalesce with the larger partner A. M’s approval is necessary for any new law. If the existing legislation is 0, A proposes new legislation and then M must either accept or reject it. If the existing legislation is m, A proposes no new legislation, anticipating that it will not receive M’s support.

- Period 4 (only if M is the new median and the existing legislation is 0): M either accepts A’s proposal or the status quo prevails.

- ${\mathsf{\Pi}}_{P}=\{0,m\}$;
- ${\mathsf{\Pi}}_{A}={[0,1]}^{3}$;
- ${\mathsf{\Pi}}_{M}={2}^{(0,1]}$.

- 1 and 2: If A wins the majority, they propose the harshest lustration 1.
- 3: If M is the median and the status quo is 0, A proposes 1, since they know that M prefers 1 to 0.

#### 5.5. Weakly Undominated Strategies in Subgames

**Example**

**5.**

- A: a preferred to b preferred to d
- B: b preferred to a preferred to d
- D: d preferred to b preferred to a

- 3—the top alternative for every player
- 2—the second-best alternative for every player
- 1—the worst alternative for every player

_{4}depicted in Figure 5 has three SPEs, i.e., ${S}_{{H}_{4}}^{SPE}$ = {(b; b; b), (a; a; a), (a; b; b)}. When all players vote identically, either (b; b; b) or (a; a; a), their vote is an NE (and also SPE) since no deviation of one player can change the outcome of voting. The third SPE, (a; b; b), is when all voters vote for their preferred alternative, i.e., when they choose their strategies that are weakly dominant in H

_{4}.

_{1}, H

_{2}, and H

_{3}have a structure that is identical to H

_{4}and have three SPEs each. Thus, when we prune all four subgames, the set of partial SPEs, ${S}_{1}^{SPE}$, includes ${3}^{4}$ = 81 partial strategy profiles. There are ${2}^{4}$ = 16 possible upgames since in each subgame, either a or b, can be the equilibrium outcome with the corresponding payoff vectors (3, 2, 1) or (2, 3, 2). Thus, every subgame may be replaced either with (3, 2, 1) or (2, 3, 2).

## 6. Conclusions

- Identify the game’s agenda, i.e., the tree consisting of all roots of the game’s subgames that is ordered by the relation of the successor imported from the game tree. Set the pruning sequence.
- Prune any subgame according to the pruning sequence and substitute its root with the subgame’s SPE payoffs. The procedure of substitution may be conducted simultaneously for any subset of agenda nodes as long as the corresponding subgames are pairwisely disjoint.
- Concatenate all partial strategy profiles resulting from the substitution.
- If at any point one receives an empty set as SPE for the subgame, this would mean that there is no SPE compatible with the set of previously selected SPEs for the subgames.
- In order to find all SPEs, one needs to try all possible substitutions of the subgames with SPE payoffs.
- One stops at the root of the game.

- Extending the results: An obvious open question is whether the results for behavioral strategies of finite support and crossing can be generalized to all “rough” behavioral strategies. Attacking this question would demand leaving the comfortable world of finite probability distributions and using measure theory in the spirit of Aumann’s [30] pioneering contribution. The framework presented in this paper goes around measure-theoretic difficulties by assuming finite support and crossing. Both assumptions imply that the total number of terminal paths that count for calculating payoffs is finite for every strategy profile. It is easy to identify the places in the proofs where this fact is used. A natural question, then, is whether the equivalence can be extended.
- Axiomatization of noncooperative game theory: The general axiomatic framework applied in the present paper encompasses more games than the classical approaches of von Neumann [4] and Kuhn [6]. When game theory was born, it seemed natural to consider only finite games; nonfinite games rarely appeared in the literature. Today, we routinely go beyond the limitations of finite games, either with a continuum of strategies that represent quantity, price, or position in the issue space or with the infinite repetition of a game. I believe that contemporary game theory deserves sound axiomatic foundations that can cover infinite games. This would lead toward a more unified and complete discipline. Concepts that were axiomatically analyzed for finite games, such as Kreps and Wilson’s (1982) sequential equilibrium, seem to be obvious targets for a more comprehensive axiomatic investigation. The present paper demonstrates that new results or extensions of well-known results can be obtained within the general framework of infinite games.
- Modification of BI beyond subgame perfection: The final question is whether backward induction can be modified for other solution concepts beyond subgame perfection. An immediate ad hoc modification would consider only those SPEs that exclude partial equilibria with weakly dominated strategies, as it was demonstrated in Example 5. Perhaps, after a suitable modification of the main principle, backward induction-like reasoning could also produce some other refinements. On the other hand, proving that this is not the case would be an interesting finding as well.

## Funding

## Acknowledgments

## Conflicts of Interest

## Appendix A

**Proof**

**of**

**Lemma**

**1.**

**Proof**

**of**

**Lemma**

**2.**

**Proof**

**of**

**Lemma**

**3.**

**s**

^{H}).

- (i)
- every terminal path $e\in {T}_{s\left(H\right)}$ defines a terminal path of ${\mathbf{s}}^{H}$ in H and all terminal paths of ${\mathbf{s}}^{H}$ in H can be obtained this way.

- (ii)
- ${P}^{G}\left(e\right)={P}^{H}\left({e}^{H}\right)$ and
- (iii)
- ${p}_{{s}^{G}}\left(e\right)={\prod}_{y\in e}{p}_{s}^{m}\left(y\right)={\prod}_{y\in {e}^{H}-\{\varphi \}}{p}_{s}^{m}\left(y\right){\prod}_{y\in e-{e}^{H}\cup \{\varphi \}}{p}_{s}^{m}\left(y\right)=={p}_{{s}^{G}}\left(\varphi \right)\times {p}_{{s}^{H}}\left({e}^{H}\right)$

**Proof**

**of**

**Lemma**

**4.**

**Proof**

**of**

**Theorem**

**1.**

**Proof**

**of**

**Lemma**

**5.**

**Proof**

**of**

**Theorem**

**2.**

## References

- Zermelo, E. Über Eine Anwendung Der Mengenlehre Auf Die Theorie Des Schachspiels. In Proceedings of the Fifth International Congress of Mathematicians, Cambridge, UK, 21–28 August 1912; Cambridge University Press: Cambridge, UK, 1913; Volume 2, pp. 501–504. [Google Scholar]
- Schwalbe, U.; Walker, P. Zermelo and the Early History of Game Theory. Games Econ. Behav.
**2001**, 34, 123–137. [Google Scholar] [CrossRef] - Von Stackelberg, H. Market Structure and Equilibrium (Marktform Und Gleichgewicht); Springer: New York, NY, USA, 2011. [Google Scholar]
- Von Neumann, J.; Morgenstern, O. Theory of Games and Economic Behavior; Princeton University Press: Princeton, NJ, USA, 1944; ISBN 978-0-691-13061-3. [Google Scholar]
- Von Neumann, J. Zür Theorie Der Gesellschaftsspiele. Math. Ann.
**1928**, 100, 295–320. [Google Scholar] [CrossRef] - Kuhn, H. Extensive Games and the Problem of Information. In Contributions to the Theory of Games I; Kuhn, H., Tucker, A., Eds.; Princeton University Press: Princeton, NJ, USA, 1953; pp. 193–216. [Google Scholar]
- Schelling, T.C. The Strategy of Conflict; Harvard University Press: Cambridge, MA, USA, 1960. [Google Scholar]
- 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**, 2, 301–324. [Google Scholar] - Rosenthal, R.W. Games of Perfect Information, Predatory Pricing and the Chain-Store Paradox. J. Econ. Theory
**1981**, 25, 92–100. [Google Scholar] [CrossRef] - Selten, R. The Chain Store Paradox. Theory Decis.
**1978**, 9, 127–159. [Google Scholar] [CrossRef] - Selten, R. Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games. Int. J. Game Theory
**1975**, 4, 25–55. [Google Scholar] [CrossRef] - Kreps, D.M.; Wilson, R. Sequential Equilibria. Econometrica
**1982**, 50, 863–894. [Google Scholar] [CrossRef] - Kohlberg, E.; Mertens, J.-F. On the Strategic Stability of Equilibria. Econometrica
**1986**, 54, 1003–1037. [Google Scholar] [CrossRef] - Basu, K. Strategic Irrationality in Extensive Games. Math. Soc. Sci.
**1988**, 15, 247–260. [Google Scholar] [CrossRef] - Basu, K. On the Non-Existence of a Rationality Definition for Extensive Games. Int. J. Game Theory
**1990**, 19, 33–44. [Google Scholar] [CrossRef] - Bicchieri, C. Self-Refuting Theories of Strategic Interaction: A Paradox of Common Knowledge. In Philosophy of Economics; Springer: New York, NY, USA, 1989; pp. 69–85. [Google Scholar] [CrossRef]
- Binmore, K. Modeling Rational Players: Part I. Econ. Philos.
**1987**, 3, 179–214. [Google Scholar] [CrossRef] - Binmore, K. Modeling Rational Players: Part II. Econ. Philos.
**1988**, 4, 9–55. [Google Scholar] [CrossRef] - Bonanno, G. The Logic of Rational Play in Games of Perfect Information. Econ. Philos.
**1991**, 7, 37–65. [Google Scholar] [CrossRef] - Fudenberg, D.; Kreps, D.M.; Levine, D.K. On the Robustness of Equilibrium Refinements. J. Econ. Theory
**1988**, 44, 354–380. [Google Scholar] [CrossRef] - Pettit, P.; Sugden, R. The Backward Induction Paradox. J. Philos.
**1989**, 86, 169–182. [Google Scholar] [CrossRef] - Reny, P. Rationality, Common Knowledge and the Theory of Games; Princeton University Press: Princeton, NJ, USA, 1988. [Google Scholar]
- Aliprantis, C.D. On the Backward Induction Method. Econ. Lett.
**1999**, 64, 125–131. [Google Scholar] [CrossRef] - Schelling, T.C.; (University of Maryland, College Park, MD, USA). Personal communication, 2008.
- Fudenberg, D.; Tirole, J. Game Theory; MIT Press: Cambridge, MA, USA, 1991. [Google Scholar]
- Myerson, R.B. Game Theory; Harvard University Press: Cambridge, MA, USA, 2013. [Google Scholar]
- Osborne, M.J.; Rubinstein, A. A Course in Game Theory; MIT Press: Cambridge, MA, USA, 1994; ISBN 0-262-14041-7. [Google Scholar]
- Escardò, M.H.; Oliva, P. Computing Nash Equilibria of Unbounded Games. Turing-100
**2012**, 10, 53–65. [Google Scholar] - Neyman, A.; Sorin, S. Stochastic Games and Applications; Kluwer Academic Publishers: Dordrecht, The Netherlands, 2003; ISBN 1-4020-1492-9. [Google Scholar]
- Aumann, R.J. Mixed and Behavior Strategies in Infinite Extensive Games; Report; Princeton University: Princeton, NJ, USA, 1961. [Google Scholar]
- Nash, J. Non-Cooperative Games. Ann. Math.
**1951**, 54, 286–295. [Google Scholar] [CrossRef] - Bendor, J.; Swistak, P. Evolutionary Equilibria: Characterization Theorems and Their Implications. Theory Decis.
**1998**, 45, 99–159. [Google Scholar] [CrossRef] - Flood, M.M. Some Experimental Games; Research Memorandum RM-789; RAND: Santa Monica, CA, USA, 1952. [Google Scholar]
- Brams, S.J.; Taylor, A.D. Fair Division: From Cake-Cutting to Dispute Resolution; Cambridge University Press: Cambridge, UK, 1996; ISBN 0-521-55390-3. [Google Scholar]
- Steinhaus, H. The Problem of Fair Division. Econometrica
**1948**, 16, 101–104. [Google Scholar] - Romer, T.; Rosenthal, H. Political Resource Allocation, Controlled Agendas, and the Status Quo. Public Choice
**1978**, 33, 27–43. [Google Scholar] [CrossRef] - Kaminski, M.M.; Nalepa, M. A Model of Strategic Preemption: Why Do Post-Communists Hurt Themselves? Decisions
**2014**, 21, 31–65. [Google Scholar] [CrossRef] - Kaminski, M.M.; Lissowski, G.; Swistak, P. The “Revival of Communism” or the Effect of Institutions? The 1993 Polish Parliamentary Elections. Public Choice
**1998**, 97, 429–449. [Google Scholar] [CrossRef] - Farquharson, R. Theory of Voting; Blackwell: Hoboken, NJ, USA, 1969. [Google Scholar]
- Riker, W.H. The Art of Political Manipulation; Yale University Press: New Haven, CT, USA, 1986; ISBN 0-300-03592-6. [Google Scholar]

© 2019 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).