Gale-Shapley algorithm
The Gale-Shapley algorithm is a method used to solve the stable marriage problem, which involves matching two sets of participants, such as men and women, based on their 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 achieving stability in the matches.
The algorithm works through a series of proposals, where one group proposes to members of the other group based on their preferences. Each member of the receiving group can either accept or reject a proposal, leading to a series of adjustments until a stable matching is reached. This process has applications in various fields, including economics and computer science, particularly in matching markets and resource allocation.