A $2.81^n$ upper bound on the number of stable matchings

Abstract

We study the maximum number $\mathrm{SM}(n)$ of stable matchings in an instance with $n$ men and $n$ women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponential upper bound; their argument gives $\mathrm{SM}(n)\le 2^{17n}$ for sufficiently large $n$. Palmer and Pálvölgyi (FOCS 2021) improved this bound to $3.55^n+O(1)$. We prove that $\mathrm{SM}(n)<2.81^n$. This brings the exponential base closer to $2.28$, the base of the best known lower bound. More precisely, we bound the number of stable matchings in each instance in terms of each person's number of stable partners, where a stable partner is someone matched to that person in at least one stable matching. Our proof assigns each person a weight determined by this number and uses these weights to bound the number of stable matchings by induction.