Consider an extension to the stable marriage problem in which each woman express
ID: 667881 • Letter: C
Question
Consider an extension to the stable marriage problem in which each woman expresses preferences over some subset of the men; she finds the remaining men unacceptable and she'd rather be alone than be married to any of these unacceptable men. Similarly, each man has preferences over a subset of women and finds the remaining women unacceptable In this setting, a marriage M is a set of (m, w)-pairs such that each woman appears in at most one pair in M; similarly, each man appears in at most one pair in M. Furthermore, for every (m, w) E M, m finds w acceptable and w finds ma acceptable. A marriage M is stable if there is no (m, w M such that (i) m and w are acceptable to each other and (ii) m is unmarried or m is married and prefers w to his current partner and (iii) w is unmarried or w is married and prefers m to her current partner (a) Describe an efficient algorithm (using pseudocode) that computes a stable marriage in this setting. Use the style and level of detail that we used for the Gale-Shapley algorithm in class. Your algorithm needs to be correct, but you do not have to provide a proof of correctness. (b) Suppose that each man and each woman has preferences for at most t individuals where 0 St S n. What is the size of the input to the problem? What is the running time of your algorithm as a function of the input sizeExplanation / Answer
a)
For each woman
For each man in the list of the woman's preference {
If the woman is in the list of the man's preferred women {
If the man is married {
If the woman is in a higher position of preference than the man's wife {
Divorce from wife
Marry the woman
}
else {
Do nothing
}
}
else {
Marry the man
}
}
else {
Do Nothing
}
}
The proposed solution is stable but it's not necessarlly optimal for all individual's points of view, as we are starting to set the pairs by taking elements from the women group first, so we are prioritizing them.
b)
The size of the input would still be N because, as I said before, we are considering all the elements of the group and for each of them we are finding a stable pair. All this could be summarized by saying that the algorith is linear, and that's the reason.
The running time would be O(n*t) in the worst case, being that only the last man in the preference list of each woman is the one that has hew in his list or in a higher position in it than actual wife. Howvever, this is variable, because for each woman, the man she ends up pairing with could be at any position in her list of preference.