I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.


More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$ be a uniform distribution on $\Xi$, namely, $\nu\_{ij}:=\nu(\{(i,j)\})=\frac{1}{N^2}$, for all $1\leq i,j\leq N$. 
 Consider the problem
 \begin{equation}
 \max\_{\mu\geq0} \bigg \{ W(\mu,\nu):\ \sum\_{i}\mu\_{ij} = \frac{1}{N}, \forall j,\ \sum\_{j} \mu\_{ij}=\frac{1}{N}, \forall i \bigg\}, \tag{1}
\end{equation}
where $W\_1(\mu,\nu)$ is the Wasserstein distance between probability distribution $\mu:=\{\mu\_{ij}\}\_{1\leq i,j\leq N}$ and $\nu$, defined as
 $$
 W\_1(\mu,\nu) :=
 \min\_{\pi\geq0} \bigg\{\sum\_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||\_1 \pi\_{(i,j),(i',j')}:\ \sum\_{i,j} \pi\_{(i,j),(i',j')} = \nu\_{i'j'},\forall i',j',\ \sum\_{i',j'} \pi\_{(i,j),(i',j')} = \mu\_{ij},\ \forall i,j\bigg\}.
 $$


My conjecture is that the maximizer of problem $(1)$ is given by $\mu\_{ij}=\frac{1}{N}{1}\_{\{i=j\}}$, or $\mu\_{ij}=\frac{1}{N}{1}\_{\{i+j=N+1\}}$, namely, the comonotonic/countermonotonic distribution. But how to prove/disprove it? Also, if it is true, could the result be extended to the multivariate case, namely, $\Xi=\{1,2,\ldots,N\}^K$ for $K>2$, or be extended for norms other than $\ell\_1$-norm, or other $W\_p$ distance ($p>1$)?


Update: Steve provides an affirmative answer for $\ell\_1$-norm with $W\_1$ distance in the case of $K=2$, and I provide a proof for $\ell\_2$ norm with $W\_2$ distance for all $K\geq2$. I am wondering if we can get some other result, such as $\ell\_1$-norm with $K>2$, or $\ell\_\infty$-norm.



The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals
I think I have an answer for the case p = 1, K = 2. I write "I think" because my computation does not coincide with the example values for $N=4$ posted earlier by OP in a comment, but I really cannot find any error in my proof, so I wanted to share it.


As already mentioned, we only need to consider permutation measures of the form $\mu = \sum\_{i=1}^N \frac{1}{N} \delta\_{i,\sigma(i)}$, since these are the extremal points of the set we optimize over.


For any such $\mu$, we can define a coupling $\pi$ by $\pi\_{(i,\sigma(i)),(i,j)} = 1/N^2$ for $i,j \in \{1,...,N\}$ and $\pi\_{(i,j),(i',j')} = 0$, if $i,j,i',j'$ are not of the form as before. That this is an admissible coupling in the definition of $W\_1$ is trivial.
The corresponding "value" is
$$
\sum\_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||\_1 \pi\_{(i,j),(i',j')} = \sum\_{1 \leq i,j' \leq N} |\sigma(i) - j'| \frac{1}{N^2}.
$$
We further show that this value is minimal if $\mu$ is the monotonic or comonotonic measure, which will yield the claim. I only show this for the monotonic case, $\mu = \frac{1}{N}\sum\_{i=1}^N \delta\_{i,i}$. Then for any admissible coupling $\hat{\pi}$, by the constraints in the calculation of the Wasserstein distances, we see 
\begin{align\*}
\sum\_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||\_1 \hat{\pi}\_{(i,j),(i',j')} =& \sum\_{1\leq i',j' \leq N} \sum\_{1 \leq i \leq N} ||(i,i)-(i',j')||\_1 \hat{\pi}\_{(i,i),(i',j')} \\ \geq& \sum\_{1\leq i',j' \leq N} \sum\_{1 \leq i \leq N} ||(i',i')-(i',j')||\_1 \hat{\pi}\_{(i,i),(i',j')}\\ =&\sum\_{1\leq i',j' \leq N} |i'-j'| \frac{1}{N^2},
\end{align\*}
where the inequality is elementwise and the last term corresponds to the value for the coupling $\pi$.


Note that this only shows that monotonic/comonotonic measures are maximizers, but not that these are the only maximizers.


