# 60 years of cyclic monotonicity: a survey

L. De Pascale, A. Kausamo, K. Wyczesany

Dedicated to Prof. R. T. Rockafellar in occasion of his 90th birthday.

##  1 Aims and scopes

The primary purpose of this note is to provide an instructional summary of the
state of the art regarding cyclic monotonicity and related notions. We will
also present how these notions are tied to optimality in the optimal transport
(or Monge-Kantorovich) problem, even though cyclic monotonicity is simply a
property of a set and can be studied on its own merit.

Cyclic monotonicity arose from the problem of characterising the subgradient
of a convex function. In [26], Minty proved monotonicity, which can also be
called 2-cyclic monotonicity, of the subgradient. To the best of our
knowledge, the definition of cyclic monotonicity was first introduced in 1966
by Rockafellar in [32], where he proved that maximal cyclic monotonicity
characterizes the subgradients of convex functions.

At the beginning of the ’90s, the study of cyclic monotonicity met the Monge-
Kantorovich mass transport problem, and it is the connection between the two
problems that brought out numerous developments and generalisations as well as
many new problems. We will highlight these links and regard cyclic
monotonicity as a geometric notion of optimality of a transport plan (see
Section 2 for a review of the relevant notions).

The optimal transport or Monge-Kantorovich problem is widely known in the
literature, and there are several extensive books that allow readers of any
level to learn the basic as well as the advanced theory (e.g. see [2, 39,
37]). Let $X$ and $Y$ be topological spaces and let $\mu$ and $\nu$ be Borel
probability measures on $X$ and $Y$, respectively. We denote by $p_{Z}$ the
projection onto a subspace $Z$, and we set

$\Pi(\mu,\nu)=\\{\gamma\in\mathcal{P}(X\times Y)\ :\ p_{X}(\gamma)=\mu,\ \
p_{Y}(\gamma)=\nu\\}.$

This is the set of all transport plans between $\mu$ and $\nu$, i.e. all
probability measures $\gamma$ on the product space $X\times Y$ such that for
any Borel sets $A\subset X,\,B\subset Y$ we have $\gamma(A\times Y)=\mu(A)$
and $\gamma(X\times B)=\nu(B)$. Given a Borel cost function $c:X\times
Y\to\mathbb{R}\cup\\{+\infty\\}$ the Kantorovich formulation of the optimal
transportation problem is to find a plan that minimises the total cost, that
is

$\min_{\gamma\in\Pi(\mu,\nu)}\int c(x,y)d\gamma.$ (1)

It is intuitively clear that if a plan $\gamma$ is optimal with respect to a
cost $c$, then for any number $m\in\mathbb{N}$ of points
$\\{(x_{i},y_{i})\\}_{i=1}^{m}\in{\rm supp}(\gamma)$, the total transport cost
of this coupling, which can be written as $\sum_{i=1}^{m}c(x_{i},y_{i})$,
should increase if instead we pair $x_{i}$’s and $y_{j}$’s in a different way.
This is exactly the concept behind _$c$ -cyclic monotonicity_ that will be
studied in detail in the following section.

##  2 Cyclic monotonicity, potentials and generalizations

###  2.1 Monotonicity and cyclic monotonicity

Let $X=Y=\mathbb{R}^{n}$. Recall that a function $f:X\to Y$ is monotone if for
any $(x_{i},y_{i}),(x_{j},y_{j})\in~{}{\rm graph}(f)$ we have that

$\langle x_{i}-x_{j},y_{i}-y_{j}\rangle\geq 0.$

This classical notion, also referred to as $2$-monotonicity, can be
generalised to $N$-point-cyclic monotonicity, and further to cyclic
monotonicity, which we define below, and which was introduced by Rockafellar
in [32]. Let us remark that Rockafellar considered a more general setting,
where $X$ is a topological vector space over $\mathbb{R}$ and $Y=X^{*}$ is its
topological dual.

By ${\mathcal{S}_{k}}$ we denote the set of all permutations on $k$ elements.

######  Definition 1.

A subset $\Gamma\subset X\times Y$ is _cyclically monotone_ if for all
$k\in\mathbb{N}$ and for all $\\{(x_{i},y_{i})\\}_{i=1}^{k}\subset\Gamma$

$\sum_{i=1}^{k}\langle x_{i}-x_{\sigma(i)},y_{i}\rangle\geq 0,$

holds for any permutation $\sigma\in{\mathcal{S}_{k}}$, where we set
$x_{k+1}:=x_{1}$.

By a basic theorem on permutations of $k$ objects the above condition is
equivalent to simply requiring that $\sum_{i=1}^{k}\langle
x_{i}-x_{i+1},y_{i}\rangle\geq 0$ holds for all $k\in\mathbb{N}$ and any
$k$-tuple of points $\\{(x_{i},y_{i})\\}_{i=1}^{k}\subset\Gamma$. Moreover,
note that cyclic monotonicity is a property of a set, and that if $\Gamma$ is
cyclically monotone then any subset of $\Gamma$ has the same property. An
important fact is that if $\varphi:X\to[-\infty,+\infty]$ is a convex function
then $\partial\varphi=\\{(x,y):\,\varphi(z)-\varphi(x)\geq\langle
y,z-x\rangle,\ \forall z\\}\subset X\times Y$, is cyclically monotone.
$\partial\varphi$ (see, e.g. the books [27, 33, 35]) is usually called the
“subdifferential” of $\varphi$, and any $y\in\partial\varphi(x)$ is a
subgradient of $\varphi$ at $x$.

The celebrated Rockafellar’s theorem states that the inverse is also true:

######  Theorem 2 ([32, Theorem 1], see also [33, 34, Theorem 24.8]).

Let $\,\Gamma\subset X\times Y$ be a cyclically monotone set. Then there
exists a convex function $\varphi:X\to\mathbb{R}$ such that
$\Gamma\subset\partial\varphi$.

We say that a function $\varphi$ is a _potential_ for $\Gamma$ if its
subgradient contains the set $\Gamma$. The proof of this theorem is
constructive and we present it in the more general setting of Theorem 7.

Rockafellar’s result may be further refined proving that
$\Gamma=\partial\varphi$ (so it is not a proper subset) if it is maximal (i.e.
not properly contained in any cyclically monotone set). Maximal $2$-cyclic
monotone sets were studied, in particular, by Minty [26].

It turns out that cyclic monotonicity can be equivalently described using the
square of the Euclidean norm, denoted by $\|\cdot\|$. Indeed, a set
$\Gamma\subset X\times Y$ is cyclically monotone if for all $k\in\mathbb{N}$
and for all $\\{(x_{i},y_{i})\\}_{i=1}^{k}\subset\Gamma$

$\sum_{i=1}^{k}\|x_{i}-y_{i}\|^{2}\leq\sum_{i=1}^{k}\|x_{i}-y_{i+1}\|^{2}.$

Clearly, this can be seen by expanding the above expression (see also Remark
3). Further, this observation is also true if $X$ is a Hilbert space $H$ and
$Y=X^{*}$ with the canonical identification $X^{*}=H$, where we denote the
norm in $H$ by $\|\cdot\|$.

###  2.2 Extensions of cyclic monotonicity

Some natural extensions of the notion above will be of interest. The first one
involves a more general cost function.

####  2.2.1 $c$-cyclic monotonicity

Let $X$ and $Y$ be two sets and let

$c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$

be a _cost function_. We say that $\Gamma\subset X\times Y$ is _$c$
-cyclically monotone_ if for all $k\in\mathbb{N}$ and
$~{}\\{(x_{i},y_{i})\\}_{i=1}^{k}\subset\Gamma$ and for any permutation
$\sigma\in{\mathcal{S}}_{k}$

$\sum_{i=1}^{k}c(x_{i},y_{i})\leq\sum_{i=1}^{k}c(x_{i},y_{\sigma(i)}).$

Clearly, cyclic monotonicity corresponds to the choice $c(x,y)=-\langle
x,y\rangle$, or equivalently $c(x,y)=\|x-y\|^{2}/2$, which we will refer to as
the _quadratic cost_.

######  Remark 3.

Note that, as in the case of the quadratic cost, adding ’non-mixing’ terms to
the cost does not influence $c$-cyclic monotonicity. More precisely, let
$c(x,y)$ be a cost function and define $\tilde{c}(x,y)=c(x,y)+p(x)+q(y)$ for
some functions $p,q$. Then a set is $c$-cyclically monotone if and only if it
is $\tilde{c}$-cyclically monotone (see e.g. [24]).

It was shown in [31, 36] that if the cost $c$ attains only finite values then,
as in the case of cyclic monotonicity, a set is $c$-cyclically monotone if and
only if it is contained in the graph of the $c$-subdifferential of a $c$-class
function. Let us recall the relevant definitions.

######  Definition 4.

The _$c$ -transform_ of a function $\varphi:X\to[-\infty,+\infty)$ is a
function $\varphi^{c}:Y\to[-\infty,+\infty]$ given by

$\varphi^{c}(y)=\inf_{x\in X}\left(c(x,y)-\varphi(x)\right).$

Similarly, when $\psi:Y\to[-\infty,+\infty)$, we use the same notation to
define

$\psi^{c}(x)=\inf_{y\in Y}\left(c(x,y)-\psi(y)\right).$

This type of conjugate functions appeared in [27] and is an elemental notion
in the theory of optimal transport. The $c$-transform is order-reversing (with
respect to a pointwise order) and it is an involution on its “$X$-image” and
“$Y$-image”, respectively. In many applications $X=Y$ and $c$ is symmetric,
i.e. $c(x,y)=c(y,x)$, in which case the image

${\mathcal{C}}:=\\{\varphi:X\to[-\infty,+\infty)\
:\,\exists\psi:X\to[-\infty,+\infty)\text{ such that }\psi^{c}=\varphi\\}$

is called the _$c$ -class_.

######  Definition 5.

Given a function $\varphi:X\to[-\infty,+\infty)$ its _$c$ -subgradient_ is
given by

$\partial^{c}\varphi=\\{(x,y)\in X\times Y~{}:~{}c(x,y)<\infty\text{ and
}c(x,y)-\varphi(x)\leq c(z,y)-\varphi(z)\text{ for all }z\in X\\}.$

######  Remark 6.

There is an alternative way of defining the $c$-subgradient of a function
$~{}{\varphi:X\to[-\infty,+\infty)}$, that is

$\tilde{\partial}^{c}\varphi=\\{(x,y)\in X\times
Y~{}:~{}\varphi(x)+\varphi^{c}(y)=c(x,y)<+\infty\\}.$

Since it is possible that $\varphi(x)=-\infty$ and $\varphi^{c}(y)=+\infty$,
some assumptions must be added to ensure that this definition is well-given.
For example, if we know that

$\text{There exists }x^{\prime}\in X\text{ such that
}c(x^{\prime},y)\in\mathbb{R}\text{ and }\varphi(x^{\prime})\in\mathbb{R},$

then $\varphi^{c}(y)\in\mathbb{R}\cup\\{-\infty\\}$ and
$(x,y)\in\partial^{c}\varphi$ if and only if
$(x,y)\in\tilde{\partial}^{c}\varphi$.

Clearly, for a symmetric cost, $(x,y)\in\partial^{c}\varphi$ if and only if
$(y,x)\in\partial^{c}\varphi^{c}$.

The following theorem is the generalisation of Rockafellar’s theorem due to
Rochet and Rüschendorf.

######  Theorem 7 ([31, Theorem 1], [36, Lemma 2.1]).

Let $X,\,Y$ be any sets and let $c:X\times Y\to\mathbb{R}$ be a cost function.
A set $\Gamma\subset X\times Y$ is $c$-cyclically monotone if and only if
there exists a $c$-class function $\varphi$ such that
$\Gamma\subset\partial^{c}\varphi$, i.e. $\varphi$ is a potential for
$\Gamma$.

###### Proof.

Let $\Gamma$ be a $c$-cyclically monotone set. Let $(x_{0},y_{0})\in\Gamma$
and define $\varphi:X\to\mathbb{R}$ as follows

$\begin{split}\varphi(x)=\inf\\{c(x,y_{n})-c(x_{n},y_{n})+c(x_{n},y_{n-1})-c(x_{n-1},y_{n-1})+\dots+\\\
c(x_{1},y_{0})-c(x_{0},y_{0}):~{}(x_{i},y_{i})\in\Gamma\ \mbox{for}\
i=1,\dots,n,\ n\in\mathbb{N}.\\}\end{split}$ (2)

Since $\Gamma$ is $c$-cyclically monotone, $\varphi(x_{0})=0$ (taking $n=1$
and $(x_{1},y_{1})=(x_{0},y_{0})$) and $\varphi$ is a $c$-class function. To
show that $\Gamma\subset\partial^{c}\varphi$ consider
$(x^{\prime},y^{\prime})\in\Gamma$, and $\varepsilon>0$ and let
$(x_{1},y_{1}),\dots,(x_{n},y_{n})\in\Gamma$ be a chain such that

$c(x^{\prime},y_{n})-c(x_{n},y_{n})+c(x_{n},y_{n-1})-c(x_{n-1},y_{n-1})+\dots+c(x_{1},y_{0})-c(x_{0},y_{0})\leq\varphi(x^{\prime})+\varepsilon.$

Let $z\in X$, since $(x^{\prime},y^{\prime})\in\Gamma$ we can consider the
chain $(x_{1},y_{1}),\dots,(x_{n},y_{n}),(x^{\prime},y^{\prime})$ among the
admissible chain for the definition of $\varphi(z)$ and get

$\varphi(z)\leq
c(z,y^{\prime})-c(x^{\prime},y^{\prime})+\varphi(x^{\prime})+\varepsilon.$

Since $\varepsilon$ is arbitrary this implies
$(x^{\prime},y^{\prime})\in\partial^{c}\varphi$. Since $\varphi(x_{0})=0$ and
$c$ assumes only real values, this last inequality, choosing
$(x^{\prime},y^{\prime})=(x_{0},y_{0})$, also implies $\varphi(z)<+\infty$. ∎

The above theorem guarantees the existence of a potential for finite-valued
cost functions. However, if the cost does attain the value $+\infty$ this
statement is no longer true. See, for instance, [5] where the authors present
an example of a set that is $c$-cyclically monotone but whose graph is not
supported on the $c$-subgradient of any function. In the attempt to use
formula (2) above in a more general setting, in [9], the notion of _$c$
-connectivity_ is proposed and is shown to be sufficient to guarantee the
existence of a potential.

######  Definition 8.

Let $X,Y$ be sets, $c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$ be a cost
function and $\Gamma\subset X\times Y$. We denote
$(x,y)\precsim(\tilde{x},\tilde{y})$ if there exist pairs
$(x_{0},y_{0}),\dots,(x_{n},y_{n})\in\Gamma$ with $(x_{0},y_{0})=(x,y)$ and
$(x_{n},y_{n})=(\tilde{x},\tilde{y})$ such that
$c(x_{1},y_{0}),\dots,c(x_{n},y_{n-1})<+\infty$. If
$(x,y)\precsim(\tilde{x},\tilde{y})$ and $(\tilde{x},\tilde{y})\precsim(x,y)$,
we denote $(x,y)\approx(\tilde{x},\tilde{y})$. We say that $\Gamma$ is _$c$
-connecting_ if $c(x,y)$ is finite for all $(x,y)\in\Gamma$ and if for all
$(x,y),(\tilde{x},\tilde{y})\in\Gamma$ we have
$(x,y)\approx(\tilde{x},\tilde{y})$.

Note that $\approx$ is an equivalence relation on $X\times Y$. If the cost
function is real-valued then all sets are trivially connecting. Hence,
$c$-connecting sets do not need to be $c$-cyclically monotone and so, on its
own, $c$-connectivity does not capture optimality in a way that $c$-cyclic
monotonicity does. However, if a $c$-connecting set $\Gamma$ is also
$c$-cyclically monotone then, for any cost function, there exists a
$c$-potential which can be obtained using Rockafellar’s approach. Indeed, the
$c$-connectivity, together with $c$-cyclical monotonicity, implies that the
function $\varphi$ defined by the formula (2) is real-valued everywhere on the
projection $p_{X}(\Gamma)$, which means that one can proceed with the proof as
in the case of a real-valued cost function $c$.

However, in general, the $c$-connectivity of $\Gamma$ is not a necessary
condition for the existence of a potential, which can be seen on simple
discrete examples. In [5], the authors show that for general costs _$c$ -path-
boundedness_ is the notion equivalent to the existence of a potential. We
discuss it in the next subsection.

####  2.2.2 $c$-path-boundedness

When the cost function is allowed to take infinite values, an important case
that has been considered on the case-by-case basis (e.g. see [10, 11, 12, 14,
20]), the $c$-cyclic monotonicity is not sufficient to guarantee the existence
of a potential. It was shown in [5] that a natural condition to consider is
$c$-path-boundedness.

######  Definition 9.

Fix sets $X,\,Y$ and $c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$. We say that
$\Gamma\subset X\times Y$ is _$c$ -path-bounded_ if $c(x,y)<\infty$ for any
$(x,y)\in\Gamma$, and for any $(x,y)\in\Gamma$ and $(z,w)\in\Gamma$, there
exists a constant $M=M((x,y),(z,w))\in\mathbb{R}$ such that for any
$m\in{\mathbb{N}}$ and any $\\{(x_{i},y_{i}):1\leq i\leq m\\}\subset\Gamma$ we
have

$c(x,y)-c(x_{1},y)+\sum_{i=1}^{m-1}\big{(}c(x_{i},y_{i})-c(x_{i+1},y_{i})\big{)}+c(x_{m},y_{m})-c(z,y_{m})\leq
M$

A $c$-path-bounded set must be $c$-cyclically monotone; indeed, if there is
some cycle for which the sum is positive, then, choosing one point on this
cycle to be both the beginning and the end of a path, one can replicate it
many times to get paths with arbitrarily large sums. Further, if the cost is
finite-valued then $c$-path-boundedness and $c$-cyclic monotonicity are
equivalent as we may choose $M=c(x,w)-c(z,w)<+\infty$.

As mentioned before, for costs attaining infinite values, $c$-connectivity
together with $c$-cyclic monotonicity implies $c$-path-boundedness. However, a
$c$-path bounded set is not always $c$-connecting. Indeed, consider, for
example, any cost function
$c:\mathbb{R}\times\mathbb{R}\to\mathbb{R}\cup\\{+\infty\\}$, which is finite
on the set $S:=\\{(x,y)\in\mathbb{R}^{2}:\ x+y>0\\}$ and $+\infty$ otherwise.
We may easily choose $\Gamma$ to consist of two points
$(x_{1},y_{1}),\,(x_{2},y_{2})$ such that $(x_{i},y_{i})\in S$ for $i=1,2$,
and which form a $c$-cyclically monotone set, but such that
$(x_{1},y_{2})\notin S$ which means that $\Gamma$ is not $c$-connecting. But
since there are only two points in $\Gamma$ it is easy to check that it is
$c$-path-bounded, and one can easily find a potential. For a much more
elaborate example but with more details provided see Example 36 in Appendix A.

The following theorem established in [5] states that $c$-path-boundedness of a
set is equivalent to the existence of a potential.

######  Theorem 10 ([5, Theorem 1]).

Let $X,\,Y$ be two arbitrary sets and $c:X\times
Y\to\mathbb{R}\cup\\{+\infty\\}$ an arbitrary cost function. For a given
subset $\Gamma\subset X\times Y$ there exists a $c$-class function
$~{}{\varphi:X\to[-\infty,+\infty]}$ such that
$\Gamma\subset\partial^{c}\varphi$ if and only if $\Gamma$ is $c$-path-
bounded.

The proof of this theorem differs greatly from the proofs in the case of
finite-valued costs. The authors reformulated the problem of finding a
$c$-potential for a given set as the problem of existence of a solution to a
special family of linear inequalities. More precisely, the following theorem
was proved in [5].

######  Theorem 11 ([5, Theorem 3.1]).

Let $c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$ be a cost function and let
$\Gamma\subset X\times Y$. Then there exists a $c$-potential for $\Gamma$,
namely a $c$-class function $~{}\varphi:X\to[-\infty,+\infty]$ such that
$\Gamma\subset\partial^{c}\varphi$ if and only if the following system of
inequalities,

$c(x,y)-c(z,y)\leq\varphi(x)-\varphi(z),$ (3)

indexed by $(x,y),(z,w)\in\Gamma$, has a solution
$\varphi:p_{X}\Gamma\to\mathbb{R}$, where $~{}{p_{X}\Gamma=\\{x\in X:\exists
y\in Y,(x,y)\in\Gamma\\}}$.

######  Remark 12.

The inequalities in the above theorem can be equivalently indexed by pairs
$((x,y),z)\in\Gamma\times p_{X}\Gamma$, where $w$ is ignored as it does not
appear in the inequalities. Moreover, note that the solution vector
$(\varphi(x))_{x\in p_{X}\Gamma}$ is indexed by $p_{X}\Gamma$. One may worry
that in fact we obtain a vector $(\varphi(x,y))_{(x,y)\in G}$, which seems
multi-valued. However, the authors observe that if $(x,y)$ and
$(x,y^{\prime})$ are both in $\Gamma$ then, writing out the relevant
inequalities for these two points, we get that
$\varphi(x,y)=\varphi(x,y^{\prime})$. In other words, the solution vector
indeed only depends on the first coordinate.

Intuitively, the above theorem says the following: since for every
$(x_{i},y_{i})\in\Gamma$ letting $\varphi_{i}(x)=c(x,y_{i})-a_{i}$ we have
that $\partial^{c}\varphi_{i}(x_{i})=y_{i}$ for any $a_{i}\in\mathbb{R}$, what
one needs to take care of is the “good gluing” of such functions, i.e. the
existence of constants $a_{i}$ such that the function
${\varphi_{a}(x):=\min_{(x_{i},y_{i})\in\Gamma}\varphi_{i}(x)}$ satisfies for
every $x_{i}\in p_{X}\Gamma$ that $\varphi_{a}(x_{i})=\varphi_{i}(x_{i})$.
Therefore, finding a potential amounts to showing that there exists a solution
$a$ to the family of inequalities

$c(x_{i},y_{i})-a_{i}\leq c(x_{i},y_{j})-a_{j}.$

The authors then show that given $\\{\eta_{i,j}\\}_{i,j\in
I}\in[-\infty,+\infty)$, where $I$ is some arbitrary index set and with
$\eta_{i,i}=0$, the system of inequalities

$\eta_{i,j}\leq a_{i}-a_{j},\quad i,j\in I$

has a solution if and only if for any $i,j\in I$ there exists some constant
$M(i,j)$ such that for any $m$ and any $i_{2},\cdots,i_{m-1}$, letting
$i=i_{1}$ and $j=i_{m}$ one has that $\sum_{k=1}^{m-1}\eta_{i_{k},i_{k+1}}\leq
M(i,j)$. This directly translates into $c$-path-boundedness.

The proof of the solvability of the system of inequalities uses Zorn’s lemma.
The authors also give a new proof of Theorem 7, which can be found in [41].

Having established the existence of a potential one may want to consider its
regularity. This is a deep and hugely rich theory, which despite being
related, is different to what we consider in this note. Therefore, we will not
address these issues. We refer the interested reader to the second book of C.
Villani [39], which offers a useful starting point and many further
references.

####  2.2.3 Adding more variables

Finally, one may consider a _multi-dimensional_ version of the same ideas,
which to the best of our knowledge, was first introduced by Kim and Pass in
[23]. Let $X_{1},\dots,X_{N}$ be sets and

$c:X_{1}\times\dots\times X_{N}\to\mathbb{R}\cup\\{+\infty\\}.$

######  Definition 13.

We say that $\Gamma\subset X_{1}\times\dots\times X_{N}$ is _$c$ -cyclically
monotone_ if for all $k\in\mathbb{N}$ and
$\\{(x^{i}_{1},\dots,x^{i}_{N})\\}_{i=1}^{k}\subset\Gamma$ and for all
permutations $\sigma_{2},\dots,\sigma_{N}\in{\mathcal{S}}_{k}$, we have

$\sum_{i}c(x^{i}_{1},x^{i}_{2},\dots,x^{i}_{N})\leq\sum_{i}c(x^{i}_{1},x^{\sigma_{2}(i)}_{2}\dots,x^{\sigma_{N}(i)}_{N}).$

In correspondence to the $c$-subgradient for two variables, for the
multivariable case one considers $c$-splitting sets.

######  Definition 14.

A set $\Gamma\subset X_{1}\times\ldots\times X_{N}$ is called _$c$ -splitting_
if there exist $N$ functions $\varphi_{i}:X_{i}\to[-\infty,+\infty)$ such that

$\varphi_{1}(x_{1})+\varphi_{2}(x_{2})+\ldots+\varphi_{N}(x_{N})\leq
c(x_{1},x_{2},\ldots,x_{N})$

holds for all $(x_{1},x_{2},\ldots,x_{N})\in X_{1}\times\ldots\times X_{N}$,
and

$\varphi_{1}(x_{1})+\varphi_{2}(x_{2})+\ldots+\varphi_{N}(x_{N})=c(x_{1},x_{2},\ldots,x_{N})$

holds for all $(x_{1},x_{2},\ldots,x_{N})\in\Gamma$. We call the functions
$(\varphi_{1},\ldots,\varphi_{N})$ a $(\Gamma,c)$-splitting tuple.

Similarly to the two variables case, it is not difficult to check that a
$c$-splitting set is $c$-cyclically monotone. The reverse implication will be
discussed in Section 4.1.

The existence of the $(\Gamma,c)$-splitting tuple for a given set $\Gamma$ has
been investigated in some special cases. In particular, Bartz, Bauschke and
Wang [8, Theorem 2.7] showed that if the cost function $c$ can be written in
the form

$c(x_{1},\ldots,x_{N})=\sum_{1\leq i<j\leq N}c_{i,j}(x_{i},x_{j}),$

where $c_{i,j}:X_{i}\times X_{j}\to\mathbb{R}$, then if for each $1\leq
i<j\leq N$ the projection $\Gamma_{i,j}$ of $\Gamma\subset
X_{1}\times\ldots\times X_{N}$ onto $X_{i}\times X_{j}$ is
$c_{i,j}$-cyclically monotone, then $\Gamma$ is $c$-cyclically monotone, and
further, there exist a $c$-splitting tuple $(\varphi_{1},\ldots,\varphi_{N})$
given by

$\varphi_{i}(x_{i})=\sum_{i<j\leq N}\psi_{i,j}(x_{i})+\sum_{1\leq
j<i}\psi_{j,i}^{c_{j,i}}(x_{i}),$

where for every $1\leq i<j\leq N$ we have
$\psi_{i,j}:X_{i}\to[-\infty,+\infty]$ is the $c_{i,j}$-potential for
$\Gamma_{i,j}$.

######  Remark 15.

This statement can be now generalized to allow $c_{i,j}:X_{i}\times
X_{j}\to\mathbb{R}\cup\\{+\infty\\}$ if we additionally assume that
$\Gamma_{i,j}$ is $c_{i,j}$-path-bounded since, as we have seen, this
guarantees the existence of the functions $\psi_{i,j}$.

Clearly, the condition of $c_{i,j}$-cyclically monotone projections is
stronger than $c$-cyclic monotonicity on the whole set $\Gamma$, and the
authors present the relevant example in [8]. However, it turns out that if we
additionally assume that $X_{1}=\ldots=X_{N}=\mathbb{R}$ are one-dimensional,
then the two conditions are equivalent.

Let us remark that the maximal multimarginal $c$-monotonicity for the
“quadratic” multimarginal cost (in the spirit of Minty [26]) was considered in
[7].

##  3 Classical optimal transport

In this section we collect results connecting $c$-cyclic monotonicity and its
various extensions to optimality of a transport plan in the Monge-Kantorovich
problem (1). Prior to the detailed exploration of the deep relationship
between $c$-cyclic monotonicity and the optimality of transport plans, let us
recall the classical setup of two marginal transport problems and justify why
in this case one can expect a minimiser of the transport problem to exist.

Let $X$ and $Y$ be topological spaces and let $\mu$ and $\nu$ be Borel
probability measures on $X$ and $Y,$ respectively. Let

$c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$

be a Borel cost function that may assume the value $+\infty$. We say that
$c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$ is _essentially bounded_ with
respect to $\mu$ and $\nu$ if there exist upper semi-continuous functions
${a:X\to(-\infty,+\infty]}$, $a\in L^{1}(\mu)$ and $b:Y\to(-\infty,+\infty]$,
$b\in L^{1}(\nu)$ such that $c(x,y)\geq a(x)+b(y)$ for all $x\in X,\,y\in Y$.
Since we may absorb the functions $a$ and $b$ into the cost, instead of
writing that the cost is essentially bounded we will sometimes write that
$c:X\times Y\to[0,+\infty]$. One needs this assumption to avoid the situation
where there are plans with a total cost $-\infty$ (and hence nothing can be
inferred about the optimal plan).

If $c$ is assumed lower semi-continuous, then the ‘total cost’ functional

$C[\gamma]:=\int c(x,y)d\gamma$

is lower semi-continuous with respect to the weak∗ convergence of probability
measures. This fact, together with Prokhorov’s theorem [30] (see Th. 5.1.3 in
[3]) that assures compactness of the set of all transport plans
$\Pi(\mu,\nu)$, gives the existence of at least one minimiser of the transport
problem (1). This is captured in the following theorem which can be found, for
example, in [40].

######  Theorem 16 ([40, Theorem 4.1]).

Let $X,\,Y$ be two Polish spaces, $\mu\in\mathcal{P}(X)$ and
$\nu\in\mathcal{P}(Y)$. Let $c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$ be a
lower semi-continuous cost function which is essentially bounded with respect
to $\mu$ and $\nu$. Then there exists a $c$-optimal plan $\pi\in\Pi(\mu,\nu)$.

In the above theorem, the existence of a plan with finite total cost is not
assumed (nor guaranteed) and when no finite cost plan exists, any plan (say,
$\mu\otimes\nu$) is optimal. Therefore, in the results to follow, it will be
assumed that there exists a plan with finite total cost. A transport plan will
be called finite if its total cost is finite.

It is of interest to understand the structure of an optimal transport plan. It
turns out that “often” a transport plan is optimal if and only if it is
concentrated on a $c$-cyclically monotone set. There is a vast array of this
type of results, which we outline in this section.

###  3.1 Optimality implies $c$-cyclic monotonicity

Analysing the geometric structure of an optimal plan is a problem with a long
history. It seems that $c$-cyclic monotonicity first appeared in this context
in [24] in the following equivalent formulation of the Kantorovich’s problem

$\min\\{\int c(\mathfrak{X},\mathfrak{Y})d\omega\ :\ \mathfrak{X}\ \mbox{and}\
\mathfrak{Y}\ \mbox{random variables with}\ Law(\mathfrak{X})=\mu,\
Law(\mathfrak{Y})=\nu\\}.$ (4)

The equivalence between problems (4) and (1) can be seen in the following way:
If $\mathfrak{X}$ and $\mathfrak{Y}$ are admissible for (4) then the joint law
$\gamma=\mathfrak{X}\otimes\mathfrak{Y}_{\sharp}\omega$ is a transport plan in
$\Pi(\mu,\nu)$ and

$\int c(x,y)d\gamma=\int c(\mathfrak{X},\mathfrak{Y})d\omega.$

On the other hand if $\gamma\in\Pi(\mu,\nu)$ then one can choose
$(\Omega,\omega)=(X\times Y,\gamma)$ and $\mathfrak{X}=p_{X}$,
$\mathfrak{Y}=p_{Y}$. In that context, which was partly motivated by some
models appearing in financial mathematics, authors started by characterizing
optimal random variables using $c$-cyclic monotonicity. In such a model,
$\mathfrak{X}$ and $\mathfrak{Y}$ could represent the prices at a given moment
of two assets or resources. In a robust financial framework the joint
probability law of the portfolio $(\mathfrak{X},\mathfrak{Y})$ cannot be
determined from market information, however, the distribution of each price is
known. The cost $c$ could be interpreted as an option whose pay-off is
determined by the vector of prices $(\mathfrak{X},\mathfrak{Y})$ whose
distribution is then of interest (maximizing or minimizing is, clearly, the
same).

The classical structure of cyclic monotonicity of optimal plans was mentioned
as a possible alternative tool in Brenier [13] and explicitly exploited in
Caffarelli [15]. After that, Gangbo and McCann [19] extended the result to
lower semi-continuous cost functions bounded from below. They showed that
every finite optimal plan with respect to such a cost lies on a $c$-cyclically
monotone set.

For more general settings there are, essentially, two arguments to prove that
the support of the optimal plan must be $c$-cyclically monotone. The first one
uses duality and appeared in [24], while the second relies on modifying a
transport plan that is not $c$-cyclically monotone and showing that its cost
can be improved. The latter technique was introduced in [1] and used, for
example, in Proposition 2.24 of Villani111At the time when the book was
written the question of sufficiency of $c$-cyclic monotonicity was wide open.
In fact, Open Problem 2.25 of the same book (later solved by Schechermeyer and
Teichmann in [38]) asks whether sufficiency holds for the quadratic cost. [40]
for the quadratic cost $\|x-y\|^{2}$ or in Theorem 2.3 of [19] for a
continuous, positive cost.

To the best of our knowledge, the most general result was proved by Beiglböck,
Goldstern, Maresch, and Schachermayer [9] who removed regularity assumptions
on the cost:

######  Theorem 17 ([9, Theorem 1.a]).

Let $X,\,Y$ be Polish spaces equipped with Borel probability measures
$\mu,\nu$ and let $c:X\times Y\to[0,\infty]$ be a Borel measurable cost
function. Then every optimal transport plan with finite total cost is
$c$-cyclically monotone.

The reverse implication ($c$-cyclic monotonicity implies optimality) is not
true in general, and we collect known results and counterexamples in the rest
of this section.

###  3.2 When $c$-cyclic monotonicity implies optimality?

We begin by presenting an example from [4], which shows that one cannot always
expect $c$-cyclic monotonicity of the support of the plan to imply optimality.
In this example the cost is regular, namely lower semi-continuous. However, it
assumes not only real values but also the value $+\infty$.

######  Example 18 ([4, Example 3.1]).

Let $X=Y=[0,1]$ and let $\mu=\nu=\lambda$ be the Lebesgue measure. Letting
$\alpha\in[0,1)$ be an irrational number define

$\Gamma=\\{(x,x):x\in X\\},\ \ \ \ \ \Gamma_{\alpha}=\\{(x,x\oplus\alpha):x\in
X\\},$

where $\oplus$ is the addition modulo $1$. Define the cost $c=a\in[0,\infty)$
on $\Gamma$, $c=b\in[0,\infty)$ on $\Gamma_{\alpha}$ and $+\infty$ otherwise.
Now both sets $\Gamma$ and $\Gamma_{\alpha}$ are $c$-cyclically monotone.
Define maps $T:X\to X\times Y$ to be $T(x)=(x,x)$ and $T_{\alpha}:X\to X\times
Y$ to be $T_{\alpha}(x)=(x,x\oplus\alpha)$. These maps induce transport plans
$\pi=T_{\\#}\lambda$ and $\pi_{\alpha}=T_{\alpha\,\\#}\lambda$ which are
supported on $\Gamma$ and $\Gamma_{\alpha}$, respectively. Both of these plans
have finite total cost, equal to $a$ and $b$ respectively, which means that
the optimality depends on the choice of values $a,b$, while, as already
mentioned, both supports are $c$-cyclically monotone.

This example shows that one will have to assume something about the cost or
the transported measures. It turns out that a joint property of measures and
the cost is needed, which was shown by Beiglböck, Goldstern, Maresch, and
Schachermayer in [9].

######  Theorem 19 ([9, Theorem 1.b]).

Let $X,\,Y$ be Polish spaces equipped with Borel probability measures
$\mu,\,\nu$ and $c:X\times Y\to[0,\infty]$ a Borel measurable cost function.
Assume that the set $\\{(x,y)\in X\times Y:\,c(x,y)=+\infty\\}$ is the union
of a closed set $F$ and a $\mu\otimes\nu$-null set $N$. Let
$\gamma\in\Pi(\mu,\nu)$ be a finite and $c$-cyclically monotone plan. Then
$\gamma$ is optimal.

This result is the state of the art, establishing when the equivalence of
optimality and $c$-cyclic monotonicity holds. Nevertheless, in what follows,
we are going to present some prior developments of this problem as we find it
interesting and instructive. Moreover, it will give the reader the idea behind
the proof of the above theorem.

####  3.2.1 Finitely-supported measures

For finite spaces $X$ and $Y$ or, equivalently, for finitely-supported
measures $\mu$ and $\nu$ one can prove that

######  Theorem 20.

Assume that $\mu$ and $\nu$ are finitely-supported Borel probability measures
on Polish spaces $X$ and $Y$, respectively. A transport plan
$\gamma\in\Pi(\mu,\nu)$ is optimal with respect to the optimal transport
problem corresponding to a cost function $c:X\times Y\to\mathbb{R}$ if and
only if it is $c$-cyclically monotone.

The above theorem can be proved in several different ways. The first and,
probably, more popular one, uses linear programming but, despite being part of
the folklore, we cannot find a complete reference with proof. Several results
for finitely supported measures are contained in [17]. In the quadratic case,
this result is left as an exercise (Exercise 2.21) in [40]. Further, we remark
that it is a particular case of Theorem 21 below. In Appendix B we give
another proof that uses a peculiar structure of finitely-supported transport
plans with the same marginals. More precisely, given two finitely-supported
transport plans with the same marginals, it is possible to obtain one of them
by permuting the coordinates of points in the support of the other.

Using Theorem 20 and the density of convex combinations of discrete measures
in the space of probability measures one can prove that there exists an
optimal transport plan with $c$-cyclically monotone support for general
marginal measures $\mu\in\mathcal{P}(X),\ \nu\in\mathcal{P}(Y)$ (see [25] and
Remark 2.26 in [40]).

####  3.2.2 Purely atomic measures

In [29], Pratelli shows that if the measures $\mu$ and $\nu$ are purely atomic
(that is, concentrated on at most countable sets) then optimality and
$c$-cyclic monotonicity are indeed equivalent.

######  Theorem 21 ([29, Theorem A]).

Let $X$ and $Y$ be Polish spaces, $\mu\in\mathcal{P}(X)$ and
$\nu\in\mathcal{P}(Y)$ purely atomic, and $c:X\times Y\to[0,\infty]$ a cost
function. Then a finite transport plan $\gamma\in\Pi(\mu,\nu)$ is optimal if
and only if it is concentrated on a $c$-cyclically monotone set.

In the same paper, using the above theorem and an approximation argument,
Pratelli obtains a result for general measures under the assumption of
continuity of the cost.

####  3.2.3 General measures

As mentioned above, Pratelli [29] shows, for any Borel measures, that if the
cost is continuous the equivalence holds.

######  Theorem 22 ([29, Theorem B]).

Let $X$ and $Y$ be Polish spaces, $\mu\in\mathcal{P}(X)$ and
$\nu\in\mathcal{P}(Y)$, and assume that the cost function $c:X\times
Y\to[0,\infty]$ is continuous. Then a finite transport plan
$\gamma\in\Pi(\mu,\nu)$ is optimal if and only if it is concentrated on a
$c$-cyclically monotone set.

Instead of insisting on the cost being continuous, it turns out that the
statement holds for any real-valued Borel cost. A posteriori, this can be seen
from Theorem 19. Indeed, for any finite-valued cost function the set
$\\{(x,y):\,c(x,y)=+\infty\\}$ is empty and hence satisfies the conditions of
the theorem, which in turn means that optimality and $c$-cyclic monotonicity
of the plan are equivalent. Since Theorem 19 has a complex proof we choose to
first show the statement for real-valued costs. We use the fundamental steps
from [9] and, for clarity, we add more detail.

######  Theorem 23.

Let $X,\,Y$ be Polish spaces equipped with Borel probability measures
$\mu,\nu$, and let $c:X\times Y\to[0,\infty)$ ($c$ is real-valued) be a Borel
measurable cost function. Then every $c$-cyclically monotone transport plan
$\gamma$ with finite total cost is optimal.

###### Proof.

Let $\Gamma$ be a cyclically monotone set such that $\gamma(\Gamma)=1$. By
Theorem 7, since $c$ is real-valued, there exists a function
$\varphi:X\to\mathbb{R}\cup\\{-\infty\\}$ such that
$\Gamma\subset\partial^{c}\varphi$. In particular, this implies that

$c(x,y)-\varphi(x)\leq c(x^{\prime},y)-\varphi(x^{\prime}),\ \forall
x^{\prime}\in X,\ (x,y)\in\Gamma.$

In fact, Theorem 7 gives a formula for $\varphi$, which we use to prove, in
line with [9], that $\varphi$ is universally measurable. This, together with
an argument showing integrability, yields the optimality of the plan.

A crucial ingredient of the proof is the fact that the image of a Borel set
via a Borel map is universally measurable (we recall the definition and the
relevant facts about _universal measurability_ in Appendix C). To show this,
we analyse the function defined in (2) by splitting the minimisation process
in two steps. First we minimise among chains of fixed length $n$, and define

$\varphi_{n}(x)=\inf\\{c(x,y_{n})-c(x_{n},y_{n})+c(x_{n},y_{n-1})-c(x_{n-1},y_{n-1})+\dots+\\\
c(x_{1},y_{0})-c(x_{0},y_{0}):\,(x_{i},y_{i})\in\Gamma\ \ \mbox{for}\ \
i=1,\dots,n\\}.$

Then we minimise with respect to $n$, which gives the potential

$\varphi(x)=\inf_{n}\varphi_{n}(x).$

Since $c$ is Borel measurable, we get that for each $n$ and any $n$-tuple of
points in $\Gamma$ the function

$c(x,y_{n})-c(x_{n},y_{n})+c(x_{n},y_{n-1})-c(x_{n-1},y_{n-1})+\dots+\\\
c(x_{1},y_{0})-c(x_{0},y_{0})$

is a Borel measurable function on $X\times\Gamma^{n}$. Hence, for each $n$ and
$\alpha\in\mathbb{R}$ the set

$\displaystyle L_{\alpha}^{n}:=\big{\\{}(x,y_{n},x_{n},\ldots,y_{0},x_{0}):\
c(x,y_{n})-c(x_{n},y_{n})+$ $\displaystyle
c(x_{n},y_{n-1})-c(x_{n-1},y_{n-1})+$
$\displaystyle+\dots+c(x_{1},y_{0})-c(x_{0},y_{0})<\alpha\big{\\}}$

is a Borel subset of $X\times\Gamma^{n}$. Since

$\\{x:\ \varphi(x)<\alpha\\}=\cup_{n}\\{x:\ \varphi_{n}(x)<\alpha\\},$ $\\{x:\
\varphi_{n}(x)<\alpha\\}=p_{X}(L^{n}_{\alpha})$

and $p_{X}$ is a Borel function, we obtain the universal measurability of
$\varphi$.

We now show that there exists a Borel measurable function $\tilde{\varphi}$
such that

$\tilde{\varphi}\leq\varphi\ \ \ \mbox{ and }\ \ \ \tilde{\varphi}=\varphi\ \
\mu-a.e.$

Indeed let ${\mathcal{I}}=\\{I_{n}\\}$ be the family of half-closed intervals
$[a_{n},b_{n})$ with rational endpoints. Observe that $\mathcal{I}$ generates
the Borel $\sigma$-algebra on $\mathbb{R}$. Let $\tilde{\mu}$ be the
completion of $\mu$ (for the definition see (16) in Appendix C). Since
$\varphi$ is universally measurable, $\varphi^{-1}(I_{n})$ is
$\tilde{\mu}$-measurable and thus can be written as the union of sets
$B_{n}\cup N_{n}$ with $B_{n}$ Borel measurable and $\mu(N_{n})=0$. Let
$N=\cup_{n}N_{n}$ we define

$\tilde{\varphi}(x)=\begin{cases}-\infty&\mbox{if}\ x\in N,\\\
\varphi(x)&\mbox{otherwise.}\end{cases}$

We then consider $\Gamma_{1}:=\Gamma\setminus p_{X}^{-1}(N)$ which is a
$c$-cyclically monotone Borel set such that $\gamma(\Gamma_{1})=1$ and

$c(x,y)-\tilde{\varphi}(x)\leq c(x^{\prime},y)-\tilde{\varphi}(x^{\prime}),\ \
\forall x^{\prime}\in X,\ (x,y)\in\Gamma_{1}.$

Moreover $\tilde{\varphi}(x)\in\mathbb{R}$ on $p_{X}(\Gamma_{1})$. We proceed,
as usual, passing to a $c$-transform of the candidate Kantorovich potential
$\tilde{\varphi}$. Define

$\psi(y)=\inf_{x\in p_{X}(\Gamma_{1})}\\{c(x,y)-\tilde{\varphi}(x)\\}.$

The function $\psi$ is universally measurable since

$\\{y:\ \psi(y)<\alpha\\}=p_{Y}(\\{(x,y)\in\Gamma_{1}:\
c(x,y)-\tilde{\varphi}(x)<\alpha\\}),$

and $\\{(x,y):\ c(x,y)-\tilde{\varphi}(x)<\alpha\\}$ is a Borel set since $c$
and $\tilde{\varphi}$ are Borel measurable. Notice, also, that

$\tilde{\varphi}(x)+\psi(y)=c(x,y),\ \forall(x,y)\in\Gamma_{1},$

and

$\tilde{\varphi}(x)+\psi(y)\leq c(x,y),\ \forall(x,y)\in
p_{X}(\Gamma_{1})\times Y,$

As in the previous case, assigning the value $-\infty$ on a $\nu$-null set
$\tilde{N}$, we consider a Borel measurable
$\tilde{\psi}:Y\to[-\infty,+\infty)$ such that

$\tilde{\psi}\leq\psi\ \ \mbox{and}\ \ \tilde{\psi}=\psi\ \nu-a.e.$

We define $\Gamma_{2}:=\Gamma_{1}\setminus p_{Y}^{-1}(\tilde{N})$. The set
$\Gamma_{2}$ is Borel measurable and $c$-cyclically monotone, and
$\gamma(\Gamma_{2})=1$. Moreover

$\tilde{\varphi}(x)+\tilde{\psi}(y)=c(x,y),\ \forall(x,y)\in\Gamma_{2}$

and

$\tilde{\varphi}(x)+\tilde{\psi}(y)\leq c(x,y),\ \forall(x,y)\in
P_{X}(\Gamma_{1})\times Y.$

Since the potential needs to be defined everywhere on $X\times Y$ we let
$\tilde{\varphi}$ be $-\infty$ outside $p_{X}(\Gamma_{2})$.

As a result we obtain a pair of Borel measurable functions
$(\tilde{\varphi},\tilde{\psi})$, which is $c$-splitting for the
$c$-cyclically monotone set $\Gamma_{2}$ on which $\gamma$ is concentrated.
The possible lack of integrability of $\tilde{\varphi}$ and $\tilde{\psi}$
does not allow us to deduce the optimality of $\gamma$ in the usual way, that
is integrating directly expressions $\tilde{\varphi}+\tilde{\psi}=c$ on the
support of $\gamma$ and $\tilde{\varphi}+\tilde{\psi}\leq c$ everywhere. We
use truncations instead.

We fix an arbitrary transport plan $\gamma^{\prime}\in\Pi(\mu,\nu)$; we may
assume that $C[\gamma^{\prime}]<+\infty$. We consider truncated potentials
$\tilde{\varphi}_{n}=(n\wedge(\tilde{\varphi}\vee-n))$ and
$\tilde{\psi}_{n}=(n\wedge(\tilde{\psi}\vee-n))$ and denote
$\xi=\tilde{\varphi}+\tilde{\psi}$,
$\xi_{n}=\tilde{\varphi}_{n}+\tilde{\psi}_{n}$. Now $\xi^{n}\uparrow\xi^{+}$
on the set $\\{\xi\geq 0\\}$, $\xi^{n}\downarrow\xi^{-}$ on the set
$\\{\xi\leq 0\\}$ and by monotone convergence, as $n\to\infty$,

$\displaystyle\int_{\xi\geq 0}\xi_{n}d\gamma\uparrow\int_{\xi\geq 0}\xi
d\gamma<+\infty,~{}~{}~{}\int_{\xi\geq
0}\xi_{n}d\gamma^{\prime}\uparrow\int_{\xi\geq 0}\xi
d\gamma^{\prime}<+\infty,$ $\displaystyle\int_{\xi\leq
0}\xi^{n}d\gamma\downarrow\int_{\xi\leq 0}\xi
d\gamma~{}~{}~{}\text{and}~{}~{}~{}\int_{\xi\leq
0}\xi_{n}d\gamma^{\prime}\downarrow\int_{\xi\leq 0}\xi d\gamma^{\prime}.$

Therefore the integrals of $\xi$ with respect to $\gamma$ and
$\gamma^{\prime}$ are well-defined, and

$\lim_{n\to\infty}\int\xi_{n}d\gamma=\int\xi
d\gamma~{}~{}~{}\text{and}~{}~{}~{}\lim_{n\to\infty}\int\xi_{n}d\gamma^{\prime}=\int\xi
d\gamma^{\prime}.$

Note that since $\gamma$ and $\gamma^{\prime}$ have the same marginals, we
have

$\displaystyle\int\xi
d\gamma=\lim_{n\to\infty}\int\xi_{n}d\gamma=\lim_{n\to\infty}\left(\int\tilde{\varphi}_{n}d\mu+\int\tilde{\psi}_{n}d\nu\right)$
$\displaystyle=\lim_{n\to\infty}\int\xi_{n}d\gamma^{\prime}=\int\xi
d\gamma^{\prime}.$

The optimality of $\gamma$ now readily follows since

$\displaystyle C[\gamma]$ $\displaystyle=\int cd\gamma=\int\xi d\gamma=\int\xi
d\gamma^{\prime}\geq\int cd\gamma^{\prime}=C[\gamma^{\prime}].\qed$

Note that the starting point of the above proof of Theorem 23 is the formula
(2) which in Theorem 7 gives the existence of a real-valued potential.
However, as we have seen in Section 2, when the cost attains infinite values
this approach fails. Hence, some assumptions must be added to give sense to
the formula, and a useful notion to consider seems to be $c$-connectivity
(recall Definition 8).

Another approach is to arrive at the existence of a potential without the use
of a formula of the type (2). In fact it was shown in [5] that if the cost
attains infinite values then $c$-cyclic monotonicity is no longer equivalent
to the existence of a potential (see example at the end of Section 2). The
authors established that a necessary and sufficient condition for the
existence of a potential is that of $c$-path-boundedness (see Definition 9).
This approach also appears in the multi marginal setting (see Theorem 29).

The issue arising from the latter approach is the possible lack of
measurability. This is why we are reverting to the condition of
$c$-connectivity.

######  Theorem 24.

Let $X,\,Y$ be Polish spaces equipped with Borel probability measures
$\mu,\nu$, and let $c:X\times Y\to[0,\infty]$ a Borel measurable cost
function. Let $\gamma$ be a $c$-cyclically monotone transport plan with finite
total cost and assume that $\gamma$ is supported on a $c$-connecting set
$\Gamma$. Then $\gamma$ is optimal.

###### Proof.

Let us recall the Rockafellar-Rochet-Rüschendorf formula: fix
$(x_{0},y_{0})\in\Gamma$ and define the function
$\varphi_{n}:X\times\Gamma^{n}:(-\infty,+\infty]$ by setting

$\varphi_{n}(x,x_{1},y_{1},\ldots,x_{n},y_{n})=c(x,y_{n})-c(x_{n},y_{n})+\sum_{i=0}^{n-1}\big{(}c(x_{i+1},y_{i})-c(x_{i},y_{i})\big{)}.$
(5)

Define for all $x\in X$

$\varphi(x):=\inf\\{\varphi_{n}(x,x_{1},y_{1},\ldots,x_{n},y_{n})~{}|~{}n\geq
1,~{}(x_{i},y_{i})_{i=1}^{n}\in\Gamma^{n}\\}.$ (6)

The key is to prove that also in this case the formula (6) makes sense. From
that point on one can proceed like in the proof of Theorem 23. Hence it
suffices to show the following:

######  Claim.

$\displaystyle\varphi(x)\in\mathbb{R}\text{ for all }x\in p_{X}(\Gamma)\ \
\text{ and }$ (7)
$\displaystyle\varphi(x)\leq\varphi(x^{\prime})+c(x,y)-c(x^{\prime},y)~{}~{}~{}\text{for
all }x\in X\text{ and }(x^{\prime},y)\in\Gamma.$ (8)

Proof.  We fix $x\in p_{X}(\Gamma)$. So there exists $y\in Y$ such that
$(x,y)\in\Gamma$. Since $\Gamma$ is $c$-connecting and
$(x,y),(x_{0},y_{0})\in\Gamma$, we can find
$(x_{1},y_{1}),\ldots,(x_{n-1},y_{n-1})\in\Gamma$ such that, setting
$(x_{n},y_{n})=(x,y)$, we have

$\varphi_{n}(x;x_{1},y_{1},\ldots,x_{n},y_{n})<+\infty.$

This means that $\varphi(x)<+\infty$, and it remains to show that
$\varphi(x)>-\infty$.

We denote $a_{1}=x$. Since $x\in p_{X}(\Gamma)$, there exists $b_{1}\in Y$
such that $(a_{1},b_{1})\in\Gamma$. The $c$-connectivity of $\Gamma$ gives us
the existence of a chain $(a_{1},b_{1}),\ldots,(a_{m},b_{m})\in\Gamma$ such
that $c(a_{2},b_{1}),$ $c(a_{3},b_{2}),\ldots,c(a_{m},b_{m-1})<+\infty$. For
any ordered collection $(x_{1},y_{1}),\ldots,(x_{n},y_{n})\in\Gamma$ such that

$\varphi_{n}(x,x_{1},y_{1},\ldots,x_{n},y_{n})<+\infty$

we extend the chain $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ by setting for all
$i\in\\{1,\ldots,m\\}$ $x_{n+i}=a_{i}$ and $y_{n+i}=b_{i}$. Due to the
$c$-cyclic monotonicity of $\gamma$ and the finiteness of all the terms
involved, we have (denoting $x_{m+n+1}=x_{0}$) that

$0\leq\sum_{i=0}^{n+m}\left(c(x_{i+1},y_{i})-c(x_{i},y_{i})\right)=c(x_{0},y_{n+m})-c(x_{n+m},y_{n+m})+\sum_{i=0}^{n+m-1}\big{(}c(x_{i+1},y_{i})-c(x_{i},y_{i})\big{)}.$

That is

$\displaystyle\alpha:$
$\displaystyle=c(a_{m},b_{m})-c(x_{0},b_{m})+\sum_{i=1}^{m-1}\big{(}c(a_{i},b_{i})-c(a_{i+1},b_{i})\big{)}$
$\displaystyle\leq
c(x,y_{n})-c(x_{n},y_{n})+\sum_{i=0}^{n-1}\big{(}c(x_{i+1},y_{i})-c(x_{i},y_{i})\big{)}.$

This, in turn, means that
$\alpha\leq\varphi_{n}(x,x_{1},y_{1},\ldots,x_{n},y_{n})$, and passing to the
infimum we get that $-\infty<\alpha\leq\varphi(x)$.

To prove the inequality (8), observe that its right hand side can we written
as

$\displaystyle\inf_{n\geq
1,(x_{i},y_{i})_{i=1}^{n}\in\Gamma^{n}}\left\\{c(x^{\prime},y_{n})-c(x_{n},y_{n})+\sum_{i=0}^{n-1}\big{(}c(x_{i+1},y_{i})-c(x_{i},y_{i})\big{)}\right\\}+c(x,y)-c(x^{\prime},y)$
$\displaystyle=\inf_{n\geq
1,(x_{i},y_{i})_{i=1}^{n}\in\Gamma^{n}}\left\\{c(x,y)-c(x^{\prime},y)+\sum_{i=0}^{n-1}\big{(}c(x_{i+1},y_{i})-c(x_{i},y_{i})\big{)}+\big{(}c(x^{\prime},y_{n})-c(x_{n},y_{n})\big{)}\right\\}$
$\displaystyle=\inf_{m\geq
1,(x_{i},y_{i})_{i=1}^{m}\in\Gamma^{m},(x_{m},y_{m})=(x^{\prime},y)}\left\\{c(x,y_{m})-c(x_{m},y_{m})+\sum_{i=0}^{m-1}[c(x_{i+1},y_{i})-c(x_{i},y_{i})]\right\\}$
$\displaystyle=\inf_{m\geq
1,(x_{i},y_{i})_{i=1}^{m}\in\Gamma^{m},(x_{m},y_{m})=(x^{\prime},y)}\varphi_{n}(x,x_{1},y_{1},\ldots,x_{m},y_{m}).$

Finally, we conclude that on both sides of (8) we take the infimum of the same
function but on the right-hand side the set over which we minimize is smaller,
which concludes the proof. ∎

######  Remark 25.

Example 18 shows that the assumption of connectivity in the above theorem is
not necessary for optimality.

The previous theorem can be used as a building block to study under which
conditions all $c$-cyclically monotone transport plans are optimal. This boils
down to the study of the structure of the set where the cost is infinite, as
it has been done in [9], and we recall the theorem.

######  Theorem 18 ([9, Theorem 1.b]).

Assume that the set where $c\equiv+\infty$ is the union of a closed set $F$
and a $\mu\otimes\nu$-null set $N$. Let $\gamma\in\Pi(\mu,\nu)$ be a finite
and $c$-cyclically monotone plan. Then $\gamma$ is optimal.

The proof is based on finding a set $\Gamma\subset X\times Y$ of full
$\gamma$-measure and a partition $\\{\Gamma\cap(C_{i}\times D_{i})\\}_{i\in
I}$ of $\Gamma$ which is countable and such that each element of the partition
is $c$-connecting. This can be done due to the fact that the set $X\times
Y\setminus F$ is open. The key property of the partition is that not only the
starting plan $\gamma$ but also _any other finite transport plan
$\tilde{\gamma}$_ satisfies $\tilde{\gamma}\left(\bigcup_{i\in I}C_{i}\times
D_{i}\right)=1$.

###  3.3 Existence of plans supported on a $c$-subgradient

In [6] the authors took a slightly different path to finding a Brenier-type
map. Omitting the equivalence between optimality and a plan being supported on
a $c$-subgradient of a function, they showed that such an optimal plan exists.
More precisely, we have the following theorem.

######  Theorem 26 ([6, Theorem 1.1]).

Let $X=Y$ be a Polish space, let $c:X\times Y\to\mathbb{R}\cup\\{+\infty\\}$
be a continuous and symmetric cost function, essentially bounded from below
with respect to probability measures $\mu\in{\mathcal{P}}(X)$ and
$\nu\in{\mathcal{P}}(Y)$. Assume $\mu$ and $\nu$ are strongly $c$-compatible,
namely satisfy that for any measurable $A\subset X$ we have

$\displaystyle\mu(A)+\nu(\\{y\in Y:\forall x\in A,\,\,c(x,y)=\infty\\})\leq
1,$ (9)

and for any measurable $A\subset X$ with $\mu(A)\neq 0,1$ we have

$\displaystyle\mu(A)+\nu(\\{y\in Y:\forall x\in A,\,\,c(x,y)=\infty\\})<1.$
(10)

If there exists _some_ finite plan transporting $\mu$ to $\nu$, then there
exists a $c$-class function $\varphi$ and an optimal transport plan
$\pi\in\Pi(\mu,\nu)$ concentrated on $\partial^{c}\varphi$.

######  Remark 27.

Note that the condition (9) is a necessary condition for the existence of a
plan such that each atom is transported at finite cost. In the special
discrete setting this condition corresponds to the Hall’s marriage theorem
that guarantees the existence of a matching. The second condition (10) turns
out to be a sufficient condition. It guarantees that the optimal plan, which
is known to be $c$-cyclically monotone is _connecting_ and therefore $c$-path-
bounded.

######  Remark 28.

The assumption of lower semi-continuity of the cost is standard and as
mentioned previously it guarantees the existence of an optimal plan. The
authors assume upper semi-continuity to guarantee measurability of the set
$\\{y\in Y:\forall x\in A,\,\,c(x,y)=\infty\\}$, which in this case is simply
closed and hence measurable. However, this assumption is not needed. Indeed,
assuming only the lower semi-continuity of the cost we see that the set

$\\{y\in Y:\forall x\in A,\,\,c(x,y)=\infty\\}=\cap_{n\in\mathbb{N}}\\{y\in
Y:\forall x\in A,\,\,c(x,y)>n\\}$

is a countable intersection of open sets and as such is measurable. Moreover,
the measurability of the potential follows from the fact that the support of
the plan is $c$-connecting.

Moreover, in the case when the target measure $\nu$ has finite support, it was
shown ([6, Theorem 1.3]) that it is sufficient to assume measurability of the
cost (and a mild condition regarding a joint property of the measures and the
cost called $c$-regularity, see [6, Definition 5.1]).

##  4 More general transport problems

###  4.1 The multi-marginal, integral case

Let $N\geq 2$, $X_{1},\ldots,X_{N}$ be Polish spaces, denote
$X=\prod_{i=1}^{N}X_{i}$ and consider a cost function
$c:X\to\mathbb{R}\cup\\{+\infty\\}$. The natural generalization of the
classical optimal transport to the multidimensional case is to consider

$\min_{\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})}C(\gamma):=\min_{\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})}\int_{X}cd\gamma,$

in the set

$\Pi(\mu_{1},\ldots,\mu_{N}):=\\{\gamma\in\mathcal{P}(X)~{}|~{}p_{X_{i}}(\gamma)=\mu_{i}\text{
for all }i=1,\ldots,N\\},$

that is, in the set of _couplings_ or _transport plans_ between the $N$
marginals $\mu_{1},\ldots,\mu_{N}$.

Like in the two-marginals case, to establish the existence of minimizers it is
sufficient to assume, for example, that the cost function is lower semi-
continuous and essentially bounded from below.

The notion of multidimensional $c$-cyclic monotonicity was introduced in
Definition 13. It brings the concept of $c$-cyclic monotonicity in classical
optimal transport to the multimarginal case. The multimarginal definition is
more complex but carries the same idea: if we permute the ‘destinations’ of
points in the support of an optimal plan, the cost should not improve. In
finite spaces for real-valued cost functions, $c$-cyclic monotonicity and
optimality are equivalent also in the multimarginal case, see Theorem 37 in
Appendix B.

The rest of this subsection is dedicated to an overview of what we know about
the sufficiency of $c$-cyclic monotonicity for optimality in general Polish
spaces for arbitrary Borel probability measures as marginals.

Recall that the concept of a $c$-splitting set (Definition 14) is the
multimarginal counterpart of the $c$-subgradient and a useful tool for proving
the optimality of a plan. In [23] Kim and Pass proved that the multimarginal
$c$-cyclic monotonicity is a necessary condition for the $c$-splitting
property of a set. In [21], Griessler showed that in Polish spaces, under some
boundedness conditions on a real-valued cost function, $c$-cyclical
monotonicity of the support of a plan implies its optimality. More precisely,
we have the following theorem.

######  Theorem 29 ([21, Theorem 1.2]).

Let $X_{1},\ldots,X_{N}$ be Polish spaces and $\mu_{1},\ldots,\mu_{N}$ be
Borel probability measures on the spaces $X_{1},\ldots,X_{N}$. Let
$c:X_{1}\times\ldots\times X_{N}\to[0,\infty)$ be a continuous cost function
such that for some $f_{i}\in L^{1}(X_{i},\mu_{i})$, $i=1,\ldots,N$, one has
$c(x_{1},\ldots,x_{N})\leq\sum_{i=1}^{N}f_{i}(x_{i})$.222This condition does
not need to hold everywhere. It is enough that there exist $N$ sets
$N_{i}\subset X_{i}$ such that $\mu_{i}(N_{i})=0$ and such that the condition
holds outside $\cup_{i}p_{X_{i}}^{-1}(N_{i})$.  Let
$\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})$ be a transport plan such that ${\rm
supp}(\gamma)$ is $c$-cyclically monotone. Then $\gamma$ is optimal.

Griessler starts by proving that a $c$-cyclically monotone transport plan is
finitely optimal, i.e. that all its finitely-supported submeasures are optimal
with respect to their marginals. He continues by commenting that by a linear
programming argument one can show that finite and $c$-cyclically monotone sets
are $c$-splitting. The transition from finite $c$-splitting sets to arbitrary
$c$-splitting sets is done by first fixing a $c$-cyclically monotone set
$\Gamma$ and an element $x^{0}\in\Gamma$, and then proving that the family

$\mathcal{F}:=\bigcup_{G\subset\Gamma\text{ finite }}\mathcal{G}_{G}\,,$

where

$\displaystyle\mathcal{G}_{G}=\\{(\varphi_{1},\ldots,\varphi_{N}):\,$
$\displaystyle\varphi\text{ is a }(G\cup\\{x^{0}\\},c)-\text{splitting tuple
such that}$ $\displaystyle\varphi_{i}(x_{i})\leq
c(x_{1}^{0},\ldots,x_{i-1}^{0},x_{i},x_{i+1}^{0},\ldots,x_{N}^{0})\text{ for
all }i=1,\ldots,N\\}\,,$

has the finite-intersection property. Hence by the compactness of the space
$\overline{\mathbb{R}}^{X_{1}}\times\overline{\mathbb{R}}^{X_{2}}\times\cdots\times\overline{\mathbb{R}}^{X_{N}}$
the set

$\bigcap_{G\subset\Gamma\,,~{}G\text{ finite}}\mathcal{G}_{G}$

is nonempty, proving the existence of a $(\Gamma,c)$-splitting tuple.

To prove the existence of a Borel measurable tuple Griessler uses the
continuity of the cost function: if $(\varphi_{1},\ldots,\varphi_{N})$ is a
$(\Gamma,c)$-splitting tuple, then by first setting

$\tilde{\varphi}_{1}(x_{1})=\inf\left\\{c(x_{1},y_{2},\ldots,y_{N})-\sum_{j=2}^{N}\varphi_{j}(y_{j}):\
(y_{2},\ldots,y_{N})\in X_{2}\times\cdots\times X_{N}\right\\}$

and then, assuming that $\tilde{\varphi}_{1},\ldots,\tilde{\varphi}_{i-1}$ are
already defined,

$\tilde{\varphi}_{i}(x_{i})=\inf\\{c(y_{1},\ldots,y_{i-1},x_{i},y_{i+1},\ldots,y_{N})-\sum_{j=1}^{i-1}\tilde{\varphi}_{j}(y_{j})-\sum_{j=i+1}^{N}\varphi(y_{j}):\\\
y_{j}\in X_{j},~{}j\in\\{1,\ldots,i-1,i+1,\ldots,N\\}\\}$

one obtains a $(\Gamma,c)$-splitting tuple that is upper semicontinous and, in
particular, Borel measurable.

To pass from measurable potentials to potentials whose integrals are well-
defined (and thus to optimality) Griessler shows that if
$(\varphi_{1},\ldots,\varphi_{N})$ is a $(\Gamma,c)$-splitting tuple and if
$x^{0}\in\Gamma$, then there exists a $(\Gamma,c)$-splitting tuple
$(\tilde{\varphi}_{1},\ldots,\tilde{\varphi}_{N})$ such that

$\tilde{\varphi}_{i}(x_{i})\leq
c(x_{1}^{0},\ldots,x_{i-1}^{0},x_{i},x_{i+1}^{0},\ldots,x_{N}^{0})~{}~{}\text{for
all }i\in\\{1,\ldots,N\\}\text{ and }x_{i}\in X_{i}\,.$ (11)

This is achieved by first noting that, since $x^{0}\in\Gamma$ and since
$(\varphi_{1},\ldots,\varphi_{N})$ is a $(\Gamma,c)$-splitting tuple, we have

$\sum_{i=1}^{N}\varphi_{i}(x_{i}^{0})=c(x_{1}^{0},\ldots,x_{N}^{0})\,,$

and, in particular, (since $c$ assumes only real values)
$\varphi_{i}(x_{i}^{0})\in\mathbb{R}$ for all $i\in\\{1,\ldots,N\\}$. Then one
defines

$\displaystyle\tilde{\varphi}_{1}(x_{1})$
$\displaystyle=\varphi_{1}(x_{1})+\sum_{j=2}^{N}\varphi_{j}(x_{j}^{0})~{}~{}~{}\text{and}$
$\displaystyle\tilde{\varphi}_{i}(x_{i})$
$\displaystyle=\varphi_{i}(x_{i})-\varphi_{i}(x_{i}^{0})~{}\text{ for
}i=2,\ldots,N.$

Starting from a Borel measurable $(\Gamma,c)$-splitting tuple
$(\varphi_{1},\ldots,\varphi_{N})$ one gets the existence of a Borel
measurable $(\Gamma,c)$-splitting tuple
$(\tilde{\varphi}_{1},\ldots,\tilde{\varphi}_{N})$ satisfying, in addition,
(11). The fact that the integrals of the functions $\tilde{\varphi}_{i}$ are
well-defined follows by the assumption that $c$ is bounded from above by a sum
$\sum_{i=1}^{N}f_{i}$ of $\mu_{i}$-integrable functions: for a fixed
$x^{0}\in\Gamma$ that satisfies $\sum_{i=1}^{N}f_{i}(x_{i}^{0})<+\infty$ we
have

$\displaystyle\int_{X_{i}}\tilde{\varphi}_{i}(x_{i})d\mu_{i}(x_{i})$
$\displaystyle\leq\int_{X_{i}}c(x_{1}^{0},\ldots,x_{i-1}^{0},x_{i},x_{i+1}^{0},\ldots,x_{N}^{0})d\mu_{i}(x_{i})$
$\displaystyle\leq\sum_{j\neq
i}f_{j}(x_{j}^{0})+\int_{X_{i}}f_{i}(x_{i})d\mu_{i}(x_{i})<+\infty.$

If $\Gamma$ is a $c$-cyclically monotone set on which a transport plan
$\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})$ is concentrated, the the optimality of
the plan $\gamma$ now follows easily: if $\gamma^{\prime}$ is another
transport plan, one has (denoting $X=\prod_{i=1}^{N}X_{i}$) that

$\int_{X}cd\gamma=\int_{X}\sum_{i=1}^{N}\tilde{\varphi}_{i}d\gamma=\int_{X}\sum_{i=1}^{N}\varphi_{i}d\gamma^{\prime}\leq\int_{X}cd\gamma^{\prime}\,.$

It is an open problem if the $c$-cyclic monotonicity of the support of a plan
implies its optimality if some of the assumptions of Griessler are lifted. For
example if we consider real-valued, Borel (not necessarily continuous) cost
function bounded from above by a sum of integrable functions. For this type of
a cost one could prove the existence of a $(c,\Gamma)$-splitting tuple as
above, but without the continuity assumption on the cost the existence of a
Borel measurable splitting tuple is not clear. Note that in the $2$-marginal
case the measurability was based on the Rockafellar-type formula (2), but in
the multimarginal case this kind of formula is not available.

If the cost function assumes the value $+\infty$ there are results in the
opposite direction. In [28], M. Petrache presented an example, for the three-
marginal case, of a $c$-cyclically monotone transport plan that is not
optimal. In the example the spaces $X_{i}$ were all equal to $\mathbb{N}$, the
natural numbers, and the cost function assumes infinite value. Clearly, this
discrete example can naturally be embedded in $\mathbb{R}^{3}$ where we view
the discrete marginal measures as elements of $\mathcal{P}(\mathbb{R})$. Note
that in this case the cost is not continuous. While if we regard $\mathbb{N}$
as a Polish space equipped with the discrete metric, the cost is continuous
but not bounded from above by a sum of integrable functions of the marginal
measure spaces.

######  Example 30 ([28, Proposition 2.1]).

We fix $N=3$ and consider the three-marginal optimal transportation problem
with the spaces $X_{1}=X_{2}=X_{3}=\mathbb{N}$ and all marginals equal to the
measure

$\mu=\sum_{k=1}^{\infty}2^{-k}\delta_{k}\in\mathcal{P}(\mathbb{N}).$

To define the cost function we fix an auxiliary function
$f:\mathbb{N}\to(0,1]$ such that

$\sum_{k=1}^{\infty}4^{-k}(f(2k-1)-f(2k))>\frac{1}{6}.$ (12)

This condition is satisfied, for example, by all decreasing functions
$f:\mathbb{N}\to(0,1]$ such that $f(1)>~{}f(2)+\frac{2}{3}$. We define the
cost function $c:(\mathbb{N})^{3}\to[0,\infty]$ as follows:

$\begin{cases}c(a,b,c)\text{ is symmetric with respect to permuting the
coordinates }(a,b,c),\\\ c(1,1,1)=1,\\\ c(a,a,a+1)=f(a)\text{ for all
}a\in\mathbb{N}\text{ and }\\\ c=+\infty\text{ for all triples }(a,b,c)\text{
not described by the previous two conditions.}\end{cases}$

We consider the following transport plans
$\gamma,\bar{\gamma}\in\Pi(\mu,\mu,\mu)$:

$\displaystyle\gamma$
$\displaystyle=\sum_{k=1}^{\infty}4^{-k}(\delta_{(2k-1,2k-1,2k)}+\delta_{(2k-1,2k,2k-1)}+\delta_{(2k,2k-1,2k-1)})~{}~{}~{}\text{and}$
$\displaystyle\bar{\gamma}$
$\displaystyle=\frac{1}{2}\delta_{(1,1,1)}+\frac{1}{2}\sum_{k=1}^{\infty}4^{-k}(\delta_{(2k,2k,2k+1)}+\delta_{(2k,2k+1,2k)}+\delta_{(2k+1,2k,2k)}).$

We will show that the plan $\gamma$ is _$c$ -cyclically monotone but not
optimal_.

The plan $\gamma$ cannot be optimal since the plan $\bar{\gamma}$ has a lower
cost:

$\displaystyle C[\gamma]-C[\bar{\gamma}]$
$\displaystyle=3\sum_{k=1}^{\infty}4^{-k}f(2k-1)-\frac{1}{2}-3\sum_{k=1}^{\infty}4^{-k}f(2k)$
$\displaystyle=3\sum_{k=1}^{\infty}4^{-k}(f(2k-1)-f(2k))-\frac{1}{2}>0,$

where we have used the property (12) of the function $f.$

It remains to show that $\gamma$ is $c$-cyclically monotone. We show that it
is finitely-optimal; by Propositions 41 and 43 of Appendix D these two notions
are equivalent. We fix a finitely-supported subplan $\alpha$ of $\gamma$, and
another transport plan $\alpha^{\prime}$ that has the same marginals as
$\alpha$. It is enough to show that $C[\alpha]\leq C[\alpha^{\prime}]$. If
$C[\alpha^{\prime}]=+\infty$, the claim holds trivially. We may thus assume
that $C[\alpha^{\prime}]<+\infty$. We show that in fact in this case
$\alpha=\alpha^{\prime}$; the idea is that the set where for given marginals
the cost can be finite is very small.

In the following we denote by $(\delta_{(a,b,c)})^{S}$ the symmetrisation

$(\delta_{(a,b,c)})^{S}=\frac{1}{6}(\delta_{(a,b,c)}+\delta_{(a,c,b)}+\delta_{(b,a,c)}+\delta_{(b,c,a)}+\delta_{(c,a,b)}+\delta_{(c,b,a)}).$

Due to the symmetries of the problem and the structure of the plan $\gamma$ we
may assume that for some $M>0$ and coefficients $a_{k}\geq 0$

$\alpha=\sum_{k=0}^{M}a_{k}(\delta_{(2k-1,2k-1,2k)})^{S}.$

The marginals of this plan are all equal to

$\mu_{\alpha}=\sum_{k=1}^{M}a_{k}\left(\frac{2}{3}\delta_{2k-1}+\frac{1}{3}\delta_{2k}\right).$

We may also assume that the measure $\alpha^{\prime}$ is symmetric. Since
$C[\alpha^{\prime}]<+\infty$, there exists nonnegative constants
$a^{\prime},a_{1}^{\prime},\ldots,a_{M}^{\prime}$,
$b_{1}^{\prime},\ldots,b_{M}^{\prime}$ such that

$a^{\prime}+\sum_{k=1}^{M}(a_{k}^{\prime}+b_{k}^{\prime})=1~{}~{}~{}\text{and}~{}~{}~{}\alpha^{\prime}=a^{\prime}\delta_{(1,1,1)}+\sum_{k=1}^{M}(a_{k}^{\prime}(\delta_{(2k-1,2k-1,2k)})^{S}+b_{k}^{\prime}(\delta_{(2k,2k,2k+1)})^{S}).$

Since the marginals of $\alpha^{\prime}$ are all equal to $\mu_{\alpha}$, we
have

$\mu_{\alpha}(\\{1\\})=\frac{2}{3}a_{1}=\alpha^{\prime}(\\{1\\}\times\mathbb{N}\times\mathbb{N})=a^{\prime}+\frac{2}{3}a_{1}^{\prime}$

and thus

$2a_{1}=3a^{\prime}+2a_{1}^{\prime}.$ (13)

Similarly we have, for all $k\geq 2$:

$\mu_{\alpha}(\\{2k-1\\})=\frac{2}{3}a_{k}=\alpha^{\prime}(\\{2k-1\\}\times\mathbb{N}\times\mathbb{N})=\frac{2}{3}a_{k}^{\prime}+\frac{1}{3}b_{k-1}^{\prime}$

which implies that

$2a_{k}=2a_{k}^{\prime}+b_{k-1}^{\prime}~{}~{}~{}\text{for all }k\geq 2.$ (14)

And finally, for $k\geq 1$, we have

$\mu_{\alpha}(\\{2k\\})=\frac{1}{3}a_{k}=\alpha^{\prime}(\\{2k\\}\times\mathbb{N}\times\mathbb{N})=\frac{1}{3}a_{k}^{\prime}+\frac{2}{3}b_{k}^{\prime}$

giving

$a_{k}=a_{k}^{\prime}+2b_{k}^{\prime}~{}~{}~{}\text{for all }k\geq 1.$ (15)

Equations (14) and (15) imply that

$a_{k}^{\prime}+2b_{k}^{\prime}=a_{k}^{\prime}+\frac{b_{k-1}^{\prime}}{2}~{}~{}~{}\text{for
all }k\geq 2,$

and thus

$b_{k+1}^{\prime}=\frac{b_{k}^{\prime}}{4}~{}~{}~{}\text{for all }k\geq 1.$

Since $b_{k}=0$ for all $k>M$ we have, therefore, $b_{k}=0$ for all $k=1$.
Hence, by (15), we have $a_{k}=a_{k}^{\prime}$ for all $k\geq 1$, and this
inserted in (13) gives $a^{\prime}=0$, completing the proof of
$\alpha=\alpha^{\prime}$.

The counterexample above shows that neither of the two-marginal Theorems 21
and 22 of Pratelli can be extended to the multi-marginal case.

###  4.2 The $L^{\infty}$-problem.

Let $X_{1}$ and $X_{2}$ be Polish spaces and $c:X_{1}\times
X_{2}\to[0,\infty]$ be a lower semi-continuous cost function. The
_$L^{\infty}$ optimal mass transportation problem_ can be stated as follows:

$\min_{\Pi(\mu_{1},\mu_{2})}C_{\infty}[\gamma]:=\min_{\Pi(\mu_{1},\mu_{2})}\gamma-\mbox{\it
essup\ }c(x_{1},x_{2})$

This problem is ‘a limit case’ of the classical optimal transport since, if
$c\geq 0$, is the variational limit, as $p\to\infty$, of the optimal transport
problems with the cost functional
$C_{p}[\gamma]:=\left(\int_{X}c^{p}\,d\gamma\right)^{\frac{1}{p}}$. In fact,
if we take a sequence $(\gamma_{p})_{p=1}^{\infty}$, with $\gamma_{p}$
minimizer of the corresponding functional $C_{p}$ (and thus $c$-cyclically
monotone), we get, as the weak∗-cluster points
$\gamma=\lim_{p\to\infty}\gamma_{p}$, some solutions of the problem
($P_{\infty}$) corresponding to the cost function $c$. If $c$ is continuous
and if for each $p$ the value $C_{p}[\gamma]$ is finite, these solutions are
_infinitely cyclically monotone_ , in the sense of the following definition:

######  Definition 31.

We say that a set $\Gamma\subset X_{1}\times X_{2}$ is _infinitely
$c$-cyclically monotone_, if for every $k$-tuple of points
$(x_{1}^{i},x_{2}^{i})_{i=1}^{k}$ of $\Gamma$ and for every permutation
$\sigma$ of the set $\\{1,\ldots,k\\}$ we have

$\max\\{c(x_{1}^{i},x_{2}^{i})~{}|~{}i\in\\{1,\ldots,k\\}\\}\leq\max\\{c(x_{1}^{i},x_{2}^{\sigma(i)})~{}|~{}i\in\\{1,\ldots,k\\}\\}\,.$

We also say that a coupling $\gamma\in\Pi(\mu_{1},\mu_{2})$ is infinitely
cyclically monotone if it is concentrated on an infinitely cyclically monotone
set.

The infinitely cyclically monotone transport plans are a class of ‘well-
behaved’ solutions to the problem ($P_{\infty}$). These plans are well-behaved
in the sense that the restrictions of infinitely cyclically monotone plans are
still infinitely cyclically monotone and thus optimal (if infinitely
cyclically monotone plans are optimal). In general, the problem ($P_{\infty}$)
is much more cumbersome than the standard optimal transportation problem. The
cost functional is neither linear nor convex, there is no classical duality
theory, and there is a high degree of non-uniqueness of the solutions. Loosely
speaking, in the problem ($P_{\infty}$) we are only interested in optimizing
the worst case, so locally its solutions can be far from optimal. In this last
sense, the infinitely cyclically monotone minimizers have better properties,
and, at least for continuous cost $c$ that admits finite $C_{p}$ solutions,
the infinitely cyclically monotone couplings exist as stated above.

The question we consider is: are optimal plans infinitely cyclically monotone,
and are infinitely cyclically monotone plans optimal? The classical two
approaches to the necessity of the condition (see Section 3.1) are based on
the linearity or on the duality for convex problems, but as was mentioned this
formulation of the problem lacks both. In fact, not all plans that are optimal
for ($P_{\infty}$) are infinitely cyclically monotone. The next example
illustrates the typical behavior. By $\mathcal{L}^{1}|_{[0,1]}$ we denote one-
dimensional Lebesgue measure on the interval $[0,1]$.

######  Example 32.

Let $X_{1}=X_{2}=\mathbb{R}$, $c(x,y)=|x-y|$,
$\mu=\tfrac{1}{2}(\mathcal{L}^{1}|_{[0,1]}+\delta_{1})$, and
$\nu=\tfrac{1}{2}(\mathcal{L}^{1}|_{[0,1]}+\delta_{10})$, then any plan that
sends $1$ to $10$ is optimal, even if the interval $[0,1]$ was mapped to
itself in a very “non-optimal” way (for example by a map $x\mapsto 1-x$). The
locally “best-behaved” optimal transport plan would be
$\gamma=\tfrac{1}{2}((id,id)_{\sharp}\mathcal{L}^{1}|_{[0,1]}+\delta_{(1,10)})$,
and this plan is, actually, infinitely cyclically monotone.

Concerning the sufficiency, Champion, De Pascale, and Juutinen in [16] laid
the foundations for the two-marginal $L^{\infty}$ transport on
$\mathbb{R}^{d}$ with the Euclidean distance as a cost function. Later Jylhä
in [22] proved the corresponding result in Polish spaces for continuous cost
functions $c:X_{1}\times X_{2}\to[0,\infty]$. If the continuity assumption is
dropped, the optimality of an infinitely cyclically monotone plan fails even
in the case of a lower semi-continuous cost with finite values. The following
counterexample is a slightly modified version of the one given by Pratelli and
Ambrosio in [4] of a non-optimal $c$-cyclically monotone transportation plan.
In the original counterexample it was necessary that $c$ assumes the value
$+\infty$ (since for a lower semi-continuous cost that assumes only finite
values, in the integral case, $c$-cyclic monotonicity is equivalent to
optimality).

######  Example 33.

Consider the two-marginal $L^{\infty}$-optimal transportation problem with
marginals $\mu=\nu=\mathcal{L}|_{[0,1]}$ and the cost function

$c(x,y)=\begin{cases}1&\text{ if }x=y\\\ 2&\text{ otherwise.}\end{cases}$

Let $\alpha$ be and irrational number. Set $T_{1}=Id_{[0,1]}$ and
$T_{2}:[0,1]\to[0,1]$, $T_{2}(x)=x+\alpha\pmod{1}$. The map $T_{1}$ is an
optimal transportation map for the problem ($P_{\infty}$) with
$C_{\infty}[T_{1}]=1$. Since the map $T_{2}$ has the cost $2$, it cannot be
optimal. However, it is infinitely cyclically monotone, as we show below.
Assume, contrary to the claim, that $T_{2}$ is not infinitely cyclically
monotone. Then there exists a minimal $K\in\mathbb{N}$ and a $K$-tuple of
couples $\\{x_{i},y_{i}\\}_{i=1}^{K}$, all belonging to the support of the
plan given by $T_{2}$, such that

$\max_{1\leq i\leq K}c(x_{i},y_{i})>\max_{1\leq i\leq K}c(x_{i+1},y_{i}),$

with the convention $x_{K+1}=x_{1}$. By the definition of the map $T_{2}$ we
have $y_{i}=x_{i}+\alpha\pmod{1}$ for all $i$. By the definition of the cost
$c$, the only form in which this inequality can hold is: $2>1$. The right-hand
side now tells us that $y_{i}=x_{i}+\alpha\pmod{1}$ for all $i$, that is,
$x_{i+1}=x_{i}+\alpha\pmod{1}$ for all $i$. Summing up, this gives (keeping in
mind that $x_{K+1}=x_{1}$) that $x_{1}=x_{1}+K\alpha\pmod{1}$, contradicting
the irrationality of $\alpha$.

####  4.2.1 The multi-marginal case

The $L^{\infty}$ problem can be stated analogously also in the multi-marginal
case: For $N\geq 2$, let $(X_{1},\mu_{1}),\ldots,(X_{N},\mu_{N})$ be Polish
probability spaces equipped with Borel probability measures
$\mu_{i}\in~{}\mathcal{P}(X_{i})$. Denoting $X=\prod_{i=1}^{N}X_{i}$, we
consider the cost function $c:X\to[0,\infty]$ and the following minimization
problem

$\min_{\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})}C_{\infty}[\gamma]:=\min_{\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})}\gamma-\mbox{\it
essup\ }_{(x_{1},\ldots,x_{N})\in X}\,c,$

where

$\Pi(\mu_{1},\ldots,\mu_{N}):=\\{\gamma\in\mathcal{P}(X):\,p_{X_{i}}(\gamma)=\mu_{i}\text{
for all }i=1,\ldots,N\\}.$

In this context the $c$-cyclic monotonicity takes the following form (compare
with Definition 14):

######  Definition 34.

We say that a set $\Gamma\subset\prod_{i=1}^{N}X_{i}$ is _infinitely
$c$-cyclic monotone_ if for every $k$-tuple of points
$(x^{1,i},\ldots,x^{N,i})_{i=1}^{k}$ of $\Gamma$ and every $(N-1)$-tuple of
permutations $(\sigma_{2},\ldots,\sigma_{N})$ of the set $\\{1,\ldots,k\\}$ we
have

$\max\\{c(x_{1}^{i},x_{2}^{i},\ldots,x_{N}^{i}):\,i\in\\{1,\ldots,k\\}\\}\leq\max\\{c(x_{1}^{i},x_{2}^{\sigma_{2}(i)},\ldots,x_{N}^{\sigma_{N}(i)}):\,i\in\\{1,\ldots,k\\}\\}\,.$

We also say that a coupling $\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})$ is
infinitely cyclically monotone if it is concentrated on an infinitely
cyclically monotone set.

For $N=2$ this definition coincides with the infinitely cyclically monotone
condition presented above for the two-marginal case, and exactly like in the
two-marginal $L^{\infty}$-optimal transportation problem, also here an optimal
plan is not necessarily infinitely cyclically monotone. De Pascale and Kausamo
proved in [18] the sufficiency of the infinite cyclic monotonicity for
continuous costs and marginal measures with compact supports:

######  Theorem 35 ([18, Theorem 1.3]).

Let $\mu_{i}\in\mathcal{P}(X_{i})$ with compact support for $i=1,\dots,N$, let
$c:X\to\mathbb{R}\cup\\{+\infty\\}$ be continuous. If
$\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})$ is an infinitely cyclically monotone
plan for $c$, then $\gamma$ is optimal.

Again, since in this case there is no duality available, one cannot rely on
$c$-splitting $N$-tuples. Therefore, the optimality proofs have to be based on
different techniques. For example, De Pascale and Kausamo first prove that all
finitely-supported submeasures of an infinitely cyclically monotone transport
plan are optimal with respect to their marginals. Using a suitable finite
discretisations of the original infinitely cyclically monotone transport
problem, they then apply $\Gamma$-convergence techniques to pass from
optimality of the discretised transport plan to the optimality of the full
transport plan. The key property of the infinitely cyclically monotone
condition of a support of a transport plan is that it is inherited by subsets.

##  Appendix A Additional example

The following example is a version of [4, Example 3.1], also presented in this
note in Example 18, but the main focus is shifted to show that $c$-path-
bounded sets need not be $c$-connecting.

######  Example 36.

Let $X=Y=[0,1]$ with the identification of the end points $0$ and $1$, and let
$\mu=\nu$ be the Lebesgue measure on $[0,1]$. Fix an irrational number
$\alpha\in[0,1)$ and define the cost function $c:X\times Y\to[0,\infty]$ as

$c(x,y)=\begin{cases}1&\text{ if }x=y\\\ 2&\text{ if }x=y+\alpha\pmod{1}\\\
+\infty&\text{ otherwise. }\end{cases}$

Consider the set

$\Gamma=\\{(x,x):x\in X\\}.$

Then the set $\Gamma$ is $c$-path-bounded but not $c$-connecting.

To see that $\Gamma$ is $c$-path-bounded, fix points $(x,y),(z,w)\in\Gamma$.
For any $m\in\mathbb{N}$ and any chain $\\{(x_{i},y_{i})\\}_{i=2}^{m-1}$ of
points in $\Gamma$, letting $(x_{1},y_{1})=(x,y)$ and $(x_{m},y_{m})=(z,w)$,
we have

$\sum_{i=1}^{m-1}\big{(}c(x_{i},y_{i})-c(x_{i+1},y_{i})\big{)}=\sum_{i=1}^{m-1}\big{(}1-c(x_{i+1},y_{i})\big{)}\leq
0,$

since for all $i\in\\{1,\ldots,m-1\\}$ we have
$c(x_{i+1},y_{i})\in\\{1,2,+\infty\\}$. Hence, for any start and finish
points, we may choose the constant $M((x,y),(z,w))$ in Definition 9 to be $0$.

The set $\Gamma$ is not connecting: if it were connecting then, for example,
for points $(0,0),(\frac{1}{2},\frac{1}{2})\in\Gamma$ there must exist a chain
$(x_{1},y_{1}),\dots,(x_{n},y_{n})\in\Gamma$ with $(x_{1},y_{1})=(0,0)$ and
$(x_{n},y_{n})=(\frac{1}{2},\frac{1}{2})$ such that
$c(x_{1},y_{0}),\dots,c(x_{n},y_{n-1})<+\infty$. This would imply the
existence of $0\leq m\leq n$ such that $\frac{1}{2}\equiv 0+m\alpha\pmod{1}$,
which is impossible given the irrationality of $\alpha$.

##  Appendix B Finite spaces

In this appendix we establish the equivalence of $c$-cyclic monotonicity and
optimality in finite spaces for real-valued cost functions. Equivalently one
could consider finitely-supported measures on arbitrary spaces. In the
following, $X_{1},\ldots,X_{N}$ are finite spaces and $\mu_{1},\ldots,\mu_{N}$
probability measures on $X_{1},\ldots,X_{N}$, respectively. We denote
$X=\prod_{i=1}^{N}X_{i}$.

######  Theorem 37.

Let $\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})$ be an optimal transport plan with
respect to a cost function $c:X\to\mathbb{R}$ where $X=\prod_{i=1}^{N}X_{i}$
and $X_{i}$ are finite spaces. Then $\gamma$ is $c$-cyclically monotone if and
only if it is optimal.

###### Proof.

Assume that $\gamma$ is optimal. Since we work in finite spaces we denote
$X_{i}=\\{x_{i}^{j}\\}_{j\in\\{1,\ldots,n_{i}\\}}$ for $i\in\\{1,\ldots,N\\}$,
where $n_{i}$ is the cardinality of $X_{i}$. We also denote
$n=n_{1}\cdot\ldots\cdot n_{N}$ and

$I=\\{1,\ldots,n_{1}\\}\times\\{1,\ldots,n_{2}\\}\times\cdots\times\\{1,\ldots,n_{N}\\}.$

The index vectors $(i_{1},\ldots,i_{N})\in I$ will be abbreviated by
$\mathbf{i}$ and vectors $(x_{1}^{i_{1}},\ldots,x_{N}^{i_{N}})\in X$ by
$\mathbf{x}^{\mathbf{i}}$. Using this notation, the plan $\gamma$ can be
expressed as

$\gamma=\sum_{\mathbf{i}\in
I}a^{\mathbf{i}}\delta_{\mathbf{x}^{\mathbf{i}}}~{}~{}~{}\text{for some
coefficients }a^{\mathbf{i}}\geq 0.$

Let us assume, contrary to the claim, that $\gamma$ is not $c$-cyclically
monotone. This means that there exist $k\in\mathbb{N}$, index set
$\tilde{I}:=\\{(i_{1}^{j},i_{2}^{j},\ldots,i_{N}^{j})\\}_{j=1}^{k}\subset I$,
points
$\\{(x_{1}^{i_{1}^{j}},\ldots,x_{N}^{i_{N}^{j}})\\}_{j=1}^{k}\subset\text{supp}\gamma$,
and permutations $\sigma_{2},\ldots,\sigma_{N}$ of the set $\\{1,\ldots,k\\}$
such that

$\sum_{1\leq j\leq k}c(\mathbf{x}^{\sigma(j)})<\sum_{1\leq j\leq
k}c(\mathbf{x}^{\mathbf{i}^{j}}),$ (15)

where we have abbreviated

$\mathbf{x}^{\mathbf{i}^{j}}:=(x_{1}^{i_{1}^{j}},\ldots,x_{N}^{i_{N}^{j}})~{}~{}~{}\text{and}~{}~{}~{}\mathbf{x}^{\sigma(j)}:=(x_{1}^{i_{1}^{j}},x_{2}^{i_{2}^{\sigma_{2}(j)}},\ldots,x_{N}^{i_{N}^{\sigma_{N}(j)}}).$

We denote

$a:=\min\\{a^{\mathbf{i}}~{}|~{}\mathbf{i}\in\tilde{I}\\}>0$

and define

$\tilde{\gamma}:=\sum_{\mathbf{i}\in
I\setminus\tilde{I}}a^{\mathbf{i}}\delta_{\mathbf{x}^{\mathbf{i}}}+\sum_{\mathbf{i}\in\tilde{I}}(a^{\mathbf{i}}-a)\delta_{\mathbf{x}^{\mathbf{i}}}+a\sum_{1\leq
j\leq k}\delta_{\mathbf{x}^{\sigma(j)}}.$

The measure $\tilde{\gamma}$ has the same marginals as $\gamma$ because
$\sigma_{2},\ldots,\sigma_{N}$ are permutations. Using (15) we get

$\displaystyle C[\tilde{\gamma}]$ $\displaystyle=\sum_{\mathbf{i}\in
I\setminus\tilde{I}}a^{\mathbf{i}}c(\mathbf{x}^{\mathbf{i}})+\sum_{\mathbf{i}\in\tilde{I}}(a^{\mathbf{i}}-a)c(\mathbf{x}^{\mathbf{i}})+a\sum_{1\leq
j\leq k}c(\mathbf{x}^{\sigma(j)})$ $\displaystyle<\sum_{\mathbf{i}\in
I\setminus\tilde{I}}a^{\mathbf{i}}c(\mathbf{x}^{\mathbf{i}})+\sum_{\mathbf{i}\in\tilde{I}}(a^{\mathbf{i}}-a)c(\mathbf{x}^{\mathbf{i}})+a\sum_{1\leq
j\leq k}c(\mathbf{x}^{\mathbf{i}^{j}})=C[\gamma],$

contradicting the optimality of $\gamma$.

The proof of the opposite direction ($c$-cyclical monotonicity implies
optimality) is essentially the same as the proof of Proposition 41 and we do
not repeat it here. ∎

##  Appendix C Universally measurable sets and functions

Let $X$ be a Polish space. Consider the measure space $(X,\Sigma,\mu)$ with
$\mu$ a $\sigma$-finite Borel measure (so $\mathcal{B}(X)\subset\Sigma$). Let
$\mathcal{N}_{\mu}=\left\\{N\subset X\ :\ \mu(N)=0\right\\}$, then
$\tilde{\Sigma}_{\mu}:=\left\\{A\cup N\ :A\in\Sigma,\
N\in\mathcal{N}_{\mu}\right\\}$ is still a $\sigma$-algebra. The measure

$\displaystyle\tilde{\mu}:\tilde{\Sigma}_{\mu}\to[0,+\infty]$ (16) $A\cup
N\mapsto\mu(A)$

is called the _completion_ of $\mu$.

A set $B\subset X$ is called _universally measurable_ if it is measurable for
the completion of every finite Borel measure $\mu$ on $X$.

######  Proposition 38.

The set of universally measurable sets is a Borel $\sigma$-algebra.

###### Proof.

This follows from the fact that the defining properties of a $\sigma$-algebra
are stable for the intersection. ∎

If $Y$ is another Polish space and $T:X\to Y$ is a Borel map, then the image
of a Borel set through $T$ is called an _analytic_ set. The following theorem
is relevant here but we do not include the proof as it is beyond the scope of
this paper.

######  Theorem 39.

Every analytic set is universally measurable.

##  Appendix D Finite optimality

In this section we prove that the $c$-cyclic monotonicity of a transport plan
is equivalent to it being finitely optimal. We present the proofs directly in
the multi-marginal case and for both the integral and the $L^{\infty}$ optimal
transport.

We start with the definition of the finite optimality.

######  Definition 40.

Let $\gamma$ be a positive and finite Borel measure on $X$. We say that
$\gamma$ is _finitely optimal_ if all its finitely-supported submeasures are
optimal with respect to their marginals. By submeasure we mean any probability
measure $\alpha$ satisfying $\,{\rm supp}(\alpha)\subset{\rm supp}(\gamma)$.

######  Proposition 41.

If $\gamma\in\Pi(\mu_{1},\ldots,\mu_{N})$ is $c$-cyclically monotone or
infinitely cyclically monotone, then it is finitely optimal for the
corresponding optimal transportation problem (integral or $L^{\infty}$,
respectively).

######  Lemma 42.

Let $\alpha=\sum_{i=1}^{l}m_{i}\delta_{(x^{1,i},\ldots,x^{N,i})}$ and
$\overline{\alpha}=\sum_{i=1}^{\overline{l}}\overline{m}_{i}\delta_{(\overline{x}^{1,i},\ldots,\overline{x}^{N,i})}$
be two discrete measures with positive, integer coefficients and the same
marginals. Let us denote by $\tilde{l}=m^{1}+\dots+m^{l}$ the number of rows
of the following table

$\left.\begin{array}[]{lll}x^{1,1}&\dots&x^{N,1}\\\ \vdots&&\vdots\\\
x^{1,1}&\dots&x^{N,1}\end{array}\right\\}\begin{array}[]{l}\\\ m^{1}\mbox{-
times}\\\ \\\ \end{array}$
$\begin{array}[]{llllllllll}\dots&\dots&\dots&&&&&&&\end{array}$
$\left.\begin{array}[]{lll}x^{1,l}&\dots&x^{N,l}\\\ \vdots&&\vdots\\\
x^{1,l}&\dots&x^{N,l}\end{array}\right\\}\begin{array}[]{l}\\\ m^{l}\mbox{-
times}\\\ \\\ \end{array}$

where the first $m^{1}$ rows are equal among themselves, the following $m^{2}$
rows are equal among themselves and so on. Let $\overline{A}$ be the analogous
table associated to $\overline{\alpha}$. Then $\overline{A}$ has $\tilde{l}$
rows and there exist $(N-1)$ permutations of the set
$\\{1,\ldots,\tilde{l}\\}$ such that $\overline{A}$ is equal to

$\begin{array}[]{lll}x^{1,1}&\dots&x^{N,\sigma^{N}(1)}\\\ \vdots&&\vdots\\\
x^{1,1}&\dots&x^{N,\sigma^{N}(m_{1})}\\\
x^{1,2}&\dots&x^{N,\sigma^{N}(m_{1}+1)}\\\ \vdots&&\vdots\\\
x^{1,l}&\dots&x^{N,\sigma^{N}(m_{1}+\dots+m_{l-1}+1)}\\\ \vdots&&\vdots\\\
x^{1,l}&\dots&x^{N,\sigma^{N}(\tilde{l})}.\end{array}$

###### Proof.

For each $k\in\\{1,\ldots,N\\}$, the $k$-th marginal of $\alpha$ is given by
the sum of the Dirac masses centered on the points of the $k$-th column of the
table $A$ with multiplicity. Analogously, the $k$-th marginal of
$\overline{\alpha}$ is given by the sum of the Dirac masses centered at the
points of the $i$-th column of the table $\overline{A}$ with multiplicity.
Since the marginals of $\alpha$ and $\overline{\alpha}$ are the same, each
point $x^{k,i}$ appearing in the $k$-th marginal must appear in both matrices
the same number of times, proving the existence of the bijections
$\sigma^{2},\ldots,\sigma^{N}$ as required. This also implies that
$\overline{A}$ has $\tilde{l}$ rows. ∎

###### Proof of Proposition 41.

We fix a finitely-supported submeasure
$\alpha=\sum_{i=1}^{l}a_{i}\delta_{X^{i}}$ of $\gamma$. We need to show that
$\alpha$ is an optimal coupling of its marginals. To do this, we fix another
coupling,
$\overline{\alpha}=\sum_{i=1}^{\overline{l}}\overline{a}_{i}\delta_{\overline{X}^{i}}$,
with the same marginals as $\alpha$. We have to show that

$\tilde{C}[\alpha]\leq\tilde{C}[\overline{\alpha}],$ (17)

where $\tilde{C}$ is any of the two total costs under consideration.

Let us first assume that the discrete measures $\alpha$ and
$\overline{\alpha}$ have rational coefficients. We consider the measures
$M\alpha$ and $M\overline{\alpha}$, where $M$ is the product of the
denominators of the coefficients of $\alpha$ and $\overline{\alpha}$. They are
discrete measures having positive, integer coefficients and the same
marginals, so we can apply Lemma 42 to find permutations
$\sigma^{2},\ldots,\sigma^{N}$ such that $M\alpha$ and $M\overline{\alpha}$
have representations $A$ and $\overline{A}$, respectively. If $\tilde{C}=C$ we
have, using the $c$-cyclical monotonicity of $\alpha$

$MC[\alpha]=\sum_{i=1}^{\tilde{l}}c(x^{1,i},\ldots,x^{N,i})\leq\sum_{i=1}^{\tilde{l}}c(x^{1,i},x^{2,\sigma^{2}(i)},\ldots,x^{N,\sigma^{N}(i))})=MC[\overline{\alpha}],$

proving the optimality of $\alpha$. If $\tilde{C}=C_{\infty}$, the conclusion
is also immediate:

$C_{\infty}[\alpha]=\max_{1\leq
i\leq\tilde{k}}c(x^{1,i},\ldots,x^{N,i})\leq\max_{1\leq
i\leq\tilde{k}}c(x^{1,i},x^{2,\sigma^{2}(i)},\ldots,x^{N,\sigma^{N}(i)})=C_{\infty}[\overline{\alpha}].$

Now, assume that $\alpha$ and $\overline{\alpha}$ have real (not necessarily
rational) coefficients, and that

$\alpha:=\sum_{i=1}^{l}a_{i}\delta_{X^{i}},\ \ \
\overline{\alpha}:=\sum_{i=1}^{\overline{l}}\overline{a}_{i}\delta_{\overline{X}^{i}}.$

We show that for all $\varepsilon>0$ there exist two discrete measures

$\beta:=\sum_{i=1}^{l}q_{i}\delta_{X^{i}}\ \mbox{and}\ \
\overline{\beta}:=\sum_{i=1}^{\overline{l}}\overline{q}_{i}\delta_{\overline{X}^{i}},$

with the same marginals, $q_{i},\overline{q}_{i}\in\mathbb{Q}$ and

$|a_{i}-q_{i}|<\varepsilon,\ \ \
|\overline{a}_{i}-\overline{q}_{i}|<\varepsilon.$

Being concentrated on $X^{1},\dots,X^{l}$ and
$\overline{X}^{1},\dots\overline{X}^{\overline{l}}$ is equivalent to the fact
that the vector
${\bf\underline{a}}:=(a_{1},\dots,a_{l},\overline{a}_{1},\dots,\overline{a}_{\overline{l}})$
is a solution of

$\mathcal{A}{\bf\underline{a}}=0,$

where $\mathcal{A}$ is a matrix with coefficients $1,0,-1$. Indeed, if we
write, for example, the equality between the first two marginals we obtain

$\sum_{i=1}^{l}a_{i}\delta_{x^{1,i}}=\sum_{i=1}^{\overline{l}}\overline{a}_{i}\delta_{\overline{x}^{1,i}}.$

Therefore, some of the points $\overline{x}^{1,i}$ must coincide with, for
example, $x^{1,1}$ which implies that for two sets of indices we have

$\sum_{i\in I}a_{i}=\sum_{j\in J}\overline{a}_{j}.$

Since the matrix $\mathcal{A}$ has integer coefficients

$\overline{Ker_{\mathbb{Q}}\mathcal{A}}=Ker_{\mathbb{R}}\mathcal{A},$

and this allows to choose $\beta$ and $\overline{\beta}$. Since
$C[\alpha]\approx C[\beta]$, $C[\overline{\alpha}]\approx
C[\overline{\beta}]$, $C_{\infty}[\alpha]=C_{\infty}[\beta]$ and
$C_{\infty}[\overline{\alpha}]=C[\overline{\beta}]$, this finishes the proof.
∎

The following proposition gives the opposite implication:

######  Proposition 43.

Let $\gamma\in\Pi_{N}(\mu_{1},\ldots,\mu_{N})$ be a finitely optimal transport
plan. Then $\gamma$ is $c$-cyclically monotone or infinitely cyclically
monotone, depending on the underlying transport problem.

###### Proof.

First, we present the proof in the case of the integral optimal transport
problem.

Assume on the contrary that there exist points
$\\{(x_{1}^{i},\ldots,x_{N}^{i})\\}_{i=1}^{k}\subset{\rm supp}(\gamma)$ and
$N-1$ permutations $\sigma_{2},\ldots,\sigma_{N}$ of the set
$\\{1,\ldots,k\\}$ such that

$\sum_{i=1}^{k}c(x_{1}^{i},x_{2}^{\sigma_{2}(i)},\ldots,x_{N}^{\sigma_{N}(i)})<\sum_{i=1}^{k}c(x_{1}^{i},x_{2}^{i},\ldots,x_{N}^{i}).$
(18)

Consider the finite submeasure $\alpha$ of $\gamma$, defined by

$\alpha=\frac{1}{k}\sum_{i=1}^{k}\delta_{(x_{1}^{i},x_{2}^{i},\ldots,x_{N}^{i})},$

and the measure

$\alpha^{\prime}=\frac{1}{k}\sum_{i=1}^{k}\delta_{(x_{1}^{i},x_{2}^{\sigma_{2}(i)},\ldots,x_{N}^{\sigma_{N}(i)})}.$

Since $\sigma_{2},\ldots,\sigma_{N}$ are bijections, the measures $\alpha$ and
$\alpha^{\prime}$ have the same marginals. However, by inequality (18) we have
$C[\alpha^{\prime}]<C[\alpha]$, contradicting the finite optimality of
$\gamma$.

The case of the $L^{\infty}$ optimal transport is analogous. The only
difference is that inequality (18) takes the form

$\max_{1\leq i\leq
k}c(x_{1}^{i},x_{2}^{\sigma_{2}(i)},\ldots,x_{N}^{\sigma_{N}(i)})<\max_{1\leq
i\leq k}c(x_{1}^{i},x_{2}^{i},\ldots,x_{N}^{i}).$

∎

## Acknowledgement

The research of the first author is part of the project _Metodologie
innovative per l’analisi di dati a struttura complessa_ financed by the
_Fondazione Cassa di Risparmio di Firenze_.

The second author acknowledges the support of GNAMPA-INDAM and of the PRIN
(Progetto di ricerca di rilevante interesse nazionale) 2022J4FYNJ,
_Variational methods for stationary and evolution problems with singularities
and interfaces_.

A visit in Firenze of the third author was partially financed with “Fondi di
ricerca di ateneo, ex 60 $\%$” of the University of Firenze.

## References

  * [1] T. Abdellaoui and H. Henich.  Sur la distance de deux lois dans le cas vectoriel.  Comptes rendus de l’Académie des sciences. Série 1, Mathématique, 319(4):397–400, 1994.
  * [2] L. Ambrosio and N. Gigli.  A user’s guide to optimal transport.  In Modelling and optimisation of flows on networks, pages 1–155. Springer, 2013.
  * [3] L. Ambrosio, N. Gigli, and G. Savaré.  Gradient flows: in metric spaces and in the space of probability measures.  Springer Science & Business Media, 2005.
  * [4] L. Ambrosio and A. Pratelli.  Existence and stability results in the ${L}^{1}$ theory of optimal transportation.  In Optimal transportation and applications, pages 123–160. Springer, 2003.
  * [5] S. Artstein-Avidan, S. Sadovsky, and K. Wyczesany.  A Rockafellar-type theorem for non-traditional costs.  Advances in Mathematics, 395:108157, 2022.
  * [6] S. Artstein-Avidan, S. Sadovsky, and K. Wyczesany.  Optimal measure transportation with respect to non-traditional costs.  Calculus of Variations and Partial Differential Equations, 62(1):35, 2023.
  * [7] S. Bartz, H. Bauschke, H. Phan, and X. Wang.  Multi-marginal maximal monotonicity and convex analysis.  Mathematical Programming, 185(1):385–408, 2021.
  * [8] S. Bartz, H. Bauschke, and X. Wang.  A class of multi-marginal c-cyclically monotone sets with explicit c-splitting potentials.  Journal of Mathematical Analysis and Applications, 461(1):333–348, 2018.
  * [9] M. Beiglböck, M. Goldstern, G. Maresch, and W. Schachermayer.  Optimal and better transport plans.  Journal of Functional Analysis, 256(6):1907–1927, 2009.
  * [10] J. Bertrand.  Prescription of Gauss curvature using optimal mass transport.  Geometriae Dedicata, 183(1):81–99, 2016.
  * [11] J. Bertrand, A. Pratelli, and M. Puel.  Kantorovich potentials and continuity of total cost for relativistic cost functions.  Journal de Mathématiques Pures et Appliquées, 110:93–122, 2018.
  * [12] J. Bertrand and M. Puel.  The optimal mass transport problem for relativistic costs.  Calculus of Variations and Partial Differential Equations, 46(1-2):353–374, 2013.
  * [13] Y. Brenier.  Polar factorization and monotone rearrangement of vector-valued functions.  Communications on pure and applied mathematics, 44(4):375–417, 1991\.
  * [14] Y. Brenier.  Extended Monge-Kantorovich theory.  In Optimal transportation and applications, pages 91–121. Springer, 2003.
  * [15] L. Caffarelli.  The regularity of mappings with a convex potential.  Journal of the American Mathematical Society, 5(1):99–104, 1992\.
  * [16] T. Champion, L. De Pascale, and P. Juutinen.  The $\infty$-wasserstein distance: Local solutions and existence of optimal transport maps.  SIAM Journal on Mathematical Analysis, 40(1):1–20, 2008.
  * [17] M. Cuturi and G. Peyré.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [18] L. De Pascale and A. Kausamo.  Sufficiency of $c$-cyclical monotonicity in a class of multimarginal optimal transport problems.  arXiv preprint arXiv:2212.08375, 2022.
  * [19] W. Gangbo and R. J. McCann.  The geometry of optimal transportation.  Acta Mathematica, 177(2):113–161, 1996.
  * [20] W. Gangbo and V. Oliker.  Existence of optimal maps in the reflector-type problems.  ESAIM: Control, Optimisation and Calculus of Variations, 13(1):93–106, 2007.
  * [21] C. Griessler.  $c$-cyclical monotonicity as a sufficient criterion for optimality in the multimarginal Monge–Kantorovich problem.  Proceedings of the American Mathematical Society, 146(11):4735–4740, 2018.
  * [22] H. Jylhä.  The $l^{\infty}$-optimal transport: infinite cyclical monotonicity and the existence of optimal transport maps.  Calculus of Variations and Partial Differential Equations, 52:303–326, 2015.
  * [23] Y.-H. Kim and B. Pass.  A general condition for Monge solutions in the multi-marginal optimal transport problem.  SIAM Journal on Mathematical Analysis, 46(2):1538–1550, 2014.
  * [24] M. Knott and C. Smith.  On Hoeffding-Fréchet bounds and cyclic monotone relations.  Journal of multivariate analysis, 40(2):328–334, 1992.
  * [25] R. J. McCann.  Existence and uniqueness of monotone measure-preserving maps.  Duke Math. J., 80:309–323, 1995.
  * [26] G. Minty.  On the monotonicity of the gradient of a convex function.  Pacific Journal of Mathematics, 14(1):243–247, 1964.
  * [27] J.-J. Moreau.  Convex functionals.  Seminaire Jean Leray, (2):1–108, 1966.
  * [28] M. Petrache.  Cyclically monotone non-optimal n-marginal transport plans and Smirnov-type decompositions for n-flows.  ESAIM: Control, Optimisation and Calculus of Variations, 26:120, 2020.
  * [29] A. Pratelli.  On the sufficiency of c-cyclical monotonicity for optimality of transport plans.  Mathematische Zeitschrift, 258(3):677–690, 2008.
  * [30] Yu. V. Prokhorov.  Convergence of random processes and limit theorems in probability theory.  Theory of Probability & Its Applications, 1(2):157–214, 1956.
  * [31] J.-C. Rochet.  A necessary and sufficient condition for rationalizability in a quasi-linear context.  Journal of Mathematical Economics, 16(2):191–200, 1987.
  * [32] R. T. Rockafellar.  Characterization of the subdifferentials of convex functions.  Pacific Journal of Mathematics, 17(3):497–510, 1966.
  * [33] R. T. Rockafellar.  Convex analysis, volume 11.  Princeton University Press, 1997.
  * [34] R. T. Rockafellar.  Convex analysis.  Princeton University Press, 2015.
  * [35] R Tyrrell Rockafellar and Roger J-B Wets.  Variational analysis, volume 317.  Springer Science & Business Media, 2009.
  * [36] L. Rüschendorf.  On c-optimal random variables.  Statistics & probability letters, 27(3):267–270, 1996.
  * [37] F. Santambrogio.  Optimal transport for applied mathematicians.  Birkäuser, NY, 55(58-63):94, 2015.
  * [38] W. Schachermayer and J. Teichmann.  Characterization of optimal transport plans for the Monge-Kantorovich problem.  Proceedings of the American Mathematical Society, 137(2):519–529, 2009.
  * [39] C. Villani.  Optimal transport: old and new, volume 338.  Springer Science & Business Media, 2008.
  * [40] C. Villani.  Topics in optimal transportation, volume 58.  American Mathematical Soc., 2021.
  * [41] K. Wyczesany.  Topics in high-dimensional geometry and optimal transport.  PhD thesis, University of Cambridge, 2021.