## Optimal Transportation with Constraint

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* ^{n}* 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*** ^{n}*, cost

*c*(

*x*,

*y*) = –2

*x*•

*y*(which is equivalent to (

*x–*

*y*)

^{2}because its integral differs by a constant), and constraint

*h*= 2, under optimal transportation

*x*corresponds to

*y*with

*x*•

*y*positive. In

**R**

^{1}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*

^{n}**R**

^{1}.

**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*extend to optimal transportation from Π

_{i}*X*to Π

_{i}*Y*with a cost which is negative if and only if the costs of the projections are all negative: optimal transportation with constraint

_{i}*h*= Π

*h*relates points of negative cost. In particular, Example 2.3 generalizes to a product of such actions on

_{i}**R**

^{2}

*with cost negative if and only if*

^{n}*x*•

_{i}*y*≥ (cos π/

_{i}*h*)|

_{i}*x*||

_{i}*y*| for all

_{i}*i*: optimal transportation with constant constraint

*h*= Π

*h*relates all points with projections on rays from the origin to a product of cones of angle π/

_{i}*h*about the ray.

_{i}**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 _{1}, M_{2} be subsets of *

**R**

*or Riemannian manifolds with boundary or metric measure spaces of volume V. Let T*^{n}_{i}be a measure-preserving map from M_{i}to M_{i}and let T = T_{1}×T_{2}. Let c(x,y) be a cost satisfying coT = -c. If density f h on M_{1}×M_{2}provides optimal transportation from M_{1}to M_{2}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*_{1}* and M*_{2} in **R***^{n}*, with

*M*

_{1}centrally symmetric, and cost –

*x*•

*y*(which is equivalent to (

*x–*

*y*)

^{2}). Then central inversion in

*x*carries optimal transportation with constraint

*h*to optimal transportation with constraint

*h*‘.

Revised 7 October 2013.