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

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'nski tetrahedron. In addition, we describe a solution to the corresponding dual problem.