JOHN W. CARROLL
THE BACKWARD INDUCTION ARGUMENT
ABSTRACT. The backward induction argument purports to show that rational and suitably informed players will defect throughout a finite sequence of prisoner’s dilemmas. It is supposed to be a useful argument for predicting how rational players will behave in a variety of interesting decision situations. Here, I lay out a set of assumptions defining a class of finite sequences of prisoner’s dilemmas. Given these assumptions, I suggest how it might appear that backward induction succeeds and why it is actually fallacious. Then, I go on to consider the consequences of adopting a stronger set of assumptions. Focusing my attention on stronger sets that, like the original, obey the informedness condition, I show that any supplementation of the original set that preserves informedness does so at the expense of forcing rational participants in prisoner’s dilemma situations to have unexpected beliefs, ones that threaten the usefulness of backward induction. KEY WORDS: Backward induction, Iterated prisoner’s dilemma, Common knowledge
1. INTRODUCTION
As I will use the phrase, a prisoner’s dilemma is any symmetric, two-player, noncooperative game with a payoff matrix of the following form: C D C(ooperate) x z Moves: D(efect)
y w
where the payoffs – w, x, y and z – are real numbers such that y is greater than x, x is greater than w, and w is greater than z. About these payoffs, all we will need to assume is that they are the values of an ordinal utility scale representing the preferences of the players. A feature of all prisoner’s dilemmas is that, no matter whether the opponent cooperates or defects, a player does better by Theory and Decision 48: 61–84, 2000. © 2000 Kluwer Academic Publishers. Printed in the Netherlands.
62
JOHN W. CARROLL
defecting rather than by cooperating. So, defection is dominant in all prisoner’s dilemmas. Prisoner’s dilemmas are dilemmas, because, if both players choose their dominant move, then they both do worse than if they had both cooperated. Nevertheless, there is a simple and familiar argument that uses the fact that defection is dominant to conclude that rational players who believe the payoff matrix will defect in a prisoner’s dilemma. I will not rehearse or consider that argument here. I will simply assume that it is sound.1 There is, however, another argument that I will rehearse and give thorough consideration. I call it the backward induction argument or the BI argument, for short. It purports to show that suitably informed, rational players faced with a finite sequence of prisoner’s dilemmas will defect throughout the sequence. It goes something like this: The players can see that, when the last prisoner’s dilemma in the sequence rolls around, there will be no incentive to cooperate; there will be as much reason to defect in this last round as there is when a prisoner’s dilemma is played only once. But, the players can also see that they will each appreciate this fact about the final round before the second-to-last round and thus will not have any incentive to cooperate in that penultimate round. The same goes for the third-to-last round and so on, back to the first round. Just to have presented at least one genuine statement of the argument, here is Robert Axelrod’s statement from the first chapter of The Evolution of Cooperation: If the game is played a known finite number of times, the players will still have no incentive to cooperate. This is certainly true on the last move since there is no future to influence. On the next-to-last move neither player will have an incentive to cooperate since they can both anticipate a defection by the other player on the very last move. Such a line of reasoning implies that the game will unravel all the way back to mutual defection on the first move of any sequence of plays that is of known finite length... (1984: 10).
The BI argument occurs frequently in the game-theory literature, especially in introductory texts. In this context, there is almost always the suggestion that the BI argument is a useful argument for predicting how certain real-life interactions would turn out at least if the real-life players were rational. Of special interest to me is that the BI argument also regularly crops up in discussions of Hobbesian justifications of political institutions. Hobbesians accept that there are important real-life and/or hypothetical interactions with the struc-
THE BACKWARD INDUCTION ARGUMENT
63
ture of a prisoner’s dilemma. Hobbesians also accept that the existence of certain political institutions might change the structure of these interactions, making it possible for rational players to achieve more favorable results. The BI argument is relevant to Hobbesian justifications, because it seems to show that, even if we take into consideration that the real-life or hypothetical prisoner’s dilemma situation may be one that will recur a specific finite number of times, rational participants in the interaction will still defect in each round and so will be stuck with a suboptimal outcome throughout the sequence.2 The BI argument is often offered quickly. In fact, it is usually advanced so quickly that it can be hard to be sure exactly what assumptions drive the argument. One thing I plan to do in this paper is to identify just what these assumptions have to be like in order for the BI argument to be valid. Just so, in Section 2, I lay out a set of assumptions defining a class of sequences of prisoner’s dilemmas. Given just these assumptions, I suggest how it might appear that the BI argument succeeds and why it is actually fallacious. If these assumptions were the only ones available, then there would be no effective deployment of the BI argument. But, of course, matters are not that simple. We also have to consider the consequences of using a stronger set of assumptions. And, that is the issue I take up in the remainder of the paper. I focus my attention on stronger sets that, like the original set, obey the informedness condition. This condition says, roughly, that the two players are fully informed. What I show is that assumptions that preserve informedness and make the BI argument valid also undermine much of the usefulness that game theorists and political theorists associate with the BI argument. With all the necessary sorts of assumptions in place, the BI argument has limited application: It is not a very useful tool for predicting the outcomes of real-life interactions, and it does not significantly impact Hobbesian justifications of political institutions. In the game-theory literature, there are lots of uses of the phrase ‘backward induction’. Many of these uses are not directly relevant to the issues to be addressed here. For example, it is easy enough to describe a finite sequence of prisoner’s dilemmas as a game in normal form, where the two players choose from strategies dictating how they will move in each of the rounds. (One such strategy would
64
JOHN W. CARROLL
be tit-for-tat: Open by cooperating and then do whatever the opponent did in the prior game.) Then, one can give an impeccable proof using mathematical induction to show that all Nash equilibria in this normal-form game result in both players defecting in every round. But, this proof is not what I am calling the BI argument; it is not the focus of this paper. It is not, because it bypasses the interesting question about what rational players will do. Anyone who thinks that this proof shows that rational players will defect throughout a finite sequence of prisoner’s dilemmas has probably simply assumed that rational players always play strategies making up some Nash equilibrium. But, a crucial question is why we should believe that. I am interested in those usually more informal arguments that take us from assumptions about the players’ rationality and what the players believe or know to conclusions about what they will do.3 Another place the phrase ‘backward induction’ appears in the game-theory literature is in the well-known discussions of refinements of the Nash equilibrium concept.4 There are many games with more than one Nash equilibria. Some of these equilibria can seem not to be good candidates to be solutions, precisely because backward inductive reasoning suggests that rational players will not play them. Though I think my paper suggests some conclusions about the applicability of such reasoning,5 these well-known discussions are, strictly speaking, tangential to the main themes of this paper, because I am restricting my attention to certain sequences of prisoner’s dilemmas and every Nash equilibrium in these games has both players defect throughout. So, refinements of the Nash equilibrium concept are not to the point. I restrict my attention in this way for two reasons: First, I do so in order to keep my discussion as simple and accessible as possible; bringing in other games would complicate matters. Second, I do so, because it is sequences of prisoner’s dilemmas – not any other games – that have played the biggest role in discussions of Hobbesian justifications of political institutions. My paper is more directly tied to recent literature arguing that the solution to a game sometimes will not be a Nash equilibrium. My work is roughly in the same spirit as the work by such authors as Bernheim (1984) and Pearce (1984) in that I will be very concerned about what the cognitive states of the players must be like in order
THE BACKWARD INDUCTION ARGUMENT
65
for us to conclude that they will rationally make certain moves. My work is more in the spirit of work by Bicchieri (1989, 1990), Pettit & Sugden (1989), Reny (1988, 1989, 1992, 1993, 1995), Sobel (1993) and Stalnaker (1996a, b); their discussions are more closely tied to finite sequences of prisoner’s dilemmas and their conclusions are more in the spirit of my own. Though I will keep the reader informed about how my work relates to the work of these authors, my approach will be different from theirs in at least one important respect: I do not adopt a Bayesian framework or any other formal framework for the discussion of the players’ cognitive states. Indeed, I do my best to make as few theoretical assumptions about the nature of belief, knowledge and rationality as I possibly can. I come to the backward induction issue as an epistemologist trained in the analytic tradition. I want my conclusions to be in keeping with certain widely accepted conclusions from contemporary analytic epistemology. As far as I can tell, at least most of what I will have to say will be consistent with the Bayesian approach taken by these other authors, but it is important to recognize that my conclusions do not depend on this approach.
2. BACKWARD INDUCTION: AN INITIAL LOOK
All of the defining sets of assumptions to be considered in this paper will have one member in common. It is a postulate that describes the basic game configuration, including that the players are rational throughout and that they have perfect recall: (G) (a) Players 1 and 2 are playing a sequence of exactly n prisoner’s dilemmas. (b) Both players are rational throughout the sequence. (c) For all k, both players correctly believe just before the kth prisoner’s dilemma what moves were played in the first through the k-1st prisoner’s dilemma. n can be any natural number greater than one. Part (a) stipulates that this is a finitely iterated prisoner’s dilemma. Part (c) ensures that there is perfect monitoring. (This is standard in iterated prisoner’s dilemmas. It permits the players to keep track of where they are in the sequence and to decide how to play in response to what has been played before.) Part (b) of (G) – the part that says that the
66
JOHN W. CARROLL
players are rational – is especially crucial, and I want to be very clear what it amounts to. At this point in the paper, all I will assume about rationality, and all part (b) amounts to, is that (i) throughout the sequence of prisoner’s dilemmas, each player believes every deductive consequence of every finite set of his or her beliefs, and (ii) each player will defect in one of the rounds if she believes just before that round both (G) and that the opponent will not cooperate in any subsequent rounds.6 This constraint certainly does not reveal all there is to reveal about rationality. It does not even reveal all the assumptions I will be making about rationality in this paper. I am merely identifying an assumption that authors who have used the BI argument seem to accept. In addition to (G), the first set of defining assumptions to be considered only includes assumptions incorporating a common belief of (G). That is, according to the additional assumptions, each player believes (G), each believes that each believes (G), and so on ad infinitum: (B1) Each player believes assumption (G). (B2) Each player believes that each player believes assumption (G). .. . There is a point of possible confusion about how these assumptions should be interpreted. They all use the verb ‘to believe’ in the present tense. This use is meant to describe something about the players right before the sequence of prisoner’s dilemmas begins. I make this seemingly trivial point, because it is easy to think that the verb is being used to describe something about the players throughout the sequence of prisoner’s dilemmas. With regard to assumption (B2), the possible confusion is between the intended reading: (B2) Each player initially believes that each player initially believes assumption (G), and the following alternative reading: (B20 ) Each player throughout the sequence believes that each player throughout the sequence believes assumption (G). It turns out that this point of possible confusion is critical. As we will see later in this second section, with all the intended readings in place, the BI argument does not establish that both players defect
THE BACKWARD INDUCTION ARGUMENT
67
throughout. As we will see at the start of the third section, taking the alternative readings, the BI argument does establish that conclusion. One last thing before turning to the BI argument. I want to call attention to a curious feature of {(G), (B1), (B2), . . . }. It is the informedness condition. As I said above, this condition reflects the fact that our original set of assumptions specifies that the players are fully informed about the game. More precisely, the informedness condition states that, for all players S and all propositions P, if P is a consequence of any finite subset of the set of defining assumptions, then S (initially) believes P. Informedness is often viewed as a positive feature of a set of defining assumptions. The reasoning seems to be this: If it were left open that merely finding out more about a game might affect what moves a rational player would make, then any conclusions about what moves would be made would have more limited significance. So, despite the fact that informedness demands that players have infinitely many beliefs, game-theorists have thought that sets of defining assumptions with this property are interesting; though such assumptions may never describe any real-life decision situation, it is thought that they generate a relevant idealization. Turning to the BI argument, let us consider the simplest case: a two-round sequence. Let us also focus on the conclusion that player 1 defects in the first round. From (B1), it follows both that player 1 believes that player 2 will be rational just before the second round and that player 2 will remember just before the second round having played the first round. If one is not particularly careful, it is also easy to think that it follows from (B2) that player 1 also believes that player 2 will believe (G) just before the second round. If player 1 did believe this, it would put him in a position to conclude that player 2 will believe just before the second round that player 1 will not cooperate in any remaining rounds, there not being any more rounds to play. In that case, player 1 could also conclude that player 2 will defect in the second round. Being rational and not believing that player 2 will cooperate in any remaining rounds, player 1 would defect in the opening round. But wait. As I hinted, there is a problem. Though if one is not particularly careful it is easy to think that it does, assumption (B2) does not really entail that player 1 believes that player 2 believes (G) just before the second round. Assumption
68
JOHN W. CARROLL
(B2) only tells us that player 1 believes that player 2 believes (G) initially. As far as player 1 is concerned, by the time the second round comes along, player 2 may no longer believe (G).7 Thus, we have uncovered one place where the BI argument breaks down. Our initial set of assumptions does not entail that player 1 defects in the opening round. Most who have endorsed the BI argument are not explicit about their defining assumptions, and – as I show below – with only a different reading of our original assumptions, the BI argument will go through. In addition, many authors are quite clear that they are not using assumptions {(G), (B1), (B2), . . . }; they quite clearly assume not only that there is a common belief of (G), but also that there is common knowledge of (G). So there is a lot more work to be done. Just so, in Section 3, I will investigate whether there is any enrichment of our original assumptions that permits standard uses of the BI argument. Sets of assumptions that build in common knowledge of (G) are explicitly discussed in Section 4.
3. STRENGTHENED ASSUMPTIONS
For purposes of illustration, here is one simple supplementation that does at least sustain the BI argument. Besides (G), it includes: (B10 ) Each player throughout the sequence believes assumption (G). 0 (B2 ) Each player throughout the sequence believes that each player throughout the sequence believes assumption (G). .. . As regards player 1’s defection in the first prisoner’s dilemma of a two-round sequence, the key is that the new assumptions stipulate that player 1 believes that player 2 will believe (G) just before the second round. See (B20 ). Thus, these new assumptions, unlike our originals, permit the conclusion that player 1 defects in the first round. Besides serving as a good example of a set of assumptions that does let the BI argument go through, {(G), (B10 ), (B20 ), . . . } serves another useful purpose. It permits us to see that by merely taking this alternate reading of our original assumptions, it does follow that player 1 defects in the first prisoner’s dilemma. Read our
THE BACKWARD INDUCTION ARGUMENT
69
assumptions (B1), (B2), . . . as (B10 ), (B20 ), . . . and the BI argument flies. Before beginning my central argument, a few preliminary points should be brought to the reader’s attention: First, I now restrict our focus to just those sets of assumptions that satisfy the informedness condition (see Section 2). Second, in order for a set of assumptions to make the BI argument valid, it must somehow ensure at least that player 1 has a certain belief, what I will call the key belief, the proposition that player 2 will believe (G) just before the second round. One last preliminary point: My discussion will center on the conditions under which player 1 could rationally8 hold the key belief, and it is of critical importance that his rational basis for this belief not be information about what play he will make in the first round. Taking the BI argument at face-value, the key belief is supposed to be something that player 1 uses to conclude that he will defect in the first round. So, it is not something whose rationality should depend on other beliefs player 1 has about what he will do in that first prisoner’s dilemma. That would partly undermine the point of the BI argument. In this third section, I argue that, if we build into the assumptions that player 1 has the key belief, then player 1 must also have some unexpected and idiosyncratic beliefs in order for the key belief to be rational. It might look like the rationality of the key belief is not much of an issue. After all, the original assumptions tell us that player 1 believes that player 2 initially believes (G), and the key belief is that player 2 just before the second round believes (G). In many ordinary situations, it is perfectly rational to assume that someone will retain a belief. For instance, if I believe that you believe that Clinton is president, then I will usually also (quite rationally) believe that you will still believe this in a few minutes. But the rationality of the key belief really is an issue for the simple reason that not all ‘belief-retention’ beliefs are rational. Just so, I should not assume that you will believe that Clinton is president in a few minutes if – just to give one relevant kind of example – I also believe you might encounter some conflicting evidence in the meantime. I will show that player 1 is in a similar situation. If we preserve informedness and build in enough to let the BI argument go
70
JOHN W. CARROLL
through, then as far as player 1 believes, player 2 might encounter some evidence that would conflict with her initial belief of (G). To see this, let us consider some of the propositions that player 2 believes at the outset, before any moves have taken place. The original assumptions tell us that player 2 initially believes: (1)
(G)
They also tell us that player 2 believes: (2)
Player 1 believes (G).
More interestingly, we can also be sure that, on any relevant strengthening of the original assumptions, player 2 believes: (3)
Player 1 believes that player 2 believes (G) just before the second round.
That player 2 believes proposition (3) is not part of our original assumptions. Still, our concern here is with enrichments of our original assumptions that both sustain the BI argument and also satisfy the informedness condition. In virtue of licensing the BI argument, any such enrichment must entail that player 1 holds the key belief. In virtue of satisfying the informedness condition, any such enrichment must also entail that player 2 initially believes that player 1 holds the key belief. So, since the key belief is the belief that player 2 believes (G) just before the second round, player 2 does initially believe proposition (3). All told, according to any relevant expansion of the original assumptions, it must be true that player 2 initially believes (1), (2) and (3). A little reflection shows that (1)-(3) together entail that player 1 defects in the first round. (Basically, these three propositions are all that is needed for the BI argument to establish that player 1 defects in the first round.) So, if player 1 were to cooperate in the opening round, he would thereby challenge player 2’s initial beliefs. To put this point in a slightly different and slightly more formal way, let proposition (4) be given by: (4)
Player 1 cooperates in the first round.
Then, the first thing to notice is that {(1), (2), (3), (4)} is a minimally inconsistent set. The second thing to notice is that should player 1
THE BACKWARD INDUCTION ARGUMENT
71
make (4) true by cooperating in the first round, he would minimally contradict a set of propositions all of which are initially believed by player 2. Since player 2 is rational, such a cooperative move might well lead player 2 to stop believing a member of {(1), (2), (3)}. In particular, it might lead player 2 to stop believing proposition (1). But, in that case, player 2 would not believe (G) just before the second round; the key belief, the belief that player 2 believes (G) just before the second round, would be false.9 Think this through from player 1’s perspective. What would it take for him rationally to have the key belief, a belief he must have in order for the BI argument to work? In other words, what would it take for him rationally to believe that player 2 will believe (G) just before the second round? Since he cannot have any independent reason for thinking that he, himself will defect in the first round (for the reasons given above concerning the point of the BI argument), to be rationally entitled to the key belief, player 1 has to consider the consequences that his cooperating might have on what player 2 believes. Given what I argue in the preceding paragraph, in the absence of some fairly special additional beliefs, it looks as if his cooperating in the first round would force player 2 to dispose of one of her present beliefs. One of the candidates for disposal is her belief of (G). So, in the absence of some fairly special additional beliefs, player 1 is not rationally entitled to the key belief. Let’s consider a simpler, but parallel, situation. Suppose that I believe that you are rational and that you now believe that a certain coin flip landed heads. Perhaps, for pretty good reasons, you believe that a two-headed coin was used. This coin flip took place yesterday and you have not yet been told how it turned out. You will be told soon. Unlike you, I believe very little about the flip: Though I do believe that the flip landed either heads or tails and that you will be told the outcome, I do not believe (and do not have any reason to believe) that the flip turned out one way rather than the other. In this situation, would it be rational for me to believe that, after being told how the coin landed, you will still believe that the coin landed heads? Pretty clearly, in the absence of some fairly special additional beliefs, it would not. As far as I believe, that coin may land tails. I naturally assume that, if it were to land tails, you would be told that it did and would then drop your belief that it landed heads. So, in the
72
JOHN W. CARROLL
absence of certain additional beliefs, I have no business believing that you will later believe that the coin landed heads. In just the same way, in the absence of certain additional beliefs, player 1 has no business believing that player 2 will believe (G) just before the second round. I am not claiming that player 1 cannot rationally believe this key belief. Consider the parallel example again. There are some other things that I might believe that would make it rational for me to assume that you will later believe that the coin landed heads. For example, I might believe that you are suspicious of reports of the results of coin tosses and very certain of your information about that toss being rigged. If so, I would believe that you would not drop your belief about the result of the toss even if you were told that it landed tails. Similarly, player 1 might have certain information about the relative strengths of player 2’s beliefs and her belief-revision mechanisms that would allow him (player 1) to predict how her beliefs would be revised if confronted with contradicting evidence. The right information would give player 1 reason to believe that player 2 will believe (G) just before the second round even given the possibility that he cooperates in the first round. Then, other things being equal, player 1 could rationally believe that player 2 would not drop her belief of (G) even if he cooperates in the first round. Player 1 would rationally be entitled to the key belief. What I am claiming is that player 1 needs these additional beliefs about player 2 or others that will do the same trick.10 What will the additional beliefs have to be like? Well, I have just given you some idea what they could be like. Let us consider this sort of possibility first. So, suppose that player 1 has information about the relative strengths of player 2’s beliefs and her beliefrevision mechanisms that would allow him to predict how her beliefs would be revised if confronted with contradicting evidence. Simplifying a lot, we can suppose, for example, that player 1 believes that player 2 believes proposition (1) much more strongly than she believes proposition (2) or proposition (3) and that player 2 abandons less strongly held beliefs before she abandons more strongly held beliefs. It is crucial to recognize that additional beliefs of this general sort are bound to include a pretty peculiar element. Evidently, whatever beliefs player 1 has about the strengths of player 2’s
THE BACKWARD INDUCTION ARGUMENT
73
beliefs and her belief-revision mechanisms will have to somehow favor player 2’s retaining proposition (1) over proposition (2) or proposition (3) should player 1 cooperate. In the particular example just given, this peculiar element is that player 1 believes that player 2 believes proposition (1) more strongly than she believes proposition (2) or proposition (3). I do not doubt that player 1 could rationally believe this. But it is very much an unexpected belief – it is not something proponents of the BI argument gave anyone any reason to expect would be important to player 1’s decision. There are a variety of additional beliefs that could serve as a rational basis for player 1’s key belief. Beliefs about the strength of player 2’s beliefs and about her belief-revision mechanisms are just one sort. But it looks as if the other possibilities will be more extraordinary. Here is a second possibility: It could be that player 1 believes that a highly reliable source familiar with player 2 has said that player 2 will believe (G) just before the second round. Here is a third: It could be that player 1 believes that player 2 would believe (G) even if player 1 were to cooperate in the first round (cf., Sobel 1993, 121-122). As regards both of these cases, we certainly had no reason to expect that such beliefs would be relevant to player 1’s decision. But, more importantly, in both of these cases, player 1 has some pretty unusual beliefs. As regards the testimony case, I think the reader will agree that rationally-believed-to-be-highly-reliable sources just do not come around reporting the future beliefs of other humans all that often. As regards the other case, think what it would take for player 1 rationally to believe that player 2 would believe (G) even if player 1 were to cooperate in the first round. It seems that it would take quite a lot considering that an opening cooperative move by player 1 would minimally contradict a set of player 2’s beliefs that includes the belief of (G). I suspect that it would take nothing short of rationally believing something about the strengths of player 2’s beliefs and her belief-revision mechanisms. If player 1 has to have beliefs which are at least this peculiar, then that undermines the applicability of the BI argument. Let us take {(G), (B10 ), (B20 ), . . . } as an example. In a certain way, there is nothing wrong with this set. Insofar as pure game theory is concerned, it is a respectable set of assumptions from which it does follow that player 1 defects in the opening prisoner’s dilemma.11
74
JOHN W. CARROLL
But, when we consider the interest of this set of assumptions, when we consider how useful it would be in modeling important decision situations, there is a problem. Our original set of assumptions, {(G), (B1), (B2), . . . }, is very strong itself. It requires the players to have infinitely many higher-order beliefs (beliefs about beliefs). The only even initially plausible way of trying to justify employing these assumptions is to claim that they generate an interesting idealization, one in which the players are fully informed. {(G), (B10 ), (B20 ), . . . } is even stronger. For these assumptions to hold and for player 1 really to be rational, it looks as if player 1 has to have a belief at least as idiosyncratic as the belief that player 2 believes proposition (1) more strongly than she does proposition (2) or proposition (3), a belief of the sort that few real-life players actually have and one not readily justified by an appeal to idealization. With {(G), (B10 ), (B20 ), . . . }, the BI argument does not have anything resembling widespread relevance game theorists have suggested that it does. It will not have the sort of applicability desired by political theorists in their discussions of Hobbesian justifications of political institutions. Here is a slightly different way to make the same point: Suppose two neighboring corn farmers prefer that there not be too much corn on the market; a surplus will drive prices down. Still, both have great incentive to produce as much of the grain as possible, because the more each has to sell the more money each makes. They are faced with a prisoner’s dilemma situation. A game-theoretically-minded economist might be tempted to use the BI argument to predict what would happen (or what rationally should happen) if the farmers believed that they had to make this decision a certain finite number of times. A Hobbesian political theorist might be tempted to go a bit further, seeing here a good reason for some sort of political institution: If there were, say, fines or other sanctions tied to excessive planting, our farmers might cooperate. Of course, probably by appealing to idealization, both the game-theoretically-minded economist and the Hobbesian will have to address the threat to this backward inductive reasoning posed by the fact that it is very unlikely that these farmers have the higher-order beliefs demanded by a set of assumptions as strong as {(G), (B1), (B2), . . . }. But, as my analysis shows, such tempting uses of the BI argument require even stronger assumptions, ones along the lines of (G), (B10 ), (B20 ), . . . .
THE BACKWARD INDUCTION ARGUMENT
75
These assumptions force rational players to have additional and somewhat idiosyncratic background beliefs. It is unlikely that the farmers have these beliefs either, and – more importantly – it does not look like any appeal to idealizations could justify their presence. Thus, the temptation to invoke the BI argument should be diminished. It surely would not be appropriate to model the corn farmers’ decision situation along the lines of (G), (B10 ), (B20 ) – not unless we were prepared to accept that our farmers believe a lot of surprising things.12 My central argument obviously depends heavily on the assumption that the enrichments of our original set of assumptions preserve informedness; it is only if player 1 believes that player 2 believes (1), (2) and (3) that the rationality of the key belief becomes an issue. Still, there is no way of rescuing standard uses of the BI argument by introducing sets of assumptions that do not preserve informedness, because the need for an appeal to idealization makes informedness a hard thing to give up: In order for the BI argument to be valid, the players need to have some higher-order beliefs. For example, with our two-round game, player 1 needs to believe that player 2 will believe (G) just before the second round. For a game of three rounds, player 1 also needs to believe that player 2 will believe just before the second round that player 1 will believe (G) just before the third round. As we increase the number of rounds, we need more and more, higher- and higher-order beliefs. Informedness is important, because it is not clear how to justify including some higher-order beliefs and not others. With certain sequences, ones for which it would be unrealistic to attribute to real-life agents all the higherorder beliefs needed to make the BI argument valid, the friend of the BI argument will probably want to justify the presence of the needed belief assumptions via an appeal to idealization. But, for any very natural use of this idealization strategy, you need all the higherorder beliefs, the entire infinite collection. For example, it is hard to see how the idealization strategy (or any other approach) could be used to motivate including an assumption having player 1 believe that player 2 will believe just before the second round that player 1 will believe (G) just before the third round without also motivating including an assumption having player 2 believe that player 1 believes that player 2 will believe just before the second round that
76
JOHN W. CARROLL
player 1 will believe (G) just before the third round. Prima facie, with the idealization strategy, it is in for a penny, in for a pound. 4. COMMON KNOWLEDGE
There are certain enrichments of {(G), (B1), (B2), . . . } that warrant their own discussion. They are ones that ensure that our players have not only a common belief of (G), but also common knowledge of (G). As I pointed out at the end of Section 2, when theorists employ the BI argument, though they are usually not very clear about exactly what their assumptions are, they often do describe the players using words like ‘knows’ and ‘knowledge’ rather than ‘believes’ and ‘belief’. Could common knowledge enrichments that permit the BI argument to go through somehow be of any help in restoring the applicability of the BI argument? Before answering this question (in the negative), let me quickly mention one common knowledge enrichment of our original assumptions that does not permit the BI argument to go through. It is the knowledge analogue of our original set of assumptions. In addition to (G), it includes: (K1) Each player knows assumption (G). (K2) Each player knows that each player knows assumption (G). .. . Pretty much everything that was said above about {(G), (B1), (B2), . . . } carries over directly to this new set. In particular, just as one might think that it follows from (B2) that player 1 believes that player 2 believes (G) just before the second round of a tworound sequence of prisoner’s dilemmas, one might think that this also follows from (K2). But, of course, it does not. All (K2) tells us is that player 1 knows that player 2 initially knows (G), but it is consistent with player 2 initially knowing (G) that she not just before the second round believe (G).13 Here is a common knowledge enrichment that does entail that both players defect throughout. (There are others, but I will limit my attention to this one.) It is the knowledge analogue of {(G), (B10 ), (B20 ), . . . }. In addition to (G), it includes: (K10 ) Each player throughout the sequence knows assumption (G).
THE BACKWARD INDUCTION ARGUMENT
77
(K20 ) Each player throughout the sequence knows that each player throughout the sequence knows assumption (G). .. . As regards the BI argument and player 1’s defection in the first round, what is crucial is that this new set entails that player 1 believes that player 2 will believe (G) just before the second round. I will continue to refer to this belief as the key belief. Given these new assumptions, it is still true that player 2 initially believes propositions (1)–(3) displayed in Section 3. And, a cooperative move by player 1 in the opening round would still minimally contradict the conjunction of these three propositions initially believed by player 2. That posed the following problem for {(G), (B10 ), (B20 ), . . . }. In the absence of additional beliefs not explicitly assigned by {(G), (B10 ), (B20 ), . . . }, it appeared that player 1 could not rationally hold the key belief. He apparently needs to consider how a cooperative move in the opening round would affect player 2’s initial beliefs, and it was clear that one possible result would be that player 2 drop his belief of (G). So, in order for player 1 rationally to hold the key belief, player 1 needs to have reason for holding the key belief in spite of the fact that he might cooperate in the opening round. It looked like only some pretty peculiar beliefs could provide the necessary sort of justification. There is a difference between {(G), (K10 ), (K20 ), . . . } and {(G), (B10 ), (B20 ), . . . } that I guess might lead someone mistakenly to think that my earlier arguments do not apply to {(G), (K10 ), (K20 ), . . . }. This common knowledge set stipulates that player 1 knows that he, himself knows that player 2 believes (G) just before the second round. It deductively follows from his knowing that player 2 believes (G) just before the second round that player 2 does believe (G) just before the second round. (Knowledge implies truth.) Thus, the new assumptions, unlike {(G), (B10 ), (B20 ), . . . }, assign player 1 an added reason to believe the key belief. Despite this minor difference, {(G), (K10 ), (K20 ), . . . } does no better as regards uses of the BI argument. My earlier argument does apply; it ultimately makes no difference whether a reason for the key belief is built into the defining assumptions. With {(G), (K10 ), (K20 ), . . . }, the supposed justification of player 1’s key belief is the belief that he, himself knows that player 2 will believe (G). I guess there could be some situations that are appropriately
78
JOHN W. CARROLL
modeled with such an added justification built in. But, given that a cooperative move in the first round by player 1 would more or less contradict player 2’s belief of (G), it looks like it will only be in fairly special situations that player 1 could either know that player 2 will believe (G) just before the second round or rationally believe that he, himself knows this. Think about what it would take to know that player 2 will believe (G) just before the second round! It would take quite a lot; it would take just the sort of information discussed at the end of Section 3 (e.g., some beliefs about player 2’s beliefs and the way she revises her beliefs that favors her retaining her belief of (G)). So we do not have any reason to think that the finite sequences of prisoner’s dilemmas characterized by {(G), (K10 ), (K20 ), . . . } will have anything resembling the relevance that sequences of prisoner’s dilemmas are usually thought to have.
5. ASSESSMENT
Game-theory (like any branch of mathematics) has a pure and an applied dimension. In pure game theory, we can ‘take any hypothesis that seems amusing, and deduce its consequences’ (Russell 1956 [f.p. 1901], 1577, said about pure geometry). If we pick the hypothesis (i.e., the defining assumptions) carefully enough, we will be able to deduce whatever conclusion we like. It is only when game theory is applied that the value of the defining assumptions for philosophy and the social sciences can be truly judged. I have tried to keep this squarely in mind, always being quite explicit about what assumptions are in play and only impugning sets of assumptions insofar as they appear to hinder applicability. Just so, in Section 2, I specified a relatively minimal set of assumptions defining a class of finite sequences of prisoner’s dilemmas and explained why the BI argument does not apply when only these assumptions are in place. Then, in the third section of the paper, I argued that, if we preserve informedness, then we will not be able to support the desired uses of the BI argument by expanding the original defining set of assumptions. With stronger sets in place, the rationality of some of the beliefs needed to make the BI argument valid will be in great jeopardy, so much so that the participants of an interaction being modeled using the resulting sequences of prisoner’s dilemmas will have to have certain unexpected and peculiar beliefs.
THE BACKWARD INDUCTION ARGUMENT
79
ACKNOWLEDGMENTS
Thanks and repeated thanks to David Auerbach, Stewart Cohen, Keith DeRose, Dan Hunter, Mirek Janusz, Joe Levine, Doug Jesseph, Jesse Prinz, Peter Ripjkema, Roy Sorensen and Peter Vanderschraaf for their help in sorting out these issues. Thanks also to the editor and an anonymous referee for their many very helpful comments. Earlier versions of this paper were presented at the 1997 Pacific meetings of the American Philosophical Association, Virginia Commonwealth University, the University of Miami, North Carolina State University, Georgia State University, Arizona State University, the University of Connecticut, Western Washington University, and the City University of New York Graduate Center. The immensely helpful critical discussion at these various presentations prompted many revisions. Thanks to all the participants in those discussions.
NOTES 1. I find the argument persuasive. As will become clear below, that defection is the rational play is also a cornerstone for proponents of Hobbesian justifications of political institutions. Still, there are many who hold that rationality (properly understood) does not require the players to defect in a prisoner’s dilemma. For instance, some (e.g. Habermas 1984) even deny that rationality is primarily a property of individuals or their particular decisions, but hold instead that it is crucially a social concept. Fortunately, the central goals of my paper are somewhat independent of what rationality demands in a prisoner’s dilemma. As we will see, my question is this: Given that rational players who believe the matrix will defect in a prisoner’s dilemma, what are the conditions like under which these players will also defect throughout a finite sequence of prisoner’s dilemmas? 2. For statements of the BI argument from introductory texts, see Luce & Raiffa (1957: 98), Davis (1970: 97), Thomas (1984: 56) and Dixit & Nalebuff (1991: 100–101). For examples from discussions of Hobbesian justifications, see Sobel (1972: 158-159), Kavka (1986: 130) and Taylor (1987: 62). 3. For essentially the same reasons, I will also not be directly concerned with mathematical proofs of the existence of equilibria in extensive-form games of perfect information of the sort given by Kuhn (1953: 209). There is no limitation in restricting my attention to finite sequences of prisoner’s dilemmas. The BI argument doesn’t apply to infinite sequences.
80
JOHN W. CARROLL
4. Selten (1975) defines the notion of a subgame perfect equilibrium. Kreps & Wilson (1982) provide the definition of a sequential equilibrium. These are only two of the better known refinements. Van Damme (1991: 1–12) and Skyrms (1990: 12–27) both provide short, accessible overviews of these issues. 5. That defection is dominant in a (single-play) prisoner’s dilemma ensures that there is only one Nash equilibrium in finite sequences of prisoner’s dilemmas. My conclusions about the BI argument also apply to the discussions of refinements of the Nash equilibrium concept because the BI argument doesn’t depend on defection’s dominance. All that really matters is that defection is the rational move for players who believe the matrix. See note 12. 6. I do not mean to endorse this informal rationality constraint. But it does seem to be assumed by proponents of the BI argument. It has a close tie with one decision-theoretic conception of rationality, the maximizing evidential expected utility (MEEU) conception. Were we to assume that we can equate believing a proposition with assigning the proposition unit probability, and were we to assume that the payoffs for the players in the prisoner’s dilemmas are values of an interval utility scale representing the preferences of the players, then ignoring two special cases, the informal rationality constraint would be a consequence of the MEEU conception. The proof is straightforward. Suppose player 1 is faced with a round and believes that player 2 will defect in all the subsequent ones, in all the rounds following this upcoming round. So, since we are equating believing with assigning unit probability, player 1 assigns the proposition that player 2 defects in all the subsequent rounds unit probability. There will be certain cases about which the MEEU conception is silent: When player 1 assigns zero to either cooperating in the upcoming round or to defecting in the upcoming round, then some of the conditional probabilities relevant to determining the action that maximizes expected utility are undefined. But setting these cases aside, it follows that player 1’s conditional probability of player 2’s defecting in all the subsequent rounds given that he (player 1) defects in the upcoming round is one. Similarly, it follows that player 1’s conditional probability of player 2’s defecting in all the subsequent rounds given that he (player 1) cooperates in the upcoming round is one. Given the MEEU conception, with this collection of conditional probabilities, and keeping in mind that defection dominates cooperation in all prisoner’s dilemmas–including the upcoming round, it follows that player 1 defects in this round just as the informal rationality constraint says he will. For further discussion of the informal rationality constraint’s connection to decision-theoretic conceptions of rationality, see Carroll (1999). 7. See Reny (1988: 2), Pettit & Sugden (1989: 171-172) and Stalnaker (1996a, b). For some earlier acknowledgments of the importance of what players will believe later in the sequence of prisoner’s dilemmas, see Sorensen (1986: 345), Sobel (1972: 158-159) and Schick (1977: 790-793).
THE BACKWARD INDUCTION ARGUMENT
81
8. As may be obvious, by ‘rational’, I do not just mean satisfies the informal rationality constraint. I mean rational in the ordinary sense of ‘rational’, whatever that amounts to. Though I have no analysis of rationality to offer, I will only be making fairly weak assumptions about what rationality requires. 9. Others have considered the claim that an opening cooperative move by player 1 might contradict beliefs initially had by player 2. See Reny (1989: 364366; 1992: 111; 1993: 261-262; and 1995: 10), Pettit & Sugden (1989: 173), Sorensen (1986: 345) and Hardin (1982: 149). I have benefitted greatly from their discussions. Many of these authors, however, sometimes suggest that there are finite sequences of prisoner’s dilemmas in which player 1 cooperates in order to generate the contradiction, thus changing player 2’s beliefs, thus leading to some cooperative outcome. For one example, consider what Reny has to say below. It is said about TOL, an extensive-form game of perfect information that is parallel in many respects to a finite sequence of prisoner’s dilemmas. (By ‘knowledge’, Reny means ‘assigns unit probability’.) ...the argument put forward here does not require that common knowledge of maximizing behavior fail at the beginning of the game. The reason for this is that ... by leaving the first dollar, player I can ensure that from then on maximizing behavior cannot be common knowledge regardless of the players’ initial knowledge. And this may make player I better off (from his point of view) than taking the first dollar, since without the common knowledge player II may rationally allow the pot to grow (1992: 111). But this is at least misleading. On the one hand, if we build into the defining assumptions that the common belief holds throughout the sequence, then (i) if player 1 were to start by cooperating, he would provide player 2 with evidence contradicting player 2’s original beliefs, but (ii) player 1 will not start by cooperating–with these assumptions, it follows that player 1 defects throughout. On the other hand, if we only assume that the common belief holds at the outset, then (i) it does not follow that player 1 will not start by cooperating, but (ii) if player 1 were to start by cooperating, he would not provide player 2 with evidence contradicting player 2’s original beliefs. In neither case does player 1 ‘ensure’ that the common belief does not continue. 10. There are certain very special cases with some similarities to the present cases for which there is at least the appearance that this sort of belief might be rational even in the absence of special additional beliefs. These cases involve variations on the lottery paradox. Suppose I believe that you believe that there are at least one thousand tickets in the lottery. I also believe that you believe of each of the first thousand tickets that it will lose. I believe that you will soon learn that there are exactly a thousand tickets in the lottery. That there are exactly 1000 tickets in this fair lottery contradicts the set consisting of your 1000 beliefs about the 1000 tickets. One might be tempted to say that I could rationally believe that you still will believe that ticket 1 will lose, because some are tempted to say that the rational response to such contradicting information is to continue to hold your original beliefs together with the
82
JOHN W. CARROLL
new contradicting information (cf. Kyburg 1970, 1974). I do not, however, find this kind of example convincing. First, much of its force rests on a fairly controversial resolution of the lottery paradox, one game theorists have hardly embraced. Second, and even so, I think the temptation to judge the belief to be rational derives from a tacit assumption about some background beliefs of the cognizer. In being tempted to judge my belief to be rational, we tacitly assume that I know quite a lot about why you believe the things you do. As the example is constructed, we naturally assume that I believe that you believe that each ticket will lose because it is very unlikely that it will win, that each of your 1000 beliefs has exactly as much going for it as any of the others, and that the new information will have at least as much (but not much more) going for it. So the rationality of my belief still depends on some extra beliefs. Furthermore, the situation that our players find themselves in is sufficiently unlike a lottery-paradox situation so that this kind of example does nothing to challenge anything I have said above. Most importantly, the minimally inconsistent sets will contain only four propositions! 11. Bicchieri (1989) seems to think that the contradiction between player 1’s cooperating in the first round and player 2’s initial beliefs is an indication that there is something theoretically objectionable about defining sets of assumptions, like {(G), (B10 ), (B20 ), . . . }, that make the BI argument valid. Bicchieri, citing Reny, says ‘An obvious requirement a theory of a game has to satisfy is that it be free of contradiction at every information set’ (1989: 70). I find myself in accord with Sobel (1993: 124) wondering why we should adopt this requirement. 12. I have restricted my attention to finite sequences of prisoner’s dilemmas. But it has not escaped my notice that the arguments could rather easily be extended to other games, especially extensive-form games of perfect information. Reny (1993: 261-262) shows that essentially the same contradiction described above would arise in these games. He argues that this calls into question the ‘plausibility’ (1993: 259) of standard equilibrium concepts like subgame perfection (and also calls into question some of the conclusions of Bernheim (1984) and Pearce (1984)). But, it is not really the plausibility of the notions that is at issue. With enough assumptions, we can establish that the solution of a game will be a subgame perfect equilibrium. The real issue is the usefulness of subgame perfection. Reny’s and my arguments show that, in order to conclude that rational players will play subgame perfect equilibrium strategies, truly rational players will have to have background beliefs permitting the players to believe initially that certain beliefs will be had later despite the fact that they are aware that something might happen in the meantime that would contradict those beliefs. There does not appear to be any way to justify the presence of these background beliefs. 13. The temptation to make the inference from (K2) may be even greater than the temptation to make the inference from (B2). There is this added temptation if one is drawn to the thesis that knowledge is evidentially secure; that, if
THE BACKWARD INDUCTION ARGUMENT
83
S is rational and S knows P at some initial time, then no purely evidential considerations can make it the case that at some later time S does not believe P. Ginet (1980) conclusively shows why this thesis is false. (See also Jackson 1987: 120-121, and Sorensen 1988: 441.) Stalnaker (1996a, b) considers the impact that differing analyses of knowledge have on backward induction. As he points out, there are ways of defining ‘knowledge’ such that the BI argument does show that rational players who are only explicitly assumed to have so-called common knowledge at the start of the sequence will defect throughout. As he also recognizes (see 1996b, his note 4), the ways of defining knowledge he considers are not correct definitions of ‘knowledge’; they do not ‘faithfully reflect’ the usual meaning of ‘knowledge’ (cf. Aumann 1995: 14).
REFERENCES Aumann, R. (1995), Backward induction and common knowledge of rationality, Games and Economic Behavior 8: 6–19. Axelrod, R. (1984), The Evolution of Cooperation (Basic Books, New York). Bernheim, D. (1984), Rationalizable strategic behavior, Econometrica 52: 1007– 1028. Bicchieri, C. (1989), Self-refuting theories of strategic interaction: A paradox of common knowledge’, Erkenntnis 30: 69–85. Bicchieri, C. (1990), Paradoxes of rationality, Midwest Studies in Philosophy 15: 65–79. Carroll, J. (1999), Decision-theoretic finitely iterated prisoner’s dilemmas. Analysis (forthcoming). Davis, M. (1970), Game Theory (Basic Books, New York). Dixit, A. & Nalebuff, B. (1991), Thinking Strategically (Norton, New York). Ginet, C. (1980), Knowing less by knowing more, Midwest Studies in Philosophy 5: 151–161. Habermas, J. (1984), Theory of Communicative Action, Volume 1 (Beacon Press, Boston). Hardin, R. (1982), Collective Action (Johns Hopkins University Press, Baltimore). Jackson, F. (1987), Conditionals (Blackwell, Oxford). Kavka, G. (1986), Hobbesian Moral and Political Theory (Princeton University Press, Princeton). Kreps, D. & Wilson, R. (1982), Sequential equilibria, Econometrica 50: 863–894. Kuhn, H. (1953), Extensive games and the problem of information, in: Kuhn & Tucker (eds.), Contribution to the Theory of Games, Volume 2 (Princeton University Press, Princeton). Kyburg, H. (1970), Conjunctivitis, in Swain (ed.), Induction, Acceptance, and Rational Belief (D. Reidel, Dordrecht). Kyburg, H. (1974), The Logical Foundations of Statistical Inference (D. Reidel, Dordrecht). Luce, D. & Raiffa, H. (1957), Games and Decisions (Wiley, New York).
84
JOHN W. CARROLL
Pettit, P. and Sugden, R. (1989), The backward induction paradox, Journal of Philosophy 86: 169–182. Pearce, D. (1984), Rationalizable strategic behavior and the problem of perfection, Econometrica 52: 1029–1053. Reny, P. (1988), Rationality, common knowledge and the theory of games, Ph.D. Dissertation, Chapter 1, Princeton University. Reny, P. (1989), Common knowledge and games with perfect information, Philosophy of Science Association 1988, Volume 2, 363–369. Reny, P. (1992), Rationality in extensive-form games, Journal of Economic Perspectives 6: 103–118. Reny, P. (1993), Common belief and the theory of games with perfect information, Journal of Economic Theory 59: 257–274. Reny, P. (1995), Rational behaviour in extensive-form games, Canadian Journal of Economics 28: 1–16. Russell, B. (1956), Mathematics and the metaphysicians, in Newman (ed.), The World of Mathematics, Volume 3 (Simon and Schuster, New York). Schick, F. (1977), Some notes on thinking ahead, Social Research 44: 786–800. Selten, R. (1975), Reexamination of the perfectness concept for equilibrium points in extensive games, International Journal of Game Theory 4: 25–55. Skyrms, B. (1990), The Dynamics of Rational Deliberation (Harvard University Press, Cambridge). Sobel, J. (1972), The need for coercion, Pennock & Chapman (eds.) Coercion, (Aldine & Atherton, Chicago). Sobel, J. (1993), Backward-induction arguments: A paradox regained, Philosophy of Science 60: 114–133. Sorensen, R. (1986), Blindspotting and choice variations of the prediction paradox, American Philosophical Quarterly 23: 337–352. Sorensen, R. (1988), Dogmatism, junk knowledge, and conditionals, Philosophical Quarterly 38: 433–454. Stalnaker, R. (1996a), Knowledge, belief, and counterfactual reasoning in games, Economics and Philosophy 12: 133–163. Stalnaker, R. (1996b), Backward Induction Arguments (manuscript). Taylor, M. (1987), The Possibility of Cooperation (Cambridge University Press, Cambridge). Thomas, L. (1984), Games, Theory, and Applications (Ellis Horwood Ltd., Chichester). van Damme, E. (1991), Stability and Perfection of Nash Equilibria (Springer Verlag, Berlin/New York).
Address for correspondence: Dr J. W. Carroll, Department of Philosophy and Religion, North Carolina State University, P.O. Box 8103, Raleigh, NC 276958103, USA Phone: (919) 515 3214; Fax: (919) 515 7856; E-mail:
[email protected]