# Proof of fungibility theorem

by Nisan2 min read12th Jan 201310 comments

# 3

Personal Blog

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$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.

Personal Blog

Pingbacks