浅谈稳定完备婚姻的算法及推广.doc

第 1 页浅谈稳定完备婚姻的算法及推广 话说在 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）是一个二分图，其中 }{21nwwwXL，，为 n 位女士的集合，而}{21nmmmYL，，为 n 位男士的集合将每一个女-顶点（女士在左边）连接到每一个男-顶点（男 士在右边） 所得的二分图在包含双方顶点集之间的所有可能边的意义下是完备的。

对 应每条边,存在一个数对 p，q，其中 p 表示在给男士排序中的位置，q}{jimw，iwjm表示在给女士排序中给女士排序中的位置这些女士和男士的完备婚姻对应二分jmiw图 G 的（n 条边的）完美匹配浅谈稳定完备婚姻的算法及推广第 2 页在记法上，使用优先秩评定矩阵所提供的模型会更方便该矩阵为一 n 行 n 列的 阵列，n 行对应每一位女士，n 列对应每一位男士在第nwww，，，L21nmmm，，，L21 i 行和第 j 列交叉位置处放上代表给排的名次和给排的名次的数对 p，qiwjmjmiw一个完备婚姻对应该矩阵上 n 个位置的集合，该集合恰好包含每一行的一个位置和每 一列的一个位置 例 1 令 n=3，并令优先秩评定矩阵为31132222311313, 223 , 1321321，，，，，，，，wwwmmm存在 3！=6 种可能的完备婚姻一种是332211mwmwmw，，由于每一位女士都得到她的第一选择，这个完备婚姻是稳定的，不过每位男士得 到的却都是最末位的选择另一中稳定的完备婚姻是通过是每位男士得到他的第一选 择而得到的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因此，不存在不稳定的配对，该完备婚姻 是稳定的浅谈稳定完备婚姻的算法及推广第 3 页2.3 延迟认可算法的举例延迟认可算法的举例例 2 将延迟认可算法用于优先秩评定矩阵32434431413433122413214214231221，，，，，，，，，，，，，，，，DCBAdcba算法结果为： 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 在ⅵ）中，不存在拒绝，因而 dDaCcBbA，，， 是稳定完备婚姻 在延迟认可算法中，如果我们交换男女的角色，让男士按照他们排列的优先级别 选择女士，那么我们得到一个稳定的完备婚姻，婚姻可能但不是必须不同于让女士选 择男士所得到的稳定完备婚姻 例 3 将延迟认可算法用于上例中的优先秩评定矩阵，其中男士选择女士结果为：i) a 选择 C，b 选择 A，c 选择 B，d 选择 A ii) A 拒绝 d，d 选择 B；B 选择 d。

iii) D 选择 D 完备婚姻 DdBcAbCa，，， 是稳定的，这是以相反的方式利用该算法所得到的相同的完备婚姻 在一个稳定完备婚姻中，如果以为女士得到作为配偶的男士比她在每一其他的稳 定完备婚姻所得到的配偶在她的排序表中至少有同样高的优先级，那么，这个稳定的 完备婚姻叫做是对该女士最优的换句话说，不存在使得该女士得到在她的排序中具 有更高级别排序的配偶的稳定完备婚姻如果一稳定完备婚姻对每一位女士都是最优 的，则称该完备婚姻是对女士最优的我们用类似的方法定义对男士最优的稳定完备 婚姻然而，存在女士优先的和男士优先的稳定完备婚姻就不是明显的了事实上， 如果每一位女士独立地得到所有稳定完备婚姻中最好的伴侣，结果导致一次男女配对， 这个结论是不明显的（可以想象用这种方法的结果有可能会导致两位女士得到相同的 男士） 显然，可能只存在一种女士最优的完备婚姻和只存在一种男士最优的完备婚姻2.4 延迟认可算法的性质延迟认可算法的性质按照 Gale-Shapely 算法，我们一定能得到一个稳定婚姻也就是说，不管这N个 男人和N个女人的优先表是如何分布的，至少存在一个稳定婚姻匹配在“男优先”算浅谈稳定完备婚姻的算法及推广第 4 页法实现中，得到的一个稳定婚姻匹配具有如下三点性质： （1） 男性能够获得尽可能好的伴侣，结果是：如果还存在其他的稳定匹配，那 么里面任何一个男性的伴侣排名都不会比“男优先”得到的结果更好，我们说此种情 况每个男性获得的是“最好”的伴侣。

（2） 女性却只能被动地一步步接近她最爱的目标, 但最后往往达不到，结果是： 如果还存在其他的稳定匹配，那么里面任何一个女性的伴侣排名都不会比“男优先” 得到的结果更差，我们说此种情况每个女性获得是“最差”的伴侣 （3） 无论男性们求婚的先后顺序如何，最终得到的是同一个稳定婚姻匹配当 然，这个算法的实现也可是：“女优先”，同样，得到的此稳定婚姻匹配具有对应的 三点性质： （1） 在所有可能的稳定婚姻匹配中，“女优先”得到的结果中每个女性获得的 是“最好”的伴侣 （2） 在所有可能的稳定婚姻匹配中，“女优先”得到的结果中每个男性获得的 是“最差”的伴侣 （3） 无论女性们求婚的先后顺序如何，“女优先”最终得到的是同一个稳定婚 姻匹配3、稳定完备婚姻的推广及应用、稳定完备婚姻的推广及应用我们先来看下面的问题：在一个小型的人才交流市场，有 5 个公司需要招聘工作 人员，聘的人数分数为我们先来做一个简化，假设参加竞聘的人54321nnnnn，，，，数就是，参加竞聘的人根据这几个公司的广告宣传以及平时对54321nnnnnn公司的了解确定对这几个公司的偏爱程度并进行排名（编号） ，并且我们规定每个人对 这几个公司的偏爱程度是不同的，即不允许同一个人对不同公司的编号相同。

同样地, 每个公司根据竞聘人员的材料也对竞聘人员进行编号，编号规则与上面的一样. 问题 是怎样分配才能使招聘工作相对稳定 我们做如下规定，如果有下面的情况发生， 就称这种分配是不稳定的： 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，就 是一个稳定的分配. 但对于一个复杂的问题，怎样才能找到一个稳定的分配呢？浅谈稳定完备婚姻的算法及推广第 5 页在前面写到的是利用优先秩评定矩阵给出了一对一( 即一个公司录用一人) 的稳 定分配的算法:延迟认可算法 我们现在把这个算法做一个推广， 使其可以方便地找到一对多的稳定分配 为此，我们引入一个矩阵，这个矩阵的行的标号是公司，列的标号是竞聘人，对 应的元素是一个有序数对，数对的第一个分量是对应的公司的排名中该竞聘人所处的 位置，第二个分量则表示该公司在对应的竞聘人的排名中所处的位置，我们称这个矩 阵为广义优先秩评定矩阵 如在例 4 中，其广义优先秩评定矩阵为14132225212524131211，，，，，，，，，，BAedcba利用这个矩阵，我们可以将延迟认可算法推广为 广义延迟认可算法 （1） 每个公司按它的排名顺序选最前面的它所需要的人数 （2） 如果有人被多个公司选中, 则该人选择在他的排名中名次最靠前的公司, 并拒绝后面的公司 （3） 被拒绝的公司在未拒绝它的人中选排名最靠前的。