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

We study a multi-marginal optimal transport problem with surplus $b(x_{1}, \ldots, 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 \neq 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 '{S}wi\c{e}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].