0
$\begingroup$

Suppose that we have two arbitrary sets $\mathcal{X}$, $\mathcal{Y}$ and are given a function $c : \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$

Consider the following inequality for arbitrary points $(x_i, y_i) \in \mathcal{X} \times \mathcal{Y}$: $$\sum_{i=1}^N c(x_i, y_i) \leq \sum_{i=1}^N c(x_i, y_{i+1}) \quad \quad \textbf{(1)} \\ \text{ and denote } \Gamma_N \equiv \{((x_1, y_1), ..., (x_N, y_N)) \in (\mathcal{X} \times \mathcal{Y}) ^N \text{ such that } \textbf{(1)} \text{ holds}\}$$

We have the convention here that $y_{N+1} \equiv y_1$. Define proj$_k(((x_1, y_1), ..., (x_N, y_N))) = (x_k, y_k)$ and $$\Gamma \equiv \bigcap_{N \in \mathbb{N}}\bigcap_{1 \leq k \leq N} \text{proj}_k(\Gamma_N)$$

Then I claim for any $N \in \mathbb{N}$ and any collection $(x_1,y_1), ..., (x_N, y_N) \in \Gamma$, (1) holds. I DO NOT KNOW HOW TO SHOW THIS PROPERLY EVEN THOUGH IT'S APPARENTLY SUPPOSED TO BE COMPLETELY "OBVIOUS", so maybe I'm being dumb. I recognize that it's intuitive, but I can't write down a rigorous proof for it and I'm in desperate need of help because I've wasted a stupid amount of time on this.

This is all part of the proof of Kantorovich duality in Villani's 2009 book on optimal transport but my question is genuinely just about the sets/definition of projection. I've posted a screenshot below of the part of the book this is taken from.

My attempt at showing this is as follows. I'm just writing out the definitions essentially because I'm lost:

Suppose we have $(x_i, y_i) \in \Gamma, i \in \{1, ..., N\}$. This means that for every $i$, $(x_i, y_i) = \text{proj}_k (z)$ where $z \in \Gamma_N$. i.e. there exists a set of $N-1$ points such that (1) holds for any permutation of the $\mathcal{Y}$ indexed points.

I have absolutely no idea how $$\sum_{i=1}^N c(x_i, y_i) > \sum_{i=1}^N c(x_i, y_{i+1})$$ might produce a contradiction. Please help me if you can. This is probably so obvious and I recognize I'm too braindead to be studying math at this point.

You don't really even need to look at the screenshot but I'm just adding it for reference.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

First of all, I'm not sure why your definition of $\Gamma$ is different from the book. In any case, if I'm parsing the notation of the book correctly, $\pi^{\otimes N}$ is the joint distribution of $N\in \mathbb{N}$ independent random variables on $\mathcal{X}\times \mathcal{Y}$, each with identical distribution $\pi$. From this it should be immediate that $\pi$ is concentrated on $\Gamma = \bigcap_{k = 1, \ldots, N} \mathrm{proj}_k(\Gamma_N)$ and that the set $$\Big\{\big\{(x_i, y_i)\big\}_{i = 1,\ldots,N} \in \Gamma_N\ \Big\vert\Big.\ \forall i = 1,\ldots,k: (x_i,y_i) \in \Gamma\Big\}$$ is closed under permutations. Using duality, we've already shown that any element of $\Gamma_N$ satisfies cyclical monotonicity, concluding the proof.

On a side note, I think that trying to produce a contradiction by assuming cyclical monotonicity fails is certainly possible but not necessary in this case. In some sense, the same mechanism is already built into duality via the constraint $\phi - \psi \leq c$ of the dual problem. If you follow the arguments on the pages preceding your screenshot in reverse it shows (in a slightly handwavy way) that cyclical monotonicity failing for optimal $\pi$ would violate this constraint.

Interestingly, some proofs not based on duality exhibit a similar contradiction directly, see theorem 2.3 of [1] for a rigorous argument and proposition 2.24 of [2] for a fairly intuitive sketch. Also, filling in the details to the duality based proof is essentially exercise 2.38 of [2].

[1] W. Gangbo and R. J. McCann. The geometry of optimal transportation. Acta Mathematica 177, 2 (1996).

[2] C. Villani. Topics in Optimal Transportation. American Mathematical Society, 2003.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the answer. I'm not even sure why Villani makes the projection argument. If you just let $\Gamma = \{(x,y): \phi_k(y) - \psi_k(x) \rightarrow c(x,y)\}$ for $\phi_k, \psi_k$ referenced on the previous page, this is a c-cyclically monotone set for which $\pi$ has measure $1$ so we'd already be done. $\endgroup$
    – qp212223
    Commented Oct 12, 2020 at 6:45
  • $\begingroup$ The problem is that you need to show that every possible $N$-tuple of $\Gamma$ satisfies the cyclical monotonicity condition. A priori, we know that all elements of $\Gamma_N$ satisfy the condition, but what if we could permute an element to produce a counterexample? The projection argument essentially discards points that would allow us to do this. Then we show that $\pi$ is concentrated on $\Gamma$ to conclude. If you can show that the same holds true for your $\Gamma$, then you found an alternative argument. $\endgroup$
    – Gabriel Clara
    Commented Oct 12, 2020 at 22:53
  • $\begingroup$ (2/2) Since $\pi$ has to be concentrated on any such $\Gamma$, the symmetric difference between the $\Gamma$ in the book and yours would have to be negligible with respect to $\pi$ though. The point about permutations is maybe clearer in the references above, where cyclical monotonicity is defined in terms of general permutations of $N$, not just via shifting each $y_i$ to $y_{i+1}$. $\endgroup$
    – Gabriel Clara
    Commented Oct 12, 2020 at 22:58
  • $\begingroup$ Well the proof for my $\Gamma$ is given on p. 68. Suppose we have $N$ points from $\Gamma$ defined in my comment, $\{(x_i, y_i)\}_{i=1}^N$. Then we obtain, by definition of $\phi_k, \psi_k$, $$\sum_{i=1}^N c(x_i, y_{i+1}) \ge \sum_{i=1}^N \phi_k(y_{i+1}) - \psi_k(x_i) = \sum_{i=1}^N \phi_k(y_{i}) - \psi_k(x_i) \rightarrow \sum_{i=1}^N c(x_i, y_i)$$ where we obtain the equality by just rearranging terms in a finite sum, and we may take the limit as $k \rightarrow \infty$ since again, we deal with a finite $N$.So $\Gamma$ is c-cyclically monotone by definition. $\endgroup$
    – qp212223
    Commented Oct 13, 2020 at 17:47
  • $\begingroup$ Upon rereading there seems to be a quite subtle reason why the projection argument comes up. Notice at the bottom of p. 68 how $\phi_k(y_i) - \psi_k(x_i) \to c(x_i, y_i)$ converges in expectation with respect to $\pi(\mathrm{d}x_i, \mathrm{d}y_i)$, for each $(x_i, y_i)$. Picking a sub-sequence yields almost sure convergence under $$\bigotimes_{i = 1}^{N} \pi(\mathrm{d} x_i, \mathrm{d} y_{i+1}),$$ but the latter is written simply as $\pi^{\otimes N}$. The projection argument is then natural to get the desired result for $\pi$. It's maybe a little unusual to write it out though. $\endgroup$
    – Gabriel Clara
    Commented Oct 16, 2020 at 4:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .