This is a file in the archives of the Stanford Encyclopedia of Philosophy. |
Proof.
The proof is by induction on m, the number of potential moves
in the game. If m = 1, then at Ii1, by (a)
agent i chooses a strategy which yields i her maximum
payoff, and this is the backwards induction solution for a game with
one move.
Now suppose the proposition holds for games having at most m = r potential moves. Let Γ be a game of perfect information with r + 1 potential moves, and suppose that ( α ) and ( β ) are satisfied at every node of Γ. Let Ii1 be the information set corresponding to the root of the tree for Γ. At Ii1, i knows that (a) and (b) obtain for each of the subgames that start at the information sets which immediately follow Ii1. Then i knows that the outcome of play for each of these subgames is the backwards induction solution for that subgame. Hence, at Ii1 i's payoff maximizing strategy is a branch of the tree starting from Ii1 which leads to a subgame whose backwards induction solution is best for i, and since i is rational, i chooses such a branch at Ii1. But this is the backwards induction solution for the entire game Γ, so the proposition is proved for m = r + 1.
Peter Vanderschraaf peterv@cyrus.andrew.cmu.edu | Giacomo Sillari Carnegie Mellon University gsillari@andrew.cmu.edu |