Backward Induction and Common Knowledge

In 1987, I wrote a paper (Binmore [14]) that questioned the rationality of the backward induction principle in finite games of perfect information. Since that time, a small literature has grown up in which Antonelli and Bicchieri [1], Ben-Porath [9], Bicchieri [10,11], Bonanno [21,22], Pettit and Sugden [28], Reny [30], Samet [32], Stalnaker [37,36] and numerous others have attempted with varying success to treat the issues formally. I believe my claim that rational players would not necessarily use their backward- induction strategies if there were to be a deviation from the backward-induction path is now generally accepted. But Aumann's [3] has recently offered a formal defense of the proposition that prior common knowledge of the players' rationality implies that play will nevertheless necessarily follow the backward-induction path. He argues that the conclusion is counter-intuitive in certain games, but attributes our discomfort with the result to a failure to appreci-ate how strong his assumptions are. However, although Aumann's deep and thought-provoking contributions to the foundations of game theory provide the chief inspiration for this note, my purpose is not to comment specifically on his recent article. Its purpose is to question the significance of this and other results of the formalist genre. Without intending any disrespect to the authors,2 I believe that there is little of genuine significance tobe learned from any of the literature that ap-plies various formal methods to backward induction problems even when the authors find their way to conclusions that I believe to be correct. It seems to me that all the anaZyticaZ issues relating to backward induction lie entirely on the surface. Inventing fancy formalisms serves only to confuse matters. The related literature on the Surprise Test Paradox provides a particularly blatant example. The paradox has a trivial resolution (Quine [29], Binmore [16]), but the various exotic logics that have been brought to bear on the problem never come near exposing the piece of legerdemain by means of which we are deceived when the problem is posed. Formalists will object, saying that an argument is open to serious evaluation only after it has been properly formalized. But this is a disingenuous response. It is true that, if we were in serious doubt about whether an author had suc- ceeded in analyzing his or her model correctly, then it would be foolish not to insist that the argument be given in precise terms. However, the literature on backward induction seldom provokes doubts at this level. The issue is almost never whether a particular model has been analyzed correctly but whether the correct model has been analyzed. In brief, I think that the backward induction problem like much else in the foundations of game theory poses only a very small challenge to our powers of formal analysis. The real challenge is not to our powers of analysis, but to our ability to find tractable models that successfully incorporate everything that matters. In particular, it seems entirely elementary that, whatever model of a player is used, it must be rich enough to encompass irrational behavior as well as rational behavior (Binmore [14]). What keeps a rational player on the equilibrium path is his evaluation of what would happen if he were to de-viate. But, if he were to deviate, he would behave irrationally. Other players would then be foolish if they were not to take this evidence of irrationality into account in planning their responses to the deviation. A formal model that ne- glects what WOUM happen if a rational player were to deviate from rational play must therefore be missing something important, no matter how elaborately it is analyzed. However, Aumann [3, Section 5c], for example, is insistent that his conclusions say nothing whatever about what players would do if vertices of the game tree off the backward-induction path were to be reached . 3 But, if nothing can be said about what would happen OH the backward- induction path, then it seems obvious that nothing can be said about the rationality of remaining on the backward-induction path. How else do we assess the cleverness of taking an action than by considering what would have happened if one of the alternative actions had been taken? But this is precisely what Aumann's [3] definition of rationality fails to do. (See Justification 6 of Section 4.) In Binmore [14], I used Rosenthal's [31] Centipede Game of Figure l(a) as an example when criticizing the defense of the backward induction principle that was then current. Figure l(b) shows the strategic form of the special case when n = 3 (the three- legged Centipede). In this note, I plan to use the same example to elaborate on the criticism just expressed of the tighter defense of the principle that is possible if one follows Aumann [3] in abandoning claims about what would happen off the backward-induction path. It is easy to verify that the backward induction principle requires that each player always plan to play dOWn in the Centipede. In particular, the unique subgame-perfect equilibrium S in the three-legged Centipede is (old, d). How-ever, the three-legged Centipede has other Nash equilibria. Part of the reason for writing this note is to argue that such alternative Nash equilibria have been too readily dismissed in the past a theme pursued at greater length in Binmore et al [17,18]. In particular, the three-legged Centipede has a mixed Nash equilibrium IV in which player I uses his backward-induction strategy with probability one, but player II mixes between a and d, using the former with probability 1/3. 4 If player I knows that player II will play across with this probability, it is false that rationality requires that he play down. In fact, he is indifferent between playing down and across. Although he plays down with probability one in equilibrium, it is nevertheless equally rational for him to play across. Among other things, this note argues that prior common knowledge of ra-tionality should not lead us to reject the equilibrium X On the contrary, it is argued that lV, rather than S, is the equilibrium of interest for the issues that the Centipede was constructed to explore. It is tempting to wave this point aside by conceding that perhaps prior common knowledge of rationality in the Centipede may lead to the play of lV and so does not, after all, necessitate that player I open the Centipede by playing down. But who cares if player I only plays across with probability zero? But there is more riding on this is-sue than immediately meets the eye, as I hope will be evident by the end of this note. In particular, I hope that it will become apparent that we need not follow Aumann [6,3] in perceiving a sharp discontinuity between what happens when there is perfect common knowledge of rationality and when this condition is relaxed slightly. In particular, there is no need for game theorists to seek to insulate themselves from the criticism of experimentalists by claiming that their theorems have no relevance to how real people behave. Section 2 comments briefly on the importance of common knowledge assumptions in general. Section 3 explores one of the reasons for the popularity of the claim that prior common knowledge of rationality implies the backward induction principle. It describes my version of a folk argument that purports to demonstrate that prior common knowledge of rationality in the Centipede Game implies that its opening move will necessarily be down. As with Aumann's [3] more complicated theorem, the argument is correct, in the sense that the con-clusion does indeed follow from the premises. But something must be wrong at the conceptual level, because the conclusion that player I will begin by playing down is obtained without any reference to his beliefs about what would happen if he were to play across. But if the probability that player I assigns to the event that player II would then also play across is sufficiently high, it is obviously not optimal for player I to begin by playing down. I believe that this apparent para-dox arises partly as a consequence of a failure to appreciate how counterfactual reasoning works. Section 4 therefore seeks to demystify this question. Section 5 attempts to resolve the paradox by retelling the story with a less restrictive background model. However, once a paradox-free model has been adopted, the door is no longer closed on the Nash equilibrium lV. Finally, Section 6 tries to say something about what the conclusions mean by taking up a clarion call from one of Aumann's [7] previous papers, and asking what we are trying to accomplish when we prove theorems in game theory. Personally, I think it is because this question has been so neglected that the foundations of game theory are now in such a mess.