3 Stable Marriage Consider a set of four men and four women with the following p
ID: 2257183 • Letter: 3
Question
3 Stable Marriage Consider a set of four men and four women with the following preferences: men preferences women preferences C 13>2>4 D 3 124 2 ASB CD 3 A>BC>D 4 A>B>D>C (a) Run on this instance the stable matching algorithm presented in class. Show each day of the algorithm, and give the resulting matching, expressed as {(M, W),... 8 (b) We know that there can be no more than n2 days for the algorithm to terminate, because at least one woman is deleted from at least one list on each day. Can you construct an instance (a set of preference lists) with n men and n women so that at least n2/2 days are required? (c) Suppose we relax the rules for the men, so that each unpaired man proposes to the next woman on his list at a time of his choice (some men might procrastinate for several days, while others might propose and get rejected several times in a single day). Can the order of the proposals change the resulting pairing? Give an example of such a change or prove that the pairing that results is the same.Explanation / Answer
Algorithm:
(a) Free Man : {A,B,C,D}, Free Woman :{1,2,3,4} Engaged: {}
For A, 1 is his first choice and 1 is free also
hence (A,1) should get engaged.
Free Man : {B,C,D}, Free Woman :{2,3,4} Engaged: {(A,1)}
next For B, 1 is his first choide but 1 is not free
1 always prefer A over B, hence (A,1) remains engaged
For B, 3 is his second choice and 3 is free also
hence (B,3) should engaged
Free Man : {C,D}, Free Woman :{2,4} Engaged: {(A,1),(B,3)}
next C, C's first choice is 1 which is already engaged with A.
1 prefer A over C, hence (A,1) remains engaged
C's second choice is 3 which is already engaged with B
3 prefer B over C, hence (B,3) remains engaged.
C's third choice is 2 which is free
hence (C,2) should engaged.
Free Man : {D}, Free Woman :{4} Engaged: {(A,1),(B,3),(C,2)}
D's first choice is 3 but 3 prefer B over D
D's second choice is 1 and 1 is engaged with A but 1 prefer D over A
hence (D,1) will engaged and A becomes free
Free Man : {A}, Free Woman :{4} Engaged: {(D,1),(B,3),(C,2)}
Now left A , his first choice is 1 which is engaged with D that is correct
his second choice is 2 which is engaged with C but 2 prefer A over C
Hence (A,2) should get engaged and C become free
Free Man : {C}, Free Woman :{4} Engaged: {(D,1),(B,3),(A,2)}
Now left C, C first choice is 1 which is married to D (which is fine)
C second choice is 3 but 3 is married to B (which is fine)
C third choice is 2, 2 is married to A (which is fine)
C fourth choice is 4 which is free, hence (C,4) should get engaged.
Free Man : {}, Free Woman :{} Engaged: {(D,1),(B,3),(A,2),(C,4)}
In some places i used engaged and married word interchangabaly.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.