The primal problem chooses how mass moves. The dual problem assigns a value to mass at each endpoint. If the combined endpoint value never exceeds the cost of a journey, then its expected value is a lower bound on every transport plan. At optimality this inequality becomes equality exactly along the journeys actually used.
Dual feasible potentials
Definition. A pair of measurable functions \((\varphi,\psi)\) is dual feasible for the cost \(c\) if \[ \varphi(x)+\psi(y)\le c(x,y) \] for all \((x,y)\), or outside a set irrelevant to the marginals under an appropriate integrable formulation. Its dual value is \[ J(\varphi,\psi)=\int_X\varphi\,\mathrm{d}\mu+\int_Y\psi\,\mathrm{d}\nu. \] The Kantorovich dual value is \[ D_c(\mu,\nu)=\sup_{\varphi\oplus\psi\le c}J(\varphi,\psi). \]
Weak duality. For every \(\pi\in\Pi(\mu,\nu)\) and every feasible \((\varphi,\psi)\), \[ J(\varphi,\psi)\le\int c\,\mathrm{d}\pi. \] Hence \(D_c(\mu,\nu)\le K_c(\mu,\nu)\).
Proof. Using the marginal constraints, \[ J(\varphi,\psi) =\int_{X\times Y}\{\varphi(x)+\psi(y)\}\,\mathrm{d}\pi(x,y) \le\int_{X\times Y}c(x,y)\,\mathrm{d}\pi(x,y). \] Taking the supremum on the left and the infimum on the right proves the claim.
Strong duality
Kantorovich duality. Let \(X,Y\) be Polish and let \(c:X\times Y\to[0,\infty]\) be lower semicontinuous. Then \[ \inf_{\pi\in\Pi(\mu,\nu)}\int c\,\mathrm{d}\pi = \sup_{\varphi\oplus\psi\le c} \left\{\int\varphi\,\mathrm{d}\mu+\int\psi\,\mathrm{d}\nu\right\}, \] where the dual may be taken over bounded continuous potentials when \(c\) is bounded and continuous, and over integrable potentials under the general formulation.
Proof for compact spaces and continuous cost. Consider the Lagrangian \[ L(\pi,\varphi,\psi) =\int c\,\mathrm{d}\pi +\int\varphi\,\mathrm{d}(\mu-\pi_X) +\int\psi\,\mathrm{d}(\nu-\pi_Y). \] For a nonnegative measure \(\pi\), \[ L=\int\varphi\,\mathrm{d}\mu+\int\psi\,\mathrm{d}\nu +\int\{c-\varphi\oplus\psi\}\,\mathrm{d}\pi. \] Taking the supremum over \(\varphi,\psi\in C\) enforces \(\pi_X=\mu,\pi_Y=\nu\): if a marginal equality fails, a continuous test function separates the two measures and scaling it makes the supremum infinite. Thus \[ \inf_{\pi\ge0}\sup_{\varphi,\psi}L(\pi,\varphi,\psi) =K_c(\mu,\nu). \] Conversely, taking the infimum over \(\pi\ge0\) gives a finite value precisely when \(c-\varphi\oplus\psi\ge0\); in that case the infimum is attained at the zero measure and equals \(J(\varphi,\psi)\). The convex minimax theorem applies after restricting to a compact mass-bounded set containing all feasible plans, because \(c\) and the potentials are continuous and the problem has a feasible point. It permits interchange of infimum and supremum and yields \(K_c=D_c\).
For Polish spaces and lower semicontinuous \(c\), approximate the marginals by compact restrictions and \(c\) from below by bounded continuous costs. Apply the compact result, use monotone convergence for the primal values, and diagonalize the dual potentials. Tightness controls the discarded mass. This gives the stated general form.
Complementary slackness
Optimality certificate. Let \(\pi\in\Pi(\mu,\nu)\) and let \((\varphi,\psi)\) be dual feasible. If both values are finite, then \(\pi\) and \((\varphi,\psi)\) are primal and dual optimal if and only if \[ \varphi(x)+\psi(y)=c(x,y) \qquad\text{for }\pi\text{-almost every }(x,y). \]
Proof. The nonnegative slack \(s=c-\varphi-\psi\) satisfies \[ \int s\,\mathrm{d}\pi =\int c\,\mathrm{d}\pi-J(\varphi,\psi). \] If the equality holds \(\pi\)-almost surely, the primal and dual values coincide, so weak duality makes both optimal. Conversely, if both are optimal, strong duality makes the right-hand side zero. A nonnegative measurable function with zero integral vanishes almost surely.
This criterion converts a global optimization problem into a geometric support condition. One does not need to compare a candidate plan with every competitor; it suffices to find potentials touching the cost on its support.
Dual attainment and normalization
Proposition. If \(X,Y\) are compact and \(c\) is continuous, the dual supremum is attained. Potentials are nonunique because \((\varphi+a,\psi-a)\) has the same feasibility and value. One may normalize, for example, by fixing \(\varphi(x_0)=0\).
Proof idea. Replace a maximizing pair successively by its \(c\)-transforms. This does not decrease the objective and produces uniformly bounded, equicontinuous potentials after normalization, because \(c\) is uniformly continuous on the compact product. Arzelà--Ascoli gives uniformly convergent subsequences. The feasibility inequality and objective pass to the limit.
Kantorovich--Rubinstein duality
Kantorovich--Rubinstein theorem. On a Polish metric space \((X,d)\), for \(\mu,\nu\in\mathcal P_1(X)\), \[ W_1(\mu,\nu) =\sup_{\operatorname{Lip}(f)\le1} \left\{\int_X f\,\mathrm{d}\mu-\int_X f\,\mathrm{d}\nu\right\}. \]
Proof. If \(f\) is \(1\)-Lipschitz, then \(f(x)-f(y)\le d(x,y)\), so \((f,-f)\) is dual feasible and weak duality gives the lower bound. For the reverse direction, start from any feasible \((\varphi,\psi)\) and define \[ f(x)=\inf_y\{d(x,y)-\psi(y)\}. \] The triangle inequality shows that \(f\) is \(1\)-Lipschitz. Feasibility gives \(\varphi\le f\), while the definition gives \(f(y)\le-\psi(y)\) by choosing the same point in the infimum. Hence \[ \int\varphi\,\mathrm{d}\mu+\int\psi\,\mathrm{d}\nu \le\int f\,\mathrm{d}\mu-\int f\,\mathrm{d}\nu. \] Taking the supremum and invoking Kantorovich duality proves the formula.
Potentials as sensitivity derivatives
Dual potentials also measure the first-order response of the optimal value to changes in the marginals. Formally, if \(\mu_t=\mu+t\sigma\) and \(\nu_t=\nu+t\tau\) preserve total mass, an optimal pair \((\varphi,\psi)\) gives \[ \frac{\mathrm{d}}{\mathrm{d}t}K_c(\mu_t,\nu_t)\bigg|_{t=0} =\int\varphi\,\mathrm{d}\sigma+\int\psi\,\mathrm{d}\tau \] whenever differentiability holds. This fact later drives statistical limit theory and numerical optimization.