Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 1Nonequilibrium Solution Concepts: IteratedÙDominance and RationalizabilityIntroduction______________________________________________________________________1Recapitulation____________________________________________________________________2Iterated strict dominance____________________________________________________________3Common knowledge of rationality____________________________________________________4Iterated strict dominance: formal definition____________________________________________7Iterated strict dominance: looking more closely_________________________________________10Rationalizability__________________________________________________________________12Rationalizability as a consistent system of beliefs________________________________________14Comparing notes________________________________________________________________15When beliefs are held in common___________________________________________________16IntroductionWe began our preparation for the study of nonequilibrium solution concepts by introducing the notion ofstrategic dominance. We defined what it means for a strategy of one player to be dominated by anotherof her strategies. Because a rational player would never play a dominated strategy, we can sometimesuse a dominance analysis to rule out some outcomes as possibilities when the game is played by rationalplayers. In some games, . the prisoners’ dilemma, a dominance analysis leads to a unique predictionof the outcome when players are rational; we say that these games are dominance solvable. In othergames, . matching pennies, a dominance analysis results in no refinement of the set of possibleoutcomes. Other games lie between these two extremes: dominance analysis rejects some outcomes asimpossible when the game is played by rational players but still leaves a multiplicity of related to the concept of a strategy being dominated for a player is the idea that this strategyis “never a best response” for that player: No matter what beliefs she has about the actions of heropponents, she could not rationally choose to play that strategy. If a strategy is dominated, it can neverbe a best response. However, it is not obvious that the implication holds in the reverse direction. . it’snot obvious that a strategy which is never a best response is also a dominated strategy. Therefore the setof strategies which are never best responses is weakly larger than the set of dominated strategies. Ananalysis based on whether strategies are possibly best responses does exhaust the implications of allplayers being rational: A strategy cannot be plausibly chosen by a rational player if and only if it isnever a best response. ÙÛ' 1996 by Jim Ratliff , <jim@>, <
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 2We have seen that in two-player games a strategy is never a best response if and only if it isdominated. For two-player games, then, a dominance analysis fully exploits the assumption that allplayers are rational. However, for games with three or more players, it is possible that an undominatedstrategy will yet never be a best response. Therefore we can sometimes rule out as a plausible choice astrategy even when it is undominated. For more-than-two-player games, then, a dominance argumentneed not fully exploit the assumption that all players are can often make sharper predictions about the possible outcomes of a game if we are willing tomake stronger assumptions. Up until now we have assumed that the players are rational but we haven’teven assumed that each knows that the others are rational. Beyond that we could further assume thateach player knows that the other players know that the others are all rational. We could continue addingadditional layers of such assumptions ad nauseam. Fortunately we can summarize the entire infinitehierarchy of such assumptions by simply saying that the rationality of the players is common constrains players to choose best responses to their beliefs but does not restrict those knowledge of rationality imposes a consistency requirement upon players’ beliefs aboutothers’ assuming that the players’ rationality is common knowledge, we can justify an iterative process ofoutcome rejection—the iterated elimination of strictly dominated strategies—which can often sharpenour predictions. Outcomes which do not survive this process of elimination cannot plausibly be playedwhen the rationality of the players is common knowledge. A similar, and weakly stronger, process—theiterated elimination of strategies which are never best responses—leads to the solution concept of1rationalizability. The surviving outcomes of this process constitute the set of rationalizable such outcome is a plausible result—and these are the only plausible results—when the players’rationality is common knowledge. In two-player games the set of rationalizable outcomes is exactly theset of outcomes which survive the iterated elimination of strictly dominated strategies. In three-or-more-player games, the set of rationalizable outcomes can be strictly smaller than the set of outcomes whichsurvives the iterated elimination of strictly dominated strategies. In a rationalizable outcome players’beliefs about the same question can differ—and hence some are incorrect; and a player can find—afterthe others’ choices are revealed—that she would have preferred to have made a different ’s briefly review the standard paradigm and notation. We have a finite set I of n players,#S¥1iI={1,…,n}. The finite pure-strategy space for player i is S; her mixed-strategy space is ÍfiÇ;iitypical elements are s˙S and ß˙Í. When player i chooses the mixed strategy ß, the probability withiiiiiwhich she plays the pure strategy s˙S is ߪsº. When we omit the subscript on a set defined for eachiiiiplayer, we mean the Cartesian product of all the player sets: ., SfiX. A subscript “_i” meansi˙I“I\{i}”. An element s˙S is called a deleted pure-strategy profile. Player i’s von Neumann-¥i¥iMorgenstern utility function is u:ÙS§Â. (We often abuse notation and consider this utility function toi 1“Weakly stronger” seems a little oxymoronic!jim@
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 3take a mixed-strategy profile as its argument instead of a pure-strategy profile. In such a case itrepresents the player’s expected utility when the players randomize independently according to theircomponent mixed strategies in the mixed-strategy profile.)We began our preparation for the study of nonequilibrium solution concepts by introducing the notionof strategic dominance. Let ß,ß’˙Í be two mixed strategies for player i. We say that ß’ strictlyiiiidominates ß if ß’ gives player i a strictly higher expected utility than does ß for every possible deletediii2pure-strategy profile s which her opponents could play, . if¥iÅs˙S,!uªß’,sº>uªß,sº.(1)¥i¥iii¥iii¥iIterated strict dominanceWe saw above that in some games, . the Prisoners’ Dilemma, each player has a dominant strategy andwe could therefore make a very precise prediction about the outcome of the game. To achieve thisconclusion we only needed to assume that each player was rational and knew her own payoffs. We alsosaw an example, viz. matching pennies, where dominance arguments got us nowhere—no player hadany dominated strategies. There are games which lie between these two extremes in the degree to whichand ease with which dominance arguments can refine the set of possible technique we’ll discuss now is called the iterated elimination of strictly dominated strategies. Inorder to employ it we will need to make stronger informational assumptions than we have up until example, we won’t merely assume that each player is rational. We might need to assume as well, ina two-payer game for example, that player 1 knows that player 2 is rational; and player 2 knows thatplayer 1 knows that player 2 is rational, etc. In some games application of the iterated elimination ofstrictly dominated strategies can require that these hierarchies of beliefs about beliefs be quite a two-player game between Row and Column, whose pure-strategy spaces are S and S,RCrespectively. Prior to a dominance analysis of a game, we know only that the outcome will be one of thestrategy profiles from the space of strategy profiles S=S˜S. We reasoned above that a rational playerRCwould never play a dominated strategy. If Row has a dominated strategy, say s, but Column does not,Rthen Row, being rational, would never play this strategy. We could therefore confidently predict that theoutcome of the game must be drawn from the smaller space of strategy profilesS’=(S\{s})˜S.(8)RRCHere is the interesting point and the key to the utility of the iterative process we’re developing:Although Column had no dominated strategy in the original game, he may well have a dominated 2We showed that satisfaction of this condition was equivalent to satisfaction of the same condition but with the substitution of ߧs¥i¥iand ͧS. . without loss of generality, in order to assess questions of dominance for player i, we can restrict attention to deleted¥i¥ipure-strategy profiles by her Fudenberg and Tirole [1991].jim@
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 44strategy s in the new, smaller game S’. If so, and if we make sufficient assumptions, we can rule outCas possible outcomes all which involve such newly dominated strategies from Column’s strategy space;this again results in a smaller space of strategy profiles. And in this smaller game additional rowstrategies may now be revealed to be dominated. In some cases this process can continue until a uniquestrategy for each player survives this elimination process. In this case we say—as we did when eachplayer had a dominant strategy in the original game—that the game is dominance knowledge of rationalityI just said that we had to make assumptions to justify the deletion of Column’s dominated strategy assumptions are necessary for this step? First, Column must be rational. Additionally, in order forColumn to see that s is dominated for him, he must see that Row will never play s. Row will neverCRplay s if she is rational; therefore we must assume that Column knows that Row is rational. With theseRadditional assumptions we can confidently predict that any outcome of the game must be drawn fromS”=(S\{s})˜(S\{s}).(9)RRCCLet’s not get too tedious, but let’s carry this out one more level. It may be the case that in the gamedefined by the strategy-profile space S” there is now a strategy of Row’s which is newly dominated, callit s. However, we can’t rule out that Row will play s unless we can assure that Row knows that theRRpossible outcomes are indeed limited to S”, . that Column will not choose s. Column won’t choose sCCif he is rational and knows that Row is rational. Therefore we must assume that Row knows that Columnis rational and knows that Column knows that Row is any finite game this chain of assumptions can only be usefully carried out to a finite depth. Toensure that we can make such assumptions to an arbitrary depth we often make a convenient5assumption: that it is common knowledge that all players are does it mean for something to be common knowledge? Let P be a proposition, . that“player 1 is rational.” If P is common knowledge, thenEveryone knows P;Everyone knows that (Everyone knows P);Everyone knows that [Everyone knows that (Everyone knows P)];Etc. 4The new game is defined by the strategy spaces S’=S\{s} and S’=S and by the utility functions u’:ÙS’§Â, i˙{R,C}, whereRRRCCieach u’ is the restriction of u:S§Â to the smaller domain S’, viz. Ås˙S’, u’ªsº=uªsº.iiii5When we predicted that Row would not play s we implicitly assumed that Row knew her own payoffs but not that Row knewRColumn’s payoffs. When we predicted that Column would never play s, we implicitly assumed that Column knew that Row knewCRow’s payoffs and that Column knew Row’s payoffs. So if we wanted to be perfectly explicit about our assumptions about the players’knowledge of their payoffs, there’s another whole hierarchy of beliefs to merge into the hierarchy of beliefs concerning rationality. Wecan summarize this hierarchy by assuming that “the players’ payoffs are common knowledge.”6Aumann [1976] gives the definition for two players; Myerson [1991] and Pearce [1984] provide it for many @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 5In other words, if P is common knowledge, then every statement of the formk(Everyone knows that) everyone knows P,(10)is true for all k˙{0,1,2,…}.Prima facie, it might seem unreasonable to expect real-life players to be able to keep track of suchunbounded hierarchies of beliefs about beliefs. Actually, common knowledge can be achieved rathersimply. Suppose you and I are both present when an event E (assumed so salient that it cannot beignored) occurs. Suppose further that then we both immediately make eye contact with one another. It is7then common knowledge (between the two of us) that E : Solving a game by the iterated elimination of strictly dominated the game in Figure 5(a). Note that Column has no strategies which are dominated by purestrategies. Note further that none of Column’s pure strategies can be dominated by a mixture of the othertwo. However, for Row, Up dominates Middle, and Down is undominated. So a rational Row wouldnever play Middle. Therefore ifRow is rational,(11)then we can strike Middle from Row’s strategy space and collapse the bimatrix, resulting in the game inFigure 5(b).Figure 5: Solving a game by the iterated elimination of strictly dominated Column knows that the possible outcomes must belong to the game in Figure 5(b)—which requiresthat he know (11), then he would see that center is dominated by both left and right. (Left and right areboth undominated.) Therefore if in addition to (11) bothColumn is rational,(12) 7For example, let E be the event that two particular people are in the same room at a particular @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 6Column knowsRow is rational,(13)we can strike center, which results in the game of Figure 5(c).If Row sees that the possible outcomes must be drawn from the game in Figure 5(c) , which requiresthat she know (12) and (13), then she would see that Up dominates Down. Therefore if alsoRow knowsColumn is rational,(14)Row knowsColumn knowsRow is rational,(15)we could strike Down, which results in the game of Figure 5(d).If Column knows that Figure 5(d) is the relevant game, which requires that he also knows (14) and(15), then Column would recognize that right dominates left. Hence, if alsoColumn knowsRow knowsColumn is rational,(16)Column knowsRow knowsColumn knowsRow is rational,(17)the only strategies which survive the iterated elimination of strictly dominated strategies are Up for Rowand right for Column. This strategy profile is shown in Figure 5(e). So we see that the necessaryassumptions to solve this game were (13) § (17). (We always assume that the players are is new here are the assumptions about the players’ higher-order beliefs about rationality.) All ofthese assumptions about beliefs are implied by the sufficient assumption that it is common knowledgethat both players are : Iterated strict dominance can require mixed-strategy wanted to make the logical reasoning in the previous example as transparent as possible, so I chose thegame such that elimination required only domination by pure strategies. However, a more generalmixed-strategy analysis can be necessary. Consider the game in Figure 6: A mixture of Up and Middle dominates Down; then left dominates are no pure-strategy dominance relationships in the original game. However, the mixed strategy™œUÙ!Ù™œM dominates Down. After deleting Down, left dominates right for Column. After deletingright, Up dominates Middle. Therefore the only possible outcome under common knowledge ofrationality is (U,l).jim@
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 7Iterated strict dominance: formal definitionIn order to support rigorous proofs of later claims regarding the surviving outcomes of the iteratedelimination of strictly dominated strategies we’ll now define this solution concept more formally. The8process is iterative; we can think of it as an algorithm (which is depicted in flowchart form in Figure 7).Very loosely to begin with…. We start with the original game S. We delete all the dominated1strategies for each player, which results in a smaller game S. More generally, we consider the gamet¥1defined by some set of not-yet-rejected outcomes S. By rejecting any player’s strategy which istt9dominated, we reach the weakly smaller game S. (Therefore S is the set of player i’s pure strategiesit¥1which are undominated in the game S.) When we reach a point where the resulting game cannot befurther shrunk by the elimination of strictly dominated strategies, then our process has concluded. We∞say that this set of outcomes, denoted S, has survived the iterated elimination of strictly formally now…. We use t˙zfi{0,1,2,…} as a counter. We denote by SÓS the set ofÁiiplayer-i pure strategies which are unrejected after t rounds of this iterative procedure. Therefore the0tperiod-0 game is just the original game: Åi˙I, S=S. We denote by ÍÓÍ the set of player-i mixediiiistrategies which are mixtures only over the pure strategies which are unrejected after t rounds; ,11Í={ß˙Í:ÙsuppÙßÓS}. In particular, Í=Í.iiiiiiit¥1t¥1Now consider the game resulting after t_1 rounds of elimination, viz. S=XÙS. Consider somei˙Iit¥1player i˙I and consider each of her not-yet-rejected pure strategies s˙S. The strategy s is dominatediiit¥1t¥1in the game S if there exists a mixed strategy ß over these not-yet-rejected pure strategies S, ¥1t¥1t¥1ß˙Í, such that ß dominates s in the game S (. for all deleted strategy profiles s˙S by heriii¥ii¥itt¥1opponents). Therefore the set S of strategies which are undominated in S isitt¥1t¥1t¥1S={s˙S:Ù‰÷ß˙Í,Ås˙S,uªß,sº>uªs,sº}.(18)ii¥iii¥iii¥iiii¥i 8Just a note of explanation about the “i˙I loop” § “end i loop” constructions in the flowchart for those who haven’t programmedcomputers: When an “i˙I loop” box is initially encountered from above, i is set to the first element of I and control passes the “end i loop” box is encountered, one of two things can happen. 1 If there are still elements i˙I which haven’t been processedin this loop, control returns to the preceding “i˙I loop” and the i counter is incremented to the next element of I. 2 If this was the lastelement i in the set I, then control drops out of the loop to the next lower previous round of eliminations may have revealed newly dominated strategies for one or more that we are not at this point requiring that the mixed strategies in Í be that Í is not a mixed strategy for player i in her smaller strategy space S. Rather it is a mixed strategy over her original strategyiitspace S but whose support includes only pure strategies in the smaller strategy space @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 8Figure 7: A flowchart definition of the iterated elimination of strictly dominated @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 9We then form the set of mixed strategiesttÍ={ß˙Í:ÙsuppÙßÓS}(19)iiiiitwhich put weight only upon the still-admissible pure strategies of S; these constitute our arsenal withitwhich to try to dominate strategies in the new game S. We note that the sequence of player-i strategytspaces {S} is nested:t˙zi+tÁ1tÅt˙z, SÓS.(20)ÁiiWe must eventually get to a stage in the iterations such that the surviving strategy set for each player†¥1†is unchanged from the previous round, . ‰†˙nfi{1,2,…}, Åi˙I, S=S. (Otherwise at least oneiipure strategy from at least one player must be eliminated in each round. The number of pure strategiesfor each player is finite. Therefore it’s impossible to remove strategies forever.) If we were to continuethe algorithm beyond this stage, we’d find that the strategy sets remained unchanged, . for all i˙I,†Á1†Á2††S=S=S=Ú. [This is clear from examination of (18). Consider any i˙I and s˙S. This s wasiiiiii†¥1†††¥1undominated in S (which is why it survived to belong to S). But S=S, so s must be undominatedii††Á1†Ákin S as well, and therefore deserves membership in S. And so on for S, k˙n.]Once we reach a stage in this iterative process at which the strategy sets are no longer shrinking, sayat period † as in the above paragraph, we have exhausted the implications of an iterative dominanceanalysis for behavior in the game. We set, for each i˙I,∞†S=S,(21)ii∞where S is the set of player-i pure strategies which survive the iterated elimination of strictlyi12dominated strategies. When the game is played under the conditions of common knowledge of∞rationality, every player i would choose some strategy s˙S. The Cartesian product of these player-ii∞∞strategy sets, viz. S=XÙS is the set of strategy profiles which survive the iterated elimination ofi˙Iistrictly dominated strategies. When the game is played under the conditions of common knowledge of∞∞rationality, any pure-strategy profile must be within the set S, . s˙S.∞To determine the set of mixed strategies Í for player i which are compatible with an iteratedidominance analysis based on the common knowledge of rationality, we first find all the mixed strategies∞∞Í which put positive weight only upon the unrejected pure strategies S,ii∞∞Í={ß˙Í:ÙsuppÙßÓS},(22)iiiiiHowever, we have seen before that a mixed strategy which spreads all its weight only among13undominated pure strategies can still be itself dominated. Therefore we must filter this set of mixed 12∞∞tWe could alternatively write that S is the intersection of the infinite sequence of player-i strategy spaces, viz. S=ËÙ˙ziÁ13See the example on pages 10–13 in the “Dominance” handout of September 7, @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 10strategies to remove any which are dominated by other mixed strategies in that set. This results in the set∞Í of mixed strategies for player i which are not rejected by an iterated dominance argument,i∞∞∞∞Í={ß˙Í:Ù‰÷ß’˙Í,Ås˙S,uªß’,sº>uªß,sº}.(23)iiiii¥iii¥iii¥i¥iExample: A dominance-solvable two-player gameLet’s perform iterated elimination of strictly dominant strategies on the game in Figure 8. U dominatesM. With M removed, l dominates r. With r removed, D dominates U. Therefore the iterated-dominanceoutcome is (D,l).Figure 8: A dominance-solvable two-player terms of our formalism, the nested pure-strategy sets for each player at each stage of the iterativeprocess are00S={U,M,D},S={l,r},RC11S={U,D},S={l,r}RC22S={U,D},S={l},RC33S={D},S={l},RC∞∞S={D},S={l}.RCThe sets of mixed strategies which survive the iterated elimination of strictly dominated strategies,∞∞viz. Í and Í, are trivial in this example. Each player has only one surviving pure strategy andRCtherefore the only mixture over that strategy is the corresponding degenerate mixed strategy, viz.∞∞Í={(0œUÄ0œMÄ1œD)},Í={(1œlÄ0œr)}.RCIterated strict dominance: looking more closelyLet’s revisit the formal specification of the iterated elimination of strictly dominated strategies to huntfor and hopefully resolve possibly problematic issues. Consider again the example from Figure 8. Whydid we reject r for Column? Because we had previously rejected M for Row on account of beingdominated by U. But we later rejected U itself for Row. Since we used U to reject M, but later decidedthat Row would never actually play U, perhaps we should call into question our rejection of M andtherefore of r for Column. How can we think about issue more clearly?jim@
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 11Perhaps one justification for reconsidering our rejection of M would be: if, starting with our final∞∞game S˜S={D}˜{l}, we reintroduced M into Row’s strategy set and found that M was no longerRCdominated, then we might conclude that our rejection of M was mistaken—that we were mislead by thelater-to-be-rejected-itself strategy U. However, if we perform that experiment we have the game ofFigure 9, and we see that M is still dominated, albeit by D now rather than 9: The dominance-solved game of Figure 8 with M restored to Row’s strategy we see that, in this example at least, a strategy which was rejected as dominated in an early stageof the iterative process was still dominated when reinjected into its player’s strategy space at the end ofthe iterative process, even though the originally dominating strategy which justified its rejection hadbeen later itself rejected as dominated. We will now see that this is a general result: any strategy whichis dominated at some stage of the iterative process would still be dominated at any later stage ifreintroduced into its player’s strategy space.∞Let’s first establish a relevant fact. For some player i˙I consider the game S˜S. We’ll now seei¥i∞∞that S is the set of player i’s pure strategies which are undominated in the game S˜S. To prove thisi¥ii∞∞equality we need to show that 1 S contains all the strategies which are undominated in S˜S and 2i¥ii∞∞any strategy which is dominated in S˜S does not belong to ¥ii∞The set S contains all of player i’s strategies which are never rejected during the iterative eliminationi∞∞process. Therefore to show that S contains all the undominated strategies in S˜S we need to showi¥iithat all of the strategies which are rejected during the iterative elimination process are in fact dominated∞∞in S˜S. So we consider a rejected strategy s˙S\S and let t˙z be the stage of the process ini¥iiiÁiwhich it is rejected. ‰ß˙Í, Ås˙S, uªß,sº>uªs,sº.(24)i¥i¥iii¥iii¥ii∞If s is dominated in S˜S, thenii¥i∞‰ß’˙Í, Ås˙S, uªß’,sº>uªs,sº.(25)ii¥i¥iii¥iii¥iWe need to show that satisfaction of (24) implies satisfaction of (25). But we note from (19) and (20)t∞tthat ÍÓÍ and SÓS. Therefore in attempting to satisfy (25), compared to satisfying (24), we cani¥i¥iichoose a mixed strategy from a larger set Í and dominance need hold only in fewer cases (viz. for alli∞ts˙S rather than for all s˙S). Therefore if (24) is satisfied, we can set ß’¶ß in order to satisfy¥i¥i¥i¥iii(25). This shows we show 2, I need to state (and you can establish!) a useful result:jim@
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 12Let S’ÓS be the set of player i’s undominated pure strategies. Let S be theiiiTheoremset of player i’s dominated pure strategies. Let ß˙Í be a mixed strategyiiwhich puts positive weight on at least one dominated pure strategy; . suppÙßËS≠õ.iiThen there exists a mixed strategy ß’˙Í such that 1 ß’ dominates ß and 2 ß’ puts no weight oniiiiidominated pure strategies; . suppÙß’ÓS’.iiProofIt’s up to you. This is extra-credit challenge #1.∞∞Now we want to show 2, . that any strategy which is dominated in S˜S does not belong to ¥ii∞Therefore we need to show that any strategy which is dominated in S˜S is rejected at some stagei¥i∞†t˙z in the iterative elimination process. Let †˙z be the “final” period of the process (. S=S).ÁÁiiI’ll show that if s survives until the last stage, viz. until stage †, then it will be rejected there. So assumei†s˙S. In order to be rejected in period † we must haveii††‰ß˙Í, Ås˙S, uªß,sº>uªs,sº.(26)ii¥i¥iii¥iii¥i∞Because s is dominated in S˜S; . there exists a ß’˙Í such that (25) holds. If it’s already the caseii¥iii†that ß’˙Í, then we’re done. [Just take ߶ߒ and note (21) to see that (26) is satisfied.] So consideriiii†the remaining case where ß’âÍ. Therefore ß’ must put positive weight on some pure strategy whichiii∞∞is dominated in S˜S (because S contains all the undominated strategies in this game and thereforei¥ii∞†Í=Í contains all the mixtures over the undominated strategies). Therefore we can use the aboveii†theorem to assert the existence of another mixed strategy ß˙Í which dominates ß’ and thereforeiiisatisfies (26).So we have shown that, for each player i˙I, the set of her pure strategies which survive the iterated∞elimination of strictly dominated strategies, viz. S, is exactly the set of pure strategies which arei∞undominated when her opponents can only choose deleted strategy profiles in S. Now that this is¥iestablished you can construct an argument to show that, if any combination of rejected strategies∞s˙S\S is reinjected into player i’s strategy space at the last stage of the iterated elimination process, itiiiwould still be rejected at that concluded earlier that a rational player would never play a dominated strategy (because she could dostrictly better in all cases by choosing instead a strategy which dominated that strategy). By assumingthat the rationality of all players is common knowledge, we developed the technique of the iteratedelimination of strictly dominated strategies in order to determine a set of strategies for each player whichsurvive this elimination procedure. We concluded that no player would ever choose a strategy outside ofher surviving set. The implication here was one way: common knowledge of rationality implies that thegame’s outcome must survive the iterated elimination of strictly dominated strategies. We did not showthat every surviving strategy could be reasonably chosen by a rational @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 13An alternative expression of the common knowledge of rationality is closely related to ourdomination discussion: A rational player would never choose a strategy which is not a best response tosome beliefs about opponents’ choices. Further, a player’s beliefs about the choices of others areconstrained in that the other players must be believed to also be playing strategies which are bestresponses to their own beliefs. The rationalizable outcomes are those which survive the iterated14elimination of strategies which are never best responses. However, this argument does go both [1984] argues not only that a rational player must choose her strategies from theirrationalizable set, but also that every strategy in this set can be consistently justified as a rational rational player must choose a best response to her beliefs about the actions of the other players. Forexample, in Figure 10, E is dominated by D; therefore there is no possible belief which Row could hold15about Column’s strategy to which E would be a best response. Therefore a rational Row would neverplay a player’s rationality constrains her action to be a best response to her beliefs, it does notrestrict what her beliefs about others’ actions can reasonably be. (After all, an irrational opponent mightdo anything.) A rational Row player could play B because it is a best response to z. But a rationalColumn would never play z, because it is dominated by y. If Row knew that Column is rational, Rowwould realize that Column would never choose z, and Row would further deduce that B is not a bestresponse to anything Column might rationally do. (B is dominated by C when Column’s strategy spaceis reduced to {w,x,y}.) Row’s knowledge of Column’s rationality restricts Row’s beliefs to put zeroweight on Column choosing 10In summary, if Row and Column are both rational and if Row knows that Column is rational, then wecan restrict our attention to the smaller game {A,C,D}˜{w,x,y} shown in Figure 11. You can convinceyourself that no further elimination of strictly dominated strategies is possible; hence (because this is a16two-player game) all of the outcomes in this smaller game are rationalizable. 14See Fudenberg and Tirole [1991].15I have indicated in boldface type the row payoffs which are maximal in each column and the column payoffs which are maximal in that in two-player games the rationalizable outcomes are exactly those which survive the iterated elimination of strictlydominated strategies. In three-or-more–player games the set of rationalizable outcomes is a weakly smaller set than those survivors ofiterated elimination of strictly dominated @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 14Figure 11: The rationalizable subset of the game from Figure as a consistent system of beliefsWe defined the rationalizable outcomes as those which survived the iterated elimination of strategieswhich were never best responses. In order to focus explicitly on the constraints which commonknowledge of rationality imposes upon players’ beliefs I will now discuss rationalizability from adifferent perspective. Consider the strategy profile (C,x) in the game of Figure 11. I will show that thisprofile is rationalizable by showing that C and x are rationalizable strategies for Row and Column,respectively. To do this I will show that there exists a consistent system of beliefs for the players whichjustifies their choices—. which shows that these choices do not conflict with the common knowledgeof rationality assumption. (See Bernheim [1984].)Let’s establish some notation so that we can tractably talk about beliefs about beliefs about beliefsabout…. Let R and C stand for the Row and Column players, respectively. If Row chooses A, we writeRªAº, and similarly for other choices by either player. If Column believes that Row will choose A, wewrite CRªAº. If Column believes that Row believes that Column will choose y, we write CRCªyº, rational Row player would play C, . RªCº, if she believes that Column will play y; . if RCªyº.Is this belief by Row reasonable? Column would play y if he thought that Row would play D; thereforewe assume RCRªDº. Would Row do this? Row would play D if she thought that Column would play x;therefore we assume RCRCªxº. Finally, Column would choose x if he believes that Row would chooseC, viz. RCRCRªCº. But C is justified by the sequence of beliefs we have just described. We summarize17the beliefs of Row’s which justify her playing C:RªCºR plays C,(27a)RCªyºR believes C will play y,(27b)RCRªDºR believes C believes R will play D,(27c)RCRCªxºR believes C believes R believes C will play x,(27d)RCRCRªCºR believes C believes R believes C believes R will play C.(27e)This hierarchy of beliefs establishes a cycle of strategies (C,y,D,x,C), all of which are thus shown tobe rationalizable. To see how the above argument is sufficient to show that x is rationalizable, let’s lookexplicitly at Column’s beliefs which would make his choice of x rationalizable. Column would play x,Cªxº, if he believed that Row would play C, . if CRªCº. Row would play C if she believed thatColumn would play y; so we assume the belief for Column that CRCªyº. Column would play y if Row 17RªCº is not a belief; but the RC򻾼 expressions below it are @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 15were playing D; therefore we assume CRCRªDº. Row would play D if Column were choosing x. So wehave the same cycle (but shifted) of rationalizable strategies {x,C,y,D,x}. We summarize Column’sbeliefs:Cªxº(28a)CRªCº(28b)CRCªyº(28c)CRCRªDº(28d)CRCRCªxº(28e)Comparing notesWe have shown that the strategy profile (C,x) is rationalizable and have explicitly determined the beliefseach player must hold in order to justify her strategy choice. Let’s examine the properties of thisoutcome from two different perspectives. First, we ask what the players would find if they got togetherto compare notes about their belief systems. Second, we’ll ask what their assessments of the wisdom oftheir strategy choices would be after the game was played; we’ll ask them: “would you do it over againthe same way?”If Row and Column, planning to play C and x, respectively, met to discuss truthfully and candidlytheir perspectives on the game being played, Row would find that her beliefs were all wrong but Columnwould have correctly anticipated see from (28b) that Column correctly conjectured (27a)—that Row would play C. Further, we seefrom (28c) § (28e) that Column also correctly intuited Row’s higher-order beliefs (27b) § (27d). Forexample, Column correctly believed that Row believed that Column believed that Row would choose was not so clairvoyant (or lucky). From (27b) we see that Row believed that Column would playy. In fact, Column played x instead. Not surprisingly, Row also got Column’s higher-order beliefs allwrong. For example, from (27c), we see that Row thought that Column thought that Row would play D;from (28b) we see that Column actually thought that Row would play the game is played, and the actual strategy choices revealed, would the players be happy with18the choices they had made? Would they do it over again the same way? Column correctly forecast thatRow would choose C, and Column played his best response to C, viz., x. So Column would be satisfiedwith the choice he made. 18There is a subtlety here. In general the players choose mixed strategies. I am not asking whether, after the game is played, a player ishappy with the pure-strategy realization of her mixed strategy given the pure-strategy realizations of others’ mixed strategies. I amasking whether she would be happy with her choice of mixed strategy given her opponents’ mixed-strategy choices. To “do it overagain the same way” means to once again choose the same lottery but have the roulette wheel spun again. The way I frame thisscenario, it is implicit that the players would observe their opponents’ mixed strategies, not just the pure-strategy realizations. This issuewill arise @
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 16Row on the other hand incorrectly forecast Column’s choice, thinking that Column would choose yinstead of x. Row’s best response to y, viz. C, was not a best response to the actually played x. ThereforeRow could have received a higher payoff, 7 instead of 5, by playing the best response to x, viz. D, beliefs are held in commonLet’s contrast the properties we identified above for the outcome (C,x) with those of anotherrationalizable outcome: (A,w). The demonstration that A and w are rationalizable requires a much lesscircuitous hierarchy of beliefs. Row would choose A if she thought that Column would choose w, ªwº. Column would choose w if he thought that Row would choose A; . we assume that RCRªAº.This yields our desired cycle of strategy profiles (A,w,A):RªAº(29a)RCªwº(29b)RCRªAº(29c)Similarly, Column’s choice of w can be justified by the beliefs:Cªwº(30a)CRªAº(30b)CRCªwº(30c)We can easily summarize the belief system generated by (29a) § (30c) by saying: It is commonknowledge that Row will play A and Column will play ’s ask the same questions for this rationalizable strategy profile that we asked for (C,x). First, whatmisconceptions would Row and Column discover if they met at Gentle Ben’s to trade their deepestsecrets? Absolutely none. Both players not only correctly anticipated the other’s action but also correctlydivined the other’s beliefs. For example, from (30c) and (29b) we see that Column correctly believedthat Row believed that Column would indeed choose Row and Column played the game and observed each other’s strategy choice, would either wantto change her strategy? No. Because each player correctly anticipated her opponent’s action, each playeda best response to the opponent’s actual choice. Neither player could improve upon her payoff given thechoice of her we see a striking qualitative difference between the profile (C,x) and (A,w). The key lies in thefollowing observation: Consider (C,x). Although x is Column’s best response to C, C is not Row’s bestresponse to x. However, consider (A,w). A is Row’s best response to w, and w is Column’s best responseto A. This is evident immediately from observing the boldface type in Figure 11. The payoff vector (5,8)corresponding to the strategy profile (C,x) had only one element in boldface, indicating that only oneplayer was picking a best response to the other’s choice. On the other hand, both of the elements in thejim@
Nonequilibrium Solution Concepts: Iterated Dominance and RationalizabilityPage 17payoff vector (7,5) corresponding to (A,w) appear in boldface, indicating that both players were pickinga best response to the other’s , Robert J. [1976] Agreeing to Disagree, Annals of Statistics 4 6: 1236—, B. Douglas [1984] Rationalizable Strategic Behavior, Econometrica 52 4 (July):1007—, Drew and Jean Tirole [1991] Game Theory, MIT , Roger B. [1991] Game Theory: Analysis of Conflict, Harvard University , David G. [1984] Rationalizable Strategic Behavior and the Problem of Perfection, Econometrica 52 4 (July): 1029—@
