38 1. The Kantorovich Duality to (x + y)/2 and simultaneously (x + y)/2 to y. Show that this strategy can be implemented with an admissible transshipment plan, and express it in terms of image measures of π. Make a schematic picture of how π is modified by this transformation. Show that the cost has been lowered by a factor 2. Deduce that the optimal transshipment cost is 0, which of course is not attained unless μ = ν. Show that the conclusion is still valid for any power |x − y|p, p 1, or more generally as soon as c(x, y) = φ(|x − y|), where φ is nondecreasing on R+, φ(0) = 0, φ (0) = 0. 1.2.3. Divergence formulation. There is yet another way to rewrite the Kantorovich-Rubinstein theorem in Rn, when the distance d is the standard Euclidean distance. Indeed, in this case, the condition ϕ Lip ≤ 1 can also be rewritten as ∇ϕ L∞ ≤ 1. By a new minimax argument which is left as an exercise, we find a new dual formulation (well, dual of the dual): (1.22) Td(μ, ν) = inf σ L1(Ê n ) ∇ · σ = μ − ν . Here ∇· denotes the divergence operator, acting on D (Rn). This formulation is very useful for numerical simulations (“minimal network flow problem”), but also for theoretical purposes, as we shall explain later on. A similar for- mulation would be available on Riemannian manifolds, with a cost function equal to the geodesic distance. While it is rather easy to understand the models underlying the standard transportation and the transshipment formulations, the divergence formula- tion may seem rather obscure to the non-expert reader. The following is an attempt to make the identity (1.22) more intuitive. Consider a reorganiza- tion in an ants’ nest, where a huge heap of pine needles should be reshaped and transported. Say that μ is a probability measure describing the heap as it stands at the beginning of the reorganization process, and ν the heap as it should be at the end. For that purpose, many, many needles have to be transported from one place to another. All ants participate and move needles around in all directions, in a seemingly disorganized way. But in fact, each of them keeps going in just one direction, with the same speed than it had at the beginning. The whole transportation process goes from t = 0 to t = 1 minute. All the ants have been assigned initial velocities in such a way that the height of the initial heap decreases at a constant rate, and similarly the height of the final heap increases at a constant rate. In mathematical words, the probability measure describing the needles at time t is tμ + (1 − t)ν. Now, if one stares at an element of volume dx around one given place x in the ants’ nest, at each time t one sees an ant carrying one or more needles, with total mass ρ(t, x) and this ant has a certain speed

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.