Frank Morgan

In Barcelona, Robert McCann talked about his work with Jonathan Korman and Christian Seis on optimal transportation with a constraint h(x,y) on the flow from x to y. A constant constraint h means that an x must be spread out over at least fraction 1/h of the target; there is not the capacity to send it all to the most desirable spot. Here we present a simplified extension of some of their results. 

1. Proposition. Consider a Riemannian manifold of say unit volume, with a transitive group of measure-preserving isometries, with cost of transportation c(x,y) increasing in distance and constant constraint 0 < h < ∞. Then optimal transportation is uniquely given by relating a point x to a geodesic ball about x of volume 1/h.

Note that the ball can have interesting topology, as on a torus for example.

Proof. By the constraint a point x must relate to a set of volume at least 1/h, and the geodesic ball minimizes cost among such. By the symmetry assumption, all balls of the same radius have the same volume, so the set related to a target point y is the ball about y with volume 1/h and the correspondence is admissible.

2. Proposition. Consider two Riemannian manifolds X, Y (or more generally two metric measure spaces) of say unit volume, with transportation cost c(x,y) and constant constraint h. Suppose that for for a point x in X, c(x,y) is negative for 1/h of the y’s in Y and positive for the rest, and for a point y in Y, c(x,y) is negative for 1/h of the x’s in X and positive for the rest (modulo sets of measure 0). Then the correspondence between points of negative cost uniquely provides optimal transportation under the constraint.

The proof is trivial: the correspondence minimizes cost.

Examples:

2.1. For integer h ≥ 2, let X consist of h equal-volume regions in Rⁿ such that the maximum diameter of a region is less than the minimum distance between regions. Let c(x,y) be a cost function on X×X increasing in distance. Then optimal transportation from X to X with constant constraint h relates the points of each region to itself. (To apply the Proposition, subtract a constant from the cost.)

2.2. For a centrally symmetric body in Rⁿ, cost c(x,y) = –2 x•y (which is equivalent to (x–y)² because its integral differs by a constant), and constraint h = 2, under optimal transportation x corresponds to y with x•y positive. In R¹ central symmetry is unnecessary as long as the origin is the median. Similarly for any cost with the same sign as –x•y. The analysis generalizes to any centrally symmetric probability measure on Rⁿ for which hyperplanes through the origin have measure 0 and to any probability measure on R¹.

2.3. For a planar region with h-fold rotational symmetry, such as a square (h=4), cost

c(x,y) = (cos π/h)|x||y| – x•y,

and constant constraint h, optimal transportation relates all points on a ray from the origin to a cone of angle π/h about that ray.

2.4. Such examples of optimal transportation from X_i to Y_i extend to optimal transportation from ΠX_i to ΠY_i with a cost which is negative if and only if the costs of the projections are all negative: optimal transportation with constraint h = Πh_i relates points of negative cost. In particular, Example 2.3 generalizes to a product of such actions on R²ⁿ with cost negative if and only if x_i•y_i ≥ (cos π/h_i)|x_i||y_i| for all i : optimal transportation with constant constraint h = Πh_i relates all points with projections on rays from the origin to a product of cones of angle π/h_i about the ray.

2.5. Such examples of optimal transportation from X to Y with cost c(x,y) extend to optimal transportation on warped products A×X, A×Y, as long as the cost c′(a,x,a,y) has the same sign as c(x,y). For example, for any 0 < h < ∞, Proposition 1 on the sphere, with cost c(x,y) = a|x||y| – x•y, with a chosen so that optimal transportation relates points of negative cost, extends to the ball, with points on a ray from the origin related to a cone of negative cost about that ray.

The following proposition is a generalization of McCann-Korman (Insights into Capacity Constrained Optimal Transport, Prop. 4.2).

3. Proposition. Let M₁, M₂ be subsets of Rⁿ or Riemannian manifolds with boundary or metric measure spaces of volume V. Let T_i be a measure-preserving map from M_i to M_i and let T = T₁×T₂. Let c(x,y) be a cost satisfying coT = -c. If density f h on M₁×M₂ provides optimal transportation from M₁ to M₂ with constant constraint h, then density f‘h’oT provides optimal transportation with constraint h’, where 1/h + 1/h’ = 1 and  f ‘ = 1-f.

Proof.  If  f h provides optimal transportation for cost c with constraint h, then f ‘h‘  provides the most expensive transportation for cost c with constraint h’, and hence optimal transportation for cost –c. Therefore  f’h’oT provides optimal transportation for cost –coT = c with constraint h‘.

Example. Take M₁ and M₂ in Rⁿ, with M₁ centrally symmetric, and cost  –x•y (which is equivalent to (x–y)²). Then central inversion in x carries optimal transportation with constraint h to optimal transportation with constraint h‘.

Revised 7 October 2013.