Prove that $-\psi(y) \leq c(x,y) + c(x,\bar y) - \psi(\bar y)$ 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?
 A: 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}
A: 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)
$$
