The stable marriage problem is a classic problem in mathematics and computer science that deals with finding a stable matching between two sets of people with different preferences. In this problem, there are n men and n women, and each person has a list of preferences ranking the members of the opposite sex from best to worst.
The goal is to match the men and women in such a way that there are no "rogue" pairs who would prefer to be with each other than with their assigned partner. In other words, the matching should be stable, meaning that there should be no two pairs (man-woman) who prefer each other to their assigned partners.
The Gale-Shapley algorithm, also known as the Deferred Acceptance algorithm, is a popular algorithm for solving the stable marriage problem. It works by having each man propose to the woman he most prefers who has not yet rejected him, and the women then choose the best proposal among those they have received so far. If a woman rejects a proposal, she cannot receive any more proposals from that man, but if she accepts a proposal, she is provisionally matched with that man.
The algorithm then continues with the men proposing to the women they most prefer among those who have not rejected them, and the women choosing the best proposal among those they have received so far. This process continues until every woman is provisionally matched with a man.
The Gale-Shapley algorithm guarantees that the matching it produces is stable, meaning that there is no pair of people who would both prefer to be with each other than with their current partner. Moreover, the algorithm produces a matching that is optimal for the proposing side, meaning that no man can be matched with a woman he prefers less than the one he is matched with.
The time complexity of the Gale-Shapley algorithm is O(n2), where n is the number of men and women. This makes the algorithm relatively efficient, even for large datasets.
Example: Suppose there are three men (M1, M2, M3) and three women (W1, W2, W3), and their preference lists are as follows:
M1: W1 > W2 > W3
M2: W2 > W1 > W3
M3: W3 > W2 > W1
W1: M2 > M3 > M1
W2: M1 > M3 > M2
W3: M2 > M1 > M3The algorithm proceeds as follows:
M1 proposes to W1, who accepts provisionally.
M2 proposes to W1, who rejects him.
M2 proposes to W2, who accepts provisionally.
M3 proposes to W3, who accepts provisionally.
M1 proposes to W2, who rejects him.
M1 proposes to W3, who accepts provisionally.
The resulting stable matching is as follows:
M1 is matched with W3
M2 is matched with W2
M3 is matched with W1
This matching is stable because there is no pair of people who would both prefer to be with each other than with their current partner.