Thanks for your answer. It seems that in your optimal coupling $\pi$ for computing $W_1$, the probability mass on $(i,\sigma(i))$ is only allowed to split in the same row. Why? This is not true for $\ell_2$-norm, but may be correct for $\ell_1$.

Thanks for your update. I just read the references and hope to get some idea. In fact, I think for $W_2$ we can explicitly compute the Wasserstein distance, and reduce the problem to a matrix problem. See my posted answer and let me know if it is correct. My main interest is using $\ell_1$ norm. Also note that the $p$ in $\ell_p$ is NOT the order of Wasserstein distance, but merely the metric of the space where the random variable takes value. I modified the question to make it clear.

Thanks for your answer. I have several questions: (1) Could you be more specific on which example in [Cuesta-Albertos et.al] for maximal Wasserstein distance? (2) For the "unsolved" general problem, do you mean it is still unsolved even if it is for uniform $C_{unif}$, or just for a general copula? (3) What is a circular neighborhood?

@TomSolberg Mainly of theoretical interest, I don't know a particular application yet... But I think this problem may occur in other fields without in the language of Wasserstein distance.

@BjørnKjos-Hanssen Yeah, this intuition makes a lot of sense. However, I cannot build a RIGOROUS connection between the goal of the problem and the goal of find a distribution with smallest neighborhood...

@BenoîtKloeckner The dyadic squares may be a good starting point for proof though.

@BenoîtKloeckner I just check $N=4$ by solving the linear programming that defines Wasserstein distance. The distance between comonotonic distribution and $\nu$ is 0.25, whereas the distance between uniform distribution on $j=i+N/2 \mod N$ and $\nu$ is 0.2.

@BenoîtKloeckner No I haven't, but what you said makes sense. In my situation, I am more interested in fixing $\nu$ to be the uniform distribution on $\Xi$. Is there a connection between the case for $\nu$ is uniform over $j=i+N/2$ and $\nu$ is uniform over $\Xi$?

Perhaps the paper by Bertsimas et al. (arxiv.org/pdf/1507.03133.pdf) is a relevant reference.