The women are A, B, C, D, E. Women\'s preference ranking over men, left is highe
ID: 3177808 • Letter: T
Question
The women are A, B, C, D, E. Women's preference ranking over men, left is highest: A: S T R P Q B: T R S P Q C: Q T R S P D: S R T Q P E: P Q R T S The men are P, Q, R, S, T Men's preference ranking over women: P: A B C D E Q: B A D C E R: B E C A D S: C B A E D T: D C B A E (a) Applying the Gale-Shapley algorithm to pair men and women, what will happen if the women propose? Show your work (you could use my slides from last Thursday as a guide), and state the final pairing of men with women. (b) What will happen if the men propose? (c) If you did it right some people will have different partners under (a) versus (b). Name one of the women who a different partner. Does she rank her partner higher when she's proposing or when she's accepting/rejecting?Explanation / Answer
(a) As per wiki, Gale -shapley algorithm when women will propose
1st Iteration:
A is free and first preference is S. A is free so (A,S) are engaged.
B is free and first preference is T. T is free so (B,T) are engaged.
C is free and first preference is Q. Q is free so (C,Q) are engaged.
D is free and first preference is S. S is engaged with A but S preference is A compared to D so D remains free.
E is free and first preference is P. A is free so (E,P) are engaged.
After 1st iteration, D is free.
2nd Iteration:
D is free and next available preference is R and R is free, so (D,R) are engaged.
So, the final match is (A,S) (B,T) (C,Q) (D,R) (E,P)
(b) As per wiki, Gale -shapley algorithm when men will propose
1st Iteration:
P is free and first preference is A. A is free so (P,A) are engaged.
Q is free and first preference is B. B is free so (Q,B) are engaged.
R is free and first preference is B. B is engaged with Q but B preference is R compared to Q so (R,B) are engaged and Q becomes free.
S is free and first preference is C. C is free so (S,C) are engaged.
T is free and first preference is D. A is free so (T,D) are engaged.
After 1st iteration, Q is free.
2nd Iteration:
Q is free and next available preference is C which prefers Q more than S. C is engaged with S , So (Q,C) are engaged and S becomes free. (Note A,D prefer P, T more than Q.)
3rd Iteration:
S is free and next available preference is A which prefers S more than P. A is engaged with P , So (S,A) are engaged and P becomes free. (Note B prefer R more than S.)
4th Iteration:
P is free and next available preference is E and E is free. E is engaged with P , So (P,E) are engaged none of mean are free. (Note B,C,D prefer R,Q,T more than P.)
So, the final match is (P,E) (Q,C) (R,B) (S,A) (T,D)
(c) The final match in part (a) is (A,S) (B,T) (C,Q) (D,R) (E,P)
The final match in part (b) is (P,E) (Q,C) (R,B) (S,A) (T,D)
The preferences of B,D,R and T does not match in part (a) and (b).
Women B has different patner. When B proposed, she got the partner T which she ranked first. When B accepts/rejects, she got the partner R which she ranked second. So she rank her partner higher when she's proposing.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.