A Stable Marriage of Poisson and Lebesgue

Picture based on research by Christopher Hoffman, Alexander Holroyd and Yuval Peres (scroll down for more information).

What is this?

We start with 300 "centres" (visible as the centres of the concentric circles), distributed independently uniformly at random in a square. Each centre has associated with it a region of the square, called its territory, indicated by concentric annuli in two different colours. The 300 territories form a partition of the square, and all territories have equal areas. Note that not all territories are connected. For example, the centre nearest the top-left corner has a perfect disc as its territory (indicated in purple and blue); the territory near the bottom-right corner (indicated in light blue and brown) has two components. Note also that some territories include parts a very long way from their centres; look at the piece of red and green territory located about one third of the way down the right side.

Such a partition could be achieved in many possible ways, but the one illustrated is a "canonical" choice. Informally, it is constructed as follows. Each centre simultaneously starts growing a circle, all at the same speed. A centre claims all territory encountered by its circle, unless another centre has claimed it earlier, and until the centre reaches its "quota" (the area of the square divided by the number of centres). (Opposite sides of the square are identified, to form a torus). Without the "quota" restriction, the resulting territories would be precisely the Voronoi cells, in which each "site" (location in the square) is allocated to the closest centre.

It is possible to extend the above procedure to the infinite plane (or to space in any number of dimensions). The analogue of uniformly distributed centres is called a Poisson process. If the quota equals 1 unit of area, and the intensity of the process (the average number of centres per unit area) equals 1, then every centre will be satisfied, and all space will be claimed. (Surprisingly, the same is not true if we start with an arbitrary set of centres of "intensity" 1 - if the centres form a regular grid with a single centre missing, then some space will not be claimed in any territory).

Stable Marriage

The above informal description is appealing, but it turns out to be difficult to make it into a rigorous definition (especially in infinite space). Instead we may proceed as follows. Suppose that both sites (that is, ordinary points in space) and centres have preferences; sites prefer to be in a territory of a nearby centre, while centres prefer to have a nearby territory. We call a partition unstable if there exist a site and centre which are not allocated to each other, but both prefer each other compared with the current partition. We call a partition stable if it is not unstable. One may convince oneself that the informal construction above should give rise to a stable partition. In fact it turns out that there is a unique stable partition.

The idea of stability as above was introduced by Gale and Shapley in the context of finite problems involving married couples and college admissions. Gale and Shapley introduced a celebrated algorithm (involving iterated proposals and rejections) for constructing stable marriages. The algorithm may be adapted to our setting and proves the existence of a stable partition. Stable marriage problems do not in general have unique solutions, but in our case the preferences of sites and centres are "consistent", both being based on distance; it turns out that this guarantees uniqueness.

Geometry

Many questions arise about the shapes of the territories. Here are a few answers. Each territory is bounded. Any bounded region of the plane contains parts of only finitely many territories (this is by no means obvious from the pictures - look at the following closeups of busy regions of a picture with 10,000 centres). Furthermore each territory has only finitely many connected components.

Subcritical and Supercritical models

Suppose we keep the intensity of the Poisson process of centres fixed at 1 per unit area, but vary the "quota" or "appetite", α say, of the centres. To extend the definition of a stable partition, suppose also that a site prefers any centre rather than be unclaimed, while a centre prefers any site rather than be unsated (i.e. have a territory smaller than α). Above we considered the "critical case" (α=1). In the subcritical case (α<1) some sites are unclaimed, while in the supercritical case (α>1) some centres are unsated. The following pictures show the five cases α = 0.2, 0.8, 1, 1.2, ∞. When α=∞ the territories are the Voronoi cells.

The critical case differs qualitatively from the subcritical and supercritical cases in more respects than just absence of unclaimed sites and unsated centres. Roughly, the critical model looks "busier" and possesses "long-range order". One way to formalize these ideas is to consider the random variable X defined as the distance from the origin to the centre whose territory contains the origin (we take X=∞ if the origin is unclaimed). We expect X to be largest in the critical case. Indeed, X has (at least) power-law tails in the critical case, and exponential tails (on the event that it is finite) in the non-critical cases. Known information about the critical case varies with dimension, as follows.
Critical case α=1
DimensionLower boundUpper bound
1E(X1/2)=∞E(X1/2-ε) < ∞
2E(X)=∞E(X0.496) < ∞
d>=3 E(Xd)=∞E(Xs) < ∞, some s(d)>0

Subcritical case α < 1 and Supercritical case α > 1
DimensionLower boundUpper bound
d>=1E(exp CXd; X < ∞)=∞E(exp cXd; X < ∞) < ∞
It is an open problem to determine the correct power law in dimensions d>=2.

References

C. Hoffman, A. E. Holroyd, and Y. Peres. Tail bounds for the stable marriage of Poisson and Lebesgue. Canad. J. Math., 61(6):1279-1299, 2009. [ PS | PDF ]
C. Hoffman, A. E. Holroyd, and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab., 34(4):1241-1272, 2006. [ PS | PDF ]
A. E. Holroyd, R. Pemantle, Y. Peres, and O. Schramm. Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat., 45(1):266-287, 2009. [ PS | PDF ]
D. Gale & L. Shapley. College admissions and stability of marriage. Amer. Math. Monthly, 69(1):9-15, 1962.
Alexander E. Holroyd 2005,2012
Contact Us Terms of Use Trademarks Privacy Statement ©2010 Microsoft Corporation. All rights reserved.Microsoft