The stable marriage problem is a classic combinatorial optimization challenge. It involves pairing individuals from two groups based on their preferences, aiming to find a stable matching where no two people would prefer each other over their assigned partners.

The Gale-Shapley algorithm provides an efficient solution to this problem. It guarantees a stable matching in polynomial time, making it applicable to real-world scenarios like college admissions, job assignments, and hospital residency placements.

The Stable Marriage Problem

Problem Definition

• The stable marriage problem involves matching individuals from two distinct groups (typically referred to as men and women) into stable pairs
• Each individual ranks all members of the opposite group according to their preferences
• A matching is considered stable if there are no two individuals who would both prefer each other over their current partners
• The goal is to find a stable matching, where no two individuals would prefer to be matched with each other rather than their current partners
• An instance of the stable marriage problem consists of an equal number of men and women, along with their preference lists

Key Components

• Two distinct groups of individuals (men and women)
• Preference lists for each individual, ranking all members of the opposite group
• Stable matching: a pairing where no two individuals would prefer each other over their current partners
• Instance of the problem: equal number of men and women, along with their preference lists
• Objective: find a stable matching based on the given preferences

Gale-Shapley Algorithm

Algorithm Description

• The Gale-Shapley algorithm, also known as the deferred acceptance algorithm, is a solution to the stable marriage problem
• The algorithm operates in rounds, where each unmatched man proposes to his highest-ranked woman who has not yet rejected him
• Each woman considers all proposals she receives in a round and tentatively accepts the proposal from the man she prefers the most, rejecting all other proposals
• If a woman receives a proposal from a man she prefers more than her current tentative match, she rejects her current match and tentatively accepts the new proposal
• The algorithm continues until all men are matched, resulting in a stable matching

Application to the Stable Marriage Problem

• The Gale-Shapley algorithm guarantees that every execution will terminate with a stable matching, regardless of the order in which the men propose
• The algorithm ensures that no two individuals would prefer each other over their assigned partners in the resulting matching
• The algorithm can be applied to any instance of the stable marriage problem, given the preference lists of the men and women
• The Gale-Shapley algorithm provides a systematic and efficient approach to solve the stable marriage problem and find a stable matching

Time Complexity and Optimality

Time Complexity Analysis

• The Gale-Shapley algorithm has a time complexity of O(n^2), where n is the number of men or women
• In the worst case, each man may need to propose to all women before finding a stable match, resulting in a total of n^2 proposals
• The algorithm always terminates after at most n^2 iterations, ensuring a polynomial-time solution to the stable marriage problem
• The time complexity of O(n^2) makes the Gale-Shapley algorithm efficient and practical for solving the stable marriage problem

Optimality Properties

• The Gale-Shapley algorithm produces a male-optimal stable matching, meaning that each man is paired with the best possible partner he can have in any stable matching
• Conversely, the algorithm results in a female-pessimal stable matching, where each woman is paired with her least preferred stable partner
• By reversing the roles of men and women in the algorithm, a female-optimal and male-pessimal stable matching can be obtained
• The optimality properties ensure that the algorithm always finds a stable matching that is favorable to one group (men or women) while being less favorable to the other group

Real-World Applications

College Admissions

• The stable marriage problem can be applied to match students to colleges based on their preferences and the colleges' rankings of students
• Students submit their preferred college choices, while colleges rank the students based on their qualifications and criteria
• The Gale-Shapley algorithm can be used to find a stable matching between students and colleges, ensuring that no student-college pair would prefer each other over their assigned matches

Job Assignments

• Companies can use the stable marriage algorithm to match job applicants to available positions based on the applicants' preferences and the company's requirements
• Job applicants rank their preferred positions, while the company ranks the applicants based on their qualifications and suitability for each position
• The algorithm finds a stable matching between job applicants and positions, optimizing the satisfaction of both parties

Hospital Residency Assignments

• The algorithm can be used to match medical school graduates to hospital residency programs, considering the preferences of both the graduates and the hospitals
• Medical graduates submit their preferred residency programs, while hospitals rank the graduates based on their qualifications and fit for the program
• The Gale-Shapley algorithm ensures a stable matching between graduates and residency programs, minimizing the likelihood of dissatisfaction or changes in the assignments

Other Applications

• Dormitory room allocation: assigning students to dormitory rooms based on their preferences for roommates and room types
• Organ donation: matching organ donors to recipients, considering factors such as compatibility and priority
• Mentor-mentee pairing: matching mentors with mentees based on their preferences and compatibility
• Project team formation: assigning individuals to project teams based on their skills, preferences, and the project requirements