The two classical formulations ask the same physical question at different mathematical resolutions. Monge moves each source point to one destination; Kantorovich permits randomized destinations and thereby turns a nonlinear constraint into a convex feasible set.
Transport costs
Let \(c:X\times Y\to(-\infty,\infty]\) be a Borel cost. The value \(c(x,y)=+\infty\) may encode a forbidden movement. For existence results we usually assume that \(c\) is lower semicontinuous and bounded below, while duality requires additional integrability conditions.
Definition. For a measurable map \(T:X\to Y\) satisfying \(T_\#\mu=\nu\), its Monge cost is \[ \mathcal C_M(T)=\int_X c(x,T(x))\,\mathrm{d}\mu(x). \] The Monge value is \[ M_c(\mu,\nu)=\inf_{T_\#\mu=\nu}\mathcal C_M(T), \] with value \(+\infty\) if no admissible map exists.
Definition. The Kantorovich value is \[ K_c(\mu,\nu)=\inf_{\pi\in\Pi(\mu,\nu)} \int_{X\times Y}c(x,y)\,\mathrm{d}\pi(x,y). \] A minimizer is an optimal transport plan. If it has the form \((\operatorname{id},T)_\#\mu\), then \(T\) is an optimal transport map.
Kantorovich relaxation
Proposition. Every admissible Monge map induces an admissible Kantorovich plan with the same cost. Consequently, \[ K_c(\mu,\nu)\le M_c(\mu,\nu). \]
Proof. If \(T_\#\mu=\nu\), set \(\pi_T=(\operatorname{id},T)_\#\mu\). Its first marginal is \(\mu\), and its second marginal is \(T_\#\mu=\nu\). The pushforward identity gives \[ \int c(x,y)\,\mathrm{d}\pi_T(x,y) =\int c(x,T(x))\,\mathrm{d}\mu(x). \] Taking the infimum over maps proves the inequality.
The inequality can be strict because the Monge feasible set may be empty. Even when maps exist, the relaxed problem is analytically better behaved: \(\Pi(\mu,\nu)\) is convex and weakly compact, while a weak limit of graph measures need not itself be concentrated on a graph.
Atomic obstruction. If \(\mu=\delta_0\) and \(\nu=\tfrac12(\delta_{-1}+\delta_1)\), then \(M_c(\mu,\nu)=+\infty\) for every finite cost because no map can split the atom at \(0\). The Kantorovich problem has the unique feasible plan \(\delta_0\otimes\nu\), with value \(\tfrac12c(0,-1)+\tfrac12c(0,1)\).
When transport maps exist
Measurable transport theorem. If \(X,Y\) are standard Borel spaces, \(\mu\) is nonatomic, and \(\nu\in\mathcal P(Y)\), then there exists a measurable \(T:X\to Y\) such that \(T_\#\mu=\nu\).
Proof idea. A nonatomic standard probability space is isomorphic modulo null sets to \(([0,1],\lambda)\). A standard Borel probability law \(\nu\) is the image of \(\lambda\) under a measurable map \(Q:[0,1]\to Y\). Composing the two maps gives \(T\). In one dimension, \(Q\) can be taken to be the quantile function of \(\nu\).
This theorem gives feasibility, not optimality. The central structural question is therefore: under what assumptions is an optimal Kantorovich plan concentrated on a graph? For quadratic cost and an absolutely continuous source, Brenier's theorem answers this by showing that the unique optimal plan is induced by the gradient of a convex function.
Three elementary models
Translation. If \(\nu=(x\mapsto x+a)_\#\mu\) on \(\mathbb R^d\), then \(T(x)=x+a\) is admissible. For \(c(x,y)=|x-y|^p\), every point travels distance \(|a|\), so the cost is \(|a|^p\). Jensen's inequality applied to any coupling gives \[ \int|x-y|^p\,\mathrm{d}\pi \ge\left|\int(x-y)\,\mathrm{d}\pi\right|^p =|a|^p, \] proving optimality when the first moments exist.
Dilation. If \(\mu\) is uniform on \([0,1]\), \(\nu\) is uniform on \([0,2]\), and \(c(x,y)=|x-y|^2\), then \(T(x)=2x\) is admissible. One-dimensional monotone rearrangement will show that it is the unique optimal map \(\mu\)-almost everywhere.
A finite assignment. For equal-weight empirical measures \(\mu=n^{-1}\sum_i\delta_{x_i}\) and \(\nu=n^{-1}\sum_j\delta_{y_j}\), every permutation \(\sigma\) induces a map with cost \(n^{-1}\sum_i c(x_i,y_{\sigma(i)})\). Kantorovich plans are doubly stochastic matrices. The Birkhoff--von Neumann theorem implies that some optimal plan is a permutation plan, although uniqueness may fail.
Convexity gained by relaxation
The Kantorovich objective is linear in \(\pi\), and its feasible set is convex. This allows compactness arguments, linear-programming duality, perturbation analysis, and entropy regularization. None of these tools requires an optimizer to be deterministic. The later theory will first solve the relaxed problem and then use duality and convex geometry to decide whether the optimizer actually comes from a map.