Mia Deijfen: Mean field stable matching

Abstract

Consider a situation where a number of objects acting to maximize their own satisfaction are to be matched. Each object ranks the other objects and a matching is then said to be stable if there is no pair of objects that would prefer to be matched to each other rather than their current partners. We consider stable matching of the vertices in the complete graph based on i.i.d. exponential edge costs. Our results concern the total cost of the matching, the typical cost and rank of an edge in the matching, and the sensitivity of the matching and the matching cost to small perturbations of the underlying edge costs.