基于Gale-Shapley算法的创业团队组建系统的研究

杨志和，胡建松，覃海焕

(上海电机学院 电子信息学院，上海 201306)



基于Gale-Shapley算法的创业团队组建系统的研究

杨志和，胡建松，覃海焕

(上海电机学院 电子信息学院，上海 201306)

创业团队的组建是一个双向选择、延迟认可的过程，找创业合伙人如同找对象一般，越来越成为人们关注的社会问题。Gale-Shapley算法是解决最佳稳定配对问题的经典算法。对创汇堂项目进行了问题分析和模型设计，介绍了系统实施与应用，最后对创汇堂项目中Gale-Shapley算法的应用进行了总结。

稳定匹配问题； 延迟认可； Gale-Shapley算法； 创业团队组建

大学校园是创新的源泉，也是创业的乐土。大学生拥有创业的激情和能力，但是大学校园还不是创新创业的实践场，这里缺乏资源整合的平台；大学生们面临着想创业找不到好的创业项目和团队、初创团队找不到稳定的合适的“人才”的困境。

创业团队的组建，就是人找项目和项目找人。当然这里的人也许带着资金、也许带着技术、也许带着客户市场，总之，他们需要结对和匹配。项目的这种结对和匹配比喻成恋爱与结婚，再适合不过了。因此，可以基于成熟的婚恋模型来映射和解决这个全新的问题，用博弈论来解决创业项目团队的最稳定匹配问题。

Gale-Shapley算法是由美国数学家Gale和Shapley发明的一种寻找稳定匹配的算法，称为延迟认可算法(Deferred-acceptance Agorithm)，简称“GS算法”；他们基于Gale-Shapley算法研究了市场设计与社会资源稳定匹配问题，并取得了巨大的社会价值。在数学和计算机科学里，稳定匹配问题(Stable Marriage Problem， SMP)是在给定每个元素偏好的条件下，在两个集合间寻找最稳定匹配的问题。“匹配”就是指从一个集合的元素到另一个集合元素的映射。本文分析了创业团队资源整合服务的需求，利用Gale-Shapley算法建立了一款面向创新创业服务的应用系统——创汇堂创业团队组建系统，使之成为面向当前高校创新创业服务的O2O(Online to Offline)平台，通过线上“创汇堂”软件来整合线下创业指导工作室、创客空间等实体的项目、人才、资金等创业资源，基于抱团思维和共赢思维，为创业者提供一站式创业服务。

1　问题分析与模型建立

1.1问题分析

在创汇堂创业团队组建系统的业务逻辑中，创业项目与人才的配对问题来自于日常的各种宣讲、招募、路演等活动。平台集中了N个创业项目和a·N(a为常数)个人才。在实际应用中，N是一个正整数。每个项目都有1个项目负责人，要求每个项目负责人都要与每个候选人才进行短暂的单独交流，并对他们做出评判和打分，然后按照喜欢程度，对他们进行排序；同样的，每个候选人才也要对所有候选项目进行了解、打分和排序。因此，作为活动的组织者，确定最佳配对关系才是关键。

在创汇堂创业团队组建系统的目标中，所谓稳定的配对，就是指人才加入心仪的项目后，双方都认为对方是最好的，不会发生解雇和被解雇或抛弃和被抛弃的想法和行为。若双方都是对方最满意的对象，自然不会解雇或抛弃对方；若有一方或双方都不是对方的最满意对象，则必须保证该项目负责人已找不到比其欲解雇的人更好的人才了，也即找不到比当前配对更好的搭配对象了。如项目(负责人)I认为其现在的首席技术官(Chief Technology Officer， CTO)W有诸多不足，不是自己最满意的CTO，他更满意的人是技术官R；但是技术官R认为自己更喜欢现在的项目X，则不会选择加入项目I；另外，财务官K很喜欢项目I，当然很想加入项目I，但是，项目(负责人)I觉得财务官K不如当前团队中的财务官M，故I也不会选择财务官K。因此，项目I没有理由也没有动力吸纳财务官K的加入，当然不会解雇现有的财务官M而选择财务官K；同理，若项目I的财务官M也找不到更适合的项目，则他们的选择和配对就是稳定的。简言之，只要满足“对项目(负责人)而言，除现任创业团队成员外，我们满意的人才都不愿意加入，而想加入的人才我们不满意；对人才而言，自己更满意的项目拒绝了自己的申请，当前的项目是能加入的项目中最满意的项目”的条件，两个集合中的所有对象都不会对另一集合中除了已经与自己配对的对象以外的对象感兴趣的状态，就形成了稳定的选择和配对。

1.2模型假设

(1)参与配对的双方始终都保持着自己的理性的、明确的喜好(偏好)；

(2)参与配对的人才都有自己喜欢的项目、业务领域或方向，且不会随时间而变化；

(3)参与配对的双方对于特定的匹配目标集合能够给出明确的喜好列表；

(4)参与配对的双方都选择的是利益最大化战略(贪婪算法)。

对于项目而言，向最满意的人才抛出Offer是顺理成章的事，招聘不到最喜欢的，则退而求其次，联系第二满意的，依次类推；对于人才而言，不断地从向自己抛出Offer的项目中选择自己最喜欢的项目也正符合其利益。这样，所有参与配对的双方都在可供选择的范围内选择了自己相对最喜欢、最满意的配对对象，这也是市场博弈的必然结果。

1.3模型建立

基于Gale-Shapley算法的最佳选择与配对主要包括如下步骤：

(1)将所有待配对对象分为2组，每组待配对对象分别为另一组待配对对象打分，依据打分结果形成各自的意愿配对列表。

(2)第1组中的各待配对对象依据自己的意愿配对列表，逐一向第2组待配对对象中未拒绝其配对请求的待配对对象提出配对请求，直到配对成功为止；第2组中的各待配对对象根据自己的意愿配对列表，对收到的配对请求进行拒绝或接受[10]。

A.以第2组中某一待配对对象为例，若该对象未收到配对请求，则继续等待匹配请求；若该对象只收到1个配对请求，则接受该配对请求，故提出该配对请求的对象配对成功；若该对象收到多个配对请求，则根据自己的意愿配对列表选择自己打分最高、最满意的那一个，配对成功，同时拒绝其他的配对请求。

B.若该对象已有匹配成功的对象且收到新的配对请求，则根据自己的意愿列表重新选择自己最满意的配对对象，重新配对成功，同时拒绝其他的配对请求。

(3)若曾经配对成功的对象在新一轮的“双选会”中被“老东家”解雇，则根据自己的意愿列表重新逐一向另一组中未拒绝其配对请求的对象提出配对请求[11]。

假设第1组待配对对象为项目，第2组待配对对象为人才，若两组待配对对象的数量相等，则可以实现完全配对，不会出现有项目而职位空缺或项目、职位全满而人才闲置的情况。

为更具体地说明算法的执行过程，本文以4个项目、4个人才的一个较小集合来表述该算法。4个项目分别是项目A、B、C、D，4个人才分别是人才1、2、3、4。图1给出了配对前待配对对象的喜好状态。图2为3轮配对过程示意图。人才选择项目时呈现出一定的偏好，如对学科领域、团队文化、收益分配制度、风险等方面的偏好；项目选择人才时也呈现出一定的偏好，如对性别、性格、社会经历、学历、特长等方面的偏好。在第1轮配对时，项目A与项目B的首选对象都是人才3，都向人才3发出配对请求，即抛出Offer，而人才3根据自己的意愿列表选择项目A，项目A与人才3配对成功；项目C、D分别向人才1、2发出配对请求，人才1、2都只收到这一个配对请求，即接受该配对请求，项目C、D分别与人才1、2配对成功。在第2轮配对时，项目B依据自己的意愿列表向未拒绝过他的人才2发出配对请求，抛出Offer，此时人才2已有配对对象(项目D)，但人才2根据自己的意愿列表重新选择了项目B，则项目B与人才2配对成功，相应地，项目D的职位重新变为空缺。第3轮配对时，项目D参照自己的意愿列表向未拒绝过他的人才4发出配对请求，人才4只收到这一个配对请求，即接受该配对请求，项目D与人才4配对成功，最终形成稳定的选择和搭配[12]。

图1　配对前的喜好状态Fig.1　State of preference before matching

图2　配对过程Fig.2　Matching process

2　创汇堂创业团队组建系统的构建

基于Gale-Shapley算法的创汇堂创业团队组建系统主要采用3层B/S架构：

(1)浏览器层，用于接收待配对对象的资料信息及展示相关信息给用户浏览。

(2)应用服务器层，包括数据挖掘模块及关联控制器。数据挖掘模块从Web服务器日志文档中挖掘用户资料浏览记录和标签，结合用户填报的原始资料，形成偏好列表，并保存到数据库服务器的兴趣偏好模型中。关联控制器读取用户的兴趣偏好模型数据，构建与之相应的信息推荐与交流，并根据该信息更新匹配关系，实现最优匹配。

(3)数据服务器层，包括会员信息总库、配对信息库以及兴趣偏好模型。会员信息总库用于存储各待配对对象的资料信息；配对信息库用于存储该关联控制器的调整配对结果；兴趣偏好模型则用于存储兴趣偏好列表[13]。

创汇堂创业团队组建系统架构如图3所示。

图3　系统架构图Fig.3　System architecture diagram

由图可见，关联控制器包括关联结构调整和活动推荐两个模块。关联结构调整模块用于根据用户的兴趣偏好模型数据，形成各待配对对象之间的配对关系，并保存在该数据服务器的配对信息库中；活动推荐模块则根据配对信息库的配对结果，结合数据服务器的会员信息总库的数据，向待配对对象进行人才或项目推荐[14]。

创汇堂创业团队组建系统主要模块如图4所示。

图4　创汇堂系统主要模块Fig.4　Main module of Chuanghuitang System

3　问题求解过程说明

3.1总体设计说明

(1)程序采用两个二维数组Project[max][max]、 Partner[max][max]来记录max个人才、项目对人才的喜欢程度顺序；

(2)数组acProject记录人才下一个追求的项目顺序(从0位开始，即最喜欢的一个开始)；

(3)数组acPartner记录每一个项目的当前人才配置(开始时设置一个虚拟人才，其喜欢程度最小)；

(4)采用4个for循环，分别对4个数组初始化；

(5)采用一个for循环遍历Project数组(为每一个人才寻觅其最喜欢的项目)；

(6)采用一个for循环输出结果。

3.2求解过程的应用

假设市场上有6个人才(PT={e1，e2，e3，e4，e5，e6})，它们寻求加入4个创业项目(PJ={v1，v2，v3，v4})，创业项目的人才需求容量分别为2、2、1、1。人才对创业项目匹配的偏好评分如表1所示。

表1　人才对创业项目的偏好评分表

其匹配过程如下：

(1)根据匹配偏好值的大小，创业人才e1、e2和e3向他们认为的最优选择创业项目v1递交求职意向书，e4、e5和e6向他们认为的最优选择项目v3递交求职意向书，而v2和v4没有收到任何创业人才的求职意向。创业项目v1和v3在收到求职意向后，根据匹配价值选择性地接受创业人才。结果是e1和e2的求职申请被v1接受，e4的求职申请被v3接受，而e3、e5和e6的求职申请被拒绝。同时，v2有2个职位空缺，v4有1个职位空缺。

(2)e3、e5和e6分别向次优选择的创业项目递交求职申请。由于v1的职位需求已满，故拒绝了e5、e6的求职申请，而v2选择接受了e3的求职申请。结果是e5、e6的求职申请再次被拒绝，同时，v2、v4各有1个职位空缺。

(3)e5、e6分别向偏好列表排位第3的的创业项目v2递交商业计划书。由于v2只有1个职位空缺，根据匹配价值，选择接受了e5，而拒绝e6。结果是e6的求职申请仍未被接受，而v4仍有1个职位空缺。

(4)e6向偏好排位最末的创业项目v4提交求职申请，并被v4所接受，一个稳定的匹配最终形成，其结果是

4　结　语

本文介绍并实践了Gale-Shapley稳定匹配理论及其实践方法，应用于创汇堂创业团队组建系统中，以4个项目和4名人才双选和配对为范例，设想由每一个项目先选择并向最满意的人才抛出Offer，然后由每个人才审视当前所获得的所有配对机会，并“暂时接受”其中最满意项目的Offer，回绝其他项目的Offer，所有未获得人才的项目将进入下一轮对“次满意”人才的“求贤”招募中，经过多轮反复实现了稳定的组团配对。该系统及其算法的核心，是人才保留并延迟接受最满意的项目的“求贤”。这一方法就是延迟接受运算法则[15]，它实现了一种更快速、更实用、更稳定的配对方法，从而提高了资源优化配置的效率和质量。

[1]哈福德.线上约会有真爱?.刘晓帆，译.二十一世纪商业评论，2015(5)：22.

[2]宋旭东，纪秀花.稳定婚姻匹配问题的一个快速枚举算法.工程图学学报，2010(3)：187-192.

[3]孔英，朱东山.企业间碳配额分配机制研究.开放导报，2013(3)：36-41.

[4]何伟军，袁亮，吴霞.稳定匹配和市场设计——2012年诺贝尔经济学奖得主的学术贡献.商业时代，2013(18)：7-8.

[5]李凤.高考志愿填报与录取机制研究.成都：西南财经大学，2010：10.

[6]连广昌，朱顺荣.Gale-Shapley匹配的推广.南京理工大学学报，1997，21(6)：569-573.

[7]段歆玮，詹文杰.基数满意值下的双边匹配模型在婚配问题中的应用∥第十五届全国计算机模拟与信息技术学术会议论文集.武汉：管理学报编辑部，2015：1-11.

[8]宋旭东，纪秀花.稳定婚姻问题的研究∥计算机技术与应用进展：2008.合肥：中国科学技术大学出版社，2008：968-972.

[9]朱琳.双边匹配理论在高考录取制度中的实验研究.广州：华南理工大学，2010：23-24.

[10]李玉花.基于多指标评价信息的双边匹配模型研究.沈阳：东北大学，2009：21-22.

[11]贺尊，汪红梅.稳定匹配理论与市场设计实践——2012年诺贝尔经济学奖得主的学术贡献及其启示.江汉论坛，2012(12)：78-83.

[12]柏汇崧，张峥.非完全信息偏好下一对一匹配问题的Gale-Shapley分配机制.企业技术开发，2014(3)：15-16，30.

[13]邓蔚之，刘强，任志虎，等.优化的Gale-Shapley算法在学生选课问题中的应用，湖南工业大学学报，2013，27(1)：67-70.

[14]侯华，王江东.基于延迟认可算法的认知无线电频谱分配.计算机应用与软件，2013，30(1)：256-259.

[15]孙昱，付少波，张天培，等.应用于测试资源匹配的婚姻稳定算法改进.河北工业大学学报，2009，38(3)：72-76.

Entrepreneurial Team Establishment System Based on Gale-Shapley Algorithm

YANG Zhihe，HU Jiansong，QIN Haihuan

(School of Electronic Information Engineering， Shanghai Dianji University， Shanghai 201306)

Entrepreneurial team formation is a process of two-way choice and delayed approval.To find a business partner is like to find a lover in general.This has become a social problem increasingly attracting interests from people.The Gale-Shapley algorithm is a classical algorithm for solving optimal stable matching problems.This paper analyzes the Chuanghuitang Project, establish a model for it, and discusses system implementation and applications.Application of the Gale-Shapley algorithm to the project is summarized.

stable marriage problem; delayed recognition; Gale-Shapley algorithm; entrepreneurial team building

2016-07-06

上海大学生创新活动计划项目资助(201611458060)

杨志和(1979-)，男，讲师，博士，主要研究方向为计算机应用技术、软件工程等，E-mail：yangzh@sdju.edu.cn

2095-0020(2016)04-0216-05

TP 301.6；TP 316.8

A