Backward induction
From Wikipedia, the free encyclopedia
In game theory, backward induction is one of dynamic programming algorithms used to compute subgame perfect equilibria in sequential games. The process proceeds by first looking at the last possible action, determine what the last player will do in each situation (i.e. information set). Using this information, one can then determine what the second to last player will do. This process continues until one determines all possible actions.
It was first employed by John von Neumann and Oskar Morgenstern in their 1944, Theory of Games and Economic Behavior [1].
[edit] Example of backward induction
Consider the ultimatum game, where one player proposes to split a dollar with another. The first player (the proposer) suggests a division of the dollar between the two players. The second player is then given the option to either accept the split or reject it. If she accepts both get the amount suggested by the proposer. If she rejects neither receives anything.
Consider the actions of the second player given any aribitary proposal by the first player (that gives the second player more than zero). Since the only choice the second player has at each of these points in the game is to choose between something and nothing, one can expect that the second will accept. Given that the second will accept all proposals offered by the first (that give the second anything at all), the first ought to propose giving the second as little as possible. This is the unique subgame perfect equilibria of the Ultimatum Game. (It is important to note that the Ultimatum Game does have several other Nash equilibria.)
See also centipede game.
[edit] Backward induction and economic entry
Consider a dynamic game in which the players are an incumbent firm in an industry and a potential entrant to that industry. As it stands, the incumbent has a monopoly over the industry and does not want to lose some of its market share to the entrant. If the entrant chooses not to enter, the payoff to the incumbent is high (it maintains its monopoly) and the entrant neither loses nor gains (its payoff is zero). If the entrant enters, the incumbent can fight or accommodate the entrant. It will fight by lowering its price, running the entrant out of business (and incurring exit costs — a negative payoff) and damaging its own profits. If it accommodates the entrant it will lose some of its sales, but a high price will be maintained and it will receive greater profits than by lowering its price (but lower than monopoly profits).
If the entrant enters, the best response of the incumbent is to accommodate. If the incumbent accommodates, the best response of the entrant is to enter (and gain profit). Hence the strategy profile in which the incumbent accommodates if the entrant enters and the entrant enters if the incumbent accommodates is a Nash equilibrium. However, if the incumbent is going to play fight, the best response of the entrant is to not enter. If the entrant does not enter, it does not matter what the incumbent chooses to do (since there is no other firm to do it to — note that if the entrant does not enter, fight and accommodate yield the same payoffs to both players; the incumbent will not lower its prices if the entrant does not enter). Hence fight is a best response of the incumbent if the entrant does not enter. Hence the strategy profile in which the incumbent fights if the entrant does not enter and the entrant does not enter if the incumbent fights is a Nash equilibrium. Since the game is dynamic, any claim by the incumbent that it will fight is an incredible threat because by the time the decision node is reached where it can decide to fight (i.e. the entrant has entered), it would be irrational to do so. Therefore this Nash equilibrium can be eliminated by backward induction.
[edit] A paradox of backward induction
The unexpected hanging paradox is a paradox which arises with backward induction. Suppose a prisoner is told that she will be executed sometime between Monday and Friday of next week. However, the exact day will be a surprise (i.e. she will not know the night before that she will be executed the next day). The prisoner, interested in outsmarting her executioner, attempts to determine which day the execution will occur.
She reasons that it cannot occur on Friday, since if it had not occurred by the end of Thursday, she would know the execution would be on Friday. Therefore she can eliminate Friday as a possibility. With Friday eliminated, she decides that it cannot occur on Thursday, since if it had not occurred on Wednesday, she would know that it had to be on Thursday. Therefore she can eliminate Thursday. This reasoning proceeds until she has eliminated all possibilities. She concludes that she will not be hanged next week.
To her surprise, she is hanged on Wednesday.
Here the prisoner reasons by backward induction, but seems to come to a false conclusion. This paradox has received some substantial discussion by philosophers.
