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.

Proof of fungibility theorem

3 Post author: Nisan 12 January 2013 09:26AM

Appendix to: A fungibility theorem

Suppose that $P$ is a set and we have functions $v_1, \dots, v_n : P \to \mathbb{R}$ . Recall that for $p, q \in P$ , we say that $p$ is a Pareto improvement over $q$ if for all $i$ , we have $v_i(p) \geq v_i(q)$ . And we say that it is a strong Pareto improvement if in addition there is some $i$ for which $v_i(p) > v_i(q)$ . We call $p$ a Pareto optimum if there is no strong Pareto improvement over it.

Theorem. Let $P$ be a set and suppose $v_i: P \to \mathbb{R}$ for $i = 1, \dots, n$ are functions satisfying the following property: For any $p, q \in P$ and any $\alpha \in [0, 1]$ , there exists an $r \in P$ such that for all $i$ , we have $v_i(r) = \alpha v_i(p) + (1 - \alpha) v_i(q)$ .

Then if an element $p$ of $P$ is a Pareto optimum, then there exist nonnegative constants $c_1, \dots, c_n$ such that the function $\sum c_i v_i$ achieves a maximum at $p$ .

Proof. Let $V = v_1 \times \cdots \times v_n : P \to \mathbb{R}^n$ . By hypothesis, the image $V(P)$ is convex.

For $p \in P$ , let the Pareto volume of $p$ be the set

$pv(p) = \{ (x_1, \dots, x_n) \in \mathbb{R}^n \mid x_i \geq v_i(p) \mbox{ for all } i \}$

This is a closed convex set. Note that $p \in P$ is a Pareto optimum precisely when $pv(p) \cap V(P) = \{ V(p) \}$ . Let's assume that this is the case; we just have to prove that $p$ maximizes $\sum c_i v_i$ for some choice of $c_i \geq 0$ .

It suffices to find a hyperplane $H \subset \mathbb{R}^n$ that contains $V(p)$ and that supports $V(P)$ . Then the desired function $\sum c_i v_i$ can be constructed by ensuring that $H$ is a level set.

If $V(P)$ lies in a proper affine subspace of $\mathbb{R}^n$ , let $Z$ be the smallest such subspace. Let $A$ be the interior of $V(P)$ in $Z$ and let $B$ be the interior of $pv(p)$ . The case where $V(P)$ is a point is trivial; suppose it's not, so $A$ is nonempty. By convexity, $V(P)$ is the closure of $A$ and $pv(p)$ is the closure of $B$ .

Since $V(P)$ is convex, $A$ is convex, and we can exhaust $A$ with a nested sequence of nonempty compact convex sets $A_j$ . And $pv(p)$ is convex, so we can exhaust $B$ with a nested sequence of nonempty compact convex sets $B_j$ . By the hyperplane separation theorem, for each $j$ , there is a hyperplane $H_j$ separating $A_j$ and $B_j$ . I claim that $H_j$ has a convergent subsequence. Indeed, each $H_j$ must intersect the convex hull of $A_1 \cup B_1$ , and the space of hyperplanes intersecting that convex hull is compact. So $H_j$ has a subsequence that converges to a hyperplane $H$ .

It's easy to see that $H$ separates $A_j$ from $B_j$ for each $j$ , and so $H$ separates $A$ from $B$ . So $H$ must contain $V(p)$ and support $V(P)$ .

$\square$

Note that the theorem does not guarantee the existence of a Pareto optimum. But if $V(P)$ is closed and bounded, then a Pareto optimum exists.

A limitation of the theorem is that it assumes a finite list of values $v_1, \dots, v_n$ , not an infinite one.

Article Navigation

Comments (10)

Comments (10)

Sort By: Best

Comment author: Oscar_Cunningham 12 January 2013 11:44:19AM 2 points [-]

Couldn't this have been in a comment to the original post or on the wiki?

Comment author: Nisan 15 January 2013 08:16:55AM 0 points [-]

Would you prefer it that way?

Comment author: Oscar_Cunningham 15 January 2013 06:31:10PM 1 point [-]

Yeah, just to keep the list of posts tidy.

Comment author: Nisan 18 January 2013 12:15:27AM 1 point [-]

I'll do it that way in the future.

Comment author: AlexMennen 23 January 2013 04:54:56AM * 0 points [-]

It suffices to find a hyperplane $H \subset \mathbb{R}^n$ that contains $V(p)$ and that supports $pv(p)$ .

I assume you also want it to support $V(P)$ ?

I love this proof, by the way.

Comment author: Nisan 23 January 2013 06:53:15AM 0 points [-]

Ah, you're right. The important thing is that it supports V(P). Thanks.

Comment author: Nisan 23 January 2013 06:45:31AM 0 points [-]

The definition of pv is the next line. Does that not show up for you?

Comment author: AlexMennen 23 January 2013 04:25:24PM * 0 points [-]

Nope. In fact, the one I wrote no longer shows up for me in my comment either. How odd.

Proof of fungibility theorem

Article Navigation

Comments (10)

Nearest Meetups

Virtual Study Room

Recent Comments

Recent Posts

Recent Open Threads

Recent Rationality Diaries

Recent Wiki Edits

Top Contributors, 30 Days

Recent Karma Awards

Comments (10)

Top Contributors, 30 Days

You'll need to login or register to do that

(Don't worry, it only takes a few seconds)

Create

Login