Gale shapley algorithm

The Gale-Shapley algorithm is a fundamental concept in Game Theory and Mechanism Design that provides a solution to the problem of creating stable pairings between two distinct sets of participants based on their expressed preference lists. Often referred to as the Deferred Acceptance algorithm, it ensures that no two participants who are not matched with each other would mutually prefer to be matched with each other over their current assignments, leading to a stable allocation. This mathematical algorithm has found widespread application in various real-world matching markets.

History and Origin

The Gale-Shapley algorithm was formally introduced by mathematicians David Gale and Lloyd S. Shapley in their 1962 paper, "College Admissions and the Stability of Marriage"²¹, ²². While they provided the theoretical framework and proved its properties, a similar process had been in practical use for the National Resident Matching Program (NRMP) in the United States since the early 1950s. Lloyd Shapley, along with Alvin E. Roth, was awarded the Nobel Memorial Prize in Economic Sciences in 2012 for their work on stable allocations and the practice of market design, which heavily relies on the principles of the Gale-Shapley algorithm¹⁸, ¹⁹, ²⁰. Roth's contributions highlighted the practical applications and adaptations of these matching theories to real-world scenarios.

Key Takeaways

The Gale-Shapley algorithm creates a stable matching between two sets of participants, meaning no two unmatched participants would prefer each other over their current partners.
It operates iteratively, with one side of the market (proposers) making offers and the other side (receivers) accepting or rejecting them based on their preferences.
The algorithm guarantees a stable outcome and always terminates.
A key characteristic is that the proposing side receives the best possible stable matching from their perspective, while the receiving side gets the worst stable matching¹⁷.
It is widely applied in various real-world scenarios, including college admissions, medical residency placements, and organ donation matching.

Formula and Calculation

The Gale-Shapley algorithm is a procedural method rather than a formula with variables. It operates through a series of iterative steps to achieve a stable matching. For two sets, say Men (M) and Women (W), where each individual has a ranked list of preference for members of the opposite set, the algorithm proceeds as follows:

Initialization: All men and women are considered "free" (unmatched).
Proposal Phase: Each free man proposes to the most-preferred woman on his list to whom he has not yet proposed.
Response Phase: Each woman who has received one or more proposals considers all proposals she has received (including any current tentative engagement).
- She tentatively accepts the proposal from the man she prefers most among them.
- She rejects all other proposals.
- Any man whose proposal is rejected becomes "free" again and will propose to his next preferred woman in the subsequent round.
Iteration: These steps (Proposal and Response) repeat until no man is free to make a proposal. At this point, all men and women are tentatively engaged, and this set of engagements forms a stable matching.

The process ensures that as proposals are made and accepted, engagements are only broken if a woman receives a better offer according to her preferences. This "deferred acceptance" mechanism is critical to its success and stability¹⁵, ¹⁶.

Interpreting the Gale-Shapley Algorithm

The interpretation of the Gale-Shapley algorithm lies in understanding its outcome: a stable allocation. A matching is considered stable if there are no two participants, A and B, who are not matched to each other, but who would both prefer to be matched with each other over their current partners. If such a pair existed, the current matching would be unstable, as A and B would have an incentive to "elope" or form a new pair outside the established system.

The algorithm's success means that it always finds at least one such stable matching. The resulting set of pairings represents a form of market equilibrium where no mutually beneficial unassigned connection exists. This property is crucial for the fairness and sustainability of allocation systems, as it prevents widespread dissatisfaction and the collapse of the matching process.

Hypothetical Example

Consider a simplified scenario with three individuals from Set A (e.g., colleges) and three individuals from Set B (e.g., students), each with their ranked preferences:

College Preferences (Set A, Proposers):

College 1: (Student B, Student C, Student A)
College 2: (Student A, Student B, Student C)
College 3: (Student B, Student A, Student C)

Student Preferences (Set B, Receivers):

Student A: (College 2, College 3, College 1)
Student B: (College 1, College 3, College 2)
Student C: (College 1, College 2, College 3)

Steps of the Gale-Shapley algorithm:

Round 1:

College 1 proposes to Student B (1st choice).
College 2 proposes to Student A (1st choice).
College 3 proposes to Student B (1st choice).
Student A receives a proposal from College 2. Tentatively accepts.
Student B receives proposals from College 1 and College 3. Prefers College 1 over College 3. Tentatively accepts College 1, rejects College 3.
Student C receives no proposals.

Round 2:

College 3, rejected by Student B, proposes to its next choice: Student A.
Student A, tentatively engaged to College 2, receives a new proposal from College 3. Student A prefers College 2 over College 3. Rejects College 3.
College 1 and College 2 remain tentatively engaged.

Round 3:

College 3, rejected by Student A, proposes to its next choice: Student C.
Student C, previously unengaged, receives a proposal from College 3. Tentatively accepts College 3.

Final Stable Matching:

College 1 – Student B
College 2 – Student A
College 3 – Student C

In this outcome, every participant is matched, and no two unmatched participants would prefer to be together, ensuring a stable allocation. This process demonstrates how even complex preference orderings can lead to a coherent and stable result.

Practical Applications

The Gale-Shapley algorithm, and its derivatives, are crucial in real-world resource allocation problems where monetary prices are not the primary mechanism for allocation. Its practical applications span various sectors:

Medical Residency Matching: Perhaps the most famous application is in the National Resident Matching Program (NRMP) in the U.S., where graduating medical students are matched to residency programs. This¹³, ¹⁴ system uses a modified version of the Gale-Shapley algorithm (the Roth-Peranson algorithm) to match tens of thousands of applicants with thousands of residency positions annually. The ¹²objective is to achieve a stable match that optimizes for the preferences of one side (students) while still being stable for the other (hospitals).
College Admissions: Many university admissions systems, particularly in countries like the UK (UCAS) and France, use algorithms derived from Gale-Shapley principles to assign students to programs based on their ranked choices and the institutions' capacities and preferences.
¹¹Kidney Exchange Programs: Nobel laureate Alvin Roth's work extensively applied stable matching algorithms to organize kidney exchange programs for incompatible donor-recipient pairs. This⁸, ⁹, ¹⁰ application has enabled thousands of life-saving transplants by creating chains or cycles of donations among multiple pairs, overcoming immunological incompatibilities that would otherwise prevent transplants.
⁶, ⁷Public School Assignments: In some urban areas, similar algorithms are used to assign students to public schools, considering student preferences and school capacities, aiming for efficient and equitable placements.
Online Dating and Job Markets: While not always strictly using the Gale-Shapley algorithm, the principles of deferred acceptance and preference matching are foundational to many platforms that seek to create optimal pairings in areas like online dating, job recruitment, and even content delivery networks.

The⁵se diverse applications highlight the algorithm's utility in ensuring market efficiency and fair outcomes in contexts where traditional economic mechanisms like pricing are either inappropriate or insufficient.

Limitations and Criticisms

While the Gale-Shapley algorithm guarantees a stable matching and ensures that the proposing side receives their best possible stable partner, it is not without limitations or criticisms.

One significant criticism centers on the inherent proposer's advantage. The side that makes the proposals (e.g., men in the classic "stable marriage problem" or students in the NRMP's current design) systematically receives a more favorable stable match than the receiving side. This³, ⁴ means that while the outcome is stable, it is not necessarily "fair" in the sense of maximizing the overall satisfaction of both parties equally, or of minimizing total dissatisfaction. The proposing side gets their most preferred partner among all stable matches, while the receiving side gets their least preferred partner among all stable matches. This² asymmetry can lead to discussions in behavioral economics about how individuals might strategically misrepresent their preference lists if they are on the receiving side, though the algorithm is designed to be strategy-proof for the proposing side.

Ano¹ther limitation arises when preferences are not strict or complete. If individuals are indifferent between several options, or if their preferences are incomplete, the algorithm's guarantees can be affected. Real-world preferences are often complex, involving factors beyond a simple linear ranking, which can introduce practical challenges and potentially increase transaction costs in implementation.

Furthermore, the algorithm's original formulation assumes equal numbers of participants in both sets, which may not always hold true in real-world matching markets. While generalized versions exist to handle unequal numbers or quotas (e.g., colleges having multiple slots for students), these adaptations can add complexity.

Gale-Shapley Algorithm vs. Stable Matching Problem

The Gale-Shapley algorithm is a specific, constructive method for finding a solution to the Stable Matching Problem. The Stable Matching Problem, also known as the Stable Marriage Problem, is a mathematical problem that seeks to pair elements from two distinct sets (e.g., men and women, or students and colleges) such that no two unmatched elements would prefer to be paired with each other over their current partners.

Essentially, the Stable Matching Problem defines what a stable matching is and poses the question of whether such a matching exists and how to find one. The Gale-Shapley algorithm provides the how – it is the step-by-step algorithm that guarantees to produce at least one such stable matching when given complete and transitive preference lists. While the problem defines the goal of optimization, the algorithm is the concrete procedure to achieve that goal, illustrating the practical application of economic theory and game theory.

FAQs

What is a "stable" matching in the context of the Gale-Shapley algorithm?

A matching is considered "stable" if there are no two participants who are not currently matched with each other, but who would both prefer to be matched with each other over their current partners. If such a pair existed, they would have an incentive to "break up" their current pairings and form a new one, making the original matching unstable.

Can the Gale-Shapley algorithm fail to find a match?

No, the Gale-Shapley algorithm is guaranteed to find a stable allocation for all participants, provided that all individuals have complete and transitive preference lists for the opposite group. The algorithm is proven to always terminate with a stable set of pairings.

Does the order of proposals matter in the Gale-Shapley algorithm?

Yes, the specific stable matching found by the Gale-Shapley algorithm depends on which side initiates the proposals. The side that proposes (e.g., men in the classic example) will always receive their most preferred stable matching, while the receiving side will receive their least preferred stable matching. However, the property of stability itself is always achieved, regardless of which side proposes.

Is the Gale-Shapley algorithm considered fair?

While the Gale-Shapley algorithm produces a stable outcome and is strategy-proof for the proposing side (meaning proposers cannot gain by misrepresenting their true preference lists), it is not necessarily "fair" in the sense of treating both sides equally. The inherent "proposer's advantage" means one side consistently achieves a better outcome than the other within the set of all possible stable matchings. This aspect is often discussed in the broader field of Nash equilibrium and incentive compatibility.