Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 8 / 3

A transport plan is a Borel probability measure on $X\times Y$ with marginals $\mu ,\nu$. It is c-cyclically monotone when it is concentrated on a set $\Gamma$ such that every finite list $(x_i,y_i)\in \Gamma$ satisfiesEquivalently, one can allow every permutation of the destinations, since a permutation decomposes into cycles. The word $c$-monotone here means this cyclic condition, not merely a two-point test for an arbitrary cost.

The potential-certificate meaning of the printed “strictly $c$-monotone” is strong c-monotonicity: there are Borel functions $u:X\to \mathbb{R}\cup \{-\infty \}$ and $v:Y\to \mathbb{R}\cup \{-\infty \}$ such thatThe functions are finite on full marginal-measure sets. This is a certificate by Kantorovich potentials, not literal strict inequality in every nonidentity cycle. Such a literal interpretation could not satisfy the requested implication, already for $c=0$.

Here is a direct transport potential path construction. Since $c$ is finite and continuous, the closure of a cyclically monotone set remains cyclically monotone. We may therefore use the closed support $\Gamma$ of $\pi$ and choose a countable dense subset ${\Gamma }_0$, containing an anchor $(x_0,y_0)$. For a chain $(x_j,y_j)\in {\Gamma }_0$, $j=0,\dots ,m$, starting at that anchor, defineThe infimum is over countably many continuous functions, so $u$ is upper semicontinuous and Borel, and never $+\infty$ because the zero-length chain is available. Cyclical monotonicity applied to a chain closing at the anchor gives $u(x_0)=0$. If $(x,y)\in \Gamma$, closing a chain through this extra pair givesso $u(x)$ is finite on the first projection of $\Gamma$.

Append the pair $(x,y)$ to a nearly minimizing chain ending at $x$. If the pair is outside ${\Gamma }_0$, approximate it by pairs in ${\Gamma }_0$ and use continuity of the finitely many costs. This gives, for every $z$,Now putIt is again an infimum of continuous functions of $y$, and therefore upper semicontinuous and Borel. The anchor bounds it above by $c(x_0,y)$. Feasibility $u(z)+v(y)\le c(z,y)$ is immediate. For $(x,y)\in \Gamma$, the preceding chain inequality gives $v(y)\ge c(x,y)-u(x)$, while testing $z=x$ gives the opposite inequality. Hence equality holds on $\Gamma$, and $v$ is finite on its second projection. This proves cyclical monotonicity implies the potential certificate.

To deduce optimality, we must not subtract possibly infinite marginal integrals. Use the symmetric clipping proof of transport optimality: let $u_n=\max (-n,\min (u,n))$ and similarly $v_n$. Because $c\ge 0$, simultaneous clipping preserves the feasible inequalityFor any competitor ${\pi }^{\prime }$ with the same marginals, boundedness givesOn the full-measure equality set for $\pi$, $u+v=c\ge 0$. There the clipped sums are nonnegative and increase to $c$: when the two signs differ, their large equal clipping levels initially cancel, then the sum increases to the nonnegative original sum. Thus the monotone convergence theorem givesThis proves optimality even if the eventual integral is infinite. Conversely, a potential certificate implies the cyclic inequalities by summing and cancelling the potentials on its full-measure equality set.

The converse from optimality is true for finite-cost optimal plans. To see this, suppose points in the support violate a finite cyclic inequality by a positive amount. Continuity supplies product neighborhoods of those points on which every selected tuple still violates it, with all involved costs bounded. Normalize the restrictions of $\pi$ to these neighborhoods to probability measures ${\alpha }_i$, with marginals ${\mu }_i,{\nu }_i$. Subtract a sufficiently small common multiple of ${\sum }_i{\alpha }_i$ and add the same multiple of ${\sum }_i{\mu }_{i+1}\otimes {\nu }_i$. Positivity is ensured by choosing the multiple at most ${\min }_i\pi (U_i)/m$, even if neighborhoods overlap. Both marginals are unchanged, but integration of the strict cyclic improvement over the product of the ${\alpha }_i$ decreases the finite total cost. This contradicts optimality, so the support is cyclically monotone.

Without a finite-value hypothesis, the unrestricted converse is false. On the discrete Polish spaces $X=Y=\mathbb{N}$, take $\mu (n)=\nu (n)=C/n^2$ andThis is finite, continuous and nonnegative, yet every coupling has infinite cost because its marginals have infinite first moments. The diagonal plan is therefore an extended-value minimizer. Its support is not cyclically monotone: two distinct diagonal pairs cost $2m+2n+2$, while swapping their destinations costs $2m+2n$. Thus under the literal printed hypotheses, optimality alone need not imply $c$-monotonicity; the usual finite-cost converse needs that qualification.

The transport cost separates into a function of $y$ and a function of $x$, so for every transport planThe value is fixed by the marginals. Hence every transport map from $\mu$ to $\nu$ is optimal, and indeed every coupling is optimal.

For an explicit description of the complete set, let $F(x)={\int }_0^{x}f(s)ds$ and $G(y)={\int }_1^{y}g(s)ds$. Their strictly positive continuous densities make $F:[0,1]\to [0,1]$ and $G:[1,2]\to [0,1]$ increasing homeomorphisms. The full family of deterministic plans iswhere $S:[0,1]\to [0,1]$ is any measurable Lebesgue-measure-preserving map. Indeed $F_{\ast }\mu$ is uniform measure and $G_{\ast }\nu$ is uniform measure, so any such $S$ produces the required pushforward. Conversely, for any transport map $T$, the map $S=G\circ T\circ F^{-1}$ preserves uniform measure. This is the measure-preserving parametrization of one-dimensional transport maps; no monotonicity is required for the linear cost.

The answer is the monotone rearrangementIt pushes $\mu$ to $\nu$ by the same cumulative-distribution argument as in part (a).

For the squared transport cost, the two-point swap difference isThus any optimal support has no crossed pairs: $x_1<x_2$ forces $y_1\le y_2$. This follows from the finite-cost converse proved above; every cost here is bounded. Conversely, an increasing graph is c-cyclically monotone for this cost. After removing the marginal terms $\sum x_i^2+\sum y_i^2$, the cycle inequalities say that pairing the sorted $x_i$ and $y_i$ maximizes $\sum x_i{y}_i$. Exchanging any inverted pairing increases that sum by the nonnegative product of the two differences, so repeated exchanges prove the inequality. Therefore the displayed increasing transport is optimal.

For uniqueness, let $\pi$ be any noncrossing coupling. The sets $A=\{x\le a\}$ and $B=\{y\le b\}$ cannot both have positive mass in $A\setminus B$ and $B\setminus A$: a point from each would give a strictly crossed pair. Consequently one of these differences has zero mass, andThis determines the joint distribution uniquely and is exactly the distribution of the common-quantile coupling $(F^{-1}(U),G^{-1}(U))$ for uniform $U$. Since $F$ is continuous and strictly increasing, that coupling is induced by $T=G^{-1}F$. Hence there is one optimal deterministic plan, with maps differing only on $\mu$-null sets; in fact it is the unique optimal coupling. This proves the one-dimensional quadratic transport uniqueness criterion directly.