1.1. General duality 21 ton of coal at place x, and a price ψ(y) for unloading it at destination y. I will set the prices in such a way that your financial interest will be to let me handle all your transportation! Indeed, you can check very easily that for any x and y, the sum ϕ(x)+ψ(y) will always be less that the cost c(x, y) (in order to achieve this goal, I am even ready to give financial compensations for some places, in the form of negative prices!)”. Of course you accept the deal. Now, what Kantorovich’s duality tells you is that if this shipper is clever enough, then he can arrange the prices in such a way that you will pay him (almost) as much as you would have been ready to spend by the other method. 1.1.4. Preliminary observation. We shall first prove a subpart of The- orem 1.3, which is completely elementary and should at least make the Kantorovich duality appear less surprising. Proposition 1.5 (Easy part of the Kantorovich duality). Under the same assumptions as in Theorem 1.3, (1.5) sup Φc∩Cb J(ϕ, ψ) ≤ sup Φc∩L1 J(ϕ, ψ) ≤ inf Π(μ,ν) I[π]. Proof. The inequality on the left of (1.5) is trivial, since Cb(X) × Cb(Y ) ⊂ L1(dμ) × L1(dν). So we only care about the inequality on the right. Let (ϕ, ψ) in Φc ∩ L1, and let π be any element of Π(μ, ν). Then, by definition of Π, J(ϕ, ψ) = X ϕ dμ + Y ψ dν = X×Y ϕ(x) + ψ(y) dπ(x, y). But inequality (1.3) holds dπ(x, y)-almost everywhere. Indeed, let Nx, Ny be measurable sets such that μ[Nx] = 0, ν[Ny] = 0, and inequality (1.3) holds for (x, y) ∈ Nx c × Ny c. Since π has marginals μ and ν, we can write π[Nx×Y ] = μ[Nx] = 0, π[X×Ny] = ν[Ny] = 0, and hence π[(Nx×Ny c c)c] = 0. As a consequence, (1.6) X×Y ϕ(x) + ψ(y) dπ(x, y) ≤ X×Y c(x, y) dπ(x, y) = I[π]. The inequality (1.5) follows from (1.6) upon taking the supremum on the left-hand side, and the infimum on the right-hand side. Remark 1.6. It follows from Proposition 1.5 that the duality supΦc∩Cb J = inf I automatically implies supΦc∩L1 J = supΦc∩Cb J. 1.1.5. A formal proof. Let us now give a formal proof of Theorem 1.3. The idea, which is standard in problems of this kind, is to rewrite the con- strained infimum problem as an inf sup problem, and exchange the two operations by formally applying a minimax principle, i.e. replacing an

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.