Multi- to one-dimensional matching
The stable marriage problem with transferable utility is well-known to be equivalent to a Monge-Kantorovich optimal transportation problem. Motivated by the possibility that the husbands (but not the wives) can be described by a single variable, we consider the problem of transporting a probability density on Rm 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 a local regularity theory for this map and the Kantorovich potentials solving the dual linear program. We identify obstructions to global regularity through examples.
This represents joint work with Pierre-Andre Chiappori and Brendan Pass.