# Optimal measure transportation with respect to non-traditional costs

S. Artstein-Avidan, S. Sadovsky, K. Wyczesany

###### Abstract.

We study optimal mass transport problems between two measures with respect to
a non-traditional cost function, i.e. a cost $c$ which can attain the value
$+\infty$. We define the notion of $c$-compatibility and
strong-$c$-compatibility of two measures, and prove that if there is a finite-
cost plan between the measures then the measures must be $c$-compatible, and
if in addition the two measures are strongly $c$-compatible, then there is an
optimal plan concentrated on a $c$-subgradient of a $c$-class function. This
function is the so-called potential of the plan.

We give two proofs of this theorem, under slightly different assumptions. In
the first we utilize the notion of $c$-path-boundedness, showing that strong
$c$-compatibility implies a strong connectivity result for a directed graph
associated with an optimal map. Strong connectivity of the graph implies that
the $c$-cyclic monotonicity of the support set (which follows from classical
reasoning) guarantees its $c$-path-boundedness, implying, in turn, the
existence of a potential. We also give a constructive proof, in the case when
one of the measures is discrete. This approach adopts a new notion of ‘Hall
polytopes’, which we introduce and study in depth, to which we apply a version
of Brouwer’s fixed point theorem to prove the existence of a potential in this
case.

##  1\. Introduction and results

The Monge transport problem is concerned with finding a _transport map_ moving
mass from one probability measure111All considered measures are Borel measures
on Polish spaces, which are complete, separable metric spaces equipped with
their Borel $\sigma$-algebra. to another, in a way which is efficient with
respect to some _cost function_. The most widely studied case of this problem
is for the quadratic cost $c(x,y)=\|x-y\|_{2}^{2}/2$, for which the
Brenier–Gangbo-McCann theorem [10, 12] implies that under mild conditions on
the measures involved, optimal transport maps exist and are given by gradients
of convex functions. In this work the main emphasis will be on _non-
traditional_ cost functions, i.e. costs that can attain the value $+\infty$,
as this project is motivated by the study of transportation with respect to
the so-called _polar cost_ given by

(1) $p(x,y)=-\ln(\langle x,y\rangle-1),$

where $p(x,y)=+\infty$ if $\langle x,y\rangle\leq 1$. This cost function is
linked with the polarity transform (see [3, 4]), similarly to the strong
connection of the quadratic cost with the Legendre transform. Transportation
with respect to polar cost was first considered in [7].

We provide necessary conditions on pairs of measures, together with a cost
$c$, for which finite cost plans exist. To this end, we discuss the class of
functions connected with a cost, called its $c$-class (see the definition in
Section 2.2). The optimality of a plan is linked with the possibility of
finding a “potential” for the plan, which is a $c$-class function such that
the plan lies on its $c$-subgradient (yet another important notion we discuss
in depth, see the definition in Equation (7)).

We will see shortly that the mere existence of a finite cost plan between two
measures $\mu$ and $\nu$ implies that the two measures considered are
$c$-compatible, namely that for any measurable set $A$ in the measure space
$(X,\mu)$, one has that $\mu(A)\leq\nu(\\{y:\exists x\in
A,\,\,c(x,y)<\infty\\})$. This is quite intuitive – all points (up to measure
$0$) in $A$ must be mapped to points in the target space with which they have
finite cost. This $c$-compatibility of two measures is thus a necessary
condition (for the formal definition of $c$-compatibility see Definition 3.2,
and for the statement of the necessity of this condition see Lemma 3.3). As an
example we will show (see Example 3.5) that $c$-compatibility is not a
sufficient condition for the existence of a finite cost plan. However, if a
finite cost plan exists, a slight strengthening of $c$-compatibility condition
in which we demand a strict inequality is already sufficient to ensure that
the optimal plan has a potential. We will show later why our notion of “strong
compatibility” is a very natural strengthening of compatibility, and discuss
cases where two measures are $c$-compatible but not strongly $c$-compatible
and how this implies that the transport problem is decomposable into sub-
problems.

In this note we only consider symmetric cost functions $c:X\times
X\to(-\infty,\infty]$ with $c(x,y)=c(y,x)$, but to see the difference between
the two variables we denote the second copy of $X$ by $Y$ and write $c:X\times
Y\to(-\infty,\infty]$. Our results hold for the non-symmetric case as well,
with only minor adjustments. We will also add a lower-bound assumption on the
cost $c$ which allows to integrate it and its marginals (see also Example
2.5). We say that $c$ is essentially bounded from below with respect to $\mu$
and $\nu$ if there exist functions $a(x)\in L^{1}(\mu)$, $b(x)\in L^{1}(\nu)$
such that $c(x,y)\geq a(x)+b(y)$. For the polar cost this condition is
satisfied if, for example, both measures have finite second moment.

Our main theorem is the following (here $\partial^{c}\varphi$ denotes the
$c$-subgradient of $\varphi$, see the definition in equation (7), and
$\Pi(\mu,\nu)$ denotes all transport plans between $\mu$ and $\nu$, see the
beginning of Section 2).

######  Theorem 1.1.

Let $X=Y$ be a Polish space, let $c:X\times Y\to(-\infty,\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

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

If there exists _some_ finite cost 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$.

The proof uses results from [5] on $c$-path-boundedness, which is a notion
that replaces $c$-cyclic monotonicity from the Rockafellar-Rochet-Rüschendorf
result (see [17, 16, 18]) in the case when the cost is non-traditional. The
$c$-path-boundedness is a necessary and sufficient condition for a set to be
included in a $c$-subgradient of a $c$-class function.

Since the initial main interest for us in developing this theory concerned the
polar cost, in which case we have a precise form for $c$-subgradients, let us
state the relevant theorem, which is almost a direct application of the
theorem above, together with some simple analysis of polar-subgradients as
performed in [4]. By ${\rm Cvx}_{0}(\mathbb{R}^{n})$ we denote a class of
lower semi-continuous convex functions from $\mathbb{R}^{n}$ to $[0,\infty]$
which take the value zero at the origin. By ${\mathcal{A}}$ we denote the
polarity transform on the class ${\rm Cvx}_{0}(\mathbb{R}^{n})$, defined in
[3] and given in (14).

######  Theorem 1.2.

Let $X=Y=\mathbb{R}^{n}$ and let $\mu,\,\nu\in{\mathcal{P}}(\mathbb{R}^{n})$
be probability measures with finite second moment, which are strongly
$p$-compatible where $p(x,y)=-\ln(\langle x,y\rangle-1)_{+}$ is the polar
cost, that is

$\mu(K)+\nu(K^{\circ})<1$

for any convex set $K$ with $\mu(K)\neq 0,1$. Assume further that $\mu$ is
absolutely continuous. Assume there exists some finite cost plan mapping $\mu$
to $\nu$. Then there exists $\varphi\in{\rm Cvx}_{0}(\mathbb{R}^{n})$ such
that $\partial^{\circ}\varphi$ is an optimal transport map between $\mu$ and
$\nu$, where

$\partial^{\circ}\varphi(x)=\\{y\in\mathbb{R}^{n}:\,\varphi(x){\mathcal{A}}\varphi(y)=\langle
x,y\rangle-1>0\\}.$

In particular, for $\mu$-almost every $x$, the set
$\partial^{\circ}\varphi(x)$ is a singleton.

We remark that the existence of a potential function for the cost $p$ and
other non-traditional costs leads naturally to the question regarding
regularity of such potentials (as introduced by Caffarelli in [11] and
developed, among others, by Trudinger and Wang in [21]). In this work we do
not pursue this direction, and instead focus on the analysis of the existence
of potentials, leaving the question of regularity for future work.

In the second half of the paper we specialize to the case where $\nu$ is
discrete. In this case we give a constructive proof for the existence of a
transport map, where the $c$-class function is given as a finite infimum of
“basic functions” (see (6)) associated with the cost. The advantage of this
method is that much of the geometry of the problem is revealed. In the proof,
we generalize a method used by K. Ball [6] for the quadratic cost, where all
possible maps are parametrized by a weight vector, and the existence of the
required one is shown using Brouwer’s fixed point theorem. However, in
contrast with the case of the classical quadratic cost function and other
traditional costs, when the cost attains infinite values the set of all
discrete measures with a given support, to which a measure $\mu$ can be mapped
with finite cost, is given by an interesting polytope which we call the _Hall
polytope_ of the measure $\mu$. The condition of strong $c$-compatibility
corresponds to measures with weight vectors in the interior of the polytope.
We present a thorough study of the structure and geometry of Hall polytopes
(which for traditional costs are just simplices), which we use to prove
Theorem 1.3 below. An advantage of this method is that we can relax the
conditions on the cost function. We do need a condition of $c$-regularity for
the measure $\mu$ (given in Definition 5.1), which for the polar cost is
satisfied if, say, $\mu$ is absolutely continuous.

######  Theorem 1.3.

Let $X$ be some Polish space and $Y=\\{u_{i}\\}_{i=1}^{m}$. Assume $c:X\times
Y\to(-\infty,\infty]$ is a measurable cost function, $\mu\in{\mathcal{P}}(X)$
is $c$-regular and
$\nu=\sum_{i=1}^{m}\alpha_{i}\mathbbm{1}_{u_{i}}\in{\mathcal{P}}(Y)$. Assume
furthermore, that the intersection

$\\{x\in X:c(x,u_{i})<\infty\\}\cap\\{x\in X:c(x,u_{j})<\infty\\}$

contains an open set for each pair $u_{i},u_{j}$. If $\mu$ and $\nu$ are
strongly $c$-compatible then there exists an optimal transport plan
$\pi\in\Pi(\mu,\nu)$ whose graph lies in the $c$-subgradient
$\partial^{c}\varphi$ of a $c$-class function $\varphi:X\to[-\infty,\infty]$.

The case where the measures $\mu$ and $\nu$ are $c$-compatible but not
strongly so, can be analyzed as well. In this case we can write
$\mu=\mu_{1}+\mu_{2}$ and $\nu=\nu_{1}+\nu_{2}$ where $\mu_{1}(X)=\nu_{1}(Y)$
(and so $\mu_{2}(X)=\nu_{2}(Y)$), where the measures $\mu_{1}$ and $\mu_{2}$
are concentrated on disjoint sets, as are $\nu_{1}$ and $\nu_{2}$, and in such
a way that any finite cost transport plan $\pi\in\Pi(\mu,\nu)$ is given as a
sum of $\pi_{1}\in\Pi(\mu_{1},\nu_{1})$ and $\pi_{2}\in\Pi(\mu_{2},\nu_{2})$.
We illustrate this in Section 7.

### Structure of the paper

Section 2 is dedicated to gathering all the required definitions and notions
and previous results. In Section 3 we discuss the notion of $c$-compatibility
and strong $c$-compatibility together with their geometric interpretation. In
Section 4 we prove Theorem 1.1. In Section 5 we go back to the discrete case
and show how one may treat it using some deep structural properties of Hall
polytopes, which we establish, proving Theorem 1.3. In Section 6 we specialize
to the polar cost, showing that for absolutely continuous measure the optimal
plan is given by a map. In Section 7 we discuss the case of measures which are
$c$-compatible but not strongly $c$-compatible. For completeness an appendix A
in which we review $c$-subgradients, with detailed examples and geometric
intuition.

### Acknowledgment

The authors were supported by the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No 770127). The second named author is grateful to the Azrieli
foundation for the award of an Azrieli fellowship.

##  2\. Background and preliminary observations

###  2.1. Transport plans and maps

Given two measure spaces $X,\,Y$, a measurable222When referring to a function
on $X\times Y$ as “measurable” we assume it is both measurable with respect to
the product $\sigma$-algebra and its fibers $f(\cdot,y)$ and $f(x,\cdot)$ are
measurable functions on $X$ and $Y$ respectively, for any $x\in X$ and $y\in
Y$.  cost function $c:X\times Y\to(-\infty,\infty]$, and probability measures
$\mu$ on $X$ and $\nu$ on $Y$, we say that there exists a _$c$ -optimal
transport map_ between them if the following infimum is attained:

$\inf_{T}\int_{X}c(x,T(x))d\mu(x),$

where $T:X\to Y$ are measurable _transport maps_ , i.e.
$\nu(B)=\mu(T^{-1}(B))$ for all measurable sets $B\subset Y$. We say that
there exists a _$c$ -optimal plan_ between them if the infimum

(2) $\inf_{\pi}\int_{X\times Y}c(x,y)d\pi(x,y)$

is attained, where $\pi\in\Pi(\mu,\nu)$, namely $\pi$ is a probability measure
on $X\times Y$ satisfying

$\pi(A\times Y)=\mu(A),\ \ \ \pi(X\times B)=\nu(B)$

for all measurable sets $A\subset X$ and $B\subset Y$. Every transport map
induces a transport plan supported on its graph, while not every plan is
induced by a map. We denote the infimum in (2), also called the “total cost”,
by $C(\mu,\nu)$. Due to the Kantorovich Duality Theorem [13, 14], when $c$ is
lower semi-continuous, the total cost is equal to

(3) $\sup_{\varphi,\psi}\left\\{\int_{X}\varphi d\mu+\int_{Y}\psi d\nu:\
\varphi\in L_{1}(X,\mu),\,\psi\in
L_{1}(Y,\nu){\rm~{}~{}~{}admissible}\right\\}$

where $(\varphi,\psi)$ is called an _admissible pair_ , if
$\varphi:X\to[-\infty,\infty]$, $\psi:Y\to[-\infty,\infty]$ satisfy

$\forall(x,y)\in X\times Y,\,\,\,\ \varphi(x)+\psi(y)\leq c(x,y).$

In the case where $\varphi=+\infty$ and $\psi=-\infty$ we stipulate
$-\infty+\infty=-\infty$, namely in such a case the condition above holds
regardless of the value of $c(x,y)$.

###  2.2. The $c$-transform

Motivated by (3), for every function $\psi:Y\to[-\infty,\infty]$ one may
consider the largest function $\varphi$ for which $(\varphi,\psi)$ is an
admissible pair, and vice versa. This gives rise to the
$\mathbf{c}$-transform, defined by

(4) $\psi^{c}(x)=\inf_{y}(c(x,y)-\psi(y)),$

and

(5) $\varphi^{c}(y)=\inf_{x}(c(x,y)-\varphi(x)).$

######  Remark 2.1.

Here if on the right hand side are infinities of opposite signs, which may
occur only if $\psi(y)=\infty$ (as $c\neq-\infty$), we use the opposite
convention, namely $-\infty+\infty=+\infty$, since when the cost $c(x,y)$ is
infinite there is no restriction on the sum $\varphi(x)+\psi(y)$. In general
one must be careful with sums of opposite side infinities, as there is no
obvious “rule of thumb” that can apply everywhere.

Note that for a general cost we may lose the measurability of $\varphi$ when
applying the $c$-transform, as well as integrability, even under the
assumption that $c$ is measurable in the strong sense we have postulated. When
$c$ is continuous, however, this is less of a problem. Also, by truncating the
functions and taking limits, the issue of integrability can sometimes be
resolved. Nevertheless, one should be extra careful when using (3) for a pair
$\varphi,\varphi^{c}$ when the cost is non-traditional, and in the existing
literature it is not always clear for which theorems does the non-traditional
case follow from the same proof.

When $X=Y$ and $c(\cdot,\cdot)$ is symmetric in its arguments the transforms
in (4) and (5) coincide. Hence, abusing notation, we use the same notation for
both. We define the $c$-class as the image of the $c$-transform
$\\{\psi^{c}:\psi:Y\to[-\infty,\infty]\\}$, or equivalently, as all the
functions $\varphi$ such that $\varphi^{cc}=\varphi$. By definition, any
function in the $c$-class is an infimum of _basic functions_ , which are
functions of the form

(6) $c(x)=c(x,y_{0})+t$

for some $y_{0}\in Y$ and $t\in\mathbb{R}$. It is useful to notice that the
$c$-class is always closed under pointwise infimum (this fact is commonly
known and used, see e.g. [1, 22], and a simple proof can be found in [24]).

###  2.3. The $c$-subgradient

Given a function $\varphi$ in the $c$-class, its $c$-subgradient is the subset
of $X\times Y$ given by

(7) $\partial^{c}\varphi=\\{(x,y):\,\varphi(x)+\varphi^{c}(y)=c(x,y)\,\text{
and }\,c(x,y)<\infty\\}.$

To illustrate the relevance of $c$-subgradients to the study of optimal
transport, let us present a folklore argument, which can be made precise for
traditional costs, and which we only use as motivation but do not claim it
holds in general.

In Kantorovich Duality Theorem, recalled as (3) above, one is inclined to
replace $\psi$ with the largest admissible partner of $\varphi$ (at least so
long as it is measurable and in $L_{1}(\nu)$), and then replace $\varphi$ by
$\varphi^{cc}$. In this sense, one may think of (3) applied only to admissible
pairs $(\varphi,\varphi^{c})$, where $\varphi=\varphi^{cc}$ is in the
$c$-class. However, for any $\pi\in\Pi(\mu,\nu)$ and $\varphi$ is in the
$c$-class,

$\displaystyle\int_{X}\varphi
d\mu(x)+\int_{Y}\varphi^{c}(y)d\nu(y)=\int_{X\times
Y}(\varphi(x)+\varphi^{c}(y))d\pi(x,y)\leq\int_{X\times Y}c(x,y)d\pi(x,y)$

So for equality between the left and right hand side to be obtained for some
(potential) $\varphi$ and (optimal plan) $\pi$, we see that $\pi$ must be
concentrated on the set $\partial^{c}\varphi$. In other words, finding optimal
plans admitting a potential is equivalent to finding some plan supported on a
$c$-subgradient. While this argument is not precise (in particular, we ignored
measurability and integrability assumptions, applying (3) to a pair
$(\varphi,\varphi^{c})$), it constitutes the motivation behind searching for
potentials in optimal transport problems.

The above observation shows the importance of the notion of the
$c$-subgradient mapping. The name $c$-subgradient is connected to the fact
that for the classical cost $c(x,y)=-\langle x,y\rangle$, the $c$-class
consists of upper semi-continuous concave functions, the $c$-transform of
$-\varphi$ is $-{\mathcal{L}}(\varphi)$, and the $c$-subgradient of $-\varphi$
at $x$ is the usual subgradient $\partial\varphi(x)$. So as not to disturb the
flow of the paper, we gathered some basic facts about the $c$-subgradient,
including the geometric intuition behind it, in Appendix A.

###  2.4. $c$-cyclic monotonicity and $c$-path-boundedness

The connection between optimality of a plan and some geometric information on
its support is quite intuitive: if a plan is optimal, then we should not gain
any profit by interchanging several portions of it. This is the idea behind
the well known notion of $c$-cyclic monotonicity. Given a cost $c:X\times
Y\to(-\infty,\infty]$, a subset $G\subset X\times Y$ is called $c$-cyclically
monotone if $c(x,y)<\infty$ for all $(x,y)\in G$, and for any $m$, any
$(x_{i},y_{i})_{i=1}^{m}\subset G$, and any permutation $\sigma$ of
$[m]=\\{1,\ldots,m\\}$ it holds that

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

This definition seems to have been first introduced by Knott and Smith [19],
as a generalization of cyclic monotonicity considered by Rockafellar [17] in
the case of quadratic cost. It is easy to check that if $\varphi$ is a
$c$-class function then any set $G\subset\partial^{c}\varphi$ is
$c$-cyclically monotone. The theorems of Rockafellar, Rochet and Rüschendorf
give the reverse implication, in the case of a traditional cost. Namely, when
$c:X\times Y\to\mathbb{R}$, a set $G\subset X\times Y$ is $c$-cyclically
monotone if and only if there exists a $c$-class function such that
$G\subset\partial^{c}\varphi$.

For non-traditional costs, this is no longer the case, and one may construct
$c$-cyclically monotone sets which admit no potential. In [5], the
corresponding result for non-traditional costs is provided. Cyclic
monotonicity has to be replaced by a stronger notion, which we called
$c$-path-boundedness.

######  Definition 2.2.

Fix sets $X,\,Y$ and $c:X\times Y\to(-\infty,\infty]$. A subset $G\subset
X\times Y$ will be called $c$-path-bounded if $c(x,y)<\infty$ for any
$(x,y)\in G$, and for any $(x,y)\in G$ and $(z,w)\in G$, there exists a
constant $M=M((x,y),(z,w))\in\mathbb{R}$, such that the following holds: For
any $m\in{\mathbb{N}}$ and any $(x_{i},y_{i})_{i=2}^{m-1}\subset G$, denoting
$(x_{1},y_{1})=(x,y)$ and $(x_{m},y_{m})=(z,w)$, we have

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

The fact that a $c$-path-bounded set is also $c$-cyclically monotone is easy
to establish (see [5]). With this definition the main theorem of [5] can be
stated.

######  Theorem 2.3.

Let $X,\,Y$ be sets and let $c:X\times Y\to(-\infty,\infty]$ be given. A set
$G\subset X\times Y$ is $c$-path-bounded if and only if there exists a
$c$-class function $\varphi$ such that $G\subset\partial^{c}\varphi$.

It was also demonstrated in [5] that under certain conditions, the notions of
$c$-cyclic monotonicity and $c$-path-boundedness do coincide. One such
instance, which will be used in this paper, is explained and formulated in
Proposition 4.1 in Section 4.

###  2.5. Some know results about existence of optimal plans and potentials

Having fixed a cost, the discussion about the structure of an optimal plan
naturally splits into several components. The first, which is relevant only
when the cost is non-traditional, is the existence of some finite cost plan
(necessary conditions will be discussed in the next section). Further, one can
ask whether an optimal plan exists. This is the object of the next theorem,
which is quoted from Villani [23].

Recall that $\Pi(\mu,\nu)$ denotes the set of all probability measures on
$X\times Y$ whose marginals are $\mu\in{\mathcal{P}}(X)$ and
$\nu\in{\mathcal{P}}(Y)$, and that $c:X\times Y\to(-\infty,\infty]$ is
essentially bounded with respect to $\mu$ and $\nu$ if there exist upper semi-
continuous function $a:X\to(-\infty,\infty]$, $a\in L_{1}(\mu)$ and
$b:X\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$.

######  Theorem 2.4.

Let $X,\,Y$ be two Polish spaces, let $\mu\in{\mathcal{P}}(X)$ and
$\nu\in{\mathcal{P}}(Y)$. Let $c:X\times Y\to(-\infty,\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)$.

Let us note that, in the above theorem, the existence of a plan with finite
total cost is not assumed as when no finite cost plan exists, any plan (say,
$\mu\otimes\nu$) is optimal in a trivial sense. Further, a simple example
demonstrates that without some kind of assumption on boundedness from below of
the cost, the total cost may be $-\infty$, and in this case optimal measures
can be concentrated on sets which are far from being $c$-cyclically monotone.

######  Example 2.5.

Let $p(x,y)=-\ln(xy-1)_{+}$ be the polar cost on
$\mathbb{R}_{+}\times\mathbb{R}_{+}$. Let $\mu$ be a discrete probability
measure on $\mathbb{R}_{+}$ given by
$\mu=\sum_{n=2}^{\infty}\alpha_{n}\mathbbm{1}_{n}$, where $\alpha_{n}$ are
such that $\sum_{n=2}^{\infty}\alpha_{n}=1$ and
$\sum_{n=2}^{\infty}n^{3/2}\alpha_{n}=\infty$. Consider transport plans of
$\mu$ to itself, namely $\Pi(\mu,\mu)$.

WE claim that in this case, the identity map $x\mapsto x$ is a transport plan
whose total cost is $-\infty$ (in particular, it is optimal) but it is not
supported on a $p$-cyclically monotone set. Indeed, consider the measure
$\pi_{\mu}$ on the diagonal whose projection is $\mu$. Its total cost is

$\sum_{n=2}^{\infty}-\ln(n^{2}-1)\alpha_{n}\leq-\sum_{n=1}^{\infty}n^{3/2}\alpha_{n}=-\infty.$

Clearly even for two points $(x_{1},y_{1})=(2,2)$ and $(x_{2},y_{2})=(3,2)$ it
holds that

$-\ln(2\cdot 2-1)-\ln(3\cdot 3-1)=-\ln(24)>-\ln(2\cdot 3-1)-\ln(3\cdot
2-1)=-\ln(25).$

We thus see that an optimal plan (albeit with negative infinity cost) may have
support which is not $c$-cyclically monotone.

Analysing the geometric structure of an optimal plan, after showing its
existence, is a problem which has a long history. After Brenier [10],
following Rüschendorf [18] determined the classical structure of cyclic
monotonicity of optimal plans, Gangbo and McCann [12] extended the result to
lower semi-continuous cost functions bounded from below. They showed that
every finite optimal plan with respect to such costs lies on a $c$-cyclically
monotone set. Beiglböck, Goldstern, Maresch, and Schachermayer [8] generalised
the result further by removing regularity assumptions on the cost:

######  Theorem 2.6 (See [8, 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]$ a Borel measurable cost function.
Then every finite optimal transport plan is $c$-cyclically monotone.

The reverse implication, that $c$-cyclic monotonicity implies optimality, is
not true in general as shown in Example 3.1 in [1]. In [8] Theorem 1.b, it was
shown that for a measurable cost function $c$ the assumption that the
“infinity” set $\\{(x,y):c(x,y)=\infty\\}$ is a union of a closed set and a
$\mu\otimes\nu$-null set, implies that every finite $c$-cyclically monotone
plan is optimal.

Finally, the question of the existence of a potential for the optimal plan
remains. A result in this direction was presented in [8]; it states that, with
assumptions as in Theorem 2.6, a finite cost plan admits a potential if and
only if it is “robustly optimal” (see Definition 1.6. in [8]). In particular,
their result implies that a plan which admits a potential is optimal. In this
note, our main goal is to find conditions on the pairs of measures that
guarantee the existence of a potential for the optimal transport plan between
them, thus guaranteeing, in fact, robust optimality.

##  3\. Compatibility

Given two probability measures, before trying to find an element of
$\Pi(\mu,\nu)$ with some good structure (say, a potential), or an optimal
element with respect to the cost, one must figure out whether any element
$\pi\in\Pi(\mu,\nu)$ has a finite cost. Clearly, if the cost function is
bounded, we may find a finite cost plan between any pair of measures. However,
if the cost admits the value $+\infty$, an obvious necessary condition for the
existence of a finite cost plan is that every set in $(X,\mu)$ has “enough”
points in $(Y,\nu)$ to which it can be mapped for a finite cost.

In the case of two discrete measures, this necessary condition is also
sufficient, which is the subject of Hall’s marriage theorem. We start with
this simple case as it gives some intuition for our next steps.

###  3.1. Starting point: Hall’s Marriage Theorem

In the following motivating example, for some $(x_{i})_{i=1}^{m}\subset X$ let
$\mu=\sum_{i=1}^{m}\frac{1}{m}\mathbbm{1}_{x_{i}}$ be a probability measure on
$X$, and for $(y_{i})_{i=1}^{m}\subset Y$ let
$\nu=\sum_{i=1}^{m}\frac{1}{m}\mathbbm{1}_{y_{i}}$ be a probability measure on
$Y$. Let $c:X\times Y\to(-\infty,\infty]$ be an arbitrary cost. A finite cost
map is a given by a bijection $T:(x_{i})_{i=1}^{m}\to(y_{i})_{i=1}^{m}$, such
that $c(x_{i},T(x_{i}))<\infty$ for all $i=1,\dots m$. The bijection $T$
corresponds, of course, to a permutation $\sigma:[m]\to[m]$. By Birkhoff’s
theorem on the extremal points of bi-stochastic matrices, every transport plan
$\pi\in\Pi(\mu,\nu)$ is a convex combination of permutation maps $T$.

The condition for the existence of a finite cost map/plan can be thus
reformulated in a graph-theoretic way: Let $G$ be a bipartite graph with a
vertex set $V=(x_{i})_{i=1}^{m}\cup(y_{i})_{i=1}^{m}$ and edges
$E=\\{(x_{i},y_{j}):\,c(x_{i},y_{j})<\infty\\}$. A finite cost map $T$
corresponds a matching in this graph. Hall’s Marriage Theorem gives the
necessary and sufficient conditions for such a matching to exist.

######  Theorem 3.1 (Hall’s Marriage Theorem).

A bipartite graph $G$ with a vertex set $V_{1}\cup V_{2}$, such that
$|V_{1}|=|V_{2}|$, contains a complete matching if and only if $G$ satisfies
Hall’s condition

$|N_{G}(S)|\geq|S|\text{ for every }S\subset V_{1},$

where $N_{G}(S)\subset V_{2}$ is the set of all neighbors of vertices in $S$.

The condition can be reformulated in terms of the measures, as

$\mu(A)\leq\nu(\\{y:\exists x\in A,\,\,c(x,y)<\infty\\})$

for any $A\subset X$, or, equivalently,

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

In fact, in this discrete and finite case, once we have determined the
existence of a finite cost map, we may consider, among the finite number of
possible matchings, the one with minimal cost (there may, of course, be more
than one). It is then not hard to show (and will follow from our results as
well) that this resulting optimal plan must lie on a $c$-subgradient of a
$c$-class function. (This fact follows from a variation of a theorem of
Rüschendorf [18], see also [5].)

###  3.2. The $c$-compatibility condition

The continuous counterpart for Hall’s condition is an obvious necessary
condition for the existence of a finite cost plan.

######  Definition 3.2.

Let $X,\,Y$ be measure spaces and $c:X\times Y\to(-\infty,\infty]$ be a
measurable cost function. We say that two probability measures
$\mu\in{\mathcal{P}}(X)$ and $\nu\in{\mathcal{P}}(Y)$ are _$c$ -compatible_ if
for any measurable $A\subset X$ it holds that

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

It is not hard to check that $c$-compatibility is in fact a symmetric notion,
and the above condition holds if and only if for any $B\subset Y$ we have

$\nu(B)+\mu(\\{x:\forall y\in B,\,\,c(x,y)=\infty\\})\leq 1.$

Indeed, to get the latter we let $A=\\{x:\forall y\in B,\,\,c(x,y)=\infty\\}$,
in which case $B\subset\\{y:\forall x\in A,\,\,c(x,y)=\infty\\}$. Applying the
assumed inequality, we get

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

The fact that any plan $\pi\in\Pi(\mu,\nu)$ which has finite cost must be
concentrated on the finiteness set

$S=\\{(x,y):c(x,y)<\infty\\}\subset X\times Y$

implies the necessity of the condition, as is given in the following lemma.

######  Lemma 3.3.

Let $X,\,Y$ be measure spaces and $c:X\times Y\to(-\infty,\infty]$ be a
measurable cost function. Given $\mu\in{\mathcal{P}}(X)$ and
$\nu\in{\mathcal{P}}(Y)$, assume there exists $\pi\in\Pi(\mu,\nu)$ which is
concentrated on $S=\\{(x,y)\in X\times Y:\ c(x,y)<\infty\\}$. Then $\mu$ and
$\nu$ are $c$-compatible.

###### Proof.

Let $A\subset X$. As $\pi\in\Pi(\mu,\nu)$, we know $\mu(A)=\pi(A\times Y)$,
and by assumption, $\pi(A\times Y)=\pi((A\times Y)\cap S)$. Similarly,

$\nu(\\{y:\forall x\in A,\,\,c(x,y)=\infty\\})=\pi((X\times\\{y:\forall x\in
A\,\,,\,\,c(x,y)=\infty\\})\cap S).$

However, these two sets are disjoint, since if $(x,y)\in S$ then
$c(x,y)<\infty$, so if $x\in A$ then clearly $y$ does not satisfy that for all
$x\in A$, $c(x,y)=\infty$. Therefore, the $\pi$-measures of the two sets sum
to at most $1$. ∎

It is useful to know that in certain situations the $c$-compatibility
condition is also sufficient for the existence of a finite cost plan; such is
the case when the finiteness set $S$ is closed. One may then use the following
theorem of Strassen [20].

######  Theorem 3.4 (Strassen).

Let $X,\,Y$ be complete separable metric measure spaces and let $S$ be a non-
empty closed subset of $X\times Y$. Given $\mu\in{\mathcal{P}}(X)$ and
$\nu\in{\mathcal{P}}(Y)$, there exists $\pi\in\Pi(\mu,\nu)$ which is supported
on $S$ if and only if for all open $B\subset Y$

(9) $\nu(B)\leq\mu(P_{X}(S\cap(X\times B))),$

where $P_{X}$ is a projection onto $X$.

In the case of a non-traditional cost $c$, the relevant set $S$ considered in
Lemma 3.3 is not necessarily closed. If $S$ is closed, and $c$ is bounded on
it, then the condition in Strassen’s Theorem is sufficient for the existence
of a finite-cost transport plan. In some cases, one may use this together with
the theorems stated in Section 2.5 and the results from [5] to show that a
minimizing plan exists and is concentrated on the graph of a $c$-subgradient.
An example of such reasoning for some explicit cost functions will appear in
the forthcoming [2].

However, for certain important costs, and in particular for the polar cost $p$
defined in $\eqref{def:polar-cost}$ which serves as a motivating example for
this study, the set $S$ of finite-cost pairs is not closed.

To illustrate the problem, let us give an example of two measures on intervals
which are $c$-compatible (we will use the one dimensional polar cost) but do
not admit any plan supported on the finiteness set $S$.

######  Example 3.5.

Consider once more the polar cost $p(x,y)=-\ln(xy-1)_{+}$ on
$\mathbb{R}^{+}\times\mathbb{R}^{+}$. Its finiteness set is
$S=\\{(x,y):xy>1\\}$. Let $\gamma$ be the uniform measure on the set
$S_{1}=\\{(x,1/x)\in\mathbb{R}^{2}:x\in[1/2,2]\\}$ and let $\mu$ be its
marginal on the first coordinate and $\nu$ its marginal on the second
coordinate.

It is not hard to check that the measures $\mu$ and $\nu$ (which are the same
measure) are $p$-compatible. Indeed, let $A\subset\mathbb{R}^{+}$ be open,
note that

$P_{X}((\mathbb{R}^{+}\times A)\cap S)=\cup_{y\in
A}(1/y,\infty)=(1/\sup(A),\infty).$

Additionally, for any number $\alpha\in[1/2,2]$ we have, by definition, that
$\nu([1/2,\alpha])=\mu([1/\alpha,2])$. Combining these observations with the
continuity of $\mu$ and $\nu$ we see that the measures are polar compatible

$\nu(A)\leq\nu([1/2,\sup(A)])=\mu([1/\sup(A),2])=\mu([1/\sup(A),\infty))=\mu(P_{X}((A\times
X)\cap S)).$

We turn to show that there is no transport plan $\pi\in\Pi(\mu,\nu)$ supported
on $S$. Assume towards a contradiction that there exists such a transport plan
$\pi$. In particular, this implies that there exists some rectangle
$B=[x_{1},x_{2}]\times[y_{1},y_{2}]\subset S$ of positive measure. By the
definition of $S$, we have that $x_{1}y_{1}>1$. As $\pi$ is supported in $S$
we see that

$\mu([1/2,x_{1}])=\pi([1/2,x_{1}]\times[x_{1}^{-1},2])\leq\nu([x_{1}^{-1},2])=\mu([1/2,x_{1}])$

where the last equality follows from the definition of $\mu$ and $\nu$. We
thus have equalities all along. Similarly,

$\nu([1/2,x_{1}^{-1}])=\pi([x_{1},2]\times[1/2,x_{1}^{-1}])\leq\mu([x_{1},2])=\nu([1/2,x_{1}^{-1}]).$

So we conclude that
$\pi([1/2,x_{1}]\times[x_{1}^{-1},2])+\pi([x_{1},2]\times[1/2,x_{1}^{-1}])=\mu([1/2,x_{1}])+\mu([x_{1},2])=1,$
that is, $\pi$ is supported on
$[1/2,x_{1}]\times[x_{1}^{-1},2]\cup[x_{1},2]\times[1/2,x_{1}^{-1}])$, which
is a contradiction to the fact that $\pi(B)>0$.

Figure 1. A schematic drawing of Example 3.5.

###  3.3. The Hall polytope

Let us consider a special case, which will be the focus of Section 5, when one
of the measures is discrete and the other one arbitrary. In such a case, the
compatibility condition can be realized geometrically by a polytope, which we
call the Hall polytope. We use
$\Delta_{m}=\\{\alpha\in\mathbb{R}^{m}:\alpha_{i}\geq
0,\,\sum_{i=1}^{m}\alpha_{i}=1\\}$ to denote the $(m-1)$-dimensional simplex.

######  Definition 3.6.

Let $X$ be some measure space, and $Y=\\{u_{i}\\}_{i=1}^{m}$. Assume
$c:X\times Y\to(-\infty,\infty]$ is a measurable cost function, and let $\mu$
be a probability measure supported on $\\{x\in X:\exists
i\in[m],\,\,c(x,u_{i})<\infty\\}$. Define the _Hall polytope_ associated with
$(u_{i})_{i=1}^{m}$ and $\mu$ by

$P=P((u_{i})_{i=1}^{m},\mu)=\bigcap_{I\subset[m]}\\{\alpha\in\Delta_{m}:\sum_{i\in
I}\alpha_{i}\leq\mu(A_{I})\\},$

where

$A_{I}:=\\{x\in X:\ \exists i\in I\ c(x,u_{i})<\infty\\}.$

Note that the definition implies that $\mu$ and
$\nu=\sum_{i=1}^{m}\alpha_{i}\mathbbm{1}_{u_{i}}$ are $c$-compatible if and
only if $\alpha\in P((u_{i})_{i=1}^{m},\mu)$.

We get back to this definition, and present a careful study of the resulting
polytopes, in Section 5.

###  3.4. Strong $c$-compatibility

We saw in Example 3.5 that $c$-compatibility is not a sufficient condition for
the existence of a finite cost plan. In fact, we will see in Example 7.2 that
there exist $c$-compatible measures which do admit a finite cost plan but not
a potential. Therefore, we consider a slight strengthening of
$c$-compatibility, which will ensure that the existence of a finite cost plan
implies the existence of a potential. We call this condition strong
$c$-compatibility, and it amounts to asking for a strict inequality in the
defining inequalities.

######  Definition 3.7.

Let $X,\,Y$ be measure spaces and $c:X\times Y\to(-\infty,\infty]$ be a
measurable cost function. We say that two probability measures
$\mu\in{\mathcal{P}}(X)$ and $\nu\in{\mathcal{P}}(Y)$ are _strongly
$c$-compatible_ if they are $c$-compatible and for any measurable $A\subset X$
with $0<\mu(A)<1$ it holds that

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

The motivation for this specific strengthening of the condition of
$c$-compatibility is twofold: First, if two measures are $c$-compatible and
not strongly $c$-compatible, this means that there exists a decomposition of
the transport problem into two sub-problems (see Section 7). Indeed, this is
quite clear from the definition: if some set $A$ of measure $\mu(A)\in(0,1)$
satisfies the equality

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

then letting $B=\\{y:\forall x\in A,\,\,c(x,y)=\infty\\}$ we see that $A$ must
be mapped to $Y\setminus B$ (and they have the same measure) and the preimage
of $B$ must be $X\setminus A$. That is, the original transport problem is in
fact decomposed into two disjoint transport problems.

Second, in the discrete setting of Section 3.3, strong $c$-compatibility
corresponds to the weight vector $\alpha$ residing in the interior of the Hall
polytope, which makes for an elegant assumption.

We stress that strong $c$-compatibility is not a necessary condition, only
$c$-compatibility is. Even if one of the measures is discrete, it could be
that the Hall polytope has an empty interior, but good transport maps,
admitting a potential, exist.

###  3.5. The geometric meaning of strong $c$-compatibility

It will be very useful to rephrase the condition of strong $c$-compatibility
in terms that are more geometric. In fact, looking back at the proof of the
symmetry of the notion of $c$-compatibility, it seems evident that we do not
need to assume an inequality $\mu(A)+\nu(\\{y:\forall x\in
A,\,\,c(x,y)=\infty\\})\leq 1$ (or a strict inequality, in the strong
$c$-compatibility assumption) for all sets $A$, and it suffices to consider
sets of the form $\\{x:\forall y\in B,\,\,c(x,y)=\infty\\}$. To make this
observation more precise, we introduce the notion of the $c$-dual of a set.

######  Definition 3.8 ($c$-duality).

Let $X,\,Y$ be two sets and let $c:X\times Y\to(-\infty,\infty]$. Fix
$t\in(-\infty,\infty]$ (which will be omitted in the notation as it is a fixed
parameter). For $K\subset X$ define the _$c$ -dual_ set of $K$ as

$K^{c}=\bigcap_{x\in K}\\{y\in Y:\,c(x,y)\geq t\\}=\\{y\in Y:\,\inf_{x\in
K}c(x,y)\geq t\\}.$

It will be convenient to assume $X=Y$ and that the cost is symmetric, and as
this is the case relevant for this note, we restrict to this case. However,
the reader will find it easy to generalize to the case where $X\neq Y$, in
which case there are two different “$c$-duality” operations, one mapping sets
in $X$ to sets in $Y$, and one mapping sets in $Y$ to sets in $X$, similarly
to the $c$-transform.

Let us point out that for the polar cost $p(x,y)=-\ln(\langle
x,y\rangle-1)_{+}$ and $t=\infty$, the set $K^{p}$ is the well known polar set
$K^{\circ}$. Indeed, we have that $\inf_{x\in K}p(x,y)=\infty$ if and only if
$\sup_{x\in K}\langle x,y\rangle\leq 1$. For the classical cost
$c(x,y)=-\langle x,y\rangle$ and $t=-1$, we also get the polarity map.

######  Remark 3.9.

If one adds the assumptions that $X$ and $Y$ are measure spaces and that the
cost is upper semi-continuous, it follows that for a fixed $x$, say, the set
$\\{y:\,c(x,y)\geq t\\}$ is closed, and hence so is $K^{c}$.

Having defined an operation on sets, let us notice some basic properties.

######  Lemma 3.10.

For every $K,L\subset X$, the following hold

  1. (i)

$K\subset(K^{c})^{c}=K^{cc}$,

  2. (ii)

if $L\subset K$ then $K^{c}\subset L^{c}$,

  3. (iii)

$K^{c}=K^{ccc}$.

###### Proof.

(i) This follows directly from the definition. If $x\in K$ and $y\in K^{c}$
then $c(x,y)\geq t$ so that $x\in K^{cc}$.

(ii) Assume that $L\subset K$, and $y\in K^{c}$, then $c(x,y)\geq t$ for all
$x\in K$ and in particular for all $x\in L$, so $y\in L^{c}$.

(iii) From (i) we know that $K\subset K^{cc}$, so from (ii) we get
$K^{c}\supset K^{ccc}$. On the other hand, applying (i) directly to $K^{c}$ we
get $K^{ccc}\subset K^{c}$, and equality is obtained. ∎

The similarity of $c$-duality to the $c$-transform is apparent. We are thus
motivated to define the $c$-class of sets, on which the $c$-duality is an
order reversing bijection. In order to avoid confusion, as we suppressed $t$
in the notation, we restrict the next definition to $t=\infty$, the case
relevant for this note.

######  Definition 3.11 ($c$-class and $c$-envelope).

Fix $t=\infty$. The $c$-class of sets consists of all closed sets $K\subset X$
such that there exists some $L\subset X$ with $K=L^{c}$. For any set $K\subset
X$ we define its $c$-envelope as the set $K^{cc}$, which is the smallest
$c$-class set containing $K$.

Let us note again that for the polar cost and $t=\infty$, the $p$-class
consists of closed convex sets containing the origin, and the $p$-envelope is
the polar convexification operation $K\mapsto K^{\circ\circ}=\overline{{\rm
conv}\\{0,K\\}}$.

Our first observation is that in Definitions 3.2 and 3.7 it is sufficient to
consider $c$-class sets, for $t=\infty$, instead of all measurable sets.

######  Lemma 3.12.

Let $c:X\times Y\to(-\infty,\infty]$ be an upper semi-continuous symmetric
cost function. Two probability measures $\mu\in{\mathcal{P}}(X)$ and
$\nu\in{\mathcal{P}}(Y)$ are $c$-compatible if and only if for every set
$K=K^{cc}\subset X$ in the $c$-class we have

$\nu(K^{c})\leq 1-\mu(K).$

They are strongly $c$-compatible if and only if in addition when
$\nu(K^{c})\neq 0,1$ we have

$\nu(K^{c})<1-\mu(K).$

###### Proof.

If $\mu$ and $\nu$ are $c$-compatible then in particular
$\nu(K^{c})\leq\mu(\\{x:\,\inf_{y\in K^{c}}c(x,y)<\infty\\})$, which can be
rewritten as $\nu(K^{c})\leq\mu(X\setminus K^{cc})=\mu(X\setminus K)$.

For the other direction let $A\subset X$ be a measurable set, and consider the
set $K=A^{cc}$. Then

$\\{y:\inf_{x\in A}c(x,y)=\infty\\}=\\{y:\forall{x\in
A}\,\,c(x,y)=\infty\\}=A^{c}=K^{c}.$

The last equality holds due to Lemma 3.10 (iii). Thus, using the condition on
$c$-class sets and Lemma 3.10 (i), we get

$\nu(A^{c})=\nu(K^{c})\leq 1-\mu(K)=1-\mu(A^{cc})\leq 1-\mu(A),$

so that $\mu$ and $\nu$ are $c$-compatible.

Similarly, two probability measures $\mu$ and $\nu$ are strongly
$c$-compatible if and only if they are $c$-compatible and for all $c$-class
sets $K\subset X$ such that $\nu(K^{c})\neq 0,1$ we have

$\nu(K^{c})<1-\mu(K).$

This follows from the same proof, the only difference being if $A\neq
A^{cc}=K$, one gets a strong inequality by $\nu(A^{c})\leq
1-\mu(A^{cc})<1-\mu(A)$, which follows by Lemma 3.10 (i). ∎

In the next lemma we show that the strong $c$-compatibility of two measures
implies a vital condition on the distribution of the transport plan between
them.

######  Lemma 3.13.

Let $\mu$ be a probability measure on $X$, $\nu$ a probability measure on $Y$,
and $\pi\in\Pi(\mu,\nu)$ a finite cost plan, with respect to the symmetric
cost $c:X\times Y\to(-\infty,\infty]$. Then $\mu$ and $\nu$ are strongly
$c$-compatible if and only if for every $c$-class set $K$ such that
$\nu(K^{c})\neq 0,1$, we have that

$\pi((X\setminus K)\times(Y\setminus K^{c}))>0.$

###### Proof.

First we note that the existence of a finite cost plan $\pi\in\Pi(\mu,\nu)$
implies $c$-compatibility (see Lemma 3.3). Thus, under our assumptions, strong
$c$-compatibility is equivalent, by Lemma 3.12, to the fact that for every
$c$-class $K$ with $\nu(K^{c})\neq 0,1$ we have that
$\nu(K^{c})<1-\mu(K)=\mu(X\setminus K)$. Since $\pi\in\Pi(\mu,\nu)$ this can
be rewritten as, for $\nu(K^{c})\neq 0,1$,

$\pi(X\times K^{c})<\pi((X\setminus K)\times Y),$

and if $\nu(K^{c})=1$ then $\mu(K)=0$. Note that as $\pi$ has finite cost, it
is concentrated on $S=\\{(x,y):c(x,y)<\infty\\}$, and so for $(x,y)$ in the
support of $\pi$, if $y\in K^{c}$ then we must have $x\not\in K$. In
particular, from the point of view of the measure $\pi$, the set on the left
hand side is contained in the set on the right hand side. We can thus rewrite
the first inequality as

$0<\pi(((X\setminus K)\times Y)\setminus(X\times K^{c}))=\pi((X\setminus
K)\times(Y\setminus K^{c})).$

completing the proof of the statement claimed. ∎

##  4\. Transportation of measure

Let us recall our main theorem, to be proved in this section.

######  Theorem 1.1.

Let $X=Y$ be a Polish space, and $c:X\times Y\to(-\infty,\infty]$ be a
continuous and symmetric cost function, essentially bounded from below with
respect to $\mu\in{\mathcal{P}}(X)$ and $\nu\in{\mathcal{P}}(Y)$. Assume
$(\mu,\nu)$ are strongly $c$-compatible, and $C(\mu,\nu)<\infty$. Then there
exists a $c$-class function $\varphi$ and an optimal transport plan
$\pi\in\Pi(\mu,\nu)$ concentrated on $\partial^{c}\varphi$.

In order to prove the theorem we will use a combination of Theorems 2.3, 2.4,
and 2.6. We will show that once we have an optimal transport plan supported on
a $c$-cyclically monotone set then it must be $c$-path-bounded. This will
follow from an observation presented in [5] which states that indeed in some
special cases $c$-cyclic monotonicity implies $c$-path-boundedness. In order
to formulate the condition let us introduce some notation.

We consider a directed graph, associated with a cost function $c:X\times
Y\to(-\infty,\infty]$ and a set $G\subset S=\\{(x,y):c(x,y)<\infty\\}\subset
X\times Y$, in which the vertices are elements of $G$ and there is a directed
edge from $(x,y)$ to $(z,w)$ if $c(z,y)<\infty$. Since $G\subset S$ we may say
that for every point in $G$ there is an edge (loop) with this point as a start
and end vertex.

The directed graph induces a (transitive) relation on points in $G$, namely
$(x,y)\prec(z,w)$ if there is a directed path from $(x,y)$ to $(z,w)$. We then
define an equivalence relation $\sim$ on elements of $G$ where we say that
$(x,y)\sim(z,w)$ if $(x,y)\prec(z,w)$ and $(z,w)\prec(x,y)$, i.e. there is a
directed cycle passing through both points. To the best of our knowledge, this
equivalence relation was first mentioned in [23, Chapter 5, p.75] and studied
in [9, 8, 5]. The following proposition was proved (with a different
formulation) in [8] and then in [5].

######  Proposition 4.1.

Let $c:X\times Y\to(-\infty,\infty]$ be some cost function and let $G\subset
X\times Y$ be a $c$-cyclically monotone set. Assume that all points in $G$
belong to one equivalence class of the equivalence relation $\sim$ defined
above. Then $G$ is $c$-path-bounded.

With this proposition in hand, our goal is to show that if $\pi$ is a finite
cost plan between two strongly $c$-compatible measures, then we can find a set
$G$, on which $\pi$ is concentrated, such that all of points in $G$ are in one
equivalence class of $\sim$.

######  Proposition 4.2.

Let $X,\,Y$ be two Polish spaces,
$\mu\in{\mathcal{P}}(X),\nu\in{\mathcal{P}}(Y)$ and assume $(\mu,\nu)$ are
strongly $c$-compatible. Let $\pi\in\Pi(\mu,\nu)$ be a finite cost transport
plan from $\mu$ to $\nu$. Then there exists a set $G$ on which $\pi$ is
concentrated such that all the points in $G$ are in one equivalence class of
$\sim$.

###### Proof.

Let $G_{1}$ denote the support of $\pi$, and let $G_{0}$ denote the set
$G_{1}\cap\\{(x,y)\in X\times Y:c(x,y)<\infty\\}$. Fix a point $(x,y)\in
G_{0}$. We shall show that the set of points $(z,w)\prec(x,y)$ in $G_{0}$ is
of $\pi$-measure one, as is the set of points $(z,w)$ such that
$(x,y)\prec(z,w)$. The intersection of these two sets will also be of measure
one, and we denote it by $G$. We will then explain why this $G$ fulfills the
requirements of the proposition.

Consider $H\subset G_{0}$ consisting of all points $(a,b)\prec(x,y)$. Assume
towards a contradiction that $\pi(H)<1$. Note that $\pi(H)>0$ since $(x,y)\in
S_{0}$ and in the support of $\pi$, so that for any neighborhood $U$ of
$(x,y)$ we have $\pi(U)>0$. Picking a small enough neighborhood $U$, we know
that if $(z,w)\in U$ then $c(z,y)<\infty$ and so $(z,w)\in H$ (it may be that
$\pi(x,y)>0$ and that $U$ consists of this one point alone).

Since $\pi(H)<1$ there is some $(z,w)\not\in H$ which is a density point of
$\pi$, that is, for any neighborhood $V$ of $(z,w)$ one has $\pi(V)>0$.

If $z\in(P_{X}H)^{cc}$ then $(P_{X}H)^{c}=(P_{X}H)^{ccc}\subset\\{z\\}^{c}$ by
Lemma 3.10 (ii) and (iii). Therefore $Y\setminus\\{z\\}^{c}\subset
Y\setminus(P_{X}H)^{c}=\\{v:\,\exists u\in P_{X}H,\,\,c(u,v)<\infty\\}$.
Further, since $(z,w)\in G$ we have that $c(z,w)<\infty$ and hence $w\in
Y\setminus\\{z\\}^{c}$. But this means that $w\in Y\setminus(P_{X}H)^{c}$ and
there exists some $a\in P_{X}H$ (and $b$ such that $(a,b)\in G_{0}$) with
$c(a,w)<\infty$. Therefore $(z,w)\prec(a,b)$, and by transitivity
$(z,w)\prec(x,y)$, a contradiction.

We may therefore assume that $(z,w)$ is such that $z\notin(P_{X}H)^{cc}=:K$.
Since $K$ is a closed set in $X$, there is a neighborhood of $z$ which does
not intersect $K$, and therefore we can find a neighborhood $V$ of $(z,w)$
which is of positive $\pi$ measure (as $(z,w)$ is a density point) and such
that its projection onto $X$ does not intersect $K$. Note that this implies in
particular that $0<\mu(K)=\pi(K\times Y)<1$, since $H\subset K\times Y$ and
$V\cap(K\times Y)=\emptyset$. We may therefore use Lemma 3.13 to deduce that

$\pi((X\setminus K)\times(Y\setminus K^{c}))>0.$

In particular there exists some point $(e,f)\in G_{0}$ Such that $e\not\in K$
and $f\not\in K^{c}$. The fact that $e\not\in K$ means in particular that
$(e,f)\not\in H$. The fact that $f\not\in K^{c}=(P_{X}H)^{ccc}=(P_{X}H)^{c}$
implies that $f\in\\{v:\,\exists u\in P_{X}H\,c(u,v)<\infty\\}$. Hence there
is some point $a\in P_{X}H$ (and $b$ such that $(a,b)\in H$) such that
$c(a,f)<\infty$, which means that $(e,f)\prec(a,b)\prec(x,y)$, thus
contradicting the fact that $(e,f)\not\in H$. We conclude that the set $H$
satisfies $\pi(H)=1$.

Similarly we consider $F\subset G_{0}$ consisting of all points $(a,b)$ such
that $(x,y)\prec(a,b)$. Using the same argument as above we get that
$\pi(F)=1$.

Hence, we found sets $F$ and $H$ of $\pi$-measure one. Let $G=F\cap H$, every
point $(z,w)\in G$ satisfies that there is a directed path, going through
points in $G_{0}$, between it and $(x,y)$. We now claim that these directed
paths only go through points in $G$ itself. Indeed, consider a cycle (in
$G_{0}$) which includes $(x,y)$ and $(z,w)\in G$. The existence of this cycle
implies that every point on it belongs to both $H$ and $F$, by the definition
of the relation $\sim$, so that the whole cycle consists of points in $G$. The
proof is now complete.

∎

###### Proof of Theorem 1.1.

By assumption, $C(\mu,\nu)<\infty$, and we may use Theorem 2.4, the
assumptions of which are satisfied, to find a $c$-optimal plan
$\pi\in\Pi(\mu,\nu)$. By Theorem 2.6, the plan $\pi$ is concentrated on some
$c$-cyclically monotone set $G_{1}$. Proposition 4.2 implies that $\pi$ is
also concentrated on some set $G_{2}$ such that all points in $G_{2}$ are in
one equivalence class of the relation $\sim$ defined above. Let $G=G_{1}\cap
G_{2}$, then $G$ is a $c$-cyclically monotone set such that all of its
elements lie in one equivalence class, therefore, by Proposition 4.1 the set
$G$ is $c$-path-bounded. Finally, we use Theorem 2.3 which implies that a
$c$-path-bounded set admits a potential, to find some $c$-class function
$\varphi$ such that $G\subset\partial^{c}\varphi$.

We have thus determined that there exists a $c$-optimal plan $\pi$ which is
concentrated on $\partial^{c}\varphi$ for some $c$-class $\varphi$, as needed.
∎

##  5\. Transportation to a discrete measure

In this section we present a different approach to the problem of finding
transport maps which lie on $c$-subgradients of functions. We consider the
case where one measure is arbitrary (we will add some mild assumptions on it,
connected with the cost, later on) and the second measure is discrete. As
explained in Section 3.3, fixing the support of $\nu$ to be the set
$\\{y_{i}\\}_{i=1}^{m}$, a necessary condition for the existence of a finite
cost plan $\pi\in\Pi(\mu,\nu)$ is that the weight vector $\alpha\in\Delta_{m}$
associated with the probability measure
$\nu=\sum_{i=1}^{m}\alpha_{i}\mathbbm{1}_{u_{i}}$ lies in the Hall polytope

$P=P((u_{i})_{i=1}^{m},\mu)=\bigcap_{I\subset[m]}\\{\alpha\in\Delta_{m}:\sum_{i\in
I}\alpha_{i}\leq\mu(A_{I})\\},$

where

$A_{I}:=\\{x\in X:\ \min_{i}c(x,u_{i})<\infty\\}.$

So, our main objective is to show that indeed, for a measure $\nu$
corresponding to a weight vector in the polytope, a finite cost transport plan
exists, and further, it is supported on the $c$-subgradient of some $c$-class
function. We are able to do this under very general assumptions on the measure
$\mu$, and provided $\alpha$ lies in the interior of the polytope (this is
Theorem 1.3). Let us introduce the notion of $c$-regularity of a measure,
which will be important for the construction given in this section. Roughly
speaking, a measure is $c$-regular if it gives $0$-measure to sets where two
different basic functions $c(\cdot,y_{1})+a_{1}$ and $c(\cdot,y_{0})+a_{0}$,
coincide and equal some finite number.

######  Definition 5.1.

Let $X,\,Y$ be measure spaces and let $c:X\times Y\to(-\infty,\infty]$ be a
measurable cost function, and $\mu$ a probability measure on $X$. If for any
$y_{1}\neq y_{0}\in Y$ and $t\in\mathbb{R}$

$\mu(\\{c(z,y_{1})-c(z,y_{0})=t\\})=0,$

then we say that $\mu$ is a _$c$ -regular measure_.

For example, when the cost is such that $\\{z:c(z,y_{1})-c(z,y_{0})=t\\}$ is
of lower dimension, and the measure is absolutely continuous, the
$c$-regularity property is satisfied.

###  5.1. Building transport maps

The idea of the proof is to manually construct functions whose $c$-subgradient
is a transport map of a $c$-regular measure $\mu$ to a certain discrete
measure $\nu$. We will consider basic functions and use the fact that the
$c$-class is closed under the pointwise infimum. Formally, we have the
following lemma.

######  Lemma 5.2.

Let $X,\,Y$ be measure spaces and let $c:X\times Y\to(-\infty,\infty]$ be a
measurable cost function. Fix a set of vectors $(u_{i})_{i=1}^{m}\subset Y$
and let $\mu$ be a $c$-regular probability measure on $X$, which is supported
on the set $\\{x\in X:\exists i\in[m]{\rm~{}with~{}}c(x,u_{i})<\infty\\}$.
Given numbers $(t_{i})_{i=1}^{m}\subset\mathbb{R}$ let

$\varphi(x)=\varphi_{(u_{i}),(t_{i})}(x)=\min_{1\leq i\leq
m}\left(c(x,u_{i})+t_{i}\right)$

be a function in the $c$-class and denote $U_{i}=\left\\{x\in X:\
\arg\min_{1\leq j\leq m}\left(c(x,u_{j})+t_{j}\right)=i\right\\}$. Then the
mapping $T$, defined to be equal to $u_{i}$ on the set $U_{i}$, is well
defined $\mu$-almost everywhere and satisfies that
$T(x)\in\partial^{c}\varphi(x)$ for all $x$ in the support of $\mu$. Moreover,
it transports $\mu$ to the measure
$\nu=\sum_{i=1}^{m}\alpha_{i}\mathbbm{1}_{u_{i}}$ on $Y$, where
$\alpha_{i}=\mu\left(U_{i}\right).$

###### Proof.

Let $\varphi(x)$ be the function defined in the statement and note that it
induces a partition of $X$ into $m$ sets $\\{U_{i}\\}_{i=1}^{m}$, where

$U_{i}=\\{x\in X:\ \arg\min_{1\leq j\leq
m}\left(c(x,u_{j})+t_{j}\right)=i\\}.$

By the definition of the $c$-subgradient given in (7),
$u_{i}\in\partial^{c}\varphi(x)$ for all $x\in U_{i}$. Let $T:X\to Y$ be the
map given by $T(x)=u_{i}$ for all $x\in U_{i}$, so indeed
$T(x)\in\partial^{c}\varphi(x)$. For $\mu$ which is $c$-regular, the
intersections of the sets $U_{i}$ are of zero measure and thus $T$ is well
defined $\mu$ almost everywhere.

Clearly, the map $T$ transports the measure $\mu$ on $X$ to the measure
$\sum_{i=1}^{m}\mu(U_{i})\mathbbm{1}_{u_{i}}$. ∎

######  Remarks 5.3.

(i) In general, the partition to sets $\\{U_{i}\\}$ as above is not disjoint,
so without the additional assumption of $c$-regularity of $\mu$ the map $T$ is
not well-defined.

(ii) Since we may add a constant to all $(t_{i})_{i=1}^{m}$ without changing
the $c$-subgradient, we will assume that $t_{i}\geq 0$. Thus, given a finite
set $(u_{i})_{i=1}^{m}\subset Y$, it will be convenient for us to consider the
family of functions

$\varphi(x)=\min_{1\leq i\leq m}\left(c(x,u_{i})-\ln(t_{i})\right),$

with $t=(t_{i})_{i=1}^{m}$ in the $m$-dimensional simplex $\Delta_{m}$.

Lemma 5.2 guarantees that given a $c$-regular measure $\mu$ and points
$(u_{i})_{i=1}^{m}\subset Y$, the map $\varphi_{(u_{i}),(t_{i})}$ induces a
transport map $T:X\to Y$ mapping $\mu$ to $\sum\alpha_{i}\mathbbm{1}_{u_{i}}$.
This simple idea will be very important in proving Theorem 1.3, and the bulk
of the proof lies in analyzing which weights $\alpha_{i}$ can be attained. In
the classical case of the quadratic cost it was proved by K. Ball that all
weight vectors $\alpha=(\alpha_{i})_{i=1}^{m}\in\Delta_{m}$ can be attained
[6], from which he then obtained the Brenier theorem for all absolutely
continuous measures $\mu$ and compactly supported $\nu$ using a limiting
argument.

In contrast, in the case of non-traditional costs one cannot expect that all
weight vectors in $\Delta_{m}$ will be attained, only those residing in the
Hall polytope. Let us briefly describe the main steps for proving the
existence of a transport map of some measure $\mu$ to a discrete measure $\nu$
with weight vector in the interior of the Hall polytope (i.e. Theorem 1.3).
Fixing a measure $\mu$ and an $m$-tuple $(u_{i})_{i=1}^{m}$, the construction
in Lemma 5.2 gives rise to a mapping $H$ from the $(m-1)$-dimensional simplex
$\Delta_{m}$ onto the set of ‘weight vectors’ $\alpha=(\alpha_{i})_{i=1}^{m}$
of the measure $\nu$ to which $\mu$ can be transported. We will show that $H$
is a surjection from the interior of the simplex onto the interior of the
relevant Hall polytope. To this end we define and analyze Hall polytopes, and
in particular construct, under some assumptions, a continuous map $R$ from the
boundary of the polytope to the boundary of the simplex, which respects
certain constraints connected with the face structure of the polytope. We use
a variant of Brouwer’s fixed point theorem for the composition $R\circ p\circ
H$, where $p$ is a radial projection from some point in the polytope, to
obtain the surjectivity.

###  5.2. Structure of the Hall Polytope

We introduce the following notation: For $I\subset[m]$,
$A\subset\mathbb{R}^{|I|}$ and $B\subset\mathbb{R}^{m-|I|}$, we denote by
$A\times_{I}B$ points in $\mathbb{R}^{m}$ with $I$-coordinates in $A$ and
$I^{c}$-coordinates in $B$. For a measure $\mu$ and a set $A\subset X$ we
denote by $\mu|_{A}$ the measure that is equal to $\mu$ on $A$ and zero on
$A^{c}$.

Hall polytopes have faces only in specific pre-determined directions. (Their
faces’ normal cones are spanned by $\\{0,1\\}$-vectors in $\mathbb{R}^{m}$,
projected onto the span of the polytope which is $(m-1)$ -dimensional.) As we
shall see in Proposition 5.4, each of these faces has a product structure, of
which each component is a Hall polytope itself.

######  Proposition 5.4.

Let $P=P((u_{i})_{i=1}^{m},\mu)$ be the Hall polytope associated with some
$m$-tuple $(u_{i})_{i=1}^{m}\subset Y$ and a probability measure
$\mu\in{\mathcal{P}}(X)$ supported on $\\{x\in X:\exists i\in[m]\
c(x,u_{i})<\infty\\}$. Then for each $I\subset[m]$, the face of $P$ given by

(10) $\displaystyle F_{I}=\\{\alpha\in P:\sum_{I}\alpha_{i}=\mu(A_{I})\\},$

admits a splitting $F_{I}=\mu(A_{I})P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$
where $P_{I}$ is the Hall polytope associated with the measure
$\frac{1}{\mu(A_{I})}\mu|_{A_{I}}$ and the vectors $\\{u_{i}\\}_{i\in I}$, and
$\hat{P}_{I}$ is the Hall polytope associated with the measure
$\frac{1}{\mu(A_{I}^{c})}\mu|_{A_{I}^{c}}$ and the vectors
$\\{u_{i}\\}_{i\in[m]\setminus I}$. In particular, in case $\mu(A_{I})=0$, we
have $P_{I}=\\{0\\}_{I}$, and in case $\mu(A_{I}^{c})=0$,
$\hat{P}_{I}=\\{0\\}_{[m]\setminus I}$.

###### Proof.

Let $\alpha\in F_{I}$, then by the definition of $F_{I}$ we have $\sum_{i\in
I}\alpha_{i}=\mu(A_{I})$ and thus $\alpha|_{I}\in\mu(A_{I})\Delta_{|I|}$.
Furthermore, for every $J\subset I$ it still holds that $\sum_{i\in
J}\alpha_{i}\leq\mu(A_{J})$ and as $A_{J}\subset A_{I}$ we also get that
$\sum_{i\in J}\alpha_{i}\leq\mu|_{A_{I}}(A_{J})$. Recall that $P_{I}$ is the
Hall polytope associated with $(u_{i})_{i\in I}$ and
$\mu(A_{I})^{-1}\mu|_{A_{I}}$, so re-normalizing the previous inequalities by
$\mu(A_{I})$ we see that the vector $\alpha|_{I}\in\mu(A_{I})P_{I}$, as
claimed.

Similarly in the $I^{c}$ coordinates, $\alpha\in F_{I}$ satisfies
$\sum_{i\in[m]\setminus I}\alpha_{i}=\mu(A_{I}^{c})$. To show
$\alpha|_{[m]\setminus I}\in\mu(A_{I}^{c})\hat{P}_{I}$ we need to check that
for every $K\subset[m]\setminus I$ we have $\sum_{i\in
K}\alpha_{i}\leq\mu(A_{K}\cap A_{I}^{c})$. To this end consider the new subset
of $[m]$ given by $J=I\cup K$. By the assumptions,

$\sum_{i\in J}\alpha_{i}\leq\mu(A_{J})=\mu\big{(}\bigcup_{i\in I}\\{x:\
c(x,u_{i})<\infty\\}\cup\bigcup_{i\in K}\\{x:\ c(x,u_{i})<\infty\\}\big{)}.$

Since the first of these unions is in fact all of $A_{I}$, we may rewrite the
inequality as

$\sum_{i\in J}\alpha_{i}\leq\mu(A_{I})+\mu(A_{I}^{c}\cap\bigcup_{i\in K}\\{x:\
c(x,u_{i})<\infty\\}).$

The sum on the left hand side is simply $\sum_{i\in I}\alpha_{i}+\sum_{i\in
K}\alpha_{i}=\mu(A_{I})+\sum_{i\in K}\alpha_{i}$, since we have assumed
$\alpha\in F_{I}$. Plugging into the inequality and canceling, we see

$\sum_{i\in K}\alpha_{i}\leq\mu(A_{I}^{c}\cap\bigcup_{i\in K}\\{x:\
c(x,u_{i})<\infty\\}),$

as claimed.

We have thus shown, so far, that
$F_{I}\subset\mu(A_{I})P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$. For the
opposite direction, assume we are given some point
$\alpha\in\mu(A_{I})P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$, and we want to
show that it belongs to $F_{I}$. Clearly, using that if $K\subset J$ then
$A_{K}\subset A_{J}$, we have for any $J\subset[m]$ that

$\displaystyle\sum_{i\in J}\alpha_{i}$ $\displaystyle=$
$\displaystyle\sum_{i\in J\cap I}\alpha_{i}+\sum_{i\in J\cap([m]\setminus
I)}\alpha_{i}\leq\mu|_{A_{I}}(A_{J\cap
I})+\mu|_{A_{I}^{c}}(A_{J\cap([m]\setminus I)})$ $\displaystyle\leq$
$\displaystyle\mu|_{A_{I}}(A_{J})+\mu|_{A_{I}^{c}}(A_{J})=\mu(A_{J}).$

This completes the second part of the proof. ∎

We will discuss the facial structure of the polytope, and make use of the
following simple observation.

######  Lemma 5.5.

Under the conditions and notations of Lemma 5.4, for any $I\subset[m]$, the
part of the boundary of $F_{I}$ given by $\mu(A_{I})\partial
P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$ is a subset of $\cup_{J\subsetneq
I}F_{J}$.

###### Proof.

The boundary of $P_{I}$ consists of points whose $I^{th}$ coordinates add up
to one, and for some $J\subsetneq I$ one of the inequalities defining the Hall
polytope associated with $\frac{1}{\mu(A_{I})}\mu|_{A_{I}}$ and $(u_{i})_{i\in
I}$ is an equality. In other words, if $\alpha\in\mu(A_{I})\partial
P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$ there is some $J\subsetneq I$ such
that $\sum_{i\in J}\alpha_{i}=\mu(A_{J})$, which means $\alpha\in F_{J}$, as
claimed. ∎

###  5.3. Non-degenerate polytopes

In this subsection we continue analyzing properties of Hall polytopes, under
an additional assumption on $\mu$ and $(\alpha_{i})_{i=1}^{m}$ which will
imply that all of the Hall polytopes’ faces $F_{I}$ (defined in (10)) are
‘full dimensional’ in the $I$ coordinates, i.e. that in the splitting
described in Proposition 5.4, the polytope $P_{I}$ is $|I|-1$ dimensional.

######  Definition 5.6.

Let $X,Y$ be measure spaces and let $c:X\times Y\to(-\infty,\infty]$ be a
measurable cost function. Given $(u_{i})_{i=1}^{m}\subset Y$, and a
probability measure $\mu$ which is supported on $\\{x\in X:\exists i\in[m]\
c(x,u_{i})<\infty\\}$, we say that $\mu$ is _non-degenerate with respect to
$(u_{i})_{i=1}^{m}$_ if for every $1\leq i<j\leq m$ it holds that

$\mu\left(\\{x:c(x,u_{i})<\infty\\}\cap\\{x:c(x,u_{j})<\infty\\}\right)>0.$

(a) Non-degenerate

(b) Non-degenerate

(c) Degenerate

Figure 2. Examples of 3-dimensional Hall polytopes

######  Proposition 5.7.

Given a probability measure $\mu\in{\mathcal{P}}(X)$, which is non-degenerate
with respect to $(u_{i})_{i=1}^{m}\subset Y$, the Hall polytope
$P=P((u_{i})_{i=1}^{m},\mu)$ satisfies that its dimension (meaning the
dimension of its affine hull) is $\dim(P)=m-1$.

###### Proof.

We shall prove this fact using induction on $m$. For $m=1$ this is clearly
true since the polytope $P$ consists of one point $\alpha=1$, that is, has
dimension $0$. Assume that the claim is true for $(m-1)$-tuples. Then, for $m$
and a given set of vectors $(u_{i})_{i=1}^{m}\subset Y$, we know by
Proposition 5.4 that $P$ has faces $F_{I}$ where $I\subset[m]$, each of the
form $F_{I}=\mu(A_{I})P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$. Let
$I_{1}=[m-1]$ and $I_{2}=\\{m\\}$. The set $[m-1]$ still satisfies, along with
$\mu|_{I}$, the conditions of the proposition, so by the inductive assumption
$P_{1}=P_{I_{1}}$ is a polytope of full dimension, that is, of dimension
$m-2$.

It remains to show that $F_{2}=F_{I_{2}}$ does not lie within the affine hull
of $F_{1}$, and hence $P$ has dimension at least $m-1$ (and of course it
cannot have a higher dimension, as it is a subset of $\Delta_{m}$). Note that
the affine hull of $F_{1}$ is characterized by the equality
$\sum_{i=1}^{m-1}\alpha_{i}=\mu(A_{[m-1]})$, which equivalently can be written
as $\alpha_{m}=1-\mu(A_{[m-1]})$. The facet $F_{2}$ satisfies
$\alpha_{m}=\mu(A_{\\{m\\}})$. Assuming towards a contradiction that these two
facets do intersect, we would need to have
$\mu(A_{[m-1]})+\mu(A_{\\{m\\}})=1$. Recall that

$A_{\\{m\\}}=\\{x\in X:\ c(x,u_{m})<\infty\\},\ A_{[m-1]}=\\{x\in X:\ \exists
i\in[m-1]\ \ c(x,u_{i})<\infty\\}$

and that by the non-degeneracy of $\mu$ it holds that $\mu(A_{\\{m\\}}\cap
A_{[m-1]})>0$. Additionally, $\mu(A_{\\{m\\}}\cup A_{[m-1]})=1$, and so

$\mu(A_{\\{m\\}}\cup
A_{[m-1]})=\mu(A_{\\{m\\}})+\mu(A_{[m-1]})-\mu(A_{\\{m\\}}\cap A_{[m-1]})$

implies that $\mu(A_{\\{m\\}}\cap A_{[m-1]})=0$ (So in particular
$\mu(A_{\\{m\\}}\cap A_{\\{1\\}})=0$), contradicting the assumption that $\mu$
is non-degenerate. ∎

######  Corollary 5.8.

Given a probability measure $\mu\in{\mathcal{P}}(X)$ which is non-degenerate
with respect to $(u_{i})_{i=1}^{m}\subset Y$, the Hall polytope
$P=P((u_{i})_{i=1}^{m},\mu)$ satisfies that each face $F_{I}$ admits a
splitting $F_{I}=P_{I}\times\hat{P}_{I}$ such that $\dim(P_{I})=|I|-1$.

###### Proof.

The fact that $F_{I}$ has such a splitting was proven already in Proposition
5.4, with $P_{I}$ being the Hall polytope of the normalized restriction of the
measure $\mu$ to $A_{I}$. $\mu_{I}$ satisfies, together with the subset
$(u_{i})_{i\in I}$, conditions of Proposition 5.7, namely that it is non-
degenerate with respect to $(u_{i})_{i\in I}$ as one may easily check that
$\mu|_{A_{I}}$ is non-degenerate with respect to $(u_{i})_{i\in I}$.
Therefore, $P_{I}$ is full dimensional, as claimed. ∎

Furthermore, in this case the associated polytope satisfies a “good” face-
intersection structure, explained in the next two propositions.

######  Proposition 5.9.

Given a probability measure $\mu\in{\mathcal{P}}(X)$ supported on $\\{x\in
X:\exists i\in[m]\ c(x,u_{i})<\infty\\}$ which is non-degenerate with respect
to $(u_{i})_{i=1}^{m}\subset Y$, let $P=P((u_{i})_{i=1}^{m},\mu)$ be the
associated Hall polytope. Given $I,J\subset[m]$, the intersection $F_{I}\cap
F_{J}$ is a subset of $F_{I\cap J}$ (we let $F_{\emptyset}=P$, so that if
$I\cap J=\emptyset$ the claim is trivial).

###### Proof.

Let $\alpha\in F_{I}\cap F_{J}$, so that $\sum_{i\in I}\alpha_{i}=\mu(A_{I})$
and $\sum_{i\in[m]\setminus I}\alpha_{i}=\mu(A_{I}^{c})$, as well as
$\sum_{i\in J}\alpha_{i}=\mu(A_{J})$ and $\sum_{i\in[m]\setminus
J}\alpha_{i}=\mu(A_{J}^{c})$. Consider the following equation

$\displaystyle\sum_{i\in I\cap J}\alpha_{i}+\sum_{i\in I\cup J}\alpha_{i}$
$\displaystyle=$ $\displaystyle\sum_{i\in I}\alpha_{i}+\sum_{i\in
J}\alpha_{i}=\mu(A_{I})+\mu(A_{J})$ $\displaystyle=$
$\displaystyle\mu(A_{I}\cap A_{J})+\mu(A_{I}\cup A_{J})\geq\mu(A_{I\cap
J})+\mu(A_{I\cup J}),$

where the final inequality follows from the inclusion $A_{I\cap J}\subset
A_{I}\cap A_{J}$.

Pairing this with the fact that each of the extreme terms satisfies that

$\sum_{i\in I\cap J}\alpha_{i}\leq\mu(A_{I\cap J})\quad{\rm
and}\quad\sum_{i\in I\cup J}\alpha_{i}\leq\mu(A_{I\cup J}),$

we conclude that both of these inequalities are in fact equalities, which
implies that

$\sum_{i\in I\cap J}\alpha_{i}=\mu(A_{I\cap J}),$

so that $\alpha$ belongs to the facet $F_{I\cap J}$. ∎

In fact, if $\mu$ is non-degenerate and $I\cap J=\emptyset$, we know much
more.

######  Proposition 5.10.

Given a probability measure $\mu\in{\mathcal{P}}(X)$ supported on $\\{x\in
X:\exists i\in[m]\ c(x,u_{i})<\infty\\}$ which is non-degenerate with respect
to $(u_{i})_{i=1}^{m}\subset Y$, let $P=P((u_{i})_{i=1}^{m},\mu)$ be the
associated Hall polytope. Then given $I,J\subset[m]$, which are disjoint, the
faces $F_{I}$ and $F_{J}$ do not intersect.

###### Proof.

By non-degeneracy of $P=P((u_{i})_{i=1}^{m},\mu)$, we know that for any $I$,
the face $F_{I}=\mu(A_{I})P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$ satisfies
that $\dim(P_{I})=|I|-1$. Assume $|I|=k_{1},|J|=k_{2}$, and, towards a
contradiction, that the intersection $F_{I}\cap F_{J}$ is non-empty. Denoting
$\beta_{I}=\mu(A_{I})$ and $\beta_{J}=\mu(A_{J})$, every point $\alpha$ in the
intersection must satisfy $\sum_{i\in I}\alpha_{i}=\beta_{I}$ and $\sum_{i\in
J}\alpha_{i}=\beta_{J}$. Letting $K=I\cup J$, $\beta_{K}=\mu(A_{K})$, by the
fact that $I$ and $J$ are disjoint, we see that $\sum_{i\in
K}\alpha_{i}=\beta_{I}+\beta_{J}$, and since $\alpha$ is a point in $P$,
$\beta_{I}+\beta_{J}\leq\beta_{K}$. However, using again that $I\cap
J=\emptyset$, we know that all points $\alpha\in P$ also satisfy $\sum_{i\in
K}\alpha_{i}\leq\beta_{I}+\beta_{J}$, and since by Proposition 5.7 $F_{K}$ is
non-empty (it is full dimensional in its $I$ coordinates), there exists some
$\alpha\in F_{K}$ such that the equality $\sum_{i\in K}\alpha_{i}=\beta_{K}$
is satisfied. This implies $\beta_{K}=\beta_{I}+\beta_{J}$. We conclude that
$F_{I}\cap F_{J}=F_{K}$. Indeed, $F_{K}\subset F_{I}\cap F_{J}$, since each
such $\alpha\in P$ satisfies $\sum_{i\in I}\alpha_{i}\leq\beta_{I}$ and
$\sum_{i\in J}\alpha_{i}\leq\beta_{J}$, and for points in $F_{K}$ an equality
must be attained in both inequalities. The reverse inclusion $F_{I}\cap
F_{J}\subset F_{K}$ is clear.

However, by Proposition 5.7 the dimension of $P_{I}$ is $k_{1}-1$ and the
dimension of $P_{J}$ is $k_{2}-1$. Recalling that $K=I\cup J$, we see that the
dimension of $P_{K}$ is at most $k_{1}-1+k_{2}-1<k_{1}+k_{2}-1=|K|-1$, which
contradicts the non-degeneracy assumption on $P$, and implies that the
intersection must be empty.

∎

###  5.4. Mapping the Hall polytope to the simplex

In this subsection we make one final preparation, and show that for any Hall
polytope $P$, associated with a non-degenerate measure and some $m$-tuple,
there exists a special mapping $R$ from $\partial P$ to $\partial\Delta_{m}$
such that $F_{I}$ is mapped to $\partial_{I}\Delta_{m}$, and on $F_{I}$, the
map only depends on the $I$ coordinates of a point.

Let us explain the notation. The relative boundary of the simplex (its
boundary in the affine space $\\{\alpha\in\mathbb{R}^{m}:\
\sum_{i=1}^{m}\alpha_{i}=1\\}$) will be denoted by $\partial\Delta_{m}$, and
the $I^{\rm th}$ component of this boundary is the lower dimensional simplex
defined by

$\partial_{I}\Delta_{m}=\\{\alpha\in\Delta_{m}:\ \sum_{i\in
I}\alpha_{i}=1\\}.$

Additionally, for $I\subset[m]$ we say that ‘a point $x\in\mathbb{R}^{m}$ has
$I^{th}$ coordinates $y\in\mathbb{R}^{|I|}$’ if the restriction of $x$ to its
coordinates indexed by $I$ is equal to $y$.

######  Proposition 5.11.

Given a probability measure $\mu\in{\mathcal{P}}(X)$ supported on $\\{x\in
X:\exists i\in[m]\ c(x,u_{i})<\infty\\}$ which is non-degenerate with respect
to $(u_{i})_{i=1}^{m}\subset Y$, let $P=P((u_{i})_{i=1}^{m},\mu)$ be the
associated Hall polytope. Then there exists a continuous mapping $R:\partial
P\to\partial\Delta_{m}$ such that
$\partial_{I}P:=F_{I}=\mu(A_{I})P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$ is
mapped to $\partial_{I}\Delta_{m}$ with

(11) $R(y,z)=R(y,z^{\prime})$

for $y\in\mu(A_{I})P_{I},z,z^{\prime}\in\mu(A_{I}^{c})\hat{P}_{I}$, that is
$R(x)=R(x^{\prime})$ if $x|_{I^{c}}=x^{\prime}|_{I^{c}}$.

###### Proof.

The construction of $R$ is recursive. We define the map first only on faces
$F_{I}$ with $|I|=1$. We then assume it has been defined on faces $F_{I}$ with
$|I|<k$ and define it on $F_{I}$ with $|I|=k$. At each step we make sure the
map we construct is well defined and continuous on its domain.

We denote the center of mass of the face $\partial_{I}\Delta_{m}$ by $q_{I}$
and the center of mass of the polytope $\mu(A_{I})P_{I}$ (the $I$-th component
of $F_{I}$) by $p_{I}$. We will ensure, within the proof, that all points in
$F_{I}$ with $I^{th}$ coordinates $p_{I}$ are mapped to $q_{I}$, and that in
general the map on a face $F_{I}$ depends only on the $I^{th}$ coordinates of
the point.

The basis for the construction are thus faces $F_{I}$ of $P$ with $|I|=1$.
These are mapped to the vertices of the simplex $\Delta_{m}$, namely
$F_{\\{i\\}}\mapsto\partial_{\\{i\\}}\Delta_{m}$ (where
$\partial_{\\{i\\}}\Delta_{m}=e_{i}$). As these faces are disjoint by
Proposition 5.9, and the map $R$ is constant on each face, we conclude that it
is continuous.

For the induction step, assume we have defined $R$ on all faces $F_{J}$ with
$|J|<k$. Let $F_{I}$ be a face of $P$ with $|I|=k$. Since
$F_{I}=\mu(A_{I})P_{I}\times_{I}\mu(A_{I}^{c})\hat{P}_{I}$ by Proposition 5.4,
we have that

$\partial F_{I}=\left(\mu(A_{I}){\rm
relint}(P_{I})\times\mu(A_{I}^{c})\partial\hat{P}_{I}\right)\cup\left(\mu(A_{I})\partial
P_{I}\times\mu(A_{I}^{c})\hat{P}_{I}\right).$

Since $R$ is already defined, by assumption, on all faces $F_{J}$ for $I\neq
J\subset I$, and since $\mu(A_{I})\partial
P_{I}\times\mu(A_{I}^{c})\hat{P}_{I}\subset\bigcup_{J\subsetneqq I}F_{J}$ by
Lemma 5.5, the map $R$ is already defined on this first component of the
boundary. Furthermore, again by assumption, it is defined in such a way that
the image of $F_{J}$ is the simplex $\partial_{J}\Delta_{m}$, and that on
$F_{J}$ the map $R$ only depends on the $J^{th}$ coordinates of the point.
Note that $\bigcup_{J\subsetneqq I}\partial_{J}\Delta_{m}$ is precisely the
boundary of $\partial_{I}\Delta_{m}$. So, we essentially are given a
continuous mapping $R$ from the boundary of $P_{I}$ to the boundary of
$\partial_{I}\Delta_{m}$. We extend it by first imposing $R(p_{I},z)=q_{I}$
for the specified points $p_{I}$ and $q_{I}$ (note that $(p_{I},z)\in F_{I}$
lies in $\mu(A_{I}){\rm relint}(P_{I})$, as $P_{I}$ is full, i.e. $I-1$,
dimensional), and then extending $R$ radially for points with $I^{th}$
coordinates in $\mu(A_{I}){\rm relint}(P_{I})$. The resulting map $R$ is now
defined on all of $F_{I}$. We do this for all index sets $I$ of size $k$. The
resulting map is well defined, since by Propositions 5.9 and 5.10 the
intersections of the faces $\\{F_{I}\\}_{|I|=k}$ are included in faces $F_{J}$
with $|J|<k$. By construction $R$ is a continuous mapping that sends $F_{I}$
to $\partial_{I}\Delta_{m}$ and, on $F_{I}$, depends only on the $I^{th}$
coordinates.

∎

As we described in Subsection 5.1, the main idea of the proof of Theorem 1.3
is to show surjectivity of a map taking a potential function $\varphi$
(indexed by some variables $(t_{i})\in\Delta_{m}$) to the weight vector
$\alpha$ of the measure $\nu$ to which the $c$-subgradient
$\partial^{c}\varphi$ maps $\mu$. We present this formally in the next
subsection, where we define and analyse this map.

###  5.5. Mapping the simplex to the Hall polytope

Having fixed some $m$-tuple $(u_{i})_{i=1}^{m}\subset Y$ and a probability
measure $\mu\in{\mathcal{P}}(X)$ supported on $\\{x\in X:\exists i\in[m]\
c(x,u_{i})<\infty\\}$ and $c$-regular, we define a map on the interior of
$\Delta_{m}$, and then extend it (using converging subsequences) to a set-
valued map on the boundary.

More precisely, for $t=(t_{i})_{i=1}^{m}\in{\rm int}(\Delta_{m})$, define

(12) $H_{(u_{i})_{i=1}^{m}}^{\mu}(t)=\alpha$

with $\alpha\in\Delta_{m}$ given by

$\alpha_{i}=\mu\left(\left\\{x\in X:\ \arg\min_{1\leq j\leq
m}c(x,u_{j})-\ln(t_{j})=i\right\\}\right).$

For $t\in\partial\Delta_{m}$, we let $H_{(u_{i})_{i=1}^{m}}^{\mu}(t)$ be the
closure of the function in the usual sense, namely the set of all limit points
$\lim H_{(u_{i})_{i=1}^{m}}^{\mu}(t^{(k)})$ as $t^{(k)}\to t$ and
$t^{(k)}\in{\rm int}(\Delta_{m})$. When $\mu$ and $(u_{i})_{i=1}^{m}$ are
fixed in advance, we denote $H=H_{(u_{i})_{i=1}^{m}}^{\mu}$. By Lemma 5.2
there is a transport map from $\mu$ to
$\nu=\sum_{i}\alpha_{i}\mathbbm{1}_{u_{i}}$ when $\alpha=H(t)$ for $t\in{\rm
int}(\Delta_{m})$, and moreover the transport map’s graph is included in the
$c$-subgradient of the function $\min_{1\leq j\leq m}c(x,u_{j})-\ln(t_{j})$.
In particular, the image of $H$ is inside the $P=P((u_{i})_{i=1}^{m},\mu)$,
the associated Hall polytope.

Our first claim regards the continuity of $H$.

######  Proposition 5.12.

Let $X$ and $Y$ be measure spaces, $c:X\times Y\to(-\infty,\infty]$
measurable, let $(u_{i})_{i=1}^{m}\subset Y$, and let $\mu\in{\mathcal{P}}(X)$
be $c$-regular and supported on $\\{x\in X:\exists i\in[m]\
c(x,u_{i})<\infty\\}$. Then, the function
$H=H_{(u_{i})_{i=1}^{m}}^{\mu}:\Delta_{m}\to P((u_{i})_{i=1}^{m},\mu)$ is well
defined and continuous on ${\rm int}(\Delta_{m})$.

###### Proof.

First note that the function $H$ is well defined as $\mu$ is $c$-regular, and
the subsets

$U_{i}:=\left\\{x\in X:\ \arg\min_{1\leq j\leq
m}c(x,u_{j})-\ln(t_{j})=i\right\\}$

form a measurable partition of $X$ (the intersections are of measure $0$, as
well as the set where the minimum is $+\infty$), as in Lemma 5.2.

To show that $H$ is continuous on ${\rm int}(\Delta_{m})$, let $t\in{\rm
int}(\Delta_{m})$, $\varepsilon>0$ be fixed. We will show that then there
exists $\delta>0$ such that for all $t^{\prime}\in\Delta_{m}$ with
$\|t^{\prime}-t\|_{2}<\delta$, we have
$\|H(t^{\prime})-H(t)\|_{2}<\varepsilon$. To see this, note that the $i^{th}$
coordinate of the difference is given by $\mu(U_{i})-\mu(V_{i})$, where

$V_{i}:=\left\\{x\in X:\ \arg\min_{1\leq j\leq
m}c(x,u_{j})-\ln(t^{\prime}_{j})=i\right\\}.$

Clearly, this difference is bounded (in absolute value) by $\mu(U_{i}\triangle
V_{i})$, where $\triangle$ denotes the symmetric difference of the two sets.
To estimate the measure of the symmetric difference, when $t$ and $t^{\prime}$
are close, we use the following sets, which converge to measure $0$ sets as
$k\to\infty$.

Define for $i\in[m],k\in{\mathbb{N}}$

$U_{i}^{k}=\left\\{x\in U_{i}:\exists j\neq i,\
c(x,u_{j})-\ln(t_{j})-c(x,u_{i})+\ln(t_{i})\leq\frac{1}{k}\right\\}.$

Note that $U_{i}^{k+1}\subset U_{i}^{k}$, and as $\mu$ is finite
$\mu(U_{i}^{k})\searrow\mu(\lim_{k}U_{i}^{k})$. Moreover,
$\mu(\lim_{k}U_{i}^{k})=0$ since by $c$-regularity of $\mu$ the limit set
$\cup_{i\neq j}\\{x\in X:\ c(x,u_{j})-\ln(t_{j})-c(x,u_{i})+\ln(t_{i})=0\\}$
has zero measure. In particular, for every $i\in[m]$ there exists some $k_{i}$
such that for all $k>k_{i}$, we have $\mu(U_{i}^{k})<\varepsilon/m$. Denote
$k_{0}=\max_{i}k_{i}$, and note that for any $k\geq k_{0}$ we have
$\mu(\cup_{j=1}^{m}U_{j}^{k})<\varepsilon$ (and in particular for $k=k_{0}$).

We next claim that there exists $\delta$ such that if $t^{\prime}$ is such
that $|t^{\prime}_{i}-t_{i}|<\delta$ for all $i$, we have that $U_{i}\triangle
V_{i}\subset\cup_{j=1}^{m}U_{j}^{k_{0}}$, which completes the proof. Indeed,
we will choose $\delta$ such that if $|t-t^{\prime}|<\delta$ then
$t_{l}e^{-1/2k_{0}}\leq t_{l}^{\prime}\leq t_{l}e^{1/2k_{0}}$ for every $l$.

First consider the case $x\in U_{i}\setminus V_{i}$, and note that then there
exists $1\leq l\leq m$ such that $x\in V_{l}$ (since the sets
$(V_{l})_{l=1}^{m}$ are a partition of $X$) and hence for all $1\leq j\leq m$
we have

$c(x,u_{l})-\ln(t^{\prime}_{l})-c(x,u_{j})+\ln(t^{\prime}_{j})\leq 0.$

By taking $j=i$ and by the choice of $\delta$,

$c(x,u_{l})-\ln(t_{l})-c(x,u_{i})+\ln(t_{i})\leq\frac{1}{k_{0}},$

which yields that $x\in U_{i}^{k_{0}}$. Similarly, in the case where $x\in
V_{i}\setminus U_{i}$, there exists $1\leq l\leq m$ such that $x\in U_{l}$ and
since $x\in V_{i}$ we have that for all $1\leq j\leq m$

$c(x,u_{i})-\ln(t_{i}^{\prime})-c(x,u_{j})+\ln(t_{j}^{\prime})\leq 0.$

By taking $j=l$ and using the assumption on $\delta$, this yields

$c(x,u_{i})-\ln(t_{i})-c(x,u_{l})+\ln(t_{l})\leq\frac{1}{k_{0}},$

which implies $x\in U_{l}^{k_{0}}$, and in particular, in both cases,
$x\in\cup_{j=1}^{m}U_{j}^{k_{0}}$. Since the parameters were chosen so that
the measure of this set is at most ${\varepsilon}$, we conclude that
$\mu(U_{i}\triangle V_{i})<{\varepsilon}$, so long as $|t^{\prime}-t|<\delta$,
which completes the proof. ∎

A main feature of the map $H_{(u_{i})_{i=1}^{m}}^{\mu}$ is that it respects
the product structure on the faces of $\Delta_{m}$. More precisely, when
applied to a point on a face $\partial_{I}\Delta_{m}$, the map is usually set-
valued. The set which such a point is mapped to, however, has a specified
$I^{th}$-coordinate (given by another map of such form, associated with a
different measure), and the $I^{c}$-coordinates of points in the image span a
full Hall polytope of another associated measure – exactly the one given in
the face splitting discussed in Proposition 5.4. This is formally described in
the next proposition.

######  Proposition 5.13.

Under the assumptions of Proposition 5.12, consider some subset $I\subset[m]$
and let $t=t_{I}\times_{I}0_{I^{c}}$ be a vector with positive
$I^{th}$-coordinates. Let

$\mu_{I}=\frac{1}{\mu(A_{I})}\mu\big{|}_{A_{I}},\,\mu_{I}^{c}=\frac{1}{\mu(A_{I}^{c})}\mu\big{|}_{A_{I}^{c}}.$

Then,

$H_{(u_{i})_{i=1}^{m}}^{\mu}(t_{1},\dots,t_{m})=\mu(A_{I})H_{(u_{i})_{i\in
I}}^{\mu_{I}}\left(t_{i}\right)_{i\in
I}\times_{I}\mu(A_{I}^{c})H_{(u_{j})_{j\in
I^{c}}}^{\mu_{I}^{c}}(\Delta_{m-|I|}).$

In particular, $H_{(u_{i})_{i=1}^{m}}^{\mu}$ maps the face
$\partial_{I}\Delta_{m}$ to the face $F_{I}$ of the Hall polytope
$P((u_{i})_{i=1}^{m},\mu)$.

###### Proof of Proposition 5.13.

We show a two-way inclusion.
For the direction $\supseteq$ take a point $(\alpha_{1},\dots,\alpha_{m})$ in
the right hand side, which is of the form

$\mu(A_{I})H_{(u_{i})_{i\in I}}^{\mu_{I}}(t_{i})_{i\in
I}\times_{I}\mu(A_{I}^{c})H_{(u_{j})_{j\notin
I}}^{\mu_{I}^{c}}(s_{j})_{j\notin I}$

where $\sum_{i\in I}t_{i}=1$ and $\sum_{j\notin I}s_{j}=1$. For
$\delta\in(0,1)$ define ${t}^{\delta}\in\Delta_{m}$ in the following way

${t}^{\delta}_{i}=\begin{cases}(1-\delta)t_{i}&i\in I\\\ \delta s_{i}&i\notin
I\end{cases}$

Clearly, $t^{\delta}\to t$ as $\delta\to 0$, thus, by continuity of $H$
(Proposition 5.12), it suffices to show that

$(\alpha_{1},\dots,\alpha_{m})\in\lim_{\delta\to
0}H_{(u_{i})_{i=1}^{m}}^{\mu}({t}^{\delta}_{i})_{i=1}^{m}.$

We will show that for every $\varepsilon>0$ there exists some $\delta_{0}$
such that for every $\delta<\delta_{0}$ we have

$||(\alpha_{1},\dots,\alpha_{m})-H_{(u_{i})_{i=1}^{m}}^{\mu}({t}^{\delta})||\leq\varepsilon.$

Denote
$(\beta_{1},\dots,\beta_{m})=H_{(u_{i})_{i=1}^{m}}^{\mu}({t}^{\delta})$. Let
us reinterpret $\beta_{i}$,

$\displaystyle\beta_{i}$ $\displaystyle=$ $\displaystyle\mu(\\{x\in
X:\arg\min_{1\leq k\leq m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\})$
$\displaystyle=$ $\displaystyle\mu(\\{x\in A_{I}^{c}:\arg\min_{1\leq k\leq
m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\})$ $\displaystyle+\mu(\\{x\in A_{I}:\
\arg\min_{1\leq k\leq m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\}).$

On $A_{I}^{c}$ the minimum is attained for $k\notin I$, hence

$\displaystyle\beta_{i}$ $\displaystyle=\mu(A_{I}^{c})\mu_{I}^{c}(\\{x\in X:\
\arg\min_{1\leq k\leq m}c(x,u_{k})-\ln(\delta s_{k})=i\\})$
$\displaystyle\quad+\mu(\\{x\in A_{I}:\ \arg\min_{1\leq k\leq
m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\})$
$\displaystyle=\mu(A_{I}^{c})\mu_{I}^{c}(\\{x\in X:\ \arg\min_{1\leq k\leq
m}c(x,u_{k})-\ln(s_{k})=i\\})$ $\displaystyle\quad+\mu(\\{x\in A_{I}:\
\arg\min_{1\leq k\leq m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\}).$

Observe that the first summand is by definition equal to

(13) $\mu(A_{I}^{c})\mu_{I}^{c}(\\{x\in X:\ \arg\min_{1\leq k\leq
m}c(x,u_{k})-\ln(s_{k})=i\\})=\begin{cases}0&i\in I\\\ \alpha_{i}&i\notin
I\end{cases}.$

We first deal with the case $i\notin I$, in which (13) gives that

$\beta_{i}=\alpha_{i}+\mu(\\{x\in A_{I}:\ \arg\min_{1\leq k\leq
m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\}).$

For $x\in A_{I}$, $\arg\min_{1\leq k\leq m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i$
means, in particular, that

$c(u_{j},x)-\ln((1-\delta)t_{j})>c(u_{i},x)-\ln(\delta s_{i})$

for all $j\in I$. Since $s_{i}$ and $t_{j}$ are fixed, we can clearly find
$\delta_{0}>0$ such that for any $\delta<\delta_{0}$ the measure of such $x$’s
is arbitrarily small. Thus, we choose $\delta_{0}$ (depending on $s$ and $t$)
such that $\alpha_{i}\leq\beta_{i}\leq\alpha_{i}+\varepsilon/m$.

For the case $i\in I$,

$\displaystyle\beta_{i}$ $\displaystyle=\mu(\\{x\in A_{I}:\ \arg\min_{1\leq
k\leq m}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\})$ $\displaystyle\leq\mu(\\{x\in
A_{I}:\ \arg\min_{k\in I}c(x,u_{k})-\ln({t}^{\delta}_{k})=i\\})$
$\displaystyle=\mu(\\{x\in A_{I}:\ \arg\min_{k\in
I}c(x,u_{k})-\ln(1-\delta)-\ln(t_{k})=i\\})$
$\displaystyle=\mu(A_{I})\mu_{I}(\\{x\in A_{I}:\ \arg\min_{k\in
I}c(x,u_{k})-\ln(t_{k})=i\\})=\alpha_{i}.$

Thus we have $\beta_{i}\leq\alpha_{i}$. Since
$\sum_{i=1}^{m}\beta_{i}=1=\sum_{i=1}^{m}\alpha_{i}$, and
$\alpha_{i}\leq\beta_{i}\leq\alpha_{i}+\varepsilon/m$ when $i\notin I$, we see
that

$\sum_{i\in I}\alpha_{i}-\varepsilon\leq 1-\sum_{j\notin
I}(\alpha_{j}+\varepsilon/m)\leq\sum_{i\in I}\beta_{i}\leq\sum_{i\in
I}\alpha_{i}$

and we conclude $\beta_{i}>\alpha_{i}-\varepsilon$ for $i\in I$.

So far we have shown that for any $1\leq i\leq m$, we have

$\alpha_{i}-\varepsilon\leq\beta_{i}\leq\alpha_{i}+\varepsilon,$

which completes the proof of the first inclusion.

We proceed to show the second inclusion $\subseteq$. Let $\alpha\in
H_{(u_{i})}^{\mu}(t)$ for $t=t_{I}\times_{I}\\{0_{I^{c}}\\}$. By the
definition of $H$ on the boundary of the simplex, there exists a sequence

$(t_{1}^{(k)},\dots,t_{m}^{(k)})=t^{(k)}\to t=(t_{1},\dots,t_{m})$

with $t^{(k)}\in{\rm int}(\Delta_{m})$, and

$H^{\mu}_{(u_{i})_{i=1}^{m}}(t^{(k)})\to\alpha.$

In particular $\sum_{i\in I}t_{i}^{(k)}\to 1$ and $\sum_{j\notin
I}t_{j}^{(k)}\to 0$. Note that for $x\in A_{I}$, as $k\to\infty$, the minimum
in the definition will be attained (from some $k_{0}$ onwards) on an index
$i\in I$. Therefore

$\sum_{j\in I}\alpha_{j}\leftarrow\sum_{j\in
I}(H_{(u_{i})_{i=1}^{m}}^{\mu}(t_{i}^{(k)}))_{j}=\mu(x\in X:\arg\min_{1\leq
i\leq m}c(x,u_{i})-\ln(t_{i}^{(k)})\in I)\rightarrow\mu(A_{I})$

(limits with respect to $k\to\infty$), which implies $\sum_{i\in
I}\alpha_{i}=\mu(A_{I})$ and thus $\sum_{j\notin I}\alpha_{j}=\mu(A_{I}^{c})$.

Set ${t^{\prime}}_{i}^{(k)}=\frac{t_{i}^{(k)}}{\sum_{j\in I}t_{j}^{(k)}}$ for
$i\in I$. It is well defined (for large enough $k$, as $\sum_{j\in
I}t_{j}=1$), and its limit is clearly
${t^{\prime}}_{i}=\frac{t_{i}}{\sum_{j\in I}t_{j}}$. Hence,

$\displaystyle H^{\mu_{I}}_{(u_{i})_{i\in I}}(t^{\prime}_{i})$
$\displaystyle=(\mu_{I}(\\{x\in X:\ \arg\inf_{k\in
I}c(x,u_{k})-\ln(t^{\prime}_{k})=i\\}))_{i\in I}$
$\displaystyle=(\frac{1}{\mu(A_{I})}\mu(\\{x\in A_{I}:\ \arg\min_{k\in
I}c(x,u_{k})-\ln(t^{\prime}_{k})=i\\}))_{i\in I}$
$\displaystyle=(\frac{1}{\mu(A_{I})}\mu(\\{x\in X:\ \arg\min_{k\in
I}c(x,u_{k})-\ln(t_{k})=i\\}))_{i\in I}=\frac{1}{\mu(A_{I})}(\alpha_{i})_{i\in
I}.$

In the second to last step we used again the fact that the minimum can be
attained at $i\in I$ only if $x\in A_{I}$. Thus,

$(\alpha_{i})_{i\in I}\in\mu(A_{I})H^{\mu_{I}}_{(u_{i})_{i\in
I}}\left(\frac{t_{i}}{\sum_{i\in
I}t_{i}}\right)=\mu(A_{I})H^{\mu_{I}}_{(u_{i})_{i\in
I}}\left((t_{i}\right)_{i\in I}).$

Setting ${t^{\prime\prime}}_{i}^{(k)}=\frac{t_{i}^{(k)}}{\sum_{j\notin
I}{t}_{j}^{(k)}}$ for $i\notin I$, the sequence
$({t^{\prime\prime}}_{i}^{(k)})_{k=1}^{\infty}$ has a converging subsequence
in $\Delta_{m-|I|}$, denote this subsequence by
$({t^{\prime\prime}}_{i}^{(k_{l})})_{l=1}^{\infty}$, and its limit
$({t^{\prime\prime}}_{i})_{i\notin I}$. Once again, by the same argument as
above, the image of this point under the map $H$ corresponding to
$\mu_{I}^{c}$ is exactly

$H_{(u_{i})_{i\notin
I}}^{\mu_{I}^{c}}(t^{\prime\prime}_{j})=\frac{1}{\mu(A_{I}^{c})}(\alpha_{j})_{j\notin
I}.$

∎

###  5.6. Transporting a non-degenerate measure to a discrete measure

We proceed to the proof of the following theorem, which is a version of
Theorem 1.3, with an extra non-degeneracy assumption of $\mu$ (recall
Definition 5.6).

######  Theorem 5.14.

Let $X$ and $Y$ be measure spaces, $c:X\times Y\to(-\infty,\infty]$
measurable, fix $(u_{i})_{i=1}^{m}\subset Y$ and let $\mu\in{\mathcal{P}}(X)$
be $c$-regular and supported on $\\{x\in X:\exists i\in[m]\
c(x,u_{i})<\infty\\}$. Assume, in addition, that $\mu$ is non-degenerate with
respect to $(u_{i})_{i=1}^{m}$. Then, the mapping
$H_{(u_{i})_{i=1}^{m}}^{\mu}:{\rm
int}(\Delta_{m})\to(P((u_{i})_{i=1}^{m},\mu))$ covers the set ${\rm
int}(P((u_{i})_{i=1}^{m},\mu))$, that is, for any $\alpha\in{\rm
int}(P((u_{i})_{i=1}^{m},\mu)))$ there exists some $t\in{\rm int}(\Delta_{m})$
such that $H_{(u_{i})_{i=1}^{m}}^{\mu}(t)=\alpha$.

###### Proof.

Denote $H=H_{(u_{i})_{i=1}^{m}}^{\mu}$ and $P=P((u_{i})_{i=1}^{m},\mu)$. By
the non-degeneracy assumption, $P$ is full dimensional, and in particular has
non-empty interior. If the image of $H$ did not cover the interior of $P$,
there would be some $\alpha\in{\rm int}P$ such that $H(t)\neq\alpha$ for all
$t\in{\rm int}(\Delta_{m})$. We use $\alpha$ to define the radial projection
$p$ of $P\setminus\\{\alpha\\}$ to its boundary. It follows that $p\circ H$ is
well defined and continuous. We then use the function $R$ as given in
Proposition 5.11 to map the boundary of $P$ to the boundary of the simplex.
Since $H(\partial_{I}\Delta_{m})\subset F_{I}$ we see that $R\circ p\circ H$
is a mapping from the simplex to its boundary which maps the $I^{th}$ facet to
itself.

Note that this composition map is a well defined function, i.e. a point-valued
map: It is clearly point-valued on ${\rm{int}}(\Delta_{m})$. Let
$t\in\partial\Delta_{m}$, and take the minimal $I$ (with respect to inclusion)
such that $t\in\partial_{I}\Delta_{m}$. Then, the coordinates $t_{I}$ are all
non-zero, and by Proposition 5.13 points in the set $H(t)$ differ only on
their $I^{c}$ coordinates. Again by Proposition 5.13, $H(t)\in
F_{I}\subset\partial P$, so $p(H(t))=H(t)$. Further, since the map $R$ depends
only on the $I$ coordinates of $H(t)$ (as $H(t)\in F_{I}$), we conclude that
the set $H(t)$ is mapped to a single point, and thus $R\circ p\circ H$ is
point-valued.

Next we claim that the composition $R\circ p\circ H$ is a continuous function
on $\Delta_{m}$. For points in the interior of $\partial\Delta_{m}$ this
follows from the fact that all three maps are continuous (see Propositions
5.12 and 5.11). We proceed to explain why the composition is continuous on the
boundary. Let $t=t_{I}\times_{I}0_{I^{c}}$ be some boundary point, with
$t_{i}>0$ for $i\in I$ (so, $t\in{\rm relint}(\partial_{I}\Delta_{m})$).
Consider a sequence $t^{(k)}\to t$ with $(R\circ p\circ H)(t^{(k)})$
converging to some vector $s$ on the boundary of the simplex. We need to show
that $s=(R\circ p\circ H)(t)$. By the definition of $H$ on boundary points,
and the continuity of $p$ and $R$, we may without loss of generality assume
$t^{(k)}\in{\rm int}(\Delta_{m})$. Indeed, for any
$t^{\prime}\in\partial\Delta_{m}$, $y\in H(t^{\prime})$ and any
${\varepsilon}>0$, there is some $t^{\prime}_{\varepsilon}\in{\rm
int}(\Delta_{m})$ with
$\left|y-H(t^{\prime}_{\varepsilon})\right|<{\varepsilon}$, so given any
sequence $t^{(k)}\to t$ with $(R\circ p\circ H)(t^{(k)})$ converging to $s$ we
can construct a sequence in the interior, converging to $t$, whose image under
$R\circ p\circ H$ converges to the same $s$. By definition of $H$, all
accumulation points of the sequence $H(t^{(k)})$ belong to $H(t)$. By
continuity of $R\circ p$, we conclude that all accumulation points of $R\circ
p\circ H(t^{(k)})$ (which we have assumed converge to the point $s$) belong to
$(R\circ p)(H(t))$. However, as we have already seen, $R\circ p\circ H(t)$ is
a point, and we get that $s=R\circ p\circ H(t)$.

However, there does not exist a continuous mapping from the simplex to its
boundary which preserves the facets. Indeed, this can be shown, for example,
using Brouwer’s fixed point theorem – as such a map could then be composed
with a permutation, arriving at a continuous mapping from the simplex to
itself with no fixed point. Hence, $H$ covers the interior of $P$, and for
every $\alpha\in{\rm int}(P)$ there is some preimage $t$. Moreover, this $t$
satisfies $t\in{\rm int}(\Delta_{m})$, otherwise, if $t_{i}=0$ for some set of
indices $i\in I$, then by Proposition 5.13, $H(t)\in F_{I^{c}}$, which does
not contain $\alpha$ (as $F_{I^{c}}$ is not in the interior of $P$). ∎

###  5.7. Removing the non-degeneracy condition

The only difference between Theorem 1.3 and Theorem 5.14, apart from notation,
is that in the latter we assume not only that

$\\{x\in X:c(x,u_{i})<\infty\\}\cap\\{x\in X:c(x,u_{j})<\infty\\}$

contains an open set for any $i\neq j$, but that $\mu$ is non-degenerate with
respect to the vectors $(u_{i})_{i=1}^{m}$, namely that

$\mu\left(\\{x:c(x,u_{i})<\infty\\}\cap\\{x:c(x,u_{j})<\infty\\}\right)>0.$

To remove this condition, we will use a straightforward perturbation argument,
similar to constructions used for example, by McCann [15], adding in this case
uniform measures on small disks, and taking limits. More formally, make use of
the following technical lemma.

######  Lemma 5.15.

Let $P=P((u_{i})_{i=1}^{m},\mu)$ be the Hall polytope associated with
$(u_{i})_{i=1}^{m}$ and the measure $\mu$ supported on $\\{x\in X:\exists
i\in[m]\ c(x,u_{i})<\infty\\}$, and assume $P$ is full dimensional. Further
assume that for $1\leq i<j\leq m$ the intersection

$\\{x\in X:c(x,u_{i})<\infty\\}\cap\\{x\in X:c(x,u_{j})<\infty\\}$

contains a disk, for any $i\neq j$, and let $\eta_{i,j}$ denote a uniform
measure on this disk, with the constants chosen so that
$\sum_{i<j\in[m]}\eta_{i,j}(X)=1$. For any $k\in{\mathbb{N}}$ let

$\mu_{k}=\frac{1}{k}\sum_{i<j\in[m]}\eta_{i,j}+(1-\frac{1}{k})\mu,$

and $P_{k}=P((u_{i})_{i=1}^{m},\mu_{k})$ the associated Hall polytope. Then,

  1. (i)

$H^{\mu_{k}}_{(u_{i})_{i=1}^{m}}\to_{k\to\infty}H^{\mu}_{(u_{i})_{i=1}^{m}}$
uniformly on $\Delta_{m}$, and

  2. (ii)

$P_{k}\to P$ as $k\to\infty$ in the Hausdorff metric.

###### Proof.

Note first that each $\mu_{k}$ is non-degenerate, so by Proposition 5.7
$P_{k}$ is full dimensional. Furthermore, we may apply Theorem 5.14, and get
that the mapping $H_{k}:=H^{\mu_{k}}_{(u_{i})_{i=1}^{m}}:{\rm
int}(\Delta_{m})\to P^{(k)}$ covers the set ${\rm int}(P^{(k)})$. Denote
$H=H^{\mu}_{(u_{i})_{i=1}^{m}}$.

For (i), let $t=(t_{1},\dots,t_{m})\in{\rm int}(\Delta^{m})$. It will be
convenient to recall the notation $U_{i}=\left\\{x\in X:\ \arg\min_{1\leq
j\leq m}c(x,u_{j})-\ln(t_{j})=i\right\\}$. The $i^{th}$ component of the
difference vector satisfies

$\displaystyle\left|\left(H_{k}(t)-H(t)\right)_{i}\right|=\left|\mu_{k}\left(U_{i}\right)-\mu\left(U_{i}\right)\right|=|\frac{1}{k}\sum_{i<j}\eta_{i,j}\left(U_{i}\right)-\frac{1}{k}\mu\left(U_{i}\right)|\leq\frac{2}{k}.$

For (ii), let $\varepsilon>0$, we will show that for all
$k>k_{0}=k(\varepsilon)$, $P_{k}\subset P+\varepsilon B_{2}^{m}$ and $P\subset
P_{k}+\varepsilon B_{2}^{m}$. For the first inclusion, let $\alpha\in{\rm
int}(P_{k})$, then since $P_{k}$ is a Hall polytope of a non-degenerate
measure, we apply Theorem 5.14 and get a point $t\in\Delta_{m}$ for which
$H_{k}(t)=\alpha$. As $H(t)\in P$, the previous assertion (i) gives
$\|\alpha-H(t)\|_{2}\leq\frac{2\sqrt{m}}{k}$, so ${\rm int}(P_{k})\subset
P+\frac{2\sqrt{m}}{k}B_{2}^{m}$ and therefore $P_{k}$ itself is also included
in the same extension of $P$. For the second inclusion, let $\alpha\in P$ and
let $\alpha^{(k)}$ be given by
$\alpha_{i}^{(k)}:=\left(1-\frac{1}{k}\right)\alpha_{i}+\frac{1}{k}\sum_{\\{j:i<j\\}}\eta_{i,j}(X)$.
We claim $\alpha^{(k)}\in P_{k}$; we check that it satisfies all of the
necessary inequalities. Clearly $\sum\alpha_{i}^{(k)}=1$, and as the support
of $\eta_{i,j}$ is a subset of $A_{\\{i\\}}\cap A_{\\{j\\}}\subset A_{I}$ for
all $i\in I$ we have

$\displaystyle\sum_{i\in I}\alpha_{i}^{(k)}$
$\displaystyle=\left(1-\frac{1}{k}\right)\sum_{i\in
I}\alpha_{i}+\frac{1}{k}\sum_{i\in
I}\sum_{\\{j:\,i<j\\}}\eta_{i,j}(X)\leq\left(1-\frac{1}{k}\right)\mu(A_{I})+\frac{1}{k}\sum_{i<j}\eta_{i,j}(A_{I})=\mu_{k}(A_{I}).$

We compute

$\|\alpha-\alpha^{(k)}\|_{2}=\left(\sum_{i=1}^{m}\frac{1}{k^{2}}(\alpha_{i}-\sum_{i\in
I}\sum_{\\{j:\,i<j\\}}\eta_{i,j}(X))^{2}\right)^{1/2}\leq\frac{2\sqrt{m}}{k}.$

Taking $k_{0}=\frac{2\sqrt{m}}{\varepsilon}$ we see that both inclusions hold.
∎

We are now set up to prove the existence of a transport map between strongly
$c$-compatible measures, one of which is discrete and the other $c$-regular.

###### Proof of Theorem 1.3.

Let $\mu$ be a $c$-regular measure on $X$ and
$\nu=\sum_{i=1}^{m}\alpha_{i}\mathbbm{1}_{u_{i}}$ a discrete measure on $Y$
which satisfy the assumptions of the theorem, and denote by
$P=P(\mu,(u_{i})_{i=1}^{m})$ the associated Hall polytope.

The condition of strong $c$-compatibility means precisely that for
$I\neq\emptyset,[m]$ we have $\sum\alpha_{i}<\mu(A_{I})$, or, in other words,
that $\alpha=(\alpha_{i})_{i=1}^{m}\in{\rm int}(P)$. In particular $P$ is non-
empty and in fact full dimensional. The conditions of Lemma 5.15 are satisfied
so we may use it to define $P_{k}$ and $H_{k}$ and find a sequence of points
$\alpha^{(k)}\in{\rm int}(P_{k})$ such that $\alpha^{(k)}\to\alpha$ as
$k\to\infty$. Take $t^{(k)}\in{\rm int}(\Delta_{m})$ such that
$H_{k}(t^{(k)})=\alpha^{(k)}$. By the compactness of $\Delta_{m}$, there
exists a converging subsequence of $t^{(k)}$, to some $t\in\Delta_{m}$, and we
denote $t^{(k)}\to t$, abusing notation slightly. We claim that $t\in{\rm
int}(\Delta_{m})$ and that $H(t)=\alpha$. Indeed,

$\displaystyle\left|H(t)-\alpha\right|$
$\displaystyle\leq\left|H(t)-H(t^{(k)})\right|+\left|H(t^{(k)})-H_{k}(t^{(k)})\right|+\left|H_{k}(t^{(k)})-\alpha^{(k)}\right|+\left|\alpha^{(k)}-\alpha\right|.$

Each of the terms tends to $0$ as $k\to\infty$: the leftmost by continuity of
$H$ (Proposition 5.12), the second by uniform convergence of $H_{k}$ to $H$,
the third term vanishes for every $k$ by choice of $t^{(k)}$, and the
rightmost by choice of the sequence $\alpha^{(k)}$. Therefore $H(t)=\alpha$.
Since $\alpha\in{\rm int}(P)$ we may use Proposition 5.13 to conclude that
$t\in{\rm int}(\Delta_{m})$.

We have thus established that $H$ is onto the interior of $P$. Recalling the
construction in Lemma 5.2, we have shown that the function

$\varphi(x)=\min_{1\leq i\leq m}(c(x,u_{i})-\ln(t_{i}))$

satisfies that its $c$-subgradient supports a transport map from $\mu$ to
$\nu$. The function $\varphi$ is therefore our desired potential. Indeed, the
map $T:X\to Y$ which maps the set $\\{x:\ \min_{1\leq j\leq
m}(c(x,u_{j})-\ln(t_{j}))=i\\}$ to $u_{i}$ for all $i\in[m]$, is a transport
map (we define $T$ on the boundary of these sets arbitrarily, as it is
$\mu$-negligible) and $(x,u_{i})\in\partial^{c}\varphi$ for $x\in U_{i}$ by
the first (and easy) part of Lemma A.2 from the appendix. ∎

##  6\. For the Polar cost: Maps versus Plans

Throughout the paper, we were careful to discuss transport plans, and not just
maps. Indeed, even in the simplest cases of discrete measures, there is no
reason for a transport map to exist, as it may require “atom splitting”, a
dangerous endeavor. Nevertheless, in the classical case, for example, when a
transport plan from some absolutely continuous measure $\mu$ to a measure
$\nu$ is concentrated on the usual subgradient of a convex function,
$\varphi\in{\rm Cvx}(\mathbb{R}^{n})$, it is easy to see that in fact one
obtains a map, not just a plan. Indeed, a convex function has a unique
subgradient almost everywhere.

For a general cost $c$ this is no longer the case, but for our main motivating
example, the polar cost $p(x,y)=-\ln(\langle x,y\rangle-1)$, a similar
argument works. Recall that for this cost the $p$-class is given by
$-\ln(\varphi)$ where $\varphi\in{\rm Cvx}_{0}(\mathbb{R}^{n})$ is a geometric
convex function, that is, a lower semi-continuous non-negative convex function
with $\varphi(0)=0$. The $p$-subgradient of the function $-\ln(\varphi)$
coincides with the polar subgradient $\partial^{\circ}$, introduced in [4], of
the function $\varphi\in{\rm Cvx}_{0}(\mathbb{R}^{n})$, and we have that

$\displaystyle\partial^{p}(-\ln(\varphi))=\partial^{\circ}\varphi=\\{(x,y):\varphi(x){\mathcal{A}}\varphi(y)=\langle
x,y\rangle-1>0\\},$

where ${\mathcal{A}}\varphi(y)=\sup_{\\{x:\,\langle
x,y\rangle>1\\}}\frac{\langle x,y\rangle-1}{\varphi(x)}$ is the polarity
transform defined in [3]. More details are provided in Appendix A together
with the proof of the following lemma.

######  Lemma A.4.

Let $\varphi\in{\rm Cvx}_{0}(\mathbb{R}^{n})$ and let $x$ satisfy
$\varphi(x)\in(0,\infty)$. Then

  1. (i)

for any $z\in\partial\varphi(x)$ such that $\langle x,z\rangle\neq\varphi(x)$,
we have that $y=\frac{z}{\langle
x,z\rangle-\varphi(x)}\in\partial^{\circ}\varphi(x)$,

  2. (ii)

for any $y\in\partial^{\circ}\varphi(x)$ there exists some
$z\in\partial\varphi(x)$ such that $\langle x,z\rangle\neq\varphi(x)$ and such
that $y=\frac{z}{\langle x,z\rangle-\varphi(x)}$.

When $\varphi(x)=0$ or $\varphi(x)=\infty$, then by definition,
$\partial^{\circ}\varphi(x)=\emptyset$. When $\varphi(x)\in(0,\infty)$, the
lemma implies that at a differentiability point of $\varphi$, the set
$\partial^{\circ}\varphi(x)$ is either a singleton or is empty, which may
happen only if the function $\varphi$ is linear on $[0,x]$. Our main theorem
thus implies the following.

######  Theorem 1.2.

Let $X=Y=\mathbb{R}^{n}$ and let $\mu,\,\nu\in{\mathcal{P}}(\mathbb{R}^{n})$
be probability measures with finite second moment, which are strongly
$p$-compatible with respect to the polar cost, that is

$\mu(K)+\nu(K^{\circ})<1$

for any convex set $K$ with $\mu(K)\neq 0,1$.

Assume further that $\mu$ is absolutely continuous and that there exists some
finite cost plan mapping $\mu$ to $\nu$. Then there exists $\varphi\in{\rm
Cvx}_{0}(\mathbb{R}^{n})$ such that $\partial^{\circ}\varphi$ is an optimal
transport map between $\mu$ and $\nu$, where

$\partial^{\circ}\varphi(x)=\\{y:\varphi(x){\mathcal{A}}\varphi(y)=\langle
x,y\rangle-1>0\\}.$

In particular, for $\mu$-almost every $x$, the set
$\partial^{\circ}\varphi(x)$ is a singleton.

###### Proof.

By Theorem 1.1, we find a function $\varphi\in{\rm Cvx}_{0}(\mathbb{R}^{n})$
such that there is an optimal plan $\pi$ concentrated on the graph of
$\partial^{p}(-\log\varphi)=\partial^{\circ}\varphi$. We claim that
$\mu$-almost everywhere, the set $\partial^{\circ}\varphi(x)$ is a singleton,
implying that $\partial^{\circ}\varphi$ is indeed a transport map.

Since $\pi$ is concentrated on $\partial^{\circ}\varphi$, the measure $\mu$ is
concentrated on the projection of $\partial^{\circ}\varphi$, so in particular
on the set of $x\in X$ with $\varphi(x)\neq 0,\infty$. We may also restrict to
points in the interior of the domain of $\varphi$, as $\varphi$ is convex and
points on the boundary of its domain have $\mu$-measure zero (using again that
$\mu$ is absolutely continuous). We have that $\mu$-almost every point $x$ in
the interior of the domain of $\varphi$ is a differentiability point of
$\varphi$, and further that $\varphi$ does not vanish on $\mu$-almost every
such point. Hence, by Lemma A.4, $\partial^{\circ}\varphi(x)$ is either a
singleton or the empty set (in which case $x$ does not belong to the
projection of $\partial^{\circ}\varphi$). We conclude that indeed
$\partial^{\circ}\varphi(x)$ must be a singleton $\mu$-almost everywhere, as
required. ∎

##  7\. Decomposable pairs

We discussed in Section 3 that when considering the transport problem of a
measure $\mu\in{\mathcal{P}}(X)$ to $\nu\in{\mathcal{P}}(Y)$, with respect to
a cost function $c:X\times Y\to(-\infty,\infty]$, where $\mu$ and $\nu$ are
$c$-compatible but not strongly $c$-compatible, the transport problem splits
into two transport problems of disjointly supported measures. Let us make this
observation more formal.

######  Proposition 7.1.

Let $c:X\times Y\to(-\infty,\infty]$, and assume
$\mu\in{\mathcal{P}}(X),\,\nu\in{\mathcal{P}}(Y)$ are $c$-compatible measures
which are not strongly $c$-compatible. There exists a $c$-class set $A\subset
X$, and $B\subset Y$ such that $Y\setminus B$ is $c$-class, with
$\mu(A)=\nu(B)\in(0,1)$, such that, letting $\mu|_{A}$ and $\nu|_{B}$ denote
the restricted measures, normalized, the pair $\mu|_{A}$ and $\nu|_{B}$ is
$c$-compatible, as is the pair $\mu|_{X\setminus A}$ and $\nu|_{Y\setminus
B}$. Moreover, any $\pi\in\Pi(\mu,\nu)$ which is concentrated in the set
$S=\\{(x,y):c(x,y)<\infty\\}$, can be written as
$\pi=\mu(A)\pi_{1}+(1-\mu(A))\pi_{2}$, where
$\pi_{1}\in\Pi(\mu|_{A},\nu|_{B})$ and $\pi_{2}\in\Pi(\mu|_{X\setminus
A},\nu|_{Y\setminus B})$, and
$C(\mu,\nu)=\mu(A)C(\mu|_{A},\nu|_{B})+(1-\mu(A))C(\mu|_{X\setminus
A},\nu|_{Y\setminus B})$.

###### Proof.

Indeed, by Lemma 3.12, the fact that the measures are not strongly
$c$-compatible implies that there exists some set $A\subset X$, which is a
$c$-class set (this means there is some $D\subset Y$, which can also be
assumed to be a $c$-class set, such that $A=\\{x:\forall y\in
D,\,c(x,y)=\infty\\}$), and such that $\mu(A)\in(0,1)$ and

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

Rearranging, this means that

$\mu(A)=\nu(\\{y:\exists x\in A,\,\,c(x,y)<\infty\\})\quad{\rm
and}\quad\mu(X\setminus A)=\nu(\\{y:\forall x\in A,\,\,c(x,y)=\infty\\}).$

Let $B=\\{y:\exists x\in A,\,\,c(x,y)<\infty\\}=Y\setminus D$. To see that
$\mu|_{A}$ and $\nu|_{B}$ are $c$-compatible, letting $\mu(A)=a$, say, and
fixing some set $A^{\prime}\subset A$, we see that

$\displaystyle\mu(A^{\prime})+\nu(\\{y\in B:\forall x\in
A^{\prime},\,\,c(x,y)=\infty\\})=$ $\displaystyle\mu(A^{\prime})+\nu(\\{y\in
Y:\forall x\in A^{\prime},\,\,c(x,y)=\infty\\})-\nu(Y\setminus B)\leq
1-(1-a)=a,$

as required. Similarly for the complementary measures. If a transport plan
$\pi\in\Pi(\mu,\nu)$ is concentrated on $S$, then $\pi$ cannot have non-zero
measure in $A\times(Y\setminus B)$ or in $(X\setminus A)\times B$. Indeed, as

$\mu(A)=\pi((A\times Y)\cap S)=\pi(A\times B)\leq\nu(B)=\mu(A)$

implying that we have equalities all along, and $\pi(A\times(Y\setminus
B))=0$. Similarly, as $Y\setminus B=D$ is a $c$-class set, $D=\\{y:\forall
x\in A,\,c(x,y)=\infty\\}$, so $D$ must be mapped to $X\setminus A$, and as
these sets have the same measure,

$\nu(D)=\pi((X\times D)\cap S)=\pi((X\setminus A)\times D)\leq\mu(X\setminus
A)=\nu(D),$

and by the same reasoning, $\pi((A\setminus X)\times B)=0$. (Figure 1 is a
good illustration of this event.)

In other words, such a transport plan can be split into its components,
$\pi_{1}=\pi|_{A\times B}$ and $\pi_{2}=\pi|_{(X\setminus A)\times(Y\setminus
B)}$ (where as above, restriction means to restrict, and renormalize to a
probability measure). This completes the proof. ∎

Of course, the fact that the problem splits into two sub-problems does not
necessarily imply we may solve it in a satisfactory way. Indeed, it may be the
case that each sub-problem has an associated potential function, but these two
functions cannot be “glued” so as to form a potential for the original
problem. This is the case for example for the polar cost in the following
example

######  Example 7.2.

Consider the set

$A=\\{(x,y):\ x\in(\tfrac{1}{2},1),\ y=3-2x\\}\cup\\{(x,y):\ x\in(1,2),\
y=\tfrac{3}{2}-\tfrac{1}{2}x\\}\subset\mathbb{R}^{+}\times\mathbb{R}^{+}.$

The set is a $p$-cyclically monotone (with respect to the polar cost
$p(x,y)=-\ln(\langle x,y\rangle-1)$ since for every point $(x,y)\in A$ we have
$\langle x,y\rangle>1$ and it is a graph of non-increasing function on its
domain, which characterized $p$-cyclically monotone sets on the ray
$\mathbb{R}^{+}$, see [5]. However, the set is not $p$-path-bounded, and thus
admits no potential.

Next, consider the measure $\mu=\nu$ on $[1/2,2]$ with density $1$ on
$[1/2,1]$ and density $1/2$ on $[1,2]$. This is a probability measure. In
fact, $\mu$ and $\nu$ are $p$-compatible as the normalized uniform measure on
the set $A$ constitutes a plan $\pi\in\Pi(\mu,\nu)$. However, they are not
strongly $p$-compatible since the set $A=[1/2,1]$ must be mapped to $B=[1,2]$
and vice versa.

In this case we see the splitting very clearly, and indeed $A$ is written as
the union of two sets, each of which admits a potential (so, in particular,
each is $c$-path-bounded, and is an optimal plan between the corresponding
restricted measures). However, there is no potential for the full set $A$, as
it is not $c$-path-bounded, and in particular no “gluing” of the two
potentials is possible.

##  Appendix A $c$-subgradients and polar subgradients

Since $c$-subgradients play such an important role in this theory, we gather
here some relevant information regarding them but which we did not include in
the main text so as not to disturb its flow.

Let us recall that given a function $\varphi$ in the $c$-class, its
$c$-subgradient is defined by

$\partial^{c}\varphi=\\{(x,y):\,\varphi(x)+\varphi^{c}(y)=c(x,y)\,\text{ and
}\,c(x,y)<\infty\\}.$

Denoting by $\partial^{c}\varphi(x)$ the set of points $y\in Y$ for which
$(x,y)\in\partial^{c}\varphi$, we have by definition that

$x\in\partial^{c}\varphi^{c}(y)\;\;\Leftrightarrow\;\;y\in\partial^{c}\varphi(x).$

Notice that $y\in\partial^{c}\varphi(x)$ if and only if the function
$c(\cdot,y)-\varphi^{c}(y)$ is above $\varphi$ and coincides with it at $x$.
This provides the first simple but useful way to think about $c$-subgradients,
summarized in Lemma A.1. Given a function $\varphi$ in the $c$-class, it is
the image, under the $c$-transform, of another $c$-class function
$\psi=\varphi^{c}$ and therefore, it can be written as an infimum over basic
functions as follows:

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

All the functions on the right hand side lie above $\varphi$. If any one of
the basic functions (indexed by $y$) on the right hand side is tangent to
$\varphi$ at the point $x$, then the pair $(x,y)$ belongs to
$\partial^{c}\varphi$, and $y\in\partial^{c}\varphi(x)$. In other words

######  Lemma A.1.

Let $\varphi$ be a $c$-class function, and $x\in X$ and assume that
$\varphi(x)<\infty$. Then $y_{0}\in\partial^{c}\varphi(x)$ if and only if
$c(x,y_{0})<\infty$ and the function
$\ell(z)=c(z,y_{0})-c(x,y_{0})+\varphi(x)$ satisfies

$\ell(z)\geq\varphi(z)\ \text{ for all }\ z\in X.$

###### Proof.

By the definition we have that $y_{0}\in\partial^{c}\varphi(x)$ if and only if

$\varphi(x)+\varphi^{c}(y_{0})=c(x,y_{0})<\infty.$

Using the definition of the $c$-transform we see that

$\varphi(x)=c(x,y_{0})-\varphi^{c}(y_{0})=\sup_{z}(c(x,y_{0})-c(z,y_{0})+\varphi(z)),$

which holds if and only if for all $z$ we have
$c(z,y_{0})-c(x,y_{0})+\varphi(x)\geq\varphi(z)$. ∎

It is useful to understand the structure of the $c$-subgradient of the basic
functions. In parallel to the classical case, where the linear functions have
constant subgradient, we show that under mild assumptions the same is true for
$c$-subgradients of basic functions. This was, of course, our motivation for
using the specific candidates for the potential functions in Section 5.

######  Lemma A.2.

Let $X,\,Y$ be measure spaces and let $c:X\times Y\to(-\infty,\infty]$ be a
measurable cost function. Consider a basic function $\varphi(x)=c(x,y_{0})+t$
for some $y_{0}\in Y$. If $c(x,y_{0})<\infty$, then
$y_{0}\in\partial^{c}\varphi(x)$. If, in addition, for any $y_{1}\neq y_{0}$
we have that $\inf_{z}\left(c(z,y_{1})-c(z,y_{0})\right)$ is not attained at
$x$ (for example, if the infimum is $-\infty$, or bounded but not attained at
all) then $\\{y_{0}\\}=\partial^{c}\varphi(x)$.

###### Proof.

Indeed, let $\varphi$ be as in the statement. From the definition it follows
that $y\in\partial^{c}\varphi(x)$ if and only if $c(x,y)<\infty$ and

$c(x,y)-\varphi(x)=\varphi^{c}(y)=\inf_{z}(c(z,y)-\varphi(z)),$

which can be reformulated as

$c(x,y)-\varphi(x)\leq c(z,y_{1})-\varphi(z)\ \ \ \text{ for all }z\in X.$

Plugging in the definition of $\varphi$ we get

$c(x,y)-c(x,y_{0})\leq c(z,y)-c(z,y_{0})\ \ \ \text{ for all }z\in X.$

We see that $y=y_{0}$ always satisfies the equality, so that
$y_{0}\in\partial^{c}\varphi(x)$. Clearly for $y_{1}\neq y_{0}$, such an
inequality means precisely that the infimum is attained at $x$. ∎

An important and motivating first example is the one coming from the clasical
cost function $c(x,y)=-\langle x,y\rangle$.

######  Example A.3.

For the cost function $c(x,y)=-\langle x,y\rangle$, whose transport plans and
maps coincide with those associated to the quadratic cost, the $c$-subgradient
coincides, up to a minus sign, with the well known subgradient. More formally,
a function $\varphi$ is in the $c$-class if and only if $-\varphi\in{\rm
Cvx}(\mathbb{R}^{n})$, namely is convex and lower semi-continuous. Denoting
$\psi=-\varphi$ and using the definition of the $c$-transform we see that
$(x,y)\in\partial^{c}\varphi$ if and only if for all $z\in X$ we have

$\psi(z)-\psi(x)=\varphi(x)-\varphi(z)\geq c(x,y)-c(z,y).$

Plugging in the quadratic cost we indeed get that $y\in\partial^{c}\varphi(x)$
if for all $z$ it holds that $\psi(x)+\langle z-x,y\rangle\leq\psi(z)$, namely
$y\in\partial\psi(x)$.

The second motivating example, which is our main point of interest, is that of
the polar cost $p:\mathbb{R}^{n}\times\mathbb{R}^{n}\to(-\infty,\infty]$,
which we once again recall

$p(x,y)=-\ln(\langle x,y\rangle-1)_{+}=\begin{cases}-\ln(\langle
x,y\rangle-1),&\ \ \text{if }\langle x,y\rangle>1\\\ +\infty,&\ \
\text{otherwise.}\end{cases}$

It was shown in [7] that for the polar cost the $p$-class consists of all
functions of the form $-\ln(\varphi)$, where $\varphi$ is a geometric convex
function, that is, a lower semi-continuous non-negative convex function with
$\varphi(0)=0$. The associated cost transform is linked with the
${\mathcal{A}}$-transform defined in [3] and given by

(14) ${\mathcal{A}}\varphi(y)=\sup_{\\{x:\,\langle
x,y\rangle>1\\}}\frac{\langle x,y\rangle-1}{\varphi(x)}.$

More precisely, one may easily verify that
$-\ln({\mathcal{A}}\varphi)=(-\ln(\varphi))^{p}$. Further, the $p$-subgradient
of the function $-\ln(\varphi)$ can be rewritten as the polar subgradient
$\partial^{\circ}$, introduced in [4], of the function $\varphi\in{\rm
Cvx}_{0}(\mathbb{R}^{n})$. Indeed, we have that

(15)
$\displaystyle\partial^{p}(-\ln(\varphi))=\partial^{\circ}\varphi=\\{(x,y):\varphi(x){\mathcal{A}}\varphi(y)=\langle
x,y\rangle-1>0\\}.$

This convenient form is a reason for us to sometimes consider a
“multiplicative” setting, where the basic functions are of the form

$\varphi_{u,t}(x)=t(\langle x,u\rangle-1)_{+}.$

The next lemma, which is a version of [4, Lemma 3.3], describes the connection
between the polar subgradient and the classical subgradient. We will use the
following notation for the zero set $Z_{\varphi}=\\{x:\varphi(x)=0\\}$ and
${\rm dom}(\varphi)=\\{x:\varphi(x)<\infty\\}$ for the domain where $\varphi$
is finite.

######  Lemma A.4.

Let $\varphi\in{\rm Cvx}_{0}(\mathbb{R}^{n})$ and let $x\in{\rm
dom}(\varphi)\setminus Z_{\varphi}$. Then

  1. (i)

for any $z\in\partial\varphi(x)$ such that $\langle x,z\rangle\neq\varphi(x)$,
we have that $y=\frac{z}{\langle
x,z\rangle-\varphi(x)}\in\partial^{\circ}\varphi(x)$,

  2. (ii)

for any $y\in\partial^{\circ}\varphi(x)$ there exists some
$z\in\partial\varphi(x)$ such that $\langle x,z\rangle\neq\varphi(x)$ and such
that $y=\frac{z}{\langle x,z\rangle-\varphi(x)}$.

###### Proof.

(i) Let $z\in\partial\varphi(x)$ with $\langle x,z\rangle\neq\varphi(x)$,
which means that for every $w$ we have $\langle
w,z\rangle-\varphi(w)\leq\langle x,z\rangle-\varphi(x)$. In particular,
$\langle x,z\rangle-\varphi(x)>0$. Hence, letting $y=\frac{z}{\langle
x,z\rangle-\varphi(x)}$ we have that $\langle x,y\rangle>1$.

To show that $y\in\partial^{\circ}\varphi(x)$, it remains to show that
$\varphi(x){\mathcal{A}}\varphi(y)=\langle x,y\rangle-1$. According to the
definition of ${\mathcal{A}}$, this holds if for every $w$ with $\langle
w,y\rangle>1$ and $\varphi(w)>0$, we have

$\frac{\langle w,y\rangle-1}{\varphi(w)}\leq\frac{\langle
x,y\rangle-1}{\varphi(x)}.$

Plugging in $y$ and rearranging gives

$\frac{\langle w,\frac{z}{\langle
x,z\rangle-\varphi(x)}\rangle-1}{\varphi(w)}\leq\frac{\langle
x,\frac{z}{\langle
x,z\rangle-\varphi(x)}\rangle-1}{\varphi(x)}={\frac{1}{\langle
x,z\rangle-\varphi(x)}}.$

Using that $\langle x,z\rangle-\varphi(x)>0$, the above inequality is
equivalent to our initial assumption $\langle w,z\rangle-\varphi(w)\leq\langle
x,z\rangle-\varphi(x)$.

(ii) Given $y\in\partial^{\circ}\varphi(x)$ it follows from the definition
that $\langle x,y\rangle>1$. Consider

$z=\frac{y\varphi(x)}{\langle y,x\rangle-1},$

which is well defined, and also implies that $y=\frac{z}{\langle
x,z\rangle-\varphi(x)}$. We need to show that $z\in\partial\varphi(x)$ and
$\langle z,x\rangle\neq\varphi(x)$.

The latter follows easily since $\langle
z,x\rangle=\varphi(x)\big{(}1+\tfrac{1}{\langle x,y\rangle-1}\big{)}$ and once
again that $\langle x,y\rangle>1$. For the former, we use as before that if
$y\in\partial^{\circ}\varphi(x)$ then for any $w$ with $\langle w,y\rangle>1$
and $\varphi(w)>0$ we have $\frac{\langle
w,y\rangle-1}{\varphi(w)}\leq\frac{\langle x,y\rangle-1}{\varphi(x)}$.
Plugging in $y$ and rearranging, we get that

$\varphi(x)+\langle w-x,z\rangle\leq\varphi(w)$

holds for any $w$ such that $\langle w,z\rangle>\langle x,z\rangle-\varphi(x)$
and $\varphi(w)>0$. In the case when $w$ is such that $\langle
w,z\rangle\leq\langle x,z\rangle-\varphi(x)$, this actually means that
$\varphi(x)+\langle w-x,z\rangle\leq 0$ and since the geometric convex
functions are non-negative the desired inequality trivially follows.

It remains to consider the case when $w\in Z_{\varphi}$, i.e. when
$\varphi(w)=0$. Then, plugging in the previously defined $z$, we have that the
inequality defining the subgradient of $\varphi$ at $x$ becomes simply

$\langle w,y\rangle\leq 1.$

That is, we need to show that $\partial^{\circ}\varphi(x)$ is contained in the
polar set of $Z_{\varphi}$. Indeed, $y\in\partial^{\circ}\varphi(x)$ implies
in particular that $y\in\text{dom}({\mathcal{A}}\varphi)$ (since the value of
${\mathcal{A}}\varphi(y)=\frac{\langle x,y\rangle-1}{\varphi(x)}<\infty$) and
it follows from the definition of ${\mathcal{A}}$ that
$\text{dom}({\mathcal{A}}\varphi)\subset Z_{\varphi}^{\circ}$, which completes
the proof. ∎

We end this appendix with one explicit example of a function and its
$p$-subgradient. More examples and applications can be found in [7, 24] and in
the forthcoming [2].

######  Example A.5.

Let $\varphi(x)=|x|^{2}/2$, in which case
${{\mathcal{A}}}\varphi(y)=|y|^{2}/2$ and the supremum in the definition of
${\mathcal{A}}\varphi$ is satisfied for $x=2y/|y|^{2}$. Hence,
$\partial^{\circ}\varphi(x)=\frac{2x}{|x|^{2}}$. Note that the mapping
$x\mapsto\partial^{\circ}\varphi(x)$ in this case is a (rescaled) spherical
inversion.

## References

  * [1] L. Ambrosio and A. Pratelli, _Existence and stability results in the ${L}^{1}$ theory of optimal transportation_, Optimal transportation and applications, Springer, 2003, pp. 123–160.
  * [2] S. Artstein-Avidan, H. Barel, Y. Rubinstein, S. Sadovsky, and K. Wyczesany, _Transportation induced by the polarity transform_ , In preparation.
  * [3] S. Artstein-Avidan and V. Milman, _Hidden structures in the class of convex functions and a new duality transform_ , Journal of the European Mathematical Society 13 (2011), no. 4, 975–1004.
  * [4] S. Artstein-Avidan and Y. A. Rubinstein, _Differential analysis of polarity: Polar hamilton-jacobi, conservation laws, and monge ampère equations_ , Journal d’Analyse Mathématique 132 (2017), no. 1, 133–156.
  * [5] S. Artstein-Avidan, S. Sadovsky, and K. Wyczesany, _A Rockafellar-type theorem for non-traditional costs_ , arXiv:2011.13263.
  * [6] K. Ball, _An elementary introduction to monotone transportation_ , Geometric aspects of functional analysis, Springer, 2004, pp. 41–52.
  * [7] H. Barel, _Optimal transportation problem for polar cost_ , Master’s thesis, Tel Aviv University, 2019.
  * [8] M. Beiglböck, M. Goldstern, G. Maresch, and W. Schachermayer, _Optimal and better transport plans_ , Journal of Functional Analysis 256 (2009), no. 6, 1907–1927.
  * [9] S. Bianchini and L. Caravenna, _On optimality of c-cyclically monotone transference plans_ , Comptes Rendus Mathematique 348 (2010), no. 11-12, 613–618.
  * [10] Y. Brenier, _Polar factorization and monotone rearrangement of vector-valued functions_ , Communications on pure and applied mathematics 44 (1991), no. 4, 375–417.
  * [11] L. A. Caffarelli, _The regularity of mappings with a convex potential_ , Journal of the American Mathematical Society 5 (1992), no. 1, 99–104.
  * [12] W. Gangbo and R. J. McCann, _The geometry of optimal transportation_ , Acta Mathematica 177 (1996), no. 2, 113–161.
  * [13] L. V. Kantorovich, _On the transfer of masses_ , Dokl. Acad. Sci. SSSR 37 (1942), 227–229.
  * [14] by same author, _On a problem of monge_ , Uspekhi Mat. Nauk. 3 (1948), 225–226.
  * [15] R. J. McCann, _A convexity theory for interacting gases and equilibrium crystals_ , Ph.D. thesis, Princeton University, 1994.
  * [16] J. Rochet, _A necessary and sufficient condition for rationalizability in a quasi-linear context_ , Journal of mathematical Economics 16 (1987), no. 2, 191–200.
  * [17] R. T. Rockafellar, _Characterization of the subdifferentials of convex functions_ , Pacific Journal of Mathematics 17 (1966), no. 3, 497–510.
  * [18] L. Rüschendorf, _On c-optimal random variables_ , Statistics & probability letters 27 (1996), no. 3, 267–270.
  * [19] C. Smith and M. Knott, _On Hoeffding-Fréchet bounds and cyclic monotone relations_ , Journal of multivariate analysis 40 (1992), no. 2, 328–334.
  * [20] V. Strassen, _The existence of probability measures with given marginals_ , The Annals of Mathematical Statistics 36 (1965), no. 2, 423–439.
  * [21] N. S. Trudinger and X. Wang, _On strict convexity and continuous differentiability of potential functions in optimal transportation_ , Archive for rational mechanics and analysis 192 (2009), no. 3, 403–418.
  * [22] C. Villani, _Topics in optimal transportation_ , no. 58, American Mathematical Soc., 2003.
  * [23] by same author, _Optimal transport: old and new_ , vol. 338, Springer Science & Business Media, 2008.
  * [24] K. Wyczesany, _Topics in high-dimensional geometry and optimal transport_ , Ph.D. thesis, University of Cambridge, 2020.

School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel

e-mail<EMAIL_ADDRESS>
e-mail<EMAIL_ADDRESS>
e-mail<EMAIL_ADDRESS>