# 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

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 !

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