On multistochastic Monge-Kantorovich problem, bitwise operations, and fractals

Abstract

The multistochastic $(n,k)$-Monge--Kantorovich problem on a product space ${\prod }_{i=1}^n{X}_i$ is an extension of the classical Monge--Kantorovich problem. This problem is considered on the space of measures with fixed projections onto $X_{i_1}\times \dots \times X_{i_k}$ for all $k$-tuples $\{i_1,\dots ,i_k\}\subset \{1,\dots ,n\}$ for a given $1\le k<n$. In our paper we study well-posedness of the primal and the corresponding dual problem. Our central result describes a solution $\pi$ to the following important model case: $n=3,k=2,X_i=[0,1]$, the cost function $c(x,y,z)=xyz$, and the corresponding two--dimensional projections are Lebesgue measures on $[0,1{]}^2$. We prove, in particular, that the mapping $(x,y)\to x\oplus y$, where $\oplus$ is the bitwise addition (xor- or Nim-addition) on $[0,1]\cong {\mathbb{Z}}_2^{\infty }$, is the corresponding optimal transportation. In particular, the support of $\pi$ is the Sierpiński tetrahedron. In addition, we describe a solution to the corresponding dual problem.

31 pages