2
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I really appreciate it! Thank you so much! $\endgroup$
    – Beerus
    Sep 6, 2023 at 15:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.