The \'Stable Matching Problem\' assumes that every man/woman have a fully ordere

Question

The 'Stable Matching Problem' assumes that every man/woman have a fully ordered list of preference. Allow us to consider a situation where we have n men and n women however, they are allowed to have ties in their ranking. An example, man m1 might prefer woman w3 the best, w1 and w4 in no particular order (that is to say, the man does not prefer w1 to w4, or w4 to w1), followed by w2. We will say that in this case, m1 is indifferent between w1 and w4. We also allow that it is possible for a man or woman to be indifferent between more than 2 people.

We note a Strong Instability in a perfect matching to consist of a man m and a woman w such that both m and w prefer each other to their current partner. Is it possible that there always exists a perfect matching with no Strong Instability? Find an algorithm that is able to find such a matching or show an example where every perfect matching has a Strong Instability.

Explanation / Answer

The answer is Yes. A simple way to think about it is to break the ties in somefashion and then run the stable matching algorithm on the resulting preference lists.We can for example break the ties lexicographically—that is, if a b is indierent between two gi, gj then gi appears on b’s preference list before gj if i < j, and if j < i gj appears before gi. Similarly, if g is indierent between bi, bj then bi appears on g’s preference list before bj if i < j, and if j < i bj appears before bi.

Now that we have a set of concrete preference lists, we run the stable matching algorithm. We claim that the matching produced would have no strong instability.But the latter claim is true because any strong instability would be an instability for the match produced by the algorithm, yet we know that the algorithm produced a stable matching—a matching with no instabilities.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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