Gale-Shapley Algorithm
The Gale-Shapley Algorithm is a method used to solve the stable marriage problem, which involves matching two equal-sized groups based on preferences. Developed by mathematicians David Gale and Lloyd Shapley in 1962, the algorithm ensures that each participant is paired in a way that no two individuals would prefer each other over their current partners, thus avoiding instability in the matches.
In the algorithm, one group proposes to members of the other group based on their preferences. Each member of the second group then tentatively accepts the best proposal they have received so far, leading to a series of proposals and rejections until a stable match is achieved. This process guarantees that all participants are matched optimally according to their preferences.