1
$\begingroup$

Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ and $\mu_Z$ and cost functions $c_1:X\times Y\to[0,\infty)$ and $c_2:Y\times Z\to [0,\infty)$. The transport problems are to minimize $\sum_{x,y} c_1(x,y)\pi_1(x,y)$ and $\sum_{y,z} c_2(y,z)\pi_2(y,z)$ over couplings $\pi_1$ and $\pi_2$ respectively.

Now suppose we introduce a cost function $c_3:X\times Z\to[0,\infty)$, which maybe satisfies something like $c_3(x,z)\leq \min_y c_1(x,y)+c_2(y,z)$, which is a sort of triangle inequality. Given this, we could greedily solve the first two transport problems separately and then compose the plans, but I suspect this not optimal. My question is how the third optimal transport problem is related to the first two, and perhaps further, how the relationship depends on the level of control of $c_3$ in terms of $c_1$ and $c_2$. I am a novice in the area, so any buzzwords that could point me in the right direction would be helpful.

Improve this question
$\endgroup$
3
  • $\begingroup$ Ah yes, sorry for the delay. So I agree with what you have written, and was fully anticipating something like this. What I am interested in is: can one describe how the relationship between $c_1$ and $c_2$ affects the inefficiency of the composed plan. In other words, can one bound the amount you overpay in $c_3$ in terms of how $c_1$ and $c_2$ fit together? In this sense, it is something of an inverse optimal transport question. $\endgroup$
    – tex.support
    Commented Oct 11 at 15:47
  • $\begingroup$ Any reasonable answer to this problem should involve the marginals too, since your "second" problem does not depend on $\mu_Y$. For the classical transportation problem where $X=Y=Z$ and $c_1(x,y)=(1-\lambda)|x-y|^2,c_2(y,z)=\lambda |y-z|^2$ and $c_3(x,z)=|x-z|^2$ then your greedy strategry is optimal if and only if $\mu_Y$ is the time-$\lambda$ geodesic interpolation between $\mu_X$ and $\mu_Z$, i-e the pushforward of the optimal plan $\pi_3(x,z)$ under the map $y=T_\lambda(x,z)=(1-\lambda)x+\lambda z$. A keyword here is perhaps McCann's interpolant. $\endgroup$
    – leo monsaingeon
    Commented Dec 4 at 16:22
  • $\begingroup$ another relevant keyword is "multimarginal optimal transport" $\endgroup$
    – leo monsaingeon
    Commented Dec 4 at 16:40

1 Answer 1

Reset to default
2
$\begingroup$

we could greedily solve the first two transport problems separately and then compose the plans, but I suspect this not optimal.

Indeed, this is not optimal in general. Here is an example:

  • $X=Y=Z=\{0,1\}$, with $\mu_X,\mu_Y,\mu_Z$ each being the uniform distribution over $\{0,1\}$
  • $c_1(0,0)=2$, $c_1(0,1)=c_2(0,0)=c_3(0,0)=1$, with all other values of $c_1,c_2,c_3$ being $0$.

Indeed, the "triangle" inequality $c_3(x,z)\le c_1(x,y)+c_2(y,z)$ needs to be checked only for $(x,z)=(0,0)$, and we have $c_3(0,0)=1\le c_1(0,y)+c_2(y,0)$ for $y=0,1$.

Next, the only optimal plan (say $P_{XY}$) to transport $\mu_X$ to $\mu_Y$ is to interchange the $\frac12$-masses at $0$ and $1$ -- that is, to transport the $\mu_X$-mass at $0$ to the $\mu_Y$-mass at $1$, and the $\mu_X$-mass at $1$ to the $\mu_Y$-mass at $0$.

Similarly, the only optimal plans (say $P_{YZ}$ and $P_{XZ}$) to transport $\mu_Y$ to $\mu_Z$ and to transport $\mu_X$ to $\mu_Z$, respectively, are each to interchange the $\frac12$-masses at $0$ and $1$.

However, the composition of the "interchange" optimal plans $P_{XY}$ and $P_{YZ}$ is, not $P_{XZ}$, but the plan that does not move any mass at all. $\quad\Box$

For an illustration, here is a picture showing the four nonzero transportation costs ($c_1(0,0)=2$ and $c_1(0,1)=c_2(0,0)=c_3(0,0)=1$, red):

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice illustration! 😁 $\endgroup$
    – Nate River
    Commented Oct 10 at 10:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .