• Previous Article
    Self-improvement of the Bakry-Émery condition and Wasserstein contraction of the heat flow in $RCD (K, \infty)$ metric measure spaces
  • DCDS Home
  • This Issue
  • Next Article
    A glimpse into the differential topology and geometry of optimal transport
April  2014, 34(4): 1623-1639. doi: 10.3934/dcds.2014.34.1623

Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions

1. 

Department of Mathematical and Statistical Sciences, 632 CAB, University of Alberta, Edmonton, Alberta, Canada, T6G 2G1, Canada

Received  October 2012 Revised  February 2013 Published  October 2013

We prove uniqueness and Monge solution results for multi-marginal optimal transportation problems with a certain class of surplus functions; this class arises naturally in multi-agent matching problems in economics. This result generalizes a seminal result of Gangbo and Święch [17]. Of particular interest, we show that this also yields a partial generalization of the Gangbo-Święch result to manifolds; alternatively, we can think of this as a partial extension of McCann's theorem for quadratic costs on manifolds to the multi-marginal setting [23].
    We also show that the class of surplus functions considered here neither contains, nor is contained in, the class of surpluses studied in [27], another generalization of Gangbo and Święch's result.
Citation: Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623
References:
[1]

M. Agueh and G. Carlier, Barycenters in the Wasserstein space,, SIAM J. Math. Anal., 43 (2011), 904.  doi: 10.1137/100805741.  Google Scholar

[2]

M. Beiglbock, P. Henry-Labordere and F. Penkner, Model independent bounds for option prices: A mass transport approach,, Finance Stoch., 17 (2013), 477.  doi: 10.1007%2Fs00780-013-0205-8.  Google Scholar

[3]

M. Bernot, J. Delon, G. Peyre and J. Rabin, Wasserstein barycenter and its application to texture mixing,, in, (6667), 435.   Google Scholar

[4]

Y. Brenier, Décomposition polaire et réarrangement monotone des champs de vecteurs,, (French) [Polar decomposition and increasing rearrangement of vector fields] C. R. Acad. Sci. Pair. Ser. I Math., 305 (1987), 805.   Google Scholar

[5]

Y. Brenier, Extended Monge-Kantorovich theory,, in, (2001), 91.  doi: 10.1007/978-3-540-44857-0_4.  Google Scholar

[6]

G. Buttazzo, L. De Pascale and P. Gori-Giorgi, Optimal-transport formulation of electronic density-functional theory,, Phys. Rev. A, 85 (2012).  doi: 10.1103/PhysRevA.85.062502.  Google Scholar

[7]

L. Caffarelli, Allocation maps with general cost functions,, in, (1996), 29.   Google Scholar

[8]

G. Carlier, On a class of multidimensional optimal transportation problems,, J. Convex Anal., 10 (2003), 517.   Google Scholar

[9]

G. Carlier and I. Ekeland, Matching for teams,, Econom. Theory, 42 (2010), 397.  doi: 10.1007/s00199-008-0415-z.  Google Scholar

[10]

G. Carlier and B.Nazaret, Optimal transportation for the determinant,, ESAIM Control, 14 (2008), 678.  doi: 10.1051/cocv:2008006.  Google Scholar

[11]

P-A. Chiapporri, R. McCann and L. Nesheim, Hedonic price equilibria, stable matching and optimal transport: Equivalence, topology and uniqueness,, Econom. Theory, 42 (2010), 317.  doi: 10.1007/s00199-009-0455-z.  Google Scholar

[12]

C. Cotar, G. Friesecke and C. Klüppelberg, Density functional theory and optimal transportation with Coulomb cost,, Comm. Pure Appl. Math., 66 (2013), 548.  doi: 10.1002/cpa.21437.  Google Scholar

[13]

I. Ekeland, An optimal matching problem,, ESAIM Control, 11 (2005), 57.  doi: 10.1051/cocv:2004034.  Google Scholar

[14]

A. Galichon and N. Ghoussoub, Variational representations for N-cyclically monotone vector fields,, preprint, ().   Google Scholar

[15]

A. Galichon and P. Henry-Labordere and N. Touzi, A stochastic control approach to non-arbitrage bounds given marginals, with an application to Lookback options,, Preprint available at , ().   Google Scholar

[16]

W. Gangbo and R. McCann, The geometry of optimal transportation,, Acta Math., 177 (1996), 113.  doi: 10.1007/BF02392620.  Google Scholar

[17]

W. Gangbo and A. Święch, Optimal maps for the multidimensional Monge-Kantorovich problem,, Comm. Pure Appl. Math., 51 (1998), 23.  doi: 10.1002/(SICI)1097-0312(199801)51:1<23::AID-CPA2>3.0.CO;2-H.  Google Scholar

[18]

N. Ghoussoub and A. Moameni, Symmetric Monge Kantorovich problems and polar decomposition of vector fields,, preprint, ().   Google Scholar

[19]

H. Heinich, Problème de Monge pour $n$ probabilités,, (French) [Monge problem for $n$ probabilities] C. R. Math. Acad. Sci. Paris, 334 (2002), 793.  doi: 10.1016/S1631-073X(02)02341-5.  Google Scholar

[20]

M. Knott and C. Smith, On a generalization of cyclic monotonicity and distances among random vectors,, Linear Algebra Appl., 199 (1994), 363.  doi: 10.1016/0024-3795(94)90359-X.  Google Scholar

[21]

V. Levin, Abstract cyclical monotonicity and Monge solutions for the general Monge-Kantorovich problem,, Set-Valued Analysis, 7 (1999), 7.  doi: 10.1023/A:1008753021652.  Google Scholar

[22]

X-N. Ma, N. Trudinger and Wang, X-J., Regularity of potential functions of the optimal transportation problem,, Arch. Rational Mech. Anal., 177 (2005), 151.  doi: 10.1007/s00205-005-0362-9.  Google Scholar

[23]

R. McCann, Polar factorization of maps on Riemannian manifolds,, Geom. Funct. Anal., 11 (2001), 589.  doi: 10.1007/PL00001679.  Google Scholar

[24]

I. Olkin and S. T. Rachev, Maximum submatrix traces for positive definite matrices,, SIAM J. Matrix Ana. Appl., 14 (1993), 390.  doi: 10.1137/0614027.  Google Scholar

[25]

B. Pass, Regularity properties of optimal transportation problems arising in hedonic pricing models,, ESAIM Control, 19 (2013), 668.  doi: 10.1051/cocv/2012027.  Google Scholar

[26]

B. Pass, Remarks on the semi-classical Hohenberg-Kohn functional,, Nonlinearity, 26 (2013), 2731.  doi: 10.1088/0951-7715/26/9/2731.  Google Scholar

[27]

B. Pass, Uniqueness and Monge Solutions in the Multimarginal Optimal Transportation Problem,, SIAM Journal on Mathematical Analysis, 43 (2011), 2758.  doi: 10.1137/100804917.  Google Scholar

[28]

B. Pass, On the local structure of optimal measures in the multi-marginal optimal transportation problem,, Calculus of Variations and Partial Differential Equations, 43 (2012), 529.  doi: 10.1007/s00526-011-0421-z.  Google Scholar

[29]

B. Pass, Optimal transportation with infinitely many marginals,, Journal of Functional Analysis, 264 (2013), 947.  doi: 10.1016/j.jfa.2012.12.002.  Google Scholar

[30]

L. Rüschendorf and L. Uckelmann, On optimal multivariate couplings,, Distributions with given marginals and moment problems (Prague, (1996), 261.   Google Scholar

[31]

L. Rüschendorf and L. Uckelmann, On the $n$-coupling problem,, J. Multivariate Anal., 81 (2002), 242.  doi: 10.1006/jmva.2001.2005.  Google Scholar

[32]

C. Villani, "Optimal Transport: Old and New,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], (2009).  doi: 10.1007/978-3-540-71050-9.  Google Scholar

show all references

References:
[1]

M. Agueh and G. Carlier, Barycenters in the Wasserstein space,, SIAM J. Math. Anal., 43 (2011), 904.  doi: 10.1137/100805741.  Google Scholar

[2]

M. Beiglbock, P. Henry-Labordere and F. Penkner, Model independent bounds for option prices: A mass transport approach,, Finance Stoch., 17 (2013), 477.  doi: 10.1007%2Fs00780-013-0205-8.  Google Scholar

[3]

M. Bernot, J. Delon, G. Peyre and J. Rabin, Wasserstein barycenter and its application to texture mixing,, in, (6667), 435.   Google Scholar

[4]

Y. Brenier, Décomposition polaire et réarrangement monotone des champs de vecteurs,, (French) [Polar decomposition and increasing rearrangement of vector fields] C. R. Acad. Sci. Pair. Ser. I Math., 305 (1987), 805.   Google Scholar

[5]

Y. Brenier, Extended Monge-Kantorovich theory,, in, (2001), 91.  doi: 10.1007/978-3-540-44857-0_4.  Google Scholar

[6]

G. Buttazzo, L. De Pascale and P. Gori-Giorgi, Optimal-transport formulation of electronic density-functional theory,, Phys. Rev. A, 85 (2012).  doi: 10.1103/PhysRevA.85.062502.  Google Scholar

[7]

L. Caffarelli, Allocation maps with general cost functions,, in, (1996), 29.   Google Scholar

[8]

G. Carlier, On a class of multidimensional optimal transportation problems,, J. Convex Anal., 10 (2003), 517.   Google Scholar

[9]

G. Carlier and I. Ekeland, Matching for teams,, Econom. Theory, 42 (2010), 397.  doi: 10.1007/s00199-008-0415-z.  Google Scholar

[10]

G. Carlier and B.Nazaret, Optimal transportation for the determinant,, ESAIM Control, 14 (2008), 678.  doi: 10.1051/cocv:2008006.  Google Scholar

[11]

P-A. Chiapporri, R. McCann and L. Nesheim, Hedonic price equilibria, stable matching and optimal transport: Equivalence, topology and uniqueness,, Econom. Theory, 42 (2010), 317.  doi: 10.1007/s00199-009-0455-z.  Google Scholar

[12]

C. Cotar, G. Friesecke and C. Klüppelberg, Density functional theory and optimal transportation with Coulomb cost,, Comm. Pure Appl. Math., 66 (2013), 548.  doi: 10.1002/cpa.21437.  Google Scholar

[13]

I. Ekeland, An optimal matching problem,, ESAIM Control, 11 (2005), 57.  doi: 10.1051/cocv:2004034.  Google Scholar

[14]

A. Galichon and N. Ghoussoub, Variational representations for N-cyclically monotone vector fields,, preprint, ().   Google Scholar

[15]

A. Galichon and P. Henry-Labordere and N. Touzi, A stochastic control approach to non-arbitrage bounds given marginals, with an application to Lookback options,, Preprint available at , ().   Google Scholar

[16]

W. Gangbo and R. McCann, The geometry of optimal transportation,, Acta Math., 177 (1996), 113.  doi: 10.1007/BF02392620.  Google Scholar

[17]

W. Gangbo and A. Święch, Optimal maps for the multidimensional Monge-Kantorovich problem,, Comm. Pure Appl. Math., 51 (1998), 23.  doi: 10.1002/(SICI)1097-0312(199801)51:1<23::AID-CPA2>3.0.CO;2-H.  Google Scholar

[18]

N. Ghoussoub and A. Moameni, Symmetric Monge Kantorovich problems and polar decomposition of vector fields,, preprint, ().   Google Scholar

[19]

H. Heinich, Problème de Monge pour $n$ probabilités,, (French) [Monge problem for $n$ probabilities] C. R. Math. Acad. Sci. Paris, 334 (2002), 793.  doi: 10.1016/S1631-073X(02)02341-5.  Google Scholar

[20]

M. Knott and C. Smith, On a generalization of cyclic monotonicity and distances among random vectors,, Linear Algebra Appl., 199 (1994), 363.  doi: 10.1016/0024-3795(94)90359-X.  Google Scholar

[21]

V. Levin, Abstract cyclical monotonicity and Monge solutions for the general Monge-Kantorovich problem,, Set-Valued Analysis, 7 (1999), 7.  doi: 10.1023/A:1008753021652.  Google Scholar

[22]

X-N. Ma, N. Trudinger and Wang, X-J., Regularity of potential functions of the optimal transportation problem,, Arch. Rational Mech. Anal., 177 (2005), 151.  doi: 10.1007/s00205-005-0362-9.  Google Scholar

[23]

R. McCann, Polar factorization of maps on Riemannian manifolds,, Geom. Funct. Anal., 11 (2001), 589.  doi: 10.1007/PL00001679.  Google Scholar

[24]

I. Olkin and S. T. Rachev, Maximum submatrix traces for positive definite matrices,, SIAM J. Matrix Ana. Appl., 14 (1993), 390.  doi: 10.1137/0614027.  Google Scholar

[25]

B. Pass, Regularity properties of optimal transportation problems arising in hedonic pricing models,, ESAIM Control, 19 (2013), 668.  doi: 10.1051/cocv/2012027.  Google Scholar

[26]

B. Pass, Remarks on the semi-classical Hohenberg-Kohn functional,, Nonlinearity, 26 (2013), 2731.  doi: 10.1088/0951-7715/26/9/2731.  Google Scholar

[27]

B. Pass, Uniqueness and Monge Solutions in the Multimarginal Optimal Transportation Problem,, SIAM Journal on Mathematical Analysis, 43 (2011), 2758.  doi: 10.1137/100804917.  Google Scholar

[28]

B. Pass, On the local structure of optimal measures in the multi-marginal optimal transportation problem,, Calculus of Variations and Partial Differential Equations, 43 (2012), 529.  doi: 10.1007/s00526-011-0421-z.  Google Scholar

[29]

B. Pass, Optimal transportation with infinitely many marginals,, Journal of Functional Analysis, 264 (2013), 947.  doi: 10.1016/j.jfa.2012.12.002.  Google Scholar

[30]

L. Rüschendorf and L. Uckelmann, On optimal multivariate couplings,, Distributions with given marginals and moment problems (Prague, (1996), 261.   Google Scholar

[31]

L. Rüschendorf and L. Uckelmann, On the $n$-coupling problem,, J. Multivariate Anal., 81 (2002), 242.  doi: 10.1006/jmva.2001.2005.  Google Scholar

[32]

C. Villani, "Optimal Transport: Old and New,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], (2009).  doi: 10.1007/978-3-540-71050-9.  Google Scholar

[1]

Nassif Ghoussoub, Bernard Maurey. Remarks on multi-marginal symmetric Monge-Kantorovich problems. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1465-1480. doi: 10.3934/dcds.2014.34.1465

[2]

Jesus Garcia Azorero, Juan J. Manfredi, I. Peral, Julio D. Rossi. Limits for Monge-Kantorovich mass transport problems. Communications on Pure & Applied Analysis, 2008, 7 (4) : 853-865. doi: 10.3934/cpaa.2008.7.853

[3]

Giuseppe Buttazzo, Eugene Stepanov. Transport density in Monge-Kantorovich problems with Dirichlet conditions. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 607-628. doi: 10.3934/dcds.2005.12.607

[4]

Abbas Moameni. Invariance properties of the Monge-Kantorovich mass transport problem. Discrete & Continuous Dynamical Systems - A, 2016, 36 (5) : 2653-2671. doi: 10.3934/dcds.2016.36.2653

[5]

Zuo Quan Xu, Jia-An Yan. A note on the Monge-Kantorovich problem in the plane. Communications on Pure & Applied Analysis, 2015, 14 (2) : 517-525. doi: 10.3934/cpaa.2015.14.517

[6]

Limei Dai. Multi-valued solutions to a class of parabolic Monge-Ampère equations. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1061-1074. doi: 10.3934/cpaa.2014.13.1061

[7]

Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037

[8]

Ovidiu Savin. A Liouville theorem for solutions to the linearized Monge-Ampere equation. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 865-873. doi: 10.3934/dcds.2010.28.865

[9]

Alessio Figalli, Young-Heon Kim. Partial regularity of Brenier solutions of the Monge-Ampère equation. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 559-565. doi: 10.3934/dcds.2010.28.559

[10]

Fan Cui, Huaiyu Jian. Symmetry of solutions to a class of Monge-Ampère equations. Communications on Pure & Applied Analysis, 2019, 18 (3) : 1247-1259. doi: 10.3934/cpaa.2019060

[11]

Luca Codenotti, Marta Lewicka. Visualization of the convex integration solutions to the Monge-Ampère equation. Evolution Equations & Control Theory, 2019, 8 (2) : 273-300. doi: 10.3934/eect.2019015

[12]

J. M. Mazón, Julio D. Rossi, J. Toledo. Optimal matching problems with costs given by Finsler distances. Communications on Pure & Applied Analysis, 2015, 14 (1) : 229-244. doi: 10.3934/cpaa.2015.14.229

[13]

Pengwen Chen, Changfeng Gui. Alpha divergences based mass transport models for image matching problems. Inverse Problems & Imaging, 2011, 5 (3) : 551-590. doi: 10.3934/ipi.2011.5.551

[14]

Zhijun Zhang. Optimal global asymptotic behavior of the solution to a singular monge-ampère equation. Communications on Pure & Applied Analysis, 2020, 19 (2) : 1129-1145. doi: 10.3934/cpaa.2020053

[15]

Shouchuan Hu, Haiyan Wang. Convex solutions of boundary value problem arising from Monge-Ampère equations. Discrete & Continuous Dynamical Systems - A, 2006, 16 (3) : 705-720. doi: 10.3934/dcds.2006.16.705

[16]

Haitao Yang, Yibin Chang. On the blow-up boundary solutions of the Monge -Ampére equation with singular weights. Communications on Pure & Applied Analysis, 2012, 11 (2) : 697-708. doi: 10.3934/cpaa.2012.11.697

[17]

Qi-Rui Li, Xu-Jia Wang. Regularity of the homogeneous Monge-Ampère equation. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 6069-6084. doi: 10.3934/dcds.2015.35.6069

[18]

Toyohiko Aiki, Kota Kumazaki. Uniqueness of solutions to a mathematical model describing moisture transport in concrete materials. Networks & Heterogeneous Media, 2014, 9 (4) : 683-707. doi: 10.3934/nhm.2014.9.683

[19]

Barbara Brandolini, Carlo Nitsch, Cristina Trombetti. Shape optimization for Monge-Ampère equations via domain derivative. Discrete & Continuous Dynamical Systems - S, 2011, 4 (4) : 825-831. doi: 10.3934/dcdss.2011.4.825

[20]

Jiakun Liu, Neil S. Trudinger. On Pogorelov estimates for Monge-Ampère type equations. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 1121-1135. doi: 10.3934/dcds.2010.28.1121

2018 Impact Factor: 1.143

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]