How to pair people perfectly so that no one wants to trade partners
In short: The stable matching problem asks how to pair two groups so that no two individuals prefer each other over their current partners. In 1962, David Gale and Lloyd Shapley proved that a stable solution always exists, a discovery that eventually earned them a Nobel Memorial Prize in Economic Sciences.
The Gale-Shapley algorithm, or deferred acceptance algorithm, solves this by having one group propose to the other in a series of rounds. Unengaged individuals propose to their most-preferred partner who has not yet rejected them. The receiving side then provisionally accepts the best offer they have received so far, holding the right to 'jilt' a current partner if a more desirable suitor appears. This process continues until everyone is engaged, guaranteeing a stable outcome where no pair exists that would both rather be with each other than their current match.
While the algorithm always finds a stable state, it is not neutral. It is 'truthful' for the proposing side, meaning they cannot improve their outcome by lying about their preferences. However, the receiving side can potentially gain a better match by misrepresenting their preferences. Furthermore, the algorithm is biased: it always yields the best possible stable outcome for the proposers and the worst for the receivers. In any given instance, there can be multiple stable matchings, and the number of these solutions can grow exponentially with the number of participants.
This logic extends far beyond theoretical marriage. It is used to assign medical students to hospital appointments and rabbis to congregations. Variants like the 'hospitals/residents' problem allow for institutions to accept multiple candidates, while the 'rural hospitals theorem' ensures that the set of assigned doctors remains consistent across all stable matchings. Unlike the stable marriage problem, the 'stable roommates' problem involves a single pool of participants, creating a different set of constraints for finding stability.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Stable matching problem
To cite this card, link to https://intellectplus.co.uk/app/science-stable-matching-problem.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Discrete mathematics · More in Science · Latest · A–Z · All topics