About Theorem 1.1 in Game Theory: Analysis of Conflict by Roger Myerson

Question

I am self-studying game theory using Myerson's Game Theory: Analysis of Conflict. I got some trouble understanding his proof of Theorem 1.1, the Expected-Utility Maximization Theorem. The Theorem goes like this:

Theorem 1.1$\space\space$ Axioms 1.1AB, 1.2, 1.3, 1.4, 1.5AB, 1.6AB, and 1,7 are jointly satisfied if and only if there exists a utility function $u : X \times \Omega \to \mathbb{R}$ and a conditional probability function $p : \Xi \to \Delta(\Omega)$ such that \begin{equation} \max_{x \in X} u(x, t) = 1\space\space \text{and}\space\space \min_{x \in X} u(x, t) = 0,\space\space \forall t \in \Omega; \tag1 \end{equation} \begin{equation} p(R|T) = p(R|S)p(S|T),\space\space \forall R,\space\space \forall S,\space\space \text{and}\space\space \forall T\space\space \text{such that} \tag2 \end{equation} \begin{equation} R \subseteq S \subseteq T \subseteq \Omega\space\space \text{and}\space\space S \neq \emptyset; \end{equation} \begin{equation} f \succsim_S g\space\space \text{if and only if}\space\space E_p(u(f)|S) \geq E_p(u(g)|S),\tag3 \end{equation} \begin{equation} \forall f, g \in L, \forall S \in \Xi. \end{equation} Furthermore, given these Axioms 1.1AB - 1.7, Axiom 1.8 is also satisfied if and only if conditions (1) - (3) here can be satisfied with a state-omdependent utility.

In his proof, there is one step, which is a one-line equation that I cannot understand:

... (Here, $|\Omega|$ denotes the number of states in the set $\Omega$.) Notice that \begin{equation} \left(\frac{1}{|\Omega|}\right)f + \left(1 - \frac{1}{|\Omega|}\right)a_0 = \left(\frac{1}{|\Omega|}\right)\sum_{t \in \Omega}\sum_{x \in X}f(x|t)c_{x, t}. \end{equation}

Could someone please help me explain this equation? Some background information and notation:

Definition$\space\space$ Let $X$ denote the set of possible prizes that the decision-maker could ultimately get. Let $\Omega$ denote the set of possible states, one of which will be the true state of the world. Suppose $X$ and $\Omega$ are finite.

Definition$\space\space$ A lottery is any function $f$ that specifies a nonnegative real number $f(x|t)$, for every prize $x$ in $X$ and every state $t$ in $\Omega$, such that $\sum_{x \in X} f(x|t) = 1$ for every $t$ in $\Omega$. Let $L$ denote the set of all such lotteries; that is, \begin{equation} L = \{f : \Omega \to \Delta(X)\}. \end{equation}

Definition$\space\space$ For any state $t$ in $\Omega$ and any lottery $f$ in $L$, $f(\cdot|t)$ denotes the probability distribution over $X$ designated by $f$ in state $t$; that is, \begin{equation} f(\cdot|t) = (f(x|t))_{x \in X} \in \Delta(X). \end{equation}

Definition$\space\space$ The information that the decision-maker might have about the true state of the world can be described by an event, which is a nonempty subset of $\Omega$. Let $\Xi$ denote the set of all such events, so that \begin{equation} \Xi = \{S\hspace{0.2cm} |\hspace{0.2cm} S \subseteq \Omega\hspace{0.2cm} \text{and}\hspace{0.2cm} S \neq \emptyset\}. \end{equation}

Definition$\space\space$ For any two lotteries $f$ and $g$ in $L$, and for any event $S$ in $\Xi$, we write $f \succsim_S g$ if and only if the lottery $f$ would be at least as desirable as $g$, in the opinion of the decision-maker, if he learned that the true state of the world was in the set $S$. That is, $f \succsim_S g$ if and only if the decision-maker would be willing to choose the lottery $f$ when he has to choose between $f$ and $g$ and he knows only that the event $S$ has occurred.

Definition$\space\space$ For any number $\alpha$ such that $0 \leq \alpha \leq 1$, and for any two lotteries $f$ and $g$ in $L$, $\alpha f + (1 - \alpha)g$ denotes the lottery in $L$ such that \begin{align*} (\alpha f + (1 - \alpha)g)(x|t) = \alpha f(x|t) + (1 - \alpha)g(x|t),\quad \forall x \in X,\quad \forall t \in \Omega. \end{align*}

Axiom 1.1A (Completeness)$\space\space$ $f \succsim_S g$ or $g \succsim_S f$

Axiom 1.1B (Transitivity)$\space\space$ If $f \succsim_S g$ and $g \succsim_S h$, then $f \succsim_S h$

Axiom 1.2 (Relevance)$\space\space$ If $f(\cdot|t) = g(\cdot|t)$ $\forall t\in S$, then $f \sim_S g$

Axiom 1.3 (Monotonicity)$\space\space$ If $f \succ_S h$ and $0 \leq \beta < \alpha \leq 1$, then $\alpha f + (1 - \alpha)h \succ_S \beta f + (1 - \beta)h$

Axiom 1.4 (Continuity)$\space\space$ If $f \succsim_S g$ and $g \succsim_S h$, then there exists some number $\gamma$ such that $0 \leq \gamma \leq 1$ and $g \sim_S \gamma f + (1 - \gamma)h$

Axiom 1.5A (Objective Substitution)$\space\space$ If $e \succsim_S f$ and $g \succsim_S h$ and $0 \leq \alpha \leq 1$, then $\alpha e + (1 - \alpha)g \succsim_S \alpha f + (1 - \alpha)h$

Axiom 1.5B (Strict Objective Substitution)$\space\space$ If $e \succ_S f$ and $g \succ_S h$ and $0 < \alpha \leq 1$, then $\alpha e + (1 - \alpha)g \succ_S \alpha f + (1 - \alpha)h$

Axiom 1.6A (Subjective Substitution)$\space\space$ If $f \succsim_S g$ and $f \succsim_T g$ and $S \cap T = \emptyset$, then $f \succsim_{S \cup T} g$

Axiom 1.6B (Strict Subjective Substitution)$\space\space$ If $f \succ_S g$ and $f \succ_T g$ and $S \cap T = \emptyset$, then $f \succ_{S \cup T} g$

Axiom 1.7 (Interest)$\space\space$ For every state $t$ in $\Omega$, there exist prizes $y$ and $z$ in $X$ such that $[y] \succ_{\{t\}} [z]$

Axiom 1.8 (State Neutrality)$\space\space$ For any two states $r$ and $t$ in $\Omega$, if $f(\cdot|r) = f(\cdot|t)$ and $g(\cdot|r) = g(\cdot|t)$ and $f \succsim_{\{r\}} g$, then $f \succsim_{\{t\}} g$

Definition$\space\space$ Let $a_1$ be a lottery that gives the decision-maker one of the best prizes in every state; and let $a_0$ be a lottery that gives him one of the worst prizes in every state. That is, for every state $t$, $a_1(y|t) = 1 = a_0(z|t)$ for some prizes $y$ and $z$ such that, for every $x$ in $X$, $y \succsim_{\{t\}} x \succsim_{\{t\}} z$. Such best and worst prizes can be found in every state because the preference relation $\succsim_{\{t\}}$ forms a transitive ordering over the finite set $X$.

Definition$\space\space$ For any prize $x$ and any state $t$, let $c_{x, t}$ be the lottery such that \begin{equation} c_{x, t}(\cdot|r) = [x](\cdot|r)\space\space \text{if}\space\space r = t,\\ c_{x, t}(\cdot|r) = a_0(\cdot|r)\space\space \text{if}\space\space r \neq t. \end{equation} That is, $c_{x, t}$ is the lottery that always gives the worst prize, except in state $t$, when it gives prize $x$.

I really appreciate any help!

Answer 1

Let's first have a look at the left hand side of the equation. Take an outcome $y$ and a state $r$. There are two cases:

1. If $y$ is not the worst outcome in state $r$ then the lottery gives: $$ \left(\frac{1}{|\Omega|}\right) f(y|r) + \left(1-\frac{1}{|\Omega|}\right) \underbrace{a_0(y|r)}_{=0} = \left(\frac{1}{|\Omega|}\right) f(y|r) $$ Notice that $a_0(y|r)$ is zero as the probability of getting $y$ in state $r$ is zero (as $y$ is not the worst outcome).

2. If $y$ is the worst outcome in state $r$ then $a_0(y|r) = 1$ and we get instead $$ \left(\frac{1}{|\Omega|}\right) f(y|r) + \left(1-\frac{1}{|\Omega|}\right) \underbrace{a_0(y|r)}_{=1}= \left(\frac{1}{|\Omega|}\right)f(y|r) + \left(1 - \frac{1}{|\Omega|}\right). $$

Now, let us focus on the right hand side and show that it is the same in both cases. First let us split up the sum into the different cases, case I where ($x \ne y$ and $t \ne r$), case II where ($x \ne y$ and $t = r$), case III where ($x = y$ and $t \ne r$) and finally, case IV where ($t = r$ and $x = y$).

$$ \begin{align*} \frac{1}{|\Omega|} \sum_{x \in X} \sum_{t \in \Omega} f(x|t)\,\,c_{x,t}(y|r) =& \frac{1}{|\Omega|} \sum_{x \ne y} \sum_{t \ne r} f(x|t) c_{x,t}(y|r), && \text{case I}\\ &+ \frac{1}{|\Omega|} \sum_{x \ne y} f(x|r) c_{x,r}(y|r), && \text{case II}\\ &+ \frac{1}{|\Omega|} \sum_{t \ne r} f(y|t) c_{y,t}(y|r), && \text{case III}\\ &+ \frac{1}{|\Omega|} f(y|r) c_{y,r}(y|r). && \text{case IV} \end{align*} $$ Substituting out $c_{x,t}(y|r)$ with $[x](y|r)$ if $t = r$ and $a_0(y|r)$ when $t \ne r$ gives $$ \begin{align*} \frac{1}{|\Omega|} \sum_{x \in X} \sum_{t \in \Omega} f(x|t)\,\,c_{x,t}(y|r) =& \frac{1}{|\Omega|} \sum_{x \ne y} \sum_{t \ne r} f(x|t) a_0(y|r),\\ &+ \frac{1}{|\Omega|} \sum_{x \ne y} f(x|r) \underbrace{[x](y|r)}_{=0},\\ &+ \frac{1}{|\Omega|} \sum_{t \ne r} f(y|t) a_0(y|r),\\ &+ \frac{1}{|\Omega|} f(y|r) \underbrace{[y](y|r)}_{=1}. \end{align*} $$ Notice that $[x](y|r)$ is zero if $x \ne y$ and equal to $1$ if $x = y$. This gives: $$ \begin{align*} \frac{1}{|\Omega|} \sum_{x \in X} \sum_{t \in \Omega} f(x|t)\,\,c_{x,t}(y|r) =& \frac{1}{|\Omega|} \sum_{x \ne y} \sum_{t \ne r} f(x|t) a_0(y|r),\\ &+ \frac{1}{|\Omega|} \sum_{t \ne r} f(y|t) a_0(y|r),\\ &+ \frac{1}{|\Omega|} f(y|r). \end{align*} $$

To determine $a_0(y|r)$ we need again distinguish between the two cases.

1. if $y$ is not the worst outcome in state $r$ then $a_0(y|r) = 0$, so we get the final outcome $$ \begin{align*} \frac{1}{|\Omega|} \sum_{x \in X} \sum_{t \in \Omega} f(x|t)\,\,c_{x,t}(y|r) =& \frac{1}{|\Omega|} \sum_{x \ne y} \sum_{t \ne r} f(x|t) \underbrace{a_0(y|r)}_{=0},\\ &+ \frac{1}{|\Omega|} \sum_{t \ne r} f(y|t) \underbrace{a_0(y|r)}_{=0},\\ &+ \frac{1}{|\Omega|} f(y|r),\\ =& \frac{1}{|\Omega|} f(y|r). \end{align*} $$ This is the same as in point 1 above.

2. If $y$ is the worst outcome in state $r$ then $a_0(y|r) = 1$ and we obtain: $$ \begin{align*} \frac{1}{|\Omega|} \sum_{x \in X} \sum_{t \in \Omega} f(x|t)\,\,c_{x,t}(y|r) =& \frac{1}{|\Omega|} \sum_{x \ne y} \sum_{t \ne r} f(x|t) \underbrace{a_0(y|r)}_{=1},\\ &+ \frac{1}{|\Omega|} \sum_{t \ne r} f(y|t) \underbrace{a_0(y|r)}_{=1},\\ &+ \frac{1}{|\Omega|} f(y|r),\\ =& \frac{1}{|\Omega|} \sum_{x \ne y} \sum_{t \ne r} f(x|t) + \frac{1}{|\Omega|} \sum_{t \ne r} f(y|t),\\ &+ \frac{1}{|\Omega|} f(y|r),\\ =& \frac{1}{|\Omega|} \sum_{t \ne r} \underbrace{\sum_{x \in X} f(x|t)}_{=1} + \frac{1}{|\Omega|} f(y|r),\\ =& \frac{1}{|\Omega|} \underbrace{\sum_{t \ne r} 1}_{=|\Omega|-1} + \frac{1}{|\Omega|} f(y|r),\\ =& \frac{|\Omega|-1}{|\Omega|}+ \frac{1}{|\Omega|} f(y|r),\\ =& \left(1 - \frac{1}{|\Omega|}\right) + \frac{1}{|\Omega|} f(y|r). \end{align*} $$ which coincides with point 2 above.