学习资源 学堂在线 清华大学 算法设计与分析
算法案例只为学习方便 无任何现实生活指导意义或冒犯意图 且不代表任何人观点
- 贪婪算法 greed
- 分治算法 divide-and-conquer
- 动态规划 dynamic prograamming
- 网络流 network flow
- 计算难解性 intractablity
- 近似算法 approxiamation algorithms
- 局部搜索 local search
- 随机算法 randomized algorithms
……
一、稳定匹配 Stable Matching
1. 不稳定 与稳定分配
稳定分配：没有不稳定对的完美分配
对于给定的n个男性和n个女性，每个人给出自己对于异性的偏好，可以从喜欢到不喜欢列出偏好矩阵
稳定则为 所有人都没有改变配偶的动机
不稳定对：男人m和女人w没有配对在一起，但是m和w相互更偏好，则m和w为不稳定对
2.追求拒绝算法 GS算法 Propose-And-Reject Algorithm [Gale-Shapley 1962]
initialize S to empty matching """一个空的匹配S"""
while (some man m is unmatched) and (m has not proposed to everywoman) do
"""当存在男性m 没有配and没有追求过所有的女性"""
w ← first woman on the list of m to whom m has not yet proposed. """m喜欢的没追过的女性为w"""
if w is unmatched """如果w没有配偶"""
add pair m-w to S
else if w prefers m to her current partner m' """如果比起现有的配偶w更喜欢m"""
remove pair m'-w from S
add pair m-w to S
else
w rejects m
return stable matching S
正确性证明：
- 有限结束
- 该算法中，男性总是按照偏好顺序追求女性，其偏好顺序中会从最喜欢到最不喜欢 囊括所有参与配对的女性
- 该算法中，女性一旦开始配对，就不会回到未配对状态，只会转而选择 （追求她的） and（她更喜欢的） 男性
综上所述，该算法至多会在n^2次迭代后结束循环（n个男人各追求n次不同的女性）；
- 完美性：算法结束所有人都有配偶
反证法：
- 假设，算法结束有一男性a没有找到自己的配偶，因为男女数目相同，则必存在一女性b也没有配偶，那么说明b还未被男性追求过；
- 但是，算法结束说明a必然已经追求过包括b在内的所有女性；
- 所以存在矛盾
- 稳定：不存在不稳定对
反证法：
- 假设，有 A-Z是不稳定对，即A和Z相互更偏好
- 情况1 Z从未追求过A ，说明Z更偏好别人，A-Z稳定
- 情况2 Z追求过A， 说明A曾拒绝过Z（相比Z，A更偏好别人），A-Z稳定
- 所以存在矛盾
综上所述，该算法是有限结束，完善，得出的是稳定匹配
对于具体实例可能有多个稳定匹配结果时
GS算法是 男性按照喜好顺序追求女性 所以是男性最优稳定匹配，女性最差稳定匹配
可能会掩盖真实偏好
在这一算法中 女性可以通过说谎获得更好的男性配偶
（在有反选机会的时候说谎，使得一名男性q去追求别的女性p，若该名女性p更喜欢q则原先已经与p配对的x就又要重新追求女性，从而说谎的女性可能会获得自己更偏好的男性，尽管该名男性的偏好列表中说谎的女性排名靠后）男性最优匹配故男性没有说谎动机
应用
- 2012 经济 诺贝尔奖
Shapley 提出稳定匹配理论，建立GS算法
Roth 将GS算法应用到 医院与医科生的招聘，和器官捐赠者与病人的匹配中 - 可以扩展到生活中任何 两方相互匹配的场景中，会使得甲方处于优势，乙方处于劣势，乙方中的成员可通过说谎得到更好的匹配
