GaleShapleyAlgorithmus

The Gale-Shapley Algorithmus, often called the Gale–Shapley algorithm, is a solution to the stable marriage problem. It was introduced by David Gale and Lloyd Shapley in 1962 and provides a method for finding a stable matching between two equally sized sets of agents, typically referred to as men and women, based on their strict preference lists. The algorithm can be adapted to many-to-one settings such as hospitals and residents or colleges and applicants.

In its classic form, the procedure proceeds in rounds. Each unengaged proposer (for example, a man) applies to his most preferred partner (a woman) to whom he has not yet proposed. Each recipient holds onto the most favorable proposal she has received so far and rejects the rest. If a recipient later receives a better proposal, she keeps the best one and rejects the previous partner, who becomes unengaged. The process repeats until every participant is engaged. The resulting pairing is stable, meaning no unmatched pair would prefer each other over their current partners.

Two key properties are stability and optimality. A stable matching contains no blocking pairs. With strict preferences and equal sets, the outcome is optimal for the proposers and pessimal for the receivers among all stable matchings; reversing the roles yields the opposite optimality. Variants extend the method to many-to-one and many-to-many matchings and to settings with ties or incomplete lists.

Complexity for the basic version is typically O(n^2) time and O(n^2) space for n pairs, though implementations may vary. The algorithm underpins real-world matching markets such as medical residency placements and various school choice mechanisms, illustrating a foundational concept in combinatorial optimization and market design.