1. Formulation of the optimal transportation problem 3 This minimization problem was studied in the forties by Kantorovich [164, 165] — who was awarded a Nobel prize for related work in econom- ics! That the optimal transference problem is related to basic questions in economics becomes clear if one thinks of μ as a density of production units, and of ν as a density of consumers. For a given transference plan π, the nonnegative (possibly infinite) quantity I[π] will be called the total transportation cost associated to π. The optimal transportation cost between μ and ν is the value (5) Tc(μ, ν) = inf π∈Π(μ,ν) I[π]. The optimal π’s, i.e. those such that I[π] = Tc(μ, ν), if they exist, will be called optimal transference plans. Readers with probabilistic minds will already have translated the Kan- torovich problem into its equivalent Probabilistic interpretation: Given two probability measures μ and ν, minimize the expectation (6) I(U, V ) = E [c(U, V )] over all pairs (U, V ) of random variables U in X, and V in Y , such that law(U) = μ, law(V ) = ν. For those who are not so familiar with basic probability theory, we recall that a random variable U in X is a measurable map with values in X, defined on a probability space Ω equipped with a probability measure P that the law of U is the probability measure μ on X defined by μ[A] = P[U −1(A)] and that the expectation stands for the integral with respect to P. Transference plans π ∈ Π(μ, ν) are all possible laws of the couple (U, V ). Such a π is often said to be the joint law of the random variables U and V one also says that it constitutes a coupling of U and V . As we shall explain in the next section, Kantorovich’s problem is a re- laxed version of the original mass transportation problem considered by Monge [195]. Monge’s problem is just the same as Kantorovich’s, except for one thing: it is additionally required that no mass be split. In other words, to each location x is associated a unique destination y. In terms of random variables, this requirement means that we ask for V to be a function of U in (6). In terms of transference plans, it means that we ask for π in (4) to have the special form (7) dπ(x, y) = dπT (x, y) ≡ dμ(x) δ[y = T (x)],

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2003 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.