文档介绍：算法-稳定匹配StableMatching
第一页，共22页。
Stable Matching
第二页，共22页。
Matching Residents to Hospitals
Goal. Given a se1st
2nd
3rd
Women’s Preference Profile
favorite
least favorite
favorite
least favorite
*
第六页，共22页。
Stable Matching Problem
Q. Is assignment X-C, Y-B, Z-A stable?
A. No. Bertha and Xavier will hook up.
Zeus
Amy
Clare
Bertha
Yancey
Bertha
Clare
Amy
Xavier
Amy
Clare
Bertha
Clare
Xavier
Zeus
Yancey
Bertha
Xavier
Zeus
Yancey
Amy
Yancey
Zeus
Xavier
1st
2nd
3rd
1st
2nd
3rd
favorite
least favorite
favorite
least favorite
Men’s Preference Profile
Women’s Preference Profile
*
第七页，共22页。
Stable Matching Problem
Q. Is assignment X-A, Y-B, Z-C stable?
A. Yes.
Zeus
Amy
Clare
Bertha
Yancey
Bertha
Clare
Amy
Xavier
Amy
Clare
Bertha
Clare
Xavier
Zeus
Yancey
Bertha
Xavier
Zeus
Yancey
Amy
Yancey
Zeus
Xavier
1st
2nd
3rd
1st
2nd
3rd
favorite
least favorite
favorite
least favorite
Men’s Preference Profile
Women’s Preference Profile
*
第八页，共22页。
Stable Roommate Problem
Q. Do stable matchings always exist?
A. Not obvious.
Stable roommate problem.
2n people; each person ranks others from 1 to 2n-1.
Assign roommate pairs so that no unstable pairs.
Observation. Stable matchings do not always exist for stable roommate problem.
B
Bob
Chris
Adam
C
A
B
D
D
Doofus
A
B
C
D
C
A
1st
2nd
3rd
A-B, C-D B-C unstable A-C, B-D A-B unstable A-D, B-C A-C unstable
*
第九页，共22页。
Propose-and-reject algorithm. [Gale-Shapley 1962] Intuitive method that guarantees to find a stable matching.
Propose-And-Reject Algorithm
Initialize each person to be free.
while (some man is free and hasn't proposed to every woman) {
Choose such a man m
w = 1st woman on m's list to whom m has not yet proposed
if (w is free)
assign m and w to be engaged
else if (w prefers m to her fiancé m')
assign m and w to be engaged, and m' to be free