Given probability distributions $(\mu_1, \mu_2,\dots,\mu_n)$ on a sufficiently nice space $X$, does there always exist a random vector $(X_1,X_2\dots,X_n)$ such that any pair $(X_i,X_j)$ is an optimal coupling of $\mu_i$ and $\mu_j$?
This is possible if we only require that $(X_k,X_{k+1})$ are optimal couplings of $\mu_k$ and $\mu_{k+1}$ for $k\in\{1,\dots,n-1\}$, this is a result of the gluing lemma. If any restrictions are required on the measures or the space, I am very interested nonetheless.
Best Answer
Consider a graph $G$ on $\{1,\ldots,n\}$ where $\mu_i$ is assigned to node $i$, and an edge $\{i,j\}$ in $G$ indicates that the coupling 0f $\mu_i$ and $\mu_j$ is required to be optimal. If $G$ has no cycles (i.e., it is a forest) then the proof of the gluing lemma (see, e.g., [1]), applied separately to each tree of the forest, extends to show that a global coupling can be arranged to be optimal on all edges of $G$. Conversely, we next verify that if $G$ contains a cycle, then there is a choice of the measures $\mu_i$ where such a global optimal coupling does not exist.
Let us first show this for a cycle of length 3:
Suppose the variable $X$ is uniform in $\{1,2,3\}$, the variable $Y$ is uniform in $\{2,3,4\}$ and $Z$ is uniform in $\{1,3,4\}$.
Under the optimal coupling $P_1$ of $(X,Y)$, we have $P_1(Y=4|X=1)=1$.
Under the optimal coupling $P_2$ of $(Y,Z)$, we have $P_2(Z=4|Y=4)=1$.
Under the optimal coupling $P_3$ of $(X,Z)$, we have $P_3(Z=4|X=1)=0$.
This shows that there is no coupling of $(X,Y,Z)$ that projects to the optimal couplings $P_1, P_2, P_3$.
For a cycle of length $k>3$, simply assign two adjacent nodes of the cycle the laws of $X$ and $Y$, and assign all other nodes the law of $Z$.
[1] Villani, Cedric. Optimal transport: old and new. Vol. 338. Berlin: springer, 2009.