Eco514|Game Theory Forward Induction Marciano Siniscalchi January 10, 2000 Introduction One of the merits of the notion of sequential equilibrium is the emphasis on out-of- equilibrium beliefs|that is, on beliefs (about past and future play) at information sets that should not be reached if a given equilibrium is played. The key insight of extensive-form analysis is that out-of-equilibrium beliefs deter- mine equilibrium behavior. For instance, consider the simple two-stage entry deter- rence game in which a potential entrant decides whether to enter a market or stay out, and the incumbent decides whether to ght or acquiesce after the entrant’s move. The Nash equilibrium in which the entrant stays out is supported by the belief that the incumbent will ght; but if we think that ghting is not a credible threat, this equilibrium collapses. But things can become much more subtle|and interesting. In particular, se- quential equilibrium takes care of the issue of non-credible threats, but it sometimes still relies on \implausible inferences" out of equilibrium. This lecture addresses this point, focusing on the notion of forward induction Outside Options and Burning Money Following much of the literature in this eld, it’s best to begin with a couple of key examples. Consider the pro le (OutB, R) in the game in Figure 1. This is clearly a Nash equilibrium; moreover, since B is a best reply to R and conversely, (OutB, R) is actually a subgame-perfect equilibrium. In fact, you can convince yourself that it is sequential and trembling-hand perfect as well. And yet, and yet... does it really make sense for Player 2 to expect Player 1 to follow In (a deviation) with B? Note that InB is strictly dominated, hence certainly irrational for Player 1: Out does strictly better. 1 1 Out 2,2 In @ @ @ @ @@2L R 1 T B 3,1 0,0 0,0 1,3 Figure 1: The Battle of the Sexes with an Outside Option On the other hand, while In constitutes a deviation from equilibrium play, it is not necessarily an irrational choice per se: if Player 1 expects Player 2 to choose L with su ciently high probability, then In followed by T is actually optimal! Wait a moment, you will say: how can Player 1 expect Player 2 to choose L when the equilibrium pro le says he should play R? Well, that’s a good question. However, note that the same equilibrium pro le also says that Player 1 should not deviate to In; so, in some sense, its prescriptions should be taken with a grain of salt! More rigorously, faced with a deviation to In, Player 2 may either think that this was merely the result of a mistake, a tremble, in which case he is entitled to continue to believe that Player 1 expects R and hence plays B; or, he can abandon his faith in this equilibrium, and attempt to come up with some alternative theory of Player 1’s behavior. The rst route is the story implicit in sequential equilibrium, THPE, and backward induction in general. According to this story, (OutB, R) is a ne equilibrium. The second route leads to forward induction. This notion is quite distinct from backward induction|and sometimes even at odds with it! But, it makes a lot of sense, at least in the opinion of this writer... The two main tenets of forward induction are: Intentionality: any move, including deviations from the equilibrium path, is intentional and purposeful. Rationalization: players recognize this, and therefore attempt to ratio- nalize, i.e. explain, deviations (or, more generally, unexpected moves) by guessing their objective. 2 Note: I am making these terms up as I write these notes. The second has been used in the literature, but neither is \standard." I only hope they are suggestive. Going back to Figure 1, the point is that, if In is interpreted as an intentional move, then Player 1 must be planning to follow it with T: there is no other way to rationalize In, because the alternative possibility (Player 1 plans to follow In with B) is irrational. Hence, Player 2 must expect T in the subgame, and hence play L. But of course this upsets our equilibrium: (OutB, R) is not stable with respect to forward-induction reasoning. On the other hand, the equilibrium (InT,L) is consistent with forward induction (FI henceforth). Thus, we conclude that, if we believe in FI, this should be our prediction. Note what happens in this game: the addition of an outside option for Player 1 makes her stronger, and enables her to \force" her preferred equilibrium in the Battle of the Sexes. There is an even more striking example of this fact. Suppose that, prior to playing the Battle of the Sexes, Player 1 has an option to burn $x, where x2 (1;2). The game is depicted in Figure 2. 1 x 2L R 1 T B 3 x,1 x,0 x,0 1 x,3 0 @ @ @ @ @@2L R 1 T B 3,1 0,0 0,0 1,3 Figure 2: Burning Money In this game, the equilibrium (0BB,RR) is sequential; the notation means \Player 1 chooses not to burn, and then plays B if x and B if 0; Player 2 plays R if x and R if 0." However, note that xBB and xBR are strictly dominated for 1 (by 0BB or 0TB); hence, if Player 2 observes x, he should expect 1 to continue with T, not B. Hence, Player 2 should choose L, and the (T,L) equilibrium should prevail in the LHS game. But then, if Player 1 anticipates this, she will never follow 0 with B: she gets at most 1 by doing so, whereas in the LHS subgame she can secure a payo of 3 x> 1. 3 And, of course, if Player 2 expects this, he will play his part and choose L. Finally, if Player 1 anticipates this, she will choose 0TT. The conclusion is that Player 1 will not need to burn anything, but the mere possibility of doing so makes her strong and allows her to force the (T,L) equilibrium. I should add that some people nd this conclusion puzzling; I personally don’t, but you may di er. Forward Induction and Iterated Weak Dominance This is a subsection I wish I could avoid writing. But, since you will likely encounter statements like \Iterated Weak Dominance captures forward induction," I guess I really have to su er through it. So, here goes. First of all, the de nition. De nition 1 Fix a nite game G = (N;(Ai;ui)i2N) and a player i2N. An action ai is weakly dominated for Player i i there exists i2 (Ai) such that 8a i2A i; X a0i2Ai ui(a0i;a i) i(ai) ui(ai;a i) and there exists a i2A i such that X a0i2Ai ui(a0i;a i) i(ai) >ui(ai;a i): It turns out that an action is weakly dominated i it is not a best response to any strictly positive probability distribution over opponents’ action pro les. You need not worry about this now, anyway. De nition 2 Fix a nite game G = (N;(Ai;ui)i2N). For every player i 2 N, let WD0i = Ai; next, for k 1, and for every i2N, say that ai 2 WDki i ai is not weakly dominated in the game Gk 1 = (N;(WDk 1i ;uk 1i )i2N) (where uk 1i denotes the appropriate restriction of ui). That is: at each round, we eliminate all weakly dominated actions for all players; then we look at the residual game, and continue until no further eliminations are possible.1 Having disposed of the formalities, let us write down the normal form of the burn- ing money game; actually, let’s write the reduced normal form, deleting redundant 1The emphasis on eliminating all weakly dominated actions is warranted: the order and extent of elimination does matter. This is but one of troubling aspects of iterated weak dominance. 4 strategies: it should be obvious to you that this makes no di erence whatsoever in terms of outcomes. In practice, I collapse strategies such as 0BB and 0TB into a single reduced-form strategy 0B. LL LR RL RR xT 3 x;1 3 x,1 x,0 x,0 xB x,0 x,0 1 x,3 1 x,3 0T 3,1 0,0 3,1 0,0 0B 0,0 1,3 0,0 1,3 Figure 3: Burning Money in Normal Form Iterated Weak Dominance eliminates xB, then RL and RR, then 0B, then LR and nally xT. Thus, it seems like IWD tracks the forward induction argument closely. However, let us ask why this is the case. Look at RL and LL; oncexB is eliminated, RL and RR are weakly dominated by LL and LR respectively. In particular, RL is weakly dominated by LL because it yields the same payo as the latter strategy if 1 chooses 0T or 0B, but a worse payo if 1 chooses xT; note that xB has been ruled out. In other words, weak dominance captures sequential rationality: under the as- sumption that 1 follows x with T, R is not sequentially rational after x. Very loosely speaking, we can expect IWD to \capture FI" whenever weak domi- nance and sequential rationality coincide (perhaps given certain restrictions on beliefs, as is the case here.) But this is certainly not a general fact: think about any normal- form game, and a strategy in that game that is weakly but not strictly dominated. You will also hear sometimes that \IWD captures backward induction." This is even more confusing! The exact relationship between IWD, BI and a version of FI (see below) is stated in Battigalli’s 1997 paper on extensive-form rationalizability. As far as I am concerned, this is what you need to know: IWD is a normal-form idea. It happens to induce the \right" (BI or FI) outcome sometimes, but essentially for technical reasons only. If you like weak dominance, that’s ne, as long as your preference is motivated by entirely normal-form considerations. In my opinion, there is no compelling and general extensive-form reason to like weak dominance, and hence IWD. Extensive-Form Rationalizability [I did not cover this material in class, but I thought you might like to look at it anyway. In particular, please look at the discussion of weak and full sequential rationality.] A (much) better way to capture forward-induction reasoning is provided by extensive- form rationalizability (EFR henceforth; cf. Pearce (1984); Battigalli (1996, 1997).) 5 It is easier to de ne EFR if we model beliefs by using conditional probability systems, or CPSs for short. You will remember I de ned these objects in our last double class on epistemic foundations. The main justi cation for adopting CPSs as our basic representation of beliefs is that, after all, belief systems and behavioral strategies represent conditional beliefs about pure strategies chosen by opponents. Thus, we may as well represent these conditional beliefs directly. Recall that Ii denotes the set of information sets of Player i, and that, for every I2Ii, S(I), Si(I) and S i(I) denote, respectively, the set of strategy pro les which reach I, the set of strategies of Player i which allow I to be reached, and the set of strategy pro les of i’s opponents which allow I to be reached. De nition 3 A conditional probability system on (S i;Ii) is a map : 2S i fS i(I) : I2Iig![0;1] such that: (i) For all I2Ii, ( jS i(I))2 (S i); (ii) For all I2Ii, (S i(I)jS i(I)) = 1; (iii) A S i(I) S i(I0) implies (AjS i(I0)) = (AjS i(I)) (S i(I)jS i(I0)). Let us now de ne extensive-form rationalizability, or EFR. First of all, CPSs allow us to de ne (weak) sequential rationality in a very simple way. De nition 4 A strategy si 2 Si is weakly sequentially rational (WSR) given the CPS on (S i;Ii), written si2ri( ), if, for all I2Ii such that si2Si(I), and for all s0i2Si(I), X s i2S i [ui(si;s i) ui(s0i;s i)] (s ijS i(I)) 0 I have discussed \weak" sequential rationality during the course. The basic idea is that the usual notion of sequential rationality requires that a strategy be condi- tionally optimal even at information sets that it precludes from being reached. As I have argued a few times during the course, this requirement is not sustainable from a decision-theoretic viewpoint. The only reason it is imposed is that, in equilibrium, a player’s actions at information sets that she herself prevents from being reached still serve as her opponents’ beliefs. And, even granting this, we must invoke back- ward induction (or something like it) to force these beliefs to be consistent with rationality|and hence restrict our attention to fully sequentially rational strategies. Extensive-form rationalizability takes a much more decision-theoretic view, and therefore needs no more than weak sequential rationality. That is, it uses a notion of rationality applied to plans of action, not strategies (if you remember the di erence). [In any case, using full sequential rationality in our de nition of EFR would not make any di erence in terms of outcomes.] 6 Here is the main de nition. De nition 5 Let S0i = Si for all i2N. Next, for every i2N and si2Si, say that si2Sni i si2Sn 1 i and there exists a CPS on (S i;Ii) such that si2ri( ) and, for all I2Ii, Sn 1 i \S i(I)6=;) (Sn 1 i jS i(I)) = 1: (I am implicitly using our conventions for product sets). The key condition is the restriction on the CPS justifying a strategy at step n. It basically says that, whenever possible, beliefs should be concentrated on the previously de ned set of level-(n 1) EFR strategies. This business of \whenever possible" can be understood by reference to the game in Figure 2, Burning Money.2 You should convince yourselves that the sequence of elimination I have used in the analysis is the one prescribed by EFR. Then, after step 5, no strategy of Player 1 reaches the LHS subgame. But there is no reason to stop at Step 6: as in the de nition of normal-form rationalizability, what should happen is that S6 = S5. But then, what should Player 2 believe in the LHS subgame? This is the reason for 2.(b): S51 \S1(LHS subgame) =;, so no restrictions apply. Then is Player 2 free to choose any best reply to any belief? Well, not quite, because candidate strategies at step 6 must have survived step 5, by condition 1. In turn, this implies that they must be best replies to CPSs that assign probability one to S41 (not S51) whenever possible; and this is possible in the LHS subgame. In fact, here’s an alternative de nition of EFR (that is, this de nition and the one above identify the same sets of strategies.) Let S0i = Si for all i2N. Next, say that si2Sni i there exists a CPS such that: 1. si2ri( ) 2. For all I2Ii and m = 0;:::;n 1: Sm i\S i(I)6=;) (Sm ijS i(I)) = 1. Thus, at any point in the game, players attribute the highest degree of strategic sophistication to their opponents, where \strategic sophistication" is interpreted as \levels of EFR." I conclude by noting that, in generic perfect information games, EFR yields the BI outcome. And, last but not least, there exists an epistemic characterization of EFR which is just as satisfactory (in the sense we have discussed in class) as the 2To be really precise, the representation of the game Burning Money suggests a game with observable actions but possibly simultaneous moves. To apply the de nitions in the text, represent the battle-of-the-sexes subgames assuming that Player 1 moves rst, and Player 2 moves next, without observing 1’s choice (other than x or 0, of course!) 7 characterization of normal-form rationalizability. Check out my Web page if you are interested. 8