基于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