c-cyclical monotonicity

Summary

Let $c$ be a cost function. A set of pairs $(x, y)$ is $c$-cyclically monotone if no cyclic reassignment of finitely many of its pairs lowers the total cost. It is the condition that an optimal transport plan must satisfy on its support: one cannot improve the plan by swapping destinations along a cycle. For the quadratic cost on $\R^n$ it is the cyclical monotonicity of Rockafellar. That notion characterizes the subsets of the graph of the subdifferential of a convex function. Under mild hypotheses, a coupling with finite cost is optimal exactly when it is concentrated on a $c$-cyclically monotone set.