Gale–shapley algorithm

What Is Gale–Shapley Algorithm?

The Gale–Shapley algorithm is a foundational algorithm in matching theory that provides a solution to the stable matching problem. It falls under the broader financial category of Market Design, a field concerned with creating efficient platforms for the allocation of resources when prices alone are insufficient. This iterative procedure is designed to pair entities from two distinct sets, such as individuals and institutions, based on their preference ranking for each other, ensuring that the resulting arrangement is "stable." A stable match means there are no two participants who are not paired together but would mutually prefer each other over their current assignments. Th⁵¹, ⁵²e Gale–Shapley algorithm has found wide application in various real-world scenarios, particularly where a fair and robust assignment of agents is crucial, moving beyond traditional supply and demand dynamics.

History and Origin

The Gale–Shapley algorithm was first formally introduced in 1962 by mathematicians David Gale and Lloyd S. Shapley in their seminal paper, "College Admissions and the Stability of Marriage". Their ⁴⁹, ⁵⁰work laid the theoretical groundwork for solving stable matching problems, which involve finding a pairing between two groups of participants that is resistant to any pair "defecting" to form a more preferred match outside of the established arrangement.

Decad⁴⁸es later, economist Alvin E. Roth observed that a version of this algorithm had been in practical use since the early 1950s for the National Resident Matching Program (NRMP) in the United States, which assigns medical students to residencies. Roth's investigations into real-world markets demonstrated the practical significance of the theoretical concept of stable allocations. For their collective contributions to the theory of stable allocations and the practice of market design, Lloyd S. Shapley and Alvin E. Roth were jointly awarded the Nobel Memorial Prize in Economic Sciences in 2012. David Gale had passed away in 2008 and was thus ineligible for the prize. Their ⁴⁵, ⁴⁶, ⁴⁷work highlighted how robust market mechanisms could be designed even in the absence of explicit prices.

Ke⁴³, ⁴⁴y Takeaways

• The Gale–Shapley algorithm guarantees a stable matching solution for any given set of preferences, meaning no two unmatched individuals would prefer to be with each other over their assigned partners.
• It i⁴¹, ⁴²s a deterministic algorithm that always terminates, producing a definitive set of pairings.
• The ⁴⁰algorithm exhibits a "proposer-optimality" property, meaning the side that makes the proposals (e.g., job seekers) receives the best possible stable match from their perspective.
• It h³⁸, ³⁹as been widely adopted in diverse practical applications, including medical residency placements, school admissions, and organ donation systems.
• The ³⁶, ³⁷algorithm relies on explicit preference ranking lists from all participating entities.

Form³⁵ula and Calculation

The Gale–Shapley algorithm is not expressed as a static mathematical formula but rather as an iterative process for solving an optimization problem. It proceeds in rounds, ensuring that eventually, all participants are matched in a stable manner. The process can be conceptualized using a bipartite graph where one set of nodes (proposers) proposes to another set of nodes (receivers).

Here's a step-by-step pseudo-code representation of the man-proposing (proposer-optimal for men) variant:

Initialize all men and women as unengaged.
While there is an unengaged man who has not proposed to every woman:
Select such an unengaged man, M.
M proposes to the highest-ranked woman, W, on his preference list to whom he has not yet proposed.

If W is unengaged:
W tentatively accepts M, and they become engaged.
Else (W is currently engaged to another man, M'):
If W prefers M to M':
W rejects M' and tentatively accepts M.
M' becomes unengaged.
Else (W prefers M' to M):
W rejects M.
M remains unengaged.

Return the set of all engaged pairs.

This iterative process continues until every man has either secured a tentative engagement or has been rejected by every woman on his list. The algori³¹, ³², ³³, ³⁴thm guarantees that all participants on the proposing side will be matched, and the resulting matching will be stable.

Interp³⁰reting the Gale–Shapley Algorithm

Interpreting the outcome of the Gale–Shapley algorithm centers on the concept of "stability." The algorithm ensures that no "blocking pair" exists—that is, no unmatched individual A and individual B would both prefer each other to their current partners. This property is²⁸, ²⁹ crucial because it means there is no mutual incentive for any pair to deviate from the established matches, contributing to the robustness and longevity of the pairings.

A key aspect of²⁷ interpreting the Gale–Shapley algorithm's output is understanding its inherent bias. While the algorithm always produces a stable matching, the resulting allocation is "proposer-optimal" for the side that initiates proposals and "recipient-pessimal" for the side that receives proposals. This means the pro²⁵, ²⁶posing side achieves the best possible stable match for themselves, while the receiving side accepts the worst possible stable match from their perspective, given the constraint of stability. This characteristi²⁴c is a significant consideration in practical market mechanisms and affects the perceived efficiency and fairness of the allocation.

Hypothetical Example

Consider a simplified scenario with three job seekers (Alice, Bob, Carol) and three companies (X, Y, Z). Each job seeker ranks the companies by preference, and each company ranks the job seekers.

Job Seeker Preferences:

• Alice: Y > X > Z
• Bob: X > Y > Z
• Carol: X > Z > Y

Company Preferences:

• Company X: Carol > Bob > Alice
• Company Y: Alice > Carol > Bob
• Company Z: Bob > Alice > Carol

Let job seekers be the proposing side.

Round 1:

• Alice proposes to Y (her first choice). Y is free, so Y tentatively accepts Alice.
• Bob proposes to X (his first choice). X is free, so X tentatively accepts Bob.
• Carol proposes to X (her first choice). X is currently engaged to Bob. X compares Carol and Bob: X prefers Carol to Bob. So, X rejects Bob and tentatively accepts Carol. Bob becomes unengaged.

Round 2:

• Bob is unengaged and has been rejected by X. He proposes to his next choice: Y.
• Y is currently engaged to Alice. Y compares Bob and Alice: Y prefers Alice to Bob. So, Y rejects Bob. Bob remains unengaged.

Round 3:

• Bob is unengaged and has been rejected by X and Y. He proposes to his last choice: Z.
• Z is free, so Z tentatively accepts Bob.

At this point, all job seekers are engaged: Alice-Y, Carol-X, Bob-Z. The algorithm terminates because all proposers are matched. This is a stable resource allocation.

Practical Applications

The Gale–Shapley algorithm and its variations have significant real-world utility across various domains, particularly in designing allocation systems for two-sided markets where monetary prices are absent or insufficient.

One of the most prominent applications is the National Resident Matching Program (NRMP) in the U.S., which matches graduating medical students to residency positions in hospitals. This system ensures that medical students are matched with hospitals based on their preferences, and hospitals are matched with residents, creating stable pairings that minimize disruptions.

Beyond medical resi²¹, ²², ²³dencies, the algorithm is employed in school admissions systems. For instance, some public school systems, like those in New York City, use algorithms inspired by Gale-Shapley to match students with schools based on ranked preferences from both students and schools, aiming for more satisfactory outcomes than traditional first-come, first-served methods.

Furthermore, the Ga¹⁹, ²⁰le–Shapley algorithm is instrumental in facilitating kidney exchange programs. In these life-saving systems, incompatible donor-recipient pairs can be matched with other incompatible pairs to enable a chain of compatible transplants. The algorithm ensures that all exchanges are stable, maximizing the number of successful transplants. It is also applied in ¹⁶, ¹⁷, ¹⁸general job markets to match job seekers with firms based on their respective preferences.

Limitations and Cr¹⁴, ¹⁵iticisms

Despite its effectiveness in achieving stable matchings, the Gale–Shapley algorithm is not without limitations and has faced criticisms. A primary concern is the inherent bias towards the proposing side. As discussed, the proposing agents (e.g., job seekers proposing to companies) are guaranteed their best possible stable match, while the receiving agents (e.g., companies receiving proposals) are relegated to their worst possible stable match. This asymmetry can raise¹², ¹³ questions about the overall "fairness" of the outcome from the perspective of the receiving side, even though the result is stable.

Another criticism relat¹¹es to the algorithm's assumptions. It typically assumes that all participants have strict preferences (no ties in their rankings) and possess complete information regarding the preferences of others. In real-world scenarios,⁹, ¹⁰ preferences might not always be strictly ordered, and participants may not have full knowledge of others' complete rankings, which can complicate the practical application and outcome of the algorithm.

Moreover, while the algorithm is strategy-proof for the proposing side (meaning they cannot benefit by misrepresenting their preferences), it is not strategy-proof for the receiving side. Individuals on the receiving end might have an incentive compatibility to strategically misrepresent their preferences to secure a better match. This potential for strat⁸egic manipulation can undermine the integrity of the preference lists, a core input for the game theory-based solution.

Gale–Shapley Algorithm vs. Stable Matching Problem

The Gale–Shapley algorithm and the Stable Matching Problem are closely related but represent distinct concepts. The Stable Matching Problem (also known as the Stable Marriage Problem) is a theoretical combinatorial optimization challenge: given two sets of participants, each with a ranked list of preferences for members of the opposite set, the problem seeks to find a pairing such that no two individuals who are not paired together would prefer to be matched with each other over their current partners. It defines the goal or the⁶, ⁷ problem statement.

The Gale–Shapley algorithm, on the other hand, is the specific and widely recognized computational procedure or method used to solve the Stable Matching Problem. It provides a systematic, step⁵-by-step approach that guarantees the existence and discovery of at least one stable matching. In essence, the Stable Matchin⁴g Problem is what needs to be solved, and the Gale–Shapley algorithm is the tool¹²³