Stable Matching Problem (StaMP) & Gale-Shapley Algorithm

The Stable Matching Problem involves pairing two equally sized groups, such as applicants and companies, or students and schools, hospitals and residency candidates, project teams and people, based on individual ranked preferences. A matching is considered stable if there are no two individuals who would both prefer each other over their assigned matches. The Gale–Shapley Algorithm, also known as the Deferred Acceptance Algorithm, solves this by having one group (e.g., companies) make proposals in rounds. Each individual tentatively accepts the best offer so far and may "trade up" if a better one comes along in a later round. This process guarantees a stable outcome, meaning no unmatched pair would both prefer to be with each other over their assigned partners.