Bayesian games with a continuum of states
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Hellman, Ziv; Levy, Yehuda John Article Bayesian games with a continuum of states Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Hellman, Ziv; Levy, Yehuda John (2017) : Bayesian games with a continuum of states, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 12, Iss. 3, pp. 1089-1120, https://doi.org/10.3982/TE1544 This Version is available at: https://hdl.handle.net/10419/197128 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/
Theoretical Economics 12 (2017), 1089–1120 1555-7561/20171089 Bayesian games with a continuum of states Ziv Hellman Department of Economics, Bar Ilan University Yehuda John Levy Department of Economics and Nuffield College, University of Oxford We show that every Bayesian game with purely atomic types has a measurable Bayesian equilibrium when the common knowledge relation is smooth. Conversely, for any common knowledge relation that is not smooth, there exists a type space that yields this common knowledge relation and payoffs such that the resulting Bayesian game does not have any Bayesian equilibrium. We show that our smoothness condition also rules out two paradoxes involving Bayesian games with a continuum of types: the impossibility of having a common prior on components when a common prior over the entire state space exists, and the possibility of interim betting/trade even when no such trade can be supported ex ante. Keywords. Bayesian games, Bayesian equilibrium, common priors, continuum of states. JEL classification. C72. 1. Introduction When are Bayesian games guaranteed to have Bayesian equilibria? One answer to that question was given in Harsanyi (1967), the same work that introduced the common prior assumption, by reducing the question of the existence of Bayesian equilibria to the question of the existence of Nash equilibria in an associated game of complete information. As the latter always exist, so do Bayesian equilibria. Harsányi’s theorem on the existence of Bayesian equilibria, however, was proved only for Bayesian games in which all variables are finite. That is, it holds for games with a finite number of players, finite action spaces, finite payoff parameters, and a finite number of possible types. When state spaces have continuum many states, Harsányi’s theorem no longer holds. Simon (2003) presented an example of a three-player Bayesian game over Ziv Hellman: [email protected] Yehuda John Levy: [email protected] The research of the first author was supported in part by the European Research Council under the European Commission’s Seventh Framework Programme (FP7/2007–2013)/ERC Grant Agreement 249159, and in part by Israel Science Foundation Grants 538/11 and 212/09. The research of the second author was supported in part by Israel Science Foundation Grant 1596/10. Copyright ©2017 The Authors. Theoretical Economics. The Econometric Society. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at http://econtheory.org. DOI: 10.3982/TE1544
1090 Hellman and Levy Theoretical Economics 12 (2017) a continuum of states with no measurable Bayesian equilibrium.1This was extended in Hellman (2014a), which contains an example of a two-player Bayesian game over a continuum of states with no Bayesian ε-equilibrium for sufficiently small ε. The main results of this paper deal with conditions for the existence of Bayesian equilibria and common priors when the state and type spaces are infinite. Theorem 1 provides sufficient conditions for the existence of measurable Bayesian equilibria within the class of Bayesian games over a continuum of states. These conditions are that (i) in every state of the world, each individual belief is purely atomic, and (ii) the common knowledge relation is smooth, that is, the common knowledge components are precisely the level sets of some measurable function. The theorem also establishes a certain necessity of the smoothness, showing that when it does not hold, there are payoffs and types with precisely this common knowledge structure for which measurable Bayesian equilibria do not exist. Continuum state spaces also present challenges relating to the concept of the common prior. Simon (2000) presented an example in which the very existence of a common prior depends on whether one is looking at the ex ante stage or the interim stage. That is, common priors exist globally in the full state space in the ex ante stage but do not exist over any common knowledge component (i.e., in the interim stage). This is so counterintuitive that Heifetz (2006) conjectured (using the concept of common improper priors) that despite the lack of consistency in the existence of common priors in such examples, there would still be behavioral consistency in terms of agreement, i.e., agents would consistently agree not to trade in both the ex ante stage and the interim stage. This leads us to the other results of this paper: in Theorems 2and 3we show that exactly the same smoothness conditions that characterize which games necessarily possess Bayesian equilibria also provide necessary and sufficient conditions for ex ante/interim stage consistency of the existence of common priors and no trade/no betting theorems in continuum of states. In particular, the conjecture of Heifetz (2006) is wrong: there are examples of behavioral inconsistency, with agents unable to agree to trade ex ante but agreeing to trade in the interim stage whenever the common knowledge relation is nonsmooth. Smoothness is a critical condition in the main results here, both those relating to measurable Bayesian equilibria and consistency of common prior existence. Intuitively, nonsmooth models appear to be rare and unusual cases, requiring a conscious effort to conjure up. It would appear that most applications of Bayesian games with a continuum of states in which one would be interested, such as models of profits, elapsed time, accumulated resources, and so on, are more likely than not to satisfy the conditions for the existence of measurable equilibria. With respect to the existence of measurable Bayesian equilibria in games with continuum-many types, a seminal paper by Milgrom and Weber (1985) proved that such 1Restricting attention to the question of the existence of measurable equilibria is not truly restrictive: given a game without measurable Bayesian equilibria, one can always construct another game, with an additional player whose payoffs depend on the strategies of the players in the original game, that has no well defined equilibria at all.
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1091 equilibria exist when players have absolutely continuous information. However, the class of smooth games that are established to have equilibria in this paper are a subset of a different class CIC, the class of games with a subset of continuously distributed informational commonality introduced by Stinchcombe (2011a), which in turn is a subclass of DIS,gameswithdiscontinuous information structures. All the results in Milgrom and Weber (1985) assume the condition of absolutely continuous information, which means that they are disjoint from DIS and hence not applicable at all to the games here. In his paper, Stinchcombe (2011a) shows that for games in CIC with generic payoff functions, the expected payoffs of the players are not continuous as functions of the strategy profiles. When the expected payoffs are continuous as a function of the players’ behavioral strategies, which are functions from players’ knowledge to actions, Bayesian equilibria exist. The smooth games in this paper are elements of CIC, leading to the conclusion that although generically the expected payoffs of those games are not continuous, they are nevertheless guaranteed by Theorem 1 to have Bayesian equilibria. More details may be found in Section 6.3. We conclude by noting that during the composition of this paper, some perhaps surprising parallels between concepts used in game theory and descriptive set theory concepts were uncovered. For example, a regular conditional distribution tof a probability measure μparallels the posterior tof a prior μwith respect to a knowledge structure; the saturation of a point with respect to a countable Borel equivalence relation corresponds to the knowledge component of a state in an epistemic game theoretic model. Hopefully, these sorts of parallels can be deepened in future research, leading to more new results. 2. Preliminaries and the model 2.1 Smoothness As is standard, a Polish space is a separable, completely metrizable space. Measurability without further qualification in this paper, in the context of a Polish space X,is understood to mean measurability with respect to the Borel σ-algebra of X. A relation Eon a Polish space is said to be Borel if it is Borel as a subset of ×. In other words, the relation is Borel if the set {(xy) ∈×|xEy}is a Borel subset of ×.Itissaidtobecountable if each equivalence class, referred to as classes or atoms, is countable. We abbreviate countable Borel equivalence relation as CBER. A very central definition from descriptive set theory that is used extensively in this paper follows. Definition 1. A Borel equivalence relation Eon a Polish space is smooth if there is a Polish space Yand a Borel function ψ:→Ysuch that for all xy ∈, xEy⇐⇒ ψ(x) =ψ(y) (i.e., the classes of Eare precisely the level sets of ψ).
1092 Hellman and Levy Theoretical Economics 12 (2017) If Eis the common knowledge relation, a function ψwitnessing the smoothness of the relation can be thought of as an auxiliary tool that enables us to ascertain when xand yare in the same common knowledge component: that occurs if and only if ψ(x) =ψ(y). AtransversalofEis a set T⊆Xthat intersects each Eequivalence class at exactly one point. It is easy to see that if a Borel Ehas a Borel transversal, then it is smooth: intuitively, the map “ψ(x) =the only element of Tthat is E-equivalent to x” witnesses the smoothness of E. For CBERs, the converse is true as well. From this, one can show that if every equivalence class of Eis finite, then Eis smooth. We use this fact repeatedly. Consider the set T={x∈X|∀y∈Xx Ey=⇒ x≤y} i.e., the set of the ≤elements of the E-equivalence classes, for any Borel linear order on the domain of E; such a set exists by a theorem of Kuratowski. This Tis seen to be Borel and a transversal of E, hence finiteness of the E-classes is sufficient for smoothness; for details, see, e.g., Example 6.1 of Kechris and Miller (2004). However, for CBERs, which are the focus of much of the material of this paper, matters are not so simple. When Eis an equivalence relation, for each x∈, one may consider the class containing x, which we denote by [x]E.AsetB⊆is said to be saturated with respect to Eif it is the union of E-equivalence classes, i.e., if there is a set A⊆such that B=[A]E:= x∈A[x]E. The collection of all the Borel E-saturated sets of a Borel equivalence relation Eforms a σ-algebra, denoted σ(E). 2.2 Proper regular conditional distributions Game theorists are used to working with priors and posteriors. The appropriate generalization to the context of the structures in this paper makes use of the concept of proper regular conditional distributions. For a Polish space X,let(X) denote the space of regular Borel probability distributions on X, with the topology of weak convergence of probability measures, and let f(X) ⊆(X) (resp. a(X) ⊆(X)) denote the subspace of finitely supported (resp. purely atomic) measures. The space (X) is itself a Polish space. If ( B)is a measurable space, μ∈(),andFis a sub-σ-algebra of B, then (see Blackwell and Ryll-Nardzewski 1963)aproper regular conditional distribution (henceforth, proper RCD) of μ,givenF, is a mapping t:×B→[01]such that for each B∈B, ω→tω(B) is Borel, and such that μ(B) = tω(B)dμ(ω) for all B∈B(1) and tω(A) =1for μ-a.e. ω∈A∈F It can be shown that (1) implies that for every T∈B, tω(T) =Eμ[1T|F](ω) μ-a.e. ω∈
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1093 In terms that may be more familiar for game theorists, a proper RCD tof a probability measure μmay be thought of as the posterior tof a prior μwithrespecttoaknowledge structure F=σ(E). 2.3 Knowledge spaces Most game theory models2work with partitionally generated type spaces. In such models, where is finite or countable, each player ihas a partition iof . This approach suffers from a difficulty in the case of a continuum of states, since the partition has to “agree” with the measurable structure. In addition, in the continuum case, one cannot work with arbitrary unions of partitions elements; only Borel unions are admissible. Our approach differs from the more classical approach given in Nielson (1984) and Brandenburger and Dekel (1987)—see Section 6.2 for more details on this—in favor of defining knowledge via relations (instead of σ-algebras), which is better suited for the class of purely atomic types that concern us. Our approach also differs from the “types” approach of Milgrom and Weber (1985);seeSection 6.1. We work in general with a nonempty, finite set of players Iand a Polish space of states .Witheachplayeriwe associate a Borel equivalence relation over , denoted Ei, called i’s knowledge relation. Intuitively, the unions of classes of Eirepresent the events that player ican identify; hence, σ(Ei)is the set of Borel events that player ican identify. (In the discrete setting in which knowledge spaces are generated from knowledge partitions iof ,σ(Ei)would be given by the unions of elements of i.) Adopting the convention that Estands for the profile of knowledge relations (Ei)i∈I, aknowledge space is then a triple ( IE). Given a knowledge space (IE),theequivalence relation induced by E, which we denote by E, is the transitive closure of the union i∈IEi; i.e., the smallest equivalence relation containing each element in E.Observe that σ(E)=i∈Iσ(Ei). In terms that may be more familiar, Eis the common knowledge equivalence relation. The class of the common knowledge relation Econtaining ω is called the common knowledge component containing ω, and is denoted C(ω). 2.4 Type spaces and priors Fix a knowledge space ( IE).Foreachi∈I,atype function tiis a mapping ti:→ () that is σ(Ei)-measurable and satisfies ti ω(A) =1whenever ω∈A∈σ(Ei). Adopting the convention that tstands for the tuple (ti)i∈I,atriple(It)is called atype space. A type space implicitly defines the knowledge relations Eiunderlying the type functions: ωEiω(i.e., (ωω)∈Ei) if and only if ti ω=ti ω.Intuitively,ti ω(B) is the probability player iassociates to the set Bin state ω. Ameasureμi∈() such that tiis a proper RCD for μigiven σ(Ei)is a prior for ti. Acommon prior is a measure μthat is a prior for the type functions of all the players i∈I. 2The definition can be broadened to “nearly all models in the economics, game theory, and the decision theory literature.”
1094 Hellman and Levy Theoretical Economics 12 (2017) 2.5 Purely atomic positive spaces We adopt two main restrictive assumptions on type spaces. The assumption of positivity, meaning that every state in a player’s knowledge component is ascribed nonzero probability by his type in said component, is convenient but not really necessary for our results. In contrast, the other supposition, of countable support for every type, is a substantively needed assumption. Definition 2. A type space satisfying the conditions that ti ω∈f(),3for all i∈Iand all ω∈, is called a finitely supported type space. Definition 3. A type space such that for all i∈Iand all ω∈,thetypeti ωis purely atomic (i.e., has countable support), is called a purely atomic type space. We always assume that types are purely atomic. (Occasionally, we also require them to be finitely supported.) In addition, we henceforth assume all type spaces satisfy positivity. Definition 4. A type space such that for all i∈Iand all ω∈,ti ω[ω]>0is called positive. (More generally, if tis a proper RCD of μwith respect to F,tis called positive if tω[ω]>0for all ω∈.)4 When positivity does not hold, the set of states that violated it are of measure zero under any prior (see Proposition 7 in Appendix A); P hence, positivity is a fairly benign and merely technical assumption. In combination, pure atomicity and positivity imply that each class of each player’s knowledge relation is countable, and hence so are the classes of the common knowledge equivalence relation.5In this case, the knowledge relation of each player is always smooth and the knowledge sets of each player are the level sets of his type function. Definition 5. A CBER is belief induced if there are finitely many smooth CBERs that generate it. 3Recall that f() is the set of finitely supported measures over ; hence, finite support is equivalent to each player ascribing positive probability only to a finite number of elements in all knowledge components. Type spaces with finite fan-out, as defined in Simon (2003), in which each partition element of the underlying partitionally based knowledge space contains only a finite number of elements, are a special case of this, although these classes coincidence if positivity (see Definition 4) is assumed. 4The restriction to positive type spaces is not a serious one and is implemented largely for convenience and simplicity. Theorem 2 only relies on this assumption to guarantee that a weaker assumption holds, namely that the knowledge classes of each player are countable. Theorem 3(i), which follows from Theorem 2, could similarly be proved under this weaker assumption. Theorems 1(ii) and 3(ii) deliver constructions in which positivity is guaranteed anyway. Only the proof of Theorem 1(i) makes direct use of positivity instead of the above weaker condition, in particular Proposition 11; this, too, can be relaxed at the expense of a more complicated proof. 5This can be shown easily if one builds the common knowledge relation inductively from the players’ knowledge relations, as done in Section A.1.
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1095 Lemma 19 implies that a CBER is belief induced if and only if it is the common knowledge relation of some finitely supported positive type space.6Not all CBERs are belief induced.7We elaborate on this in Appendix B. 2.6 Bayesian games and Bayesian equilibria ABayesian game =(ItAr)consists of the following components: •The set (It) forms a type space (with knowledge relations Eunderstood implicitly as generated by t). •The equality A=(Ai)i∈Iis a tuple consisting of a finite action set for each player i∈I. •The relationship r:×i∈IAi→RIis a bounded measurable payoff function, with rithen being the resulting payoff to player i. The payoff function rextends multilinearly to mixed actions in the usual manner. Astrategy of a player i∈Iis a mapping si:→(Ai)that is constant on each player’s knowledge component. In other words, if ωω∈are in the same atom of Ei, i.e., ti ω[ω]>0, then si(ω) =si(ω). ABayesian ε-equilibrium with ε≥0isaprofileofstrategiess=(si)i∈Isuch that for each i∈I,allω∈,8and each alternative strategy x∈(Ai)of player i,9 {ω|ti ω[ω]>0} riωsωti ωω+ε≥ {ω|ti ω[ω]>0} riωxs−iωti ωω When a Bayesian ε-equilibrium ssatisfies the condition that each siis Borel measurable,10 sis said to be a measurable11 Bayesian ε-equilibrium (ε-MBE). When ε=0,we refer simply to an MBE instead of a 0-MBE. 6On a knowledge relation with finite classes, one can define a type function that is uniform over each class. 7The authors are grateful to Benjamin Weiss for pointing this out. 8If there is a common prior, the definition can be modified to require ε-optimality of the strategy in almost every state. 9Recall that we have assumed types are purely atomic and payoffs are bounded. 10The combination of being Borel measurable and being constant in each knowledge component of player iis equivalent to requiring that siis σ(Ei)-measurable. 11It is possible for a game to have Bayesian ε-equilibria that are not measurable as in, for example, Simon (2003). However, for our purposes it suffices to concentrate on characterizing the existence of measurable ε-equilibria, because given a game that admits only nonmeasurable equilibria, it is always possible to create another game that has no equilibria at all. This is accomplished by adding an additional player k to who is not in the player set of . The payoffs of players i= kin are defined to be exactly identical to their payoffs in ,whilek’s payoff is given by an integral over the actions of the players i= k.Butifthe equilibrium strategies of the players i= kare nonmeasurable, at equilibrium player kcannot even define a payoff, much less an optimal strategy. See Hellman (2014a) for an explicit example of such a construction.
1096 Hellman and Levy Theoretical Economics 12 (2017) 3. Results 3.1 Measurable Bayesian equilibria Our main claim is that smoothness of type spaces is crucial for many results, including the existence of measurable equilibria in Bayesian games, the persistence of common priors over components, and consistency of no betting in the ex ante and interim stages. These are all detailed in this section. Definition 6. A purely atomic positive type space whose common knowledge relation is smooth is called a smooth type space. A Bayesian game whose underlying type space is smooth is called a smooth Bayesian game. Sometimes we want to specify exactly how a type space fails to be smooth. Definition 7. Let Ebe a nonsmooth belief-induced CBER. Then a type space τ whose underlying common knowledge relation is Eis called an E-nonsmooth type space. A Bayesian game whose underlying type space is E-nonsmooth is called an E- nonsmooth Bayesian game. Theorem 1 extends Harsányi’s theorem, essentially stating that (within the class of purely atomic type spaces) a Bayesian game is guaranteed to have a measurable Bayesian equilibrium if and only if it is smooth. Theorem 1 also resolves the paradox appearing in Section 4.2.1. Theorem 1. (i) Every smooth Bayesian game has an MBE. (ii) Conversely, for every nonsmooth belief-induced CBER E,thereisanE-nonsmooth Bayesian game that has no MBE. In part (ii), the types can be constructed to be positive, have finitely supported types, and a common prior, and such that the game in fact does not possess an ε-MBE for ε>0small enough. To prove Theorem 1(i), we proceed in three steps. First, we develop a notion of the space of all (positive) Bayesian games with countably many states S,playersetI,and set of actions A(Proposition 11), which we denote by B(SIA) (or just Bfor short). Second, we then prove the existence of a Bayesian equilibrium selection for this class of games (Corollary 13). Finally, we show that one can measurably map the games induced on each common knowledge component of a general game into the space of games on countably many states S(Proposition 14). The composition of this mapping and the Bayesian equilibrium selection from the second step give us the required global Bayesian equilibrium. We can construct such a mapping because the smoothness, it turns out, allows us measurably to enumerate the elements of each atom, and once we have this enumeration, we can map the game on each atom to its appropriate game in the space B;when we lack such an enumeration, this cannot be done because we have no canonical way to select the mapping. Details are given in Section A.3.
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1103 Example 5. We have =AZfor some finite Aand the relation is given by (xj)j∈Z∼ (yk)k∈Zif and only if ∃m∈Z,∀n,xn=yn+m, i.e., the relation induced by the shift. This common knowledge relation is induced when the state of nature is represented by a doubly infinite sequence of data elements in Abut there is uncertainty as to where the “middle” point is. This relation is well known to be nonsmooth. ♦ Since the common knowledge structures above are not smooth, common knowledge components may not possess common priors, Bayesian equilibria may not exist for certain priors and payoffs, and for certain type structures—even those induced by a common prior—we may find acceptable bets on components even though there are no globally acceptable bets. Again, constructively coming to these conclusions in each separate case could be extremely cumbersome, while Theorem 1 guarantees the existence of such cases in a general manner. We end with a generalization of an Example appearing in Section 4. We include Example 6 here to show that even when it is the case that when a player observes his own type he knows that the types of the other players are limited to a finite number of possible points, the resulting knowledge structure may be nonsmooth. Example 6. Let there be Nplayers and let ⊆RNbe a finite union n j=1jsuch that each jis a subset of a plane Pjof dimension n−1not parallel to any axis; i.e., each Pj is of the form x∈Rnaixi=cfor some a1anc∈Rsuch that ai= 0for all i Assume there is a common prior μon each jthat is absolutely continuous with respect to the n−1-dimensional Lebesgue measure on Pj. The information structure is such that for each i,playeriis informed of the ith coordinate, i.e., Ei:= (x1xN) (y1yN)∈×|xi=yi For each player, the knowledge classes are finite. The resulting knowledge structure may be smooth, but, as the examples of Section 4 show, may also be nonsmooth. ♦ 6. Relationship to the literature 6.1 Type spaces Many papers on games of incomplete information, such as Milgrom and Weber (1985), model players’ information by types. In such modelling, each player ihas a type space iwith measurable structure Fi, and the set of states of the world in their framework is := iiwith a nonatomic common prior μdefined on a σ-algebra Fcontaining iFi. Players in this framework are told their own signals and then use that to deduce a distribution on the states of the world via Bayesian updating with respect to a common prior μ; we omit the technical details. The model of Bayesian games studied in this paper can also be formulated using type spaces. In our framework, each knowledge relation Eiis smooth and the classes are
1104 Hellman and Levy Theoretical Economics 12 (2017) level sets of the type function. Hence, by Proposition 1 in Appendix A, the quotient space i:= /Ei, which is the collection of classes of Eiwith the quotient σ-algebra, is standard Borel, i.e., a Polish space in some topology consistent with its measurable structure. Equivalently, we can take ito be the range of player i’s type function. A common prior μon then induces a common prior on ii, itself a quotient space of . 6.2 Knowledge An alternative approach to modelling knowledge and type spaces on a continuum of states, going back to Nielson (1984) (see also Brandenburger and Dekel 1987)istomodel information using σ-algebras. That is, player i’s knowledge is represented by a σ-algebra Fi, where it is understood that two elements x,yare in the same information component for player iwhenever x∈B∈Fiimplies that y∈B. (The connection to a knowledge equivalence relation (Ei)i∈Ifrom our framework is given by Fi=σ(Ei).) We have avoided this approach for several reasons. First of all, while that approach may be more appropriate for general knowledge structures, when the types are purely atomic (and hence knowledge classes are countable), it is more intuitive, in our opinion, to express the knowledge of the players, as well as the common knowledge structures, using equivalence relations. While it is true that our framework is set upon the background of measurable structures, it still echoes the standard partitional approach to knowledge. The only reason we cannot directly extend the standard approach is because we restrict ourselves to measurable sets. Second, if one wishes to model continuum knowledge spaces based directly on knowledge of σ-algebras, various serious technical problems arise. For example, there is no guarantee that each player’s knowledge components are measurable or, more generally, that the saturation of a measurable set with respect to a player’s knowledge (or the induced common knowledge relation) is measurable. These problems are partially overcome by identifying sets that differ by a set of measure 0, but, other than the fact that this requires a common prior at the onset, this fix is useless for our purposes, as we need to look at the individual common knowledge components, which are generically of null measure. 6.3 Equilibrium existence Given the technical difficulties discussed in the previous subsection that are encountered in dealing with general knowledge structures, results on equilibrium existence in general knowledge structures are almost nonexistent. One seminal positive result that does establish the existence of equilibrium is Milgrom and Weber (1985). As discussed in Section 6.1,Milgrom and Weber (1985) model incomplete information using types, and our framework can directly be translated into that framework. The notion of strategies in Milgrom and Weber (1985) also differs from the definition used here; they use distributional strategies in contrast to the definition of strategies given above in Section 2.6. This is also not a serious difference; Balder (1988) similarly proves equilibrium existence for the same class of games in the class of strategies of the “more classical” sense used here.
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1105 However—and here is where the real substantive difference lies—Milgrom and Weber (1985) then go on to assume that the common prior μis absolutely continuous with respect to iμi,withμibeing the marginal on i. Unless the common prior is purely atomic, this assumption clearly implies that types cannot be purely atomic and, hence, this assumption, which guarantees the existence of Bayesian equilibrium, is not satisfied in our framework. Following Stinchcombe (2011a), denoting the class of games in which μis not absolutely continuous with respect to a product measure by DIS (for discontinuous information structure), the results of this paper relate solely to a subclass of DIS. In contrast, the class of games in Milgrom and Weber (1985) is precisely those that are disjoint from DIS. Stinchcombe (2011a) also studies structures within the DIS class. That paper defines a structure of beliefs to have a subset satisfying continuously distributed informational commonality (CIC) if on a nonnull subset at least two players can agree on a nonatomically distributed variable; formally, if there is a set B⊆that is common knowledge (i.e., B∈jσ(Ej), recalling notation from Section 6.1)withμ(B) > 0,players i j ∈I, and a Borel mapping φ:B→[01]that is σ(Ei)∩σ(Ej)-measurable (in B), such that φ∗◦μ:= μ◦φ−1is nonatomic.17 Denoting the class of information structures that contain CIC’s by CIC,TheoremAofStinchcombe (2011a) shows that CIC ⊆DIS.18 By definition, smooth games are in CIC.19 Nonmembership in the class DIS guarantees equilibrium by Milgrom and Weber (1985). However, within DIS, membership or nonmembership in CIC has no direct implications for the existence of MBE. On the one hand, a two-player game that is ergodic (that is, the only common knowledge sets are of μ-measure 0or 1)isnot in CIC;an example of this is the game in Hellman (2014b), which is ergodic and has no equilibria. On the other hand, it is easy to construct games with no equilibria in which two players have identical knowledge, which places them within CIC; e.g., to the game from Hellman (2014b), add dummy players with perfect information. Theorem B of Stinchcombe (2011a) showsthatforgamesinCIC with generic payoff functions, the expected payoffs of the players are not continuous as functions of the strategy profiles (where the strategies, viewed as maps from type spaces to mixed actions that are measurable with respect to players’ information, are endowed with the weak-∗topology induced by μ). As previously mentioned, every smooth Bayesian game is in CIC, while Theorem 1 of this paper shows that every such game has an MBE. Thus, games with purely atomic types and smooth common knowledge relations form an interesting class: although generically the expected payoffs of such games are not continuous, measurable Bayesian equilibria are still guaranteed to exist. The relationships between DIS and CIC, and their implications for Bayesian equilibrium existence are summarized graphically in Figure 3. 17That is, for each x∈[01],μ({ω∈B|φ(ω) =x})=0. 18The theorem requires that the knowledge σ-algebras of at least two players support nonatomic measures; this holds by construction in our setup as all player’s knowledge relations are smooth; see Proposition 1. 19All Polish spaces are Borel isomorphic.
1106 Hellman and Levy Theoretical Economics 12 (2017) Figure 3. A representation of the interrelationships between DIS and CIC and the implications of these properties for the existence of equilibria. We also mention in passing Stinchcombe (2011b), which shows the existence of correlated equilibrium. In that framework, actions are a function not only of types, but also of a public signal chosen uniformly in [01]. Interestingly, the proof there shows that MBE exists in all Bayesian games if one allows for saturated measurable structures, i.e., structures constructed using nonstandard analysis. Such extensions, however, are highly nonconstructive. Appendix A: Tools and proofs A.1 Mathematical tools Recall that [T]Edenotes the saturation of Twith respect to a CBER E, i.e., the smallest union of classes of Econtaining T. In terms that may be more familiar to game theorists used to working with finite partitions, [ω]Eis the knowledge component containing ω. Recall that a transversal of an equivalence relation is a set that intersects each equivalence class at exactly one point. Given a Polish and a CBER E,welet/Edenote the quotient space whose elements are the equivalence classes by E, and the induced σ-algebra consists of precisely the images of the E-saturated sets in under the quotient map. We make repeated use of the following proposition, which follows from Propositions 6.3 and 6.4 of Kechris and Miller (2004) and the discussion preceding them. Proposition 1. The following conditions are equivalent for a CBER Eon a Polish space :
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1107 (a) The CBER Eis smooth. (b) There is a Borel transversal for E. (c) The quotient space /Eis standard Borel.20 Proposition 2 follows from21 Theorem 1 of Blackwell and Ryll-Nardzewski (1963). Proposition 2. If Eis a smooth CBER on a Polish space and μ∈(), then there exists a proper RCD tof μgiven σ(E). Proposition 3 is a slight variation of the Lusin–Novikov theorem (e.g., Kechris 1995, Theorem 18.10). Proposition 3. Let Ebe a CBER on a Polish space . Then there are Borel functions (fn)∞ n=1:→such that for all ω∈,{fn(ω)}n∈N=[ω]E. From this (or related results) one can deduce by standard techniques; see, e.g., Dougherty et al. (1994, Theorem 5.1). Proposition 4. Let Ebe a smooth CBER on a Polish space and let Sbe a countably infinite set. Then there is a Borel mapping :→Ssuch that for each E-class Cof ,the restriction |C:C→Sis injective and (C) =Sif Cis infinite. We also recall the following well known result, of which we make repeated implicit use. Proposition 5. Let X,Ybe Polish spaces and let f:X→Ybe Borel such that for each y∈Y,f−1(y) is at most countable (i.e., the map is countable-to-one). Then for each Borel B⊆X,f(B)is Borel. Let τbe a type space with knowledge relations (Ei)i∈I.Foreachi∈Iand each set N⊆,letCi(N) denote the saturation of Nwith respect to Ei, i.e., Ci(N) =[N]Ei.For each finite sequence ˆ i=(i1ik)∈I∗=n≥0Inand N⊆,let Cˆ i(N) =CikCik−1···Ci1(N)··· and C(N) = ˆ i∈I∗ Cˆ i(N) which is the smallest common knowledge set containing N. Since, by Propositions 4and 5, the saturation of Borel sets under a CBER is also Borel, we have the following lemma. 20That is, there is a measurable bijection between it and a Polish space. 21The condition given there for the existence of proper RCDs is easily seen to follow from the existence of a Borel transversal, which, by Proposition 1, follows from smoothness.
1108 Hellman and Levy Theoretical Economics 12 (2017) Lemma 6. If Nis Borel, then so is Ci(N) for each i∈Iand so is C(N). The following proposition justifies our restriction to positive type spaces. Proposition 7. If tis a proper RCD of μwith respect to σ(E)for a CBER E,then μω|tω[ω]=0=0 In particular, if τis a type space (not necessarily positive) with a common prior μ,thenfor each i∈I, μω∈|ti ω[ω]=0=0 Proof. Denote N={ω|tω[ω]=0}. Since tω[ω]=0if (ωω)/∈Eand since tω[ω]=0 for all the countably many ωwith (ωω)∈Esince ω→tωis σ(E)-measurable, we see that tω[N]=0for all ω∈. The proposition follows from the definition of an RCD. The following definition and its properties can be found in Dougherty et al. (1994, Section 3). Definition 9. Let Ebe a CBER on a Polish space . A measure μ∈() is called E- quasi-invariant if for any Borel set A⊆,μ(A) =0if and only if μ([A]E)=0. Lemma 8. Let Ebe a CBER on a Polish space ,andlettbe a proper RCD of μ∈() given σ(E).Thentis positive on an E-saturated set of full measure if and only if μis E-quasi-invariant. Proof. Assume μis E-quasi-invariant. Denoting N={ω|tω[ω]=0},Proposition 7 implies that μ(N) =0,soμ([N]E)=0. Therefore, tis positive on the E-saturated set of full measure \[N]E. Conversely, if tis positive on a E-saturated set of full measure X,thenforBorelA⊆ with μ(A) =0, denoting B=A∩X, 0=μ(A) ≥μ(B) = tω(B)dμ(ω) =[B]E tω(B)dμ(ω) (A.1) since tω(B) =0for ω/∈[B]E. Since tis positive in X,tω(B) > 0in Band, hence, in [B]Eas ω→tωis σ(E)-measurable. Hence, by (A.1), μ([B]E)=0and, hence, finally μ([A]E)=0, as [A]E⊆[B]E∪( \X). If ( E)and (D)are Polish spaces with induced Borel equivalence relations E and D,( E)is said to be embeddable into ( D)if there is an injective Borel mapping ψ:→such that for all ωη ∈,ωEη⇐⇒ ψ(ω)Dψ(η); in this case, we denote ( E)(D). ACBERissaidtobehyperfinite (Dougherty et al. (1994)) if it is induced by the action of a Borel Zaction on ; i.e., if there is a bijective22 Borel mapping T:→such that xEy⇐⇒ ∃ n∈Z,Tn(x) =y. 22If a Borel mapping between Polish spaces is injective, then by Proposition 5,itsinverseisalsoBorel.
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1109 Proposition 9. Let E1and E2be nonsmooth CBERs on Polish spaces 1and 2,withE1 being hyperfinite. Then (1E1)(2E2). Proof. Since E2is nonsmooth, the Glimm–Effros dichotomy for CBERs (see Harrington et al. 1990 or Dougherty et al. 1994, Theorem 3.4) implies that there is a universal hyperfinite CBER23 (0E0)such that (0E0)(2E2).ByTheorem7.1ofDougherty et al. (1994), any two nonsmooth hyperfinite equivalence relations can be embedded into each other; hence, (1E1)(0E0).Hence,(1E1)(2E2). A.2 Embedding of games Proposition 10 is the primary tool needed for the proofs of Theorems 1(ii) and 3(ii). Proposition 10. Let and Xbe Polish spaces, and let Ebe a CBER on that is nonsmooth and belief induced. Let τX=(XJ(tj X)j∈J)be an everywhere finitely supported and positive type space with a common prior μX, and assume that its common knowledge equivalence relation EXis hyperfinite. Then one can construct a Borel embedding ψ:X→and a set of players I,suchthatJ⊂I, along with an everywhere finitely supported and positive type space τ=(I(ti)i∈I)possessing a common prior μfor which the following statements hold: •The CBER Eis the common knowledge relation induced by the type space τ. •We have tj ψ(·)=ψ∗((tj X)(·))for each j∈Jin X;explicitly,forωω∈Y, tj ψ(ω)[ψ(ω)]=(tj X)ω[ω]. •For j∈Jand ω/∈ψ(X),tj ω=δω, i.e., the Dirac measure at ω. •We have ψ∗(μX):= μX◦ψ−1μand ψ∗(μX)(A) =μ(A) for A∈σ(E). The middle two points say that for each player j∈J, his type function on Xbecomes his type function on ψ(X), and he has perfect knowledge on \ψ(X). Note in particular that if ω1EXω2,thenψ(ω1)Eψ(ω2). The last point says that the prior induced on by μXis absolutely continuous with respect to the final common prior μ,andtheyagree on E-saturated sets. Proof of Proposition 10. Since EXis hyperfinite, by Proposition 9 there is an embedding ψ:(XEX)(E). Denote =ψ(X) and 0=[]E=[ψ(X)]E; both and 0are Borel by Propositions 3and 5. Since Eis belief induced, by Proposition 18 there exist a set of players Kand smooth CBERs (Ek)k∈Kwith finite classes such that Eis induced by (Ek)k∈K.Forj∈J,definethe knowledge relations Ej=(xy) |(x =y)∨xy ∈ψ(X) ∧ψ−1(x) ψ−1(y)∈Ej X 23Given 0=2N,E0is the tail equivalence relation; Dougherty et al. (1994, Corollary 8.2) shows this to be hyperfinite.
1110 Hellman and Levy Theoretical Economics 12 (2017) i.e., Ejis induced by Ej Xon ψ(X) and player jhas perfect knowledge outside of .Define I=K∪J. By construction, Eis induced by (Ei)i∈I, since it is induced by (Ei)i∈I\Jand Ej refines Efor j∈J. Denote by E0=E0and E=E|the restrictions of Eto 0=[]Eand ,respectively. For brevity, let ˆμ=ψ∗(μX):= μX◦φ−1;ˆμis then E-quasi-invariant by the assumption that μXis positive and by Proposition 8.ByDougherty et al. (1994,Proposition 3.1), there exists an E0-quasi-invariant measure νon 0satisfying ˆμνand satisfying ˆμ(A) =ν(A) for A∈σ(E). Observe the following string of implications for a set A⊆, ˆμ(A) =0→ˆμ[A∩]E=0→ˆμ[A∩]E=0→ν[A∩]E=0(A.2) where the first implication is because ˆμis E-quasi-invariant, the second is because [A∩]E⊆[A∩]E∪( \), and the last is since ν,ˆμagree on E-saturated sets. Also, ν(A \) =0→ν[A\]E=0→ˆμ[A\]E=0(A.3) where the first implication is because νis E-quasi-invariant, and the last is since ˆμν. We deal now with two cases to construct μto be quasi-invariant: If ν() =1,letμ=ˆμ.ThenifA⊆with μ(A) =0, then ν(A \) ≤ν( \) =0and ˆμ(A) =0. It follows that since [A]E=[A∩]E∪[A\]E,wehaveμ([A]E)=0by (A.2) and (A.3). Otherwise, if ν() < 1,set μ=1 2ˆμ+1 2ν(·|0\) If μ(A) =0, then clearly we also have ˆμ(A) =0and ν(A \) =0,andthen,asabove, μ([A]E)=0. Either way, μis E0-quasi-invariant. Now, for i∈I\J,lettibe a proper RCD of μwith respect to Ei,whichexistsbyProposition 2.ByLemma 8, it is positive on an Ei-saturated set of full μ-measure and can be modified on a μ-null set to be positive everywhere.24 Clearly, for j∈J,tjas defined in the statement of the proposition is a positive proper RCD of μwith respect to Ej, since μ(·|) =ˆμ(·|). A.3 Proof of Theorem 1 Fix a countably infinite set S.LetBdenote the collection of all I-tuples (sigi)i∈Ifor which (SIA(sigi)i∈I)constitutes a positive Bayesian game, with (si)denoting the types and (gi)denoting the payoff functions. Collection Bis endowed with the topology of pointwise convergence:25 for each αin a directed set, denote by ϒαapair(si αgi α)i∈Iof I-tuples of types and payoff functions associated to αby a net. Then ϒα→ϒ=(sigi)i∈I in Bif for every player i∈I,everyω∈S, and every pure action profile a∈i∈IAione has gi α(ωa) →gi(ω a) and si α(ω) →si(ω). 24Since Eihas finite classes, over a μ-null set of Eiclasses let tibe uniform in each class. 25We define the topology in terms of nets.
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1111 Proposition 11. Collection Bis homeomorphic to a Borel subset of := ((S) ×Ri∈IAi)S×Iand, hence, is Polish (in some topology that induces the same Borel structure). The simple intuition is that for each player and state pair (si) ∈S×I, we need to specify an element in (S) as well as an element of Ri∈IAi, which specifies what payoff that player receives as a result of each possible action profile. Henceforth, we identify Bwith some such fixed subset of . Proof of Proposition 11.WriteB=i∈I(Bi s×Bi g),whereBi s(resp. Bi g) denotes the projection of Bto the space of types (resp. payoffs) for player i, with the induced topologies. It suffices to show that Bi sis homeomorphic to a Borel subset of ((S))Sand that Bi gis homeomorphic to a Borel subset of RS×i∈IAi. The latter claim is trivial once one notices that for any countable set C,thesetof bounded functions in RCis Borel, as it can be written n∈N c∈Ca∈RC||ac|≤n and that the Tychonoff topology is indeed the required topology of pointwise convergence. We next turn to the former claim. As mentioned above, the intuition describing the map from Bi sto ((S))Sis to specify the beliefs of player iin each state. Hence, the image of Bi sunder such a map is given by the subset of defined by two conditions: they satisfy positivity and they are constant over their support. Mathematically, these conditions are, respectively, ω∈Ssi∈(S)S|si ω[ω]>0 ∩ ωηζ∈Ssi∈(S)S|si ω[η]>0→si ω(ζ) =si η[ζ] and again the topology is the topology of pointwise convergence. Denote by =i∈Iithe space of strategy profiles over (SIA).Thespaceiof strategies for player ion the countable space Sis clearly a compact subspace of ((Ai))S; hence, is a compact space in the induced topology. Proposition 12. The Bayesian equilibrium correspondence BE :B→has a Borel graph and takes on compact nonempty values. Proof. The fact that every Bayesian game with a countable state space has at least one Bayesian equilibrium follows from standard fixed point arguments; see, e.g., Simon (2003). The fact that the set of Bayesian equilibria is compact also follows by standard
1112 Hellman and Levy Theoretical Economics 12 (2017) arguments. To show that the graph Gof the BE correspondence is Borel, note that26 G=sigii∈Iσ∈B×|∀ω∈S∀i∈I∀b∈Ai v∈S givσ(ω)si ω[v]≥ v∈S givbσ−p(ω)si ω[v] Corollary 13. There exists a Borel mapping ψ:B→such that for all ∈B,ψ() is a Bayesian equilibrium of . The proof of Corollary 13 follows immediately from Proposition 12 and the selection theorem of Kuratowski and Ryll-Nardzewski (see, e.g., Aliprantis and Border 2006, Theorem 18.13, and Himmelberg 1975). Recalling that C(ω) is the common knowledge component containing a state ω,denote by s|C(ω) the restriction of the collection of types to the domain C(ω) and denote by g|C(ω) the same restriction with respect to the payoff functions. Given two Bayesian games (SIAsSgS)and (TIAsTgT) with finite or countable state spaces and the same player and action sets, an embedding from Sto Tis an injective mapping φ:S→Tsuch that the following statements hold: •For all ω∈S,i∈I, and pure action profiles x,gi S(ωx) =gi T(φ(ω) x). •For all ωη ∈Sand i∈I,(si S)ω[η]=(si T)φ(ω)[φ(η)]. Note that ψ(S) is then common knowledge in the type space sT. Intuitively, the Bayesian game (SIAsSgS)is copied isomorphically to the Bayesian game (φ(S)IAs|φ(S)g|φ(S)). Proposition 14. Let =(IAtr) be a Bayesian game such that the common knowledge relation Eis smooth. Let B=B(SIA) be the set of Bayesian games that all share some same countable state space Sand the same player and action space as . Then there is a Borel map :→Sand a Borel map27 :/E→Bsuch that for each ω∈,ifwedenote ω=C(ω)IAt|C(ω)r|C(ω) then |C(ω) is an embedding of ωin (C(ω)). See Figure 4. Note that for some ω,C(ω) may be finite, in which case |C(ω) is not surjective. 26The quantifiers are all countable here. 27By Proposition 11,/Eis standard Borel.
Theoretical Economics 12 (2017) Bayesian games with a continuum of states 1119 Balder, Erik J. (1988), “Generalized equilibrium results for games with incomplete information.” Mathematics of Operations Research, 13, 265–276. [1104] Blackwell, David and Czesław Ryll-Nardzewski (1963), “Non-existence of everywhere proper conditional distributions.” The Annals of Mathematical Statistics, 34, 223–225. [1092,1107] Brandenburger, Adam and Eddie Dekel (1987), “Common knowledge with probability 1.” Journal of Mathematical Economics, 16, 237–245. [1093,1104] Chang, Joseph T. and David Pollard (1997), “Conditioning as disintegration.” Statistica Neerlandica, 51, 287–317. [1115] Dougherty, Randall, Stephen C. Jackson, and Alexander S. Kechris (1994), “The structure of hyperfinite Borel equivalence relations.” Transactions of the American Mathematical Society, 341, 193–225. [1107,1108,1109,1110,1114] Feinberg, Yossi (2000), “Characterizing common priors in the form of posteriors.” Journal of Economic Theory, 91, 127–179. [1097,1101] Harrington, Leo A., Alexander S. Kechris, and Alain Louveau (1990), “A Glimm–Effros dichotomy for Borel equivalence relations.” Journal of the American Mathematical Society, 3, 903–928. [1109] Harsanyi, John C. (1967), “Games of incomplete information played by Bayesian players, part I: The basic model.” Management Science, 14, 159–182. [1089] Heifetz, Aviad (2006), “The positive foundation of the common prior assumption.” Games and Economic Behavior, 56, 105–120. [1090,1101] Hellman, Ziv (2014a), “A game with no Bayesian approximate equilibrium.” Journal of Economic Theory, 153, 138–151. [1090,1095,1097,1099,1114] Hellman, Ziv (2014b), “Countable spaces and common priors.” International Journal of Game Theory, 43, 193–213. [1097,1101,1105,1115] Hellman, Ziv and Dov Samet (2012), “How common are common priors?” Games and Economic Behavior, 74, 517–525. [1114] Himmelberg, Charles J. (1975), “Measurable relations.” Fundamenta Mathematicae, 87, 53–72. [1112] Kechris, Alexander S. (1995), Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York. [1107,1115] Kechris, Alexander S. and Benjamin D. Miller (2004), Topics in Orbit Equivalence,volume 1852 of Lecture Notes in Mathematics. Springer-Verlag, Berlin. [1092,1106,1118] Lehrer, Ehud and Dov Samet (2011), “Agreeing to agree.” Theoretical Economics, 6, 269– 287. [1098,1099,1100] Milgrom, Paul R. and Nancy Stokey (1982), “Information, trade and common knowledge.” Journal of Economic Theory, 26, 17–27. [1099]
1120 Hellman and Levy Theoretical Economics 12 (2017) Milgrom, Paul R. and Robert J. Weber (1985), “Distributional strategies for games with incomplete information.” Mathematics of Operations Research, 10, 619–632. [1090,1091, 1093,1103,1104,1105] Nielson, Lars T. (1984), “Common knowledge, communication, and convergence of beliefs.” Mathematical Social Sciences, 8, 1–14. [1093,1104] Rudin, Walter (1986), Real and Complex Analysis, third edition. Higher Mathematics Series. McGraw-Hill, New York. [1102] Samet, Dov (1998), “Common priors and separation of convex sets.” Games and Economic Behavior, 24, 172–174. [1115] Simon, Robert (2000), “The common prior assumption in belief spaces: An example.” Discussion Paper #228, Center for the Study of Rationality, Hebrew University, Jerusalem. [1090,1099] Simon, Robert Samuel (2003), “Games of incomplete information, ergodic theory, and the measurability of equilibria.” Israel Journal of Mathematics, 138, 73–92. [1089,1094, 1095,1099,1111] Stinchcombe, Maxwell B. (2011a), “Balance and discontinuities in infinite games with type-dependent strategies.” Journal of Economic Theory, 146, 656–671. [1091,1105] Stinchcombe, Maxwell B. (2011b), “Correlated equilibrium existence for infinite games with type-dependent strategies.” Journal of Economic Theory, 146, 638–655. [1106] Co-editor Faruk Gul handled this manuscript. Manuscript received 27 May, 2013; final version accepted 30 August, 2016; available online 12 September, 2016.