Consider the uniform distribution $\lambda$ on $[0,1]$, and a point measure $\rho$ with density $\frac{1}{2} (\delta_{x_1} + \delta_{x_2})$, where we have $0\le x_1 \le x_2 < 1/2$.
If our cost is just the distance $c(x,y) = | x - y|$, it seems reasonably clear that the optimal transport map from $\lambda$ to $\rho$ would be $$ T(x) = \begin{cases} x_1 & \text{if } x < 1/2\\ x_2 & \text{if } x \ge 1/2 \end{cases} $$ and the optimal coupling would have density along the lines of $$ \mathrm{d}\pi(x,y) = \frac{1}{2} \left( \chi_{[0,1/2)}(x) \delta_{x_1}(y) + \chi_{[1/2,1]}(x) \delta_{x_2}(y)\right), $$ where $\chi_{A}$ is an indicator function. However, consider the usual Kantorovich dual formulation where we want to find $$ \sup_{\phi, \psi} \left( \int_0^1 \phi(y) \, \mathrm{d}y - \frac{1}{2}(\psi_1 + \psi_2)\right) = \sup_{\psi} \left( \int_0^1 \psi^c(y) \, \mathrm{d}y - \frac{1}{2}(\psi_1 + \psi_2)\right) $$ where the supremum is taken over all 1-Lipschitz functions $\phi$ and $\psi = \{ \psi_1,\psi_2\}$ such that $| \psi_1 - \psi_2 | \le | x_1 - x_2 |$, and where $\phi(y) - \psi_i \le |x_i - y|$. Furthermore $\psi^c$ is the usual $c$-transform, which in this case is $$ \psi^c(y) = \min_{i} \left(\psi_i + | x_i - y |\right). $$ (There is some abuse of notation here BTW)
My problem is: This dual solution doesn't seem to work in this case. Ideally we want Laguerre cells $$ \mathrm{Lag}_1 := \{ x : |x - x_1| + \psi_1 \le |x - x_2| + \psi_2, \,\, \forall j \neq i\} = [0,1/2), $$ and similarly $\mathrm{Lag}_2 = [1/2,1]$. I just can't see how we can find values $\psi_1, \psi_2$ that give us these Laguerre cells. If say $\psi_2 = \psi_1 + \varepsilon$ where $\varepsilon < x_2 - x_1$, then $\psi$ would be "$c$-convex" and we would get $$ \mathrm{Lag}_1 = [0, (x_2 - x_1 + \varepsilon)/2) $$ which obviously has measure of less than $1/2$. If $\varepsilon > x_2 - x_1$ then we'd have that $\mathrm{Lag}_1 = [0,1]$ and $\mathrm{Lag}_2 = \emptyset$, and furthermore it seems that $\psi$ would not be $c$-convex any more.
Am I missing something here? I can't see in the theory (e.g. Theorem 5.10 from Villani's Optimal Transport: Old and New) why we wouldn't be able to have a dual form in this example. Also in the question On semi-discrete Wasserstein distance there is a similar issue: you can see that the green points are not contained within their respective Laguerre cells, which may mean it is similarly impossible to find a $c$-convex $\psi$.
