Gale–Shapley Algorithm

Published Mar 22, 2024

Definition of Gale-Shapley Algorithm

The Gale-Shapley Algorithm, also known as the Deferred Acceptance Algorithm, is a solution to the Stable Matching Problem, which essentially involves matching members of two groups to one another based on preferences, ensuring a stable outcome. A “stable” match means there are no two individuals who would both rather be matched with each other than with their current partners. This algorithm, introduced by David Gale and Lloyd Shapley in 1962, has wide applications, including in marriage and job markets.

Example

Consider the application of the Gale-Shapley Algorithm in a simplified job market scenario where there are three employers (A, B, C) and three job seekers (X, Y, Z). Each employer has a ranked preference of whom they’d like to hire most, and each job seeker has a ranked preference of where they’d like to work. The Gale-Shapley Algorithm can be used to ensure that a stable set of hirings is made – that is, no employer-job seeker pair would rather work with each other over their current match.

The process begins with each job seeker “proposing” to their top-choice employer. If an employer receives multiple proposals, they tentatively accept the job seeker they prefer most and reject the others. Rejected job seekers propose to their next-choice employer in the next round, and employers may “trade up” if they receive a preferable proposal. This process continues until every job seeker is matched with an employer, ensuring all matches are stable.

Why the Gale-Shapley Algorithm Matters

The Gale-Shapley Algorithm is significant because it offers a mathematically sound method of ensuring stability in matches across various applications. Its most noted use is in the National Resident Matching Program (NRMP), which matches medical residents to hospitals. Here, it helps align the preferences of hospitals and residents, optimizing outcomes and preventing the “exploding offers” problem, where candidates must respond to job offers in a very short time frame. By ensuring stable matches, the Gale-Shapley Algorithm minimizes disruptions and dissatisfaction in the matching process, whether in job markets, school admissions, or other areas where two-sided matching is applicable.

Frequently Asked Questions (FAQ)

Is the Gale-Shapley Algorithm fair?

The concept of “fairness” in the context of the Gale-Shapley Algorithm can be subjective; however, it is designed to respect the preferences of participants on one side of the market entirely (e.g., job seekers or applicants) and is efficient in finding a stable match for all participants. The side that makes the proposals (e.g., job seekers) is guaranteed to get their “best” stable outcome, whereas the receivers (e.g., employers) agree to the “worst” stable outcome they could get considering the proposals. This can lead to discussions about the algorithm’s equity from the perspective of both sides.

Can the Gale-Shapley Algorithm be used in online dating?

Yes, in theory, the Gale-Shapley Algorithm could be adapted for use in online dating platforms to match users based on their preferences. However, real-world application would require addressing complexities like non-binary preferences, the dynamics of attraction, and the fact that human relationships are not always transitive and consistent.

Has the Gale-Shapley Algorithm won any awards?

Yes, Lloyd Shapley was awarded the Nobel Memorial Prize in Economic Sciences in 2012, along with Alvin E. Roth, for the theory of stable allocations and the practice of market design, which includes their work on the Gale-Shapley Algorithm.

Are there limitations to the Gale-Shapley Algorithm?

One limitation of the Gale-Shapley Algorithm is its assumption of complete information and strict preference rankings, which may not always be realistic in every application, such as in human relationships or complex job markets. Furthermore, it assumes a closed system with a fixed number of offers and acceptances, which may not reflect real-world scenarios where new participants can enter the market or alter their preferences.