The standard backward-induction reasoning in a game like the centipede assumes that the players maintain a common belief in rationality throughout the game. But that is a dubious assumption. Suppose the first player X didn't terminate the game in the first round; what would the second player Y think then? Since the backwards-induction argument says X should terminate the game, and it is supposed to be a sound argument, Y might be entitled to doubt X's rationality. Alternatively, (...) Y might doubt that X believes Y is rational, or that X believes Y believes X is rational, or Y might have some higher-order doubt. X’s deviant first move might cause a breakdown in common belief in rationality, therefore. Once that goes, the entire argument fails. The argument also assumes that the players act rationally at each stage of the game, even if this stage could not be reached by rational play. But it is also dubious to assume that past irrationality never exerts a corrupting influence on present play. However, the backwards-induction argument can be reconstructed for the centipede game on a more secure basis.1 It may be implausible to assume a common belief in rationality throughout the game, however the game might go, but the argument requires less than this. The standard idealisations in game theory certainly allow us to assume a common belief in rationality at the beginning of the game. They also allow us to assume this common belief persists so long as no one makes an irrational move. That is enough for the argument to go through. (shrink)

There are two curious features about the backward induction argument (BIA) to the effect that repeated non-cooperation is the rational solution to the finite iterated prisoner’s dilemma (FIPD). First, however compelling the argument may seem, one remains hesitant either to recommend this solu- tion to players who are about to engage in cooperation or to explain cooperation as a deviation from rational play in real-life FIPD’s. Second, there seems to be a similarity between the BIA for the FIPD and (...) the surprise exam paradox (SEP) and one cannot help but wonder whether the former is indeed no more than an instance of the latter. I argue that there is an important difference between the BIA for the FIPD and the SEP, but that a comparison to the SEP can help us understand why the conclusion of the BIA for the FIPD strikes us as a counterintuitive solution to real-life FIPD’s. (shrink)

A cornerstone of game theory is backward induction, whereby players reason backward from the end of a game in extensive form to the beginning in order to determine what choices are rational at each stage of play. Truels, or three-person duels, are used to illustrate how the outcome can depend on (1) the evenness/oddness of the number of rounds (the parity problem) and (2) uncertainty about the endpoint of the game (the uncertainty problem). Since there is no known endpoint (...) in the latter case, an extension of the idea of backward induction is used to determine the possible outcomes. The parity problem highlights the lack of robustness of backward induction, but it poses no conflict between foundational principles. On the other hand, two conflicting views of the future underlie the uncertainty problem, depending on whether the number of rounds is bounded (the players invariably shoot from the start) or unbounded (they may all cooperate and never shoot, despite the fact that the truel will end with certainty and therefore be effectively bounded). Some real-life examples, in which destructive behavior sometimes occurred and sometimes did not, are used to illustrate these differences, and some ethical implications of the analysis are discussed. (shrink)

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. (shrink)

A large class of games is that of non-cooperative, extensive form games of perfect information. When the length of these games is finite, the method used to reach a solution is that of a backward induction. Working from the terminal nodes, dominated strategies are successively deleted and what remains is a unique equilibrium. Game theorists have generally assumed that the informational requirement needed to solve these games is that the players have common knowledge of rationality. This assumption, however, has (...) given rise to several problems and paradoxes. Most notably, it has been shown that the common knowledge assumption makes the theory of the game inconsistent at some information set. The present paper shows that a) no common knowledge of rationality need be assumed for the backward induction solution to hold. Rather, it is sufficient that the players have a number of levels of knowledge proportional to the length of the game, and b) it is also necessary that the number of levels of knowledge is finite and proportional to the length of the game. For a higher number of levels of knowledge, inconsistencies arise. (shrink)

The backward induction controversy in game theory flared up and then practically ended within a decade – the 1990s. The protagonists, however, did not converge on an agreement about the source of the controversy. Why was this the case, if opposing sides had access to the same modelling techniques and empirical facts? In this paper I offer an explanation for this controversy and its unsettled end. The answer is not to be found in the modelling claims made by the (...) opposing protagonists, but in the tacit metaphors they operate under. Aristotle defined metaphor as giving a 'thing a name that belongs to something else' (Poetica, 1457b). The meaning of metaphors has not changed much since then – in contrast to models which are comparatively new, and still not well-understood, scientific tools. The controversy of backward induction in game theory provides a test bed for the explanatory power of metaphors. This paper frames the controversy in terms of metaphor choice to provide a common framework for the protagonists. This results in the identification of three different domains – mathematical logic, game theory and the world – each connected to the other via different metaphors. The controversy around backward induction is placed in, and tentatively explained by, this framework. (shrink)

Backward induction has been the standard method of solving finite extensive-form games with perfect information, notwithstanding the fact that this procedure leads to counter-intuitive results in various games. However, beginning in the late eighties, the method of backward induction became an object of criticism. It is claimed that the assumptions needed for its defence are quite implausible, if not incoherent. It is therefore natural to ask for the justification of backward induction: Can one show that rational players (...) who know the structure of the game, have trust in each other's practical rationality and reason correctly, will act in accordance in backward induction? Several researchers have tried a justification of this kind, but the argument presented in Robert Aumann's paper from 1995 is perhaps the most well-known and influential attempt to provide such a justification. Clausing provides a sustained discussion of the justification problem for backward induction. It is an excellent work and the criticism I will present below does not detract from this evaluation: the issues discussed by the author are complex and it is difficult to get everything right. Furthermore, I hope that the criticism to be presented may be instructive; Even though it has not been Clausing's intention, his logical reconstruction of Aumann's defence of backward induction allows us to see very clearly what is wrong with that argument. It also provides us with * This paper was presented at workshops in Lund and in Uppsala, in the Fall of 1999. I am indebted to the participants for their useful comments. The work on the paper was supported by a generous research grant from The Bank of Sweden Tercentenary Foundation. (shrink)

According to a familiar argument, iterated prisoner's dilemmas of known finite lengths resolve for ideally rational and well-informed players: They would defect in the last round, anticipate this in the next to last round and so defect in it, and so on. But would they anticipate defections even if they had been cooperating? Not necessarily, say recent critics. These critics "lose" the backward-induction paradox by imposing indicative interpretations on rationality and information conditions. To regain it I propose subjunctive interpretations. (...) To solve it I stress that implications for ordinary imperfect players are limited. (shrink)

Two justifications of backward induction (BI) in generic perfect information games are formulated using Bonanno's (1992; Theory and Decision 33, 153) belief systems. The first justification concerns the BI strategy profile and is based on selecting a set of rational belief systems from which players have to choose their belief functions. The second justification concerns the BI path of play and is based on a sequential deletion of nodes that are inconsistent with the choice of rational belief functions.

Backward induction was one of the earliest methods developed for solving finite sequential games with perfect information. It proved to be especially useful in the context of Tom Schelling’s ideas of credible versus incredible threats. BI can be also extended to solve complex games that include an infinite number of actions or an infinite number of periods. However, some more complex empirical or experimental predictions remain dramatically at odds with theoretical predictions obtained by BI. The primary example of such (...) a troublesome game is Centipede. The problems appear in other long games with sufficiently complex structure. BI also shares the problems of subgame perfect equilibrium and fails to eliminate certain unreasonable Nash equilibria. (shrink)

We conceive of a player in dynamic games as a set of agents, which are assigned the distinct tasks of reasoning and node-specific choices. The notion of agent connectedness measuring the sequential stability of a player over time is then modeled in an extended type-based epistemic framework. Moreover, we provide an epistemic foundation for backward induction in terms of agent connectedness. Besides, it is argued that the epistemic independence assumption underlying backward induction is stronger than usually presumed.

According to decision theory, the rational initial action in a sequential decision-problem may be found by backward induction or folding back. But the reasoning which underwrites this claim appeals to the agent's beliefs about what she will later believe, about what she will later believe she will still later believe, and so forth. There are limits to the depth of people's beliefs. Do these limits pose a threat to the standard theory of rational sequential choice? It is argued, first, (...) that the traditional solutions of certain games depend on knowledge which exceeds depth limits, and that these solutions therefore cannot be shown rational in the usual sense. Then, for that related reason even folding back solutions of one-person problems cannot be! A revision of our notion of rational choice is proposed, analogous to the reliabilist account of knowledge of Goldman and others, by which this paradox is resolved. (shrink)

The problem of finding sufficient doxastic conditions for backward induction in games of perfect information is analyzed in a syntactic framework with subjunctive conditionals. This allows to describe the structure of the game by a logical formula and consequently to treat beliefs about this structure in the same way as beliefs about rationality. A backward induction and a non-Nash equilibrium result based on higher level belief in rationality and the structure of the game are derived.

Backwards induction is an intriguing form of argument. It is used in a number of different contexts. One of these is the surprise exam paradox. Another is game theory. But its use is problematic, at least sometimes. The purpose of this paper is to determine what, exactly, backwards induction is, and hence to evaluate it. Let us start by rehearsing informally some of its problematic applications.

The traditional form of the backward induction argument, which concludes that two initially rational agents would always defect, relies on the assumption that they believe they will be rational in later rounds. Philip Pettit and Robert Sugden have argued, however, that this assumption is unjustified. The purpose of this paper is to reconstruct the argument without using this assumption. The formulation offered concludes that two initially rational agents would decide to always defect, and relies only on the weaker assumption (...) that they do not believe they will not be rational in later rounds. The argument employs the idea that decisions justify revocable presumptions about behaviour. (shrink)

We formalise a notion of dynamic rationality in terms of a logic of conditional beliefs on (doxastic) plausibility models. Similarly to other epistemic statements (e.g. negations of Moore sentences and of Muddy Children announcements), dynamic rationality changes its meaning after every act of learning, and it may become true after players learn it is false. Applying this to extensive games, we “simulate” the play of a game as a succession of dynamic updates of the original plausibility model: the epistemic situation (...) when a given node is reached can be thought of as the result of a joint act of learning (via public announcements) that the node is reached. We then use the notion of “stable belief”, i.e. belief that is preserved during the play of the game, in order to give an epistemic condition for backward induction: rationality and common knowledge of stable belief in rationality. This condition is weaker than Aumann’s and compatible with the implicit assumptions (the “epistemic openness of the future”) underlying Stalnaker’s criticism of Aumann’s proof. The “dynamic” nature of our concept of rationality explains why our condition avoids the apparent circularity of the “backward induction paradox”: it is consistent to (continue to) believe in a player’s rationality after updating with his irrationality. (shrink)

We analyze the sequential structure of dynamic games with perfect information. A three-stage account is proposed, that species setup, reasoning and play stages. Accordingly, we define a player as a set of agents corresponding to these three stages. The notion of agent connectedness is introduced into a type-based epistemic model. Agent connectedness measures the extent to which agents' choices are sequentially stable. Thus describing dynamic games allows to more fully understand strategic interaction over time. In particular, we provide suffcient conditions (...) for backward induction in terms of agent connectedness. Also, our framework makes explicit that the epistemic independence assumption involved in backward induction reasoning is stronger than usually presumed, and makes accessible multiple-self interpretations for dynamic games. (shrink)

According to the standard objection to backward induction in games, its application depends on highly questionable assumptions about the players' expectations as regards future counterfactual game developments. It seems that, in order to make predictions needed for backward reasoning, the players must expect each player to act rationally at each node that in principle could be reached in the game, and also to expect that this confidence in the future rationality of the players would be kept by each player (...) come what may: even at the game-nodes that could only be reached by irrational play. Both expectations seem to be rather unreasonable: a player's initial disposition to rational behaviour may be weakened by a long stretch of irrational play on his part and, even more importantly, his initial confidence in the other players' future rationality may be undermined by an irrational play on their part. For different formulations of this objection see Binmore, Reny and, Bicchieri, Pettit and Sugden. and Aumann and.). (shrink)

Many philosophers and game theorists have been struck by the thought that the backward induction argument (BIA) for the finite iterated pris- oner’s dilemma (FIPD) recommends a course of action which is grossly counter-intuitive and certainly contrary to the way in which people behave in real-life FIPD-situations (Luce and Raiffa 1957, Pettit and Sugden 1989, Bovens 1997).1 Yet the backwards induction argument puts itself forward as binding upon rational agents. What are we to conclude from this? Is (...) it that people in real-life FIPD-situations tend to act irrationally and that our own intuitions about what to do in such situations reveal us to be irra- tional? Alternatively, should we abandon game theory and decision theory as a guide to rationality? Or are there other ways in which the apparent disparity between the dictates of rationality and the reality of reasoning can be accommodated? (shrink)

Robert Aumann argues that common knowledge of rationality implies backward induction in finite games of perfect information. I have argued that it does not. A literature now exists in which various formal arguments are offered in support of both positions. This paper argues that Aumann's claim can be justified if knowledge is suitably reinterpreted.

The logical foundations of game-theoretic solution concepts have so far been explored within the con¯nes of epistemic logic. In this paper we turn to a di®erent branch of modal logic, namely temporal logic, and propose to view the solution of a game as a complete prediction about future play. The branching time framework is extended by adding agents and by de¯ning the notion of prediction. A syntactic characterization of backward induction in terms of the property of internal consistency of (...) prediction is given. (shrink)

We formalise a notion of dynamic rationality in terms of a logic of conditional beliefs on plausibility models. Similarly to other epistemic statements, dynamic rationality changes its meaning after every act of learning, and it may become true after players learn it is false. Applying this to extensive games, we "simulate" the play of a game as a succession of dynamic updates of the original plausibility model: the epistemic situation when a given node is reached can be thought of as (...) the result of a joint act of learning that the node is reached. We then use the notion of "stable belief, i.e. belief that is preserved during the play of the game, in order to give an epistemic condition for backward induction: rationality and common knowledge of stable belief in rationality. This condition is weaker than Aumann's and compatible with the implicit assumptions underlying Stalnaker's criticism of Aumann's proof. The "dynamic" nature of our concept of rationality explains why our condition avoids the apparent circularity of the "backward induction paradox": it is consistent to believe in a player's rationality after updating with his irrationality. (shrink)

According to the so-called “Folk Theorem” for repeated games, stable cooperative relations can be sustained in a Prisoner’s Dilemma if the game is repeated an indefinite number of times. This result depends on the possibility of applying strategies that are based on reciprocity, i.e., strategies that reward cooperation with subsequent cooperation and punish defectionwith subsequent defection. If future interactions are sufficiently important, i.e., if the discount rate is relatively small, each agent may be motivated to cooperate by fear of retaliation (...) in the future. For finite games, however, where the number of plays is known beforehand, there is a backward induction argument showing that rational agents will not be able to achieve cooperation. On behalf of the Hobbesian “Foole”, who cannot see any advantage in cooperation, Gregory Kavka (1983, 1986) has presented an argument that significantly extends the range of the backward induction argument. He shows that, for the backward induction argument to be effective, it is not necessary that the precise number of future interactions be known. It is sufficient that there is a known definite upper bound on the number of interactions. A similar argument is developed by John W. Carroll (1987). We will here question the assumption of a known upper bound. When the assumption is made precise in the way needed for the argument to go through, its apparent plausibility evaporates. We then offer a reformulation of the argument, based on weaker, and more plausible, assumptions. (shrink)

Gian Aldo Antonelli and Cristina Bicchieri. Backwards Forwards Induction.

An important approach to game theory is to examine the consequences of beliefs that agents may have about each other. This paper investigates respect for public preferences. Consider an agent A who believes that B strictly prefers an option a to an option b. Then A respects B’s preference if A assigns probability 1 to the choice of a given that B chooses a or b. Respect for public preferences requires that if it is common belief that B prefers a (...) to b, then it is common belief that all other agents respect that preference. Along the lines of Blume, Brandenburger and Dekel [3] and Asheim [1], I treat respect for public preferences as a constraint on lexicographic probability systems. The main result is that given respect for public preferences and perfect recall, players choose in accordance with Iterated Backward Inference. Iterated Backward Inference is a procedure that generalizes standard backward induction reasoning for games of both perfect and imperfect information. From Asheim’s characterization of proper rationalizability [1] it follows that properly rationalizable strategies are consistent with respect for public preferences; hence strategies eliminated by Iterated Backward Inference are not properly rationalizable. (shrink)

The ability to anticipate the future is of great benefit to any organism. Whenever such a foreseeing takes place, it typically happens because an organism has been able to learn about some regularity in the past and then uses this information to expect some happenings in the future. Modern human beings have perfected this capacity far beyond any other animal by getting to know the laws by which nature operates. But it is still based on past experience that even human (...) beings are able to say something about the future. So every form of anticipation of the future relies on inductive reasoning based on knowledge of causal processes in the past. Both these processes and the processes by which we learn to anticipate the future are common in the sense that it is always an earlier cause that brings about a later effect. The ability to anticipate depends on the fact that our cognitive faculties only work on information that stems from the past. Had it been possible for us to receive reliable information about the future, the ability of anticipation might not have existed or might have been less faulty than it sometimes is. (shrink)

An important approach to game theory is to examine the consequences of beliefs that rational agents may have about each other. This paper considers respect for public preferences. Consider an agent A who believes that B strictly prefers an option a to an option b. Then A respects B’s preference if A considers the choice of a “infinitely more likely” than the choice of B; equivalently, if A assigns probability 1 to the choice of a given that B chooses a (...) or b. Respect for public preferences requires that if it is common belief that B prefers a to b, then it is common belief that all other agents respect that preference. Along the lines of Blume, Brandenburger and Dekel [4] and Asheim [1], I treat respect for public preferences as a constraint on lexicographic probability systems. The main result is that if respect for public preferences and perfect recall obtains, then players choose in accordance with Iterated Backward Inference. Iterated Backward Inference is a procedure that generalizes standard backward induction reasoning for games of both perfect and imperfect information. From Asheim’s characterization of proper rationalizability [1] it follows that properly rationalizable strategies are consistent with respect for public preferences; hence strategies eliminated by Iterated Backward Inference are not properly rationalizable. (shrink)

Rational choice theory enjoys unprecedented popularity and influence in the behavioral and social sciences, but it generates intractable problems when applied to socially interactive decisions. In individual decisions, instrumental rationality is defined in terms of expected utility maximization. This becomes problematic in interactive decisions, when individuals have only partial control over the outcomes, because expected utility maximization is undefined in the absence of assumptions about how the other participants will behave. Game theory therefore incorporates not only rationality but also common (...) knowledge assumptions, enabling players to anticipate their co-players' strategies. Under these assumptions, disparate anomalies emerge. Instrumental rationality, conventionally interpreted, fails to explain intuitively obvious features of human interaction, yields predictions starkly at variance with experimental findings, and breaks down completely in certain cases. In particular, focal point selection in pure coordination games is inexplicable, though it is easily achieved in practice; the intuitively compelling payoff-dominance principle lacks rational justification; rationality in social dilemmas is self-defeating; a key solution concept for cooperative coalition games is frequently inapplicable; and rational choice in certain sequential games generates contradictions. In experiments, human players behave more cooperatively and receive higher payoffs than strict rationality would permit. Orthodox conceptions of rationality are evidently internally deficient and inadequate for explaining human interaction. Psychological game theory, based on nonstandard assumptions, is required to solve these problems, and some suggestions along these lines have already been put forward. Key Words: backward induction; Centipede game; common knowledge; cooperation; epistemic reasoning; game theory; payoff dominance; pure coordination game; rational choice theory; social dilemma. (shrink)

La théorie des jeux évolutionnaires s'oppose à la théorie des jeux classique en ce qu 'elle élimine les raisonnements des joueurs. Peut-elle dépasser les apories de la théorie classique ? Mais en reconsidérant le raisonnement classique d'induction rétrograde, en y introduisant des possibilités de révision, on évite son aspect paradoxal. L'intérêt de la théorie des jeux évolutionnaires est donc surtout de simuler l'évolution d'interactions dans des populations.Evolutionary game theory does not take into account reasoning players, in contrast with classical (...) game theory. Can it overcome some drawbacks of classical theory ? If we reconsider the backward induction reasoning, and if introduce the possibility of revising, paradoxes and drawbacks disappear. So the main interest of evolutionary game theoiy consists in the simulation of evolution of interactions among populations. (shrink)

One might think that money pumps directed at agents with cyclic preferences can be avoided by foresight. This view was challenged two decades ago by the discovery of a money pump with foresight, which works against agents who use backward induction. But backward induction implausibly assumes that the agent would act rationally and retain her trust in her future rationality even at choice nodes that could only be reached if she were to act irrationally. This worry does not (...) apply to BI-terminating decision problems, where at each choice node backward induction prescribes a move that terminates further action. For BI-terminating decision problems, it is enough to assume that rationality and trust in rationality are retained at choice nodes reachable by rational moves. The old money pump with foresight was not BI-terminating. In this paper, we present a new money pump with foresight, one that is both BI-terminating and considerably simpler. (shrink)

In the standard money pump, an agent with cyclical preferences can avoid exploitation if he shows foresight and solves his sequential decision problem using backward induction (BI). This way out is foreclosed in a modified money pump, which has been presented in Rabinowicz (2000). There, BI will lead the agent to behave in a self-defeating way. The present paper describes another sequential decision problem of this kind, the Centipede for an Intransitive Preferrer, which in some respects is even more (...) striking than the modified pump. In the new problem, the BI reasoning that implies self-defeating behavior does not rest on the controversial robustness assumption concerning beliefs in one's future rationality. This strengthens the claim that foresight cannot save the intransitive preferrer from a self-defeating course of action. (shrink)

We present an axiomatic approach for a class of finite, extensive form games of perfect information that makes use of notions like “rationality at a node” and “knowledge at a node.” We distinguish between the game theorist's and the players' own “theory of the game.” The latter is a theory that is sufficient for each player to infer a certain sequence of moves, whereas the former is intended as a justification of such a sequence of moves. While in general the (...) game theorist's theory of the game is not and need not be axiomatized, the players' theory must be an axiomatic one, since we model players as analogous to automatic theorem provers that play the game by inferring (or computing) a sequence of moves. We provide the players with an axiomatic theory sufficient to infer a solution for the game (in our case, the backwards induction equilibrium), and prove its consistency. We then inquire what happens when the theory of the game is augmented with information that a move outside the inferred solution has occurred. We show that a theory that is sufficient for the players to infer a solution and still remains consistent in the face of deviations must be modular. By this we mean that players have distributed knowledge of it. Finally, we show that whenever the theory of the game is group-knowledge (or common knowledge) among the players (i.e., it is the same at each node), a deviation from the solution gives rise to inconsistencies and therefore forces a revision of the theory at later nodes. On the contrary, whenever a theory of the game is modular, a deviation from equilibrium play does not induce a revision of the theory. (shrink)

This collection of papers in epistemic logic is oriented towards applications to game theory and individual decision theory. Most of these papers were presented at the inaugural conference of the LOFT (Logic for the Theory and Games and Decisions) conference series, which took place in 1994 in Marseille. Among the notions dealt with are those of common knowledge and common belief, infinite hierarchies of beliefs and belief spaces, logical omniscience, positive and negative introspection, backward induction and rationalizable equilibria in (...) game theory. (shrink)

In evolutionary models of indirect reciprocity, reputation mechanisms can stabilize cooperation even in severe cooperation problems like the prisoner’s dilemma. Under certain circumstances, conditionally cooperative strategies, which cooperate iff their partner has a good reputation, cannot be invaded by any other strategy that conditions behavior only on own and partner reputation. The first point of this paper is to show that an evolutionary version of backward induction can lead to a breakdown of this kind of indirectly reciprocal cooperation. Backward (...) induction, however, requires strategies that count and then cease to cooperate in the last, last but one, last but two, … game they play. These strategies are unlikely to exist in natural settings. We then present two new findings. (1) Surprisingly, the same kind of breakdown is also possible without counting. Strategies using rare golden opportunities for defection can invade conditional cooperators. This can create further golden opportunities, inviting the next wave of opportunists, and so on, until cooperation breaks down completely. (2) Cooperation can be stabilized against these opportunists, by letting an individual’s initial reputation be inherited from that individual’s parent. This ‘inclusive reputation’ mechanism can cope with any observably opportunistic strategy. Offspring of opportunists who successfully exploited a conditional cooperator cannot repeat their parents’ success because they inherit a bad reputation, which forewarns conditional cooperators in later generations. (shrink)