Forward induction
The task of forward induction in game theory is to find the optimal strategies for rational players in a game with successive moves. To better represent the game, look at the so-called game tree and analyze the game from its beginning to the end, i.e. H. one works “forward” through the tree. Thus, the forward induction is in contrast to the backward induction , in which the previous moves are analyzed in order to find the best options for the players.
Example I.
table
| Col.1 (man) / Col.2 (woman) | movie theater | theatre |
|---|---|---|
| movie theater | 1.3 | 0.0 |
| theatre | 0.0 | 3.1 |
Game flow
The game is played as follows: Player 1 (man) is given a so-called outside option at the beginning. He can decide whether he wants to participate in the game - strategy (W) - or not to participate in the game - strategy (S). If he decides to end the game (S), both players receive payout 2. If, on the other hand, he takes part in the game, a battle-of-the-sexes game continues . In this game, the players want to coordinate by performing the same action - (cinema, cinema) or (theater, theater). In this way, they receive a higher payout than in the case of different behavior in which they only receive a payout of zero.
For the man who is rational, it would make sense to continue the game if he can get a payout greater than 2. He can guarantee the payout of 2 immediately by playing the strategy (S) and ending the game. He only gets a higher payout than 2 if he plays the strategy (theater) in the partial game. Because if he (cinema) plays he only gets a payout of 1.
For the woman the optimal strategy would also be (theater), because she knows that the man acts rationally and that the strategy (theater) also plays in the partial game. So she gets at least a payout of 1 instead of a payout of 0 (if she had played the strategy (cinema)).
Conclusion :
If a node is reached that is possibly out of the equilibrium path, then the player deciding on that node should consider which actions the other player could have chosen instead, but did not choose. Then he should look forward and consider what strategy the other player plans to choose as the game progresses . So the players should think forwards - from the beginning to the end of the tree, and a deviation of a player from the equilibrium path should be interpreted as a signal of how that player plans to decide in the future.
Equilibria
The partial game (coordination game) has the following Nash equilibria
1 (cinema, cinema) - player 1 plays (cinema) and player 2 plays (cinema)
2. (theater, theater) - player 1 plays (theater) and player 2 plays (theater)
The two players here prefer equilibrium over non-equilibrium. The preferences regarding the two equilibria can, but need not, be different.
A subgame-perfect balance of the modified game (with outside option) is that the man plays (S) and (cinema) and the woman (cinema) plays. But since (Kino, Kino) is a Nash equilibrium of the subgame and the man expects a payout of only 1 in this Nash equilibrium, he will play strategy (S) on the first move to get the payout 2.
Example II
The following game is considered:
Bimatrix
| Player 1 / Player 2 | A2 | (B2, C2) | (B2, D2) |
|---|---|---|---|
| A1 | 9.9 | 9.9 | 9.9 |
| (B1, C1) | 9.9 | 10.1 | 0.0 |
| (B1, D1) | 9.9 | 0.0 | 1.10 |
Game flow
For this example, the logic of the forward induction means that the waiver of A i , i = (1,2) must be interpreted in such a way that in the sub-game following (B1, B2) player i wants to earn more than 9. So player 1 will not play (D1) and player 2 will not choose (C2) because the two players will only receive a maximum payout of 1. The fact that this is of course to be interpreted in this way for the two players indicates that such interpretations can sometimes be absurd. According to moves (B1) and (B2), such demands on behavior in the sub-game are inconsistent and should be revised.
Equilibria
In this example the strategies (B1, D1) are weakly dominated by A1 and the strategies (B2, C2) by A2 and are therefore used with a probability of zero. In the subgame following the sequence of moves (B1, B2), the strategy (C1, D2) is followed, but this does not lead to an equilibrium of the subgame.
Forward induction vs. Backward induction
Game theory describes optimizing behavior in an interactive situation through equilibrium concepts.
With forward induction, you can use actions to communicate your intention - how you intend to play in the following. The game is analyzed from the beginning to the end of the game tree, so you work “forward”. So one can exclude an equilibrium concept like subgame perfect equilibrium through the forward induction.
In contrast to the forward induction, the analysis of the game with the backward induction begins at the lower end of the game tree, ie at the decision nodes where it is the last player's turn. At each of these nodes the best answer of this player is determined. This is how you work your way “backwards” through the tree. This procedure is repeated until the optimal strategies of all players at each node are found.
With the help of backward induction, an equilibrium concept such as the subgame-perfect equilibrium in the case of an extensive form game with complete information can be found. The subgame-perfect equilibrium represents a generalization of the principle of backward induction. Here, a rational behavior in the sense of the Nash equilibrium is required not only for the entire game tree, but also for all subgames. These are all parts of the game tree that have the structure of a game tree themselves. The implausible behavior is eliminated with the backward induction also at the decision nodes, which cannot be reached in the course of the game.
See also
literature
- D. Fudenberg, Jean Tirole: Game Theory. MIT Press, 1991.
- Gernot Sieg: Game Theory. Oldenbourg Verlag, Munich 2005.
- Siegfried K. Berninghaus, Karl-Martin Ehrhart, Werner Güth: Strategic games: An introduction to game theory. Springer, Berlin / Heidelberg 2006.
- David. M. Kreps, Robert Wilson: Reputation and Imperfect Information. In: Journal of Economic. Theory, vol. 27, 1982.
Individual evidence
- ↑ http://wikiludia.mathematik.uni-muenchen.de/wiki/index.php?title=R%C3%BCckw%C3%A4rtsinduktion
- ↑ Gernot Sieg: Game Theory. Oldenbourg Verlag, Munich 2005, pp. 112-113
- ^ D. Fudenberg, Jean Tirole: Game Theory. MIT Press, 1991. pp. 460-463
- ^ Siegfried K. Berninghaus, Karl-Martin Ehrhart, Werner Güth: Strategic games: An introduction to game theory. Springer, Berlin / Heidelberg 2006. pp. 141-143
- ↑ David M. Kreps, Robert Wilson: Reputation and Imperfect Information. In: Journal of Economic. Theory, vol. 27, 1982