Title: Two-sided matching markets with correlated random preferences have few stable pairs
Authors: Simon Mauras - Université de Paris, IRIF (France) [presenting]
Abstract: Stable matching in a community consisting of $N$ men and $N$ women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962. We study the number of stable pairs, that is, the man/woman pairs that appear in some stable matching. We prove that if the preference lists on one side are generated at random using a given popularity model, the expected number of stable edges is bounded by $N\ln N + N$, matching the asymptotic value for uniform preference lists. If in addition that the popularity model is a geometric distribution, then the number of stable edges is $O(N)$ and the incentive to manipulate is limited. If in addition, the preference lists on the other side are uniform, then the number of stable edges is asymptotically $N$ up to lower-order terms: most participants have a unique stable partner, hence non-manipulability.