1. Formulation of the optimal transportation problem 5 This problem has been famous for a long time: for its solution the Acad- emy of Paris offered a prize [103]. It was claimed soon after by Appell, who wrote a beautiful treatise [16] on the subject. In these notes, we shall use the name “Monge-Kantorovich problem” for either Kantorovich’s or Monge’s minimization problem. Example (Dirac mass). Assume that ν is a Dirac mass: ν = δa. Then there is a unique element in Π(μ, ν) (all the mass should be transported to a), and obviously, (11) Tc(μ, δa) = X c(x, a) dμ(x). Example (The discrete case). Suppose X and Y are discrete spaces where all points have the same mass: μ = 1 n n i=1 δxi , ν = 1 n n j=1 δyj . Any measure in Π(μ, ν) can clearly be represented as a bistochastic n × n matrix π = (πij)i,j. Here by bistochasticity we mean that all the πij are nonnegative and that ∀j, i πij = 1 ∀i, j πij = 1. So in this case the Kantorovich problem reduces to inf ⎧ ⎨ ⎩n 1 ij πij c(xi,yj) π ∈ Bn⎭ ⎫ ⎬ , with Bn denoting the set of bistochastic n × n matrices. This is a linear minimization problem on the bounded convex set Bn ⊂ Mn(R). By Choquet’s theorem, we know that this problem admits solu- tions which are extremal points of Bn, i.e. elements of Bn which cannot be written as a nontrivial convex combination of two points in Bn. By Birkhoff’s theorem, these extremal points are the permutation matri- ces, i.e. those matrices such that πij = δj,σ(i) for some permutation σ of {1,...,n} (here δjk is the Kronecker symbol: δjk = 1 if j = k, 0 otherwise). Thus, optimal transference plans in Kantorovich’s problem coincide with solutions of Monge’s problem inf 1 n i c(xi,yσ(i)) σ ∈ Sn

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.