Multi-marginal optimal transport: Theory and applications

Pass, Brendan

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 49 (2015) no. 6, pp. 1771-1790.

Over the past five years, multi-marginal optimal transport, a generalization of the well known optimal transport problem of Monge and Kantorovich, has begun to attract considerable attention, due in part to a wide variety of emerging applications. Here, we survey this problem, addressing fundamental theoretical questions including the uniqueness and structure of solutions. The answers to these questions uncover a surprising divergence from the classical two marginal setting, and reflect a delicate dependence on the cost function, which we then illustrate with a series of examples. We go on to describe some applications of the multi-marginal optimal transport problem, focusing primarily on matching in economics and density functional theory in physics.

Classification : 49K30, 49J30, 49K20, 91B68, 81V45, 90C05, 35J96
Mots clés : Multi-marginal optimal transport, Monge−Kantorovich problem, structure of solutions, uniqueness of solutions, matching, purity, density functional theory, strictly correlated electrons

M. Agueh and G. Carlier, Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43 (2011) 904–924. | DOI | MR | Zbl

L. Ambroso and N.Gigli, A users guide to optimal transport. In Modelling and Optimisation of Flows on Networks. In vol. 2062 of Lect. Notes Math. Springer (2013) 1–155. | MR

M. Beiglbock and C. Griessler, An optimality principle with applications in optimal transport. Preprint arXiv:1404.7054.

M. Beiglbock, P. Henry-Labordere and F. Penkner, Model independent bounds for option prices: a mass transport approach. Finance Stoch. 17 (2013) 477–501. | DOI | MR | Zbl

M. Beiglbock and N. Juillet, On a problem of optimal transport under marginal martingale constraints. To appear in Ann. Probab. (2015). | MR

J. Bigot and T. Klein, Consistent estimation of a population barycenter in the Wasserstein space. Proc. of the International Conference Statistics and its Interaction with Other Disciplines (2013) 153–157.

Y. Brenier, Decomposition polaire et rearrangement monotone des champs de vecteurs. C.R. Acad. Sci. Pair. Ser. I Math. 305 (1987) 805–808. | MR | Zbl

Y. Brenier, The dual least action problem for an ideal, incompressible fluid. Arch. Ration. Mech. Anal. 122 (1993) 323–351. | DOI | MR | Zbl

G. Buttazzo, L. De Pascale and P. Gori-Giorgi, Optimal-transport formulation of electronic density-functional theory. Phys. Rev. A 85 (2012) 062502. | DOI

L. Caffarelli, Allocation maps with general cost functions. In Partial Differential Equations and Applications. Vol. 177 of Lect. Notes Pure Appl. Math. Dekker, New York (1996) 29–35. | MR | Zbl

L.A. Caffarelli and R.J. Mccann, Free boundaries in optimal transport and Monge-Ampère obstacle problems. Ann. Math. 171 (2010) 673–730. | DOI | MR | Zbl

G. Carlier, On a class of multidimensional optimal transportation problems. J. Convex Anal. 10 (2003) 517–529. | MR | Zbl

G. Carlier and I. Ekeland, Matching for teams. Econ. Theory 42 (2010) 397–418. | DOI | MR | Zbl

G. Carlier and B. Nazaret, Optimal transportation for the determinant. ESAIM: COCV 14 (2008) 678–698. | Numdam | MR | Zbl

G. Carlier, A. Oberman and E. Oudet, Numerical methods for matching for teams and Wasserstein barycenters. To appear in ESAIM: M2AN (2015). Doi:. | DOI | Numdam | MR

H. Chen, G. Friesecke and C. Mendl, Numerical methods for a Kohn-Sham density functional model based on optimal transport. J. Chem. Theory. Comput. 10 (2014) 4360–4368. | DOI

P.A. Chiappori, A. Galichon and B. Salanie, The roommate problem is more stable than you think. CESifo working paper Serie (2014).

P-A. Chiapporri, R. Mccann and L. Nesheim, Hedonic price equilibria, stable matching and optimal transport; equivalence, topology and uniqueness. Econ. Theory. 42 (2010) 317–354. | DOI | MR | Zbl

M. Colombo and S. Di Marino, Equality between Monge and Kantorovich multimarginal problems with Coulomb cost . Ann. Mat. Pura Appl. 194 (2015) 307–320. | DOI | MR | Zbl

M. Colombo, L. De Pascale and S. Di Marino, Multimarginal optimal transport maps for 1-dimensional repulsive costs. Canad. J. Math. 67 (2015) 350–368. | DOI | MR | Zbl

C. Cotar, G. Friesecke and C. Klüppelber, Density functional theory and optimal transportation with coulomb cost. Comm. Pure Appl. Math. 66 (2013) 548–599. | DOI | MR | Zbl

C. Cotar, G. Friesecke and C. Klüppelberg, Smoothing of transport plans with fixed marginals and rigorous semiclassical limit of the Hohenberg-Kohn functional. Preprint. | MR

C. Cotar, G. Friesecke and B. Pass, Infinite body optimal transport with Coulomb cost. Calc. Var. Partial Differ. Eqs. 54 (2015) 717–742. | DOI | MR | Zbl

J. Dahl, A maximal principal for pointwise energies of quadratic Wasserstein minimal networks. Preprint arXiv:1011.0236v3.

Y. Dolinsky and M.H. Soner, Robust hedging and martingale optimal transport in continuous time. Probab. Theory Relat. Fields 160 (2014) 391–427. | DOI | MR | Zbl

Y. Dolinsky and M.H. Soner, Robust hedging with proportional transaction costs. Finance Stoch. 18 (2014) 327–347. | DOI | MR | Zbl

I. Ekeland, An optimal matching problem. ESAIM: COCV 11 (2005) 57–71. | Numdam | MR | Zbl

P. Embrechts, G. Puccetti, L. Ruschendorf, R. Wang and A. Beleraj, An academic response to basel 3.5. Risks 2 (2014) 25–48. | DOI

L.C. Evans,Partial differential equations and Monge−Kantorovich mass transfer. In vol. 26 of Current Dev. Math. Int. Press (1999) 65–126. | MR | Zbl

Alessio Figalli, The optimal partial transport problem. Arch. Ration. Mech. Anal. 195 (2010) 533–560. | DOI | MR | Zbl

G. Friesecke, C. Mendl, B. Pass, C. Cotar and C. Klüppelber. N-density representability and the optimal transport limit of the Hohenberg-Kohn functional. J. Chem. Phys. 139 (2013) 164–109. | DOI

A. Galichon and N. Ghoussoub, Variational representations for N-cyclically monotone vector fields. Pacific J. Math. 269 (2014) 323–340. | DOI | MR | Zbl

A. Galichon, P. Henry-Labordere and N. Touzi, A stochastic control approach to non-arbitrage bounds given marginals, with an application to Lookback options. Ann. Appl. Probab. 24 (2014) 312–336. | DOI | MR | Zbl

W. Gangbo, Habilitation thesis, Universite de Metz, available at: http://people.math.gatech.edu/˜gangbo/publications/habilitation.pdf (1995).

W. Gangbo and R. Mccann, The geometry of optimal transportation. Acta Math. 177 (1996) 113–161. | DOI | MR | Zbl

W. Gangbo and A. Świȩch, Optimal maps for the multidimensional Monge−Kantorovich problem. Comm. Pure Appl. Math. 51 (1998) 23–45. | DOI | MR | Zbl

N. Ghoussoub and A. Moameni, Symmetric Monge−Kantorovich problems and polar decompositions of vector fields. Geom. Funct. Anal. 24 1129–1166. | DOI | MR | Zbl

N. Ghoussoub and A. Moameni, A self-dual polar factorization for vector fields. Comm. Pure. Appl. Math. 66 (2013) 905–933. | DOI | MR | Zbl

N. Ghoussoub and B. Pass. Decoupling of DeGiorgi-type systems via multi-marginal optimal transport. Comm. Partial Differ. Eqs. 6 (2014) 1032–1047. | DOI | MR | Zbl

N. Ghoussoub and B. Maurey, Remarks on multi-marginal symmetric Monge-Kantorovich problems. Discrete Contin. Dyn. Syst. 34 (2014) 1465–1480. | DOI | MR | Zbl

H. Heinich, Probleme de Monge pour $n$ probabilities. C.R. Math. Acad. Sci. Paris 334 (2002) 793–795. | DOI | MR | Zbl

P. Henry-Labordere, X. Tan and N. Touzi, An Explicit Martingale Version of the One-dimensional Brenier’s Theorem with Full Marginals Constraint. Preprint available at: https://www.ceremade.dauphine.fr/˜tan/MartingaleBrenierII.pdf. | MR

P. Henry-Labordere and N. Touzi, An explicit martingale version of Brenier’s theorem. Preprint arXiv:1302.4854.

H.G. Kellerer, Duality theorems for marginal problems. Z. Wahrsch. Verw. Gebiete 67 (1984) 399–432. | DOI | MR | Zbl

Y.-H. Kim and R. Mccann, Continuity, curvature, and the general covariance of optimal transportation. J. Eur. Math. Soc. 12 (2010) 1009–1040. | DOI | MR | Zbl

Y.-H. Kim and B. Pass, Multi-marginal optimal transport on a Riemannian manifold. Preprint arXiv:1303.6251. | MR

Y.-H. Kim and B. Pass, A general condition for Monge solutions in the multi-marginal optimal transport problem. SIAM J. Math. Anal. 46 (2014) 1538–1550. | DOI | MR | Zbl

J. Kitagawa and B. Pass, The multi-marginal optimal partial transport problem. Preprint arXiv:1401.7255. | MR

M. Knott and C. Smith, On a generalization of cyclic monotonicity and distances among random vectors. Linear Algebra Appl. 199 (1994) 363–371. | DOI | MR | Zbl

V. Levin, Abstract cyclical monotonicity and Monge solutions for the general Monge−Kantorovich problem. Set-Valued Anal. 7 (1999) 7–32. | DOI | MR | Zbl

G.G. Lorentz, An inequality for rearrangements. Amer. Math. Monthly 60 (1953) 176–179. | DOI | MR | Zbl

X-N. Ma, N. Trudinger and X-J. Wang, Regularity of potential functions of the optimal transportation problem. Arch. Ration. Mech. Anal. 177 (2005) 151–183. | DOI | MR | Zbl

R. Mccann, Polar factorization of maps on Riemannian manifolds. Geom. Funct. Anal. 11 (2001) 589–608. | DOI | MR | Zbl

R.J. Mccann, A glimpse into the differential topology and geometry of optimal transport. Discrete Contin. Dyn. Syst. 34 (2014) 1605–1621. | DOI | MR | Zbl

R.J. Mccann, B. Pass and M. Warren, Rectifiability of optimal transportation plans. Canad. J. Math. 64 (2012) 924–934. | DOI | MR | Zbl

C. Mendl and L. Lin, Towards the Kantorovich dual solution for strictly correlated electrons in atoms and molecules. Phys. Rev. B 87 (2013) 125106. | DOI

A. Moameni, Invariance properties of the Monge−Kantorovich mass transport problem. Preprint . | arXiv | MR

A. Moameni, Multi-marginal monge−kantorovich transport problems: A characterization of solutions. C. R. Math. Acad. Sci. Paris 352 (2014) 993–998. | DOI | MR | Zbl

I. Olkin and S.T. Rachev, Maximum submatrix traces for positive definite matrices. SIAM J. Matrix Ana. Appl. 14 (1993) 390–39. | DOI | MR | Zbl

R.G. Parr and W. Yang, Density functional theory of atoms and molecules. Oxford University Press, Oxford (1995).

B. Pass, Structural results on optimal transportation plans. Ph.D. thesis, University of Toronto (2011). Available at: http://www.ualberta.ca/˜pass/thesis.pdf. | MR

B. Pass, Uniqueness and Monge solutions in the multimarginal optimal transportation problem. SIAM J. Math. Anal. 43 (2011) 2758–2775. | DOI | MR | Zbl

B. Pass, On the local structure of optimal measures in the multi-marginal optimal transportation problem. Calc. Var. Partial Differ. Equ. 43 (2012) 529–536. | DOI | MR | Zbl

B. Pass, On a class of optimal transportation problems with infinitely many marginals. SIAM J. Math. Anal. 45 (2013) 2557–2575. | DOI | MR | Zbl

B. Pass, Remarks on the semi-classical Hohenberg-Kohn functional. Nonlinearity 26 (2013) 2731–2744. | DOI | MR | Zbl

B. Pass, Multi-marginal optimal transport and multi-agent matching problems: uniqueness and structure of solutions. Discrete Contin. Dyn. Syst. 34 (2014) 1623–1639. | DOI | MR | Zbl

Brendan Pass. Optimal transportation with infinitely many marginals. J. Funct. Anal. 264 (2013) 947–963. | DOI | MR | Zbl

G. Puccetti and L. Ruschendorf, Sharp bounds for sums of dependent risks. J. Appl. Probab. 50 (2013) 42–53. | DOI | MR | Zbl

J. Rabin, G. Peyre, J. Delon and M. Bernot, Wasserstein barycenter and its application to texture mixing. In Scale Space and Variational Methods in Computer Vision (2012) 435–446.

L. Rüschendorf and L. Uckelmann, On Optimal Multivariate Couplings. In Proc. of Prague 1996 Conference on Marginal Problems. Kluwer Acad. Publ. (1997) 261–274. | MR | Zbl

Michael Seidl, Strong-interaction limit of density-functional theory. Phys. Rev. A 60 (1999) 4387–4395. | DOI

Michael Seidl, Paola Gori-Giorgi and Andreas Savin, Strictly correlated electrons in density-functional theory: A general formulation with applications to spherical densities. Phys. Rev. A 75 (2007) 042511. | DOI

C. Villani, Topics in Optimal Transportation. In vol. 58 of Grad. Stud. Math. American Mathematical Society, Providence (2003). | MR | Zbl

C. Villani, Optimal Transport: Old and New. In vol. 338 of Grundlehren Math. Wiss. Springer, New York (2009). | MR | Zbl