A Poisson allocation of optimal tail

DOI10.1214/15-AOP1001MaRDI QIDQ282511zbMATH OpenOpenAlexFDO

Authors Roland Markó, Ádám Timár

Publication date 12 May 2016

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.5259, https://projecteuclid.org/euclid.aop/1457960396

zbMATH Keywords

fair allocationPoisson processtranslation-equivariant mapping

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05)

Abstract: The allocation problem for a $d$-dimensional Poisson point process is to find a way to partition the space to parts of equal size, and to assign the parts to the configuration points in a measurable, "deterministic" (equivariant) way. The goal is to make the diameter $R$ of the part assigned to a configuration point have fast decay. We present an algorithm for $dgeq3$ that achieves an $O(operatornameexp(-c{R}^d))$ tail, which is optimal up to $c$. This improves the best previously known allocation rule, the gravitational allocation, which has an $operatornameexp(-R^{1+o(1)})$ tail. The construction is based on the Ajtai-Koml'{o}s-Tusn'{a}dy algorithm and uses the Gale-Shapley-Hoffman-Holroyd-Peres stable marriage scheme (as applied to allocation problems).

Recommendations

• Gravitational allocation to Poisson points
• Poisson matching
• Tail Bounds for the Stable Marriage of Poisson and Lebesgue
• Percolation for the stable marriage of Poisson and Lebesgue
• A stable marriage of Poisson and Lebesgue

Cites work

• A stable marriage of Poisson and Lebesgue
• Connected allocation to Poisson points in \(\mathbb R^{2}\)
• Extra heads and invariant allocations
• Gravitational allocation to Poisson points
• How to find an extra head: Optimal random shifts of Bernoulli and Poisson random fields
• scientific article; zbMATH DE number 4009416 (Why is no real title available?)
• On optimal matchings
• Optimal transport from Lebesgue to Poisson
• Phase transitions in gravitational allocation
• Poisson matching
• The integrability of the square exponential transportation cost

Cited in

(14)

• Gravitational allocation for uniform points on the sphere
• Optimal lot disposition from Poisson-Lindley count data
• Connected allocation to Poisson points in \(\mathbb R^{2}\)
• Best choice from the planar Poisson process
• Tail Bounds for the Stable Marriage of Poisson and Lebesgue
• Gravitational allocation on the sphere
• Phase transitions in gravitational allocation
• There is no stationary cyclically monotone Poisson matching in 2d
• A factor matching of optimal tail between Poisson processes
• There is no stationary p-cyclically monotone Poisson matching in 2d
• Dynamic spatial matching
• Optimal transport of stationary point processes: metric structure, gradient flow and convexity of the specific entropy
• Poisson allocations with bounded connected cells
• Gravitational allocation to Poisson points

This page was built for publication: A Poisson allocation of optimal tail

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q282511)