Introduction

This chapter, which is an accompanying paper to [BLS09], consists of two parts. In Section 9.2 we present a version of Fenchel's perturbation method for the duality theory of the Monge–Kantorovich problem of optimal transport. The treatment is elementary as we suppose that the spaces (X, μ), (Y, ν), on which the optimal transport problem [Vil03, Vil09] is defined, simply equal the finite set {1, …, N} equipped with uniform measure. In this setting the optimal transport problem reduces to a finite-dimensional linear programming problem.

The purpose of this first part of the paper is rather didactic: it should stress some features of the linear programming nature of the optimal transport problem, which carry over also to the case of general Polish spaces X, Y equipped with Borel probability measures μ, ν, and general Borel measurable cost functions c : X × Y → [0, ∞]. This general setting is analysed in detail in [BLS09]; Section 9.2 may serve as a motivation for the arguments in the proof of Theorems 1.2 and 1.7 of [BLS09] which pertain to the general duality theory.

The second – and longer – part of the paper, consisting of Sections 9.3 and 9.4, is of a quite different nature. Section 9.3 is devoted to illustrating a technical feature of [BLS09, Theorem 4.2] by an explicit example.