Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 7 / 4 / Solution

We prove Kantorovich duality theorem here by a positive-functional extension argument; it produces the minimizing transport plan at the same time as equality of the values. Let $Y=X\times X$ and $c(x,y)=d(x,y)$. This is a bounded continuous function because $X$ is a compact metric space. Write $C(Y)$ for the real space of continuous functions on a compact space, and letOn this vector subspace define $\ell (s)=\int fd\mathbf{P}+\int gd\mathbf{Q}$. It is well-defined: two representations differ by a constant in the first variable and the opposite constant in the second, and both measures have mass one. It is positive, since $s\ge 0$ implies $\min f+\min g\ge 0$ and hence $\ell (s)\ge 0$. Also $\ell (1)=1$.

Define the majorant envelope, which is a sublinear functional:Constants majorize every $h$, and positivity gives $\min h\le p(h)\le \max h$, so this quantity is finite. Taking approximate minimizing majorants proves subadditivity; rescaling majorants proves positive homogeneity. Moreover $p(s)=\ell (s)$ for $s\in S$, and subtracting $s$ from a majorant provesThe dual value in the question is exactlySubadditivity at $c+(-c)=0$ gives $m_d\le p(c)$.

On $S+\mathbb{R}c$, assign the value $\ell (s)+t{m}_d$ to $s+tc$. If $c\notin S$ the representation is unique. If $c\in S$, then $m_d=\ell (c)$, so the assignment is still well-defined. It is dominated by $p$: for $t\ge 0$, use $t{m}_d\le tp(c)=p(tc)$; for $t<0$, positive homogeneity gives $p(tc)=(-t)p(-c)=t{m}_d$. Together with the translation identity, these verify domination in both cases.

The real Hahn-Banach theorem extends this functional to $T:C(Y)\to \mathbb{R}$ with $T\le p$. If $h\ge 0$, then $p(-h)\le \ell (0)=0$, so $T(h)\ge 0$. Thus $T$ is a positive linear functional, with $T(1)=1$ and $T(c)=m_d$. Positivity also gives $|T(h)|\le \Vert h{\Vert }_{\infty }$, so $T$ is continuous. The Riesz-Markov-Kakutani representation theorem supplies a Borel probability measure ${\pi }_0$ on the compact space $Y$, satisfying $T(h)={\int }_{Y}hd{\pi }_0$.

For every $f\in C(X)$, its pullback $f(x)$ belongs to $S$, so $\int f(x)d{\pi }_0=\int fd\mathbf{P}$. Likewise $\int g(y)d{\pi }_0=\int gd\mathbf{Q}$. Uniqueness in the Riesz-Markov-Kakutani representation theorem shows that these are exactly the two marginal distributions. Finally, every feasible pair $f+g\le c$ gives a lower bound for the cost of every transport plan, by integration. Our constructed plan achieves that bound:This Kantorovich duality by positive extension establishes the requested existence and equality without assuming an optimal plan in advance.

The metric structure additionally gives the Kantorovich–Rubinstein theorem formulation. For a feasible pair define $h(x)={\inf }_y\{d(x,y)-g(y)\}$. The triangle inequality for $d$ makes $h$ one-Lipschitz continuous, $h\ge f$, and $h(y)\le -g(y)$. Hence the dual objective is at most $\int hd\mathbf{P}-\int hd\mathbf{Q}$. Conversely $(h,-h)$ is feasible for every one-Lipschitz $h$. ThereforeNormalizing $h(x_0)=0$ for a fixed $x_0$ gives a uniformly bounded equicontinuous family; it is closed and compact in the uniform topology by the Arzela-Ascoli theorem. The objective is uniformly continuous on this family, so the supremum is attained as well. In particular, $m_d$ is the first Wasserstein distance between the two measures.