Minicourse: Invariant Matching

Peres Y.

Suppose that red and blue points occur as independent point processes in R^d, and consider translation-invariant schemes for perfectly matching the red points to the blue points. (Translation-invariance means that the matching is constructed in a way that does not favor one spatial location over another). What is best possible cost of such a matching, measured in terms of the edge lengths? What happens if we insist that the matching is non-randomized, or if we forbid edge crossings, or if the points act as selfish agents? I will discuss recent progress and open problems on these topics, as well as on the related topic of fair allocation. In particular I will address some new discoveries on multi-color matching and multi-edge matching.