A Structure Theorem in Optimal Transport
Speaker: Elias ManuelidesDate of Talk: April 8, 2026
This is part of a series of talks in an optimal transport reading seminar.
1. The Goal and Morals
In the last talk (which I missed), it was shown that if \(\gamma \) is an optimal transport plan from measures \(\mu \) to \(\nu \) with respect to some cost function \(c\), then the support of \(\gamma \) is necessarily a \(c\)-cyclically monotone set. That is, optimality of \(\gamma \) implies a combinatorial condition on its support. In fact, this is both necessary and sufficient for optimality.
The aim is to prove that this combinatorial property in turn implies some very strict geometric constraints. This geometry is so restrictive that any transport plan whose support is of the right shape will necessarily be optimal.
In practise, such a structure theorem is extremely useful because it vastly reduces the size of the search space when one is trying to determine an optimal transport map between two (even discrete) measures.
2. Precise Statement
More precisely,
Definition 1.
A function \(\psi : X\to \mathbb{R} \cup \left\lbrace -\infty \right\rbrace\) is \(c\)-concave if there exists a set \(\mathcal{A}\subseteq Y\times \mathbb{R}\) such that
\[\psi (x) = \inf _{(y, \lambda )\in \mathcal{A}} \left( c(x, y) + \lambda \right). \]Notably, when \(c\) is continuous, \(\psi \) is automatically upper semicontinuous.
Definition 2.
The \(c\)-superdifferential of a function \(\psi \), denoted \(\partial^c \psi \), is defined as
\[\partial^c \psi := \left\lbrace (x, y) \in X\times Y : \psi (v) \leq \psi (x) + c(v, y) - c(x, y)\ \forall v\in X \right\rbrace.\]When \(c(x, y) = \frac{1}{2}\left\lvert x-y \right\rvert^2\), the \(c\)’s in this definition become inner products that match the usual definition of a superdifferential. In words, it is saying that \(\psi (v) - \psi (x)\) is a lower bound for the change in cost associated with shipping from \(v\) to \(y\) instead of from \(x\) to \(y\). This \(c\) replaces the role of the (bi)linear structure on Euclidean space.
Theorem 3.
\(\Gamma \subseteq X\times Y\) is \(c\)-cyclically monotone if and only if \(\Gamma \subseteq \partial^c \psi \) for some \(c\)-concave \(\psi\) on \(X\).
3. The Proof
Suppose \(\Gamma \subseteq \partial^c \psi \) for some \(c\)-concave function \(\psi \) on \(X\). Let \(\left( x_i, y_i \right) _{i=1}^{n}\) be points in \(X\times Y\). It suffices to show that
\[c \left( x_1, y_1 \right) + \ldots + c \left( x_n, y_n \right) \leq c \left( x_1, y_n \right) + c \left( x_2, y_1 \right) + \ldots + c \left( x_n, y _{n-1} \right).\]The idea is that this is a “pointwise” bad decision: we have
\[c \left( x _{i+1}, y_i \right) - c \left( x_i, y_i \right) \geq \psi \left( x _{i+1} \right) - \psi \left( x_i \right)\]by definition. Now sum and rearrange to get the inequality.
On the other hand, if \(\Gamma \) is already \(c\)-cyclically monotone, we fix a reference point \(\left( x_0, y_0 \right)\), and we define
\[\psi (x) = \inf \left( \left[ c \left( x_1, y_0 \right) + \cdots + c \left( x, y_n \right) \right] - \left[ c \left( x_n, y_n \right) + \cdots + c \left( x_0, y_0 \right) \right]\right),\]where the infimum is taken over all finite lists of points \(\left( x_i, y_i \right) _{i=1}^{n}\).
This is sort of a magical formula, but there is some intuition. Initially, one may have a plan to send \(x_i \mapsto y_i\) for each \(i = 0,\ldots, n\). However, an antagonistic boss may steal \(x_0\) from the supply, reimburisng you with supplies from \(x\). This definition of \(\psi \) describes the least costly way to rearrange your delivery plan around your boss’ unreasonable demands.
This is a really good picture to give intuition to an otherwise disgusting and difficult-to-motivate formula!
The remainder of the proof is routine: check that \(\psi \) is \(c\)-concave and that \(\Gamma \subseteq \partial^c \psi \).