Maximum cost optimal transport

Question

Kantorovich's optimal transportation problem

\begin{equation} \tau_c(\mu,\nu)=\min\limits_{\pi\in\Pi(\nu,\mu)} \int_{X\times Y}c(x,y)d\pi(x,y) \end{equation} where $\Pi(\mu,\nu) = \{\pi\in P(X\times Y); \pi(A\times Y) = \mu(A), \pi(X\times B) = \nu(B) \}$

It is a well-studied topic when cost function $c$ is non-negative. But if $c$ is actually a non-positive function, I could not find any literature researching it. Namely, The problem is equivalent to the maximum cost transport \begin{align} M_c(\mu,\nu)&:=\max\limits_{\pi\in\Pi(\nu,\mu)} \int_{X\times Y}\vert c(x,y)\vert d\pi(x,y)\\ &=-\min\limits_{\pi\in\Pi(\nu,\mu)} \int_{X\times Y}-\vert c(x,y)\vert d\pi(x,y)\\ &=-\min\limits_{\pi\in\Pi(\nu,\mu)} \int_{X\times Y}c(x,y) d\pi(x,y) \end{align}

This problem seems quite different from the optimal transport problem in the sense that it is well-defined and it can yield non-trivial solutions. For example, consider the maximum cost transport in the interval $[0,1]$, with cost function $c(x,y)=\vert x-y\vert$

$X=Y=[0,1]$, and $d\mu(x)=dx$, then obviously, $M_1(\mu,\mu)$ is not $0$, and \begin{equation} M_1(\mu,\mu)\le\int_{[0,1]\times [0,1]}1d\pi(x,y)=1 \end{equation}

Actually I can prove that $M_1(\mu,\mu)=\frac12$. I think that $M_1(\mu,\mu)=0$ if and only if $\mu$ is point measure. It seems that $M_c$ could describe how "dispersive" or "concentrated" a measure is.

Moreover, some of the useful theorems in classical optimal transport theory still hold for the maximal cost transport, for example, I can prove that the duality formulation of Kantorovich's problem still holds for maximal cost transport. Namely,

Theorem (Duality formulation of maximal cost transport) Let $X$ and $Y$ be Polish spaces, let $\mu\in P(X), \nu\in P(Y)$, and let $c:X\times Y\rightarrow \mathbb R_+\cup \{\infty\} $ be a continuous cost function.Then \begin{equation} \sup\limits_{\Pi(\mu, \nu)}\int_{X\times Y}c(x,y)d\pi(x,y)=\inf\limits_{\Phi_c}\int_X\phi d\mu+\int_Y \psi d\nu \end{equation} where $$\Pi(\mu,\nu) = \{\pi\in P(X\times Y); \pi(A\times Y) = \mu(A), \pi(X\times B) = \nu(B) \}$$ and $$\Phi_c:=\{(\phi,\psi)\in L^1(d\mu)\times L^1(d\nu):\phi(x)+\psi(y)\ge c(x,y)\}$$

Any literature about the maximum cost transport would be appreciated.

Answer 1

Consider the following variant of the problem. Let $(X,d)$ be a compact metric space, and let $\delta>0$. Take the cost function $c_\delta(x,y) := d(x,y)^{-\delta}$. Given a probability $\nu$ on $X$, define its $\delta$-energy as: $$ e_\delta(\nu):=\inf_{\xi \in \Pi(\nu,\nu)} \int c_\delta d\xi . $$ This looks like the usual minimization problem, but since the cost function is somewhat bizarre (it decreases as the two points separate), the problem has a flavor similar to yours.

In Section 10.4 Viana's book Lectures on Lyapunov Exponents you can find some information about the problem above. No general theory is developed, since this is used only as a tool for the proof of a theorem on continuity of Lyapunov exponents. However, you will find there the following interesting lemma:

Lemma. Suppose $\nu$ is a probability measure on $X$.

1. If $\nu$ has an atom with mass $>1/2$ then $e_\delta(\nu)=+\infty$.

2. If $\nu$ has no atom with mass $\ge 1/2$ then $e_\delta(\nu)<+\infty$.

Comments:

• (1) is almost trivial, but (2) is trickier.
• The lemma is stated in the book for a specific compact metric space, but the proof applies in general.
• The presentation in the book is based on a celebrated but still unfinished work by Avila, Eskin, and Viana. See this blog post by Carlos Matheus for a nice discussion.

Answer 2

The problem of maximizing the total cost is just the original problem plus some constant:

As implied by the duality theorem you mentioned, if the maximal total cost is not $\infty$, there must be some $(\phi,\psi)\in L^1(d\mu)\times L^1(d\nu)$ so that $\phi(x)+\psi(y)\geq c(x,y)$, so just take a new cost function $\tilde{c}(x,y):=\phi(x)+\psi(y)-c(x,y)\geq0$.

The maximal total cost is: $$ \begin{array}{cc} \sup_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}c\text{d}\pi &=\\\\ \sup_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}\phi(x)+\psi(y)-\tilde{c}(x,y)\text{d}\pi(x,y) &=\\\\ \int_X\phi\text{d}\mu+\int_Y\psi\text{d}\nu-\inf_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}\tilde{c}\text{d}\pi \end{array} $$ So maximizing the total cost for $c$ can be achieved by minimizing the total cost for $\tilde{c}\geq0$.

Since it is basicly the same problem, I don't think you would find any significance literature about it.