The stable marriage problem is a bipartite matching problem in graph theory in which n boys and n girls each possess a complete, strict preference ordering over the opposite set, and the goal is to find a perfect matching containing no "rogue couple" — a pair who prefer each other to their assigned partners — a property termed stability. The Gale–Shapley (deferred-acceptance) algorithm constructively produces a stable matching via an iterative proposal process in which proposers work down their preference lists while recipients tentatively hold their best offer and reject the rest, and it is proven (by termination bounds, an invariant showing recipients' held offers never worsen, and contradiction arguments) to always terminate, to always fully marry every participant, and to always yield a stable matching, with the additional theorem that the algorithm is simultaneously optimal for the proposing side and pessimal for the receiving side among all possible stable matchings.
The stable marriage problem is a bipartite matching problem in graph theory in which n boys and n girls each possess a complete, strict preference ordering over the opposite set, and the goal is to f…