# A simple counterexample to the Monge ansatz in multi-marginal optimal transport, convex geometry of the set of Kantorovich plans, and the Frenkel-Kontorova model

arXiv: https://arxiv.org/abs/1808.04318 · HTML: https://mlsanity.com/paper/1808.04318/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2018.

## Built on by (most cited first, 2 of 2)

- [Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems](https://mlsanity.com/paper/2103.12624/) (2021)
- [The GenCol algorithm for high-dimensional optimal transport: general formulation and application to barycenters and Wasserstein splines](https://mlsanity.com/paper/2209.09081/) (2022)

## Abstract (arXiv)

It is known from clever mathematical examples citeCa10 that the Monge ansatz may fail in continuous two-marginal optimal transport (alias optimal coupling alias optimal assignment) problems. Here we show that this effect already occurs for finite assignment problems with N=3 marginals, ℓ=3 'sites', and symmetric pairwise costs, with the values for N and ℓ both being optimal. Our counterexample is a transparent consequence of the convex geometry of the set of symmetric Kantorovich plans for N=ℓ=3, which -- as we show -- possess 22 extreme points, only 7 of which are Monge. These extreme points have a simple physical meaning as irreducible molecular packings, and the example corresponds to finding the minimum energy packing for Frenkel-Kontorova interactions. Our finite example naturally gives rise, by superposition, to a continuous one, where failure of the Monge ansatz manifests itself as nonattainment and formation of 'microstructure'.