Answer the question basic on the Gale-Shapley algorithm. 1 Intro The Stable Matc

Question

Answer the question basic on the Gale-Shapley algorithm.

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) In a perfect matching nobody should be left unmatched so 2 men and 2 women can be matched in 2 ways:

man1-woman1 man2-woman-2 (OR)

man1-woman2 man2-woman-1

B) Only 1 stable matching. m-w and n-x because

If m and x are matched then since m's 1st preference is w then he proposes her and since for her m has higher priority than n she leaves him to pair with m.

Else m is happy with w and w is happy with m so m wont propose x so x wont leave n and even if n proposes w she rejects him and both couples are stable.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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