When Do Types Induce the Same Belief Hierarchy?

Abstract

Type structures are a simple device to describe higher-order beliefs. However, how can we check whether two types generate the same belief hierarchy? This paper generalizes the concept of a type morphism and shows that one type structure is contained in another if and only if the former can be mapped into the other using a generalized type morphism. Hence, every generalized type morphism is a hierarchy morphism and vice versa. Importantly, generalized type morphisms do not make reference to belief hierarchies. We use our results to characterize the conditions under which types generate the same belief hierarchy.

1. Introduction

Higher-order beliefs play a central role in game theory. Whether a player is willing to invest in a project, for example, may depend on what he or she thinks that his or her opponent thinks about the economic fundamentals, what he or she thinks that his or her opponent thinks that he or she thinks, and so on, up to arbitrarily high order (e.g., [1]). Higher-order beliefs can also affect economic conclusions in settings ranging from bargaining [2,3] and speculative trade [4] to mechanism design [5] . Higher-order beliefs about actions are central to epistemic characterizations, for example, of rationalizability [6,7], Nash equilibrium [8,9] and forward induction reasoning [10]. In principle, higher-order beliefs can be modeled explicitly, using belief hierarchies. For applications, the type structures introduced by Harsanyi [11] provide a simple, tractable modeling device to represent players’ higher-order beliefs.

While type structures provide a convenient way to represent higher-order beliefs, it may be difficult to check whether types generate the same belief hierarchy. The literature has considered the following question: given two type structures, $\mathcal{T}$ and ${\mathcal{T}}^{\prime }$, is it the case that for every type in $\mathcal{T}$, there is a type in ${\mathcal{T}}^{\prime }$ that generates the same belief hierarchy? That is, is the type structure $\mathcal{T}$ contained in ${\mathcal{T}}^{\prime }$?1 The literature has considered two different tests to address this question, one based on hierarchy morphisms and one based on type morphisms. Hierarchy morphisms can be used to give a complete answer to this question: a type structure $\mathcal{T}$ is contained in ${\mathcal{T}}^{\prime }$ if and only if there is a hierarchy morphism from the former to the latter. A problem with this test is that hierarchy morphisms make reference to belief hierarchies, as we shall see. Therefore, this test requires us to go outside the purview of type structures. The second test uses type morphisms. Type morphisms are defined solely in terms of the properties of the type structures. However, the test based on type morphisms only provides a sufficient condition: if there is a type morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$, then $\mathcal{T}$ is contained in ${\mathcal{T}}^{\prime }$ [14]. However, as shown by Friedenberg and Meier [12], the condition is not necessary: it may be that ${\mathcal{T}}^{\prime }$ contains $\mathcal{T}$, yet there is no type morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$. The work in [12] also provides a range of conditions under which the condition is both necessary and sufficient. However, they do not directly address the question of whether there might be an alternate test (which provides conditions that are both necessary and sufficient) that does not require us to describe the belief hierarchies explicitly.

This paper provides such a test, by generalizing the notion of a type morphism. We show that a type structure is contained in another if and only if there is a generalized type morphism from the former to the latter. Therefore, a generalized type morphism is a hierarchy morphism and vice versa. Unlike the definition of hierarchy morphisms, the definition of generalized type morphisms does not make reference to belief hierarchies. Therefore, this test can be carried out without leaving the purview of type structures. Using this result, it is straightforward to verify whether two types generate the same belief hierarchy, as we show.

Hierarchy morphisms are used in a number of different settings. For example, they can be used to check whether types have the same rationalizable actions [15] and play an important role in the literature on the robustness to misspecifying the parameter set more generally; see, e.g., Ely and Peski [16] and Liu [17]. Hierarchy morphisms are also used to study the robustness of Bayesian-Nash equilibria to misspecifications of players’ belief hierarchies [18,19] and in epistemic game theory. The current results make it possible to study these issues without describing players’ belief hierarchies explicitly, using that every hierarchy morphism is a generalized type morphism and conversely.

A critical ingredient in the definition of a generalized type morphism is the σ-algebra on a player’s type set, which separates his or her types if and only if they differ in the belief hierarchy that they generate. Mertens and Zamir ([13], p. 6) use this σ-algebra to define non-redundant type structures, and this σ-algebra also plays an important role in the work of Friedenberg and Meier [12], where it is used to characterize the conditions under which hierarchy morphisms and type morphisms coincide. The work in [13] provides a nonconstructive definition of this σ-algebra, and [12] show that the σ-algebra defined by [13] is the σ-algebra generated by the functions that map types into belief hierarchies. We provide a constructive definition of this σ-algebra, by means of a type partitioning procedure that does not make reference to belief hierarchies.

While many of the ingredients that underlie our results are known in some form or another, we view the contribution of this paper as combining these ideas in a new way to generalize the concept of a type morphism, so that it provides a necessary and sufficient condition for a type structure to be contained in another that does not refer to belief hierarchies.

A number of papers has shown that the measurable structure associated with type structures can impose restrictions on reasoning [12,20,21,22,23]. This paper contributes to that literature in two ways. First, we elucidate the connection by constructing the measurable structure on type sets that is generated by players’ higher-order beliefs. Second, we provide tools to easily go from the domain of type structures to the domain of belief hierarchies and vice versa.

The outline of this paper is as follows. The next section introduces basic concepts. Section 3 discusses type morphisms and hierarchy morphisms. Section 4 defines our generalization of a type morphism and proves the main result. Section 5 applies this result to characterize the conditions under which types generate the same belief hierarchy. Section 6 considers the special case where players have finitely many types. Proofs are relegated to the Appendix A.

2. Belief Hierarchies and Types

In this section, we show how belief hierarchies can be encoded by means of a type structure. The original idea behind this construction goes back to Harsanyi (1967). We first provide the definition of a type structure and subsequently explain how to derive a belief hierarchy from a type in a type structure. We conclude the section with an example of two type structures that are equivalent, in the sense that they produce exactly the same sets of belief hierarchies for the players. This example thus shows that the same belief hierarchy can be encoded within different type structures.

2.1. Type Structures

Consider a finite set of players I. Assume that each player i faces a basic space of uncertainty $(X_i,{\Sigma }_i)$, where $X_i$ is a set and ${\Sigma }_i$ a σ-algebra on $X_i$. That is, ${\mathcal{X}}_i=(X_i,{\Sigma }_i)$ is a measurable space. The combination $\mathcal{X}={(X_i,{\Sigma }_i)}_{i\in I}$ of basic uncertainty spaces is called a multi-agent uncertainty space. The basic space of uncertainty for player i could, for instance, be the set of opponents’ choice combinations, or the set of parameters determining the utility functions of the players, or even a combination of the two.

A belief hierarchy for player i specifies a probability measure on ${\mathcal{X}}_i$, the first-order belief, a probability measure on ${\mathcal{X}}_i$ and the opponents’ possible first-order beliefs, the second-order belief, and so on. As is standard, we encode such infinite belief hierarchies by means of type structures.

For any measurable space $(Y,\widehat{\Sigma })$, we denote by $\mathrm{\Delta }(Y,\widehat{\Sigma })$ the set of probability measures on $(Y,\widehat{\Sigma })$. We endow $\mathrm{\Delta }(Y,\widehat{\Sigma })$ with the coarsest σ-algebra that contains the sets:

$$\{\mu \in \mathrm{\Delta }(Y,\widehat{\Sigma })\mid \mu \left(E\right)\ge p\}:E\in \widehat{\Sigma },p\in [0,1].$$

This is the σ-algebra used in Heifetz and Samet [14] and many subsequent papers; it coincides with the Borel σ-algebra on $\mathrm{\Delta }(Y,\widehat{\Sigma })$ (induced by the weak convergence topology) if Y is metrizable and $\widehat{\Sigma }$ is the Borel σ-algebra. Product spaces are endowed with the product σ-algebra. Given a collection of measurable spaces $(Y_i,{\mathcal{Y}}_i)$, $i\in I$, write $\mathcal{Y}$ for the product σ-algebra ${⨂}_{j\in I}{\mathcal{Y}}_j$ and ${\mathcal{Y}}_{-i}$ for the product σ-algebra ${⨂}_{j\ne i}{\mathcal{Y}}_j$, where $i\in I$.

Definition 1.

(Type structure) Consider a multi-agent uncertainty space $\mathcal{X}={(X_i,{\Sigma }_i)}_{i\in I}$. A type structure for $\mathcal{X}$ is a tuple $\mathcal{T}={(T_i,{\Sigma }_i^{\mathcal{T}},b_i)}_{i\in I}$ where, for every player i,

(a) $T_i$ is a set of types for player i, endowed with a σ-algebra ${\Sigma }_i^{\mathcal{T}}$, and

(b) $b_i:T_i\to \mathrm{\Delta }(X_i\times T_{-i},{\widehat{\Sigma }}_i)$ is a measurable mapping that assigns to every type $t_i$ a probabilistic belief $b_i\left(t_i\right)\in \mathrm{\Delta }(X_i\times T_{-i},{\widehat{\Sigma }}_i)$ on its basic uncertainty space and the opponents’ type combinations, where ${\widehat{\Sigma }}_i={\Sigma }_i\otimes {\Sigma }_{-i}^{\mathcal{T}}$ is the product σ-algebra on $X_i\times T_{-i}$.

Finally, if $f:Y\to (Y^{\prime },{\Sigma }^{\prime })$ is a function from Y to the measurable space $(Y^{\prime },{\Sigma }^{\prime })$, then $\sigma \left(f\right)$ is the σ-algebra on Y generated by f, that is, it is the coarsest σ-algebra that contains the sets $\{y\in Y:f(y)\in E\}$ for $E\in {\Sigma }^{\prime }$.

2.2. From Type Structures to Belief Hierarchies

In the previous subsection, we have introduced the formal definition of a type structure. We now show how to “decode” a type within a type structure, by deriving the full belief hierarchy that it induces.

Consider a type structure $\mathcal{T}={(T_i,{\Sigma }_i^T,b_i)}_{i\in I}$ for $\mathcal{X}$. Then, every type $t_i$ within $\mathcal{T}$ induces an infinite belief hierarchy:

$$h_i^{\mathcal{T}}\left(t_i\right)=({\mu }_i^{\mathcal{T},1}\left(t_i\right),{\mu }_i^{\mathcal{T},2}\left(t_i\right),\dots ),$$

where ${\mu }_i^{\mathcal{T},1}\left(t_i\right)$ is the induced first-order belief, ${\mu }_i^{\mathcal{T},2}\left(t_i\right)$ is the induced second-order belief, and so on. We will inductively define, for every n, the n-th order beliefs induced by types $t_i$ in $\mathcal{T}$, building upon the $(n-1)$-th order beliefs that have been defined in the preceding step.

We start by defining the first-order beliefs. For each player i, define:

$$H_i^1:=\mathrm{\Delta }(X_i,{\Sigma }_i)$$

to be the set of beliefs about $X_i$, and for every type $t_i\in T_i$, define its first-order belief ${\mu }_i^{\mathcal{T},1}\left(t_i\right)$ by:

$${\mu }_i^{\mathcal{T},1}\left(t_i\right)\left(E_i\right):=b_i\left(t_i\right)(E_i\times T_{-i})\mathrm{for}\mathrm{all}{E}_i\in {\Sigma }_i.$$

Clearly, ${\mu }_i^{\mathcal{T},1}\left(t_i\right)\in \mathrm{\Delta }(X_i,{\Sigma }_i)$ for every type $t_i$. Define $h_i^{\mathcal{T},1}\left(t_i\right):={\mu }_i^{\mathcal{T},1}\left(t_i\right)$. The mapping ${\mu }_i^{\mathcal{T},1}$ from $T_i$ to $H_i^1$ is measurable by standard arguments. For $n>1$, suppose the set $H_i^{n-1}$ has been defined and that the function $h_i^{\mathcal{T},n-1}$ from $T_i$ to $H_i^{n-1}$ is measurable. Let ${\widehat{\Sigma }}_i^{n-1}$ be the product σ-algebra on $X_i$ × ${\times }_{j\ne i}{H}_j^{n-1}$, and define:

$$H_i^n:=H_i^{n-1}\times \mathrm{\Delta }(X_i\times H_{-i}^{n-1},{\widehat{\Sigma }}_i^{n-1}).$$

For every type $t_i$, define its n-th-order belief ${\mu }_i^{\mathcal{T},n}\left(t_i\right)$ by:

$$\mathrm{for}\mathrm{all}E\in {\widehat{\Sigma }}_i^{n-1}:{\mu }_i^{\mathcal{T},n}\left(t_i\right)\left(E\right)=b_i\left(t_i\right)\left(\{(x_i,t_{-i})\in X_i\times T_{-i}\mid (x_i,h_{-i}^{\mathcal{T},n-1}\left(t_{-i}\right))\in E\}\right),$$

with $h_{-i}^{\mathcal{T},n-1}\left(t_{-i}\right)={\left(h_j^{\mathcal{T},n-1}\left(t_j\right)\right)}_{j\ne i}$. Since $h_j^{\mathcal{T},n-1}$ is measurable for every player j, ${\mu }_i^{\mathcal{T},n}$ is indeed a probability measure on $(X_i\times H_{-i}^{n-1},{\widehat{\Sigma }}_i^{n-1})$. Define $h_i^{\mathcal{T},n}\left(t_i\right):=(h_i^{\mathcal{T},n-1}\left(t_i\right),{\mu }_i^{\mathcal{T},n}\left(t_i\right)).$ It follows that $h_i^{\mathcal{T},n}\left(t_i\right)\in H_i^n$. Moreover, $h_i^{\mathcal{T},n}$ is measurable.

Note that, formally speaking, the n-th-order belief ${\mu }_i^{\mathcal{T},n}\left(t_i\right)$ is a belief about $X_i$ and the opponents’ first-order until $(n-1)$-th order beliefs. Moreover, by construction, the n-th and $(n+1)$-th order beliefs ${\mu }_i^{\mathcal{T},n}\left(t_i\right)$ and ${\mu }_i^{\mathcal{T},n+1}\left(t_i\right)$ are coherent in the sense that they induce the same belief on $X_i$ and the opponents’ first-order until $(n-1)$-th order beliefs.

Finally, for every type $t_i\in T_i$, we denote by:

$$h_i^{\mathcal{T}}\left(t_i\right):={\left({\mu }_i^{\mathcal{T},n}\left(t_i\right)\right)}_{n\in \mathbb{N}}$$

the belief hierarchy induced by type $t_i$ in $\mathcal{T}$. Furthermore, define $H_i$ to be the set $\mathrm{\Delta }\left(X_i\right)\times {\times }_{n\ge 1}\mathrm{\Delta }(X_i\times H_{-i}^n)$ of all belief hierarchies. We say that two types, $t_i$ and $t_i^{\prime }$, of player i generate the same belief hierarchy if $h_i^{\mathcal{T}}\left(t_i\right)=h_i^{\mathcal{T}}\left(t_i^{\prime }\right)$. Types $t_i$ and $t_i^{\prime }$ generate the same n-th-order belief if ${\mu }_i^{\mathcal{T},n}\left(t_i\right)={\mu }_i^{\mathcal{T},n}\left(t_i^{\prime }\right)$.2

2.3. Example

Consider a multi-agent uncertainty space $\mathcal{X}={(X_i,{\Sigma }_i)}_{i\in I}$ where $I=\{1,2\}$, $X_1=\{c,d\}$, $X_2=\{e,f\}$ and ${\Sigma }_1,{\Sigma }_2$ are the discrete σ-algebras on $X_1$ and $X_2$, respectively. Consider the type structures $\mathcal{T}=(T_1,T_2,{\Sigma }_1,{\Sigma }_2,b_1,b_2)$ and ${\mathcal{T}}^{\prime }=(R_1,R_2,{\Sigma }_1,{\Sigma }_2,{\beta }_1,{\beta }_2)$ in

Table 1. Two equivalent type structures.

Type Structure $\mathcal{T}$

$T_1=\{t_1,t_1^{\prime },t_1^{″}\},T_2=\{t_2,t_2^{\prime },t_2^{″}\}$

$b_1\left(t_1\right)=\frac{1}{2}(c,t_2)+\frac{1}{2}(d,t_2^{\prime })$

$b_1\left(t_1^{\prime }\right)=\frac{1}{6}(c,t_2)+\frac{1}{3}(c,t_2^{″})+\frac{1}{2}(d,t_2^{\prime })$

$b_1\left(t_1^{″}\right)=\frac{1}{2}(c,t_2^{\prime })+\frac{1}{2}(d,t_2^{″})$

$b_2\left(t_2\right)=\frac{1}{4}(e,t_1)+\frac{1}{2}(e,t_1^{\prime })+\frac{1}{4}(f,t_1^{″})$

$b_2\left(t_2^{\prime }\right)=\frac{1}{8}(e,t_1)+\frac{1}{8}(e,t_1^{\prime })+\frac{3}{4}(f,t_1^{″})$

$b_2\left(t_2^{″}\right)=\frac{3}{8}(e,t_1)+\frac{3}{8}(e,t_1^{\prime })+\frac{1}{4}(f,t_1^{″})$

Type Structure ${\mathcal{T}}^{\prime }$

$R_1=\{r_1,r_1^{\prime },r_1^{″}\},$   $R_2=\{r_2,r_2^{\prime },r_2^{″}\}$

${\beta }_1\left(r_1\right)=\frac{1}{4}(c,r_2)+\frac{1}{4}(c,r_2^{″})+\frac{1}{2}(d,r_2^{\prime })$

${\beta }_1\left(r_1^{\prime }\right)=\frac{1}{2}(c,r_2^{\prime })+\frac{1}{8}(d,r_2)+\frac{3}{8}(d,r_2^{″})$

${\beta }_1\left(r_1^{″}\right)=\frac{1}{2}(c,r_2^{\prime })+\frac{3}{8}(d,r_2)+\frac{1}{8}(d,r_2^{″})$

${\beta }_2\left(r_2\right)=\frac{1}{4}(e,r_1^{\prime })+\frac{3}{4}(f,r_1)$

${\beta }_2\left(r_2^{\prime }\right)=\frac{3}{4}(e,r_1^{\prime })+\frac{1}{4}(f,r_1)$

${\beta }_2\left(r_2^{″}\right)=\frac{1}{8}(e,r_1^{\prime })+\frac{1}{8}(e,r_1^{″})+\frac{3}{4}(f,r_1)$

.

Then, it can be verified that the types $t_1,t_1^{\prime },r_1^{\prime }$ and $r_1^{″}$ generate the same belief hierarchy, and so do the types $t_1^{″}$ and $r_1,$ the types $t_2,t_2^{″}$ and $r_2^{\prime }$ and the types $t_2^{\prime },r_2$ and $r_2^{″}.$ In particular, for every type in $\mathcal{T}$, there is another type in ${\mathcal{T}}^{\prime }$ generating the same belief hierarchy, and vice versa. In this sense, the two type structures $\mathcal{T}$ and ${\mathcal{T}}^{\prime }$ are equivalent.

3. Hierarchy and Type Morphisms

The literature has considered two concepts that map type structures into each other, type morphisms and hierarchy morphisms. Throughout the remainder of the paper, fix two type structures, $\mathcal{T}={(T_i,{\Sigma }_i^{\mathcal{T}},b_i)}_{i\in I}$ and ${\mathcal{T}}^{\prime }={(T_i^{\prime },{\Sigma }_i^{{\mathcal{T}}^{\prime }},b_i^{\prime })}_{i\in I}$ on $\mathcal{X}$. The functions that map types from $\mathcal{T}$ and ${\mathcal{T}}^{\prime }$ into belief hierarchies are denoted by $h_i^{\mathcal{T}}$ and $h_i^{{\mathcal{T}}^{\prime }}$, respectively.

Definition 2.

(Hierarchy morphism) For each player $i\in I$, let ${\phi }_i$ be a function from $T_i$ to $T_i^{\prime }$, such that for every type $t_i\in T_i$, $h_i^{{\mathcal{T}}^{\prime }}\left({\phi }_i\left(t_i\right)\right)=h_i^{\mathcal{T}}\left(t_i\right)$. Then, ${\phi }_i$ is a hierarchy morphism (from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$). With some abuse of notation, we refer to the profile ${\left({\phi }_i\right)}_{i\in I}$ as a hierarchy morphism.

Therefore, if there is a hierarchy morphism between $\mathcal{T}$ and ${\mathcal{T}}^{\prime }$, then every type in $\mathcal{T}$ can be mapped into a type in ${\mathcal{T}}^{\prime }$ in a way that preserves belief hierarchies. We say that the type structure ${\mathcal{T}}^{\prime }$ contains $\mathcal{T}$ if, and only if, there is a hierarchy morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$.

Type morphisms are mappings between type structures that preserve beliefs.

Definition 3.

(Type morphism) For each player $i\in I$, let ${\phi }_i$ be a function from $T_i$ to $T_i^{\prime }$ that is measurable with respect to ${\Sigma }_i^{\mathcal{T}}$ and ${\Sigma }_i^{{\mathcal{T}}^{\prime }}$.3 Suppose that for each player i, type $t_i\in T_i$ and $E\in {\Sigma }_i\otimes {\Sigma }_{-i}^{{\mathcal{T}}^{\prime }}$,

$$b_i\left(t_i\right)\left(\{(x_i,t_{-i})\in X_i\times T_{-i}\mid (x_i,{\phi }_{-i}\left(t_{-i}\right))\in E\}\right)=b_i^{\prime }\left({\phi }_i\left(t_i\right)\right)\left(E\right).$$

(1)

Then, $\phi :={\left({\phi }_i\right)}_{i\in I}$ is a type morphism (from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$).

Heifetz and Samet [14] have shown that one type structure is contained in another whenever there is a type morphism from the former to the latter.

Proposition 1.

([14], Prop. 5.1) If φ is a type morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$, then it is a hierarchy morphism. Therefore, if there is a type morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$, then ${\mathcal{T}}^{\prime }$ contains $\mathcal{T}$.

Unlike hierarchy morphisms, type morphisms do not make reference to belief hierarchies. Therefore, to check whether there is a type morphism from one type structure to another, we need to consider only the type structures. However, the condition that there be a type morphism from one type structure to another provides only a sufficient condition for the former to be contained in the latter. Indeed, Friedenberg and Meier [12] show that the condition is not necessary: there are type structures such that one is contained in the other, yet there is no type morphism between the two.

4. Generalized Type Morphisms

Type morphisms require beliefs to be preserved for every event in the types’ σ-algebra. However, for two types to generate the same belief hierarchy, it suffices that their beliefs are preserved only for events that can be described in terms of players’ belief hierarchies. We use this insight to define generalized type morphisms and show that a type structure contains another if and only if there is a generalized type morphism from the latter to the former.

The first step is to define the relevant σ-algebra. Mertens and Zamir ([13], p. 6) provide the relevant condition. We follow the presentation of Friedenberg and Meier [12].

Definition 4.

([12], Def. 5.1) Fix a type structure $\mathcal{T}$ and fix a sub-σ algebra ${\tilde{\Sigma }}_i^{\mathcal{T}}\subseteq {\Sigma }_i^{\mathcal{T}}$ for each player $i\in I$. Then, the product σ-algebra ${\tilde{\Sigma }}^{\mathcal{T}}$ is closed under $\mathcal{T}$ if for each player i,

$$\{t_i\in T_i\mid b_i\left(t_i\right)\left(E\right)\ge p\}\in {\tilde{\Sigma }}_i^{\mathcal{T}}$$

for all $E\in {\Sigma }_i\otimes {\tilde{\Sigma }}_{-i}^{\mathcal{T}}$ and $p\in [0,1]$.

The coarsest (sub-)σ algebra that is closed under $\mathcal{T}$ is of special interest, and we denote it by ${\mathcal{F}}^{\mathcal{T}}={⨂}_{i\in I}{\mathcal{F}}_i^{\mathcal{T}}$. It is the intersection of all σ-algebras that are closed under $\mathcal{T}$.4 The work in [13] uses this σ-algebra to define non-redundant type spaces, and [12] use it to characterize the condition under which a hierarchy morphism is a type morphism.

Friedenberg and Meier [12] provide a characterization of the σ-algebra ${\mathcal{F}}^{\mathcal{T}}$ in terms of the hierarchy mappings. Recall that $\sigma \left(h_i^{\mathcal{T}}\right)$ is the σ-algebra on $T_i$ generated by the mapping $h_i^{\mathcal{T}}$. That is, $\sigma \left(h_i^{\mathcal{T}}\right)$ is the coarsest σ-algebra that contains the sets:

$$\{t_i\in T_i\mid h_i^{\mathcal{T}}\left(t_i\right)\in E\}:E\subseteq H_i\mathrm{measurable}.$$

Lemma 1.

([12], Lemma 6.4) Let the product σ-algebra ${\mathcal{F}}^{\mathcal{T}}$ be the coarsest σ-algebra that is closed under $\mathcal{T}$. Then, for each player i, ${\mathcal{F}}_i^{\mathcal{T}}=\sigma \left(h_i^{\mathcal{T}}\right)$.

We are now ready to define generalized type morphisms.

Definition 5.

(Generalized type morphism) For each player $i\in I$, let ${\phi }_i$ be a function from $T_i$ to $T_i^{\prime }$ that is measurable with respect to ${\Sigma }_i^{\mathcal{T}}$ and ${\mathcal{F}}_i^{{\mathcal{T}}^{\prime }}$.5 Suppose that for each player i, type $t_i\in T_i$ and $E\in {\Sigma }_i\otimes {\mathcal{F}}_{-i}^{{\mathcal{T}}^{\prime }}$,

$$b_i\left(t_i\right)\left(\{(x_i,t_{-i})\in X_i\times T_{-i}\mid (x_i,{\phi }_{-i}\left(t_{-i}\right))\in E\}\right)=b_i^{\prime }\left({\phi }_i\left(t_i\right)\right)\left(E\right).$$

Then, $\phi :={\left({\phi }_i\right)}_{i\in I}$ is a generalized type morphism (from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$).

Note that a type morphism is always a generalized type morphism, but not vice versa. Like type morphisms, generalized type morphisms are defined using the language of type structures alone; the definition does not make reference to belief hierarchies. The difference between type morphisms and generalized type morphisms is that the former requires beliefs to be preserved for all events in the σ-algebra ${\Sigma }_i\otimes {\Sigma }_{-i}^{{\mathcal{T}}^{\prime }}$ for player i, while the latter requires beliefs to be preserved only for events in the σ-algebra ${\Sigma }_i\otimes {\mathcal{F}}_{-i}^{{\mathcal{T}}^{\prime }}$, and this σ-algebra is a coarsening of ${\Sigma }_i\otimes {\Sigma }_{-i}^{{\mathcal{T}}^{\prime }}$ (Definition 4 and Lemma 1).

Our main result states that one structure is contained in another if and only if there is a generalized type morphism from the former to the latter.

Theorem 1.

A mapping φ is a hierarchy morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$ if and only if it is a generalized type morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$. Hence, a type structure ${\mathcal{T}}^{\prime }$ contains $\mathcal{T}$ if and only if there is a generalized type morphism from $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$.

This result establishes an equivalence between generalized type morphisms and hierarchy morphisms. It thus provides a test that can be used to verify whether one type structure is contained in the other that does not refer to belief hierarchies.

While the characterization in Theorem 1 does not make reference to belief hierarchies, the result may not be easy to apply directly. The σ-algebras ${\mathcal{F}}_i^T$ are defined as the intersection of σ-algebras that are closed under $\mathcal{T}$, and there can be (uncountably) many of those. We next define a simple procedure to construct this σ-algebra.

Procedure 1.

(Type partitioning procedure) Consider a multi-agent uncertainty space $\mathcal{X}={(X_i,{\Sigma }_i)}_{i\in I}$ and a type structure $\mathcal{T}={(T_i,{\Sigma }_i^{\mathcal{T}},b_i)}_{i\in I}$ for $\mathcal{X}$.

Initial step: For every player i, let ${\mathcal{S}}_i^{\mathcal{T},0}=\{T_i,\varnothing \}$ be the trivial σ-algebra of his or her set of types $T_i$.

Inductive step: Suppose that $n\ge 1$ and that the sub-σ algebra ${\mathcal{S}}_i^{\mathcal{T},n-1}$ on $T_i$ has been defined for every player i. Then, for every player i, let ${\mathcal{S}}_i^{\mathcal{T},n}$ be the coarsest σ-algebra that contains the sets:

$$\{t_i\in T_i\mid b_i\left(t_i\right)\left(E\right)\ge p\}$$

for all $E\in {\Sigma }_i\otimes {\mathcal{S}}_{-i}^{\mathcal{T},n-1}$ and all $p\in [0,1]$. Furthermore, let ${\mathcal{S}}_i^{\mathcal{T},\infty }$ be the σ-algebra generated by the union ${\bigcup }_n{\mathcal{S}}_i^{\mathcal{T},n}$.

A simple inductive argument shows that ${\mathcal{S}}_i^{\mathcal{T},n}$ refines ${\mathcal{S}}_i^{\mathcal{T},n-1}$ for all players i and all n; clearly, ${\mathcal{S}}_i^{\mathcal{T},\infty }$ refines ${\mathcal{S}}_i^{\mathcal{T},n}$ for any n. The next result shows that the type partitioning procedure delivers the σ-algebras that are generated by the hierarchy mappings.

Proposition 2.

Fix a type structure $\mathcal{T}$, and let $i\in I$. Then, ${\mathcal{S}}_i^{\mathcal{T},\infty }=\sigma \left(h_i^{\mathcal{T}}\right)$ and ${\mathcal{S}}_i^{\mathcal{T},n}=\sigma \left(h_i^{\mathcal{T},n}\right)$ for all $n\ge 1$. Therefore, ${\mathcal{S}}_i^{\mathcal{T},\infty }={\mathcal{F}}_i^{\mathcal{T}}$.

Hence, we can use the type partitioning procedure to construct the σ-algebras, which we need for our characterization result (Theorem 1). Heifetz and Samet [24] consider a similar procedure in the context of knowledge spaces to show that a universal space does not exist for that setting. The procedure also has connections with the construction in Kets [22] of type structures that describe the beliefs of players with a finite depth of reasoning. In the next section, we use Theorem 1 and the type partitioning procedure to characterize the types that generate the same belief hierarchies.

5. Characterizing Types with the Same Belief Hierarchy

We can use the results in the previous section to provide simple tests to determine whether two types, from the same type structure or from different structures, generate the same belief hierarchy. We assume in this section that ${\mathcal{X}}_i$ is countably generated: there is a countable collection of subsets $E_i^n\subseteq X_i$, $n=1,2,\dots$, such that ${\Sigma }_i$ is the coarsest σ-algebra that contains these subsets. Examples of countably-generated σ-algebras include the discrete σ-algebra on a finite or countable set and the Borel σ-algebra on a finite-dimensional Euclidean space. Recall that an atom of a σ-algebra Σ on a set Y is a set $a\in \Sigma$, such that Σ does not contain a nonempty proper subset of a. That is, for any $a^{\prime }\in \Sigma$, such that $a^{\prime }\subseteq a$, we have $a^{\prime }=a$ or $a^{\prime }=\varnothing$.6

Lemma 2.

Let $i\in I$ and $n\ge 1$. The σ-algebras ${\mathcal{S}}_i^{\mathcal{T},n}$ and ${\mathcal{S}}_i^{\mathcal{T},\infty }$ are atomic. That is, for each $t_i\in T_i$, there are atoms $a_i^n\left(t_i\right)$ and $a_i^{\infty }\left(t_i\right)$ in ${\mathcal{S}}_i^{\mathcal{T},n}$ and ${\mathcal{S}}_i^{\mathcal{T},\infty }$, respectively, such that $t_i\in a_i^n\left(t_i\right)$ and $t_i\in a_i^{\infty }\left(t_i\right)$.

This result motivates the name “type partitioning procedure”: the procedure constructs a σ-algebra that partitions the type sets into atoms. Proposition 3 shows that these atoms contain precisely the types that generate the same higher-order beliefs.

Proposition 3.

For every player i, every $n\ge 1$ and every two types $t_i,t_i^{\prime }\in T_i$, we have that

(a) for every $n\ge 0$, types $t_i$ and $t_i^{\prime }$ generate the same n-th-order belief if and only if there is an atom $a_i^n\in {\mathcal{S}}_i^{\mathcal{T},n}$, such that $t_i,t_i^{\prime }\in a_i^n$;

(b) types $t_i$ and $t_i^{\prime }$ generate the same belief hierarchy if and only if there is an atom $a_i^{\infty }\in {\mathcal{S}}_i^{\mathcal{T},\infty }$, such that $t_i,t_i^{\prime }\in a_i^{\infty }$.

There is a connection between Proposition 3 and the work of Mertens and Zamir [13]. The work in [13] defines a type structure $\mathcal{T}$ to be non-redundant if for every player i, the σ-algebra ${\mathcal{F}}_i^{\mathcal{T}}$ separates types; see Liu ([17], Prop. 2) for a result that shows that this definition is equivalent to the requirement that there are no two types that generate the same belief hierarchy. Therefore, [13] already note the connection between the separating properties of ${\mathcal{F}}^{\mathcal{T}}$ and the question of whether types generate the same belief hierarchy. The contribution of Proposition 3 is to provide a simple procedure to construct the σ-algebra ${\mathcal{F}}^{\mathcal{T}}$ and to show that the separating sets can be taken to be atoms (as long as the σ-algebra on $X_i$ is countably generated).

Proposition 3 can also be used to verify whether two types from different type structures generate the same higher-order beliefs, by merging the two structures. Specifically, consider two different type structures, ${\mathcal{T}}^1={(T_i^1,{\Sigma }_i^1,b_i^1)}_{i\in I}$ and ${\mathcal{T}}^2={(T_i^2,{\Sigma }_i^2,b_i^2)}_{i\in I}$, for the same multi-agent uncertainty space $\mathcal{X}={(X_i,{\Sigma }_i)}_{i\in I}$. To check whether two types $t_i^1\in T_i^1$ and $t_i^2\in T_i^2$ induce the same belief hierarchy, we can merge the two type structures into one large type structure and then run the type partitioning procedure on this larger type structure. That is, define the type structure ${\mathcal{T}}^{*}={(T_i^{*},{\Sigma }_i^{*},b_i^{*})}_{i\in I}$ as follows. For each player i, let $T_i^{*}$ be the union of $T_i^1$ and $T_i^2$ (possibly made disjoint by replacing $T_i^1$ or $T_i^2$ with a homeomorphic copy), and define the σ-algebra ${\Sigma }_i^{*}$ on $T_i^{*}$ by:

$$E\in {\Sigma }_i^{*}\mathrm{if}\mathrm{and}\mathrm{only}\mathrm{if}E\cap T_i^1\in {\Sigma }_i^1\mathrm{and}E\cap T_i^2\in {\Sigma }_i^2.$$

Furthermore, define $b_i^{*}$ by:

$$b_i^{*}\left(t_i\right):=\left\{\begin{array}{cc}{b}_i^1\left(t_i\right),& \mathrm{if}{t}_i\in T_i^1\\ b_i^2\left(t_i\right),& \mathrm{if}{t}_i\in T_i^2\end{array}\right.$$

for all types $t_i\in T_i$.7 Applying the type partitioning procedure on ${\mathcal{T}}^{*}$ gives a σ-algebra ${\mathcal{S}}_i^{*,\infty }$ on $T_i^{*}$ for each player i. If $t_i^1\in T_i^1$ and $t_i^2\in T_i^2$ belong to the same atom of ${\mathcal{S}}_i^{*,\infty }$, then $t_i^1$ and $t_i^2$ induce the same belief hierarchy. The converse also holds, and hence, we obtain the following result.

Proposition 4.

Consider two type structures $T^1={(T_i^1,{\Sigma }_i^1,b_i^1)}_{i\in I}$ and $T^2={(T_i^2,{\Sigma }_i^2,b_i^2)}_{i\in I}.$ Let $T^{*}={(T_i^{*},{\Sigma }_i^{*},b_i^{*})}_{i\in I}$ be the large type structure defined above, obtained by merging the two type structures, and let ${\mathcal{S}}_i^{*,\infty },$ for a given player $i,$ be the σ-algebra on $T_i^{*}$ generated by the type partitioning procedure. Then, two types $t_i^1\in T_i^1$ and $t_i^2\in T_i^2$ induce the same belief hierarchy, if and only if, $t_i^1$ and $t_i^2$ belong to the same atom of $S_i^{*,\infty }.$

The type partitioning procedure is thus an easy and effective way to check whether two types, from possibly different type structures, generate the same belief hierarchy or not.

We expect our main results to apply more broadly. The proofs can easily be modified so that the main results extend to conditional probability systems in dynamic games [25], lexicographic beliefs [26], beliefs of players with a finite depth of reasoning [22,27] and the Δ-hierarchies introduced by Ely and Peski [16].

6. Finite Type Structures

When type structures are finite, our results take on a particularly simple and intuitive form. Say that a type structure $\mathcal{T}$ is finite if the type set $T_i$ is finite for every player i. For finite type structures, we can replace σ-algebras by partitions.

We first define the type partitioning procedure for the case of finite type structures. A finite partition of a set A is a finite collection $\mathcal{P}=\{P_1,\dots ,P_K\}$ of nonempty subsets $P_k\subseteq A$, such that ${\bigcup }_{k=1}^K{P}_k=A$ and $P_k\cap P_m=\varnothing$ whenever $k\ne m$. We refer to the sets $P_k$ as equivalence classes. For an element $a\in A,$ we denote by $\mathcal{P}\left(a\right)$ the equivalence class $P_k$ to which a belongs. The trivial partition of A is the partition $\mathcal{P}=\left\{A\right\}$ containing a single set; the full set A. For two partitions ${\mathcal{P}}^1$ and ${\mathcal{P}}^2$ on A, we say that ${\mathcal{P}}^1$ is a refinement of ${\mathcal{P}}^2$ if for every set $P^1\in {\mathcal{P}}^1$, there is a set $P^2\in {\mathcal{P}}^2$, such that $P^1\subseteq P^2$.

In the procedure, we recursively partition the set of types of an agent into equivalence classes, starting from the trivial partition and refining the previous partition with every step, until these partitions cannot be refined any further. We show that the equivalence classes produced in round n contain exactly the types that induce the same n-th order belief. In particular, the equivalence classes produced at the end contain precisely those types that induce the same (infinite) belief hierarchy.

Procedure 2

(Type partitioning procedure (finite type structures)). Consider a multi-agent uncertainty space $\mathcal{X}={(X_i,{\Sigma }_i)}_{i\in I}$ and a finite type structure $\mathcal{T}={(T_i,{\Sigma }_i^{\mathcal{T}},b_i)}_{i\in I}$ for $\mathcal{X}$.

Initial step: For every agent i, let ${\mathcal{P}}_i^0$ be the trivial partition of his or her set of types $T_i$.

Inductive step: Suppose that $n\ge 1$ and that the partitions ${\mathcal{P}}_i^{n-1}$ have been defined for every agent i. Then, for every agent i, and every $t_i\in T_i$,

$$\begin{array}{c}{\mathcal{P}}_i^n\left(t_i\right)=\{t_i^{\prime }\in T_i|b_i\left(t_i^{\prime }\right)(E_i\times P_{-i}^{n-1})=b_i\left(t_i\right)(E_i\times P_{-i}^{n-1})\\ forall{E}_i\in {\Sigma }_i,andall{P}_{-i}^{n-1}\in {\mathcal{P}}_{-i}^{n-1}\}.\end{array}$$

(2)

The procedure terminates at round n whenever ${\mathcal{P}}_i^n={\mathcal{P}}_i^{n-1}$ for every agent i.

In this procedure, ${\mathcal{P}}_{-i}^{n-1}$ is the partition of the set $T_{-i}$ induced by the partitions ${\mathcal{P}}_j^{n-1}$ on $T_j$. Again, it follows from a simple inductive argument that ${\mathcal{P}}_i^n$ is a refinement of ${\mathcal{P}}_i^{n-1}$ for every player i and every n. Note that if the total number of types, viz., ${\sum }_{i\in I}\left|T_i\right|$, equals N, then the procedure terminates in at most $N-\left|I\right|$ steps. We now illustrate the procedure by means of an example.

Example 1.

Consider the first type structure $\mathcal{T}=(T_1,T_2,{\Sigma }_1,{\Sigma }_2,b_1,b_2)$ from Table 1.

Initial step: Let ${\mathcal{P}}_1^0$ be the trivial partition of the set of types $T_1$, and let ${\mathcal{P}}_2^0$ be the trivial partition of the set of types $T_2$. That is,

$${\mathcal{P}}_1^0=\left\{\{t_1,t_1^{\prime },t_1^{″}\}\right\}and{\mathcal{P}}_2^0=\left\{\{t_2,t_2^{\prime },t_2^{″}\}\right\}.$$

Round 1: By Equation (2),

$$\begin{array}{c}{\mathcal{P}}_1^1\left(t_1\right)=\{{\tau }_1\in T_1|\\ b_1\left({\tau }_1\right)(\left\{c\right\}\times T_2)=b_1\left(t_1\right)(\left\{c\right\}\times T_2)=\frac{1}{2},\\ b_1\left({\tau }_1\right)(\left\{d\right\}\times T_2)=b_1\left(t_1\right)(\left\{d\right\}\times T_2)=\frac{1}{2}\}\\ =\{t_1,t_1^{\prime },t_1^{″}\},\end{array}$$

which implies that:

$${\mathcal{P}}_1^1={\mathcal{P}}_1^0=\left\{\{t_1,t_1^{\prime },t_1^{″}\}\right\}.$$

At the same time,

$$\begin{array}{c}{\mathcal{P}}_2^1\left(t_2\right)=\{{\tau }_2\in T_2|\\ b_2\left({\tau }_2\right)(\left\{e\right\}\times T_1)=b_2\left(t_2\right)(\left\{e\right\}\times T_1)=\frac{3}{4},\\ b_2\left({\tau }_2\right)(\left\{f\right\}\times T_1)=b_2\left(t_2\right)(\left\{f\right\}\times T_1)=\frac{1}{4}\}\\ =\{t_2,t_2^{″}\}\end{array}$$

which implies that ${\mathcal{P}}_2^1\left(t_2^{\prime }\right)=\left\{t_2^{\prime }\right\},$ and hence:

$${\mathcal{P}}_2^1=\{\{t_2,t_2^{″}\},\left\{t_2^{\prime }\right\}\}.$$

Round 2: By Equation (2),

$$\begin{array}{c}{\mathcal{P}}_1^2\left(t_1\right)=\{{\tau }_1\in T_1|\\ b_1\left({\tau }_1\right)(\left\{c\right\}\times \{t_2,t_2^{″}\})=b_1\left(t_1\right)(\left\{c\right\}\times \{t_2,t_2^{″}\})=\frac{1}{2},\\ b_1\left({\tau }_1\right)(\left\{c\right\}\times \left\{t_2^{\prime }\right\})=b_1\left(t_1\right)(\left\{c\right\}\times \left\{t_2^{\prime }\right\})=0,\\ b_1\left({\tau }_1\right)(\left\{d\right\}\times \{t_2,t_2^{″}\})=b_1\left(t_1\right)(\left\{d\right\}\times \{t_2,t_2^{″}\})=0,\\ b_1\left({\tau }_1\right)(\left\{d\right\}\times \left\{t_2^{\prime }\right\})=b_1\left(t_1\right)(\left\{d\right\}\times \left\{t_2^{\prime }\right\})=\frac{1}{2}\}\\ =\{t_1,t_1^{\prime }\},\end{array}$$

which implies that ${\mathcal{P}}_1^2\left(t_1^{″}\right)=\left\{t_1^{″}\right\}$, and hence:

$${\mathcal{P}}_1^2=\{\{t_1,t_1^{\prime }\},\left\{t_1^{″}\right\}\}.$$

Since ${\mathcal{P}}_1^1={\mathcal{P}}_1^0$, we may immediately conclude that:

$${\mathcal{P}}_2^2={\mathcal{P}}_2^1=\{\{t_2,t_2^{″}\},\left\{t_2^{\prime }\right\}\}.$$

Round 3: As ${\mathcal{P}}_2^2={\mathcal{P}}_2^1$, we may immediately conclude that:

$${\mathcal{P}}_1^3={\mathcal{P}}_1^2=\{\{t_1,t_1^{\prime }\},\left\{t_1^{″}\right\}\}.$$

By Equation (2),

$$\begin{array}{c}{\mathcal{P}}_2^3\left(t_2\right)=\{{\tau }_2\in T_2|\\ b_2\left({\tau }_2\right)(\left\{e\right\}\times \{t_1,t_1^{\prime }\})=b_2\left(t_2\right)(\left\{e\right\}\times \{t_1,t_1^{\prime }\})=\frac{3}{4},\\ b_2\left({\tau }_2\right)(\left\{e\right\}\times \left\{t_1^{″}\right\})=b_2\left(t_2\right)(\left\{e\right\}\times \left\{t_1^{″}\right\})=0,\\ b_2\left({\tau }_2\right)(\left\{f\right\}\times \{t_1,t_1^{\prime }\})=b_2\left(t_2\right)(\left\{f\right\}\times \{t_1,t_1^{\prime }\})=0,\\ b_2\left({\tau }_2\right)(\left\{f\right\}\times \left\{t_1^{″}\right\})=b_2\left(t_2\right)(\left\{f\right\}\times \left\{t_1^{″}\right\})=\frac{1}{4}\}\\ =\{t_2,t_2^{″}\},\end{array}$$

which implies that ${\mathcal{P}}_2^3\left(t_2^{\prime }\right)=\left\{t_2^{\prime }\right\},$ and hence,

$${\mathcal{P}}_2^3=\{\{t_2,t_2^{″}\},\left\{t_2^{\prime }\right\}\}={\mathcal{P}}_2^2.$$

As ${\mathcal{P}}_1^3={\mathcal{P}}_1^2$ and ${\mathcal{P}}_2^3={\mathcal{P}}_2^2$, the procedure terminates at Round 3. The final partitions of the types are thus given by:

$${\mathcal{P}}_1^{\infty }=\{\{t_1,t_1^{\prime }\},\left\{t_1^{″}\right\}\}\mathrm{and}{\mathcal{P}}_2^{\infty }=\{\{t_2,t_2^{″}\},\left\{t_2^{\prime }\right\}\}.$$

The reader may check that all types within the same equivalence class indeed induce the same belief hierarchy. That is, $t_1$ induces the same belief hierarchy as $t_1^{\prime }$, and $t_2$ induces the same belief hierarchy as $t_2^{″}$. Moreover, $t_1$ and $t_1^{″}$ induce different belief hierarchies, and so do $t_2$ and $t_2^{\prime }$.

Our characterization result for the case of finite type structures states that the type partitioning procedure characterizes precisely those groups of types that induce the same belief hierarchy. We actually prove a little more: we show that the partitions generated in round n of the procedure characterize exactly those types that yield the same n-th order belief.

Proposition 5

(Characterization result (finite type structures)). Consider a finite type structure $\mathcal{T}={(T_i,{\Sigma }_i,b_i)}_{i\in I},$ where ${\Sigma }_i$ is the discrete σ-algebra on $T_i$ for every player i. For every agent i, every $n\ge 1$ and every two types $t_i,t_i^{\prime }\in T_i$, we have that

(a) $h_i^{\mathcal{T},n}\left(t_i\right)=h_i^{\mathcal{T},n}\left(t_i^{\prime }\right),$ if and only if, $t_i^{\prime }\in {\mathcal{P}}_i^n\left(t_i\right)$;

(b) $h_i^{\mathcal{T}}\left(t_i\right)=h_i^{\mathcal{T}}\left(t_i^{\prime }\right),$ if and only if, $t_i^{\prime }\in {\mathcal{P}}_i^{\infty }\left(t_i\right)$.

The proof follows directly from Proposition 3 and is therefore omitted. As before, this result can be used to verify whether two types from different type structures generate the same belief hierarchies, by first merging the two type structures and then running the type partitioning procedure on this “large” type structure.