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- sets that should not be reached if a given equilibrium is plane( play)at information equilibrium beliefs-that is, on beliefs(about past and future pla 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 fight 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 fight; but if we think that fighting 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 nuch of the literature in this field, it's best to begin with a couple of ke examples Consider the profile(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
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-ofequilibrium 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 determine equilibrium behavior. For instance, consider the simple two-stage entry deterrence game in which a potential entrant decides whether to enter a market or stay out, and the incumbent decides whether to fight 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 fight; but if we think that fighting is not a credible threat, this equilibrium collapses. But things can become much more subtle—and interesting. In particular, sequential 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 field, it’s best to begin with a couple of key examples. Consider the profile (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
T3,10,0 B0.01,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 sufficiently 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 profile says he should play R? Well, that's a good question. However, note that the same equilibrium profile 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 behavior The first route is the story implicit in sequential equilibrium, THPE, and backward induction in general. According to this story, (OutB, R)is a fine 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
1 Out 2,2 In ❅ ❅ ❅ ❅ ❅❅ 2 L 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 sufficiently 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 profile says he should play R? Well, that’s a good question. However, note that the same equilibrium profile 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 first route is the story implicit in sequential equilibrium, THPE, and backward induction in general. According to this story, (OutB, R) is a fine 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 rationalize, i.e. explain, deviations (or, more generally, unexpected moves) by guessing their objective. 2
Ised in the literature, but neither is"standard. " I only hope they are suggestive een Note: I am making these terms up as I write these notes. The second has b Us Going back to Figure 1, the point is that, if In is interpreted as an intentional move, then Player I 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 edict 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 Se There is an even more striking example of this fact. Suppose that, prior to playin the Battle of the Sexes, Player 1 has an option to burn S T, where I E(1, 2). The game is depicted in Figure 2 0 B0,01,3 Figure 2: Burning Money In this game, the equilibrium(OBB, RR) is sequential; the notation means"Player 1 chooses not to burn, and then plays B if a and B if 0; Player 2 plays R if r and R However, note that z BB and BR are strictly dominated for 1 (by OBB or OTB hence, if Player 2 observes he should expect l 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 payoff of 3-x>1
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 x ∈ (1, 2). The game is depicted in Figure 2. 1 x 2 L R 1 T B 3 − x,1 −x,0 −x,0 1 − x,3 0 ❅ ❅ ❅ ❅ ❅❅ 2 L 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 payoff 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 OTT 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 find this conclusion puzzling; i personally dont but you may differ 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 suffer through it So, here goes. First of all, the definition Definition 1 Fix a finite game G=(N, (Ai, uiieN) and a player i E N. An action i is weakly dominated for Player i iff there exists a; E A(Ai) such that 2 ui(al,a-i)ai(ai)2ui(ai, a-i and there exists a-i E A-i such that ui(an, a-iai(ai>ui(ai, a-i) ∈A It turns out that an action is weakly dominated iff it is not a best response to any strictly positive probability distribution over opponents' action profiles. You need not worry about this now, anyway Definition 2 Fix a finite game G=(N, (Ai, ui)ieN. For every player i E N, let WD=A;next,fork≥1, and for every i∈N, say that a∈ Wd iff a; is not weakly dominated in the game G-l=(N, (WDi-, ui- ieN)(where ui-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 I Having disposed of the formalities, let us write down the normal form of the burn- ng money game; actually, let's write the reduced normal form, deleting redundant I The 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 dom
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 find this conclusion puzzling; I personally don’t, but you may differ. 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 suffer through it. So, here goes. First of all, the definition. Definition 1 Fix a finite game G = (N,(Ai , ui)i∈N ) and a player i ∈ N. An action ai is weakly dominated for Player i iff there exists αi ∈ ∆(Ai) such that ∀a−i ∈ A−i , X a 0 i∈Ai ui(a 0 i , a−i)αi(ai) ≥ ui(ai , a−i) and there exists a−i ∈ A−i such that X a 0 i∈Ai ui(a 0 i , a−i)αi(ai) > ui(ai , a−i). It turns out that an action is weakly dominated iff it is not a best response to any strictly positive probability distribution over opponents’ action profiles. You need not worry about this now, anyway. Definition 2 Fix a finite game G = (N,(Ai , ui)i∈N ). For every player i ∈ N, let WD0 i = Ai ; next, for k ≥ 1, and for every i ∈ N, say that ai ∈ WDk i iff ai is not weakly dominated in the game Gk−1 = (N,(WDk−1 i , uk−1 i )i∈N ) (where u k−1 i 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 burning 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 difference whatsoever in terms of outcomes. In practice, I collapse strategies such as OBB and OTB into a single reduced-form strategy 0B LL LR RL RR rT3-x,13-x,1-x,0 B|-x0 r,01-x,31-x,3 0T3,1 0.0 3,1 0,0 OB0.0 1,3 Figure 3: Burning Money in Normal Form Iterated Weak Dominance eliminates B, then RL and RR, then oB, then LR and finally T. 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; once B 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 payoff as the latter strategy if chooses ot or OB, but a worse payoff if 1 chooses aT; note that aB has been ruled In other words, weak dominance captures sequential rationality: under the as- sumption that 1 follows a with T, R is not sequentially rational after a Very loosely speaking, we can expect IWD to"capture Fr'whenever weak domi- nance and sequential rationality coincide(perhaps given certain restrictions on belief 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 fine, 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 ectensive- form rationalizability(EFR henceforth; cf. Pearce(1984); Battigalli (1996, 1997).)
strategies: it should be obvious to you that this makes no difference 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 finally 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; once xB 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 payoff as the latter strategy if 1 chooses 0T or 0B, but a worse payoff if 1 chooses xT; note that xB has been ruled out. In other words, weak dominance captures sequential rationality: under the assumption 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 dominance 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 normalform 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 fine, 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 extensiveform rationalizability (EFR henceforth; cf. Pearce (1984); Battigalli (1996, 1997).) 5