A stable marriage of poisson and lebesgue

• 成果类型: Article
• 署名作者: Hoffman, Christopher; Holroyd, Alexander E.; Peres, Yuval
• 署名单位: University of Washington; University of Washington Seattle; University of British Columbia; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/009117906000000098
• 发表日期: 2006
• 页码: 1241-1272
• 关键词: invariant percolation; infinite clusters; random-fields

摘要

Let Xi be a discrete set in R-d. Call the elements of Xi 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 Iota 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 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. 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.