Stable matchings with correlated preferences

Stable matchings are a way to pair different groups in an (arguably) fair manner. Common examples of stable matchings come from pairing men and women into couples and pairing medical residents with their first job. The mathematical study of stable matchings began over 60 years ago with the beautiful work of Gale and Shapley. Since then many statistics of stable matchings have been extensively studied in the case that the preferences of the different groups are independent and all preferences are equally likely. Pitel proved that the number of stable matchings of n men and n women is of order n log(n). In this talk we consider a distribution on preferences that are highly correlated. We show that with these preferences there are exponentially many stable matches.

This is joint work with Avi Levy and Elchanan Mossel.