Be the first user to complete this post

  • 0
 Add to List
Hard

462. Stable Marriage Problem - Gale–Shapley Algorithm

Stable Marriage

Given N men and N women and the marriage preference order for each man and woman. Their marriage will be stable when these men and women marry in such a manner so that everyone gets the most desired partner as per the availability( partners in a marriage cannot find anyone else better than what they get). 

Wiki Definition- Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of the opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable. (Source- Wiki)

Objective: Given N men and N women and the preference marriage order for each man and woman write an algorithm to marry them in a manner so that their marriages are stable.

Example:

There are 2 men (m1 and m2) and 2 women (w1 and w2). Marriage preference order is given below -

Preference order of m1 - [w1, w2] 
Preference order of m2 - [w1, w2] 
Preference order of w1 - [m1, m2] 
Preference order of w2 - [m1, m2]

Possible couples for marriage

  • (m1, w1) and (m2, w2)
    • 

  • (m1, w2) and (m2, w1)
    • 
Couples (m1, w2) and (m2, w1) are not stable since m1 would prefer w1 over w2 (assigned to m1) similarly w1 would prefer m1 over m2 (assigned to w1).
    On the other hand couples (m1, w1) and (m2, w2) are stable since there are no two people of the opposite sex who would both rather have each other than their current partners. Let's see what are other two people of the opposite sex (m1, w2) and (m2, w1). In (m1, w2), w2 would prefer m1 but m1 would not prefer w2 over w1 (assigned to m1) and similarly in (m2, w1), m2 would prefer w1 but w1 would not prefer m2 over m1 (assigned to w1) so (m1, w1) and (m2, w2) are stable couple.

    Approach:

    Gale–Shapley algorithm (also known as the Deferred Acceptance algorithm)

    Pseudo Code:

    function stableMatching
	Initialize all m ∈ M and w ∈ W to free
	while ∃ free man m who still has a woman w to propose to
		w = first woman on m’s list to whom m has not yet propose
		if w is free
		(m, w) become engaged
		else some pair (m', w) already exist
			if w prefers m to m
				m' becomes freeengaged
			else
                                    engaged

    Let's understand the pseudo-code:

    Initially, all men and women are free, means not engaged. Each man will propose the women from his preference list (from higher priority to lower) and during iterating the preference list for each woman, check if woman is also free, if yes then engage them if not that means this woman has already accepted the proposal from some other man, in that case, either this woman dumps that other man and accept the proposal from current man (this will happen only if current man is having preference than that other man as per this woman's preference list) or this woman decides not to dump the man so current man will try his luck with the other woman in his list. This process will not stop until all the men and women are engaged. This algorithm also guarantees that all men and women are married. 

    See the code below and read the comments for more understanding. 

    Output:

    Man 0 is looking for a woman now-
Women 0 has ACCEPTED the man: 0
Man 1 is looking for a woman now-
Women 0 has DUMPED the man: 0
Women 0 has ACCEPTED the man: 1
Man 0 is looking for a woman now-
Women 1 has ACCEPTED the man: 0
Man 2 is looking for a woman now-
Women 1 has DUMPED the man: 0
Women 1 has ACCEPTED the man: 2
Man 0 is looking for a woman now-
Women 2 has ACCEPTED the man: 0
Man 3 is looking for a woman now-
Women 3 has ACCEPTED the man: 3
------------------Final Matching----------------------------
Woman: 0 is engaged with man: 1
Woman: 1 is engaged with man: 2
Woman: 2 is engaged with man: 0
Woman: 3 is engaged with man: 3

    References: 

    Related Problems: