×

A multi-objective interpretation of optimal transport. (English) Zbl 1396.90045

Summary: This paper connects discrete optimal transport to a certain class of multi-objective optimization problems. In both settings, the decision variables can be organized into a matrix. In the multi-objective problem, the notion of Pareto efficiency is defined in terms of the objectives together with nonnegativity constraints and with equality constraints that are specified in terms of column sums. A second set of equality constraints, defined in terms of row sums, is used to single out particular points in the Pareto-efficient set which are referred to as “balanced solutions.” Examples from several fields are shown in which this solution concept appears naturally. Balanced solutions are shown to be in one-to-one correspondence with solutions of optimal transport problems. As an example of the use of alternative interpretations, the computation of solutions via regularization is discussed.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C29 Multi-objective and goal programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
91B14 Social choice
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Rachev, S.T., Rüschendorf, L.: Mass Transportation Problems: Volume I: Theory. Springer, New York (1998) · Zbl 0990.60500
[2] Rachev, S.T., Rüschendorf, L.: Mass Transportation Problems: Volume II: Applications. Springer, New York (1998) · Zbl 0990.60500
[3] Villani, C.: Topics in Optimal Transportation. No. 58 in Graduate Studies in Mathematics. American Mathematical Society, Providence, RI (2003)
[4] Villani, C.: Optimal Transport: Old and New. Springer, Berlin (2008) · Zbl 1156.53003
[5] Monge, G.: Mémoire sur la théorie des déblais et des remblais. In: Histoire de l’Académie Royale des Sciences avec les mémoires de mathématique et de physique tirés des registres de cette Académie, pp. 666-705 (1781) · Zbl 1335.90068
[6] Kantorovich, L.V.: On the translocation of masses. Doklady Akademii Nauk USSR 37, 199-201 (1942). In: Russian. English translation in Journal of Mathematical Sciences 133, 1381-1382 (2006) · Zbl 1080.49507
[7] Fréchet, M.: Sur les tableaux de corrélation dont les marges sont données. Annales de l’Université de Lyon. 3. sér., Sciences. Section A: Sciences mathématiques et astronomie 14, 53-77 (1951) · Zbl 0548.34034
[8] Santambrogio, F.: Optimal Transport for Applied Mathematicians. Birkhäuser, New York (2015) · Zbl 1401.49002 · doi:10.1007/978-3-319-20828-2
[9] Galichon, A.: Optimal Transport Methods in Economics. Princeton University Press, Princeton, NJ (2016) · doi:10.1515/9781400883592
[10] Gale, D.: Fair division of a random harvest. Technical Report ORC 77-21, Operations Research Center, UC Berkeley (1977) · Zbl 0198.23401
[11] Gale, D.; Sobel, J.; Green, JR (ed.); Scheinkman, JA (ed.), Fair division of a random harvest: the finite case, 193-198 (1979), New York · doi:10.1016/B978-0-12-298750-2.50016-2
[12] Bühlmann, H., Jewell, W.S.: Optimal risk exchanges. ASTIN Bull. 10, 243-262 (1979) · Zbl 0679.62090 · doi:10.1017/S0515036100005882
[13] Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Advances in Neural Information Processing Systems, pp. 2292-2300. MIT Press, Cambridge, MA (2013) · Zbl 0856.90091
[14] Benamou, J.D., Carlier, G., Cuturi, M., Nenna, L., Peyré, G.: Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comput. 37, A1111-A1138 (2015) · Zbl 1319.49073 · doi:10.1137/141000439
[15] Brualdi, R.A., Parter, S.V., Schneider, H.: The diagonal equivalence of a nonnegative matrix to a stochastic matrix. J. Math. Anal. Appl. 16, 31-50 (1966) · Zbl 0231.15017 · doi:10.1016/0022-247X(66)90184-3
[16] Lemmens, B., Nussbaum, R.: Nonlinear Perron-Frobenius theory. In: Cambridge Tracts in Mathematics, vol. 189. Cambridge University Press, Cambridge (2012) · Zbl 1246.47001
[17] Pazdera, J., Schumacher, J.M., Werker, B.J.M.: The composite iteration algorithm for finding efficient and financially fair risk-sharing rules. J. Math. Econ. 72, 122-133 (2017) · Zbl 1394.91226
[18] Brams, S.J., Taylor, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, New York (1996) · Zbl 0991.91019 · doi:10.1017/CBO9780511598975
[19] Moulin, H.J.: Fair Division and Collective Welfare. MIT Press, Cambridge, MA (2003)
[20] Foley, D.: Resource allocation and the public sector. Yale Econ. Essays 7, 45-98 (1967)
[21] Nash, J.F.: The bargaining problem. Econometrica 18, 155-162 (1950) · Zbl 1202.91122 · doi:10.2307/1907266
[22] Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2006) · Zbl 0956.90039
[23] Isermann, H.: The enumeration of all efficient solutions for a linear multiple-objective transportation problem. Naval Res. Logist. 26, 123-139 (1979) · Zbl 0396.90060 · doi:10.1002/nav.3800260112
[24] Balasko, Y.: Budget-constrained Pareto-efficient allocations. J. Econ. Theory 21, 359-379 (1979) · Zbl 0427.90014 · doi:10.1016/0022-0531(79)90046-2
[25] Gale, D., Sobel, J.: On optimal distribution of output from a jointly owned resource. J. Math. Econ. 9, 51-59 (1982) · Zbl 0471.90011 · doi:10.1016/0304-4068(82)90016-7
[26] Kleinberg, J., Tardos, É.: Balanced outcomes in social exchange networks. In: Proceedings of the Fortieth ACM Symposium on Theory of Computing (STOC 2008, held in Victoria, BC, Canada), pp. 295-304. ACM, New York (2008) · Zbl 1231.91120
[27] Myerson, R.B.: Game Theory. Analysis of Conflict. Harvard University Press, Cambridge, MA (1991) · Zbl 0729.90092
[28] Gardner, M.: Aha! Insight. Freeman, New York (1978)
[29] Michie, D., Spiegelhalter, D.J., Taylor, C.C. (eds.): Machine Learning, Neural and Statistical Classification. Ellis Horwood, Chichester (1994) · Zbl 0827.68094
[30] Rotar, V.I.: Actuarial Models. The Mathematics of Insurance. Chapman & Hall/CRC, Boca Raton (2007) · Zbl 1117.62118
[31] Isermann, H.: Proper efficiency and the linear vector maximum problem. Oper. Res. 22, 189-191 (1974) · Zbl 0274.90024 · doi:10.1287/opre.22.1.189
[32] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1998) · Zbl 0970.90052
[33] Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Appl. Math. 70, 95-161 (1996) · Zbl 0856.90091 · doi:10.1016/0166-218X(95)00103-X
[34] Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7, 200-217 (1967) · Zbl 0186.23807 · doi:10.1016/0041-5553(67)90040-7
[35] Kruithof, J.: Telefoonverkeersrekening. De Ingenieur 52, E15-E25 (1937). In: Dutch. English translation: Telephone traffic calculus, Technical report, Bell Telephone Manufacturing Company, Antwerp (January 1952)
[36] Deming, W.E., Stephan, F.F.: On a least squares adjustment of a sampled frequency table when the expected marginal totals are known. Ann. Math. Stat. 11, 427-444 (1940) · Zbl 0024.05502 · doi:10.1214/aoms/1177731829
[37] Brown, D.T.: A note on approximations to discrete probability distributions. Inf. Control 2, 386-392 (1959) · Zbl 0117.14804 · doi:10.1016/S0019-9958(59)80016-4
[38] Sinkhorn, R.: Diagonal equivalence to matrices with prescribed row and column sums. Am. Math. Mon. 74, 402-405 (1967) · Zbl 0166.03702 · doi:10.2307/2314570
[39] Ireland, C.T., Kullback, S.: Contingency tables with given marginals. Biometrika 55, 179-188 (1968) · Zbl 0155.26701 · doi:10.1093/biomet/55.1.179
[40] Fienberg, S.E.: An iterative procedure for estimation in contingency tables. Ann. Math. Stat. 41, 907-917 (1970) · Zbl 0198.23401 · doi:10.1214/aoms/1177696968
[41] Csiszár, \[I.: II\]-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3, 146-158 (1975) · Zbl 0318.60013 · doi:10.1214/aop/1176996454
[42] Rüschendorf, L.: Convergence of the iterative proportional fitting procedure. Ann. Stat. 23, 1160-1174 (1995) · Zbl 0851.62038 · doi:10.1214/aos/1176324703
[43] Bauschke, H.H., Lewis, A.S.: Dykstra’s algorithm with Bregman projections: a convergence proof. Optimization 48, 409-427 (2000) · Zbl 0992.90052 · doi:10.1080/02331930008844513
[44] Oshime, Y.: An extension of Morishima’s nonlinear Perron-Frobenius theorem. J. Math. Kyoto Univ. 23, 803-830 (1983) · Zbl 0548.34034 · doi:10.1215/kjm/1250521436
[45] Peyré, G.: Entropic approximation of Wasserstein gradient flows. SIAM J. Imaging Sci. 8, 2323-2351 (2015) · Zbl 1335.90068 · doi:10.1137/15M1010087
[46] Stephan, F.F.: An iterative method of adjusting sample frequency tables when expected marginal totals are known. Ann. Math. Stat. 13, 166-178 (1942) · Zbl 0060.31505 · doi:10.1214/aoms/1177731604
[47] Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pac. J. Math. 21, 343-348 (1967) · Zbl 0152.01403 · doi:10.2140/pjm.1967.21.343
[48] Franklin, J., Lorenz, J.: On the scaling of multidimensional matrices. Linear Algebra Appl. 114, 717-735 (1989) · Zbl 0674.15001 · doi:10.1016/0024-3795(89)90490-4
[49] Borwein, J.M., Lewis, A.S., Nussbaum, R.D.: Entropy minimization, DAD problems, and doubly stochastic kernels. J. Funct. Anal. 123, 264-307 (1994) · Zbl 0815.15021 · doi:10.1006/jfan.1994.1089
[50] Georgiou, T.T., Pavon, M.: Positive contraction mappings for classical and quantum Schrödinger systems. J. Math. Phys. 56(033301), 1-24 (2015) · Zbl 1322.81057
[51] Birkhoff, G.: Extensions of Jentzsch’s theorem. Trans. Am. Math. Soc. 85, 219-227 (1957) · Zbl 0079.13502
[52] Bushell, P.J.: Hilbert’s metric and positive contraction mappings in a Banach space. Arch. Ration. Mech. Anal. 52, 330-338 (1973) · Zbl 0275.46006 · doi:10.1007/BF00247467
[53] Menon, M.: Reduction of a matrix with positive elements to a doubly stochastic matrix. Proc. Am. Math. Soc. 18, 244-247 (1967) · Zbl 0153.05301 · doi:10.1090/S0002-9939-1967-0215873-6
[54] Nadler, S.B.: A note on an iterative test of Edelstein. Can. Math. Bull. 15, 381-386 (1972) · Zbl 0244.54027 · doi:10.4153/CMB-1972-070-7
[55] Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia, PA (1997) · Zbl 0863.65031 · doi:10.1137/1.9781611971453
[56] Pukelsheim, F.: Biproportional scaling of matrices and the iterative proportional fitting procedure. Ann. Oper. Res. 215, 269-283 (2014) · Zbl 1302.65114 · doi:10.1007/s10479-013-1468-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.