Generalized Backward Induction: Justification for a Folk Algorithm
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 subg...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-08-01
|
| Series: | Games |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-4336/10/3/34 |
| _version_ | 1819146385471045632 |
|---|---|
| author | Marek Mikolaj Kaminski |
| author_facet | Marek Mikolaj Kaminski |
| author_sort | Marek Mikolaj Kaminski |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-22T13:13:05Z |
| format | Article |
| id | doaj.art-3938abe3143747429b5efb798fdbd830 |
| institution | Directory Open Access Journal |
| issn | 2073-4336 |
| language | English |
| last_indexed | 2024-12-22T13:13:05Z |
| publishDate | 2019-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Games |
| spelling | doaj.art-3938abe3143747429b5efb798fdbd8302022-12-21T18:24:42ZengMDPI AGGames2073-43362019-08-011033410.3390/g10030034g10030034Generalized Backward Induction: Justification for a Folk AlgorithmMarek Mikolaj Kaminski0Department of Political Science and Mathematical Behavioral Sciences, University of California, 3151 Social Science Plaza, Irvine, CA 92697-5100, USAI 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.https://www.mdpi.com/2073-4336/10/3/34subgame perfect equilibriumbackward inductionrefinementaxiomatic game theoryagenda setterimperfect informationpolitical economy |
| spellingShingle | Marek Mikolaj Kaminski Generalized Backward Induction: Justification for a Folk Algorithm Games subgame perfect equilibrium backward induction refinement axiomatic game theory agenda setter imperfect information political economy |
| title | Generalized Backward Induction: Justification for a Folk Algorithm |
| title_full | Generalized Backward Induction: Justification for a Folk Algorithm |
| title_fullStr | Generalized Backward Induction: Justification for a Folk Algorithm |
| title_full_unstemmed | Generalized Backward Induction: Justification for a Folk Algorithm |
| title_short | Generalized Backward Induction: Justification for a Folk Algorithm |
| title_sort | generalized backward induction justification for a folk algorithm |
| topic | subgame perfect equilibrium backward induction refinement axiomatic game theory agenda setter imperfect information political economy |
| url | https://www.mdpi.com/2073-4336/10/3/34 |
| work_keys_str_mv | AT marekmikolajkaminski generalizedbackwardinductionjustificationforafolkalgorithm |