Gravitational allocation to Poisson points

Abstract

For $d\ge 3$, we construct a non-randomized, fair, and translation-equivariant allocation of Lebesgue measure to the points of a standard Poisson point process in $\mathbb{R}^d$, defined by allocating to each of the Poisson points its basin of attraction with respect to the flow induced by a gravitational force field exerted by the points of the Poisson process. We prove that this allocation rule is economical in the sense that the allocation diameter, defined as the diameter $X$ of the basin of attraction containing the origin, is a random variable with a rapidly decaying tail. Specifically, we have the tail bound \[\mathbb{P}(X > R) \le C \operatorname{exp}\big[-c R (\log R)^{\alpha_d} \big]\] for all $R>2$, where: $\alpha_d = \frac{d-2}{d}$ for $d\ge 4$; $\alpha_3$ can be taken as any number less than $-4/3$; and $C$ and $c$ are positive constants that depend on $d$ and $\alpha_d$. This is the first construction of an allocation rule of Lebesgue measure to a Poisson point process with subpolynomial decay of the tail $\mathbb{P}(X>R)$.