Monge solutions and uniqueness in multi-marginal optimal transport via graph theory

Abstract

We study a multi-marginal optimal transport problem with surplus $b(x_1,\dots ,x_m)={\sum }_{\{i,j\}\in P}{x}_i\cdot x_j$, where $P\subseteq Q:=\{\{i,j\}:i,j\in \{1,2,...m\},i\ne j\}$. We reformulate this problem by associating each surplus of this type with a graph with $m$ vertices whose set of edges is indexed by $P$. We then establish uniqueness and Monge solution results for two general classes of surplus functions. Among many other examples, these classes encapsulate the Gangbo and Świȩch surplus [12] and the surplus ${\sum }_{i=1}^{m-1}{x}_i\cdot x_{i+1}+x_m\cdot x_1$ studied in an earlier work by the present authors [23].