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].
Categories: math.OC