Optimal transport 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

*

*We can find $K < M$


*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 !
 A: 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.
A: 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.
