Stable Marriages

The stable marriage problem is another classic appreciation of discrete mathematics to social networks. 

Suppose that you have been hired to be a matchmaker with n men and n woman who wish to be paired up with their perfect matches. Each man provides the matchmaker with a list of the woman ranking from first choice to last choice, as same for the woman. 

The matchmakers job is to provide a way to pair up the n men and n women in such a way so no man or woman is left behind. 

The stable marriage theorem states that your job can always be accomplished, no matter how the men and women have ranked one another. This theorem provides an algorithm that accomplishes your task. 

In round 1: every man proposes to his first choice. those woman who receives the offers tentatively accept the best offer and tell the other men not to come back. The rejected men then propose to their next choice, and the women then tentatively accept the best offer they have so far received and tell the other proposers to go away. This process continues until every man and woman are paired up. 

Example One: Suppose the matchmaker receives the following list: 

man 1 (3,1,4,2,5)

man 2 (1,3,5,2,4) 

man 3 (5,4,3,2,1)

man 4 (1,5,4,2,3)

man 5 (3.4.5.1.2)

woman 1 (3,5,1,4,2) 

woman 2 (3,1,2,4,5)

woman 3 (1,2,3,4,5)

woman 4 (5,3,1,2,4)

woman 5 (5,4,3,2,1)

 Use the stable marriage algorithm to find a stable parring. 

Answer: Men 1,2,3,4 and 5 will propose to women 3,1,5, 1, and 3 respectively. Woman 1 rejects man 2, woman 3 rejects man 5. So then men 2 and 5 propose to women 3 and 4 respectively, but man 2 is rejected again because woman 3 is already taken. Man 2 now continues to move down his list to woman number 5, who accepts him and rejects man number 3. Now man 3 proposes to woman 3, who rejects him. Then man 3 proposes to woman 2 who accepts his offer. WIth no man or woman unattached, the algorithm terminates with stable pairings: 

man 1 with woman 3, man 2 with woman 5, man 3 with woman 2, man 4 with woman 1, and man 5 with woman 4. 

Examine Question: Suppose the matchmaker receives the following list: 

man 1 (c, a, d, b, e)

man 2 (a, c, e, b, d) 

man 3 (e, d, c, b, a) 

man 4 (a, e, d, c, b)

man 5 (c, d, e, b, a)

woman a (3,1,2,4,5)

woman b (3, 5, 1, 4, 2)

woman c (5,3,1,2,4)

woman d (1,2,3,4,5)

woman e (5,4,3,2,1)

A. Use the stable marriage algorithm to find a solution pairing. (men proposes to women)

B. Find another stable marriage obtained by having the women propose to the men.