Simultaneous optimal transport
HTML articles powered by AMS MathViewer
- by Ruodu Wang and Zhenyuan Zhang;
- Trans. Amer. Math. Soc.
- DOI: https://doi.org/10.1090/tran/9393
- Published electronically: May 8, 2025
- PDF | Request permission
Abstract:
We propose a general framework of mass transport between non-negative vector-valued measures, which will be called simultaneous optimal transport (SOT). The new framework is motivated by the need to transport resources of different types simultaneously, i.e., in single trips, from specified origins to destinations; similarly, in economic matching, one needs to couple two groups, e.g., buyers and sellers, by equating supplies and demands of different goods at the same time. The mathematical structure of simultaneous transport is very different from the classic setting of optimal transport, leading to many new challenges. The Monge and Kantorovich formulations are contrasted and connected. Existence conditions and duality formulas are established. More interestingly, by connecting SOT to a natural relaxation of martingale optimal transport (MOT), we introduce the MOT-SOT parity, which allows for explicit solutions of SOT in many interesting cases.References
- David R. Adams and Lars Inge Hedberg, Function spaces and potential theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 314, Springer-Verlag, Berlin, 1996. MR 1411441, DOI 10.1007/978-3-662-03282-4
- Narges Ahani, Tommy Andersson, Alessandro Martinello, Alexander Teytelboym, and Andrew C. Trapp, Placement optimization in refugee resettlement, Oper. Res. 69 (2021), no. 5, 1468–1486. MR 4330625, DOI 10.1287/opre.2020.2093
- Charalambos D. Aliprantis and Kim C. Border, Infinite dimensional analysis, 3rd ed., Springer, Berlin, 2006. A hitchhiker’s guide. MR 2378491
- Luigi Ambrosio, Lecture notes on optimal transport problems, Mathematical aspects of evolving interfaces (Funchal, 2000) Lecture Notes in Math., vol. 1812, Springer, Berlin, 2003, pp. 1–52. MR 2011032, DOI 10.1007/978-3-540-39189-0_{1}
- Hedy Attouch, Giuseppe Buttazzo, and Gérard Michaille, Variational analysis in Sobolev and BV spaces, 2nd ed., MOS-SIAM Series on Optimization, vol. 17, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2014. Applications to PDEs and optimization. MR 3288271, DOI 10.1137/1.9781611973488
- Xavier Bacon, Multi-species optimal transportation, J. Optim. Theory Appl. 184 (2020), no. 2, 315–337. MR 4054282, DOI 10.1007/s10957-019-01590-z
- X. Bacon, G. Carlier, and B. Nazaret, A spatial Pareto exchange economy problem, Appl. Math. Optim. 87 (2023), no. 3, Paper No. 45, 29. MR 4565012, DOI 10.1007/s00245-022-09947-z
- Brendan K. Beare, Copulas and temporal dependence, Econometrica 78 (2010), no. 1, 395–410. MR 2642867, DOI 10.3982/ECTA8152
- Mathias Beiglböck, Pierre Henry-Labordère, and Friedrich Penkner, Model-independent bounds for option prices—a mass transport approach, Finance Stoch. 17 (2013), no. 3, 477–501. MR 3066985, DOI 10.1007/s00780-013-0205-8
- Mathias Beiglböck and Nicolas Juillet, On a problem of optimal transport under marginal martingale constraints, Ann. Probab. 44 (2016), no. 1, 42–106. MR 3456332, DOI 10.1214/14-AOP966
- Mathias Beiglböck, Marcel Nutz, and Nizar Touzi, Complete duality for martingale optimal transport on the line, Ann. Probab. 45 (2017), no. 5, 3038–3074. MR 3706738, DOI 10.1214/16-AOP1131
- Adrien Blanchet and Guillaume Carlier, Optimal transport and Cournot-Nash equilibria, Math. Oper. Res. 41 (2016), no. 1, 125–145. MR 3465745, DOI 10.1287/moor.2015.0719
- Jose Blanchet and Karthyek Murthy, Quantifying distributional model risk via optimal transport, Math. Oper. Res. 44 (2019), no. 2, 565–600. MR 3959085, DOI 10.1287/moor.2018.0936
- J. Boerma, A. Tsyvinski, A. P. and Zimin, Sorting with team formation, J. Political Economy (2021), To appear.
- Guillaume Carlier, Victor Chernozhukov, and Alfred Galichon, Vector quantile regression: an optimal transport approach, Ann. Statist. 44 (2016), no. 3, 1165–1192. MR 3485957, DOI 10.1214/15-AOS1401
- Yongxin Chen, Giovanni Conforti, and Tryphon T. Georgiou, Measure-valued spline curves: an optimal transport viewpoint, SIAM J. Math. Anal. 50 (2018), no. 6, 5947–5968. MR 3881237, DOI 10.1137/18M1166249
- Yongxin Chen, Tryphon T. Georgiou, and Allen Tannenbaum, Vector-valued optimal mass transport, SIAM J. Appl. Math. 78 (2018), no. 3, 1682–1696. MR 3814037, DOI 10.1137/17M1130897
- Krzysztof J. Ciosmak, Optimal transport of vector measures, Calc. Var. Partial Differential Equations 60 (2021), no. 6, Paper No. 230, 22. MR 4314146, DOI 10.1007/s00526-021-02095-2
- Hans Crauel, Random probability measures on Polish spaces, Stochastics Monographs, vol. 11, Taylor & Francis, London, 2002. MR 1993844
- Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos, Strong duality for a multiple-good monopolist, Econometrica 85 (2017), no. 3, 735–767. MR 3664178, DOI 10.3982/ECTA12618
- H. De March, Entropic approximation for multi-dimensional martingale optimal transport, Preprint, arXiv:1812.11104, 2018.
- Hadrien De March and Nizar Touzi, Irreducible convex paving for decomposition of multidimensional martingale transport plans, Ann. Probab. 47 (2019), no. 3, 1726–1774. MR 3945758, DOI 10.1214/18-AOP1295
- D. Delacrétaz, S. D. Kominers, and A. Teytelboym, Refugee resettlement, University of Oxford Department of Economics Working Paper, 2016.
- Freddy Delbaen, Commonotonicity and time-consistency for Lebesgue-continuous monetary utility functions, Finance Stoch. 25 (2021), no. 3, 597–614. MR 4283313, DOI 10.1007/s00780-021-00459-2
- Claude Dellacherie and Paul-André Meyer, Probabilities and potential. B, North-Holland Mathematics Studies, vol. 72, North-Holland Publishing Co., Amsterdam, 1982. Theory of martingales; Translated from the French by J. P. Wilson. MR 745449
- P. Dybvig, Distributional analysis of portfolio choice, J. Bus. 61 (1988), no. 3, 369–393.
- P. Embrechts, G. Puccetti, and L. Rüschendorf, Model uncertainty and VaR aggregation, J. Banking Finance 37 (2013), no. 8, 2750–2764.
- Ivar Ekeland, Notes on optimal transportation, Econom. Theory 42 (2010), no. 2, 437–459. MR 2564444, DOI 10.1007/s00199-008-0426-9
- Hans Föllmer and Alexander Schied, Stochastic finance, De Gruyter Graduate, De Gruyter, Berlin, 2016. An introduction in discrete time; Fourth revised and extended edition of [ MR1925197]. MR 3859905, DOI 10.1515/9783110463453
- Shmuel Friedland, Simultaneous similarity of matrices, Adv. in Math. 50 (1983), no. 3, 189–265. MR 724475, DOI 10.1016/0001-8708(83)90044-0
- Alfred Galichon, Optimal transport methods in economics, Princeton University Press, Princeton, NJ, 2016. MR 3586373, DOI 10.1515/9781400883592
- A. Galichon, P. Henry-Labordère, and N. Touzi, A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options, Ann. Appl. Probab. 24 (2014), no. 1, 312–336. MR 3161649, DOI 10.1214/13-AAP925
- Wilfrid Gangbo and Robert J. McCann, The geometry of optimal transportation, Acta Math. 177 (1996), no. 2, 113–161. MR 1440931, DOI 10.1007/BF02392620
- Nikita A. Gladkov, Alexander V. Kolesnikov, and Alexander P. Zimin, On multistochastic Monge-Kantorovich problem, bitwise operations, and fractals, Calc. Var. Partial Differential Equations 58 (2019), no. 5, Paper No. 173, 33. MR 4010649, DOI 10.1007/s00526-019-1610-4
- Nikita A. Gladkov, Alexander V. Kolesnikov, and Alexander P. Zimin, The multistochastic Monge-Kantorovich problem, J. Math. Anal. Appl. 506 (2022), no. 2, Paper No. 125666, 82. MR 4318841, DOI 10.1016/j.jmaa.2021.125666
- I. J. Good, On the independence of quadratic expressions, J. Roy. Statist. Soc. Ser. B 25 (1963), 377–382. MR 168076
- S. Gover, Duality theorems and vector measures in optimal transportation theory, Doctoral Dissertation, Technion—Israel Institute of Technology, 2020.
- Gaoyue Guo and Jan Obłój, Computational methods for martingale optimal transport problems, Ann. Appl. Probab. 29 (2019), no. 6, 3311–3347. MR 4047982, DOI 10.1214/19-AAP1481
- L. P. Hansen and T. J. Sargent, Robust control and model uncertainty, Amer. Econom. Rev. 91 (2001), no. 2, 60–66.
- Pierre Henry-Labordère, Model-free hedging, Chapman & Hall/CRC Financial Mathematics Series, CRC Press, Boca Raton, FL, 2017. A martingale optimal transport viewpoint. MR 3699668
- Francis Hirsch, Christophe Profeta, Bernard Roynette, and Marc Yor, Peacocks and associated martingales, with explicit constructions, Bocconi & Springer Series, vol. 3, Springer, Milan; Bocconi University Press, Milan, 2011. MR 2808243, DOI 10.1007/978-88-470-1908-9
- Harry Joe, Dependence modeling with copulas, Monographs on Statistics and Applied Probability, vol. 134, CRC Press, Boca Raton, FL, 2015. MR 3328438
- A. M. Mathai and Serge B. Provost, Quadratic forms in random variables, Statistics: Textbooks and Monographs, vol. 126, Marcel Dekker, Inc., New York, 1992. Theory and applications. MR 1192786
- Fabio Maccheroni, Massimo Marinacci, and Aldo Rustichini, Ambiguity aversion, robustness, and the variational representation of preferences, Econometrica 74 (2006), no. 6, 1447–1498. MR 2268407, DOI 10.1111/j.1468-0262.2006.00716.x
- Georg Nöldeke and Larry Samuelson, The implementation duality, Econometrica 86 (2018), no. 4, 1283–1324. MR 3843490, DOI 10.3982/ECTA13307
- Marcel Nutz and Florian Stebegg, Canonical supermartingale couplings, Ann. Probab. 46 (2018), no. 6, 3351–3398. MR 3857858, DOI 10.1214/17-AOP1249
- Marcel Nutz and Ruodu Wang, The directional optimal transport, Ann. Appl. Probab. 32 (2022), no. 2, 1400–1420. MR 4414708, DOI 10.1214/21-aap1712
- Marcel Nutz, Ruodu Wang, and Zhenyuan Zhang, Martingale transports and Monge maps, Ann. Appl. Probab. 34 (2024), no. 6, 5556–5577. MR 4839632, DOI 10.1214/24-aap2099
- Brendan Pass, Multi-marginal optimal transport: theory and applications, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 6, 1771–1790. MR 3423275, DOI 10.1051/m2an/2015020
- G. Peyré and M. Cuturi, Computational optimal transport: with applications to data science, Found. Trends Mach. Learn. 11 (2019), no. 5–6, 355–607.
- Aldo Pratelli, On the equality between Monge’s infimum and Kantorovich’s minimum in optimal mass transportation, Ann. Inst. H. Poincaré Probab. Statist. 43 (2007), no. 1, 1–13 (English, with English and French summaries). MR 2288266, DOI 10.1016/j.anihpb.2005.12.001
- J. Quiggin, Generalized expected utility theory: the rank-dependent model, Kluwer, the Netherlands, 1993.
- Svetlozar T. Rachev and Ludger Rüschendorf, Mass transportation problems. Vol. II, Probability and its Applications (New York), Springer-Verlag, New York, 1998. Applications. MR 1619171
- Marzena Rostek, Quantile maximization in decision theory, Rev. Econom. Stud. 77 (2010), no. 1, 339–371. MR 2599290, DOI 10.1111/j.1467-937X.2009.00564.x
- L. Rüschendorf, On the minimum discrimination information theorem, Statist. Decisions suppl. 1 (1984), 263–283. Recent results in estimation theory and related topics. MR 785212
- Ludger Rüschendorf, Bounds for distributions with multivariate marginals, Stochastic orders and decision under risk (Hamburg, 1989) IMS Lecture Notes Monogr. Ser., vol. 19, Inst. Math. Statist., Hayward, CA, 1991, pp. 285–310. MR 1196061, DOI 10.1214/lnms/1215459862
- Ludger Rüschendorf, Mathematical risk analysis, Springer Series in Operations Research and Financial Engineering, Springer, Heidelberg, 2013. Dependence, risk bounds, optimal allocations and portfolios. MR 3051756, DOI 10.1007/978-3-642-33590-7
- Ernest K. Ryu, Yongxin Chen, Wuchen Li, and Stanley Osher, Vector and matrix optimal mass transport: theory, algorithm, and applications, SIAM J. Sci. Comput. 40 (2018), no. 5, A3675–A3698. MR 3870089, DOI 10.1137/17M1163396
- Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
- Vladimir V. Sergeichuk, Unitary and Euclidean representations of a quiver, Linear Algebra Appl. 278 (1998), no. 1-3, 37–62. MR 1637319, DOI 10.1016/S0024-3795(98)00006-8
- Jie Shen, Yi Shen, Bin Wang, and Ruodu Wang, Distributional compatibility for change of measures, Finance Stoch. 23 (2019), no. 3, 761–794. MR 3968284, DOI 10.1007/s00780-019-00393-4
- H. Mete Soner, Nizar Touzi, and Jianfeng Zhang, Quasi-sure stochastic analysis through aggregation, Electron. J. Probab. 16 (2011), no. 67, 1844–1879. MR 2842089, DOI 10.1214/EJP.v16-950
- V. Strassen, The existence of probability measures with given marginals, Ann. Math. Statist. 36 (1965), 423–439. MR 177430, DOI 10.1214/aoms/1177700153
- Erik Torgersen, Comparison of statistical experiments, Encyclopedia of Mathematics and its Applications, vol. 36, Cambridge University Press, Cambridge, 1991. MR 1104437, DOI 10.1017/CBO9780511666353
- Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
- Cédric Villani, Optimal transport, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag, Berlin, 2009. Old and new. MR 2459454, DOI 10.1007/978-3-540-71050-9
- Vladimir Vovk and Ruodu Wang, E-values: calibration, combination and applications, Ann. Statist. 49 (2021), no. 3, 1736–1754. MR 4298879, DOI 10.1214/20-aos2020
- Bin Wang and Ruodu Wang, Joint mixability, Math. Oper. Res. 41 (2016), no. 3, 808–826. MR 3520751, DOI 10.1287/moor.2015.0755
- Ruodu Wang and Johanna F. Ziegel, Scenario-based risk evaluation, Finance Stoch. 25 (2021), no. 4, 725–756. MR 4318899, DOI 10.1007/s00780-021-00460-9
- Gershon Wolansky, Optimal transport—a semi-discrete approach, De Gruyter Series in Nonlinear Analysis and Applications, vol. 37, De Gruyter, Berlin, [2021] ©2021. MR 4759985
Bibliographic Information
- Ruodu Wang
- Affiliation: Department of Statistics and Actuarial Science, University of Waterloo, Canada
- MR Author ID: 880329
- ORCID: 0000-0003-3849-4555
- Email: wang@uwaterloo.ca
- Zhenyuan Zhang
- Affiliation: Department of Mathematics, Stanford University
- MR Author ID: 1404846
- Email: zzy@stanford.edu
- Received by editor(s): June 20, 2023
- Received by editor(s) in revised form: October 30, 2024, and December 20, 2024
- Published electronically: May 8, 2025
- Additional Notes: The first author was financially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC, RGPIN-2018-03823, RGPAS-2018-522590).
- © Copyright 2025 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
- MSC (2020): Primary 49Q22, 60E15, 46G10
- DOI: https://doi.org/10.1090/tran/9393