The Stable Matching Problem, as discussed in the text, assumes that all men and

Question

The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this problem we will consider a version of the problem in which men and women can be indifferent between certain options. As before we have a set M of n men and a set Wof n women. Assume each man and each woman ranks the members of the opposite gender, but now we allow ties in the ranking. For example (with n- 4), a woman could say that m1 is ranked in first place; second place is a tie between m2 and m3 (she has no preference between them); and m4 is in last place. We will say that w prefers m to m' if m is ranked higher than m' on her preference list (they are not tied) With indifferences in the rankings, there could be two natural notions for stability. And for each we can ask about the existence of stable matchings, as follows. (a) A strong instability in a perfect matching S consists of a man m and a woman w, such that each of m and w prefers the other to their partner in S. Does there always exist a perfect matching with no strong instability? Either give an example of a set of men and women with preference lists for which every perfect matching has a strong instability; or give an algorithm that is guaranteed to find a perfect matching with no strong instability. (b) A weak instability in a perfect matching S consists of a man m and a woman w, such that their partners in S are w and m', respectively, and one of the following holds: m prefers w to w', and w either prefers m to m' or is indifferent between these two choices; or w prefers m to m', and m either prefers w to w' or is indifferent between these two choices. In other words, the pairing between m and w is either preferred by both, or preferred by one while the other is indifferent. Does there always exist a perfect matching with no weak instability? Either give an example of a set of men and women with preference lists for which every perfect matching has a weak instability; or give an algorithm that is guaranteed to find a perfect matching with no weak instability.

Explanation / Answer

1. Strong Instabilities

Yes, there always exists a stable matching with no strong instabilities.

The Solution for Stable Marriage Problem was given by Gale-Shapely algorithm.

It can be modified so that men and women break ties arbitrarily, but we have to ensure that men never propose to the same woman twice.

The only difference between this and the original Gale-Shapely algorithm is that one man (m) can only break another man’s (m’) engagement when his ranking is strictly higher in the woman’s w preference list. This means there should not be a tie between m and m’ in w’s preference list.

The algorithm outputs a perfect matching, as before, since each man has every woman on his preference list and each woman will remain engaged once proposed to.

The Algorithm is as below:

Input: Sets M,W and preference lists

Output: List of engagements

find some woman w such that m has not proposed to w and no other woman not yet proposed to ranks higher than w.;

if (w is free) then

                (w,m) are engaged;

else

m ranks higher than w’s current partner m’;

Break (w,m) ’s engagement;

(w,m) are engaged;

(Note: If w is indifferent between m and current partner, do nothing.)

2. Week Instabilities

There need not always exist a matching with no week instabilities.

Example: Suppose there are two men [m,m’] and two women [w,w’] such that both men prefer w to w’.

Now, if each woman is indifferent between the two men , there will be 2 kinds of matching,

Either m -- w, m’ -- w’

Or m -- w’, m’ -- w

Both matching have a week instability since both m and m’ prefer w and she is indifferent between the two of them.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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