I am trying to understand the proof of the following
Theorem Let $X, Y$ be metric spaces and $c: X \times Y \to \mathbb{R}$ be a continuous and bounded function and let $\Gamma \subset X \times Y$ be $c$-monotone. Then there exists $\varphi : X \to \mathbb{R} \cup \{-\infty \} $, a $c$-concave function, s.t. $\varphi \not \equiv - \infty$ and $$ \varphi(x) + \varphi^c(y) = c(x,y) \quad \quad \text{ for all } (x,y) \in \Gamma $$
where
$\Gamma \subset X \times Y$ is said to be $c$-monotone if for any $n \in \mathbb{N}$, for any $ \{ (x_1, y_1) , \dots (x_n,y_n) \} \subset \Gamma$ and any $\sigma \in S_n$ we have $$ \sum_{i=1}^n c(x_i, y_{\sigma(i)}) \ge \sum_{i=1}^n c(x_i, y_i) $$
$\varphi : X \to \mathbb{R} \cup \{-\infty \} $ is said to be $c$-concave if there exists $\{y_i\}_{i \in I} \subset Y$ and $\{ \alpha_i\}_{i \in I} \subset \mathbb{R}$ s.t. $$ \varphi(x) = \inf_{i \in I} \{ c(x,y_i) + \alpha_i \} $$
Given $\varphi : X \to \mathbb{R} \cup \{-\infty \} $ the function $\varphi^c : Y \to \mathbb{R} \cup \{-\infty \} $ is defined as $$ \varphi^c(y) = \inf_{x \in X} \{ c(x,y)-\varphi(x) \} $$
Moreover I define $$ \partial^c \varphi (x) = \{ y \in Y \mid c(x',y)-\varphi(x') \text{ is minimal at } x'=x \}$$
proof
It is easy to see that $\varphi(x) + \varphi^c(y) = c(x,y)$ iff $y \in \partial^c \varphi (x)$, then it is enough to prove $(x,y) \in \Gamma \Rightarrow y \in \partial^c \varphi (x)$. Let $\varphi$ be defined as $$ \varphi(x) = \inf \{ c(x,y_n) -c(x_n, y_n) + c(x_n, y_{n-1}) + \dots c(x_1, y_0) -c(x_0,y_0) \} $$ where the infimum is made over all possible $n \ge 1$ and $ \{ (x_1, y_1) , \dots (x_n,y_n) \} \subset \Gamma$. It can be shown that $\varphi$ is $c$-concave and upper semicontinuous and $\varphi(x_0)=0$. I am struggling in proving $(x,y) \in \Gamma \Rightarrow y \in \partial^c \varphi (x)$. Indeed, it should be equivalent to prove $$ c(x',y) -\varphi(x') \ge c(x,y) -\varphi(x) \quad \quad \text{ for all } x' \in X $$ $$ \Leftrightarrow$$ $$\varphi(x)-\varphi(x') \ge c(x,y)-c(x',y) \quad \quad \text{ for all } x' \in X $$ By the definition of $\varphi$ and using $\inf(f) -\inf(g) \ge \inf (f-g)$ I should have $$ \varphi(x)-\varphi(x') \ge \inf_{y_n \in \text{proj}_Y \Gamma} \{ c(x,y_n) -c(x',y_n) \} \quad \quad \text{ for all } x' \in X $$ and $RHS \ge c(x,y)-c(x',y)$ iff $RHS = c(x,y)-c(x',y)$ i.e. iff, for any fixed $x' \in X$, I have $$ c(x,y_n) -c(x',y_n) \ge c(x,y)-c(x',y) \quad \quad \text{ for all } y_n \in \text{proj}_Y \Gamma $$ $$ \Leftrightarrow$$ $$ c(x,y_n)+c(x',y) \ge c(x,y) + c(x',y_n) \quad \quad \text{ for all } y_n \in \text{proj}_Y \Gamma $$ which could be true if $(x',y_n) \in \Gamma$ but I can't do such an assumption.
Any idea of how I can conclude?
Ok, it was quite easy: take $ (x_n,y_n) = (x,y)$, then
$$\varphi(x') = \inf \{ c(x',y_n) - c(x_n, y_n) + c(x_n, y_{n-1}) + \dots + c(x_1, y_0)-c(x_0,y_0) \} \le $$ $$ \le c(x',y)-c(x,y) + c(x, y_{n-1}) + \dots + c(x_1, y_0)-c(x_0,y_0) $$ Then I take the infimum of both sides over all possibile $\{ (x_{n-1},y_{n-1}), \dots, (x_1, y_1) \} \subset \Gamma $ and I obtain
$$ \varphi(x') \le c(x',y)-c(x,y) + \varphi(x) \Leftrightarrow c(x',y)-\varphi(x') \ge c(x,y) - \varphi(x)$$