# Maximum cost optimal transport

Kantorovich's optimal transportation problem

$$$$\tau_c(\mu,\nu)=\min\limits_{\pi\in\Pi(\nu,\mu)} \int_{X\times Y}c(x,y)d\pi(x,y)$$$$ 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 $$$$M_1(\mu,\mu)\le\int_{[0,1]\times [0,1]}1d\pi(x,y)=1$$$$

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 $$$$\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$$$$ 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.

• Can you please proofread the notation in the last example? Is f there representing Lebesgue measure? – Yuval Peres Oct 4 '19 at 19:50
• @YuvalPeres Yes, I have changed the notation. Actually if we only consider the measure that has a density function, then the optimal transport or maximum cost transport could be seen as it is defined on functional space. That is the reason why I wrote $M_c(f,f)$ in the first place. Sorry for the inconvenience. – Wen Ding Oct 4 '19 at 19:55
• Did you want to write $M_1$ or $M_c$ at the end? – Yuval Peres Oct 5 '19 at 5:28
• Try asking Gabriel Peyré, co-author of Computational Optimal Transport arxiv.org/abs/1803.00567 .That book only deals with the usual situation of minimizing cost, rather than maximizing cost (minimizing negative cost), but it's worth a shot. Maybe analogous to difference between convex optimization and correspondingconcave optimization problem (obtained by maximizing rather than minimizing the objective of the original convex optimization problem, still subject to the same convex constraints). The concave opt. problem is generally much more difficult than the convex opt. problem. – Mark L. Stone Oct 8 '19 at 21:53
• Kantorovich OT is a linear program and as such, maximizing and minimizing is basically the same thing... – Dirk Oct 9 '19 at 3:30

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$$.

• (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.
• Thank you. Your reference is very helpful. In Section 10.4 of Viana's book, it seems that $d$ has to be positive to satisfy the condition of the theorem. The non-trivialness of the problem you mentioned is because of the negative power of the distance, which causes the cost $c(x,y)$ to decrease when $\vert x-y\vert$ increases. But it is still positive, therefore the infimum is always non-negative. However, the problem in my setting is negative cost.The proof from $d$ is always positive to $d$ is always negative is nontrivial. For example, the infimum may not exist if $d$ is negative. – Wen Ding Oct 8 '19 at 21:13
• @user80599 Sorry, there was a wrong sign; I fixed it. – Jairo Bochi Oct 9 '19 at 11:22

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.