婚恋市场中的双边匹配问题及其优化探究

（1）研究背景

经济社会的快速发展以及城市化水平的不断提高，人们的生活节奏也越来越快，许多适龄婚恋男女的生活圈子越来越窄，找到合适的婚恋对象成为当今社会许多个人与家庭的一大烦恼。男女婚恋不仅仅是一个个人问题、家庭问题，还是一个重要的社会问题。当前男女婚恋已经成为社会关注的一个重要的焦点问题，大龄剩男剩女也成为人们提及的热点词汇，也体现了人们对社会男女婚恋问题的重视程度。在中国乡村，传统的媒婆作为男女婚恋的中介，在撮合男女婚恋方面一直以来发挥着关键作用；在城市基于实体店的婚恋中介是以往男女婚恋匹配的重要机构，至今仍在发挥着一定的作用。但随着互联网的发展，尤其是移动互联网的普及，基于电子中介的婚恋网站成为城市男女婚恋的首选。婚恋网站区别于传统媒婆与实体店中介的重要特点在于能够快速聚合大量的婚恋男士与女士，为男女双方提供了大量可供选择的候选婚恋对象。男士或女士只需要向婚恋网站交纳一定的费用成为婚恋网站的会员就可以通过网站看到大量女士或男士的信息，从中可以选择自己感兴趣的异性，然后通过婚恋网站的联系方式与之沟通交流与约会；如果通过交往后发现彼此并不适合，男士或女士可以继续通过婚恋网站选择下一个自己感兴趣的女士或男士作为约会对象，直至找到自己满意的婚恋对象。基于电子中介的婚恋网站消除了以往地理区域带来的限制，可以随时随地向男女提供婚恋服务。但当前存在的大多数婚恋网站只具备男士或女士选择自己感兴趣的女士或男士功能，几乎都没有同时考虑男女双方的需求，往往男士对女士非常满意，但女士却不一定对男士感兴趣。同时考虑男女双方需求，实现双方的最优匹配是一个值得研究的课题。

（2）婚恋匹配相关研究

①稳定匹配性质研究

婚恋匹配问题最早由Gale和Shapley在1962年提出，他们对婚恋男女双方给出严格偏好序信息的稳定匹配问题进行了开创性研究，发现严格偏好序信息下稳定匹配总是存在的，并提出了获得男士和女士最优稳定匹配的延迟接受算法[38]。Mc Vitie和Wilson（1971）[73]针对具有严格偏好序信息的婚恋匹配问题，在Gale和Shapley的基础上进行了深入研究，研究发现了一个重要现象：在男士和女士形成的所有稳定匹配中，没有实现匹配（即单身）的男士和女士都是一样的，换言之，在某一个稳定匹配中有婚恋对象的男士或女士，那么在其他的所有稳定匹配中也都有婚恋对象；在某一个稳定匹配中没有婚恋对象的男士或女士，那么在其他所有稳定匹配中也都没有婚恋对象。Knuth（1976）[74，394]对所有稳定匹配的结构进行了研究，发现了另外一个重要现象：婚恋匹配中所有稳定匹配形成一个重要的结构——格。具体研究结论为：当双边主体的偏好是严格偏好，稳定匹配的集合形成一个格结构，并且格结构中的最大元素是男士发出申请的延迟接受算法产生的稳定匹配，格结构中的最小元素是女士发出申请的延迟接受算法产生的稳定匹配。Roth（1982）[39]进一步研究了婚恋匹配市场，研究发现Gale和Shapley在1962年提出的延迟接受算法获得的男士和女士最优稳定匹配都是弱帕累托最优匹配；并且不存在一个稳定匹配机制使得所有男士和女士表达真实偏好是一个占优策略，简而言之不存在一个同时获得稳定匹配和对所有男士和女士而言是防操纵的匹配机制。Roth和Sotomayor（1992）[75]针对具有严格偏好信息的婚姻匹配问题，证明了若稳定匹配数量不止一个，那么无论采用哪种稳定匹配机制，在其他男士和女士都表达真实偏好的情况下，都至少存在一个男士或女士可以通过提供虚假偏好来获得更好的利益。王烨和李雨生（2013）[92]从纳什均衡角度出发，考虑图论中的稳定匹配问题，将婚姻匹配问题转化为图论中的二部图，研究发现稳定匹配可以用纳什均衡理论进行直观解释，并证明了稳定匹配是纳什均衡。Domaniç（2017）[91]等研究了稳定婚姻问题的一个变种问题，即具有无差异偏好信息的稳定婚姻匹配问题，提出了一种能够产生帕累托稳定匹配的机制，并且该机制对一方匹配主体而言是群体防操纵的，该机制的关键技术是将稳定婚姻市场视为一个一般化的分配博弈，研究结果表明了机制的有效性。

②稳定匹配精确算法研究(www.xing528.com)

Matsui（2011）[87]采用博弈论方法研究了具有完全偏好列表的婚姻匹配问题，依据男女双方给出的对方偏好列表，引入女士之间的博弈，每个女士选择的一个策略对应着对男士的一个完全偏好列表，产生的女士支付是男士发出邀约Gale-Shapley算法结果中女士对应的匹配对象，并提出了一个多项式时间算法来检验给定的婚姻是否为一个均衡结果。为帮助用户有效地搜索婚恋对象，缩小期望匹配的婚恋对象范围，从而最大化在线门户网站的匹配机会，Joshi和Kumar（2012）[88]针对印度电子婚恋环境下的在线婚恋匹配问题，采用模糊层次分析法计算男女双方在多指标下的总分，提出一个计算男女双方匹配度的相容性指标，采用Gale-Shapley稳定匹配算法向用户推荐合适的婚恋交友对象。Shrivastava和Rangan（2016）[90]研究了具有无差异且偏好列表具有不完全有限长度的社会稳定性问题，研究表明找到一个具有最大规模的弱社会稳定匹配是一个NP-hard问题，并给出了一种获得最大规模弱社会稳定匹配的算法。段歆玮和詹文杰（2015）[93]通过分析在线相亲网站上的会员数据，给出了男女满意度评价指标体系的结构和权重以及各指标的满意度和整体满意度的计算方法，提出了基于满意度基数新的线性规划模型及其相应算法，这一新方法的整体满意度明显优于基于序数信息的Gale-Shapley算法。吴威让等（2016）[94]研究了不完全偏好下的稳定婚配的匹配率、满意度问题，利用构造满意度函数的方法，获得了在不完全偏好下的婚配市场的人均满意度不低于完全偏好下的人均满意度的结果，更好地阐释了当今社会的剩女（男）现象。

③稳定匹配近似算法研究

Manlove和Irving（2002）[76]研究了具有部分偏好列表和无差异偏好的婚姻匹配问题，分析了此类问题可能存在不同规模的稳定匹配，指出即便无差异偏好只存在于男女一方，位于偏好列表的尾部，并且无差异长度是2，找到一个具有最大或最小规模的稳定匹配以及确定一个给定的男女对是否是稳定的也是困难的；找到或近似地找到一个平等稳定匹配和最小后悔稳定匹配都是困难的，并给出一个找到最大或最小规模稳定匹配的近似比为2的算法。Halldórsson等（2003）[77]针对双边主体给出的偏好中具有不完全偏好列表和无差异偏好的最大基数稳定匹配问题，给出了第一个近似比小于2的随机近似算法，证明了只有男士偏好列表存在无差异偏好，最多只有一个无差异偏好并且长度为2时，随机近似算法的近似比为10/7。Halldórsson等（2004）[78]研究了具有不完全偏好列表和无差异偏好的最大基数稳定匹配问题，给出了一个随机近似算法RANDBRK，证明了期望的近似比最大为10/7（＜1.4286），针对无差异偏好只存在男士偏好列表中，每个男士最多只有一个无差异偏好并且长度为2的最大基数稳定匹配问题，证明了给出的随机近似算法可以提供一个比较低的下界32/23（＞1.3913）。Halldórsson等（2007）[79]针对具有无差异偏好和不完全偏好列表的双边匹配问题，当只有男士一方存在无差异偏好时，提出的获得最大规模稳定匹配的近似算法的近似比为2/（HL-2），其中L为无差异偏好的最大长度；当男女双方都允许存在无差异偏好且偏好长度最长为2时，近似算法的近似比为13/7（＜1.858），并且将近似比下界提高到21/19（＞1.1052）。Irving和Manlove（2008）[80]针对具有不完全偏好列表和无差异偏好的稳定婚姻匹配问题，研究了只有一方具有无差异偏好信息并且无差异偏好位于偏好列表末尾的最大基数稳定匹配问题，给出了一个近似比为5/3的近似算法。Király（2008，2011）[81，82]针对稳定婚姻中具有不完全偏好列表和一方具有无差异偏好信息的最大基数稳定匹配问题，给出了一个简单的多项式时间近似算法，研究表明该算法的近似比为3/2，优于Irving和Manlove给出的近似比为5/3的近似算法，并且该算法具有更简单以及运行速度更快的优点。Mcdermid（2009）[83]针对具有不完全偏好列表和无差异偏好的稳定婚姻匹配问题，给出了一个获得最大基数稳定匹配的多项式时间近似算法，证明了该算法的近似比为3/2，优于Király给出的近似算法的近似比5/3。Paluch（2014）[84]研究了具有无差异偏好列表的婚姻匹配问题，指出以获得最大匹配对数量的稳定匹配为目标的当前最好近似算法近似比为3/2，提出了一个获得近似比为3/2以及时间复杂度为O（m）的近似算法，并证明了算法的时间复杂度优于McDermid给出的时间复杂度。Irving等（2009）[85]研究了经典稳定婚姻问题中偏好列表具有无差异偏好并且具有有限长度的最大基数弱稳定匹配，证明了若每个男士偏好列表的长度最大为2，则最大基数弱稳定匹配是多项式可解的；然而每个男士偏好列表的长度最大为3时，这个问题称为NPhard问题，并且近似比不可能达到δ＞1。Iwama等（2014）[86]研究了具有无差异偏好和不可接受匹配主体的最大稳定匹配问题，指出多项式时间算法给出的近似比不超过33/29（＞1.1379），除非P=NP，并且当前最好的近似算法的近似比为1.5；即使只有一方存在无差异偏好，近似比也不超过21/19（＞1.1052），除非P=NP，而当前已知的最好的近似比为1.5。提出了一个多项式时间近似算法，将近似比提高到了25/17（＜1.4706）。在偏好列表具有截断和无差异偏好的婚姻匹配问题中，找到匹配规模最大的稳定匹配具有很强的计算复杂性，Munera（2015）[89]等采用自适应搜索的局部搜索技术来解决这一问题，计算实验表明该方法比当前最先进的精确算法和近似算法更有效。

（3）评述与展望

男女婚恋匹配问题作为双边匹配最早研究的领域之一，历经几十年的发展，取得了大量研究成果。许多学者对具有严格偏好信息、具有无差异偏好信息、具有完全偏好列表、具有部分偏好列表等双边匹配问题进行了研究，研究了不同类型偏好信息下稳定匹配的存在性，稳定匹配求解的复杂性，获得稳定匹配的精确算法、近似算法、搜索算法、智能优化算法等。以往研究大多从理论研究的视角，关注男女婚恋市场稳定匹配问题，关于电子中介婚恋网站中男女婚恋匹配研究不多，只发现Joshi、Kumar、段歆玮、詹文杰研究了婚恋网站中男女最优匹配的方法。婚恋网站中男女双方的数量规模往往都比较大，如何利用大数据技术结合双边匹配理论为男女双方推荐合适的婚恋对象，提高婚恋成功率，降低婚恋成本是未来需要研究的一个重要内容。