Affordable Access

Two-sided matching markets with correlated random preferences have few stable pairs

  • Gimbert, Hugo
  • Mathieu, Claire
  • Mauras, Simon
Publication Date
Dec 02, 2020
External links


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 in a seminal paper by Gale and Shapley. In this paper, 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 the popularity model of Immorlica and Mahdian, 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 popularity model is a geometric distribution, then the number of stable edges is $\mathcal 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.

Report this publication


Seen <100 times