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.
