Consider the usual Monge-Kantorovich transportation problem where $X$ and $Y$ are Polish spaces, $\mu$ and $\nu$ are probability measures on $X$ and $Y$, and $c:X\times Y \to \mathbb{R}^+ \cup \{+\infty \}$ is a lower semi-continuous cost function. The Kantorovich duality theorem states that the transportation cost between $\mu$ and $\nu$ is equal to the supremum of $$\int_X \varphi~ d\mu +\int_Y \psi~ d\nu $$ over all $L_1$ functions $\varphi(x)$ and $\psi(y)$ such that $\varphi(x)+\psi(y)\leq c(x,y)$ for $d \mu$-almost all $x\in X$ and $d \nu$-almost all $y\in Y$.
My question is: if $c(x,y)\in \{0,1\}$ for all $x$ and $y$, and for each $x$ there exists $y_1,y_2$ such that $c(x,y_1)=0$ and $c(x,y_2)=1$ (and similarly for each $y$ there exist $x_1,x_2$ such that the equivalent condition holds) does it follow that there exists a solution (or "almost exists" a solution) where $\varphi(x)$ and $\psi(x)$ only take values in the set $\{-1,0,1\}$? Finite dimensional experiments with linear programs suggest that the answer is "yes" but I cannot tell if they extend to the general setting.
UPDATE: I added additional conditions about $c$, which guarantees that we can find solutions such that $0\leq\varphi\leq1$ and $-1\leq \psi \leq 0$. This is because we can shift $\varphi$ and $\psi$ such that $\sup_x \varphi(x)=1$, which guarantees that $\psi(y)\geq-1$. Furthermore, it must always be true that $\psi(y)\leq 0$ because otherwise there would exist $x,y$ such that $\varphi(x) + \psi(y) > 1$. This in turn guarantees that we can always assume that $\varphi(x)\geq 0$ as well.