1
$\begingroup$

Let $c : X\times Y \rightarrow \mathbb{R}$ and $\mu$ (and $\nu$) two probabilities over $X$ (and $Y$). I'm going to define two problems.

The first is $$ \tag{KP} K := \inf \left\{ \int_{X\times Y} c \; \text{d}\pi \ \middle| \ \pi \in \Pi(\mu,\nu) \right\}, $$ where $\Pi(\mu,\nu)$ is the subset of the probability measure $\pi$ such as $$ \pi (A\times Y) =\mu(A) \text{ and } \pi(X\times B)=\nu(B). $$ The second problem is $$ \tag{MP} M := \inf \left\{ \int_{X} c(x,T(x))d\mu(x) \ \middle| \ T_{\text{#}} \mu = \nu \right\} $$ with $T_{\text{#} \mu}$ the push-forward measure.

I'm looking for some easy case when

  1. We can find $K < M$

  2. We can show that $KP$ have solution but $MP$ do not.

One can prove $K \le M$ so if $MP$ don't have solution then $KP$ neither.

Do somebody know some cases ? (or can find it) Thank you very much for your help !

$\endgroup$

2 Answers 2

1
$\begingroup$

1) If $\mu=\delta_0$, $\nu=\frac{1}{2}(\delta_0+\delta_1)$ then $K<\infty=M$. If you want an example where both $K,M$ are finite and $K<M$ take $\mu=\nu=\frac{1}{3}\delta_0+\frac{2}{3}\delta_1$. Then $M=c(0,0)+c(1,1)$ (the only admissible transport map $T$ sends 0 to 0 and 1 to 1), and $K\leq\frac{1}{3}(c(0,1)+c(1,0)+c(1,1))$ (you can see this by using $\pi$ that sends 0 to 1 and splits 1 to 0 and 1). So choosing the right $c$ will imply $K<M<\infty$ (for example $c(0,0)=c(1,1)=1$ and $c(0,1)=c(1,0)=0$).

2) Again, if $\mu=\delta_0$, $\nu=\frac{1}{2}(\delta_0+\delta_1)$ then $K$ has a solution (as opposed to your comment) and $M$ don't. If you want an example where $M<\infty$ and don't have a solution it is a bit more subtle, for example you can transport an interval of mass 1 to 2 intervals of mass $\frac{1}{2}$ each, see example 4.9 here.

$\endgroup$
0
0
$\begingroup$

If $\mu(X)\ne \nu(Y)$ then both problems have no feasible points and are unsolvable.

If $\mu$ is concentrated on one point (Dirac), and $\nu$ is concentrated on two points (two Diracs), then $M = +\infty$. Splitting of point masses is not possible in MP.

$\endgroup$
0

You must log in to answer this question.