Book: Algorithm Design (Text book :Kleinberg, J. & Tardos, E. (2014). Algorithm
ID: 3698986 • Letter: B
Question
Book: Algorithm Design (Text book :Kleinberg, J. & Tardos, E. (2014). Algorithm Design. Harlow, Essex, U.K.: Pearson. ISBN: 9780321295354)
2. For this problem, we will explore the issue of truthfulness in the Stable
Matching Problem and specifically in the Gale-Shapley algorithm. The
basic question is: 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 m and ra’ on her list of preferences (i.e.,
by falsely claiming that she prefers m’ to m) and nmning the algorithm
with this false preference list, w will end up with a man m" that she truly
prefers to both m and m’? (We can ask the same question for men, but
will focus on the case of women for purposes of this question.)
Resolve this question by doing one of the following two things:
(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
Please find my answer:
Yes, it’s possible.Consider the following instance with n=3 men and women.Woman w3 will lie in this instance;the first six columns are true preferencelists, and the final one is w3’s false, but stated, preference list.For the sake ofthis example, let’s assume that G-S breaks ties by using the lowest-numberedunmatched man to ask;similar examples exist for other tiebreakers.
m1m2m3w1w2w3w3’w3w1w3m1m1m2m2w1w3w1m2m2m1m3w2w2w2m3m3m3m1Initially, with the listed tie-breaker, Gale-Shapley will produce the pairs(m1,w3) (m2, w1) and (m3,w2).However, if w3’s false preference list isused (and the other five remain truthful), we are left with (m1,w1), (m2,w3),and (m3,w2) -- leaving w3 with her truly first choice
It is possible for a woman to “game” the system.Assume we have three men,m1tom3and three womenw1tow3with the following (true)preferences:•m1:w3,w1,w2•m2:w1,w3,w2•m3:w3,w1,w2•w1:m1,m2,m3•w2:m1,m2,m3•w3:m2,m1,m3First consider a possible execution of Gale-Shapley with these true preference lists. Firstm1proposes tow3thenm2proposes tow1. Thenm3proposes tow2andw1and gets rejected,?nally proposes tow2and is accepted. This execution forms pairs (m1,w3), (m2,w1), and(m3,w2), thus pairingw3withm1, who is her