The Stable Matching Problem, as discussed in the text, assumes that all men and
ID: 3741897 • Letter: T
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
For the case a:
Even if we modify the preference list of men/ women to have a tie, the original stable matching algorithm will work fine and will generate no strong instability.
The algorithm for the stable matching problem is:
n:: Number of men/women participating in the algorithm,
W:: Set of women,
M:: Set of men,
PLW:: Preference list of the women, PLW[w1] means preference list of woman 1 and PLW[w1][1] denotes the 1st preferred man by woman w1.
PLM:: Preference list of men, PLM[m1] means preference list of man 1 and PLM[m1][1] denotes the 1st preferred woman by man m1.
Free:: Array of length n, which is initialized with value 0 for all the elements, where 0 indicate that the woman is free and 1 indicates that the woman is assigned to some man and i^th index represent i^th woman.
Assign:: It is used to store the assigned (man, woman) pair.
Algorithm
While(there is any unassigned man):
//Let the unassigned man id be mid
wid=PLM[mid][1] // wid is the most preferred woman on the preference list of man mid
if(Free[wid]==0) // If the woman wid is free, not assigned to any man
assign mid to wid
Assign=Assign union (wid,mid)
delete wid from preference list of mid.
else //If the woman wid is not free
m2=Assign[wid] // m2 is the man id assigned to woman, wid by the algorithm
check preference list of wid // PLW[wid]
if (man mid is preferred over m2 by wid in PLW[wid])
Assign mid to wid
Assign=Assign union (wid,mid)
delete wid from preference list of man mid.
else //woman wid preference m2 the man previously assign to wid over the new man mid
delete wid from preference list of man mid
man mid still remains free even after the iteration of the loop and is taken for assocation later again by the algorithm.
In the end, the Assign will return the final associated pair of (man, woman) and the algorithm will terminate after all the man gets associated with some woman. Hopefully, this algorithm is explanoratory enough. If you have any query relating to the algorithm feel free to ask. In the Stable Marriage algorithm, every man will propose every woman only once, that is the reason we are deleting the woman id from the preference list of man, in the algorithm.
For the condition b:
There is possibility of weak instability with Stable Marriage problem. Let us understand this with the help of an example.
Let us consider, there are two men with id: m1,m2 and two women with id w1,w2.
Let the preference lists of men:
PLM:: m1: w2,w1
PLM:: m2: w2,w1
Let the preference lists of women :
PLW:: w1:m2,m1
PLW:: w2: m2,m1
The allocation generated by the Stable Matching algorithm will be:
m1 assigned to w1 and
m2 assigned to w2.
For weak instability problem, with man m and woman w assigned to w` and m`
m assigned to w, prefers w` over w
w assigned to m`, prefers m over m'.
Now for the association of the example considered, if we consider m
as m1, w` as w1, m` as m2 and w as w2 then, from the preference list of m1 we can deduce m1 is assigned to w1 but prefers w2, thereby generating a weak instability.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.