Mathematics – Probability
Scientific paper
2005-05-31
Annals of Probability 2006, Vol. 34, No. 4, 1241-1272
Mathematics
Probability
Published at http://dx.doi.org/10.1214/009117906000000098 in the Annals of Probability (http://www.imstat.org/aop/) by the Ins
Scientific paper
10.1214/009117906000000098
Let $\Xi$ be a discrete set in ${\mathbb{R}}^d$. Call the elements of $\Xi$ centers. The well-known Voronoi tessellation partitions ${\mathbb{R}}^d$ into polyhedral regions (of varying sizes) by allocating each site of ${\mathbb{R}}^d$ to the closest center. Here we study ``fair'' allocations of ${\mathbb{R}}^d$ to $\Xi$ in which the regions allocated to different centers have equal volumes. We prove that if $\Xi$ 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. (I.e., 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 $\xi$ is a union of finitely many bounded connected sets. However, in the case of a Poisson process, an infinite volume of sites are allocated to centers further away than $\xi$. 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$.
Hoffman Christopher
Holroyd Alexander E.
Peres Yuval
No associations
LandOfFree
A stable marriage of Poisson and Lebesgue does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A stable marriage of Poisson and Lebesgue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A stable marriage of Poisson and Lebesgue will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-455690