Proof of fungibility theorem

nisan

Proof of fungibility theorem

post by Nisan · 2013-01-12T09:26:09.484Z · LW · GW · Legacy · 10 comments

10 comments

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$