stablemarriage

Stable marriage refers to a class of problems in matching theory where two disjoint sets of agents, traditionally men and women, must be paired so that no two agents would both prefer each other to their assigned partners. Each participant has a strict preference ranking over members of the opposite set. A matching pairs each participant with at most one partner, and it is stable if there is no blocking pair—a man and a woman who would both prefer to be with each other rather than with their current partners.

Existence and construction: For any finite instance with strict preferences, a stable matching exists. The Gale–Shapley algorithm demonstrates this by having one side repeatedly propose to members of the opposite side in order of preference, while the other side holds the best offer received and rejects others. The process ends when everyone is matched. The resulting stable matching is optimal for the proposing side and pessimal for the other side among all stable matchings. A symmetric variant with the other side proposing yields the opposite extreme.

Extensions and variants: The model extends to many-to-one matchings (hospital-residents, college admissions) and to cases with unequal numbers, incomplete preference lists, or ties. Different stability notions (weak or strong stability) arise in the presence of ties. The set of stable matchings forms a lattice, enabling trade-offs between different participants’ objectives.

Applications and impact: The framework underpins real-world systems such as medical residency placement, school choice programs, and organ-exchange markets. It offers a principled, computationally practical method for pairing that avoids certain kinds of instability, with a clear understanding of which party may influence outcomes through preference reporting.