Prove that $-\psi(y) \leq c(x,y) + c(x,\bar y) - \psi(\bar y)$

Question

In the book Optimal Transport for Applied Mathematicians, Theorem 1.37, the authors states an inequality, but I'm having trouble seeing how one shows that the inequality is indeed true.

Definition: Given a function $c:X\times Y \to \mathbb R$, we say that $\Gamma \subset X \times Y$ is $c$-cyclically monotone ($c$-CM) if for every $k \in \mathbb N$, every permutation $\sigma$ and every finite family of points $(x_1,y_1),...,(x_k,y_k) \in \Gamma$ we have $$ \sum^k_{i=1} c(x_i,y_i) \leq \sum^k_{i=1} c(x_i,y_{\sigma(i)}) $$

Now, assume that $\Gamma$ is $c$-CM. Then, fix $(x_0, y_0) \in \Gamma$, and define: $$ -\psi(y) = \inf\{ -c(x_n,y) +c(x_n,y_{n-1})-c(x_{n-1},y_{n-1})+...+ c(x_1,y_0) - c(x_0,y_0) : n \in \mathbb N, (x_i,y_i) \in \Gamma \quad \forall i=1,...,n \} $$

How does one then shows that fo $(x,y) \in \Gamma$ and $\bar y \in \text{Proj}_y \circ\Gamma$, we can then write: $$ -\psi(y) \leq - c(x,y) + c(x,\bar y) - \psi(\bar y) $$

In the proof, the author claims that this inequality follows from the very definition of the function $\psi$. What I found odd was that since $y$ and $\bar y$ are arbitrary, then I could just swap them, obtaining the opposite inequality, and hence, I actually have an equality. Which would be kind of odd. Anyways, how can you prove this inequality? And is it actually an equality?

Answer 1

Ok, so after some struggle and the help of a friend I figured what I was misunderstanding. Here is the proof:

First, note that since $\bar y \in \pi_y\circ\Gamma$, this means that $\exists \quad \bar x : (\bar x,\bar y) \in \Gamma$. Also, note that $\{(x,y),(\bar x, \bar y)\} \subset \Gamma$, henece $$ -\psi(y) \leq -c(x,y) + c(x,\bar y) - c(\bar x, \bar y) $$

Now, fix the first two terms in the inequality. Note that for any $n \in \mathbb N$ and $(x_i,y_i) \in \Gamma$ for $i \in \{0,...,n\}$, we have: $$ -\psi(y) \leq -c(x,y) + c(x,\bar y) - c(\bar x_n, \bar y) + c(\bar x_n,\bar y)-...-c(\bar x_0,\bar y_0) $$

We can then conclude that $$ -\psi(y) \leq -c(x,y) + c(x,\bar y) + \inf \{-c(\bar x_n, \bar y) +...-c(\bar x_0,\bar y_0): n\in \mathbb N , (\bar x_i,\bar y_i) \in \Gamma \quad \forall i \in \{0,...,n\} \} \\ -\psi(y) \leq -c(x,y) + c(x,\bar y) -\psi(\bar y) $$

Answer 2

By assumption $-\psi(\bar{y})>-\infty$. Thus, there is a cycle $\Gamma':=\lbrace (x_{1},y_{1}),\dots,(x_{r},y_{r})\rbrace$ such that $-\psi(\bar{y})=-c(x_{r},\bar{y})+c(x_{r},y_{r-1})+\dots+c(x_{1},y_{0})-c(x_{0},y_{0})$. Then, considering the cylce $\Gamma'':=\Gamma'\cup\lbrace{(x,\bar{y})\rbrace}$ it follows \begin{equation} -\psi(y)\le -c(x,y)+\sum_{k=1}^{r+1} c(x_{k},y_{k-1})-c(x_{k-1},y_{k-1})-c(x_{0},y_{0})=-c(x,y)+c(x,\bar{y})-\psi(\bar{y}). \end{equation}