<p>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!</p>
<p>Here is the theorem:</p>
<blockquote>
<p><strong>Theorem 3.5</strong><span class="math-container">$\quad$</span> <em>Let <span class="math-container">$\alpha$</span> be any strictly positive real number. Suppose that, for every player <span class="math-container">$i$</span>, the utility function <span class="math-container">$u_i:C\to\mathbb{R}$</span> is continuous on the compact domain <span class="math-container">$C$</span>. Then there exists an essentially finite game <span class="math-container">$\hat{\Gamma}=(N,(C_i)_{i \in N},(\hat{u}_i)_{i \in N})$</span> such that the distance between <span class="math-container">$u$</span> and <span class="math-container">$\hat{u}$</span> is less than <span class="math-container">$\alpha$</span>.</em></p>
</blockquote>
<p>My proof is as follows:</p>
<blockquote>
<p><strong>Proof</strong><span class="math-container">$\quad$</span> Since each <span class="math-container">$u_i$</span> is a continuous mapping of a compact metric space <span class="math-container">$C$</span> into a metric space <span class="math-container">$\mathbb{R}$</span>, it is uniformly continuous on <span class="math-container">$C$</span>; that is, for every <span class="math-container">$\alpha&gt;0$</span> there exists <span class="math-container">$\epsilon&gt;0$</span> such that
<span class="math-container">\begin{align*}
\delta_{\mathbb{R}}(u_i(c),u_i(c')) &lt; \alpha.
\end{align*}</span>
for all <span class="math-container">$c$</span> and <span class="math-container">$c'$</span> in <span class="math-container">$C$</span> for which <span class="math-container">$\delta_C(c,c') &lt; \epsilon$</span>. Since each <span class="math-container">$C_i$</span> is a compact metric space, it can be covered by finitely many open balls. Without loss of generality, suppose <span class="math-container">$C_i \subseteq \bigcup_{k_i=1}^{m_i}B_i(b_i^{k_i},\frac{\epsilon}{n})$</span>. Let <span class="math-container">$D_i$</span> denote the finite set <span class="math-container">$\{b_i^1,\dots,b_i^{m_i}\}$</span>. For each <span class="math-container">$i$</span> in <span class="math-container">$N$</span>, define <span class="math-container">$f_i:C_i \to D_i$</span> as <span class="math-container">$f_i(c_i) = b_i^{k_i}$</span> if and only if <span class="math-container">$c_i \in B_i(b_i^{k_i},\frac{\epsilon}{n})$</span> for <span class="math-container">$k_i = 1,\dots,m_i$</span>. Since for every <span class="math-container">$b_i^{k_i}$</span> in <span class="math-container">$D_i$</span>, the set <span class="math-container">$\{c_i \in C_i|f_i(c_i) = b_i^{k_i}\}$</span> is equal to the open set <span class="math-container">$B_i(b_i^{k_i},\frac{\epsilon}{c})$</span>, we have that <span class="math-container">$f_i$</span> is (Borel) measurable. Let <span class="math-container">$\Gamma^* = (N,(D_i)_{i \in N},(u_i)_{i \in N})$</span> be a finite strategic-form game and denote
<span class="math-container">\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*}</span>
Now, we define the essentially finite game as <span class="math-container">$\hat{\Gamma} = (N,(C_i)_{i \in N},(\hat{u}_i)_{i \in N})$</span>. Since <span class="math-container">$\delta_C(c_i,b_i^{k_i}) &lt; \frac{\epsilon}{n}$</span> for all <span class="math-container">$i$</span> in <span class="math-container">$N$</span>, then <span class="math-container">$\delta_C(c,(b_1^{k_1},\dots,b_n^{k_n})) = \sum_{i \in N}\delta_C(c_i,b_i^{k_i}) &lt; \epsilon$</span>. Therefore, for all <span class="math-container">$i$</span> in <span class="math-container">$N$</span>,
<span class="math-container">\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)| &lt; \alpha.
\end{align*}</span>
Hence, the distance between <span class="math-container">$u$</span> and <span class="math-container">$\hat{u}$</span>, <span class="math-container">$\max_{i \in N} \sup_{c \in C} |u_i(c) - \hat{u}_i(c)|$</span>, is less than <span class="math-container">$\alpha$</span>.</p>
</blockquote>
<p>Here are some definitions and assumptions from the text, especially how the metric is defined for <span class="math-container">$C = \prod_{i \in N}C_i$</span> as well as the definition of an essentially finite game:</p>
<blockquote>
<p><strong>Definition</strong><span class="math-container">$\quad$</span> Let <span class="math-container">$N$</span> denote the finite set of players,
<span class="math-container">\begin{align*}
    N = \{1,2,\dots,n\}.
\end{align*}</span>
For each player <span class="math-container">$i$</span> in <span class="math-container">$N$</span>, let <span class="math-container">$C_i$</span> be a compact metric space that denotes the set of all pure strategies available to player <span class="math-container">$i$</span>. As usual, let <span class="math-container">$C = \prod_{i \in N}C_i = C_1 \times \dots \times C_n$</span>. As a finite Cartesian product of compact metric spaces, <span class="math-container">$C$</span> is also a compact metric space (with <span class="math-container">$\delta(c,\hat{c}) = \sum_{i \in N}\delta(c_i,\hat{c}_i)$</span>).</p>
</blockquote>
<blockquote>
<p><strong>Definition</strong><span class="math-container">$\quad$</span> The <em>Borel-measurable subsets</em> of <span class="math-container">$C$</span> and of each <span class="math-container">$C_i$</span> 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</p>
</blockquote>
<blockquote>
<p><strong>Definition</strong><span class="math-container">$\quad$</span> A function <span class="math-container">$f_i$</span> from <span class="math-container">$C_i$</span> into a finite set <span class="math-container">$D_i$</span> is <em>(Borel) measurable</em> if and only if, for every <span class="math-container">$b_i$</span> in <span class="math-container">$D_i$</span>, <span class="math-container">$\{c_i \in C_i|f_i(c_i) = b_i\}$</span> is a Borel-measurable set.</p>
</blockquote>
<blockquote>
<p><strong>Definition</strong><span class="math-container">$\quad$</span> We may say that the game <span class="math-container">$\hat{\Gamma}$</span> is <em>essentially finite</em> if and only if there exists some finite strategic-form game <span class="math-container">$\Gamma^* = (N,(D_i)_{i \in N},(v_i)_{i \in N})$</span> and measurable functions <span class="math-container">$(f_i:C_i \to D_i)_{i \in N}$</span> such that,
<span class="math-container">\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*}</span></p>
</blockquote>
<p>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!</p>
<hr />
<h2>Revised definition and proof of the (Borel) measurable function <span class="math-container">$f_i$</span>:</h2>
<p>For each <span class="math-container">$i$</span> in <span class="math-container">$N$</span>, define <span class="math-container">$f_i:C_i \to D_i$</span> as <span class="math-container">$f_i(c_i) = b_i^{k_i}$</span> if and only if <span class="math-container">$k_i$</span> is the smallest index among <span class="math-container">$\{1,\dots,m_i\}$</span> such that <span class="math-container">$c_i \in B_i(b_i^{k_i},\frac{\epsilon}{n})$</span>. For every <span class="math-container">$b_i^{k_i}$</span> in <span class="math-container">$D_i$</span>, we have
<span class="math-container">\begin{align*}
    \left\{c_i \in C_i|f_i(c_i) = b_i^{k_i}\right\} &amp;= 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)\\
    &amp;= 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\\
    &amp;= 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*}</span>
which is a finite intersection of open and closed sets and thus is a Borel-measurable set. Thus, <span class="math-container">$f_i$</span> is (Borel) measurable.</p>

CC BY-SA 4.0
2023-12-02T02:43:33.503Z
The definition of $f_i$ does not work; the balls covering $C_i$ need not be disjoint.
Michael Greinecker
CC BY-SA 4.0
2023-12-02T03:43:49.657Z
@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})$?
Beerus
CC BY-SA 4.0
2023-12-02T03:45:23.643Z
Wait, but I need to show that $f_i$ is Borel measurable, which I'm not sure how....
Beerus
CC BY-SA 4.0
2023-12-02T10:31:40.510Z
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.
Michael Greinecker
CC BY-SA 4.0
2023-12-02T20:50:40.163Z
@MichaelGreinecker Thanks a lot for your help! I really lack the knowledge of measure theory here, so I prefer to stick with the definition from the text. I added the definition of a Borel-measurable set as well as the revised proof of $f_i$ being Borel-measurable. Could you please help me check if my understanding of your comment is correct? I really appreciate it!
Beerus
CC BY-SA 4.0
2023-12-02T22:36:38.607Z
Yes, it looks good.
Michael Greinecker
<microeconomics><mathematical-economics><game-theory><self-study><proof>
About Theorem 3.5 (The Finite-Approximation Theorem) in Game Theory: Analysis of Conflict by Roger Myerson
Beerus
# About Theorem 3.5 (The Finite-Approximation Theorem) in Game Theory: Analysis of Conflict by Roger Myerson

(Asked by: username_0 on 2023-12-02)

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.

**Tags:** microeconomics, mathematical-economics, game-theory, self-study, proof
> **Comments:**
> **username_1**: The definition of $f_i$ does not work; the balls covering $C_i$ need not be disjoint.  
> **username_0**: @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})$?  
> **username_0**: Wait, but I need to show that $f_i$ is Borel measurable, which I'm not sure how....  
> **username_1**: 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.  
> **username_0**: @MichaelGreinecker Thanks a lot for your help! I really lack the knowledge of measure theory here, so I prefer to stick with the definition from the text. I added the definition of a Borel-measurable set as well as the revised proof of $f_i$ being Borel-measurable. Could you please help me check if my understanding of your comment is correct? I really appreciate it!  
> **username_1**: Yes, it looks good.  

---

## 0 answers

