Probability Seminar

Alexander HolroydUniversity of Washington
Matching Random Points

Monday, September 30, 2019 - 4:00pm
Malott 406

How effectively can two random sets of points (say red and blue) be matched to each other? What can be said about optimal matchings in which the lengths of the edges are minimized? The answer depends in part on precisely what notion of minimality we use. For instance, we may imagine the points as agents who try to greedily optimize their own self-interest, or we may instead aim for global notions of fairness. How do the answers change if we insist that the matching can be determined locally, without global coordination? I will explain how such questions can be turned into formal mathematical ones. I will talk about recent progress and the many open questions, as well as variants such as fair allocation, and multi-color and multi-edge matching.

See for pictures.