Eco514|Game Theory Lecture 15: Sequential Equilibrium Marciano Siniscalchi November 11, 1999 Introduction The theory of extensive games is built upon a key notion, that of sequential rationality, and a key insight, the centrality of o -equilibrium beliefs. The de nition of sequential equilibrium brings both to the fore in a straightforward manner, and emphasizes their interrelation. From subgame perfection to sequential rationality . Let us begin by considering a game with observed actions (but possibly simultaneous moves). Fix a pro le s2S; according to the de nition, s is a subgame-perfect equilibrium of i , for every history h2HnZ, the continuation strategy pro le sjh is a Nash equilibrium of the subgame (h) beginning at h. Equivalently, we can say that s is a SPE i , for every history h2HnZ, and every player i 2 N, there is no strategy s0i 2 Si that yields a higher payo to Player i than si in the subgame (h). Moreover, we can actually restrict this requirement to subgames starting at histories h 2 P 1(i). Consider a history h0 such that i 62 P(h0); then either Player i never moves in the subgame (h0) (in which case si is trivially optimal), or there exists a collection of historiesfh00gsuch that (i) h0 is a subhistory of every h00, and (ii) i2P(h00) for each such h00. According to the pro le s i, exactly one of these histories, say h, will be reached starting from h0, and by assumption sijh is a best reply to s ijh in (h). Therefore, sijh0 is also a best reply to s ijh0 in (h0). In other words, s is a SPE i each component strategy si is a best reply against s i conditional upon reaching any history where Player i moves|including those histories that are not generated by s, or perhaps explicitly excluded by si itself. This is precisely the notion of sequential rationality. 1 There is little reason why this concept should not apply to general extensive games as well. However, observe that, in games with observed actions, xing a strategy pro le s is su cient to generate well-de ned beliefs in every subgame|i.e. well-de ned beliefs conditional upon reaching any history. This is not the case in general extensive games (or in Bayesian extensive games with observed actions, for that matter). In some (very special) games, this does not really matter. For instance, consider Fig. 1. L2,2 1q M R @ @ @ @@q r A A A AA 0,0 l 3,1 q 1,1 A A A AA 0,2 2 I2 Figure 1: A special game (OR 219.1) Observe that (L;r) is a Nash equilibrium of this game; note also that, since Player 1 chooses L in this equilibrium, it is not clear what Player 2 should believe if the information set I2 = f(M);(R)g is reached! Thus, the equilibrium strategy pro le is insu cient to pin down players’ conditional beliefs. Yet, in this particular game, this is essentially irrelevant: regardless of his beliefs about Player 1’s actual choice, r is conditionally strictly dominated at I2. Whatever Player 2’s beliefs, r cannot thus be sequentially rational, so (L;r) is \not a legitimate solution" to the extensive game in Figure 1. On the other hand, (M;l) is. In this simple game, Player 2’s beliefs about the strategy (action) actually chosen by Player 1 is irrelevant as far as his choices are concerned. However, this is seldom the case: consider Fig. 2, which di ers from Fig. 1 only in that the payo s at the terminal history fM;rg have been modi ed. Consider (L;r) again. Upon being reached, Player 2 must conclude that Player 1 did not choose L; hence, he must adopt new, distinct from the equilibrium pro le. Suppose that he thinks that Player 1 actually chose M: then r is indeed a sequential best reply! Suppose instead that he thinks that Player 1 chose R: in this case r is not sequentially rational. 2 L2,2 1q M R @ @ @ @@q r A A A AA 0,2 l 3,1 q 1,1 A A A AA 0,2 2 I2 Figure 2: A typical case (OR 220.1) Formal de nitions The simple games in the previous section emphasize that o -equilibrium beliefs matter: they determine whether or not a given pro le is an equilibrium. Moreover, the putative equilibrium pro le does not yield a complete speci cation of beliefs. In particular, at any information set, a (behavioral) strategy pro le yields a complete speci cation of continuation strategies, but may fail to provide information about past play| precisely because, at information sets o the path of play generated by , it must necessarily be the case that at least one player j made choices other than those prescribed by j! The original pro le is clearly silent about such alternative choices. Note that this problem does not arise in games with observed actions, precisely because past play is observable (so there is no uncertainty about previous moves). However, it does arise in Bayesian games with observed actions; see the next section for details. Kreps and Wilson propose the following de nition. De nition 1 Fix a general extensive game . A belief system is a map : Si2NIi ! (HnZ) such that, for every i2N and Ii2Ii, (Ii)(Ii) = 1. It is most helpful to view a belief system as a summary representation of past play leading to information sets. That is, informally speaking, one could imagine that, if the play reaches an information set Ii (where Player i has to move) which is not consistent with the originally expected behavioral strategy pro le , players conclude that a di erent pro le 0 is actually being played, and base their inferences and forecasts on the latter. However, based on simple consistency considerations, 0 and should agree at least as far as moves at information sets following I are concerned. But, if this is the case, then all that is required in addition to in order to verify the sequential rationality of i at Ii is the distribution over histories in Ii induced by 0|which is precisely the type of information encoded in (I). 3 From now on, the basic unit of our analysis will be a pair ( ; ) consisting of a behavioral strategy pro le and a belief system; such a pair is called an assessment. Focus on games with perfect recall. In keeping with conventional usage, we de ne se- quentially rational assessments. First, de ne the conditional outcome function O( ; jI) to be the distribution over Z induced by the assessment ( ; ) conditional upon starting the game at I: formally, for every z2Z, if no h2I is a subhistory of z, then O( ; jI)(z) = 0; otherwise, by perfect recall, there can be only one such subhistory h (if there were two, then one would have to be a subhistory of the other, and an information set cannot contain a pair of nested histories). Thus, z = (h;a1;:::;aK), and we let O( ; jI)(z) = (I)(h) K 1Y ‘=1 P(h;a1;:::;a‘)(h;a1;:::;a‘)(a‘+1) (recall that, with some abuse of notation, for h2Ii2Ii, i(h) = i(Ii)). De nition 2 Fix a general extensive game . An assessment ( ; ) for is sequentially rational i , for every player i 2 N, every information set Ii 2Ii, and every behavioral strategy 0i2Bi, X z2Z Ui(z)O( ; jIi) X z2Z Ui(z)O(( 0i; i) jIi) It should be obvious that some relationship between belief systems and behavioral strate- gies in an assessment ( ; ) should be maintained. In particular, at least at information sets consistent with , should be derived from by means of Bayes’ rule. But we may reasonably require more than this. For instance, consider a modi cation of the game in Figure 2 in which Player 1 chooses between L and C, and if 1 chooses C, a third player 10 chooses between M and R; then Player 2 has to choose observing only Player 1’s initial move. That is, Player 1’s choice among L, M and R is split between two players, 1 and 10, choosing consecutively. Consider a behavioral strategy pro le in which Player 1 chooses L and Player 10 chooses M. Then, even after a deviation by Player 1, we would probably still want to require that (f(C;M);(C;R)g)((C;M)) = 1; that is, a deviation by Player 1 should not a ect Player 2’s beliefs about the choices of Player 10. However, strictly speaking, Bayes’ rule does not apply to this information set, because it lies o the path induced by the behavioral strategy pro le under consideration. [Note incidentally that if 1 and 10 were the same player, this argument would be less convincing; one would have to invoke some kind of trembles or mistakes, whereas the argu- ment in the case where 1 and 10 are distinct is essentially based on independence. As will be clear, however, the standard de nition of sequential equilibrium does not discriminate between these two cases.] 4 Kreps and Wilson suggest the following de nition. De nition 3 Fix a nite general extensive game . An assessment ( ; ) is consistent i there exists a sequence of assessments ( n; n) converging to ( ; ) and such that (i) ni (Ii)(a) > 0 for every i2N, I2Ii and a2A(I); and (ii) n is derived from n via Bayes’ rule. It is easy to see that this de nition captures the intended restrictions. Note that (ii) makes sense because, since every action in the game receives positive probability, every information set is also reached with positive probability, so Bayes’ rule always applies. Myerson suggests the following argument. Almost all elements of the setB of behavioral strategy pro les satisfy Condition (i) in De nition 3: that is, Condition (i) is generically satis ed. Also, Condition (ii) is very reasonable, so we de nitely want all assessments ( ; ) such that satis es (i) to be deemed consistent if and only if is derived from by Bayes’ rule. Finally, it seems reasonable (and convenient) to assume that the set of consistent assessments is closed; hence, it makes sense to de ne it to be precisely the closure of the set of assessments satisfying (i) and (ii). This may not appear to be a tremendously compelling argument; however, let me add that, for certain classes of games, consistency is equivalent to much simpler conditions on beliefs (when the latter are represented in an appropriate format). Also, consistency can be characterized for general games in a manner that does not involve limits (although the characterization is not tremendously appealing). We are nally ready to de ne sequential equilibrium. De nition 4 Fix a nite general extensive game . An assessment ( ; ) is a sequential equilibrium of i it is consistent and sequentially rational. Perfect Bayesian equilibrium Some people nd the de nition of sequential equilibrium unwieldy (this refers in particular to the consistency requirement). Also, consistency is only de ned for nite games, so sequential equilibrium does not really apply to relatively simple games such as Bayesian extensive games with observed actions where type sets are in nite. In such games, just like in a Bayesian game with simultaneous moves, one must specify a strategy for each payo -type of each player. That is, we must specify type-contingent strategies. Hence, upon reaching a history h, players may be able to make inferences about their opponents’ types based on the (equilibrium) strategy pro le. However, at histories o the anticipated path of play, it is clear that the strategy pro le does not convey any information about opponents’ types. 5 This is of course exactly the type of problem that beliefs system solve in general games. Here, however, the situation is much simpler, because the domain of uncertainty (the sets of payo types) are xed throughout the game. In Perfect Bayesian equilibria (see OR for details), the information conveyed by strat- egy pro les is complemented by measures i(h) 2 ( i) associated with each nonterminal history. In interpreting the de nitions, it is important to remember that, just like the probabilities pi, i(h) represents the beliefs of players other than i about Player i’s type. These beliefs are common to all players, which is reasonable: after all, the priors pi are common, and all players observe exactly the same occurrences as the play progresses. The key condition in the de nition of a PBE is the requirement that these beliefs be action-determined. That is: if Player i does not move at a history h, then the beliefs about her should not change at h; and if Player i does move, than beliefs about her should only be a ected by her own action at h (not by somebody else’s action). Just like the consistency requirement in SE, this complements Bayesian updating with restrictions on beliefs following unexpected actions (i.e. on beliefs at o -equilibrium histo- ries). 6