TheoremProved

Kantorovich duality theorem

Statement

For probability measures $\mu$ on $X$ , $\nu$ on $Y$ (Polish spaces) and a continuous, bounded-below cost $c$ , the Kantorovich problem is equal to a dual maximization over pairs of Kantorovich potentials $\varphi:X\to\mathbb R$ , $\psi:Y\to\mathbb R$ satisfying $\varphi(x) + \psi(y) \le c(x,y)$ pointwise: $\min_{\gamma\in\Pi(\mu,\nu)}\int_{X\times Y} c\,d\gamma \;=\; \sup_{\varphi(x)+\psi(y)\le c(x,y)}\left(\int_X\varphi\,d\mu+\int_Y\psi\,d\nu\right),$ and both the minimum and the supremum are attained.

Why is it true?

Think of $\varphi(x)$ as a price charged for picking up mass at $x$ and $\psi(y)$ as a price paid for dropping it off at $y$ , in a decentralized market of independent shippers. No shipper can profitably undercut the direct route: buying at $\varphi(x)$ and selling at $\psi(y)$ can never beat physically moving the mass and paying $c(x,y)$ — exactly the constraint $\varphi(x)+\psi(y)\le c(x,y)$ . In a market that clears optimally, equality $\varphi(x)+\psi(y)=c(x,y)$ holds exactly along the routes actually used by an optimal plan.

Proof sketch

For finite discrete measures $\mu=\sum_i p_i\delta_{x_i}$ , $\nu=\sum_j q_j\delta_{y_j}$ , the Kantorovich problem is the finite linear program $\min \sum_{i,j} c_{ij}\gamma_{ij}$ subject to $\gamma_{ij}\ge0$ , $\sum_j\gamma_{ij}=p_i$ , $\sum_i\gamma_{ij}=q_j$ . Its LP dual is exactly $\max \sum_i p_i\varphi_i+\sum_j q_j\psi_j$ subject to $\varphi_i+\psi_j\le c_{ij}$ for all $i,j$ — one dual variable per primal (marginal) constraint. The primal is feasible (the product coupling $p_iq_j$ always works) and bounded below by $0$ , and the feasible polytope $\{\gamma_{ij}\ge0\}\cap\Pi(\mu,\nu)$ is compact, so strong linear-programming duality gives equality of the two optimal values, with both attained. This proves the theorem exactly in the discrete case; the general statement on Polish spaces follows from the same primal-dual pattern applied via Fenchel–Rockafellar duality to convex functionals on $C_b(X\times Y)$ (Kantorovich 1942; see Villani 2009, Theorem 5.10, for the full argument).

Topics that use this theorem

Optimal transport

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Cédric Villani (2009). Optimal Transport: Old and New
Marco Cuturi (2013). Sinkhorn Distances: Lightspeed Computation of Optimal Transport · arXiv:1306.0895
Yann Brenier (1991). Polar Factorization and Monotone Rearrangement of Vector-Valued Functions · DOI:10.1002/cpa.3160440402
John Lott, Cédric Villani (2009). Ricci Curvature for Metric-Measure Spaces via Optimal Transport