By utilizing the Gale-Shapley algorithm for the Stable Matching Problem, can a m
ID: 668547 • Letter: B
Question
By utilizing the Gale-Shapley algorithm for the Stable Matching Problem, can a man or a woman end up better off by lying about his or her preferences? More concretely, we suppose each participant has a true preference order. Now consider a woman w. Suppose w prefers man m to m', but both m and m' are low on her list of preferences. Can it be the case that by switching the order of and m on her list of preferences and running the algorithm with this false preference list, w will end up with a man" that she truly prefers to both m and m'? Either a) give a proof that, for any set of preference lists, switching the order of a pair on the list cannot improve a woman's partner in the Gale-Shapley algorithm; or b) give an example of a set of preference lists for which there is a switch that would improve the partner of a woman who switched preferences.
Explanation / Answer
Answer:
B)
Example:
Consider there are three men in a list say M1, M2 and M3. Similarly, consider there are three women in a list say W1, W2 and W3. The order of preferences for each man and woman are given as,
M1: W3W1W2, M2: W1W3W2 AND M3:W3W1W2
W1: M1M2M3, W2: M1M2M3 AND W3: M2M1M3
According to the preferences, W3 is containing true preferences. Thus, change the order of W3 preferences to W’3 preference.
This can be tabulated as,
Men preferences
Women preferences
W’3 alternate preferences
M1
M2
M3
W1
W2
W3
W’3
W3
W1
W3
M1
M1
M2
M2
W1
W3
W1
M2
M2
M1
M3
W2
W2
W2
M3
M3
M3
M1
By using W3 true preference list, execute the Gale-Shapley algorithm. The execution of the algorithm results as:
M1
W3
W3
M2
W1
W1
M3
[W3][W1]W2
W2
After execution, the pairs formed are (M1, W3), (M2, W1) and (M3, W2).
Now, execute the Gale-Shapley algorithm for the list of preferences for W3 by choosing the list of men from M3 to M1. The execution of the algorithm results as:
M1
W3
-
W1
W1
M2
W1
-
W3
W3
M3
[W3][W1]W2
-
[W1]W2
W2
Now according the order of switching from the above table, M1 first proposes W3 and leave her and propose to W1. This results as pair (M1, W1).
M2 first proposes W1 after proposing M2 leaves her propose to W3. This results as a pair(M2, W3).
M3 first proposes W1 and was recently left by W3. After that he pairs up with W2. This results as a pair(M3, W2).
If observed, W3 ends up with pairing with M2. In this, matching pair, W3’s true selection is M2.
Thus, it is clear that by falsely pairing or switching the order of the W3 preferences, a woman might get a truly desirable partner by using the Gale-Shapely algorithm.
Men preferences
Women preferences
W’3 alternate preferences
M1
M2
M3
W1
W2
W3
W’3
W3
W1
W3
M1
M1
M2
M2
W1
W3
W1
M2
M2
M1
M3
W2
W2
W2
M3
M3
M3
M1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.