Decide whether the following statement is true or false: For any instance of the

Question

Decide whether the following statement is true or false:

For any instance of the Stable Matching Problem, if there exists a perfect matching that is not stable due to m and w wanting to be together, then (m, w) will be in every stable matching of that instance. In other words, if (m, w') and (m', w) are both in a perfect matching and m prefers w over w0 and w prefers m over m', then (m, w) will be in every stable matching.

Please provide the reason if the answer is true. If the answer is false please provide counter-example

Explanation / Answer

Assume that {m,m'} and {w,w'} represent set of two men and two women respectively.

The perfect matching (m,w') and (m',w) are not in stable perfect matching because here m prefers w' over w and w prefers m' over m.
This matching would result in the instability in matching because both m and w pair up with other partners leaving their own partners.

Thus, the answer is False.

Counter-example:

When the men m agree on the order of women w and women w agree upon the order of men m, there exists a perfect matching which is
stable.
The unique stable matching that exists is (m,w) and (m',w').

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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