2. (Stable Matching Problem with Indifferences) In this problem, we will conside

Question

2. (Stable Matching Problem with Indifferences) In this problem, we will consider a situation in which men and women can be indifferent between two choices. Suppose we allow men and women to rank the members of the opposite sex with ties to indicate indifference. For example, a woman w can place both men m and m2 in the same rank. That is, she has no preference between these two men. There could be two notions for instability as a result of indifferences as follows ·A strong instability in a perfect matching S consists of a man m and a woman w, such that n and w prefer each other to their current partners in S. » A weak instability in a perfect matching S consists of a man m and a woman w, such that their current respective partners and m' satisfy one of the following conditions m prefers w to w', and w either prefers m to m or is indifferent between the two choices; or -w prefers m to m,, and m either prefers w to w, or is indifferent between the two choices In other words, the matching between m and w is either preferred by both, or preferred by one while the other is indifferent uestion (a) Does there always exist a perfect matching without strong instability? (b) Does there always exist a perfect matching without weak instability? For these two problems, either give an instance of a matching problem with the strong/weak instability or provide an algorithm that is guaranteed to find a perfect matching without the strong/weak instability

Explanation / Answer

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

We can either modify the Gale-Shapley algorithm so that women and men break ties based on their choice at any moment. This must however also ensure that a man cannot propose to the same woman twice as in G-S algorithm.

Otherwise, we run the same G-S algorithm but break ties before the algorithm starts to get a stable matching.

ALGORITHM

for every man m belonging to M:

do create a totally ordered list of women, listing all women he is indifferent in arbitrary order;

for each woman w :

do create a totally ordered list of men, listing men to whom she is indifferent in arbitrary order; R

Run Gale-Shapley algorithm

b)No, there need not always exist a matching with no weak instabilities.

Suppose there are two men {m1, m2} and two women {w1, w2},

Here, both men m1 and m2 prefer w1 to w2, and both woman w1 and w2 are indifferent between the 2 men. There are only 2 kinds of matchings: either {(m1,w1), (m2, w2)}, or {(m2, w1), (m1, w2)}.

Both matchings have a weak instability as both men prefer w1 and she is indifferent between the two of them.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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