Articles Tagged ‘appendix’ - Less Wrong Discussion

Main
- Posts
- Comments
Discussion
- Posts
- Comments

You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Math appendix for: "Why you must maximize expected utility"

8 Benja 13 December 2012 01:11AM

This is a mathematical appendix to my post "Why you must maximize expected utility", giving precise statements and proofs of some results about von Neumann-Morgenstern utility theory without the Axiom of Continuity. I wish I had the time to make this post more easily readable, giving more intuition; the ideas are rather straight-forward and I hope they won't get lost in the line noise!

The work here is my own (though closely based on the standard proof of the VNM theorem), but I don't expect the results to be new.

I represent preference relations as total preorders $\preccurlyeq$ on a simplex $\Delta_N$ ; define $\prec$ , $\sim$ , $\succcurlyeq$ and $\succ$ in the obvious ways (e.g., $x\sim y$ iff both $x\preccurlyeq y$ and $y\preccurlyeq x$ , and $x\prec y$ iff $x\preccurlyeq y$ but not $y\preccurlyeq x$ ). Write $e^i$ for the $i$ 'th unit vector in $\mathbb{R}^N$ .

In the following, I will always assume that $\preccurlyeq$ satisfies the independence axiom: that is, for all $x,y,z\in\Delta_N$ and $p\in(0,1]$ , we have $x\prec y$ if and only if $px + (1-p)z \prec py + (1-p)z$ . Note that the analogous statement with weak preferences follows from this: $x\preccurlyeq y$ holds iff $y\not\prec x$ , which by independence is equivalent to $py + (1-p)z \not\prec px + (1-p)z$ , which is just $px + (1-p)z \preccurlyeq py + (1-p)z$ .

Lemma 1 (more of a good thing is always better). If $x\prec y$ and $0\le p < q \le 1$ , then $(1-p)x + py\prec (1-q)x + qy$ .

Proof. Let $r := q-p$ . Then, $(1-p)x + py = \big((1-q)x + py\big) + rx$ and $(1-q)x + qy = \big((1-q)x + py\big) + ry$ . Thus, the result follows from independence applied to $x$ , $y$ , $\textstyle\frac{1}{1-r}\big((1-q)x + py\big)$ , and $r$ . $\square$

Lemma 2. If $x\preccurlyeq y\preccurlyeq z$ and $x\prec z$ , then there is a unique $p\in[0,1]$ such that $(1-q)x + qz \prec y$ for $q\in[0,p)$ and $y\prec (1-q)x + qz$ for $q\in(p,1]$ .

Proof. Let $p$ be the supremum of all $r\in[0,1]$ such that $(1-r)x + rz\preccurlyeq y$ (note that by assumption, this condition holds for $r=0$ ). Suppose that $0\le q<p$ . Then there is an $r\in(q,p]$ such that $(1-r)x + rz\preccurlyeq y$ . By Lemma 1, we have $(1-q)x + qz \prec (1-r)x + rz$ , and the first assertion follows.

Suppose now that $p < q \le 1$ . Then by definition of $p$ , we do not have $(1-q)x + qz\preccurlyeq y$ , which means that we have $(1-q)x + qz\succ y$ , which was the second assertion.

Finally, uniqueness is obvious, because if both $p$ and $p'$ satisfied the condition, we would have $\textstyle y \prec \big(1 - \frac{p+p'}2\big)x + \frac{p+p'}2z \prec y$ . $\square$

Definition 3. $x$ is much better than $y$ , notation $x\succ_* y$ or $y\prec_* x$ , if there are neighbourhoods $U$ of $x$ and $V$ of $y$ (in the relative topology of $\Delta_N$ ) such that we have $x' \succ y'$ for all $x'\in U$ and $y'\in V$ . (In other words, the graph of $\succ_*$ is the interior of the graph of $\succ$ .) Write $x\preccurlyeq_* y$ or $y\succcurlyeq_* x$ when $x\nsucc_* y$ ( $x$ is not much better than $y$ ), and $x\sim_* y$ ( $x$ is about as good as $y$ ) when both $x\preccurlyeq_* y$ and $x\succcurlyeq_* y$ .

Theorem 4 (existence of a utility function). There is a $u\in\mathbb{R}^N$ such that for all $x,y\in\Delta_N$ ,

$\sum_i x_i\,u_i \;<\; \sum_i y_i\,u_i\;\;\iff\;\; x\prec_* y\;\;\implies\;\;x\prec y.$

Unless $x\sim y$ for all $x$ and $y$ , there are $i,j\in\{1,\dotsc,N\}$ such that $u_i\neq u_j$ .

Proof. Let $i$ be a worst and $j$ a best outcome, i.e. let $i,j\in\{1,\dotsc,N\}$ be such that $e^i\preccurlyeq e^k\preccurlyeq e^j$ for all $k\in\{1,\dotsc,N\}$ . If $e^i\sim e^j$ , then $e^i \sim e^k$ for all $k$ , and by repeated applications of independence we get $x\sim e^i\sim y$ for all $x,y\in\Delta_N$ , and therefore $x\sim_* y$ again for all $x,y\in\Delta_N$ , and we can simply choose $u=0$ .

Thus, suppose that $e^i\prec e^j$ . In this case, let $u$ be such that for every $k\in\{1,\dotsc,N\}$ , $u_k$ equals the unique $p$ provided by Lemma 2 applied to $e^i\preccurlyeq e^k\preccurlyeq e^j$ and $e^i\prec e^j$ . Because of Lemma 1, $u_i = 0 \neq 1 = u_j$ . Let $f(r) := (1-r)e^i + re^j$ .

We first show that $\textstyle p := \sum_k x_k\,u_k < \sum_k y_k\,u_k =: q$ implies $x\prec y$ . For every $k$ , we either have $u_k < 1$ , in which case by Lemma 2 we have $e^k \prec f(u_k + \epsilon_k)$ for arbitrarily small $\epsilon_k > 0$ , or we have $u_k = 1$ , in which case we set $\epsilon_k := 0$ and find $e^k\preccurlyeq e^j = f(u_k + \epsilon_k)$ . Set $\textstyle \epsilon := \sum_k x_k\,\epsilon_k$ . Now, by independence applied $N-1$ times, we have $\textstyle x = \sum_k x_k\,e^k \preccurlyeq \sum_k x_k f(u_k + \epsilon_k) = f(p+\epsilon)$ ; analogously, we obtain $y \succcurlyeq f(q-\delta)$ for arbitrarily small $\delta > 0$ . Thus, using $p<q$ and Lemma 1, $x\preccurlyeq f(p+\epsilon)\prec f(q-\delta)\preccurlyeq y$ and therefore $x\prec y$ as claimed. Now note that if $\textstyle\sum_k x_k\,u_k < \sum_k y_k\,u_k$ , then this continues to hold for $x'$ and $y'$ in a sufficiently small neighbourhood of $x$ and $y$ , and therefore we have $x\prec_* y$ .

Now suppose that $\textstyle \sum_k x_k\,u_k \ge \sum_k y_k\,u_k$ . Since we have $u_i = 0$ and $u_j = 1$ , we can find points $x'$ and $y'$ arbitrarily close to $x$ and $y$ such that the inequality becomes strict (either the left-hand side is smaller than one and we can increase it, or the right-hand side is greater than zero and we can decrease it, or else the inequality is already strict). Then, $x'\succ y'$ by the preceding paragraph. But this implies that $x\not\prec_* y$ , which completes the proof. $\square$

Corollary 5. $\preccurlyeq_*$ is a preference relation (i.e., a total preorder) that satisfies independence and the von Neumann-Morgenstern continuity axiom.

Proof. It is well-known (and straightforward to check) that this follows from the assertion of the theorem. $\square$

Corollary 6. $u$ is unique up to affine transformations.

Proof. Since $u$ is a VNM utility function for $\preccurlyeq_*$ , this follows from the analogous result for that case. $\square$

Corollary 7. Unless $x\sim y$ for all $x,y\in\Delta_N$ , for all $r\in\mathbb{R}$ the set $\textstyle \{x\in\Delta_N : \sum_i x_i\,u_i = r\}$ has lower dimension than $\Delta_N$ (i.e., it is the intersection of $\Delta_N$ with a lower-dimensional subspace of $\mathbb{R}^N$ ).

Proof. First, note that the assumption implies that $N\ge 2$ . Let $v\in\mathbb{R}^N$ be given by $v_i = 1$ , $\forall i$ , and note that $\Delta_N$ is the intersection of the hyperplane $A := \{x\in\mathbb{R}^N : x\cdot v = 1\}$ with the closed positive orthant $\mathbb{R}^N_+$ . By the theorem, $u$ is not parallel to $v$ , so the hyperplane $B_r := \{x\in\mathbb{R}^N : x\cdot u = r\}$ is not parallel to $A$ . It follows that $A\cap B_r$ has dimension $N-2$ , and therefore $\textstyle\{x\in\Delta_N : \sum_i x_i\,u_i = r\} \;=\; A\cap B_r\cap\mathbb{R}^N_+$ can have at most this dimension. (It can have smaller dimension or be the empty set if $A\cap B_r$ only touches or lies entirely outside the positive orthant.) $\square$