On the Structure of Optimal Transportation Plans between Discrete Measures

It is well known that the optimal transportation plan between two probability measures mu and nu is induced by a transportation map whenever mu is an absolutely continuous measure supported over a compact set in the Euclidean space and the cost function is a strictly convex function of the Euclidean distance. However, when mu and nu are both discrete, this result is generally false. In this paper, we prove that, given any pair of discrete probability measures and a cost function, there exists an optimal transportation plan that can be expressed as the sum of two deterministic plans, i.e., plans induced by transportation maps. As an application, we estimate the infinity-Wasserstein distance between two discrete probability measures mu and nu with the p-Wasserstein distance, times a constant depending on mu, on nu, and on the fixed cost function.