• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

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

Gladkov N., Kolesnikov A., Zimin A.
The multistochastic (n,k)-Monge--Kantorovich problem on a product space ∏ni=1Xi is an extension of the classical Monge--Kantorovich problem. This problem is considered on the space of measures with fixed projections onto Xi1×…×Xik for all k-tuples {i1,…,ik}⊂{1,…,n} for a given 1≤k<n. In our paper we study well-posedness of the primal and the corresponding dual problem. Our central result describes a solution π to the following important model case: n=3,k=2,Xi=[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)→x⊕y, where ⊕ is the bitwise addition (xor- or Nim-addition) on [0,1]≅Z∞2, is the corresponding optimal transportation. In particular, the support of π is the Sierpiński tetrahedron. In addition, we describe a solution to the corresponding dual problem.