0
$\begingroup$

I am study infinite strategy set using Myerson's Game Theory textbook. The author stated the following theorem (Theorem 3.5) but did not prove it. I tried the proof, and would really appreciate it if someone could help me check!

Here is the theorem:

Theorem 3.5$\quad$ Let $\alpha$ be any strictly positive real number. Suppose that, for every player $i$, the utility function $u_i:C\to\mathbb{R}$ is continuous on the compact domain $C$. Then there exists an essentially finite game $\hat{\Gamma}=(N,(C_i)_{i \in N},(\hat{u}_i)_{i \in N})$ such that the distance between $u$ and $\hat{u}$ is less than $\alpha$.

My proof is as follows:

Proof$\quad$ Since each $u_i$ is a continuous mapping of a compact metric space $C$ into a metric space $\mathbb{R}$, it is uniformly continuous on $C$; that is, for every $\alpha>0$ there exists $\epsilon>0$ such that \begin{align*} \delta_{\mathbb{R}}(u_i(c),u_i(c')) < \alpha. \end{align*} for all $c$ and $c'$ in $C$ for which $\delta_C(c,c') < \epsilon$. Since each $C_i$ is a compact metric space, it can be covered by finitely many open balls. Without loss of generality, suppose $C_i \subseteq \bigcup_{k_i=1}^{m_i}B_i(b_i^{k_i},\frac{\epsilon}{n})$. Let $D_i$ denote the finite set $\{b_i^1,\dots,b_i^{m_i}\}$. For each $i$ in $N$, define $f_i:C_i \to D_i$ as $f_i(c_i) = b_i^{k_i}$ if and only if $c_i \in B_i(b_i^{k_i},\frac{\epsilon}{n})$ for $k_i = 1,\dots,m_i$. Since for every $b_i^{k_i}$ in $D_i$, the set $\{c_i \in C_i|f_i(c_i) = b_i^{k_i}\}$ is equal to the open set $B_i(b_i^{k_i},\frac{\epsilon}{c})$, we have that $f_i$ is (Borel) measurable. Let $\Gamma^* = (N,(D_i)_{i \in N},(u_i)_{i \in N})$ be a finite strategic-form game and denote \begin{align*} \hat{u}_i(c) = u_i(f_1(c_1),\dots,f_n(c_n)) = u_i(b_1^{k_1},\dots,b_n^{k_n}),\quad \forall i \in N,\quad \forall c \in C. \end{align*} Now, we define the essentially finite game as $\hat{\Gamma} = (N,(C_i)_{i \in N},(\hat{u}_i)_{i \in N})$. Since $\delta_C(c_i,b_i^{k_i}) < \frac{\epsilon}{n}$ for all $i$ in $N$, then $\delta_C(c,(b_1^{k_1},\dots,b_n^{k_n})) = \sum_{i \in N}\delta_C(c_i,b_i^{k_i}) < \epsilon$. Therefore, for all $i$ in $N$, \begin{align*} \delta_{\mathbb{R}}(u_i(c),u_i(b_1^{k_1},\dots,b_n^{k_n})) = \delta_{\mathbb{R}}(u_i(c),\hat{u}_i(c)) = |u_i(c)-\hat{u}_i(c)| < \alpha. \end{align*} Hence, the distance between $u$ and $\hat{u}$, $\max_{i \in N} \sup_{c \in C} |u_i(c) - \hat{u}_i(c)|$, is less than $\alpha$.

Here are some definitions and assumptions from the text, especially how the metric is defined for $C = \prod_{i \in N}C_i$ as well as the definition of an essentially finite game:

Definition$\quad$ Let $N$ denote the finite set of players, \begin{align*} N = \{1,2,\dots,n\}. \end{align*} For each player $i$ in $N$, let $C_i$ be a compact metric space that denotes the set of all pure strategies available to player $i$. As usual, let $C = \prod_{i \in N}C_i = C_1 \times \dots \times C_n$. As a finite Cartesian product of compact metric spaces, $C$ is also a compact metric space (with $\delta(c,\hat{c}) = \sum_{i \in N}\delta(c_i,\hat{c}_i)$).

Definition$\quad$ The Borel-measurable subsets of $C$ and of each $C_i$ be the smallest class of subsets that includes all open subsets, all closed subsets, and all finite or countably infinite unions and intersections of sets in the class

Definition$\quad$ A function $f_i$ from $C_i$ into a finite set $D_i$ is (Borel) measurable if and only if, for every $b_i$ in $D_i$, $\{c_i \in C_i|f_i(c_i) = b_i\}$ is a Borel-measurable set.

Definition$\quad$ We may say that the game $\hat{\Gamma}$ is essentially finite if and only if there exists some finite strategic-form game $\Gamma^* = (N,(D_i)_{i \in N},(v_i)_{i \in N})$ and measurable functions $(f_i:C_i \to D_i)_{i \in N}$ such that, \begin{align*} \hat{u}_i(c) = v_i(f_1(c_1),\dots,f_n(c_n)),\quad \forall i \in N,\quad c \in C. \end{align*}

Could someone please help me check my proof and see if everything is regiorous, or if there is any mistake, or if certain part of the proof shall be improved? Thanks a lot in advance!


Revised definition and proof of the (Borel) measurable function $f_i$:

For each $i$ in $N$, define $f_i:C_i \to D_i$ as $f_i(c_i) = b_i^{k_i}$ if and only if $k_i$ is the smallest index among $\{1,\dots,m_i\}$ such that $c_i \in B_i(b_i^{k_i},\frac{\epsilon}{n})$. For every $b_i^{k_i}$ in $D_i$, we have \begin{align*} \left\{c_i \in C_i|f_i(c_i) = b_i^{k_i}\right\} &= B_i\left(b_i^{k_i},\frac{\epsilon}{n}\right) \Big\backslash \left(B_i\left(b_i^{k_i-1},\frac{\epsilon}{n}\right) \cup \dots \cup B_i\left(b_i^1,\frac{\epsilon}{n}\right)\right)\\ &= B_i\left(b_i^{k_i},\frac{\epsilon}{n}\right) \cap \left(B_i\left(b_i^{k_i-1},\frac{\epsilon}{n}\right) \cup \dots \cup B_i\left(b_i^1,\frac{\epsilon}{n}\right)\right)^c\\ &= B_i\left(b_i^{k_i},\frac{\epsilon}{n}\right) \cap \left[B_i\left(b_i^{k_i-1},\frac{\epsilon}{n}\right)\right]^c \cap \dots \cap \left[B_i\left(b_i^1,\frac{\epsilon}{n}\right)\right]^c, \end{align*} which is a finite intersection of open and closed sets and thus is a Borel-measurable set. Thus, $f_i$ is (Borel) measurable.

$\endgroup$
6
  • 1
    $\begingroup$ The definition of $f_i$ does not work; the balls covering $C_i$ need not be disjoint. $\endgroup$ Dec 2, 2023 at 2:43
  • $\begingroup$ @MichaelGreinecker You're right! Thank you so much! What if I define $f_i$ as follows: For each $i$ in $N$, define $f_i:C_i \to D_i$ as $f_i(c_i) = b_i^{k_i}$ if and only if $k_i$ is the smallest index among $1,\dots,m_i$ such that $c_i \in B_i(b_i^{k_i},\frac{\epsilon}{n})$? $\endgroup$
    – Beerus
    Dec 2, 2023 at 3:43
  • $\begingroup$ Wait, but I need to show that $f_i$ is Borel measurable, which I'm not sure how.... $\endgroup$
    – Beerus
    Dec 2, 2023 at 3:45
  • 1
    $\begingroup$ That works and the resulting function is Borel. Using hopefully clear notation, the preimage of every singleton Borel set is empty or $B_n\setminus(B_{n-1}\cup\ldots\cup B_1)$ and every preimage of a Borel set is a finite union of such preimages because $D_i$ is finite. $\endgroup$ Dec 2, 2023 at 10:31
  • 1
    $\begingroup$ Yes, it looks good. $\endgroup$ Dec 2, 2023 at 22:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.