浅谈稳定完备婚姻的算法及推广话说在1962年，两个数学家David Gale 和Lloyd Shapely 提出了下面的问题：给定若干个男生和同样多的女生，他们每个人都对所有的异性有一个心理的偏好次序。
是否存在一种男女配对组合构成一种稳定的组合关系？这里稳定组合的意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
（可以理解，这样的异性太容易红杏出墙了，所以是某种不稳定因素。
）进一步的问题是，在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式（如果它存在的话）？你可以理解为这是数学家们替月老问的问题：给定一群孤男寡女，寻找一种牵红线的方式，以确保把红杏扼杀在摇篮里。
1、稳定完备婚姻上面这一问题被称为稳定婚姻问题。
它有很多种可能的解法。
为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特定的数学价值。
当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？我们看下面的例题： 某社团中有n 位女士和m 位男士。
假定每位女士按照其对每位男士作为配偶的偏爱程度排名次，无并列。
也就是说，这种排列是纯顺序的，每位女士将这些男士的排列成顺序 1,2,3,… ,n ，类似的,每位男士也对这些女士排列成顺序1，2，3,…，n,我们知道，在这个社团里配对成完备婚姻的方式有n!种。
假定某种婚姻匹配中存在女士A 和 B 及两位男士a 和b,使得i) A 和a 结婚；ii) B 和b 结婚；iii) A 更偏爱b （名次更优先）而非a ；iv) B 更偏爱A 而非B 。
那么，我们认为该完备婚姻是不稳定的。
因为在这种假设下，A 和b 可能会背着别人相伴逃跑，他们都认为，与当前配偶相比每个都更偏爱自己的新伴侣。
如果完备婚姻不是不稳定的，我们则称其为稳定的完备婚姻。
2、稳定完备婚姻的算法2.1 建立模型用二分图来为这个问题建立数学模型。
令G=（X,△,Y ）是一个二分图，其中}{21n w w w X ，，=为n 位女士的集合，而}{21n m m m Y ，，= 为n 位男士的集合。
将每一个女-顶点（女士在左边）连接到每一个男-顶点（男士在右边）。
所得的二分图在包含双方顶点集之间的所有可能边的意义下是完备的。
对应每条边}{j i m w ，,存在一个数对p ，q ，其中p 表示在i w 给男士排序中j m 的位置，q 表示在给女士排序中j m 给女士排序中i w 的位置。
这些女士和男士的完备婚姻对应二分图G 的（n 条边的）完美匹配。
在记法上，使用优先秩评定矩阵所提供的模型会更方便。
该矩阵为一n 行n 列的阵列，n 行对应每一位女士n w w w ，，， 21，n 列对应每一位男士n m m m ，，， 21。
在第i 行和第j 列交叉位置处放上代表i w 给j m 排的名次和j m 给i w 排的名次的数对p ，q 。
一个完备婚姻对应该矩阵上n 个位置的集合，该集合恰好包含每一行的一个位置和每一列的一个位置。
例1 令n=3，并令优先秩评定矩阵为31132222311313,223,1321321，，，，，，，，w w w m m m 存在3！=6种可能的完备婚姻。
一种是332211m w m w m w ↔↔↔，，由于每一位女士都得到她的第一选择，这个完备婚姻是稳定的，不过每位男士得到的却都是最末位的选择。
另一中稳定的完备婚姻是通过是每位男士得到他的第一选择而得到的。
2.2延迟认可算法的基本思想问题：对于每一个优先秩评定矩阵，都存在稳定的完备婚姻策略。
如何找到一个稳定的完备婚姻?通过延迟认可算法（Gale-Shapely 算法）先对所有女士进行落选标记开始。
当存在落选女士时，进行以下操作1）每一位落选女士在所有尚未拒绝她的男士中选择一位被他排名最优先的男士2）每一位男士在所有已经选择他，并且他尚未拒绝的女士中挑选被他排名最优先的女士，对她推迟决定，并于此时拒绝其余女士。
于是，在算法执行期间，由女士向男士求婚，一些男女订婚，但是，如果收到更好的求婚，男士可以悔婚。
即算法中，一旦男士订婚，他就一直处在订婚状态，但是她的未婚妻可以改变；而且，对他来说每次改变都是一种改进。
然而，女士则在算法执行期间订婚若干次；每一次对她来说都讲导致更不理想的伴侣。
只要不存在被拒绝女士，那么每一位男士恰与一位女士订婚，由于人数相等，每一位女士也恰与男士订婚。
现在将每一位男士和他订婚的女士配对就可以得到一种完备婚姻，而且可以证明，这种完备婚姻是稳定的。
考虑女士A 和B 及男士a 和b ，是A 与a 配对，B 与b 配对，但是A 更偏爱b 而不是a 。
我们证明b 不可能比起偏爱B 来更偏爱A 。
由于在算法的某个阶段A 在a ，b 间更偏爱b, A 选择b ，但 A 因b 将某位女士排得更优先而被b 拒接过。
但是，在算法过程中与男士b 配对的女士实际上至少与他拒接过的任何女士有同等的优先级。
既然A 被b 拒接过，b 必然更偏爱B 而不是A 。
因此，不存在不稳定的配对，该完备婚姻是稳定的。
2.3 延迟认可算法的举例例2 将延迟认可算法用于优先秩评定矩阵32434431413433122413214214231221，，，，，，，，，，，，，，，，D C B A dc b a算法结果为：i) A 选择a ，B 选择b ，C 选择d ，D 选择a ；a 拒绝D 。
ii) D 选择d ，d 拒绝C 。
iii) C 选择a ；a 拒绝A 。
iv) A 选择b ；b 拒绝B 。
v) B 选择a ；拒绝B 。
vi) B 选择 c 。
在ⅵ）中，不存在拒绝，因而d D a C c B b A ↔↔↔↔，，，是稳定完备婚姻。
在延迟认可算法中，如果我们交换男女的角色，让男士按照他们排列的优先级别选择女士，那么我们得到一个稳定的完备婚姻，婚姻可能但不是必须不同于让女士选择男士所得到的稳定完备婚姻。
例3 将延迟认可算法用于上例中的优先秩评定矩阵，其中男士选择女士。
结果为： i) a 选择C ，b 选择A ，c 选择B ，d 选择Aii) A 拒绝d ，d 选择B ；B 选择d 。
iii) D 选择D 。
完备婚姻D d B c A b C a ↔↔↔↔，，，是稳定的，这是以相反的方式利用该算法所得到的相同的完备婚姻。
在一个稳定完备婚姻中，如果以为女士得到作为配偶的男士比她在每一其他的稳定完备婚姻所得到的配偶在她的排序表中至少有同样高的优先级，那么，这个稳定的完备婚姻叫做是对该女士最优的。
换句话说，不存在使得该女士得到在她的排序中具有更高级别排序的配偶的稳定完备婚姻。
如果一稳定完备婚姻对每一位女士都是最优的，则称该完备婚姻是对女士最优的。
我们用类似的方法定义对男士最优的稳定完备婚姻。
然而，存在女士优先的和男士优先的稳定完备婚姻就不是明显的了。
事实上，如果每一位女士独立地得到所有稳定完备婚姻中最好的伴侣，结果导致一次男女配对，这个结论是不明显的（可以想象用这种方法的结果有可能会导致两位女士得到相同的男士）。
显然，可能只存在一种女士最优的完备婚姻和只存在一种男士最优的完备婚姻。
2.4延迟认可算法的性质按照 Gale-Shapely 算法，我们一定能得到一个稳定婚姻。
也就是说，不管这N 个男人和N 个女人的优先表是如何分布的，至少存在一个稳定婚姻匹配。
在“男优先”算法实现中，得到的一个稳定婚姻匹配具有如下三点性质：（1） 男性能够获得尽可能好的伴侣，结果是：如果还存在其他的稳定匹配，那么里面任何一个男性的伴侣排名都不会比“男优先”得到的结果更好，我们说此种情况每个男性获得的是“最好”的伴侣。
（2） 女性却只能被动地一步步接近她最爱的目标, 但最后往往达不到，结果是：如果还存在其他的稳定匹配，那么里面任何一个女性的伴侣排名都不会比“男优先”得到的结果更差，我们说此种情况每个女性获得是“最差”的伴侣。
（3） 无论男性们求婚的先后顺序如何，最终得到的是同一个稳定婚姻匹配。
当然，这个算法的实现也可是：“女优先”，同样，得到的此稳定婚姻匹配具有对应的三点性质：（1） 在所有可能的稳定婚姻匹配中，“女优先”得到的结果中每个女性获得的是“最好”的伴侣。
（2） 在所有可能的稳定婚姻匹配中，“女优先”得到的结果中每个男性获得的是“最差”的伴侣。
（3） 无论女性们求婚的先后顺序如何，“女优先”最终得到的是同一个稳定婚姻匹配。
3、稳定完备婚姻的推广及应用我们先来看下面的问题：在一个小型的人才交流市场，有5个公司需要招聘工作人员，聘的人数分数为54321n n n n n ，，，，。
我们先来做一个简化，假设参加竞聘的人数就是54321n n n n n n ++++=，参加竞聘的人根据这几个公司的广告宣传以及平时对公司的了解确定对这几个公司的偏爱程度并进行排名（编号），并且我们规定每个人对这几个公司的偏爱程度是不同的，即不允许同一个人对不同公司的编号相同。
同样地, 每个公司根据竞聘人员的材料也对竞聘人员进行编号，编号规则与上面的一样. 问题是怎样分配才能使招聘工作相对稳定。
我们做如下规定，如果有下面的情况发生， 就称这种分配是不稳定的：1. 竞聘人a 被公司A 录用；2. 在竞聘人a 的排名中,公司B 在公司A 的前面；3. 在公司B 所录用的人员中，至少有一个人b,使得在B 的排名中a 在b 的前面，否则称分配为稳定的。
所谓的分配不稳定性是比较容易理解的，如果上面三种情况同时发生，则a 认为公司B 比公司A 更好，同时公司B 认为a 比b 更能为本公司创造财富，a 就会选择公司B ，从而使得a 在公司A 工作造成不稳定因素。
3.1广义延迟认可算法例4 在两个公司，A,B 录用五个人a ，b ，c ，d ，e 的分配中，A 选三个人，B 选两个人。
a ，b ，c 均把公司A 排在第一位，d ，e 均把B 排在第一位。
A 对五个人的排名为a ，b ，c ，d ，e,而B 的排名为a ，c ，d ，e ，b 。
如果最后的结果是A 选a ，c ，e ，而B 选b ，d ，则这种分配是不稳定的。
因为b 首选公司A ，同时A 也认为b 比较适合本公司（b 在A 的排名中为第二位），于是A 不会要e 而会录用b, 如果硬把e 放在公司A ，势必会造成人员的不稳定。
当然,对于这个简单的问题，容易看出，只要让A 录用a ，b ，c ，B 录用d ，e ，就是一个稳定的分配. 但对于一个复杂的问题，怎样才能找到一个稳定的分配呢？在前面写到的是利用优先秩评定矩阵给出了一对一( 即一个公司录用一人) 的稳定分配的算法:延迟认可算法。
我们现在把这个算法做一个推广， 使其可以方便地找到一对多的稳定分配。