Substantive Rationality and Backward Induction 

(Research Seminar, April 10, 2003)

Joseph Halpern

Department of Computer Science, Cornell University

Abstract

Some of the major puzzles in game theory today involve the notion of rationality. Assuming that all players are rational, and know that they are all rational, and know that they know, etc., results in strategies that seem highly irrational. At the 1998 TARK (Theoretical Aspects of Rationality and Knowledge) conference, there was a 2.5 hour round table, involving some leading game theorists and philosphers, on ``Common knowledge of rationality and the backward induction solution for games of perfect information''. During the discussion Robert Aumann stated the following theorem:

Common knowledge of substantive rationality implies the backward induction solution in games of perfect information.

Robert Stalnaker then stated the following theorem:

Common knowledge of substantive rationality does not imply the backward induction solution in games of perfect information.

In this talk I will carefully explain all the relevant notions (games of perfect information, knowledge and common knowledge, strategies, rationality, and substantive rationality) and explain why, although both Aumann and Stalnaker were apparently using the same definitions, they were able to (correctly) prove such different results. The key turns out to lie in getting a good model of counterfactual reasoning in games. I will in fact provide a formal model that allows us to prove both results and to understand the technical differences between them. The model has the added advantage of giving us a deeper insight into what conclusions we can draw from rationality and common knowledge of rationality. No prior knowledge will be assumed.