部分偏好下的稳定婚配问题来源：人大经济论坛论文库　作者：姜囡　时间：2013-06-07

部分偏好下的稳定婚配问题

姜囡（指导老师，陈金阳）

(湖北师范学院数学与统计学院 湖北 黄石，435002)

1. 引言

1.1研究背景及意义

 1962年两个数理经济学家David Gale和Lloyd Shapley在一篇名为“College Admissions and the Stability of Marriage”的论文中首次引出并介绍了稳定婚姻这个问题.考虑个男士的集合和个女士的集合.令便是所有可能的形如的有序对的集合, 其中,.一个匹配是来自的有序对的集合,并且具有下述性质:每个的成员和每个的成员至多出现在的一个有序对中一个完美匹配是具有下述性质的匹配：的每个成员和的每个成员恰好出现在一个对里.一个完美匹配仅仅对应于一个男士和女士配对的方式,以这种方式,每个人最终与某个人结婚,且没有人与多个人结婚—既没有单身的，也没有一夫多妻或一妻多夫的情况.在完美匹配的背景下又引入优先的概念,每个男士对所有的女士排名, 如果给的排名高于,我们就说偏爱超过.我们将把的按顺序的排名作为他的优先表,但我们不允许排名出现并列的类似的,每个女士也对所有男士排名给定一个完美匹配，在中存在两个对和,他们具有更偏爱而不爱,且更偏爱而不爱的性质.在这种情况下,没有什么能阻止和放弃他们当前的伴侣而走到一起，我们称这个完美匹配是不稳定的，我们称像这样的对是一个相对于的不稳定因素，(虽然不属于，但是和双方都偏爱另一方而不爱他们在中的伴侣我们说一个匹配是稳定的,那么要满足以下两点：（1）是完美匹配；（2）不存在相对于的不稳定因素.现在这个问题已经广泛的应用于婚配问题中.

1.2稳定配置理论综述

匹配问题的研究始于Gale-Shapely（1962）,是作为一种博弈问题进行刻画研究的, 主要解决的就是在价格机制不能发挥作用的情况下如何实现有效的资源配置,如很多公立学校不能向学生收取学费，器官移植因受到伦理道德的约束而不能进行单方面的转移支付，婚姻问题等.

假设两个非空集合和分别表示未婚男士和未婚女士的集合.我们在集合和定义如下的偏好关系：如果对于某个男士而言,比要好,就记作,如果该男士认为至少和一样好,就记作.即前者是严格的偏好关系,而后者包含严格偏好关系和无差异关系.类似的对于女士而言,可以定义和.

婚姻匹配：,则为映射,它满足：若,则；若,则.即对于而言,称为的配偶.则可知婚姻匹配为双射,它满足：.所有婚姻匹配（或简称匹配）的集合记为.我们用配对表示男士和女士在匹配下结婚,则且.

某社团中有n位女士和m位男士.假定每位女士按照其对每位男士作为配偶的偏爱程度排名次，无并列.也就是说，这种排列是纯顺序的，每位女士将这些男士的排列成顺序类似的,每位男士也对这些女士排列成顺序.婚姻匹配称为不稳定的,如果使得：

成立,我们说匹配被阻止了,称为阻止对（即和可以各自离开原来的婚姻安排,私自结婚）.反之若匹配不存在阻止对,则匹配称为稳定的.

本文主要应用稳定配置理论二分图最大匹配法及部分偏好下的GS算法对稳定婚配问题进行分析，通过构造满意度函数，对每个参与者进行匹配的满意度分析，说明参与者对部分偏好下的稳定不完全匹配结果的满意度更高，解释了“剩男剩女”现象产生的原因，试图给当前的婚恋网站和婚介所提供一定的参考.

1.3 有关基础知识

1.3.1 GS算法

已知所有人的喜好列表，且不存在独身主义者．在第一轮选择过程中，让这些男士去向他们最心仪（喜好列表中排序第一）的女士求婚.等所有男士求婚完毕后，所有收到求婚的女士都从自己的求婚者中（根据个人的喜好列表）选择自己最喜欢的人并且接受他为未婚夫，没人求婚的女士只能暂时等一等．以上过程称为一轮，之后的每一轮都按照类似的方式进行．

在第一轮结束后，还处于单身状态的男士中的每个人再次向还没有对其求婚过的女士中自己最喜欢的人求婚（无论女士是否已经有了未婚夫），然后，等所有单身男士求婚完毕后，所有收到求婚的女士都从自己的求婚对象中选择自己最喜欢的人接受为未婚夫．原来有未婚夫而求婚者中有自己更喜欢对象的女士会换掉自己的未婚夫．等到这一轮完毕之后，再开始如上所述的新一轮的求婚．依此类推，当所有女士（男士）都已订婚时，算法结束.为了计算GS算法的复杂度，在每一轮，接到求婚的女士有三种可能的情形，第一种是接受求婚者，第二种是拒绝这一轮的求婚者，第三种是解除婚约并接受这一轮的一个求婚者.对于第一种情形，她正好做一次选择，而对于后两种情形，她最多做次选择，因此，对每名女士这种算法有步骤，因此总共有步骤.具体的算法如下：

1.3.2 二分图最大匹配

给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配.

最大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数.最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配.选择这样的边数最大的子集称为图的最大匹配问题.设是一个图，M是E的一个子集，如果M不含环且任意两边都不相邻，则称M为G的一个匹配.G中边数最多的匹配称为G的最大匹配.对于图，在每条边e上赋一个实数权.设M是G的一个匹配.定义，并称之为匹配M的权.G中权最大的匹配称为G的最大权匹配.如果对一切，e∈E，w(e)=1,则G的最大权匹配就是G的最大匹配.

2. 二分图最大匹配下的稳定婚配

2.1二分图模型

用二分图来为这个问题建立数学模型.令是一个二分图，其中

为位女士的集合，

为位男士的集合.将每一个女-顶点（女士在左边）连接到每一个男-顶点（男士在右边）.所得的二分图在包含双方顶点集之间的所有可能边的意义下是完备的.对应每条边,存在一个数对，其中表示在给男士排序中的位置，表示在给女士排序中给女士排序中的位置.这些女士和男士的婚配对应二分图的（条边的）完美匹配.

在记法上，使用优先秩评定矩阵所提供的模型会更方便.该矩阵为-行列的阵列，行对应每一位女士，列对应每一位男士.在第行和第列交叉位置处放上代表给排的名次和给排的名次的数对，.一个婚配对应该矩阵上个位置的集合，该集合恰好包含每一行的一个位置和每一列的一个位置.

例2.1：当时，令男女偏好排名（）如下：

则优先秩评定矩阵为

存在6种可能的婚配.在女士优先的情况下，婚配的结果如下：

由于每一位女士都得到她的第一选择，这个婚配是稳定的，不过每位男士得到的却都是最末位的选择.另一稳定的结果是在男士优先的情况下，每位男士得到他的第一选择.

由此可见，对于每一个优先秩评定矩阵，都存在稳定的婚配策略.通过延迟认可算法，即Gale-Shapely算法可以实现.

在女优先的情况下，进行以下操作：

1）每一位落选女士在所有尚未拒绝她的男士中选择一位被他排名最优先的男士；

2）每一位男士在所有已经选择他，并且他尚未拒绝的女士中挑选被他排名最优先的女士，对她推迟决定，并于此时拒绝其余女士.

于是，在算法执行期间，由女士向男士求婚，一些男女订婚，但是，如果收到更好的求婚，男士可以悔婚.即算法中，一旦男士订婚，他就一直处在订婚状态，但是她的未婚妻可以改变；而且，对他来说每次改变都是一种改进.然而，女士则在算法执行期间订婚若干次；每一次对她来说都讲导致更不理想的伴侣.只要不存在被拒绝女士，那么每一位男士恰与一位女士订婚，由于人数相等，每一位女士也恰与男士订婚.现在将每一位男士和他订婚的女士配对就可以得到一种婚配.

2.2 算法性质

男女匹配问题中，最优状况莫过于每个人跟自己的第一选择匹配.但是，在大多数情况下这种匹配方案会因需求的双重巧合问题而无法实现.盖尔和夏普利从合作博弈的角度认为匹配的关键是稳定性：如果没有任何一对男女能够通过其他的匹配方式来提高自己的配对满意度，那么可以认为匹配是稳定的.这样的稳定配置满足两个条件：一是符合个人理性；二是实现两两稳定匹配.当匹配稳定时，就没有男士会喜欢除自己配偶以外的其他女士；同样，也没有女士会喜欢除自己配偶以外的其他男士，因此不存在任何一对男女背叛婚姻的情况.

根据上述说明可以知道，不管这N个man和N个woman的偏好表是如何分布的, 至少存在一个稳定婚姻匹配.且由男士发出婚约的Gale-Sharpley算法得到的稳定匹配，对于男士而言是最优匹配，每个男士在核中找得对应最优的女性配偶，而女士却在核中找得对应最差的男性配偶；同理，用由女士发出婚约的Gale-Sharley算法得到的稳定匹配，对于女士而言是最优匹配，每个女士在核中找得对应最优的男性配偶，而男士却在核中找得对应最差的女性配偶.

例2.2：在女优先的情况下，将延迟认可算法用于优先秩评定矩阵　　

算法结果为：

ⅰ）选择,选择,选择,选择,选择；拒绝，拒绝.

ⅱ）选择，选择;拒绝.

ⅲ) 选择;拒绝.

ⅳ) 选择;拒绝.

ⅴ) 选择;拒绝.

ⅵ) 选择.

在ⅵ）中，不存在拒绝，因而是稳定婚配.

在上述算法中，如果我们交换男女的角色，即在男优先的情况下，让男士按照他们排列的优先级别选择女士，同样，也可以得到一个稳定的婚配.算法结果如下：

ⅰ)选择，选择，选择，选择，选择.

ⅱ)拒绝，拒绝.

ⅲ)选择，选择.

婚配是稳定的.

由此可见，在二分图模型下，可以得到正好完全匹配的配对方式，而且男优先和女优先的匹配结果正好相同，说明在延迟算法中得到的婚配是稳定的，且一定存在一种配对结果.

3. 部分偏好下的稳定婚配问题

3.1 模型叙述

当今的青年男女总希望自己找到称心如意的终身伴侣，都希望建立一个美满幸福的家庭，现在是开放的年代，适龄青年男女的婚恋再也不是靠父母主婚、媒妁之言了，而是提倡婚姻自由，独立自主.但由于当事人的家庭情况、自身条件尤其是价值观、思想品德和文化素养各不相同，适龄青年的择偶观有了较大的变化.除了考虑对方的职务、地位、学历、名气，也追求对方的长相、身材、举止、风度等，当没有达到自己预期的条件时，很多人会选择“宁缺毋滥”.故在此算法的改进中，假设对方在接受到邀请时，只考虑自己偏好排名靠前的男士或女士，排名靠后的邀请，直接选择拒绝，不会单纯的为了婚配而盲目的接受邀请.

假设两个非空集合和分别表示名未婚男士和名未婚女士的集合.对每个集合和定义如下的偏好关系：如果对于某个男士而言,比要好,就记作,并对其偏好的前位女士进行偏好排列，即在严格的偏好关系下进行部分排序.同样的对某位女士做同样的偏好排序，即只对她偏好的前位男士进行部分排序.在GS算法的原理下，根据部分偏好下的偏好顺序对他们进行稳定婚配试验，得出匹配的结果，称这种情况下的婚配为部分偏好下的GS算法稳定婚配.

假设有3名男士和3名女士，婚配时只选择自己优先顺序的前2名，没有出现在偏好排序上的邀请对象直接拒绝，他们的部分偏好顺序如下（同例2.1）：

即当向发出邀请时，因不在偏好顺序中，故直接拒绝，即使单身也绝不委曲求全.

定义3.1：匹配率为配对成功的人数与参与人数比值，即.

从二分图最大匹配中可以知道，全偏好下的婚配是完全匹配，即匹配率=100%，由于部分偏好下只对前人进行了排序，通常得到的匹配结果是稳定不完全匹配，即一般情况下匹配率100%.

用表示偏好顺序，用表示偏好程度，则，其中为部分偏好下参与排名的人数，为总排名数.则匹配率为偏好顺序和偏好程度的函数，记为.

显然，稳定婚配的匹配率受男女士配对的偏好顺序和偏好程度影响，即在相同人数条件下，偏好程度不变时，不同的偏好顺序下匹配率不同；在偏好顺序不变时、不同的偏好程度下的匹配率也不相同.下面将具体对两个因素分析.

3.2 匹配率影响分析

假设参与婚配的男女各有个，根据上述的模型叙述可知，在给定一种偏好、偏好排列的人数的情况下，可以得出每种匹配的结果和匹配率.现在每种条件下，求解婚配情况.现给定2种全偏好的排列如下：

偏好排列1（）：

偏好排列2（）：

3.2.1 偏好顺序对匹配率的影响

假定时，

情况1：现男士和女士双方有如下偏好排序（参考）：

重复例2.2中的匹配过程，在男优先的情况下，得到的稳定不完全匹配的最终结果为：；在女优先的情况下，得到的匹配结果为，可见，男优先和女优先的结果一致，说明部分偏好下的婚配是稳定的，此时匹配率.

情况2：，现男士和女士双方有如下偏好排序（参考）：

在这种情况下，男优先的最终结果为：，女优先的最终结果为，男优先和女优先的结果一致，说明这种方法下的婚配同样是稳定的，但是此时匹配率.

当参与婚配的人数、部分偏好下参与排名的人数均相同时，即，在偏好排列1下的稳定不完全婚配中，得到的匹配率为80%，而在偏好排列2下的稳定不完全婚配中，得到的匹配率为60%,由此可见偏好顺序直接影响着部分偏好下的匹配率.

3.2.1 偏好程度对匹配率的影响

为进一步了解影响稳定婚姻匹配率的因素，不妨调整参与人数和偏好的排名数来讨论稳定婚配的情况.

情况1：当时，参考，男女士的部分偏好如下：

重复上述婚姻匹配的过程，在男优先的情况下，得到的稳定不完全配对结果为：，此时未能成功配对，即落单.在女优先的情况下，得到的配对结果为：，同样的，未能成功配对.在部分偏好下的GS算法中，婚姻匹配结果是稳定的，且存在一种不完全匹配的结果.此时成功匹配4对，匹配率.

情况2：当时，同样参考，男女士的偏好顺序如下：

在这种情况下，男优先的最终结果为：，女优先的最终结果为，男优先和女优先的结果一致，说明这种方法下的婚配同样是稳定的，但是此时匹配率.

对比发现，在这种偏好的排列下，婚配的双方选择参与匹配的人数不同时，得到的配对结果及匹配率都是不一样的.

情况3：当，时，参考，这种情况下的男女偏好为：

此时稳定不完全婚配的结果为，剩余1名男士和1名女士落单，此时匹配率.

从上述分析过程中发现：

（1）当参与人数相同（）时，而偏好程度不同（不同）时，匹配率不同.越大，匹配率越大（时，，时，）.

（2）当相同（），而参与人数不同时，匹配率也不同.越大，匹配率<
参考文献：
　　 [1] D.Gale and L.S.Shapley. College Admissions and the Stability of Marriage[J]. The American Mathmatical Monthly. Jan ,1962 .Vol. 69 , No. 1.45-50 [2]王朝瑞.图论[M].第3版.北京:北京理工大学出版社,2004:130-132. [3]谭浩