A Stable Marriage of Poisson and Lebesgue

By Christopher E. Hoffman, Alexander E. Holroyd, Yuval Peres. 2005

92 citations recorded by the source corpus.

Let be a discrete set in R d . Call the elements of centers. The well-known Voronoi tessellation partitions R d into polyhedral regions (of varying sizes) by allocating each site of R d to the closest center. Here we study \fair" allocations of R d to in which the regions allocated to dieren t centers have equal volumes. We prove that if is obtained from a translation-invariant point process, then there is a unique fair allocation which is stable in the sense of the Gale-Shapley marriage problem. (That is, sites and centers both prefer to be allocated as close as possible, and an allocation is said to be unstable if some site and center both prefer each other over their current allocations.) We show that the region allocated to each center is a union of nitely many bounded connected sets. However, in the case of a Poisson process, an innite volume of sites are allocated to centers further away than . We prove power law lower bounds on the allocation distance of a typical site. It is an open problem to prove any upper bound in d > 1.

Subfields: Applied Mathematics, Discrete Mathematics and Combinatorics, Economics and Econometrics

View Paper: https://www.semanticscholar.org/paper/d55b2cf86f94e70e20578b76997bca57d97398c2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Discrete Mathematics and Combinatorics

In Economics and Econometrics

Citations in the corpus

Poisson Matching (2007, background): “(ii) Fair allocations of Lebesgue measure to a Poisson process (see [11] and also [5, 10, 14] for definitions and background).”
Gravitational allocation to Poisson points (2006, background): “Hoffman, Holroyd, and Peres [7] constructed an allocation rule for every translation-invariant point process in R with unit intensity, the stable marriage allocation, in every dimension d 1.”
Lectures on the Poisson Process (2017, methodology): “11 Stable Allocations The chapter is based on the article [48] by Hoffman, Holroyd and Peres.”
Zeros of Gaussian Analytic Functions and Determinantal Point Processes (2009, methodology): “One such method, introduced by Hoffman, Holroyd and Peres in (33), produces matchings which are stable in the sense of the Gale-Shapley stable marriage problem (28).”
Optimal transport from Lebesgue to Poisson (2010, methodology): “[HP05] A. E. Holroyd and Y. Peres.”