Minimal Matching of Random Points
6th March 2020, 3:30 pm – 4:30 pm
Fry Building, LG.22
What is fairness, and to what extent is it practically achievable? I’ll talk about a simple mathematical model under which one might hope to understand such questions. Red and blue points occur as independent homogeneous Poisson processes of equal intensity in Euclidean space, and we try to match them to each other. We would like to minimize the sum of a some function (say, a power, gamma) of the distances between matched pairs. This does not make sense, because the sum is infinite, so instead we satisfy ourselves with minimizing *locally*. If the points are interpreted as agents who would like to be matched as close as possible, the parameter gamma encodes a measure of fairness – large gamma means that we try to avoid very long edges, even if that means increasing the lengths of shorter edges – small gamma means everyone is in it for themselves.
In dimension 1 we have a reasonably complete picture, with a phase transition at gamma=1. For gamma<1 there is a unique minimal matching, while for gamma>1 there are multiple matchings but no stationary solution. In higher dimensions, even existence is not clear in all cases.
Based on joint work with Svante Janson and Johan W\”astlund.