Fair allocations to random points, using the stable marriage algorithm, Riemann mapping, and Newtonian gravity |
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 http://www.stat.berkeley.edu/~peres/stable/stable.html for one solution based on the Gale-Shapley stable marriage algorithm, and http://depts.washington.edu/probab/research.php 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 http://www.math.huji.ac.il/~romik/Site/Allocations.html 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.) |
Web page: Alexandru I. Suciu | Comments to: alexsuciu@neu.edu | |
Posted: March 28, 2009 | URL: http://www.math.neu.edu/bhmn/peres09.html |