The Gale-Shapley algorithm, also known as the deferred acceptance algorithm, is a keystone in matching theory. Conceived by mathematicians David Gale and Lloyd Shapley in 1962, the algorithm was crafted to untangle the Stable Marriage Problem, a challenge centered on pairing two sets of individuals, like men and women, based on their preferences. The brilliance of the solution lies in ensuring stability, which means no pair would defect to be with each other rather than their assigned partners.
What Does the Gale-Shapley Algorithm Do?
The Gale-Shapley algorithm is a deferred acceptance algorithm used in matching theory. It provides a methodical blueprint for finding a stable matching between two sets of participants. It includes three stages:
- A proposal stage where one participant offers to match with another.
- An evaluation stage, where the other participant evaluates the proposal and either accepts or rejects it.
- An iteration stage, where the remaining unmatched pairs go through the process again.
The Gale-Shapley algorithm guarantees a stable outcome, and it is man-optimal.
In this article, we will unravel the Stable Marriage Problem, illuminate the inner workings of the Gale-Shapley algorithm and walk through an example with supporting Python code.
What Is the Stable Marriage Problem?
The stable marriage problem (SMP) is a classic conundrum in mathematics and computer science. It seeks to orchestrate a stable match between two equal-sized groups of participants, typically men and women. The objective is to secure a stable matching, where no two participants would desert their current partners for one another.
Formally, the problem can be framed as follows:
- There are two sets of participants, usually referred to as “men” and “women.”
- Each man ranks all the women according to his preferences, and each woman does the same for the men.
- A stable matching emerges when no man and woman, already matched, would prefer to abandon their partners for each other. If such a scenario arises, the match is deemed unstable, since that pair would “defect” to be with one another.
Example of the Stable Marriage Problem
Let’s create an example involving three men and three women. Their preferences might look something like this:
Men Preferences
- Man 1: Woman 1, Woman 2, Woman 3
- Man 2: Woman 2, Woman 3, Woman 1
- Man 3: Woman 3, Woman 1, Woman 2
Women Preferences
- Woman 1: Man 2, Man 1, Man 3
- Woman 2: Man 1, Man 2, Man 3
- Woman 3: Man 3, Man 1, Man 2
Our task now is to forge a matching between the men and women that guarantees stability. The aim is to ensure that no man and woman would prefer each other over their assigned matches.
What Is the Gale-Shapley Algorithm?
The Gale-Shapley algorithm provides a methodical blueprint for finding a stable matching between two sets of participants. Here’s how it unravels:
- Initialization: Each participant begins unmatched.
- Proposals: Men, or one set of participants, approach their most desired woman, or counterpart, who hasn’t yet rejected them.
- Acceptance or Rejection: Women evaluate incoming proposals. If a woman receives a proposal she favors over her current match, she “trades up” and embraces the new suitor, discarding her former match.
- Iteration: The process loops until all men are paired or until every woman has rejected the least desired proposals.
The Gale-Shapley algorithm guarantees a stable outcome and, crucially, it is man-optimal. This means each man is paired with the best possible partner he could have in any stable matching. The Gale-Shapley algorithm can also be used to match doctors with hospitals, donors with organs and other resource allocation situations.
How Does the Gale-Shapley Algorithm Work?
The algorithm revolves around a cyclical dance of proposals and rejections. Men propose, and women deliberate over whether to accept or spurn the offers based on their preferences. Let’s break it down step-by-step:
1. Proposal
Each man extends a proposal to the woman he most desires. If the woman is unattached, she tentatively accepts the offer. However, if she is already engaged, she compares the new suitor with her current partner. If she finds the new man more appealing, she accepts the proposal and dumps her previous match. Otherwise, she rejects the new proposal.
2. Rejection
When a woman rejects a man, the man proceeds to his next choice on the list and proposes to her. This cycle repeats until every man is coupled with a partner.
3. Stability Check
The algorithm halts when no unmatched man can issue a new proposal. At this point, the matching is guaranteed to be stable, and no couple will wish to trade partners
How to Solve the Stable Marriage Problem Using the Gale Shapley Algorithm
Let’s translate the Gale-Shapley algorithm into Python to tackle the Stable Marriage Problem. The algorithm proceeds iteratively, where each free man proposes to the women in the order of his preferences. If a woman is free, she accepts the proposal. If she is already engaged, she compares her current partner with the new proposer, and if she prefers the new man, she switches partners. This continues until all men are engaged.
The function gale_shapley() returns a dictionary of engaged pairs, ensuring that no man or woman would prefer another partner more than their current match. The algorithm guarantees a stable matching where no two individuals would prefer to be with each other over their assigned partners.
def gale_shapley(men_preferences, women_preferences):
n = len(men_preferences)
free_men = list(men_preferences.keys()) # All men start out free
engaged_pairs = {} # To store engaged pairs
men_proposals = {man: [] for man in men_preferences} # Track proposals
# While there are free men who haven't proposed to all women
while free_men:
man = free_men[0] # Grab the first free man
man_pref = men_preferences[man]
for woman in man_pref:
if woman not in men_proposals[man]:
men_proposals[man].append(woman) # Record the proposal
# If the woman is free, engage them
if woman not in engaged_pairs.values():
engaged_pairs[man] = woman
free_men.remove(man)
break
else:
# If the woman is already engaged, check if she prefers the new man
current_man = next(m for m, w in engaged_pairs.items() if w == woman)
woman_pref = women_preferences[woman]
if woman_pref.index(man) < woman_pref.index(current_man):
# Engage the new man and free the current one
engaged_pairs[man] = woman
free_men.remove(man)
free_men.append(current_man)
del engaged_pairs[current_man]
break
return engaged_pairs
# Example usage
men_preferences = {
'Man1': ['Woman1', 'Woman2', 'Woman3'],
'Man2': ['Woman2', 'Woman3', 'Woman1'],
'Man3': ['Woman3', 'Woman1', 'Woman2'],
}
women_preferences = {
'Woman1': ['Man2', 'Man1', 'Man3'],
'Woman2': ['Man1', 'Man2', 'Man3'],
'Woman3': ['Man3', 'Man1', 'Man2'],
}
result = gale_shapley(men_preferences, women_preferences)
print(result)When we feed this data into the Gale-Shapley algorithm, the resulting stable pairs are, as follows:
- Man 1 is paired with Woman 2
- Man 2 is paired with Woman 1
- Man 3 is paired with Woman 3
This matching is stable because no man and woman prefer each other over their current matches, ensuring that no pair will defect from their assigned partners.
Frequently Asked Questions
What is the significance of the Gale-Shapley algorithm?
The Gale-Shapley algorithm has far-reaching applications beyond marriage matching. It is instrumental in matching students with schools, doctors with hospitals and even organ donors with recipients. Its significance lies in its ability to guarantee a stable, harmonious solution where no participant prefers someone else over their current match.
What is the runtime of the Gale-Shapley algorithm?
The Gale-Shapley algorithm boasts a time complexity of O(n²), where “n” refers to the number of participants in one group (either men or women). Each man proposes to every woman at most once, resulting in at most n² proposals.
