1994

LESSWRONG
LW

1993

5

Proof of fungibility theorem

12th Jan 2013

3 min read

5

5

Proof of fungibility theorem

4Oscar_Cunningham

1Oscar_Cunningham

New Comment

10 comments, sorted by

Click to highlight new comments since: Today at 1:15 AM

[-]Oscar_Cunningham13y40

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

Would you prefer it that way?

[-]Oscar_Cunningham13y10

Yeah, just to keep the list of posts tidy.

I'll do it that way in the future.

[-]AlexMennen13y00

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.

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

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

[-]AlexMennen13y00

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

Does it show up for you in the html source?

Maybe an unescaped character is causing the trouble.

[-]AlexMennen13y00

Problem appears to have been on my end. I can see both now.

More from Nisan

Curated and popular this week

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.

Mentioned in

35A fungibility theorem