1 FINITE-ORDER IMPLICATIONS OF ANY EQUILIBRIUM JONATHAN WEINSTEIN AND MUHAMET YILDIZ Fix an arbitrary equilibrium re fi Abstract. nement. Assume that, when we nement applies to a particular fi need to check whether a prediction of this re situation, we only know fi nitely many orders of players’ interim beliefs. Many models may be consistent with this limited knowledge. In this paper, we char- acterize the predictions that are robust to these alternative speci fi cations of the model, in the sense that they remain true independent of which of these models fi is chosen, given that we apply the fi nement to each model. xed equilibrium re ff parameters is rich enough, for generic Assuming that the set of underlying payo ff s, we show that a prediction is robust if and only if it is true for all rational- payo izable strategies. Therefore, equilibrium re fi nements will be useful in generating stronger predictions than those of rationalizability only when we have informa- tion about the entire in fi nite hierarchy of beliefs, which is unlikely in practice. tact when we restrict our attention to We also show that our result remains in nite type spaces, or impose the common-prior assumption. fi : robustness, equilibrium re Key words nement, rationalizability, incomplete fi information, higher-order beliefs. JEL Numbers : C72, C73. Date : First Version: September, 2003; This Version: January, 2004. We thank Daron Acemoglu, Pierpaolo Battiga ff rey lli, Adam Brandenburger, Glenn Ellison, Je Ely, Drew Fudenberg, and the seminar participants at Berkeley, Caltech, Econometric Society Winter Meeting 2003, Harvard, MIT, Northwestern, Penn State, UPenn, Stanford, Washington University, Wisconsin-Madison, and Yale for helpful comments. We thank Eddie Dekel and two anonymous referees for detailed comments. We are especially grateful to Stephen Morris for extensive discussions that led to numerous improvements in the paper. This paper was written when Yildiz visited Cowles Foundation of Yale Uni versity, and he thanks them for their generous support and hospitality. 1

2 2 1. Introduction In economic models, there are often many Nash equilibria. In order to be able to make sharp predictions, game theorists have therefore developed stronger solution nements of equilibrium, such as perfect concepts, which lead to a multitude of re fi nements, fi and robust equilibrium. In applications, researchers typically use these re often applying them to Bayesian games in which speci ctypespacesarechosen fi to model the players’ incomplete information. In this paper, we characterize the predictions of such re fi nements that retain their validity when we actually have only a partial knowledge of the players’ incomplete information. To explain our framework, imagine a researcher who subscribes to some re- fi nement of Nash equilibrium. For each possible incomplete-information model, represented by a Bayesian game, the researcher can compute a set of possible strategies using the re nement. He would like to be able to make predictions in a fi case of genuine incomplete information. By this we mean that when he is asked to yhavesomebeliefsaboutwhatthepayo make his prediction, the players alread s ff are, which are called the fi rst-order beliefs, beliefs about the other players’ beliefs, which are called the second-order beliefs, and so on. In a standard type space, where a type of a player is a signal about payo ff -relevant fundamentals, players form these beliefs at the interim stage upon learning their types, and we can com- pute an entire hierarchy of beliefs for a given type using the joint distribution of signalsandthefundamentals(seeSection3). Now we introduce the key assumption that the researcher is restricted to ob- fi nitely many orders of beliefs. This is especially plausible because serving only common sense suggests that the players themselves will have their beliefs only par- tially articulated in their own minds. In particular, we assume that the researcher fi rst k orders of beliefs and nothing more. Many types that come from observes the di ff erent type spaces are consistent with this observation, i.e., their fi rst k orders of beliefs are as observed. He applies his re nement to obtain a set of strategies in fi each of these type spaces, specifying a set of actions for each of these types. The researcher cannot rule out any of these actions based on his observation and his re fi nement. Now consider the researcher analyzing a particular type space, using his re fi ne- ment. Under our restriction on what he can observe in the interim stage, he can

3 FINITE-ORDER IMPLICATIONS 3 fi cations of higher-order only make predictions that are robust to alternative speci beliefs, in the sense that they will remain true for each of the models consistent fi k orders of beliefs, given that he would have used rst with his observation on the the same equilibrium re fi nement in those alternative models as well. These are the ed by knowing only fi nitely many orders of beliefs. predictions that can be veri fi ff parameters is rich enough, for Assuming that the space of underlying payo ff swewillcharacterizetherobustpredictions: apredictionisrobust generic payo . That is, no if and only if it is true for all rationalizable strategies in the model fi equilibrium re nement produces any more predictive power than rationalizability, unless we also make a very precise assumption about the in fi nite hierarchy of beliefs. In other words, we cannot verify the predictions that are driven by the fi nement without observing the entire in fi equilibrium re nite hierarchy of beliefs. In particular, we show that, if the above researcher observes that the fi rst k , then he cannot rule out any action orders of beliefs are consistent with a type t i that survives k rounds of iterated elimination of actions that are never a strict best . On the other hand, by a result of Dekel, Fudenberg, and Morris reply for type t i (2003), he can rule out the actions that are eliminated in rounds of iterated k .Whenthereareno best reply for type weak elimination actions that are never a t i 1 ), these elimination ties for best response (e.g., in generic games and nice games procedures lead to the same outcome, yielding the above characterization. This characterization is extended to all cases by allowing slight uncertainty in lower- order beliefs. One may think that the above lack of robustness may be due to some large type spaces that do not satisfy certain standard assumptions, such as the common- prior assumption. Our conclusions, however, remain virtually unchanged when we restrict the possible type spaces to be fi nite and generated by a common prior. This is mainly because the common-prior assumption does not put any signi fi cant fi nite-order beliefs (Lipman (2003)). restriction on A key element of our perspective on robustness is that we consider hierarchies of 2 ff -relevant parameters to be the basic objects to be perturbed. beliefs about payo 1 These are games where the action spaces are com pact intervals and the utility functions are strictly concave in own action and continuous, as in many classical economic models. 2 We de fi ne a perturbation as a mapping to a new type space such that the image of each type has the same fi rst k orders of beliefs as the original type (see Section 5).

4 4 JONATHAN WEINSTEIN AND MUHAMET YILDIZ fi les Alternatively, one could focus on perturbations of prior beliefs on type pro (e.g. Kajii and Morris (1997)). That is, we focus on the interim stage (after types are realized, but before actions are taken), rather than the ex-ante stage. This approach is attractive because the ex-ante stage is often a hypothetical construct used to model the beliefs players hold in the interim stage (see Dekel and Gul (1987) and Battigall i (2003) for a detailed discussion). It is therefore appropriate to consider two situations with similar interim beliefs to be close, regardless of what prior beliefs led to the existing situation. Since distinct ex-ante models can lead to similar interim beliefs, our approach deals with the modeler’s problem of selecting an ex-ante model that is appropriate for a given interim situation. We wanttomakepredictionsthatareindependentofselectionamongthemodelsthat are consistent with the data. In the next section, using a variant of the e-mail game, we illustrate our results and compare them to the major existing results in the robustness literature. We fi nitions in Section 3. In Section 4, we prove a key result present the basic de about the sensitivity of equilibria in universal type space, which will lead to the results in Section 5. In Section 5, we formulate our robustness notion and char- fi acterize the robust predictions of arbitrary equilibrium re nements. In Section 6, we present a modi fi ed version of our result without the richness assumption. In Section 7, we present three applications of our results, obtaining stark results on Cournot oligopoly and continuity and robustness of equilibrium strategies. Section 8 concludes. Some of the proofs are relegated to the appendix. E-mail Game and Literature Review 2. To fi x our ideas consider the coordinated attack game with payo ff matrix Attack No Attack Attack θ , θ θ − 5 ,0 No Attack θ − 5 0,0 0, where θ ∈ Θ = { − 2 , 2 , 6 } . First, consider the model in which it is common knowledge that =2 . Thiscaseismodeledbyatypespace T with only one θ CK .Inthisgame,thereare (2) t type for each player i , which will be denoted by i two Nash equilibria in pure strategies, namely, (Attack, Attack) and (No Attack, No Attack), and an equilibrium in mixed strategies. Now imagine an incomplete

5 FINITE-ORDER IMPLICATIONS 5 nd it possible that = − 2 .Ex fi θ informationgameinwhichtheplayersmay 2 and 2 .Player1 ante, players assign probability 1/2 to each of the values − and automatically sends a message if θ =2 .Eachplayer θ observes the value of automatically sends a message back whenever he receives one, and each message is lost with probability 1/2. When a message is lost the process automatically stops, and each player is to take one of the actions of Attack or No Attack. This ̃ T = { − 1 , 1 , 3 , 5 ,... }×{ 0 , 2 , 4 , 6 ,... } game can be modeled by the type space , i is the total number of messages sent or received by player t where the type i p = − 1 who knows that θ = − 2 ), and the common prior t (except for type 1 ̃ = − 1 ,t 1 =0) = 1 / 2 and for each integer m ≥ , × p T where on ( θ = − 2 ,t Θ 2 1 2 m =2 ,t 1 − =2 m − 1 ,t m =2 m − 2) = 1 / 2 )= m and p ( θ =2 ,t =2 ,t =2 θ ( p 1 2 2 1 m +1 2 ≥ . Here, for k , knows that the other player 1 ,type k knows that θ =2 / 1 2 θ ,andsoonthrough knows k orders of belief. The new incomplete-information =2 game is dominance-solvable, and the unique equilibrium action for each player is No Attack. k orders Recall the researcher from the introduction, who could observe only of beliefs for each player and has no knowledge of how players arrived at these θ beliefs. Suppose that he observes that the players mutually believe that =2 through k orders of beliefs. He cannot know whether the true model is T ,or ̃ k T and the players have types greater than or equal to whether the true model is . Now suppose that he subscribes to a non-empty equilibrium re fi nement that selects T the (Attack,Attack) equilibrium in the complete information game ,asPareto- dominance does. Since his re fi nement must assign the outcome (No Attack, No ̃ T Attack)foreachpossibletypeinthealternativetypespace , the researcher cannot know whether the outcome will be (Attack, Attack) or (No Attack, No Attack) according to his solution concept. To put it di ff erently, even if the researcher believed that the right model is T and it is commonly accepted that his solution concept is the right solutio n concept, he could not prove his prediction that there will be an attack with the available data, which is insu ffi cient to con fi rm that the ̃ correct model is and not T . Consequently, we say that his prediction that there T willbeanattackisnotrobustatorder k ,forany k . The above argument is based on Rubinstein’s (1989) result that an equilib- rium re fi nement that selects (Attack,Attack) must be sensitive to speci fi cations of higher-order beliefs. A re fi nement that selects (No Attack,No Attack) is not

6 6 JONATHAN WEINSTEIN AND MUHAMET YILDIZ sensitive in this example. Subsequently, in their seminal paper, Carlsson and van Damme (1993) presented a class of similar p erturbations, where players observe noisy signals, according to which nearby types would always play the risk-dominant equilibrium, which is (No Attack, No Attack) in the above game. They then pro- posed that we should instead select the risk-dominant equilibrium of (No Attack, No Attack). As we will discuss later, Kajii and Morris (1997) also proposed a no- tion of robustness to incomplete information, according to which (No Attack, No Attack) is a robust equilibrium. Nevertheless, as we will now show, an equilibrium re fi fi cations nement that selects (No Attack, No Attack) must be sensitive to speci nements that select (At- of higher-order beliefs in precisely the same way as re fi = − 2 with θ =6 ,we θ tack, Attack). Indeed, if in the above example we replace obtain another, equally natural model, for which (Attack, Attack) is the unique 3 That is, we consider a new model fi le. equilibrium outcome for each type pro ˇ 5 = { − 1 , 1 , 3 , with type space ,... T 0 , 2 , 4 , 6 ,... } and the common prior q }×{ ̃ 1 ≥ m , and for each integer 2 / =0) = 1 ,t 1 − = T θ ( q where =6 × Θ on ,t 2 1 2 m =2 ,t 1 − =2 m − 1 ,t m =2 m − 2) = 1 / 2 )= m and q ( θ =2 ,t =2 ,t =2 θ ( q 1 2 2 1 2 m +1 . One can easily check that this game is dominance-solvable, and all types 1 / 2 play Attack. In our formulation, then, of the possible predictions are non- both robust, and the predictions of risk-dominance are no more robust than those of Pareto-dominance or other re fi nements. Indeed, our result will establish for ar- bitrary games and equilibrium re fi nements that a prediction will be robust only if it is true for all strategies that survive our elimination process–in the above example, all actions survive this process. With the above example in mind, we now compare our result to important earlier results on robustness. Kajii and Morris ( 1997) introduced a notion of robustness of a given equilibrium of a given complete-information game to incomplete infor- fi nition requires that for any incomplete-information game with mation. Their de a common prior that puts high probability on the original game, the original equi- librium action of the complete information game is played by most of the types in 4 This concept of robustness an equilibrium of the incomplete information game. 3 At the end of Section 5, relaxing their assumptions on the noise structure, we also fi nd a similar example in the framework of Carlsson and van Damme (1993). 4 In Subsection 7.3, we give the formal de fi nition of robust equilibrium and show how their results change when we switch to an interim notion of perturbation or drop the common-prior assumption.

7 FINITE-ORDER IMPLICATIONS 7 rules out incomplete information games that involve large changes in prior but may lead to interim beliefs that are similar to the actual situation. They thus 6 =2 is not close to zero. Thus, they exclude the e-mail game, if the probability of θ would exclude the constructions above, in which that probability is 1/2. Kajii and Morris (1997) show, nevertheless, that this construction would work for the risk- dominant equilibrium (as in the original e-mail game), even if that probability is 5 Our latter example would not work if that probability is small. As we have small. shown above, however, a researcher could not distinguish these probabilities with- out having the knowledge of the entire in fi nite-hierarchy of beliefs. Then, the key ff erence between our notions of perturbation is that they focus on small changes di prior to interim beliefs, while our beliefs, without regard to the size of changes to focus is the reverse. Their approach is appropriate when there is an ex-ante stage with well-understood inference rules and we know the prior to some degree. As we discussed in the introduction, however, in genuine incomplete-information situa- tions, the type spaces and ex-ante stage are just tools for modeling interim beliefs. In that case, it is appropriate to consider types with similar interim beliefs, even if they come from models that assign small prior probability to the actual situation. Another distinction is that we ask if a predicted behavior is true in the perturbed game in every equilibrium that satis es a given re fi nement, while they ask whether fi the predicted behavior is true in some equilibrium of the perturbed game. Our approach allows us to check directly if a theorem of the form "for all equilibria s that satisfy (a given) re fi nement, Q ( s ) is true" remains valid if the modeling assumptions are slightly altered in the sense of this paper. The robust equilibrium notion of Kajii and Morris is silent as to whether such a theorem would remain valid if we modify the model using their perturbation. Brandenburger and Dekel (1987) have shown that given a distribution on ratio- fi lesofagivencompleteinformationgame,wecanenrichtype nalizable strategy pro ff -irrelevant types and fi space by adding payo nd an equilibrium in the new game 6 that yields the same distribution on the strategy pro fi les of the original game. 5 Using the construction of Kajii and Morris ( 1997), for complete-information games, one could show that any robust prediction of a re fi nement must be true for ( p ) -dominant ,...,p 1 n equilibrium with p if such an equilibrium exists. + ··· + p 1 < n 1 6 This result has been extended t o incomplete-information games by Dekel, Fudenberg, and Morris (2003) and also by Battigalli and Siniscalchi (2003), who also consider common-knowledge restriction on fi rst-order beliefs. Our discussion applies to these extensions as well.

8 8 JONATHAN WEINSTEIN AND MUHAMET YILDIZ That is, in order for a prediction to be robust with respect to the entire set of equilibria nements ,itmustbetrueforallrationalizablestrategies. without any re fi fi for any re of equilibrium, when we allow other In contrast, we show that nement payo ff -relevant types from alternative models that lead to similar interim beliefs, in order for a prediction gained by the re nement to be robust, it must be true for fi all strategies that survive our elimination process. Notice that these two results point to somewhat contradictory properties for equilibrium correspondence. Bran- denburger and Dekel suggest a large multiplicity of equilibria. Our result suggests fi ne rationalizability without precise information about types. that it is hard to re This in turn suggests that there are relatively few rationalizability actions for a large set of types. Following our framework, Yildiz (2005) shows that generically there is indeed a unique rationalizable action. Considering only payo ff -irrelevant types (as Brandenburger and Dekel do), one cannot address the problem of robustness for arbitrary re fi nements, addressed in this paper. To see this, consider a non-dominance-solvable complete-information game with a pure Nash equilibrium, such as the complete-information case of the coordination game above. Following Brandenburger and Dekel, consider incom- plete information games in which players have private information about some ff -irrelevant parameter. By Tan and Werlang (1988), there is such an incom- payo plete information game with an equilibrium such that each rationalizable strategy is played by some type. Since all types have the same belief hierarchy, this equi- librium is highly sensitive to higher-order beliefs. Because of this equilibrium, we cannot rule out any rationalizable action without invoking a re fi nement. Neverthe- less, in those models, there always exists another equilibrium in which all types play accordingtoa fi xed pure strategy equilibrium of the original complete-information game. In contrast to extreme discontinuity of the former equilibrium with respect 7 this equilibrium is constant. Then, ff s, to players’ hierarchy of beliefs about payo following Carlsson and van Damme (1998) and others, such as Morris and Shin (1998), we can invoke a continuity argument to eliminate the discontinuous equi- librium. This would take us back to a subset of the equilibria of the original game. In contrast, if one considers the payo ff -relevant types of our paper, it will be hard to invoke such a continuity argument. We show that, under a rich set of parame- ters, every rationalizable strategy will be discontinuous at every type with multiple 7 It is not even a function of these beliefs.

9 FINITE-ORDER IMPLICATIONS 9 fi nements based on continuity would lead to the empty rationalizable strategies; re set when we consider all possible types. It is crucial for the result of Brandenburger and Dekel that they drop the common-prior assumption. By Aumann (1987), under the common-prior assump- tion, all types in their type spaces must play a correlated equilibrium strategy. Since economists commonly work under the common-prior assumption, they may ignore such a result. In contrast, each of the type spaces we constructed above has a common prior. Indeed, our results will remain virtually intact when we impose the common-prior assumption. Our approach is closest to that of Fudenberg, Kreps, and Levine (1988) and Dekel and Fudenberg (1990). Fudenber g, Kreps, and Levine (1988) have shown that any equilibrium of any complete-information game can be made strict by ff perturbing the payo s, showing that one cannot obtain any more predictions than fi those of all equilibria by considering re nements that do not eliminate any strict fi nements that do eliminate some strict equilibria, equilibria. Our result covers re such as the popular risk-dominance, and compares them to the larger set of all rationalizable strategies for arb itrary information structures. In the same vein, Dekel and Fudenberg (1990) analyze the robustness of pre- dictions based on iterated elimination of weakly dominated strategies when one allows payo ff uncertainty as in this paper. They show that with uncertainty about players’ beliefs at all orders, the robust predictions gained from this procedure for a complete-information game is equivalent to those of iterated strict domi- 8 They also nance after one round of eliminating weakly dominated strategies. show that even if we know that each player’s prior put high probability to origi- ff s, we could not rule out the possibility that a strategy that survive the nal payo latter elimination process is a strict equilibrium action. Hence, under this limited knowledge, the "robust" predictions of a re fi nement that does not eliminate any 8 Borgers (1994) shows that the latter solution concept charcterizes the strategies that are consistent with almost common knowledge of players not playing weakly dominated strategies. Here, almost common knowledge is in the sense of common -belief by Monderer and Samet p (1989). Monderer and Samet show that an equilib rium remains as an approximate equilibrium (similar to robust equilibrium of Kajii and Morris) if there is common p -belief of the original game for high p , but we cannot check this condition without knowledge of in fi nite hierarchy of beliefs.

10 10 JONATHAN WEINSTEIN AND MUHAMET YILDIZ strict equilibrium are no more than the predictions of the latter solution concept. Nevertheless, as they note, their construction crucially relies on their departure from the common-prior assumption (as in Brandenburger and Dekel), and without common-prior assumption, such restrictions on priors do not put any restriction on the second-order beliefs and higher (see Section 7.3). Hence, in our formulation, they in e ff ect assume that the researcher has information only about the rst- fi order beliefs. In contrast, we consider arbitrary re fi nements, arbitrary information structures (as opposed to the complete information games) for the original game, impose common-prior assumption, allow the researcher to observe players’ beliefs at arbitrarily high orders (as opposed to just observing the rst-order beliefs), and fi 9 yet we conclude that the robust predictions are just those of rationalizability. Following the critique of Wilson (1987), a sizeable literature has established that fi ndings in economics, such as the full surplus extraction property of some central Cremer and Mclean (1988) in mechanism design (Neeman (2004) and Heifetz and Neeman (2003)) and the Coase conjecture in bargaining (Feinberg and Skrzypacz (2002)), crucially rely on the assumptions on the second-order beliefs and higher. In this paper, considering general games, under a richness assumption, we show that every equilibrium is highly sensitive to the way higher-order beliefs are speci- fi ed. When all the common-knowledge assumptions are dropped, one cannot make any prediction that is stronger than rationalizability, no matter how sophisticated the re nements one uses. Of course, some may want to make explicit common- fi ff knowledge restrictions on players’ payo s and beliefs. In that case, it seems that a similar analysis to ours would show that the predictions of any re fi nement that remain valid with only partial knowledge of interim beliefs will be equivalent to that of ∆ -rationalizability of Battigalli and Siniscalchi (2003), which corresponds 10 to common-knowledge of these assumptions and rationality. 9 We show that, if we just know the fi rst-order beliefs, then robust predictions are just those of rationality. 10 Battigalli and Siniscalchi (2003) justify their solution concept following the framework of Brandenburger and Dekel; the above discussion of Brandenburger and Dekel applies to their analysis as well.

11 FINITE-ORDER IMPLICATIONS 11 3. Basic Definitions N We consider a 1 , 2 ,...,n } . There is a possibly unknown = nite set of players { fi ∈ Θ where Θ is a compact (and hence complete and θ ff payo -relevant parameter and utility function A separable) metric space. Each player i has action space i Q 11 A → R ,where A : Θ er in × ff . A We consider the set of games that di = u i i i cationsofthebeliefstructureon θ , i.e. their type spaces, which we their speci fi ×···× T associated with beliefs = also call models. A type space is a set T T 1 n . ∈ ∆ ( Θ × T T ∈ ) for each t κ i − i t i i by in a type space T , we can compute the belief of t Θ on t Given any type i i 1 t , = κ marg t Θ i i which is called the t fi rst-order belief of . We can compute the second-order belief i 1 1 ( θ,t , by setting ) ,...,t , i.e. his belief about t of i n 1 ¡ ¢ ª¢ ¡© 1 2 1 t ,t )= κ F ) | ( θ,t ( θ,t F ∈ − t i i i − i i n ⊆ Θ × ∆ ( Θ ) for each measurable F . Wecancomputeanentirehierarchyof ¢ ¡ 2 1 k ,t ,...,t by proceeding in this way. We say that a type space ,... T beliefs t i i i does not have redundant types if ¢¡ ¡ ¡ ¢ ¢ 1 1 2 k 2 k ̃ ̃ ̃ ̃ ̃ t ,...,t 6 = ,t ,... t t T , ⇒ t ∈ , ,..., t t = t ,... 6 ∀ . t i i i i i i i i i i i Mertens and Zamir (1985) showed that any type space without redundant types fi ne following can be embedded in the universal type space, which we proceed to de 12 Brandenburger and Dekel (1993). nition incorporates an additional assumption that the players’ beliefs at Our de fi nite order have countable (or fi each nite) support. This assumption is made to fi Q Q 11 Notation: ,...,Y = of sets, write Y = Given any list y Y , , Y Y Y = i 1 n i − j i − 6 i = j i ( y ,y . Likewise, for ) ∈ Y ,and ( y ,y )=( y ,...,y ,...,y ,y ,y ,...,y ) ,...,y i 1 − i n i − 1 i − 1 − i i i +1 1 n i +1 any family of functions f by : . → Z )) ,wede fi ne f y ( : Y f )=( → Z y ( Y f i − j − − i i − j i − j j j i 6 = i j Given any metric space ( Y,d ) ,wewrite ∆ ( Y ) for the space of probability distributions on Y , endowedwithBorel σ σ -algebra in product -algebra and the weak topology. We use the product δ spaces. We write for the probability distribution that puts probability 1 on { x } .Wealso x write supp ( π ) for the support of a probability distribution π ,marg for the marginal of π on π Y Y , and proj . for the projection mapping to Y Y 12 If there are redundant types, one needs to consider a larger type space (Ely and Peski (2004)) in order to analyze the robustness of predictions . The results of such an analysis will, if anything, show more sensitivity to the assump tions about higher-order beliefs.

12 12 JONATHAN WEINSTEIN AND MUHAMET YILDIZ avoid technical issues related to measurability (see Remark 1.) Our type space is dense in universal type space, and any countable type space with no redundant type is embedded in our space. i h n ˆ ) and X = X Θ = × inductively by ( X ∆ X De ne a sequence of sets fi 1 k − k k 0 ˆ ) for each k> 0 ,where ( ∆ ( X X is the set of probability distribu- ∆ ) ⊆ X 1 k − 1 1 − k − k Q u u that have countable support. Universal type space T = is T X tions on k − 1 i N i ∈ ³ ́ n Q ∞ ˆ the subset of in which it is common knowledge that the players’ ) X ( ∆ − 1 k =1 k beliefs are coherent, i.e., the players know their own beliefs and their marginals in universal type space is sim- erentordersagree. Noticethatatype from di ff t i Q ∞ 2 1 ˆ ,... ,t ∈ ) . We will use the ) fi ply the in ( nite hierarchy of beliefs t ∆ ( X k − 1 i i =1 k u u ̃ ̃ , T ∈ T as generic type ∈ as generic types of any player i and t, t t t variables i i i les. fi pro From now on we will focus on type spaces with no redundant types; allowing redundant types would not change our results. As we mentioned, each such type 13 We will space is isomorphic to a belief-closed subset of universal type space. therefore represent all such type spaces as belief-closed subsets of universal type as its belief hierarchy: space, and write each type t i ¢ ¡ 1 2 k = ,t . t ,...,t ,... t i i i i T T fi A type space (or a belief-closed subset) i ff is said to be contains fi nitely nite 1 fi T .Membersof has fi nite support for each t nite type ∈ t many members and i i i spaces are referred to as . fi nite types : s .Given A → is any measurable function T i strategy T w.r.t. A of a player i i i i ) A and any pro fi le s × Θ of strategies, we write π ( ·| t ( for ∆ ∈ ) ,s t any type i − i − i i i − the joint distribution of the underlying uncertainty and the other players’ actions ; and s ·| fi ned for correlated mixed strategy π ( t is similarly de ,σ ) induced by t i − i i i − ) π ( BR ,wewrite ) .Foreach i ∈ N and for each belief π ∈ ∆ ( Θ × A σ le fi pro − i i i − ) ∈ A ,a that maximize the expected value of u θ,a ( a for the set of actions − i i i i i ∗ ∗ ∗ s ,s ) is a ,... =( le s under the probability distribution π .Astrategypro fi 2 1 , i ff at each t Bayesian Nash equilibrium i ¢¢ ¡ ¡ ∗ ∗ ) t ( BR ∈ ,s t ·| π . s i i i i − i 13 u T ⊂ T . Aset belief-closed i ff supp ( κ T ∈ ) ⊂ Θ × T t for each is said to be i − i t i i

13 FINITE-ORDER IMPLICATIONS 13 ∗ u on universal type space full range i ff An equilibrium T s is said to have u ∗ s (FR) T )= A. ( We prove a modi ed version of our results without this full range assumption in fi Section 6. Moreover, the assumption is without loss of generality, as we can restrict u ∗ , by eliminating the actions that are never played in ) ( T the action space to s ∗ . Finally, full range is implied by the following assumption on the equilibrium s , commonly used in the global games literature. We will richness of the set Θ mention this assumption explicitly for those results for which it is used. a i ,thereexists θ ∈ . a and each (Richness Assumption) For each i Assumption 1 i Θ such that a a 0 0 i i ) ,a a ∀ ) >u , ( θ ( θ ,a )( a ,a = 6 . ∀ a ,a u − i i − i i i i i − i i This assumption corresponds to allowing the broadest possible set of beliefs s,whichshouldbeallowedwhenwedropallcommon- ff about other players’ payo knowledge assumptions. ∗ on universal type space has Under Assumption 1, every equilibrium s Lemma 1. full range. . We will use interim rationalizability of Dekel, Fuden- Elimination Processes 003), Battigalli and S iniscalchi (2003). berg, and Morris (2003); see also Battigalli (2 Interim rationalizability allows correlations not only within players’ strategies but . Clearly, allowing such correlation only makes also between their strategies and θ our sets larger. Since our main result is a lower bound in terms of these sets, this only strengthens our result. Moreover, our characterization provides yet ,set cation for this correlated rationalizability. For each i and t another justi fi i k k 0 ] ]= A t ,andde fi ne sets S if [ t t ] for k> 0 iteratively, by letting a [ ∈ S [ S i i i i i i i i ¢ ¡ T × ( such that ) A × ∈ π BR for some π ∈ ∆ Θ marg a and only if i i i i − − A × Θ i − ¢ ¡ k − 1 a =1 ,i.e., a t [ and π ∈ is a best reply to a belief ] π = S κ marg × − i t − i i Θ T i i − − i k − 1 orders of that assigns positive probability only to the actions that survive )is i (with type t elimination. The set of all rationalizable actions for player i ∞ \ ∞ k t t ]= . ] [ [ S S i i i i =0 k

14 14 JONATHAN WEINSTEIN AND MUHAMET YILDIZ T ), we mean a strategy s rationalizable strategy : T By a → A (w.r.t. a model i i i ∞ [ ∈ S ( with s t ] for each t ) ∈ T . t i i i i i i fi Next we de ne the set of strategies that survive iterative elimination of strategies 0 ∞ A ] , similarly. We set W ]= [ t t [ that are never strict best reply, denoted by W i i i i ¢ ¡ k W a ∈ [ t π ] if and only if BR for some and let } a { = ∈ π marg i i i i × Θ A i i − ¢ ¡ − 1 k A ) such that marg ] =1 π = κ [ and π t a ∈ W × .Fi- T × Θ ( ∆ − i i i i t Θ × T − − − i − i − i nally, we set ∞ \ k ∞ t ]= t [ . W ] [ W i i i i k =0 Notice that we eliminate a strategy if it is not a strict best-response to any belief on the remaining strategies of the other players. Clearly, this yields a smaller set than 14 In some games, the result of iterative elimination of weakly dominated strategies. the latter may yield strong predictions. For example, in fi nite perfect information games it leads to backwards induction outcomes. Nevertheless, in generic normal- form games of complete information, all these concepts are equivalent and usually have weak predictive power. Sensitivity to higher-order beliefs 4. In Section 5, we will analyze the robustness of predictions according to arbitrary nements to the assumptions about higher-order beliefs in arbitrary equilibrium re fi type spaces. Robustness of such predictions is closely related to the sensitivity of an equilibrium on universal type space with respect to the changes in higher-order beliefs. In this section, we will focus on the latter problem. ∗ on universal type space and a type t of a player i . fi s x an equilibrium We i ∗ ) . Now imagine a researcher who only t ( s According to equilibrium, he will play i i ∗ is rst k orders of beliefs of player fi and knows that equilibrium s knows the i i will play played. All the researcher can conclude from this information is that one of the actions in ª © ¡ ¢ ∗ k m m ∗ u ̃ ̃ ̃ , . k ≤ ] m ∀ t = ∈ T ,t ≡ s t [ s t | t A i i i i i i i i 14 In particular, if we use non-reduced normal-form of an extensive-form game, many strategies will be outcome equivalent, in which case our proc edure will eliminate all of these strategies. To avoid such over-elimination, we can use reduced-f orm, by representing all outcome-equivalent strategies by only one strategy.

15 FINITE-ORDER IMPLICATIONS 15 fi Assuming, plausibly, that a researcher can verify only nitely many orders of a will play one of the player’s beliefs, all a researcher can ever know is that player i actions in ∞ \ k ∞ ∗ ∗ s ]= . s [ [ ] ,t ,t A A i i i i k =0 k ∗ [ s ,t ] for games with countable A fi Our next result nds tight bounds for the sets i i action spaces. ∗ For any countable (or A , any equilibrium Proposition 1. s nite) action space fi ,andany ∈ , i ∈ N k t with full range, any , N i k ∗ k k ]; A t [ ] [ s ⊆ ,t ] ⊆ S [ t W i i i i i i in particular, ∞ ∞ ∗ ∞ W ] ⊆ A ⊆ ] [ s [ ,t t ] t S . [ i i i i i i k k ∗ [ t ,t ] ⊆ A can be spelled out as follows. Suppose [ ] s The conclusion that W i i i i k th order and do not have any further that we know a player’s beliefs up to the that survives k rounds of a information. Suppose also that he has an action i iterated elimination of strategies that cannot be a strict best reply–for some type whose fi rst k orders of beliefs match what we know. Then, we cannot rule out that ∗ . Now, consider the equilibrium re fi nement that will be played in equilibrium s a i ∗ at each type space T .Ifanaction a T survives k to selects the restriction of s i ,thenwe within a type space T t rounds of our elimination procedure for a type i nd another type, possibly from another type space, whose fi rst k orders of fi can but plays a according to the unique solution of the ed by fi t beliefs are as speci i i as a solution of our equilibrium nement. Hence, we cannot rule out action a fi re i fi re rst k orders of beliefs are as speci fi ed nement when we only know that the fi fi nement then can only be robust if it remains true . A prediction of our re t by i as the solution at t . In the next section we will formalize this a when we assign i i fi nements. We now proceed to the proof of the result, for arbitrary equilibrium re which highlights the logic behind this sensitivity to higher-order beliefs. k k ∗ t =0 ] ⊆ ] , the statement is equiva- k [ s [ ,t .For A We fi rst show that W Proof. i i i i and any player i k t lent to the full-range assumption. For any given ,writeeach − i ¡ ¢ ¡ ¢ +1 k k − 1 1 2 k t are the lower ,... =( l,h ,t ) ,...,t where l = as t ,t h = t and − i − i − i − i i − − i

16 JONATHAN WEINSTEIN AND MUHAMET YILDIZ 16 © ª u l l,h ) ∈ T = L ∃ h and higher-order beliefs, respectively. Let | :( . The induction − i hypothesisisthat [ − 1 k − 1 u 0 ∗ k − 1 k ] ≡ T [( l,h )] . ⊆ A ) W [ ∈ ) [ s l , ( l,h )] ( ∀ ( l,h W − i i − − i i − 0 h k ̃ ∈ W and any such that [ t t ] . We will construct a type a Fix any type t i i i i i ¢ ¡ ∗ ̃ ̃ t ,showingthat and and the fi rst k orders of beliefs are same under t t a = s i i i i i ¢ ¡ k ∗ k s ∈ ,t a ] .Now,byde fi nition of W A { [ t = ] , BR π } [ for some marg a i i i i i × Θ A i i i − ¢ ¡ ¢ ¡ 1 k − u × A . ] t W ∈ a =1 [ π π = κ and such that marg ∈ ∆ π Θ T × i − × T − i Θ − i t − i i i − i − ¢ ¡ ∈ ) π marg ∈ supp a , By the induction hypothesis, for each θ,l,a ( i i − − A × L × Θ − i ¢ ¡ 1 k − 1 − k ∗ marg → for some s ⊆ , ( l,h )] l h . Hence, there exists a mapping μ : supp [ ] π [ A W L × A × Θ i − − i i − u , × T Θ − i ́ ³ ̃ ,θ,l a ( ) 7 → ) θ,l, , h :( μ (4.1) θ,l,a i − − i such that ³ ́ ∗ ̃ (4.2) s l, ( a h ,θ,l ) = . a − i − i − i ̃ by fi ne We de t i ¢ ¡ 1 − κ π ≡ , μ ◦ marg ̃ t A × L × Θ i i − u T the probability distribution induced on Θ × by the mapping μ and the prob- − i k has countable support and the action ability distribution . Notice that, since t π i ¢ ¡ is μ is countable, in which case π marg spaces are countable, the set supp × L × Θ A i − is well-de fi ned. By a well-known isomorphism by trivially measurable. Hence κ ̃ t i ̃ , such that is the belief of a (unique) type t Mertens and Zamir (1985), κ ̃ i t i m ̃ − 1 m × δ = 1) , m> ( marg ∀ κ (4.3) t N } i \{ ̃ ̃ t i t ( ∆ )] X i × Θ [ m 2 − i ¡ ¢ 1 m ̃ ̃ t and κ κ has countable support. =marg . Since supp is countable, each t ̃ ̃ t t Θ i i i i μ ,the fi rst k orders of beliefs (about ( θ,l ) ) are identical under By construction of ̃ t : and t i i ¢ ¢ ¡ ¤ £¡ 1 − marg = marg κ π μ ◦ π marg marg = marg ̃ t Θ × Θ L × Θ Θ A Θ × L L L × × L × A × i i − i − ³ ́ = marg marg = marg = , π κ marg π u t L Θ L × Θ T Θ × L × × Θ i i − where the second equality is by (4.1). Together with (4.3) and identical equality ¢ ¡ m m ∗ ̃ ̃ , = t t ,thisshowsthat for each m s k . Towards showing that ≤ a = t t for i i i i i i

17 FINITE-ORDER IMPLICATIONS 17 ¡ ¢ u − 1 ̃ κ let ∈ ∆ ̃ Θ × = ,where π × A ◦ γ T be the equilibrium belief of type t ̃ i − i t − i i ¢ ¡ ∗ .Byconstruction, l,h ( ) γ → 7 ) θ,l,h :( θ,l,s − i 1 − 1 − marg γ ̃ π = κ proj ◦ ◦ ̃ t Θ × A × L Θ × L × A i − i − i ¡ ¢ − − 1 1 − 1 proj π = ◦ μ π. marg = γ ◦ marg ◦ Θ A × A × Θ × L L × × A × Θ L i i − − i − γ , proj [By (4.2) and the de nition of fi ◦ γ ◦ μ is the identity mapping, L × A Θ × − i yielding the last equality.] Therefore, ¢ ¡ ∗ ̃ = marg ·| t π ̃ ,s marg = π π. i × Θ Θ × A A i − i − − i ∗ ̃ a Since is the only best reply to these beliefs, : must play a t in equilibrium s i i i ¢ ¡ ¢¢ ¡ ¡ ¡ ¢ ∗ ∗ ̃ ̃ s (4.4) π . ,s a { = } t BR = BR ∈ ·| marg π t i i i i i Θ × A i i − − i m k m k ∗ ̃ ̃ for ] ⊆ S [ t [ t = ] ,observethatforany s t t with ,t A To see the inclusion i i i i i i i ≤ k ,wehave m each ¤ ¤ £ £ ¢ ¡ ∞ ∗ k k ̃ ̃ ̃ s ] t [ , ∈ S t S t t S ⊆ = i i i i i i i i where the last equality is due to a result by Dekel, Fudenberg, and Morris (2003) ¡ ¢ k k 1 that S depends only on the fi [ k orders of beliefs t rst ] ,...,t t ,completing i i i i the proof. [Dekel, Fudenberg, and Morris (2003) make some further niteness fi assumptions. For a constructive but much longer proof of the last part under our relaxed assumptions, see our earlier working paper.] ¤ Remark 1. Notice that the countability assumptions about the fi nite-order be- ned is a well-de fi liefs and the action spaces are used only to make sure that κ ̃ t i is measurable. In fact, whenever μ probability distribution, or μ is measurable, our μ is measurable; proof is valid. Below, we present another class of games in which may not be measurable in general. These assumptions are not needed at all for μ k ∗ k s [ ,t . ] ⊆ S [ t ] A the inclusion i i i i The next example shows that either of the inclusions in Proposition 1 may be strict in general.

18 18 JONATHAN WEINSTEIN AND MUHAMET YILDIZ Take Example 1. { 1 , 2 } , Θ = { θ N ,θ = } , and let the action spaces and the 0 1 θ be given by ff payo functions for each 1 0 a a 0 . 0,0 a 0,0 1 1,1 a 0,0 ∗ ff relevant.) De fi ne s (Note that θ is not payo by ( CK 0 ( = ); t θ if t a 0 i i ∗ )= t ( s i i 1 otherwise. a 0 k 1 k 1 [ t , ]= { a } and S t [ t ]= { a ,a } for each k 1 Clearly, for each W ≥ ,wehave i i i i i ¤ ¤ £ £ CK 1 1 0 k k ∗ ∗ CK = { a ( ,a . } ,and A } θ ; ) ) ; t t a ( θ { = s s A while 1 0 i i i i On the other hand, in many cases the two elimination processes are equivalent, k . We now present and Proposition 1 yields a precise characterization of the set A ¢ ¡ CK ̄ denote the type who believes that it θ two such important cases. First, let t i 15 ̄ ̄ = θ at which the payo ff θ θ ,forsome s are generic. is common knowledge that In this case, any action that is not strictly dominated will be a strict best reply against some belief (at each round), and hence the two elimination processes will be equivalent. Therefore, Proposition 1 yields the following characterization. ∗ with full range, Corollary 1. For any fi nite-action game and any equilibrium s saregenericatsome θ , then for each i and k , if the payo ff ¤ ¤ £ £ k ∗ CK k CK ) ,t = S ( ) θ . θ ( t s A i i i i = k ,we fi nd that the set of actions we cannot exclude In particular, letting ∞ fi nite-order knowledge of players’ beliefs is precisely the set of rational- with only izable actions. The second case is the class of “nice” games (Moulin (1984)), which are widely used in economic theory, such as imperfect competition, spatial competition, pro- vision of public goods, theory of fi rm, etc. 15 A i ff s are generic at θ i ff there do not exist i ,non-zero α ∈ R We say that the payo , and distinct P 0 0 0 a , α ,a θ,a ,and a a such that (i) u ( ( θ,a u ,a ) a )= u ( ( θ,a a ,a , )= ) or (ii) − i i − i i i i i i i i i − − i − i i a i ¢ ¡ P 0 a ) u ( α ,a . θ,a =0 i i i − i a i

19 FINITE-ORDER IMPLICATIONS 19 ,a fi i ff for each i , A nition 1. =[0 , 1] and u Agameissaidtobe ( θ,a ) nice De − i i i i 16 in . and strictly concave ) ,a a a =( is continuous in a i − i i In a nice game, since players always have unique best reply, our elimination processes will be equivalent, yielding the functional equation (4.5) S. W = Moreover, a lemma by Moulin (1984) and Battigalli (2003) ensures that we can focus on degenerate beliefs, allowing us to circumvent the measurability issue dis- k for nice games A cussed in Remark 1. We then obtain the same characterization of that we found above under the conditions of Corollary 1. (The formal statement of the lemma and the proof of the proposition are in the appendix.) ∗ with full range, any count- s Proposition 2. For any nice game, any equilibrium u ,forany k ≤∞ , T ∈ N ,and t , ∈ i ⊂ able, belief-closed T T i i k k ∗ . ]= A s ] [ [ t ,t S i i i i Under a stability condition similar to that of Nyarko (1996), Weinstein and Yildiz (2003) have shown that the maximum impact of higher-order beliefs to k ∗ ] [ . Then, ,t →∞ s shrinkstoapointas k diminish exponentially, i.e. the set A i i Proposition 2 shows that, in nice games, these stability conditions must imply that the game is dominance solvable. fi nements, we will assume that the re fi In analysis of general equilibrium re nement is non-empty at least in fi nite games. Since the existence results are often for mixed-strategies, we now extend Proposition 1 to the mixed-strategy equilibria. Using interim formulation, we de fi ne a mixed strategy as any measurable function ∗ fi → ∆ ( A ) .Amixedstrategypro T le σ : is Bayesian Nash equilibrium i ff σ i i i ¡ ¢¢ ¡ ∗ ∗ ∗ BR has full range ( )) ,σ t ⊆ σ .Wesaythat π ·| t t and for each i σ supp ( i i i i i − i ∗ ( . Clearly, under Assumption t with supp ( σ } a , there exists t )) = { for each a i ff i i i i i 1, every equilibrium on universal type space has full range. We also set ª © ¡ ¡ ¢¢ k ∗ m m ∗ ̃ ̃ ≤ | [ σ σ supp m ; t ∀ k ]= t = , t } , a { = a t A i i i i i i i i 16 We use the strict concavity assumption to make sure that a player’s utility function for any fi xed strategy pro fi le of the others is always single-peaked in his own action. (Single-peakedness is not preserved in presence of uncertainty.)

20 20 JONATHAN WEINSTEIN AND MUHAMET YILDIZ ∗ ̃ σ t the set of all actions that are played with probability 1 under by some type i fi orders of beliefs are identical to those of t whose . k rst i For any countable-action game, any (possibly mixed strategy) equi- Proposition 3. ∗ , k ≤∞ with full range, any i ∈ N ,andany t , σ librium i k k ∗ k W ] ⊆ A [ t [ σ . ,t [ ] ⊆ S t ] i i i i i i ∗ fi rst k orders of a player’s has full range and we know only the σ That is, if k is played with prob- a ∈ [ t ] ,wecannotruleoutthat W a beliefs, then for any i i i i ∗ . The proof of this result simply focus on the types with ability 1 according to σ pure actions and applies the proof of Proposition 1. 5. Robustness to higher-order beliefs In this section we will formalize our notion of robustness to higher-order beliefs and bound the set of robust predictions for arbitrary re fi nements of equilibrium. Under Assumption 1, we will obtain a sharp characterization. We start by formally fi presenting some basic de nitions. De fi nition 2. A solution concept is any mapping Σ that maps each type space T to a set Σ ( T ) of (mixed) strategy pro fi les σ with respect to T .An equilibrium , re is any solution concept Σ such that for each T and σ ∈ Σ ( T ) nement σ is a fi T . Bayesian Nash equilibrium of k , which yields all the strategy We will frequently refer to solution concepts S k k (similarly de ned). W ,and T at each T fi [ t ] for each t ∈ S ∈ t ( s les with fi pro ) De nition 3. Given a solution concept Σ and a type space T ,bya prediction of fi ( Σ ,T ) ,wemeananyformula Q with free variable s : T → A such that Q ( s ) is ∈ true for each ∈ supp ( σ ) and each σ s Σ ( T ) . Although we allow solution concepts to be mixed, we are here focusing on the deterministic predictions, the predictions that remain true for each realization. Here a prediction can be about the behavior of a particular type. In an auction, forexample,apredictioncouldbe"thetypewithlowestvaluationbidszero."A

21 FINITE-ORDER IMPLICATIONS 21 erent types, prediction can also be about a relation between the behavior of di ff e.g., "a player’s bid is an increasing function of his valuation." rst envision a researcher who subscribes to an equilibrium re nement Σ and We fi fi can observe players’ beliefs nite order k ,where k precisely up to an arbitrary but fi is large. This is clearly an unrealistically generous assumption, but we will show that, despite this, the researcher cannot make very strong predictions. ̃ ̃ T ,apair ( nition 4. T,τ ) of a model Given a model T and a mapping τ : fi De ̃ ̃ T is said to be a k T of T i ff for each t ∈ T and → t = τ ( t ) ,wehave -perturbation l l ̃ t for each = . l ≤ k t i i fi nition of k -perturbation requires that whenever our researcher believes The de fi le t in T may describe the actual situation, he cannot rule out that that a type pro ̃ fi le τ ( t ) in thetypepro T describes the situation. That is, the researcher cannot reject the perturbation without rejecting the original model. A perturbation may result from relaxing the assumption that a certain fact is common knowledge, k th order, and perhaps instead assuming that it is mutually known only up to fl ecting such a making some other assumption abo ut the higher-order beliefs. Re fi les. This is the case relaxation, the perturbed model will then have more type pro ̃ (in or in T in the coordinated attack game of Section 2. As we discussed, type k CK ˇ . Therefore, both k up to order (2) ) agrees with the common knowledge type t T i ¡ ¢ ̃ ˇ and ( T T,τ T,τ are k -perturbations of the complete information game ) for any mapping τ k . whose values are both at least Our robustness condition will require that the prediction remains valid for all perturbations de ned as above. The motivation is clear. Imagine a researcher fi T , knowing that when he is asked to validate that his model analyzing a model fi rst k orders of applies to a particular situation, he will be able to observe only beliefs. He knows that, if he can validate that T is consistent with the actual ̃ situation, T will also be consistent with the actual situation. If a prediction of ̃ T does not remain true for a perturbation , then he cannot justify T his model that his prediction applies to a particular situation, even when he could validate his model. Therefore, the researcher would like to focus on the predictions of T ̃ that are robust to alternative speci fi cations, such as T , given that he was going

22 22 JONATHAN WEINSTEIN AND MUHAMET YILDIZ fi cations as well. We de ne to apply his solution concept in those alternative speci fi robustness as follows. fi Q of ( Σ ,T ) Aprediction k -robust (to higher-order nition 5. De is said to be ̃ ̃ k -perturbation ( σ T,τ ) ,foreach σ ∈ Σ ( beliefs) T ) ,foreach s ∈ supp ( i ) ff for each , ( ◦ τ ) is true. Prediction Q is said to be robust to higher-order beliefs i ff it is Q s k< . -robust for some k ∞ -robust if it remains true in models where That is, a prediction is said to be k according to the perturbation mapping and k beliefs change at orders higher than we apply the same solution concept throughout. We could weaken our robustness ( s ◦ requirement by requiring ) to be true only if s is the "unique" solution Q τ ( σ in the perturbed model, i.e., supp τ ( t ))) = { s ( t ) } at each t ∈ T .Itwillbe ( clear that our results would remain valid under this substantially weaker require- ment. Returning again to the coordinated attack example, the prediction of no ª © CK is not robust under any (2) t T attack for the complete information game = ¡ ¢ ¢ ¡ CK ˇ T,τ with τ t is a ) k,k ( > (2) , because for each Σ nement fi equilibrium re k ¡ ¡ ¢ ¢¢ ¡ CK ˇ σ T , τ t (2) assigns -perturbation of Σ σ of T , and for the unique member k probability 1 to (Attack,Attack). Similarly, the prediction of attack is not robust. Both of the non-robustness results in this example are special cases of the up- coming proposition. It states no re fi nement can make robust predictions that are ∞ , the iterated W any more powerful than the predictions that are generated by elimination of actions that are never a strict best reply. Proposition 4. Let A be countable (or fi nite), T be any model, and Σ be an equi- u that has full range. Every ) k -robust prediction librium re Σ ∈ ( T nement with fi σ ¢ ¡ k ,T .Inparticular,if Q is robust to higher- is also a prediction of ( W Σ ) ,T of Q ∞ ,T ) . Conversely, if Q is a prediction ( W order beliefs, then Q is a prediction of ¢ ¡ k ( ,then Q is a k -robust prediction of ,T Σ ,T ) . S of Take any k -robust prediction Q of ( Σ ,T ) and any s : T → A with s ( t ) ∈ Proof. k ̃ such t ] for each t ∈ T . By Proposition 3, for each t ,thereexists [ t = τ ( t ) W u l l ̃ T .Taking i and each k ≤ l for each ) t = ,τ ( ))) = t } ) ( t ( s { and t ( that supp τ ( σ i i as a k -perturbation of T ,wethenconcludethat Q ( s ) is true. Therefore, Q is a ¢ ¢ ¡ ¡ k k Q ,T of .Take S . For the converse, take any prediction ,T W prediction of

23 FINITE-ORDER IMPLICATIONS 23 ̃ ̃ and T,τ ) of T and any s ∈ supp ( σ ) ( σ ∈ Σ ( k T ) .For also any -perturbation k k k T ( s S ∈ τ is a Q ,showingthat ] .Since [ τ ( t )] = S ) [ t ◦ S )) t ( τ ( s , ) t ( τ each ∈ ¢ ¡ k ,T is true. Therefore, ,thisshowsthat Q ( s ◦ τ ) -robust Q is a k prediction of S ( Σ ,T ) . ¤ prediction of For nice games, using Proposition 2, we obtain a characterization: u ) ∈ Σ with σ For any nice game, any equilibrium re Σ ( T Proposition 5. nement fi that has full range, any model T ,andany k< ∞ , a prediction Q of ( Σ ,T ) is k - ¢ ¡ k ,T . robust if and only if S is a prediction of Q While the above propositions yield strong bounds for robust predictions, they fi leave number of issues unresolved. Firstly, they assume that the re nement is non- empty on universal type space. But most existing existence results for re fi nements 17 Secondly, our robustness condition above requires that the nite models. fi assume researcher does not restrict the set of models a priori. In particular, for simplicity, our proof uses the universal type space as one of possible models. Although we fi nd this a reasonable condition, some may want to restrict the set of models by fi at. For example, it is customary in economics literature to assume that there is a common prior, and one may want to impose the common prior assumption on hout a common prior all together. One possible models, ignoring the models wit fi may also want to focus on small models, such as nite type spaces, for perhaps to assure existence. Finally, our lower bound for countable-action games is in terms ∞ , which may be small in certain games, weakening our results. We will next W of show that these potential issues are not crucial for our results. Indeed, requiring that the predictions remain valid if there is also very small misspeci fi cation in lower-order beliefs, we will obtain a characterization of robust predictions in terms fi nite models of rationalizability, even when the set of models are restricted to be with common prior. Formally, a fi nite model T is said to have a common prior (with full support) if 0 × T ∆ ( Θ × T ) such that supp ( p )= Θ there exists a probability distribution p ∈ 0 Θ ⊆ Θ and κ . In the remainder = p ( ·| T ×{ t }× T ∈ ) for each t Θ for some t i i i − i i 17 Simon (2003) shows existence of equilibrium with non-measurable strategies for the union of countable type spaces, but he also shows that there may not exist an equilibrium with measurable strategies in universal type space for some payo ff functions. We do assume that the strategies are measurable for ease of exposition, but that as sumption does not play any role in our results.

24 24 JONATHAN WEINSTEIN AND MUHAMET YILDIZ fi of the section we will focus on the nite models with a common prior. We now imagine that a researcher can observe fi nitely many orders of beliefs with some small noise. We focus on the case that the noise is small in the sense that, for l ̃ that the researcher nds possible converge to fi nite-order beliefs t l each ,the k ≤ fi i l in the sense of "convergence in distribution", i.e., in weak the observed beliefs t i l is a probability distribution.) To do this, we consider t topology. (Recall that i fi nite-order beliefs that metrizes the weak topology. The an arbitrary metric d on is taken to measure the distance according to the test the re- arbitrary metric d l , the researcher , l ≤ k searcher employs. Given the observed or estimated beliefs, t i ¡ ¢ l l l ̃ ̃ d with t ,t possible (or cannot reject ≤ l for all k ≤  fi t nds the set of beliefs i i i dence) for some 0 ,where  is meant to mea- fi them at a particular level of con > sure the precision of the researcher’s observations. Again, we focus on the limit → and k →∞ .  0 ̃ ̃ Amodel ( of T,τ ) is said to be ( ,k ) - perturbation De T i ff (i) fi T is fi nite nition 6. ̃ ̃ τ → τ T is such that for each t and T t = : ( t ) , and has a common prior, and (ii) ¢ ¡ l l ̃ ,t l . ≤ for each k ≤  t d we have i i -robust fi Q of ( Σ ,T ) is said to be ( ,k ) Aprediction i ff for each ( ,k ) - De nition 7. ̃ ̃ T,τ ) of T ,foreach σ ∈ Σ perturbation ( ( ) ,foreach s ∈ supp ( σ ) , Q ( s ◦ τ ) is true. T Prediction is said to be robust i ff it is ( ,k Q -robust for some > 0 and k< ∞ . ) On the one hand, we strengthen our robustness requirement by requiring  to be positive but arbitrarily small, instead of setting it to zero as in the previous de fi nition. On the other hand, we weaken our condition substantially by ignoring the perturbations that do not lead to a nite model with a common prior. In fi particular, the universal type space is no longer accepted as a possible perturbation. The next result, proven in Yildiz (2005, Proposition 3), will help us to characterize the robust predictions. A is fi nite. Under Assumption 1, for any fi nite model Assume that Lemma 2. 0 : A ,foreach > → and k< ∞ ,there T fi le s T , any rationalizable strategy pro ̃ ̃ ,k ) -perturbation ( exist a T,τ ) of T ,where ( T is fi nite and has a common prior, ∞ s [ τ ( t )] = { ( t ) } for each t ∈ T . such that S This result immediately yields a sharp characterization of the robust predictions.

25 FINITE-ORDER IMPLICATIONS 25 A Proposition 6. nite. Under Assumption 1, for any equilibrium is Assume that fi Σ nement fi nite models with a common prior, any fi nite fi re that is non-empty on ,andany k< ∞ model Q of ( Σ ,T ) is robust if and only if Q is a T , a prediction ∞ ,T ) . ( S prediction of Under the stronger richness assumption of Assumption 1, this result provides a characterization of robust predictions, which addresses all of the issues discussed above. Firstly, we only assume that fi nite models with a Σ is non-empty on the common prior. Since it is customary to prove such an existence result whenever fi fi nements. are nement is proposed, this assumption allows most equilibrium re nite models with a common prior. Secondly, our perturbation considers only the fi Hence, the non-robustness implied by our characterization is not due to models that are usually assumed away by economists. Therefore, it is immune to the possible critique for earlier results based on models without a common prior, discussed in Section 2. Finally, we have a characterization in terms of usual rationalizability, k is a W muting the hope of obtaining positive robustness results in cases in which small set. We will now revisit the coordinated attack problem of Section 2 and illustrate how the methodology of global games can be extended to more general information structures and why the results will critically rely on the assumptions made on the information structure. (Izmalkov and Yildiz (2006)) . In the coordinated attack problem of Example 2 ,where = θ + εη i observes a noisy signal x Section 2, assume that each player i i θ ,η ,with ) is independently distributed from η ( 2 1 ¡ ¢ (5.1) Pr x >η | ∀ 6 η = q ( ) i = j i i i j 18 , is the probability according to player i , 1) ,where Pr for some constant q ∈ (0 i

26 26 JONATHAN WEINSTEIN AND MUHAMET YILDIZ / =1 q − 1 . Global games literature focuses on this case. Here, 2 measures 2 q / according to i . Using the techniques and the mild the level of optimism of j 0 is ε> assumptions of Carlsson and van Damme, one can easily check that, when ∗ x 6 =5(1 − q ) , there is a unique rationalizable action s ) ( ,given x small, for each i i i by ( Attack if x ) > − 5(1 q i ∗ )= x ( s i i . ) < 5(1 − q x No Attack if i In the complete-information gam e, Attack is risk-dominant when θ> 5 / 2 ,and No Attack is risk-dominant when θ< 5 / 2 . Under the common-prior assumption (i.e. when / 2 ), players play according to risk dominance. In the general =1 q ,wecan model, however, risk-dominance does not play any role. Given any x i q of optimism su ffi ciently make Attack uniquely rationalizable by choosing the level q of optimism high, or make No Attack uniquely rationalizable by choosing the level ffi ciently low. Notice that, when ε is very small, the value of q has a very small su ¡ ¢ − − x η = ε η and on players’ beliefs, and the players’ beliefs x impact on j i j i ε 0 converge to that of common knowledge at all orders as , but equilibrium → behavior does not. θ as the vulnerability of economy, Morris and Shin (1998) have applied Taking this idea to the currency-attack problem (where there is a continuum of players). They have illustrated that, attacks are closely related to the vulnerability of econ- omy, as the likelihood of an attack is increasing with θ .Theyalsonotedthat,in their model, investor sentiments do not play a role, which were given a prominent role in previous informal arguments based on multiple equilibria of the complete information game. In the above example, however, there is a precise measure concerning investor sentiments, namely q − 1 / 2 , that determines belief in others’ con fi dence in the economy. It plays an intuitive role similar to the vulnerability of the economy. Attack becomes more likely if the players become more optimistic or the economy becomes more vulnerable. That is, considering more general informa- tion structures, we can develop insightful models as in the global games literature, but focusing on their particular models which lead to risk-dominance is a very restrictive way of doing that. Now, under the original assumptions of Carlsson and van Damme, despite the degenerate case of multiplicity in the complete-information game, there is an open

27 FINITE-ORDER IMPLICATIONS 27 19 set of nearby types that can only play risk-dominant equilibrium. The global games literature would then argue that we ignore the complete-information case, even if that case is consistent with the researcher’s observation of the situation. Nevertheless, when the complete-information case is consistent with his observa- tion, there will also be an alternative open set of types that are consistent with his observation, leading to the opposite outcome of (Attack,Attack) as the only possibility–as in the above example. Then, the researcher will not be able to check whether the conditions assumed in the information structure of Carlsson and van fi ed even if he considers the complete-information to be Damme (1993) are satis degenerate. To put it di ff erently, while the global games literature criticizes the multiplicity arguments for relying on simplifying common-knowlegde assumptions that we cannot check, our example shows that the same applies to their results. Their conclusions also critically depend on their simplifying assumptions on the noise structure. More broadly, as Carlsson and van Damme (1993) and Kajii and Morris (1997) illustrate, by considering only some of the information structures that lead to a set oflower-orderbeliefs,onemaybeabletomakesharperpredictions. Theanalysisof such structure would be of great interest, but it is beyond the scope of this paper. Our paper shows that the resulting predictions will always critically depend on the assumptions built into these structures, and we cannot verify those assumptions and the conclusions with limited knowledge of the situation. 6. Without Full-Range Assumption For ease of exposition, we have so far focused on equilibria with full range. Our full range assumption allowed us to consider large changes in higher-order beliefs. A researcher may be certain that it is common knowledge that the set of parameters are restricted to a small subset, or equivalently, the equilibrium considered may not vary much as the beliefs about the underlying uncertainty change. We will now present an extension of our main result to such cases. (For illustrations of proofs,seeourearlierworkingpaper.) 19 When a type has unique rationalizable action , this action will be uniquely rationalizable for all types in an open neighborhood of this type (with respect to the product topology in the universal type space).

28 28 JONATHAN WEINSTEIN AND MUHAMET YILDIZ k Local Rationalizability ×···× B . For any ⊂ A ,de fi ne sets S B , [ B ; t ] i 1 n i k [ B ; t T ] , i ∈ N , k ∈ N , t , as before but set by setting ∈ S i i i i 0 0 [ B t [ W B . ; B ; t ]= ]= S i i i i i fi ne the Unlike before, the new sets can become larger as k increases. Hence, we de limit sets by ∞ ∞ [ \ m ∞ S ]= ] [ B t ; t ; B [ S , i i i i k =0 m k = ∞ ∞ [ \ m ∞ ]= t ; . B [ W ] t [ B ; W i i i i =0 m = k k ∗ , if the game has countable action spaces, s Proposition 7. For any equilibrium then ∗ u k ∗ k ∗ u k ); t i,k,t ] ⊆ A [ ∀ [ s s ,t ]( ] ⊆ S ); t [ s ( ( T T ); W i i i i i i i ∗ B s if the game is nice, then with notation of Proposition 2, for any ⊆ ( T ) , £ ¢ £ ¤ ¤¡ u k k ∗ k ∗ ˆ ˆ ˆ S s [ ,t ( ]= S t T ); t s . A ⊆ B t i,k, ; ∀ i i i i i i i ∞ ∞ W Replacing S with their local versions, this proposition establishes that and ∞ provided by Propositions 4 and 5 remains valid even if one does A the bounds for not assume that the equilibrium has full range. Then, using this result instead of Propositions 1 and 2, we can obtain similar bounds to those of Propositions 4 and ∞ ∞ and with S W 5 without assuming full range assumption, but instead replacing their local versions for some set of actions which are known to be played by some types. The last statement in the proposition implies that, for nice games, even the slight changes in very higher-order beliefs will have substantial impact on equilibrium behavior, unless the game is locally dominance-solvable. There are important games in which a slight failure of common knowledge assumption in very high orders leads to substantially di ff erent outcomes–as we show next. 7. Applications In this section, we will provide three applications of our results. First, we will show that in Cournot oligopoly with su ffi ciently fi rms, even a slight relaxation of the common-knowledge assumption will preclude us from making any prediction

29 FINITE-ORDER IMPLICATIONS 29 rm will produce more than the monopoly beyondtheelementaryfactthatno fi outcome. Second, we will sho w that an equilibrium (or rationalizable) strategy if and only if is continuous with respect to the product topology at a given type that type has a unique rationalizable action. Third, we will show that, under our perturbation, there is a rob y if the game is dominance ust equilibrium if and onl solvable. ciently many 7.1. rms, Cournot Oligopoly. In a Cournot oligopoly with su ffi fi any production level that is less than or equal to the monopoly production is 20 Then, our Proposition 2 implies rationalizable (Bernh eim (1984), Basu (1992)). that a researcher cannot rule out any such output level as the output equilibrium fi rm no matter how many orders of beliefs he speci fi for a es, assuming the set of payo ff parameters is rich. Using Proposition 7, we will now show that the richness assumption is not needed for this conclusion. Even a slight doubt about the payo ff s in very high orders will lead a researcher to fail to rule out any outcome that is rm’s equilibrium output. More broadly, this less than the monopoly outcome as a fi establishes that our non-robustness results apply to some very important games in economics, even without our richness assumptions. Consider fi rms with identical constant marginal cost c> 0 .Simultaneously, n where ) at cost θ = Q q c and sell its output at price P ( Q ; q i rm fi each produces i i P ̄ θ fi xed q is the total supply. For some , we assume that Θ is a closed interval i i ¢ ¡ ¢ ¡ ª © ̄ ̄ ̄ ̄ 0 P Θ 0; = θ ∈ > θ , P θ · ; 6 θ . We also assume that is strictly decreasing with ¢ ¡ ̄ P Q ; θ =0 . Therefore, there exists a unique lim when it is positive, and →∞ Q ́ ³ ¡ ¢ ̄ ̄ ˆ ˆ ˆ ; = c .Weassumethat,on [0 , Q Q ; , P ] · θ is continuously θ such that Q P 0 00 ff P twice-di erentiable and < + QP . 0 It is well known that, under the assumptions of the model, (i) the pro fi t function, ¡ ¢ ̄ ; ; (ii) the unique θ q = q ( P ( q,Q + Q ) − c ) , is strictly concave in own output q u ∗ to others’ aggregate production ( Q is strictly decreasing on Q ) q best response i − i − ∗ ˆ λ< ); (iii) for some λ ≤ 0 /∂Q with slope bounded away from 0 (i.e., ] Q , [0 ∂q − i ¡ ¡ ¢¢ ¢ ¡ ∗ CK CK ̄ ̄ , t s , is unique and symmetric (Okuguchi θ θ t equilibrium outcome at 20 Borgers and Janssen (1995) show that if we replicate both consumers and the fi rms in such a way that the cobweb dynamics is stable for the resulting demand and supply curves, then the Cournot oligopoly will be dominance-solvable. In that case, by Proposition 2, equilibrium outcomes will not be sensitive to higher-order beliefs.

30 30 JONATHAN WEINSTEIN AND MUHAMET YILDIZ is a payo θ ff -relevant parameter and Suzumura (1971)). We will also assume that ∗ is a continuous and strictly increasing function Q ; θ ) ( q in the following sense: − i ¢¢ ¡ ¡ ¢ ¡ CK ∗ ̄ ̄ θ . t θ =( , − 1) s where Q n Q at of θ − i − i j ̄ n< ∞ such that for any Lemma 3. In the Cournot oligopoly above, there exists ¢¢ ¤ ¢¢ ¡ ¡ ¡ ¡ £ n CK ∗ CK ∗ ̄ ̄ ⊂ 0 > with ,wehave A ,s θ +  − θ t t n> ̄ and any B = s n 1 1 1 1 £ ¢¤ ¤ £ ¡ M CK ∞ ̄ S = 0 ,q θ B ( t ∀ i ∈ N ) , ; i ¡ ¢ ¢¢ ¡ ¡ ∗ CK M ̄ ̄ where q is the monopoly output under · ; and s θ P θ is the unique t ¢ª ¡ © CK ̄ θ . equilibrium of the complete information game t This is a straightforward extension of a result by Basu (1992) for rationalizability to local rationalizability. The proof is in the appendix. Together with Proposition 7, this lemma yields the following. ¤ £ ̄ ̄ Θ − ε, In the Cournot oligopoly above, let θ + ε Proposition 8. for arbi- = θ ∗ on the universal type space, s ε> 0 . Then, for any equilibrium trarily small ¤ ¡ £ ¢¤ £ ∞ M CK ∗ ̄ A ,t = s 0 ,q ∈ θ ( ∀ i , N ) i i ¡ ¢ M ̄ q where P θ . · is the monopoly output under ; q ,by(i)above,wehaveanice Sincewecanputalargeupperboundon Proof. ∗ ( T ) as in Lemma 3. Hence, Lemma ⊂ s game. By the hypothesis, there exists B 3 and Proposition 7 imply ¢¤ ¤ £ ¢¤ ¤ ¡ £ £ ¡ £ CK ∗ ∞ CK ∞ M M ̄ ̄ ,t = , t s ; A B ,q 0 θ θ S ⊆ ⊆ ,q 0 i i i i yielding the desired equality. ¤ ffi ciently many fi rms, any equilibrium pre- Our proposition suggests that, with su diction that is not implied by strict dominance will be invalid whenever we slightly deviate from the idealized complete information model. To see this, consider two ̄ fi dent that it is common knowledge that θ = researchers. One is con θ .Theother is slightly skeptical: he is only willing to concede that it is common knowledge ̄ ̄ ̄ ̄ ̄ ̄ θ θ − ≤ ε andagreeswiththe k th-order mutual knowledge of that = θ θ .Heis an arbitrarily generous skeptic; he is willing to concede the above for arbitrarily small ε> 0 and arbitrarily large fi nite k . Our proposition states that the skeptic nonetheless cannot rule out any output level that is not strictly dominated.

31 FINITE-ORDER IMPLICATIONS 31 It is well-known that some equilibria of some 7.2. Continuity of equilibrium. games are discontinuous in the universal type space under the product topology. For example, if we combine the e-mail game of Rubinstein (1989) with the com- plete information case, there will be one continuous equilibrium, prescribing No Attack everywhere, and one discontinuous equilibrium, prescribing Attack only in the complete information case. After all, best response of a single player may be nite. Similarly, a Nash equilibrium may be discontinuous discontinuous when A fi is function of complete information games, while the Nash equilibrium correspon- dence is generically lower-hemicontinuous on the space of complete-information games. Now we will show that, in nice and fi nite-action games every equilibrium strategy will be discontinuous at every type with multiple rationalizable actions. on A .(When A is will be equivalent nite, d fi We consider an arbitrary metric d A A m is said to ff i A converge ) a ∈ to some to the discrete metric.) A sequence ( a N m ∈ m is A .When m>k < ( a for each ,a ) > d such that k ,thereexists for each 0 A m = a for m>k . fi es to the requirement that a fi nite this simpli nition 8. fi le s is said to be continuous (with respect to product fi De A strategy pro ¢ ¡ ̃ les fi of type pro [ m t ] for each sequence i t topology) at ff ∈ N m ¤ ¢ ¤ £ ¡ £ k k ̃ ̃ m ] [ → s ( t ) t . m ⇒ ] s → t [ ∀ k t ∗ Proposition 2 implies that if an equilibrium s with full range is continuous at ∞ ∗ ) t [ , yielding the following discontinuity result. ]= { s } ( t S t ,then ∗ u Proposition 9. s For any nice game, every equilibrium with full T → : A for which there are more than one range is discontinuous at each type pro fi le t les. In particular, if a nice game possesses an equilibrium fi rationalizable action pro ∗ that is continuous and has a full range, then the game is dominance solvable. s ∗ ∞ with ∈ S with full range and any a t ] such that t [ s Proof. Take any equilibrium ∗ m m ̃ ̃ = a . Then, for each k ,thereexists [ t ( k ] such that t t ) [ k ]= t 6 for each m ≤ k s ¢ ¡ ¡ ¢ ∗ ∗ ∗ ∗ ̃ ̃ .But,by ) s t ( t ( . Clearly, ) s 6 a s doesnotconvergeto = = ] k [ t ] k [ t and s m m m m ̃ ̃ t t , and hence [ k [ k ] → t ]= as m and each k>m , de t nition, for each fi ∗ is discontinuous at t . ¤ k →∞ . Therefore, s

32 32 JONATHAN WEINSTEIN AND MUHAMET YILDIZ Under a stability condition, Nyarko (1996) shows that equilibrium is continuous on universal type space. Our result then shows that his condition implies that the game is dominance-solvable. Considering a class of simple dominance-solvable gamesthatsatis es the stability condition of Nyarko (1996), Morris (2002) shows, fi among other things, that continuity of equilibrium is not uniform over these games. That is, even in dominance-solvable games, we may need to pay special attention to how we specify the higher-order beliefs. One can obtain a discontinuity result for countable-action games at each type ∞ , similar to the previous proposition. For mixed-strategy equilib- ] | > 1 [ t with W | ria, one can obtain similar discontinuity results under substantially weaker conti- nuity requirements (see our working paper). We will now obtain a characterization for all rationalizable strategies in fi nite-action games. is fi nite. Under Assumption 1, a rationalizable Proposition 10. A Assume that u ˆ ˆ fi nite type pro fi → is continuous at a t if and only if A t has le fi strategy pro s : T le ̄ ̄ ¤ £ ∞ ̄ ̄ ˆ =1 . This characterization remains t S a unique rationalizable action, i.e., CPA ∈ = { t | t , T T is fi nite and has a common prior } . s T is intact if the domain of ∞ S Proof. The"if"partfollowsfromthefactthat is upper-semicontinuous (Dekel, Fudenberg, and Morris (2004)). To prove the "only if" part, take any rationalizable ¢ ¤ ¡ £ ∞ ˆ ˆ . By Lemma 2, there exists a = t a 6 with t s S strategy pro fi le s and any a ∈ ∞ ˆ } [ t m ]] = { a [ .Since s ( t [ m ]) = a → [ sequence of types t with s ( t [ m ]) ∈ S m ] t ¢ ¡ ˆ t . The last statement follows from , s ( t [ m ]) does not converge to s for each t [ m ] CPA in Lemma 2. ¤ ] ∈ T the fact that [ m t Proposition 10 establishes that, at each fi nite type, either there is a unique rationalizable action and all rationalizable strategies are continuous (in fact, lo- cally constant) at that type, or there are multiple rationalizable actions and all rationalizable strategies are discontinuous at that type. As discussed in Section 2, this raises a serious di culty in usefulness of continuity arguments to re fi ne ffi equilibrium (or rationalizability). Whenever there is a possibility of re fi ning ra- tionalizability, all of the rationalizable strategies are discontinuous at the relevant type, and imposing continuity leads to the empty set. Note that generically there exists a unique rationalizable outcome, and hence all rationalizable strategies are continuous at generic types, where there is no need for a re fi nement.

33 FINITE-ORDER IMPLICATIONS 33 Robustness of equilibrium. Kajii and Morris (1997) introduced an ex ante 7.3. notion of robustness of equilibrium to incomplete information. We will now inves- tigate how the results will change if we consider an analogous interim notion of robustness for equilibrium, or drop the common-prior assumption in their formu- lation. Following Kajii and Morris (1997), we will assume that the set of payo ff N ,thereexists fi fi v : A → R pro les is not restricted, so that for each payo ff le pro ( θ, · )= v . With our notation, for pure strategy equilibria, their u θ such that ned as follows. robustness can be de fi fi (Kajii and Morris (1997)) . An equilibrium ˆ a ∈ A of a complete- De nition 9 ¡ ¢ª © CK ̄ is said to be θ robust to incomplete information i ff for information game t every 0 ,thereexists ε> 0 such that for each fi nite T with common prior δ> ¡ ª¢ ¢¢ ¡ ¢ ¡ ¡© ̄ ̄ · )= u ( θ, · )= u θ, ( , u ≥ ε i θ, · ,κ θ, · − =1 ∀ 1 u θ,t such that ) | p ( p i i t i i i ∗ ∗ )) = of p ( supp ( σ ( t with { ˆ a } ) ≥ δ . T σ there exists an equilibrium T That is, if the common prior of puts high probability on the event that the payo ff s are as described in the complete-information game and everybody knows ff s, then T will have an equilibrium in which most of the types will play his payo according to the original equilibrium. Here, there is no restriction on players’ interim beliefs, other than what the restriction on the prior implies. This de nition fi envisions a researcher who believes that his complete information model is the true model with high probability according to the prior of the correct model. As we discussed before, we are interested in the robustness in the interim stage when we do not have any information about the ex ante stage, which the researcher fi ne interim robustness, constructs to model the interim beliefs. Accordingly, we de again for pure strategy equilibria of complete information games, as follows. ¡ ¢ª © CK ̄ θ of a complete-information game fi nition 10. t De ˆ a ∈ A An equilibrium is said to be interim robust to incomplete information i ff there exists ε> 0 and ¡ ¢ª © CK ̄ θ ,thereexistsan T,τ ) of k< t ( ε,k such that for each ) -perturbation ( ∞ ¡ ¡ ¡ ¢¢¢¢ ¡ ∗ CK ∗ ̄ σ T of with supp a t nite and has fi is = { ˆ τ } ,where T θ equilibrium σ a common prior. In this de fi nition, we keep their requirement that the perturbed game has a com- mon prior, but we do not require the perturbed game to assign a high probability

34 34 JONATHAN WEINSTEIN AND MUHAMET YILDIZ to the original model. Instead, we require only that the perturbed model has a type that has similar beliefs in the interim stage. Also, instead of requiring that most of the types play according to the original equilibrium, we only require the type with similar beliefs to do so. Kajii and Morris (1997) showed that, although a unique Nash equilibrium need not be robust to incomplete information, if there is a unique correlated equilib- ,...,p ) -dominant equilibrium with p ( rium, then it will be robust. Moreover, any n 1 ··· + p < + 1 ,suchasarisk-dominantequilibrium,isrobust.Thesearestrin- p n 1 gent su ffi cient conditions, but they yield existence of robust equilibria in many cases, such as generic two-player, two-action games. In contrast, we will now show that existence of interim robust equilibrium is equivalent to dominance-solvability. Therefore, when we do not impose that the prior of the correct model assigns high fi probability to the actual case, there will be signi cantly fewer robust equilibria, even if we impose stringent conditions on the beliefs of the perturbed type. ̄ be fi nite and let Let θ have generic payo ff s. Under Assumption Proposition 11. A ¢ª ¡ © CK ̄ has an interim robust equilibrium ˆ a if and only if there is a unique θ t 1, ¡ ¢ CK ̄ θ . rationalizable action pro t fi le for ∞ is upper-semicontinuous, so S Proof. The"if"partfollowsfromthefactthat £ ¡ ¢¤ ∞ ∞ CK ̄ ]= [ t { ˆ a } in a neighborhood t θ = { ˆ a } ,wehave S that whenever S ¡ ¢ CK ̄ θ . Then, when -perturbation ε ) k large, for every ( ε,k is small and t of ¢¢¤ ¡ £ ¡ ∗ ∞ CK ̄ ,wecon- T be any equilibrium of a θ t = { ˆ τ } . Letting σ , ) ( S T,τ ¢¢¢¢ ¡ ¡ ¡ ¡ ∗ CK ̄ t τ θ . To prove the "only if" part, assume = { ˆ a } clude that supp σ ̄ ̄ © ¢ª ¡ £ ¡ ¢¤ ∞ CK CK ̄ ̄ ̄ ̄ ˆ a of t > 1 , and take any equilibrium θ t .Thereexists θ S that ¢¤ ¡ £ ∞ CK ̄ ,there ε> θ ∞ with a 6 =ˆ a . Then, by Lemma 2, for each t 0 and k< ∈ S a ¢¢¤ ¡ ¡ £ ¢ª ¡ © CK ∞ CK ̄ ̄ S . τ θ such that θ = { a } t ( t ) exists ) -perturbation ε,k ( T,τ of ¢¢¢ ¡ ¡ ¡ CK ̄ θ must assign zero probability to σ T of σ τ Then, for any equilibrium t , ¤ ˆ ˆ a is not interim robust. . Therefore, a What happens if we drop the common-prior assumption in Kajii-Morris de fi n- ition of robustness, keeping their (prior, rather than interim) notion of perturba- tion? To answer this question, let us modify De fi nition 9. ¡ ¢ª © CK ̄ θ t A of a complete-information game De fi nition 11. An equilibrium ˆ a ∈ is said to be weakly robust to incomplete information without CPA i ff there exists

35 FINITE-ORDER IMPLICATIONS 35 fi nite T ,de fi ned by κ 0 ε> ≡ p ) ( ·| t and such that for each for priors ( p ) ,...,p n i i 1 t i ª¢ ¢¢ ¢ ¡ ¡ ¡ ¡© ̄ ̄ θ, · u )= ( u )= · θ, ( =1 · · θ, θ, for ,κ ∀ j ≥ 1 − ε ) θ,t u | u ( p such that j j j i t j j ∗ ∗ assigns positive of T and t ∈ T such that σ σ i each , there exist an equilibrium . at ,and t is assigned a positive probability by some p probability to t ˆ a i nition, fi Above, we drop the common-prior assumption in the Kajii-Morris de making robustness more stringent. We also weaken the robustness condition signif- a is played in equilibrium with positive probability icantly by simply requiring that ˆ ˆ a according to some player, as opposed to being the pure equilibrium outcome with high probability. We show that the impact of dropping the common-prior assump- tion is so strong that now robustness roughly implies that we have a dominant- strategy equilibrium. This is because without a common prior, the restrictions on prior beliefs have no implications for interim beliefs beyond second order. , ˆ a beaNashequilibriumof ) , 2 } ,let ˆ a =(ˆ a Proposition 12. For N = { 1 2 1 © ¡ ¡ ¢ª ¢ª © CK CK ̄ ̄ is a dominant strategy in t a ˆ θ θ .Then, ˆ a is where neither of t i not weakly robust to incomplete information without CPA. fi ne, for arbitrary ε ,amodel T as in De fi Proof. We will de nition 11 which will not is not a ˆ a ,since i possess any equilibrium with the desired properties. For each i ̃ and ̃ a .Let such that u ( ̄ a , ) a ) >u (ˆ a , ̃ a a dominant strategy, there exist ̄ − i i i − i − i i i i s of the other a is a strictly dominant action and the payo ff ̃ be a state at which θ i i 21 0 00 ̄ t ,withpriorbeliefs ,t = N ,t i ∈ } , { .De fi ne T with T j are as in player θ i i i i × p ,p T ) ( Θ × T given in the following tables for each triple in 1 1 2 2 00 0 00 0 00 0 ̄ t t t t t t t θ t t θ θ 2 1 2 2 2 2 2 2 2 2 2 2 2 , 0,0 0,0 0,0 t ε 0,0 0,0 0,0 t 0,0 ε − ε − 1 0,0 t 1 1 1 ε ε 0 0 2 2 0 ε 0,0 , t 0,0 0,0 0,0 0,0 t ε − t − 1 , 0,0 ε 0,0 1 1 1 2 2 ε ε 00 00 00 0,0 0,0 , 0,0 0,0 0,0 0,0 0,0 t 0,0 t t 1 1 1 2 2 ©¡ ¢ ¡ ¢ª 0 0 ̄ ̄ = ne F Now, de θ,t ,t ,t fi θ,t saregivenas players’ payo ff F , .On 2 1 1 2 0 ̄ and t put zero t θ s, i.e., both types , and each player knows his own payo ff in i i es the condition in fi satis T , .Since p ε ( F )= p − ( F )=1 θ = θ probability on 2 i 1 ∗ fi nition 11. However, we will show that there does not exist any equilibrium σ De 21 Notice that p and p have common support, and hence our result would not change if we 1 2 imposed the common-support assumption.

36 36 JONATHAN WEINSTEIN AND MUHAMET YILDIZ ˆ where a p is played with positive probability anywhere on the common support of 1 ∗ 00 and .First,eachtype t p = puts probability 1 on θ . Take any equilibrium θ σ . i 2 i 00 0 ,type t ̃ a t with probability 1. Now, type must play θ Hence, by de fi nition of i i i i ¡ ¡ ¢ ¢ 00 ̄ θ,t ε/ (2 ε puts probability on ,t 2 +1) / ε +1) on 1 θ (2 . and probability i − i − i − 0 00 ̃ . Then, , who plays puts nearly probability 1 on type a t t ε When is small, type − i − i i 0 t , and hence a yields higher expected payo ff than ˆ ̄ under equilibrium beliefs, a i i i puts zero probability on ˆ . Everywhere in the common support of p ,one and a p 2 1 i 0 00 ˆ or t a ,and , which put zero probability on of the types is either of the form t i i i ∗ ¤ puts zero probability on ˆ a . hence σ Oyama and Tercieux (2005) extend Proposition 12 to players. They show that n if an equilibrium is weakly robust to incomplete information without CPA, then n − 1 players play dominant strategies. As mentioned above, the extreme lack of robustness in these results stems from the fact that without CPA, restrictions on priors do not put any restriction on beliefs at second order and higher. Then, 1 is Proposition 1 suggests that robustness of an equilibrium would require that W singleton, leading to Proposition 12. Oyama and Tercieux (2005) also consider a weaker robustness notion for equilibrium without CPA, combining our approach of bustness of Kajii and Morris (1997). They restricting higher-order beliefs with ro consider perturbations where each player’s prior puts high probability on the event fi rst k that the fi ed, for arbitrarily large k . Consistent orders of beliefs are as speci with Proposition 1, they show that there is no robust equilibrium in this very weak ∞ 1 > | . W | sense whenever Conclusion 8. Most predictions in economics are based on some equilibrium re nement, applied fi to speci fi c models. In this paper, we recognize that, when we need to check whether such a prediction applies to a particular situation, we could only know fi nitely many orders of players’ interim beliefs. There are many models compatible with this partial information. We ask which predictions remain valid under our limited information, in the sense that we could make that prediction independent of which compatible model is chosen, given that we will apply the same re fi nement at each model. We show that predictions remain valid only if they are true for all strategies that survive iterated elimination of actions that are never a strict best reply. For

37 FINITE-ORDER IMPLICATIONS 37 nd a characterization: a prediction remains valid if and only generic payo ff s, we fi if it is true for all rationalizable strategies. Therefore, equilibrium re fi nements will ns only when we have information about be useful in generating extra predictio fi nite hierarchy of beliefs. We prove this by establishing that every theentirein cation of higher-order equilibrium re fi nement has to be highly sensitive to speci fi beliefs when there are multiple rationalizable actions. This sensitivity is what drives our result. We also show that our result remains intact when we restrict our nite) type spaces, or impose the common-prior assumption. fi attention to small (i.e. Appendix A. Omitted Proofs For any nice game, for any Lemma 4 t (Moulin (1984) and Battigalli (2003)) . , i , , k i 1 − k k a and any t for ] , there exists a pure strategy ˆ s ] t S ˆ s [ such that ( t ∈ [ ) ∈ S i i i i − i − i − − i i − each t and − i ( π ( ·| t . , ˆ s } a )) = { BR i − i i i k k a ProofofProposition2. For any such ∈ [ t s ]= W S ˆ [ t , by Lemma 4, there exists ] i − i i i i i − 1 k 1 − k s ˆ that a S .Since ) [ · ]= S ) · ( s ˆ , · ] and ∈ t is a strict best reply against π ( ·| [ i − i i − i − i − i κ and has countable support, P ( ·| t κ , ˆ s , the probability distribution induced by ) i − t t i i i ˆ s on Θ × L × A , has a countable support: i i − − supp P ( ·| t , ˆ s . } )= { ( θ,l, ˆ s κ supp ( θ,l,h )) | ( θ,l,h ) ∈ i t i − i − i ̃ (not necessarily in T ∈ t Hence our proof of Proposition 1 applies. That is, there exists i i ¢ ¡ m m ∗ ̃ ̃ t T and for each t s = t ) such that m ≤ k , yielding the equality above. ¤ = a i i i i i i n | 1+1 / | λ ̄ ,where λ is as in (ii). Let ProofofLemma3. be any integer greater than 0 n 0 0 0 0 0 for some q ̄ q q with q , < ̄ q , .By(ii),forany ] ̄ Take any n> ̄ n . By (iii), B =[ q £ ¡ ¢¤ k CK k k n ̄ B =[ q t ; θ k> 0 , S q ̄ ,where , ] ́ ³ ³ ́ ∗ k k k ∗ 1 − k − 1 ( q q 1) . and − n ( n − 1) ̄ q q = = q q ̄ k k ∗ k k ∗ ̄ n − 1) q , q 1) Q ,sothat ≡ ( n − 1) ̄ q ≡ ,and Q ( =( n − Q ne fi De ́ ³ ́ ³ k 1 k − 1 ∗ − k k ∗ ̄ ̄ Q and Q . Q = Q = Q Q k ∗ is strictly less than − 1 .Hence Q decreases with Since ( n − 1) λ< 1 ,theslopeof Q ∗ k ̄ ̄ k fi nite Q and becomes 0 at some k ,and k and takes value Q increases with (0) = £ ¤ ¡ ¢¤ £ n M M k CK ̄ ̄ ̄ q n ( − 1) k S .Thatis, +1 for each k> at k . Therefore, θ t 0 ,q B = ; £ ¢¤ ¤ £ ¡ n ∞ CK M ̄ θ = 0 ,q S . ¤ B ; t

38 38 JONATHAN WEINSTEIN AND MUHAMET YILDIZ References [1] Aumann, Robert (1987): “Correlated Equilibrium as an Expression of Bayesian Rationality,” Econometrica , 55, 1-18. ass of rationalizable equilibria of oligopoly [2] Basu, K. (1992): “A characterization of the cl games,” 40, 187-191. Economics Letters nite, dynamic games with complete informa- [3] Battigalli, P. (2003): “Rationalizability in in fi , 57, 1-38. tion,” Research in Economics [4] Battigalli, P. and M. Siniscalchi (2002): “Strong Belief and Forward-Induction Reasoning,” Journal of Economic Theory 106, 356-391. [5] Battigalli, P. and M. Siniscalchi (2003) “Rat Ad- ionalization and Incomplete Information,” vances in Theoretical Economics 3-1, Article 3. [6] Bergemann, D. and S. Morris (2003): “Robust Mechanism Design,” mimeo. [7] Bernheim, D. (1984): “Rationalizable strategic behavior,” , 52, 1007-1028. Econometrica [8] Börgers T. (1994): “Weak Dominance and Approximate Common Knowledge,” Journal of Economic Theory , 64, 265-276. [9] Börgers T. and M. Janssen (1995): “On the dom inance solvability of large Cournot games,” Games and Economic Behavior 8, 297-321. [10] Brandenburger, A. and E. Dekel (1987): “Rationalizability and Correlated Equilibria,” Econometrica , 55, 1391-1402. [11] Brandenburger, A. and E. Dekel (1993): “Hierarchies of Beliefs and Common Knowledge,” Journal of Economic Theory , 59, 189-198. Econo- [12] Carlsson, H. and E. van Damme (1993): “Global Games and Equilibrium Selection,” , 61, 989-1018. metrica [13] Cremer, J. and. R. McLean (1988): “Full extraction of the Surplus in Bayesian and Dominant Econometrica , 56, 1247-1257. Strategy Auctions”, [14] Dekel, E. and D. Fudenberg (1990): “Rational Behavior with Payo Uncertainty,” Journal ff of Economic Theory , 52, 243-267. [15] Dekel, E. D. Fudenberg, S. Morris (2003): “Interim Rationalizability,” mimeo. [16] Dekel, E. D. Fudenberg, S. Morris (2004): “Dense Types,” mimeo. [17] Dekel, Eddie and Faruk Gul (1997): “Rationality and Knowledge in Game Theory,” in Kreps, D. and K. Wallis (eds): Advances in Economics and Econometrics: Theory and Applications , Cambridge University Press, UK. [18] Ely, J. and M. Peski (2004): “Hierarchies of beliefs and interim rationalizability,” mimeo. [19] Feinberg, Y. (2002): “Subjective Reasoning in Dynamic Games,” forthcoming in Games and Economic Behavior . [20] Feinberg, Y. and A. Skrzypacz (2002): “Unce rtainty about uncertainty and delay in bar- gaining,” forthcoming in Econometrica . [21] Harsanyi, J. (1967): “Games with Incomplete Information played by Bayesian Players. Part I: the Basic Model,” Management Science 14, 159-182.

39 FINITE-ORDER IMPLICATIONS 39 eric Infeasibility of Full Surplus Extraction [22] Heifetz, A. and Z. Neeman (2003): “On the Gen in Mechanism Design,” mimeo. [23] Kajii, A. and S. Morris (1997): “The Robustn ess of Equilibria to Incomplete Information,” Econometrica , 65, 1283-1309. [24] Kajii, A. and S. Morris (1998): “Payo ff Continuity in Incomplete Information Games,” Journal of Economic Theory , 82, 267-276. , 71, 1255- Econometrica [25] Lipman, B. (2003): “Finite Order Implications of Common Priors,” 1267. [26] Mertens and Zamir (1985): “Formulation of B ayesian Analysis for Games with Incomplete International Journal of Game Theory Information,” , 10, 619-632. [27] Monderer, D. and D. Samet (1989): “Approximating Common Knowledge with Common Games and Economic Behavior Beliefs,” , 1, 170-190. [28] Morris, S. (2002): “Typical Types,” mimeo. [29] Morris, S. and H. Shin (1998): “Unique Equilibrium in a Model of Self-Ful fi lling Attacks,” 88, 587-597 American Economic Review [30] Morris, S. and Ui (2002): “Generalized Potentials and Robust Sets of Equilibria,” mimeo. [31] Moulin, H. (1984): “Dominance solvability and Cournot stability,” Mathematical Social Sciences 7, 83-102. [32] Neeman, Z. (2004) “The Relevance of Private Information in Mechanism Design,” Journal of Economic Theory 117, 55-77. [33] Nyarko, Y. (1996): “Convergence in Economic Models with Bayesian Hierarchies of Beliefs,” Journal of Economic Theory , 74, 266-296. iqueness of the Courn [34] Okuguchi, K. and Suzumura, K. (1971): “Un ot Oligopoly Equilib- rium,” Economic Studies Quarterly , 22, 81-83. [35] Oyama, D. and O. Tercieux (2005): “Strategic Implications of (Non-)Common Priors II: Robustness of Equilibria,” mimeo (University of Tokyo and PSE). [36] Pearce, D. (1984): “Rationalizable Strategic Behavior and the Problem of Perfection,” , 52, 1029-1050. Econometrica [37] Rubinstein, A. (1989): “The Electronic M ail Game: Strategic Behavior Under ‘Almost Common Knowledge’,” The American Economic Review , Vol. 79, No. 3, 385-391. [38] Simon, R. (2003): “Games of Incomplete Inf ormation, Ergodic Theory, and Measurability of Equilibria,” 138, 73-92. Israeli Journal of Mathematics [39] Tan, T. and S. Werlang (1988): “The Bayesian foundations of solution concepts of games,” Journal of Economic Theory 45, 370-391 [40] Townsend, R. (1983): “Forecasting the Forecasts of Others,” Journal of Political Economy , 9-4, 546-88. [41] Ui, T. (2001). “Robust Equilibria of Potential Games,” Econometrica 69, 1373-1380. [42] Weinstein, J. and M. Yildiz (2003): “Impact of Higher-Order Uncertainty,” MIT Department of Economics Working Paper 03-14.

40 40 JONATHAN WEINSTEIN AND MUHAMET YILDIZ [43] Wilson, R. (1987): “Game-Theoretic Analys es of Trading Processes,” in: Truman Bewley (ed.) Advances in Economic Theory: Fifth World Congress , Cambridge UK: Cambridge University Press, 33-70. [44] Yildiz (2005): “Generic Uniquenes s of Rationalizable Actions,” mimeo. MIT URL :

Related documents