PC Seminar: Mean field stable matchings

Abstract: Consider the complete bipartite graph on n+n vertices where the edges are equipped with i.i.d. exponential costs. A matching of the vertices is stable if it does not contain any pair of vertices where the connecting edge is cheaper than both matching costs. There exists a unique stable matching obtained by iteratively pairing vertices with small edge costs. We shall compare the asymptotic behaviour of the stable matching to the minimum matching studied by Aldous in 2001. A highlight of the comparison concerns the sensitivity of the matching and the matching cost to a small perturbation of the underlying edge costs, where the heavier tails of the stable matching causes it to behave differently.

This is a seminar in our seminar series on Probability and Combinatorics (PC).