Monge Solutions for Multi-Marginal Optimal Transport

29 concepts13 papers2 proposals

Classical optimal transport (OT) answers a fundamental question: how do we map a single source probability distribution to a single target distribution with minimal cost? However, many modern problems require us to align three, four, or thousands of distributions simultaneously. This is the domain of Multi-Marginal Optimal Transport (MMOT). Instead of computing a pairwise coupling, MMOT seeks a joint probability distribution across $N$ marginals that minimizes a collective, multi-variable cost function.

While this sounds like a straightforward scaling of classical OT, the underlying geometry and mathematical guarantees change dramatically when moving from two marginals ($N=2$) to three or more ($N \ge 3$).

The Breakdown of Two-Marginal Intuition

In standard two-marginal optimal transport, two foundational properties give us structural peace of mind:

  1. Cyclical Monotonicity: A transport plan is optimal if and only if its support is $c$-cyclically monotone. This means you cannot reduce the total cost by reshuffling any finite chain of transport assignments.
  2. Monge Solutions: Under mild smoothness conditions (known as the "twist condition"), the optimal transport plan is deterministic. Mass from a single source point does not split; it maps to exactly one destination. This concentrated plan is called a Monge solution.

When we extend the problem to $N \ge 3$ marginals, this elegant machinery breaks down. As demonstrated by Mircea Petrache in Cyclically monotone non-optimal N-marginal transport plans and Smirnov-type decompositions for N-flows, $c$-cyclical monotonicity is no longer sufficient to guarantee optimality in higher dimensions. By introducing combinatorial frameworks like $N$-flows and $N$-graphs, the author showed that complex, non-optimal transport plans can still appear locally monotone.

Furthermore, the classical equivalence between cyclical monotonicity and "splitting sets"—the geometric sub-gradients used to construct optimal potentials—disappears. Without this equivalence, proving whether a multi-marginal plan is unique or deterministic becomes exceptionally difficult.

Restoring Determinism: The Twist on Splitting Sets

To guarantee that an optimal multi-marginal plan doesn't fractured mass across infinite combinations, researchers needed a new condition tailored to multi-way interactions.

In A general condition for Monge solutions in the multi-marginal optimal transport problem, Young-Heon Kim et al. introduced a unifying criterion called the twist on splitting sets. Instead of evaluating pairwise injectivity, this condition analyzes the relationship between the gradient of the cost function with respect to one variable and the joint configuration of all remaining variables. When a cost function satisfies this multi-marginal twist, the optimal transport plan is guaranteed to be unique and concentrated entirely on the graph of a set of deterministic maps.

Two-Marginal Twist:       Source x -----------> Target y (Unique Map)
Multi-Marginal Twist:     Source x -----------> (Target y1, Target y2, ..., Target yN) 
                                                [Jointly determined as a single Monge graph]

This structural guarantee allows MMOT to operate reliably on curved geometries. For instance, Brendan Pass et al. extended this framework to non-Euclidean spaces in Multi-marginal optimal transport on Riemannian manifolds. They proved that when the cost function represents the squared distance to a central barycenter on a Riemannian manifold, the optimal plan remains unique and retains its Monge structure.

Even when full determinism cannot be achieved due to non-convexities, the solution often degrades gracefully into a "multi-map." As shown by Théo Dumont et al. in On the Existence of Monge Maps for the Gromov-Wasserstein Problem, the support of the optimal plan can still be bounded within the union of a small, finite number of deterministic functions, preventing arbitrary mass diffusion.

Why It Works: Applications in Data and Geometry

The theoretical resolution of the multi-marginal Monge problem explains why MMOT functions as a powerful tool across diverse domains. By framing multi-dataset problems as a single joint optimization, we can bypass the errors that accumulate when compounding pairwise comparisons.

Wasserstein Barycenters

Finding the "average" or central representative of multiple probability distributions is fundamentally an MMOT problem. In Existence and consistency of Wasserstein barycenters, Jean-Michel Loubes et al. demonstrated that finding a barycenter amounts to identifying a multi-marginal coupling that simultaneously minimizes transport costs across all involved probability measures.

Hypergraph Geometry

Traditional graph theory relies on pairwise metrics like the Ollivier-Ricci curvature to detect bottlenecks and bridges. However, real-world networks often feature multi-node interactions (hyperedges).

To compute curvature on hypergraphs, Shahab Asoodeh et al. in Curvature of Hypergraphs via Multi-Marginal Optimal Transport and Corinna Coupette et al. in Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework leveraged MMOT. By utilizing Wasserstein barycenters to compute a central distribution across all nodes within a hyperedge, they successfully reduced complex, higher-order set relationships into a single, geometrically meaningful scalar value.

Inference in Graphical Models

When performing probabilistic inference on aggregate populations rather than tracked individuals, the computational complexity typically explodes. In Inference With Aggregate Data in Probabilistic Graphical Models: An Optimal Transport Approach, Rahul Singh et al. formulated aggregate observations as fixed marginal constraints in an entropic regularized MMOT problem. This formulation enables algorithms like Sinkhorn Belief Propagation to achieve global convergence with a computational complexity that is entirely independent of the population size.

Key Foundational Work

A general condition for Monge solutions in the multi-marginal optimal transport problem (2013) — contributed 8 concept elements to this direction.
Multi-marginal optimal transport on Riemannian manifolds (2015) — contributed 5 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multi_marginal_optimal_transport_ec0bdf60,
  title = {multi-marginal optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-marginal-optimal-transport/rdr_ec0bdf60c35840808dd349210fea0ce6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_marginal_optimal_transport_ec0bdf60_v1,
  title = {multi-marginal optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-marginal-optimal-transport/rdr_ec0bdf60c35840808dd349210fea0ce6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake