The Geometry of Fair Allocation to Random Points
Channel: UMD Mathematics
Date: 2013-04-23

Yuval Peres
Principal Researcher and Theory Group Manager
Microsoft Research Redmond

ABSTRACT

Given a random scatter of points (obtained as a limit of uniform picks from a large cube, or as the zeros of a random analytic function) , our goal is to allocate to each point of the process a unit of volume, in a deterministic translation-invariant way, so that the diameter of the region allocated to each point is stochastically as small as possible. One approach to this problem, studied in joint work with C. Hoffman and A. Holroyd, uses the stable marriage algorithm of Gale and Shapley. In  dimensions 3 and higher, gravity without inertia yields a satisfying solution.  The fairness of the allocation is a consequence of the divergence theorem; The diameters of the allocated regions are analyzed using methods from percolation theory.  Finally, I will relate the properties of the allocation to rigidity properties of the underlying point process.

Recorded April 13th, 2013 at Calabifest: The 28th Geometry Festival.