The stable marriage allocation introduced by Chris Hoffman, Alexander Holroyd and Yuval Peres. They proved a bound on the effectiveness of the matching in one dimension. In a recent paper by Alexander Holroyd, Robin Pemantle, Yuval Peres and Oded Schramm, new bounds are derived in all dimensions.

Picture by Alexander Holroyd

A (translation-equivariant) allocation rule is a way of taking the points of a translation-invariant random point process (scaled to have unit mean density) in d-dimensional space, and assigning to them pairwise disjoint subsets called cells, such that each of the random points gets a cell of volume 1, the cells together cover all of d-dimensional space except a set of measure 0, and such that the rule uses no information on where the origin is, in the sense that shifting all the points by a constant amount will result in cells which are the original cells shifted by the same amount.

Allocation rules have been studied in several papers by Sourav Chatterjee, Chris Hoffman, Alexander Holroyd, Maxim Krikun, Thomas Liggett, Fedor Nazarov, Ron Peled, Robin Pemantle, Yuval Peres, Dan Romik, Oded Schramm, Mikhail Sodin, Boris Tsirelson, and Alexander Volberg (and maybe others - sorry if I forgot you!). Here are some related pictures:

The “gradient flow” allocation, suggested by Boris Tsirelson and analyzed in detail in a paper by Fedor Nazarov, Mikhail Sodin and Alexander Volberg. The underlying point process is the process of zeros of the Gaussian Entire Function.

The “gravitational allocation”, inspired by the gradient flow allocation, that uses flow along the lines of a Newtonian gravitational force field to allocate volume to the Poisson points (which are considered as stars exerting the gravitational force). Analyzed by Sourav Chatterjee, Ron Peled, Yuval Peres and Dan Romik.

Picture by Manjunath Krishnapur

An allocation rule suggested by Maxim Krikun, based on conformally mapping the plane minus a minimal spanning forest induced by the Poisson points to the upper half plane and then performing a stable marriage algorithm with the hyperbolic distance metric. It proves that an allocation rule in the plane can have connected cells.

An allocation rule suggested by Yuliy Baryshnikov, that so far is only defined on a finite region. It minimizes the mean square distance of all the Poisson centers to the points in their cells, and can be computed using a modified (“weighted”) Voronoi diagram. We believe in dimensions 3 and higher its definition can be extended to a translation-equivariant allocation rule on the entire d-dimensional space.

Picture by Maxim Krikun

Allocation rules