Fair allocations to random points, using the stable marriage algorithm, Riemann mapping, and Newtonian gravity


Yuval Peres

Microsoft Research


Thursday, April 23, 2009

Talk at 4:30 p.m. in Room 2-190

Tea from 4:00 - 4:30 p.m. in Room 2-290
Refreshments afterwards, in Room 2-290


Abstract:   Given an infinite collection of points in the plane (a point process) how do we allocate the same area to each point in a decentralized, shift invariant way? See for one solution based on the Gale-Shapley stable marriage algorithm, and for another. Different approaches to this problem have connections with probability, combinatorics, ergodic theory, the Riemann mapping theorem, and Newtonian gravity (in higher dimensions); see the gallery at but there is lots of room for new creative ideas. (Talk based on works of the speaker as well as C. Hoffman, A. Holroyd, S. Chatterjee, R. Peled, D. Romik and M. Krikun.)


Home Web page:  Alexandru I. Suciu Comments to: 
Posted: March 28, 2009    URL: