Duality says that optimal mass moves only where \(\varphi(x)+\psi(y)=c(x,y)\). The \(c\)-transform organizes all such touching pairs, while cyclical monotonicity describes them without mentioning the potentials. Together they are the geometric language of optimality.
The \(c\)-transform
Definition. For \(\varphi:X\to[-\infty,\infty]\), define its \(c\)-transform on \(Y\) by \[ \varphi^c(y)=\inf_{x\in X}\{c(x,y)-\varphi(x)\}. \] For \(\psi:Y\to[-\infty,\infty]\), define \(\psi^c(x)=\inf_y\{c(x,y)-\psi(y)\}\). A function is \(c\)-concave if it equals the \(c\)-transform of some function. Some authors use the sign-reversed term \(c\)-convex; the present note follows the dual inequality \(\varphi+\psi\le c\).
Proposition. The \(c\)-transform reverses order. Moreover, \[ \varphi\le\varphi^{cc}, \qquad \varphi^{ccc}=\varphi^c. \] A function \(\varphi\) is \(c\)-concave exactly when \(\varphi=\varphi^{cc}\), up to the usual properness qualifications.
Proof. If \(\varphi_1\le\varphi_2\), then \(c-\varphi_1\ge c-\varphi_2\), so taking infima gives \(\varphi_1^c\ge\varphi_2^c\). For every \(x,y\), \[ \varphi^c(y)\le c(x,y)-\varphi(x), \] hence \(\varphi(x)\le c(x,y)-\varphi^c(y)\). Taking the infimum over \(y\) gives \(\varphi\le\varphi^{cc}\). Apply the order reversal to this inequality to obtain \(\varphi^c\ge\varphi^{ccc}\); applying the double-transform inequality to \(\varphi^c\) gives the reverse inequality. If \(\varphi=\psi^c\), then \(\varphi^{cc}=\psi^{ccc}=\psi^c=\varphi\). The converse is immediate from \(\varphi=(\varphi^c)^c\).
Reduction of the dual problem
Proposition. If \((\varphi,\psi)\) is dual feasible, then \(\psi\le\varphi^c\). Replacing \(\psi\) by \(\varphi^c\), and then \(\varphi\) by \(\varphi^{cc}\), preserves feasibility and cannot decrease the dual objective. Consequently the dual problem may be written \[ K_c(\mu,\nu) =\sup_{\varphi=\varphi^{cc}} \left\{\int\varphi\,\mathrm{d}\mu+\int\varphi^c\,\mathrm{d}\nu\right\}. \]
Proof. Feasibility gives \(\psi(y)\le c(x,y)-\varphi(x)\) for every \(x\); taking the infimum yields \(\psi\le\varphi^c\). By definition, \(\varphi(x)+\varphi^c(y)\le c(x,y)\), so the replacement is feasible. The same argument on the other side replaces \(\varphi\) by \((\varphi^c)^c=\varphi^{cc}\). Both replacements increase only one potential, hence do not lower the objective.
The \(c\)-superdifferential
Definition. For a \(c\)-concave \(\varphi\), its \(c\)-superdifferential is \[ \partial^c\varphi =\{(x,y):\varphi(x)+\varphi^c(y)=c(x,y)\}. \] The fiber \(\partial^c\varphi(x)=\{y:(x,y)\in\partial^c\varphi\}\) contains the destinations at which the \(c\)-support associated with \(y\) touches \(\varphi\) at \(x\).
Corollary. If \(\varphi\) is an optimal Kantorovich potential and \(\pi\) is an optimal plan, then \[ \operatorname{supp}\pi\subset\partial^c\varphi \] whenever the potentials and cost are continuous; in general the inclusion holds \(\pi\)-almost surely.
Cyclical monotonicity
Definition. A set \(\Gamma\subset X\times Y\) is \(c\)-cyclically monotone if for every \(N\ge1\), every \((x_i,y_i)\in\Gamma\), and every permutation \(\sigma\) of \(\{1,\ldots,N\}\), \[ \sum_{i=1}^N c(x_i,y_i) \le \sum_{i=1}^N c(x_i,y_{\sigma(i)}). \] It is enough to test cyclic permutations after decomposing a permutation into disjoint cycles.
Proposition. Every \(c\)-superdifferential \(\partial^c\varphi\) is \(c\)-cyclically monotone.
Proof. If \((x_i,y_i)\in\partial^c\varphi\), then \[ c(x_i,y_i)=\varphi(x_i)+\varphi^c(y_i). \] Feasibility gives \(\varphi(x_i)+\varphi^c(y_{\sigma(i)})\le c(x_i,y_{\sigma(i)})\). Sum over \(i\). Since permutation does not change \(\sum_i\varphi^c(y_i)\), the desired inequality follows.
Optimal support theorem. Under the standard lower-semicontinuity and finite-cost hypotheses, every optimal plan is concentrated on a \(c\)-cyclically monotone Borel set. Conversely, if a finite-cost plan is concentrated on a \(c\)-cyclically monotone set and that set admits an integrable \(c\)-potential, then the plan is optimal.
Proof. For the forward direction, take optimal dual potentials. Complementary slackness places the plan on \(\partial^c\varphi\), which is cyclically monotone. For the converse, the \(c\)-version of Rockafellar's construction produces a \(c\)-concave \(\varphi\) with \(\Gamma\subset\partial^c\varphi\). Thus \(\varphi+\varphi^c=c\) on the support. Integrating gives equality of primal and dual values, so weak duality proves optimality.
Rockafellar's construction
Fix \((x_0,y_0)\in\Gamma\). A potential containing a \(c\)-cyclically monotone set in its \(c\)-superdifferential can be built as \[ \varphi(x)=\inf_{\substack{N\ge1\\(x_i,y_i)\in\Gamma}} \left[ c(x,y_N)-c(x_N,y_N) +\sum_{i=0}^{N-1}\{c(x_{i+1},y_i)-c(x_i,y_i)\} \right]. \] Cyclical monotonicity prevents contradictory negative cycles. Comparing a chain ending at \(x\) with the same chain extended by \((x,y)\in\Gamma\) yields \(\varphi(z)-\varphi(x)\le c(z,y)-c(x,y)\), which is precisely the supporting inequality defining \((x,y)\in\partial^c\varphi\).
Quadratic cost and ordinary convexity
Proposition. For \(c(x,y)=\tfrac12|x-y|^2\) on \(\mathbb R^d\), let \[ u(x)=\tfrac12|x|^2-\varphi(x). \] Then \(\varphi\) is \(c\)-concave exactly when \(u\) is convex, and \[ y\in\partial^c\varphi(x) \quad\Longleftrightarrow\quad y\in\partial u(x). \]
Proof. Expand \[ \tfrac12|x-y|^2-\varphi(x) =u(x)-x\cdot y+\tfrac12|y|^2. \] The \(c\)-transform is therefore a Legendre--Fenchel transform up to quadratic terms. The touching equality becomes \[ u(z)\ge u(x)+y\cdot(z-x)\qquad\text{for every }z, \] which is exactly \(y\in\partial u(x)\).
Two-point condition. For quadratic cost, the two-cycle inequality is \[ |x_1-y_1|^2+|x_2-y_2|^2 \le |x_1-y_2|^2+|x_2-y_1|^2, \] which simplifies to \[ (x_1-x_2)\cdot(y_1-y_2)\ge0. \] In one dimension this forbids crossings: \(x_1<x_2\) implies \(y_1\le y_2\). In higher dimensions, all cycle lengths are needed to characterize gradients of convex functions.