Question

1 Intro The Stable Matching problem is solved with the Gale-Shapley algorithm. Here is the description of the Gale-Shapley algorithm from the Kleinberg text. It talks about a matching between equal numbers of men and women. 1 Initially all me M and wE W are free 2 While there is a man m who is free and hasn't proposed to every woman Choose such a man m Let w be the highest-ranked woman in m's preference list to whom m has not yet proposed If wis free then (m, w) become engaged Else w is currently engaged to m' If w prefers m to m then m r emains free Else w prefers m to m' 10 (m, w) become engaged m becomes free 12 13 Endif 14 Endwhile 15 Return the set S of engaged pairs Endif

Answer 1