A stable marriage is a one-to-one matching between two equally sized sets of participants, each of whom ranks the participants in the other set, such that there is no blocking pair. A blocking pair consists of two participants who are not matched to each other but each prefer the other to their assigned partner. A stable marriage exists for every instance with complete strict preference lists (Gale and Shapley 1962).
The stable marriage problem asks for a stable marriage for a given collection of preference lists.
With
participants on each side and complete strict preference lists, the number of distinct
stable marriages is less than
(Ghorbani and Mnich 2026). The proof
uses weights whose admissibility is checked by exact rational arithmetic and certified
bounds for the exponential function.