Pure-strategy Nash equilibria in large games: characterization and existence

Abstract

In this paper, we first characterize pure-strategy Nash equilibria in large games restricted with countable actions or countable payoffs. Then, we provide a counterexample to show that there is no such characterization when the agent space is an arbitrary atomless probability space (in particular, Lebesgue unit interval) and both actions and payoffs are uncountable. Nevertheless, if the agent space is a saturated probability space, the characterization result is still valid. Next, we show that the characterizing distributions for the equilibria exist in a quite general framework. This leads to the existence of pure-strategy Nash equilibria in three different settings of large games. Finally, we notice that our characterization result can also be used to characterize saturated probability spaces.

1 Introduction

A large game models its agent space with an atomless probability space which captures the predominant characteristic in a large conflicting economy whereby a single player is negligible but a group of players are influential. Over the past few decades, research on large games has been fruitful. Various results on the existence or non-existence of pure or mixed strategy Nash equilibria are determined in various settings of large games.¹

However, most studies on large games focus on showing the existence or non-existence of Nash equilibria but few pay attention to characterizing the equilibria, which, from our point of view, might be a loss in the literature. From this paper, we can see that a good characterization result helps explain equilibria from another perspective which enhances our understanding of them. Moreover, it can also provide an alternative and even easier way to show the existence of equilibria.²

We start by considering a generalized large game where the agent space is divided into countable (finite or countably infinite) different subgroups and each player’s payoff depends on her own action and the action distribution in each of the subgroups.³ In such a large game, a pure-strategy action profile that assigns an action to each player is called a (pure-strategy) Nash equilibrium if no player has the incentive to deviate from her assigned action. A (pure-strategy) equilibrium distribution is a distribution on the action space that is induced by a pure-strategy Nash equilibrium.

If such a large game is further restricted by having (i) a countable action space or (ii) a countable payoff space or (iii) a saturated probability space of agents, then a given distribution on the action space is shown to be an equilibrium distribution if and only if for every Borel, closed or open subset of actions, the players in each subgroup playing actions in it are no more than the players having a best response in the set. We also show through a counterexample that if both actions and payoffs are uncountable and the agent space is a general probability space, say the Lebesgue unit interval, then a similar characterization result is not valid.

Following these characterization results, we proceed to show the existence of the characterizing distribution for the equilibrium. Our result (Theorem 5) reveals that the characterizing distributions do exist and they exist in a much more general framework than the equilibria. In particular, there is no need to impose any further restrictions on the agent, action or payoff space other than the regular conditions that define a large game. This result, together with the previous characterization results, leads to the existence of pure-strategy Nash equilibria in three settings of large games under countability or saturation assumption. These existence results generalize or parallel the corresponding results in Khan and Sun (1995, 1999) and also include a new scenario showing the existence of pure-strategy Nash equilibria in large games endowed with at most countably many different payoffs while dropping any countability or saturation restrictions on the agent or action space.

Throughout the paper, we present quite a number of results on the characterization or existence of pure-strategy equilibria in large games. However, our paper is not tedious and our proofs are mostly elementary. This can be seen as another advantage in considering the existence of pure-strategy equilibria via characterization.⁴

The paper is organized as follows. Section 2 introduces the large game model. Section 3 presents all the characterization results. Section 4 shows the existence of characterizing equilibria and hence, also pure-strategy equilibria. Section 5 contains some concluding remarks.

2 Large game model

Let $(T,\fancyscript{T},\lambda )$ be an atomless probability space of players and $I$ a countable (finite or countably infinite) index set. Let $(T_i)_{i\in I}$ be a measurable partition of $T$ with positive $\lambda$-measures $(\alpha _i)_{i\in I}$, i.e., $\alpha _i=\lambda (T_i)>0$ for all $i\in I$. For each $i\in I$, let $\lambda _i$ be the re-scaled probability measure obtained from the restriction $\lambda |_{T_i}$ of $\lambda$ on $T_i$, namely $\lambda _i(S) = \lambda (S)/\lambda (T_i)$ for any measurable set $S$ in $T_i$. By introducing this partition, we imply that the players are divided into $I$ groups.

Let the action space, denoted by $A$, of the game be a Polish space with $\fancyscript{B}(A)$ its Borel $\sigma$-algebra and $\fancyscript{M}(A)$ the set of all Borel probability measures on $A$. Suppose that all the players in each group $i\in I$ choose their actions from a common compact subset $A_i$ of $A$. Without loss of generality, we assume that $(A_i)_{i\in I}$ are disjoint of each other.⁵ For ease of notation, we define an action correspondence $K:T\twoheadrightarrow A$ for all players such that $K(t)=A_i$ for all $t\in T_i$. Let $\fancyscript{M}(A_i)$ be the set of all Borel probability measures on $A_i$ endowed with the topology of weak convergence of probability measures and $\prod _{i\in I}\fancyscript{M}(A_i)$ the usual product space endowed with the product topology. For ease of notation, we let $\Theta := A\times \prod _{i\in I}\fancyscript{M}(A_i)$ and $\Theta _i:= A_i\times \prod _{i\in I}\fancyscript{M}(A_i)$, $i\in I$.⁶

The payoff function (or simply, payoff) of each player depends on her own action as well as on the distribution of actions played by the players in each of the groups. Mathematically, we let the space of payoffs be the space of all continuous real-valued functions on $\Theta$ which is denoted by $\mathcal C(\Theta )$ and endowed with the topology of compact convergence.

Definition 1

Given player space $T$ and action space $A$, a large game is a measurable mapping $U$ from $T$ to $\mathcal C(\Theta )$.⁷ A measurable function $f:T\rightarrow A$ is called a pure-strategy profile if $f(t)\in K(t)$ for all $t\in T$. A pure-strategy profile $f$ is called a pure-strategy (Nash) equilibrium if for $\lambda$-almost all $t\in T$,

$$\begin{aligned} U(t)[f(t),(\lambda _i f_i^{-1})_{i\in I}]\ge U(t)[a,(\lambda _i f_i^{-1})_{i\in I}]\text { for all } a\in K(t), \end{aligned}$$

where $f_i$ is the restriction of $f$ to $T_i$. A distribution $\mu \in \fancyscript{M}(A)$ is called an equilibrium distribution if there exists a pure-strategy equilibrium $f$ such that $\mu =\lambda f^{-1}$.

Given a pure-strategy profile $f: T\rightarrow A$ and its induced distribution $\mu :=\lambda f^{-1}$, let $f_i$ be the restriction of $f$ to $T_i$ and $\mu _i$ the re-scaled probability measure of $\mu$ on $A_i$. Since $(A_i)_{i\in I}$ are disjoint sets, $f_i^{-1}(B)=f^{-1}(B)$ for all $B\in A_i$ and hence, for any $B\in \fancyscript{B}(A_i)$, $\mu _i(B)=\frac{\mu (B)}{\mu (A_i)}=\frac{\lambda f^{-1}(B)}{\lambda f^{-1}(A_i)}=\frac{\lambda f_i^{-1}(B)}{\lambda f_i^{-1}(A_i)}=\frac{\lambda f_i^{-1}(B)}{\lambda (T_i)}=\lambda _i f_i^{-1}(B)$. Thus, we have $\mu _i=\lambda _i f_i^{-1}$ for all $i\in I$.

Recall that a correspondence $F$ from $T$ to $A$, denoted by $F: T\twoheadrightarrow A$, is called measurable if for each closed subset $C$ of $A$, the set

$$\begin{aligned} F^{-1}(C):=\{t\in T: F(t)\cap C\ne \emptyset \} \end{aligned}$$

is measurable in ${\fancyscript{T}}$. A function $f$ from $T$ to $A$ is said to be a measurable selection of $F$ if $f$ is measurable and $f (t)\in F(t)$ for all $t \in T$. When $F$ is measurable and closed valued, the classical Kuratowski-Ryll-Nardzewski Theorem [see e.g., Aliprantis and Border (1999, p 567)] shows that $F$ has a measurable selection.

Given an arbitrary probability measure $\mu \in \fancyscript{M}(A)$, the best responses of player $t$ facing the collective behavior $\mu$ is given by

$$\begin{aligned} B^\mu (t):=\arg \max _{a\in K(t)} U(t)(a,(\mu _i)_{i\in I}) \end{aligned}$$

where $\mu _i$ is the re-scaled probability measure of $\mu$ on $A_i$. By the Measurable Maximum Theorem [Aliprantis and Border (1999, p 570)], $B^\mu$ is a measurable correspondence from $T$ to $A$, has nonempty compact values and admits a measurable selection. Let $B^\mu _i: T_i\twoheadrightarrow A_i$ be the restriction of $B^\mu$ to $T_i$.

3 Characterizing large games

Unless otherwise specified, throughout this section, we follow all the notations defined in the last section.

3.1 Large games with countable actions

Our first result is on large games with countable actions.

Theorem 1

Let $\mu \in \fancyscript{M}(A)$ and $\mu _i$ the re-scaled probability measure of $\mu$ on $A_i$. If the action space $A$ in the large game $U$ is countable, then the following statements are equivalent:

• (i) $\mu$ is an equilibrium distribution;

• (ii) for each $i\in I$, $\mu _i(C)\le \lambda _i [({B_i^\mu })^{-1}(C)]$ for every subset $C$ in $A_i$;

• (iii) for each $i\in I$, $\mu _i(D)\le \lambda _i [({B_i^\mu })^{-1}(D)]$ for every finite subset $D$ in $A_i$.

To prove this theorem, we need the following lemma from Khan and Sun (1995), which is a special case of the famous marriage theorem offered by Bollobas and Varopoulos (1975).⁸

Lemma 1

(Khan and Sun 1995, Theorem 4)⁹ Let $(T,\mathcal {T},\lambda )$ be an atomless probability space, $I$ a countable index set, $(T_i)_{i \in I}$ a family of sets in $\mathcal {T}$ and $(\alpha _i)_{i \in I}$ a family of non-negative numbers. Then, the following two statements are equivalent

• $\lambda (\bigcup _{i \in {D}}T_i )\ge {\sum _{i \in {D}}\alpha _i}$ for all finite subsets $D$ of $I$;

• there is a family of sets, $(S_i)_{i \in I}$, in $\mathcal {T}$ such that for all $i,j\in I, i\ne j,$ one has $S_i \subseteq T_i$, $\lambda (S_i)=\alpha _i$ and $S_i\cap S_j = \emptyset$.

Proof of Theorem 1

(i)$\Rightarrow$(ii): Let $\mu$ be an equilibrium distribution. Then by definition, there exists a Nash equilibrium $f : T \rightarrow A$ such that $\mu =\lambda f^{-1}$. Notice that for each $i\in I$, $f_i(t)\in B_i^{\mu }(t)$ for all $t \in T_i$. Thus, for any $i\in I$ and for every $C\subseteq A_i$,

$$\begin{aligned} \mu _i(C)= & {} \lambda _i(f_i^{-1}(C))=\lambda _i\Big (\{t\in T_i: f_i(t)\in C\}\Big )\\\le & {} \lambda _i(\{t\in T_i: B_i^{\mu }(t)\cap C\ne \emptyset \})=\lambda _i\left[ ({B_i^\mu })^{-1}(C)\right] . \end{aligned}$$

(ii) $\Rightarrow$ (iii): It is obvious.

(iii)$\Rightarrow$(i): Suppose (iii) holds. Fix an arbitrary $i\in I$. Since $A$ is a countable set, it can be written as $A:=\{a_1, a_2,\ldots \}=\{a_j\}_{j\in \mathbb N}$. For each $j\in \mathbb N$, let $\beta _j:=\mu _i(\{a_j\})$ and $T_i^j:=(B_i^\mu )^{-1}(\{a_j\})=\{t\in T_i: a_j\in B_i^\mu (t)\}$. Let $D$ be an arbitrary finite subset of $\mathbb N$. Observe that $(B_i^\mu )^{-1}(\bigcup _{j\in D}\{a_j\})=\bigcup _{j\in D}T_i^j$. Statement (iii) tells that $\sum _{j\in D}\beta _j=\mu _i(\bigcup _{j\in D}\{a_j\}) \le \lambda _i(\bigcup _{j\in D}T_i^j)$. Thus, by Lemma 1, there exists a family of sets, $(S_j)_{j \in \mathbb N}$, such that for all $j,k\in \mathbb N, k\ne j,$ one has $S_j\subseteq T_i^j$, $\lambda _i(S_j)=\beta _j$ and $S_j\cap S_k = \emptyset$.

Now, define a measurable function $h_i:T_i\rightarrow A$ such that for all $j\in \mathbb N$ and for all $t\in S_j, h_i(t)=a_j$. Since for any $j\in \mathbb N$, $t\in S_j$ implies that $a_j\in (B_i^\mu )(t)$, we have $h_i(t)\in B_i^\mu (t)$ for all $t\in T$. Furthermore, $\lambda _i(h_i^{-1}(\{a_j\}))=\lambda _i(S_j)=\beta _j=\mu _i(\{a_j\})$ for all $j\in \mathbb N$, which implies $\lambda _i h_i^{-1}=\mu _i$. Repeat the above arguments for all $i\in I$ and define a measurable function $h: T\rightarrow A$ by letting $h(t)=h_i(t)$ if $t\in T_i$. Thus, it is clear that $h$ is a pure strategy Nash equilibrium and $\mu =(\mu _i)_{i\in \mathbb N}=\lambda h^{-1}$ is the equilibrium distribution induced by $h$. $\square$

Remark 1

Note that $\mu$ is an equilibrium distribution if and only if there exists a measurable selection $f$ of $B^\mu$ such that $\mu =\lambda f^{-1}$. Hence, if $\mu$ is an equilibrium distribution, then $\mu _i(C)=\lambda _i(f_i^{-1}(C))=\lambda _i\{t\in T_i: f_i(t)\in C\}$, is simply the proportion of players playing their actions in $C$. Therefore, the above theorem literally says that a distribution on the product action space is an equilibrium distribution if and only if for any subset or any finite subset of the actions, there are fewer players in each group playing their actions in the subset than having a best response in it. It should be noted that the case that $|I|=1$ and $A$ is finite in our theorem is the main result in Blonski (2005).

3.2 Large games with countable payoffs

In the last section, we characterize large games with a countable set of actions. One may wonder if we can allow an action space without the countability restriction. The answer is “yes” provided that there are only countably many payoff functions in the game or equivalently, all the players in each group play a common payoff function.

Definition 2

The players in a large game $U$ is said to be homogeneous if for each group $i\in I$, $U(t)$ is same for all $t\in T_i$.

Since the total number of elements in a countable collection of countable sets is still countable, this definition of homogeneity is equivalent to assuming that in each group, there are at most countably many payoff functions for its players.

Theorem 2

Let $\mu \in \fancyscript{M}(A)$ and $\mu _i$ the re-scaled probability measure of $\mu$ on $A_i$. If the players in the large game $U$ are homogeneous, then the following statements are equivalent:

• (i) $\mu$ is an equilibrium distribution;

• (ii) for each $i\in I$, $\mu _i(C)\le \lambda _i [({B_i^\mu })^{-1}(C)]$ for every Borel subset $C$ in $A_i$;

• (iii) for each $i\in I$, $\mu _i(D)\le \lambda _i [({B_i^\mu })^{-1}(D)]$ for every closed subset $D$ in $A_i$;

• (iv) for each $i\in I$, $\mu _i(O)\le \lambda _i [({B_i^\mu })^{-1}(O)]$ for every open subset $O$ in $A_i$.

To prove this theorem, we first introduce the following well known lemma which can be obtained by appropriately adjusting the proof of Theorem 3.11 in Skorokhod (1956).

Lemma 2

(Skorokhod 1956, Theorem 3.11) Let $(T,\mathcal T, \lambda )$ be an atomless probability space and $A$ a Polish space. Then, for any $\nu \in \fancyscript{M}(A)$, there exists a measurable function $f:T \rightarrow A$ such that $\lambda f^{-1}=\nu$.

Proof of Theorem 2

Firstly, we want to make sure that for each $i\in I$ and every $C\in \fancyscript{B}(A_i)$, $( B_i^\mu )^{-1}(C)$ is measurable. To see this, fix any $i\in I$. The homogeneous condition, i.e., $U(t)$ is fixed for all $t\in T_i$, implies that $B_i^\mu (t)$ is the same for all $t\in T_i$. Thus, we can let $C_i:=B_i^\mu (t)$ for all $t\in T_i$. Then, for any $C\in \fancyscript{B}(A_i)$, we have

$$\begin{aligned} \left( B_i^\mu \right) ^{-1}(C)=\left\{ t\in T_i: B_i^\mu (t)\cap C\ne \emptyset \right\} =\left\{ \begin{array}{ll} T_i &{} \quad \text{ if } \quad C_i \cap C\ne \emptyset ;\\ \emptyset &{} \quad \text{ otherwise }, \end{array} \right. \end{aligned}$$

which is measurable.

(i)$\Rightarrow$(ii): Suppose $\mu$ is now an equilibrium distribution. By assumption, there exists a Nash equilibrium $f : T \rightarrow A$ such that $\mu =(\lambda _i f_i^{-1})_{i\in I}$ and $f(t)\in B^\mu (t)$ for all $t \in T$. Therefore, for any $C\in \fancyscript{B}(A_i)$,

$$\begin{aligned} \mu _i(C)= & {} \left( \lambda _if_i^{-1}\right) (C)=\lambda _i\Big (\{t\in T_i: f_i(t)\in C\}\Big )\\\le & {} \lambda _i\left( \{t\in T_i: B_i^\mu (t)\cap C\ne \emptyset \}\right) \\= & {} \lambda _i\left[ \left( B_i^\mu \right) ^{-1}(C)\right] . \end{aligned}$$

(ii) $\Rightarrow$ (iii): It is obvious.

(iii) $\Rightarrow$ (iv): Let $O$ be an open set in $A_i$. Then there is an increasing sequence $\{F_n\}^\infty _{n=1}$ of closed sets in $A_i$ such that $O = {\bigcup \limits ^\infty _{n=1}} F_n$. For each $n$, we have $( B_i^\mu )^{-1}(F_n) \subseteq ( B_i^\mu )^{-1}(O)$, which implies that $\mu _i(F_n) \le \lambda _i[( B_i^\mu )^{-1}(F_n)] \le \lambda _i[( B_i^\mu )^{-1}(O)].$ Thus, $\mu _i (O) \le \lambda _i[( B_i^\mu )^{-1}(O)].$

It remains to show (iv) $\Rightarrow$ (i). Recall that for all $i\in I$, the set $C_i:=B_i^\mu (t)$ for any $t\in T_i$ is compact and hence, also complete and separable. Fix any $i\in \mathbb N$. By the fact that the set $(A_i-C_i)$ is open, we have

$$\begin{aligned} 1-\mu _i(C_i)=\mu _i(A_i-C_i)\le \lambda _i[ ( B_i^\mu )^{-1}(A_i-C_i)]=0, \end{aligned}$$

(1)

which gives $\mu _i(C_i)=1 \text { for all } i$. Therefore, by Lemma 2, there exists a measurable function $f_i: T_i\rightarrow C_i$ such that $\mu _i=\lambda _i {f_i}^{-1}$. By definition, $f_i\in B_i^\mu$.

Define $f: T\rightarrow A$ by letting $f(t)=f_i(t)$ for all $t\in T_i$ and all $i\in I$. Thus, $f$ is a measurable selection of $B^\mu$ and $\mu =(\mu _i)_{i\in I}=(\lambda _i f_i^{-1})_{i\in I}$ is an equilibrium distribution. $\square$

3.3 Large games without countability restrictions

Now one may ask, does such a characterization result exist for a large game without the countability restriction on action or payoff space? Our next result gives a negative answer to this question.

Theorem 3

Let $\mu \in \fancyscript{M}(A)$ and $\mu _i$ the re-scaled probability measure of $\mu$ on $A_i$. There exists a large game $U$ such that the following statements are not equivalent:

• (i) $\mu$ is an equilibrium distribution of $U$;

• (ii) for each $i\in I$, $\mu _i(C)\le \lambda _i [({B_i^\mu })^{-1}(C)]$ for every Borel subset $C$ in $A_i$.

To show this result, we need only to give one counterexample.

Example 1

Consider a large game $U$ given as follows. Let the space of players be the Lebesgue unit interval $T=[0,1]$ endowed with its Boral $\sigma$-algrbra and the Lebesgue measure $\lambda$. Let the action space A be the interval $[-1,1]$ and let the payoffs be given by $U(t)(a,\mu )=-|t-|a||$ where $t\in T$, $a\in A$ and $\mu \in \fancyscript{M}(A)$.¹⁰

Let $\eta$ be the uniform distribution on $[-1,1]$. Thus, given $\eta$, the best response set for player $t$ is:

$$\begin{aligned} B^{\eta }(t)=\arg \max _{a\in [-1,1]} U(t)(a,\eta ) = \{t, -t\}. \end{aligned}$$

Let C be an arbitrary Borel subset in A and let $C_1=C\cap (0,1]$ and $C_2=C\cap [-1,0]$. Let $\tilde{C}_2=\{t\in [0,1]: -t\in C_2\}$ be the positive reflection of $C_2$ on interval $[0,1]$. Then,

$$\begin{aligned} \lambda [{(B^{\eta })}^{-1}(C)]= & {} \lambda \Big ( \{t\in T : B^{\eta }(t)\cap C \ne \emptyset \}\Big )\\= & {} \lambda \{t\in T : t \in C_1 \text { or }-t \in C_2\}\\\ge & {} \max \{\lambda (C_1),\lambda (\tilde{C}_2)\}\\\ge & {} \frac{\lambda (C_1)+\lambda (\tilde{C}_2)}{2}. \end{aligned}$$

Since $\eta$ is the uniform distribution on $[-1,1]$, $\eta (C)=\eta (C_1\bigcup C_2)=\eta (C_1)+\eta (C_2)=\frac{\lambda (C_1)+\lambda (\tilde{C}_2)}{2}$. Therefore, we have

$$\begin{aligned} \lambda [{(B^{\eta })}^{-1}(C)]\ge \eta (C). \end{aligned}$$

Now we shall prove by contradiction that $\eta$ cannot be an equilibrium distribution.

Suppose $\eta$ is an equilibrium distribution. Then, by definition, there exists a measurable selection $f$ of $B^{\eta }$ such that $\lambda f^{-1}=\eta$ and $f(t)\in B^{\eta }(t)$ for all $t\in T$. Let $D=f^{-1}((0,1])$. Then,

$$\begin{aligned} f(t)=\left\{ \begin{array}{ll} t, &{} \quad t \in D\\ -t, &{}\quad t \notin D.\\ \end{array} \right. \end{aligned}$$

Note that $f^{-1}(D)=\{t: f(t)\in D\}=\{t: t\in D\}=D$. Hence, $\lambda (D)=\lambda (f^{-1}(D)=\eta (D)= \frac{\lambda (D)}{2}$. So $\lambda (D)=0$.

Now Let $E=f^{-1}([-1,0])$. Then, $E$ is the complement event of $D$ on $T$, i.e. $E=T\setminus D$. Hence $\lambda (E)=\lambda (T\setminus D)=\lambda (T)-\lambda (D)=1$. On the other hand because $\lambda f^{-1}=\eta$, $\lambda (E)=\lambda (f^{-1}([-1,0]))=\eta ([-1,0])=1/2$. This is a contradiction. Therefore, $\eta$ cannot be an equilibrium distribution.

3.4 Large games with agent space being a saturated probability space

Although a general characterization result for equilibria in large games does not hold as we have seen from last section, we notice that if we assume the agent space to be a saturated probability space, then we can still have a similar characterization result. This result follows easily from the work of Sun (1996) and Keisler and Sun (2009).

We first introduce the concept of a saturated probability space.¹¹

Definition 3

(i) A probability space $(T,\fancyscript{T},\lambda )$ is called essentially countably generated or countably generated (modulo null sets) if there is a countable set $\{X_n\in \fancyscript{T}: n\in \mathbb N\}$ such that for any $Y\in \fancyscript{T}$, there is a set $Y'$ in the $\sigma$-algebra generated by $\{X_n: n\in \mathbb N\}$ with $\lambda (Y\triangle Y')=0$, where $\triangle$ denotes the symmetric difference in $\fancyscript{T}$.

(ii) A probability space $(T,\fancyscript{T},\lambda )$ is called saturated if for any subset $C\in T$ with $\lambda (C) > 0$, the re-scaled probability space $(C, \fancyscript{T}_C, \lambda _C)$ is not countably-generated, where $\fancyscript{T}_C:= \{C\cap C': C'\in \fancyscript{T}\}$ and $\lambda _C$ is the probability measure derived from the restriction of $\lambda$ to $\fancyscript{T}_C$.

Note that in our Example 1, the Lebesgue unit interval $[0, 1]$ endowed with its $\sigma$-algebra of Lebesgue measurable sets and the Lebesgue measure, is a countably-generated probability space and hence, not saturated.

Theorem 4

If the agent space $(T,\fancyscript{T},\lambda )$ of a large game $U$ is a saturated probability space, then the four statements (i)-(iv) in Theorem 2 are still equivalent when the homogeneous condition is removed.

To prove the above theorem, we shall refer to the following lemma which is analogous to Proposition 3.5 of Sun (1996)

Lemma 3

Let $F$ be a closed valued measurable correspondence from a saturated probability space $(\Omega , \fancyscript{F}, P)$ to a Polish space X. Let $\nu$ be a Borel probability measure on $X$. Then the following statements are equivalent:

• (i) there is a measurable selection $f$ of $F$ such that $Pf^{-1}=\nu$;

• (ii) for every Borel set C in X, $\nu (C)\le P(F^{-1}(C))$;

• (iii) for every closed set D in X, $\nu (D)\le P(F^{-1}(D))$;

• (iv) for every open set O in X, $\nu (O)\le P(F^{-1}(O))$.

Proof

This lemma is analogous to Proposition 3.5 of Sun (1996). It follows easily by combining Theorem 3.6 (P3) of Keisler and Sun (2009) and Proposition 3.5 of Keisler and Sun (2009). $\square$

Proof of Theorem 4

For any $i\in I$, notice that $B_i^\mu$ is a compact valued (and hence closed valued) measurable correspondence from an atomless Loeb probability space $(T_i, \fancyscript{T}_i, \lambda _i)$ to the Polish space $A$. Thus, by applying Lemma 3 to $B_i^\mu$, we see that $\mu _i=\lambda _i f_i^{-1}$ for some $f_i$ being a measurable selection of $B_i^\mu$ if and only if for every Borel (closed, or open) set $H$ in $A_i$, $\mu _i (H)\le \lambda _i[ ({B_i^\mu })^{-1}(H)]$.

Since the above result holds for all $i\in I$, thus $\mu =(\mu _i)_{i\in I}$ is an equilibrium distribution if and only if for each $i\in I$ and every Borel (closed, or open) set $H$ in $A_i$, $\mu _i (H)\le \lambda _i[ ({B_i^\mu })^{-1}(H)]$. $\square$

4 Existence of equilibria in large games

The above characterization results enable us to understand equilibria in large games from another perspective. Moreover, these characterization results also enable us to prove the existence of pure-strategy equilibria by showing the existence of characterizing equilibria distributions.

Theorem 5

There exists in every large game $U$ a distribution $\mu \in \fancyscript{M}(A)$ such that for each $i\in I$,

$$\begin{aligned} \mu _i(E)\le \lambda _i [({B_i^\mu })^{-1}(E)]\text { for every Borel set }E\text { in }A_i. \end{aligned}$$

where $\mu _i$ is the re-scaled probability measure of $\mu$ on $A_i$.

Proof of Theorem 5

Let $\mu _i\in M(A_i)$ for all $i\in I$. For easy notation, we use $\bar{\mu }$ to denote the distribution vector $(\mu _1,\mu _2,\cdots )$, i.e., $\bar{\mu }:=(\mu _i)_{i\in I}$. Also, define $B^{\bar{\mu }}(t):=\arg \max _{a\in K(t)} U(t)(a,(\mu _i)_{i\in I})$ which is the best response correspondence.

Now for each group $i\in I$, let $B_i^{\bar{\mu }}: T_i\twoheadrightarrow A_i$ be the restriction of $B^{\bar{\mu }}$ to $T_i$ and $U_i:T_i\rightarrow \mathcal C(\Theta )$ the restriction of $U$ to $T_i$. Define $V_i: T_i\rightarrow \mathcal C(\Theta _i)$ by letting $V_i(t)=U_i(t)|_{\Theta _i}$, where $U_i(t)|_{\Theta _i}$ is the restriction of $U_i(t)$ to $\Theta _i$ and $\mathcal C(\Theta _i)$ is also endowed with the topology of compact convergence. Thus, we also have $B_i^{\bar{\mu }}(t)=\arg \max _{a\in A_i} V_i(t)(a,(\mu _i)_{i\in I})$. As mentioned earlier in the paper, each topological space is endowed with its Borel $\sigma$-algebra on which we define the measurability.

We next claim that $V_i$ is also measurable. To verify this, we first define $W_i: \mathcal C(\Theta )\rightarrow \mathcal C(\Theta _i)$ by letting $W_i(u)=u|_{\Theta _i}$ for all $u\in \mathcal C(\Theta )$. Thus, $V_i=W_i\circ U_i$ and hence, we only need to show that $W_i$ is measurable. Let $d$ be the usual metric on $\mathbb R$. Given an element $f$ of $\mathcal C(\Theta _i)$, a compact subset $D$ of $\Theta _i$ and a number $\epsilon >0$, let $B_{\Theta _i}(f,D,\epsilon )=\{g\in \mathcal C(\Theta _i): \sup \{d(f(x),g(x))|x\in D\}<\epsilon \}$. Thus, the sets $B_{\Theta _i}(f,D,\epsilon )$ form a basis for the topology of compact convergence on $\mathcal C(\Theta _i)$.(See, eg, p 283 in Munkres (2000)) Hence, we only need to show that $W_i^{-1}(B_{\Theta _i}(f,D,\epsilon ))$ is measurable. To see this, let $\Delta =\{u\in \mathcal C(\Theta ): u|_D=f\}$ and note that

$$\begin{aligned} W_i^{-1}(B_{\Theta _i}(f,D,\epsilon ))= & {} \{h\in \mathcal C(\Theta ): h|_{\Theta _i}\in B_{\Theta _i}(f,D,\epsilon )\} \\= & {} \{h\in \mathcal C(\Theta ): \sup \{d(f(x),h(x))|x\in D\}<\epsilon \} \\= & {} \bigcup _{u\in \Delta }\{h\in \mathcal C(\Theta ): \sup \{d(u(x),h(x))|x\in D\}<\epsilon \}\\= & {} \bigcup _{u\in \Delta }B_{\Theta }(u,D,\epsilon ). \end{aligned}$$

Since $B_{\Theta }(u,D,\epsilon )$ is open by the definition of the topology on $\mathcal C(\Theta )$, $W_i^{-1}(B_{\Theta _i}(f,D,\epsilon ))$ is also open and hence, measurable. Thus, our claim is verified.

For all $i\in I$, define $\Gamma _i^{\bar{\mu }}:\mathcal C(\Theta _i)\twoheadrightarrow A_i$ by letting $\Gamma _i^{\bar{\mu }}(u)=\arg \max _{a\in A_i} u(a,({\mu }_i)_{i\in I})$ for all $u\in \mathcal C(\Theta _i)$. Thus, we have $B_i^{\bar{\mu }}(t)=\Gamma _i^{\bar{\mu }}(V_i(t))$ for all $t\in T_i$. By the Berge’s Maximum Theorem, $\Gamma _i^{{\bar{\mu }}}$ is upper semicontinuous.¹² Thus, $(\Gamma _i^{{\bar{\mu }}})^{-1}(F)$ is measurable for all closed set $F \in A$.¹³ It is also straightforward to verify that $V_i^{-1}[(\Gamma _i^{{\bar{\mu }}})^{-1}(F)]= (B_i^{{\bar{\mu }}})^{-1}(F)$ for any closed set $F \in A$. Since $V_i$ is measurable, $\lambda _iV_i^{-1}$ is a Borel probability measure on $\mathcal C(\Theta _i)$.

Let $\bar{\eta }:=(\eta _i)_{i\in I}\in \prod _{i\in I}\fancyscript{M}(A_i)$. Define $\Phi : \prod _{i\in I}\fancyscript{M}(A_i)\twoheadrightarrow \prod _{i\in I}\fancyscript{M}(A_i)$ as

$$\begin{aligned} \Phi ({\bar{\mu }})=\{{\bar{\eta }}: {\eta }_i(E)\le \lambda _i [ (B_i^{{\bar{\mu }}})^{-1}(E)] \text { for each } i\in I \text { and any } E \in \fancyscript{B}(A_i)\}. \end{aligned}$$

It is easy to see that $\Phi$ is nonempty,¹⁴ closed-valued and convex-valued.

Now we want to show that $\Phi$ is upper semicontinuous or, equivalently, has a closed graph. To this end, we choose a sequence $\{({\bar{\mu }}^m,{\bar{\eta }}^m)\}_{m\in \mathbb N}$ from $\left( \prod _{i\in I}\fancyscript{M}(A_i)\times \prod _{i\in I}\fancyscript{M}(A_i)\right)$ with ${\bar{\eta }}^m\in \Phi ({\bar{\mu }}^m)$ for each $m$ and converging to $({\bar{\mu }}^0,{\bar{\eta }}^0)$. We need to show that ${\bar{\eta }}^0\in \Phi ({\bar{\mu }}^0)$.

Fix any $i\in I$. Let $F$ be a closed subset of $A_i$ and let $\Lambda _m:=({\Gamma _i^{{\bar{\mu }}^m}})^{-1}(F)$ and $\Lambda _0:=({\Gamma _i^{{\bar{\mu }}^0}})^{-1}(F)$. Since $\Gamma _i^{{\bar{\mu }}^0}$ is upper semicontinuous and $F$ is closed, $\Lambda _0$ is also closed. Since $\Theta _i$ is compact, $\mathcal C(\Theta _i)$ is metrizable and we let $\hat{d}$ be one of the compatible metrics on $\mathcal C(\Theta _i)$. For all $k=1,2,\ldots$, let $G_k=\{u\in \mathcal C(\Theta _i): \hat{d}(u,\Lambda _0)\}<\frac{1}{k}\}$.

Fix any $k$. We claim that $\Lambda _m\subset G_k$ for large enough $m$. To see this, let $u_m\in \Lambda _m$, which, by the definition of $\Lambda _m$, implies that there is an $a_m\in F$ such that $u_m(a_m,{\bar{\mu }}^m)=\max _{a\in A_i} u_m(a,{\bar{\mu }}^m)$. Since ${\bar{\mu }}^m\rightarrow {\bar{\mu }}^0$ and $u_m$ is uniformly continuous on $A_i\times \prod _{i\in I}\fancyscript{M}( A_i)$ ¹⁵, when $m$ is large enough, we have $|u_m(a_m,{\bar{\mu }}^0)-\max _{a\in A_i} u_m(a,{\bar{\mu }}^0)|< \frac{1}{k}$. Thus, it is straightforward to find a continuous real function $u_m'\in \mathcal C(\Theta _i)$ such that $u_m'(a_m,{\bar{\mu }}^0)=\max _{a\in A_i} u_m'(a,{\bar{\mu }}^0)=\max _{a\in A_i} u_m(a,{\bar{\mu }}^0)$ and $\hat{d}(u_m,u_m')<\frac{1}{k}$.¹⁶ Thus, $u_m'\in \Lambda _0$ and $u_m\in G_k$.

Hence, the above result and our hypothesis imply that ${\bar{\eta }}_i^m(F)\le \lambda _iV_i^{-1} (\Lambda _m)\le \lambda _iV_i^{-1} (G_k)$ for large enough $m$. Since ${\bar{\eta }}_i^m(F)\rightarrow {\bar{\eta }}_i^0(F)$, we have ${\bar{\eta }}_i^0(F)\le \lambda _iV_i^{-1}(G_k)$. Since $G_k\downarrow \Lambda _0$, we have ${\bar{\eta }}_i^0(F)\le \lambda _iV_i^{-1}(\Lambda _0)=\lambda _iV_i^{-1}[(\Gamma _i^{{\bar{\mu }}^0})^{-1}(F)]=\lambda _i [ (B_i^{{\bar{\mu }}^0})^{-1}(F)]$.

Now, we want to show the above result holds for all Borel set $E\in A$. To verify this, recall that every probability measure on a Polish space is regular.¹⁷ Therefore, we have

$$\begin{aligned} {\bar{\eta }}_i^0(E)= & {} {\bar{\eta }}_i^0(E\cap A_i) = \sup \{{\bar{\eta }}_i^0(F): F \text { is closed and } F\subseteq E\cap A_i\} \\\le & {} \sup \{\lambda _i[({B_i^{{\bar{\mu }}^0}})^{-1}(F)]: F \text { is closed and } F\subseteq E\cap A_i\} \\\le & {} \lambda _i[({B_i^{{\bar{\mu }}^0}})^{-1}(E\cap A_i)]=\lambda _i[({B_i^{{\bar{\mu }}^0}})^{-1}(E)]. \end{aligned}$$

Since the above arguments hold for all $i\in I$, we conclude that ${\bar{\eta }}^0\in \Phi ({\bar{\mu }}^0)$. Therefore $\Phi$ also has a closed graph. Hence, by the Ky Fan fixed point theorem in Fan (1952), there is a fixed point ${\bar{\mu }}^*\in \Phi ({\bar{\mu }}^*)$.

Define a probability measure $\mu$ such that $\mu |_{A_i}=\mu _i^*$ for all $i\in I$ and $0$ otherwise. Then, $\mu$ is the probability measure that we seek. $\square$

Remark 2

Theorem 5 does not impose any restrictions on the agent, payoff and/or action spaces and hence, is a quite general result.

Combining Theorems 1, 2, 3, and 5 leads us to the existence of pure-strategy equilibria in large games.

Theorem 6

If a large game $U$ satisfies one of the following three conditions:

• (a). the action space $A$ is a countable set;

• (b). all the players in each group share a common payoff;

• (c). the agent space $(T, \fancyscript{T}, \lambda )$ is a saturated probability space,

then there exists a pure-strategy equilibrium for the game.

Remark 3

By allowing $|I|$ to be countably infinite and the action space $A$ to be Polish, our case (a) is a generalization to Theorem 10 in Khan and Sun (1995) and Theorem 3.2 in Yu and Zhang (2007) and our case (c) strengthens Theorem 1 in Khan and Sun (1999). Moreover, our case (b) is new.

Remark 4

The existence results in Theorem 6 are obtained easily. However, this is not the case if we want to prove these results directly. Actually, the direct proofs on the existence of equilibria for the three settings of large games need to be constructed individually and each of them may well involve a lot of effort (see, eg, Khan and Sun (1995, 1999)).

Finally, we notice that similar to Theorem 4.6 in Keisler and Sun (2009), we can have a global characterization of saturated probability spaces using our characterization result. For this purpose, it suffices to consider the case where $I$ is a singleton, i.e., all players share a common action space $A$.¹⁸

Proposition 1

Let $(T,\fancyscript{T},\lambda )$ be an atomless probability space and $A$ an uncountable compact metric space. Then, $(T,\fancyscript{T},\lambda )$ is saturated if and only if for every large game $U$ with player space $(T,\fancyscript{T},\lambda )$ and action space $A$, any Borel probability distribution $\mu$ on $A$ which satisfies $\mu (D)\le \lambda [({B^\mu })^{-1}(D)]$ for every closed subset $D$ in $A$ must be an equilibrium distribution.

Proof

The necessity part (“only if” part) has already been shown by Theorem 4. We only need to show the sufficiency part here. Suppose the condition in the theorem holds. Now, by Theorem 5 we know that for every large game $U$ there exists a $\mu$ on $A$ which satisfies $\mu (D)\le \lambda [({B^\mu })^{-1}(D)]$ for every closed subset $D$ in $A$. Thus it is an equilibrium distribution by the condition of the theorem. Hence there is a Nash equilibrium for the game. Therefore, by Theorem 4.6 in Keisler and Sun (2009), $(T,\fancyscript{T},\lambda )$ must be saturated. $\square$

Remark 5

Because of Theorem 2, Proposition 1 is still valid if the condition “for every closed subset $D$” in the last row is replaced by “for every open subset $O$” or “for every Borel subset $C$”.

5 Concluding remarks

In this paper, we provide a unified framework for characterizing equilibrium distributions in large games. Our framework also leads to an easy way of proving the existence of Nash equilibria in large games. Our division of the agent space into countably many groups and the corresponding existence results are new and can be practically useful. It is noticed that our characterization framework can also be used to characterize saturated probability spaces. We hope our method used here can be applied to other situations, for example, large games with traits as discussed in Khan et al. (2013) and games with public and private information as discussed in Fu et al. (2007). We may address this issue in subsequent work.