Stanford Encyclopedia of Philosophy
Supplement to Common Knowledge

Proof of Proposition 3.12

• i is rational, i knows this and i knows the game, and
• At any information set I ^{jk+ 1} that immediately follows I ^ik, i knows at I ^ik what j knows at I ^{jk+ 1}.

Proof.
The proof is by induction on m, the number of potential moves in the game. If m = 1, then at I ⁱ¹, 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 I ⁱ¹ be the information set corresponding to the root of the tree for . At I ⁱ¹, i knows that (a) and (b) obtain for each of the subgames that start at the information sets which immediately follow I ⁱ¹. Then i knows that the outcome of play for each of these subgames is the backwards induction solution for that subgame. Hence, at I ⁱ¹ i's payoff maximizing strategy is a branch of the tree starting from I ⁱ¹ which leads to a subgame whose backwards induction solution is best for i, and since i is rational, i chooses such a branch at I ⁱ¹. But this is the backwards induction solution for the entire game , so the proposition is proved for m = r + 1.

Return to Common Knowledge