Multi‐to One‐Dimensional Optimal Transport |
| |
| Authors: | Pierre‐André Chiappori Robert J McCann Brendan Pass |
| |
| Institution: | 1. Department of Economics Columbia, University 1009A International Affairs Building, 420 West 118th St, New York, NY, USA;2. Department of Mathematics, University of Toronto Bahen Centre, 40 St. George St., Room 6290, Toronto, Ontario, CANADA;3. Department of Mathematical and Statistical, Sciences University of Alberta, Edmonton, Alberta, CANADA |
| |
| Abstract: | We consider the Monge‐Kantorovich problem of transporting a probability density on  to another on the line, so as to optimize a given cost function. We introduce a nestedness criterion relating the cost to the densities, under which it becomes possible to solve this problem uniquely by constructing an optimal map one level set at a time. This map is continuous if the target density has connected support. We use level‐set dynamics to develop and quantify a local regularity theory for this map and the Kantorovich potentials solving the dual linear program. We identify obstructions to global regularity through examples. More specifically, fix probability densities f and g on open sets  and  with  . Consider transporting f onto g so as to minimize the cost  . We give a nondegeneracy condition on  that ensures the set of x paired with g‐a.e.] y ∈ Y lie in a codimension‐n submanifold of X. Specializing to the case m > n = 1, we discover a nestedness criterion relating s to (f,g) that allows us to construct a unique optimal solution in the form of a map  . When  and g and f are bounded, the Kantorovich dual potentials (u,υ) satisfy  , and the normal velocity V of  with respect to changes in y is given by  . Positivity of V locally implies a Lipschitz bound on f; moreover,  if  intersects  transversally. On subsets where this nondegeneracy, positivity, and transversality can be quantified, for each integer  the norms of  and  are controlled by these bounds,  , and the smallness of  . We give examples showing regularity extends from $X to part of  , but not from Y to  . We also show that when s remains nested for all (f,g), the problem in  reduces to a supermodular problem in  . © 2017 Wiley Periodicals, Inc. |
| |
| Keywords: | |
|
|
to another on the line, so as to optimize a given cost function. We introduce a nestedness criterion relating the cost to the densities, under which it becomes possible to solve this problem uniquely by constructing an optimal map one level set at a time. This map is continuous if the target density has connected support. We use level‐set dynamics to develop and quantify a local regularity theory for this map and the Kantorovich potentials solving the dual linear program. We identify obstructions to global regularity through examples. More specifically, fix probability densities f and g on open sets 
and 
with 
. Consider transporting f onto g so as to minimize the cost 
. We give a nondegeneracy condition on 
that ensures the set of x paired with g‐a.e.] y ∈ Y lie in a codimension‐n submanifold of X. Specializing to the case m > n = 1, we discover a nestedness criterion relating s to (f,g) that allows us to construct a unique optimal solution in the form of a map 
. When 
and g and f are bounded, the Kantorovich dual potentials (u,υ) satisfy 
, and the normal velocity V of 
with respect to changes in y is given by 
. Positivity of V locally implies a Lipschitz bound on f; moreover, 
if 
intersects 
transversally. On subsets where this nondegeneracy, positivity, and transversality can be quantified, for each integer 
the norms of 
and 
are controlled by these bounds, 
, and the smallness of 
. We give examples showing regularity extends from $X to part of 
, but not from Y to 
. We also show that when s remains nested for all (f,g), the problem in 
reduces to a supermodular problem in 
. © 2017 Wiley Periodicals, Inc.