1 Intro The Stable Matching problem is solved with the Gale-Shapley algorithm. H

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

Explanation / Answer

A) Choosing an 'm' from the list of all free m's is one event that is certain to occur each time the loop body is executed.

B) A man can purpose to n women at max as it is certain that this alogorithm terminates after a given number of steps and so if a men gets rejected for all n - 1 times , he purposes then he is gaurantee to get matched in the last try as without that the algorithm can't terminate to a result.

C ) The upper bound of this is n(n-1)+1

D) n - 1 women are engaged and it indicates the women in men's order always has him as the least priority men , so he proposed all the women and runs out of options.

E) Consider the case that women say 'A' is the preference in all men's list. Then in such a case if first men proposes and gets engaged , then she remains engaged for the whole run of algo and as the women can't choose a men. So in that case all other men will keep asking the same women and only one women get engaged.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.