2 Introduction In this book a central question is the following Basic problem: How to realize the transportation at minimal cost? Before studying this question, we have to make clear what a way of transportation, or a transference plan, is. We shall model transference plans by probability measures π on the product space X × Y . Informally, dπ(x, y) measures the amount of mass transferred from location x to location y. We do not a priori exclude the possibility that some mass located at point x may be split into several parts (several possible destination y’s). For a transference plan π ∈ P (X × Y ) to be admissible, it is of course necessary that all the mass taken from point x coincide with dμ(x), and that all the mass transferred to y coincide with dν(y). This means Y dπ(x, y) = dμ(x), X dπ(x, y) = dν(y). More rigorously, we require that (1) π[A × Y ] = μ[A], π[X × B] = ν[B], for all measurable subsets A of X and B of Y . This is equivalent to stating that for all functions ϕ, ψ in a suitable class of test functions, (2) X×Y ϕ(x) + ψ(y) dπ(x, y) = X ϕ(x) dμ(x) + Y ψ(y) dν(y). In general, the natural set of admissible test functions for (ϕ, ψ) is L1(dμ) × L1(dν), or equivalently L∞(dμ) × L∞(dν). In most situations of interest, this class can be narrowed to just Cb(X) × Cb(Y ), or C0(X) × C0(Y ) we shall discuss this more precisely later on. Those probability measures π that satisfy (1) are said to have marginals μ and ν, and will be the admissible transference plans. We shall denote the set of all such probability measures by (3) Π(μ, ν) = π ∈ P (X × Y ) (1) holds for all measurable A, B . This set is always nonempty, since the tensor product μ ⊗ ν lies in Π(μ, ν) (this corresponds to the most stupid transportation plan that one may imag- ine: any piece of sand, regardless of its location, is distributed over the entire hole, proportionally to the depth). We now have a clear mathematical definition of our basic problem. In this form, it is known as Kantorovich’s optimal transportation problem: (4) Minimize I[π] = X×Y c(x, y) dπ(x, y) for π ∈ Π(μ, ν).

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.