On the Existence of Monge Solutions to Multi-marginal Optimal Transport with Quadratic Cost and Uniform Discrete Marginals

A natural and important question in multi-marginal optimal transport is whether the Monge ansatz is justified; does there exist a solution of Monge, or deterministic, form? We address this question for the quadratic cost when each marginal measure is m-empirical (that is, uniformly supported on m points). By direct computation, we provide an example showing that the ansatz can fail when the underlying dimension d is 2, the number of marginals N to be matched is 3, and the size m of their supports is 3. As a consequence, the set of m-empirical measures is not barycentrically convex when $$N \ge 3$$ N ≥ 3 , $$d \ge 2$$ d ≥ 2 , and $$m \ge 3$$ m ≥ 3 . It is a well-known consequence of the Birkhoff-von Neumann theorem that the Monge ansatz holds for $$N=2$$ N = 2 , standard techniques show it holds when $$d=1$$ d = 1 , and we provide a simple proof here that it holds whenever $$m=2$$ m = 2 . Therefore, the N, d, and m in our counterexample are as small as possible.