Maria Deijfen

Stockholm University Stockholm University

Stable matching on the complete graph

Probability Seminar

8th March 2024, 3:30 pm – 4:30 pm
Fry Building, 2.04

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 to small perturbations of
the underlying edge costs.

Comments are closed.