Kantorovich duality

Kantorovich duality is the fundamental duality theorem for optimal transport, establishing that the primal problem (minimising transport cost over couplings) equals a dual problem (maximising the gap between integrated “prices” subject to a feasibility constraint). For lower semicontinuous cost $c$ on Polish spaces $\mathcal{X}\times \mathcal{Y}$:

${\min }_{\pi \in \Pi (\mu ,\nu )}\int cd\pi ={\sup }_{\varphi -\psi \le c}\left(\int \varphi d\nu -\int \psi d\mu \right)$

The dual variables $(\psi ,\varphi )$ are “competitive prices” — $\psi (x)$ is the price of picking up mass at $x$, $\varphi (y)$ is the price of delivering to $y$. The constraint $\varphi (y)-\psi (x)\le c(x,y)$ says no arbitrage: the profit from transporting $(x\to y)$ cannot exceed the cost. At the optimum, $\varphi (y)-\psi (x)=c(x,y)$ on the support of $\pi$ — there is zero profit on routes actually used.

The theorem also establishes the equivalence between five characterisations of optimality: (a) $\pi$ is optimal, (b) $\pi$ is $c$-cyclically monotone, (c)-(d) there exist dual functions achieving equality $\pi$-a.s., (e) $\pi$ is concentrated on a fixed $c$-cyclically monotone set $\Gamma$.

Key Details

• For $c=d$ (distance): reduces to the Kantorovich-Rubinstein formula $W_1(\mu ,\nu )={\sup }_{\Vert \psi {\Vert }_{\text{Lip}}\le 1}(\int \psi d\mu -\int \psi d\nu )$
• For $c(x,y)=-x\cdot y$: reduces to $\sup \mathbb{E}[X\cdot Y]=\inf (\int \phi d\mu +\int {\phi }^{\ast }d\nu )$ over convex $\phi$
• Optimal $\psi$ can be taken $c$-convex with $\varphi ={\psi }^c$
• The set $\Gamma ={\partial }_c\psi$ (the $c$-subdifferential) is common to ALL optimal plans

Textbook References

Optimal Transport Old and New (Villani, 2009)

• Theorem 5.10 (pp. 70-71): Full statement with three parts — (i) duality, (ii) five equivalent characterisations of optimality, (iii) existence of dual maximisers under integrability
• Particular Case 5.16 (p. 72): Kantorovich-Rubinstein formula for $c=d$
• Particular Case 5.17 (pp. 72-73): Quadratic cost $c=-x\cdot y$; dual reduces to infimum over convex functions and their Legendre transforms
• Theorem 5.20 (p. 89): Stability of optimal transport under perturbations of cost and marginals

---

concept