王彥博，于瀚辰，沈體雁

WANG Yanbo,YU Hanchen,SHEN Tiyan

北京大學 政府管理學院，北京 100871

School of Government，Peking University，Beijing 100871，China

1 相關文獻綜述

大多數(shù)情況下經(jīng)濟學家都簡單假定“市場”能夠直接產(chǎn)生競爭均衡的價格，但在器官匹配、學生擇校等領域，基于道德、社會習慣、公平性等方面的考慮，無法將資源完全商品化，從而無法完全由價格決定最后的分配結果，因此需要對交易規(guī)則進行充分設計以達到某種最優(yōu)目標[1-2]。“市場設計學”在20世紀90年代之后逐漸成為一個嚴謹?shù)目茖W分支，從這一時期開始經(jīng)濟學家獲得了對復雜市場（尤其是公共資源分配市場）進行設計的機會，并在實踐上獲得巨大成功，最知名的案例是1996年由Roth主導重新設計的美國住院醫(yī)生實習系統(tǒng)以及1994年由McAfee等人設計的美國收音頻譜拍賣系統(tǒng)，他們對現(xiàn)存市場各方面的細節(jié)問題做深入考察，抽象出基本的模型假設，并提供一組可行的制度安排，提高了市場效率[3-5]。

市場設計最成功的實踐案例都發(fā)生在拍賣市場和匹配市場。其中匹配市場設計的理論基礎為匹配理論（Matching Theory），主要研究離散不可分資源的匹配、分配、交換問題，核心工作是匹配算法的設計以及算法穩(wěn)定性、帕累托有效、策略行為免疫等相關性質(zhì)的證明，其中又以穩(wěn)定性最為重要[6-7]。匹配理論的創(chuàng)始人是Gale和Shapley，他們在1962年探討了一對一的婚姻匹配問題和一對多的大學招生問題，建立了基本的雙邊匹配模型，提出延遲-接受算法（亦常被稱為G-S算法），并證明該算法總存在穩(wěn)定結果，此后國內(nèi)外學者圍繞匹配模型展開大量研究[8-9]。近年來對雙邊匹配算法的理論探討主要集中于個體行為假設的變形以及匹配模型的擴展，如Klumpp將線性空間模型引入了雙邊匹配問題[10]，Erdil討論了個體偏好序非嚴格情況下的穩(wěn)定匹配[11]，Castillo討論了參與主體采取截短策略時的風險和收益[12]。匹配理論的繁榮發(fā)展促進了市場設計學在勞動力就業(yè)、高校錄取、定向廣告、電子商務、人力資源、金融等多個領域的應用[13-17]。

機制設計、拍賣理論、匹配理論等工具常被用于分析既定規(guī)則下市場參與者的均衡行為，但因現(xiàn)實市場環(huán)境過于復雜，常常無法獲得理論上的解析解，因此還需要計算模擬、心理實驗等方法作為補充，Roth將這一綜合方法稱之為“經(jīng)濟工程學”[3]。Roth于1996年受邀重新設計NRMP匹配算法以解決由于學生情侶增多而導致的NRMP參與率逐年下滑問題，在算法設計和評價過程中，他使用1993—1995年間NRMP參與者的真實偏好數(shù)據(jù)以及隨機生成的偏好數(shù)據(jù)進行大量仿真模擬，新的Roth-Peranson算法于1998年正式在NRMP投入使用，重新提升了NRMP的參與率，成為模擬實驗與理論分析互補達成市場設計的成功范例[18]。Shapley和Roth也由于“穩(wěn)定匹配理論和市場設計實踐”而獲得了2012年諾貝爾經(jīng)濟學獎。

2 傳統(tǒng)雙邊匹配算法存在的問題

無論是G-S算法，還是NRMP采用的Roth-Peranson算法，都存在以下問題[4，18-20]：（1）單邊占優(yōu)問題，率先發(fā)出申請的一方總體效用優(yōu)于被動接受申請的一方。（2）缺乏最低保障，部分參與者效用可能會極差。（3）缺乏靈活調(diào)控空間，算法最多只能產(chǎn)生兩個穩(wěn)定匹配結果，即參與雙方某一方占優(yōu)的結果，而無法細致調(diào)節(jié)每一個參與主體的優(yōu)先順序。

以學生和醫(yī)院匹配為例，G-S算法必須首先選擇學生或醫(yī)院中的某一方作為申請方，申請方按照自己的偏好順序從優(yōu)到次向心儀的對象發(fā)出申請，收到申請的一方選擇接受或者拒絕。這種設計能夠保證得到穩(wěn)定匹配結果，但匹配流程優(yōu)先照顧申請方的偏好，因此導致申請方整體效用比被申請方高[8]。模擬100個學生和100個醫(yī)院的一對一匹配，為每個學生和醫(yī)院隨機生成長度為100的偏好序，圖1展示了G-S算法匹配結果的偏好位序累積情況，圖中橫坐標表示最終被匹配到了偏好序中第幾位的對象，縱坐標表示累計的匹配數(shù)量，例如學生匹配結果曲線中的一個點（X=3,Y=12）表示有12個學生最終被匹配到了其偏好序中前3位的醫(yī)院，曲線越凸意味著效用越高。當設定學生為申請方時（圖1（a））大多數(shù)學生都匹配到了其偏好序中前15位的醫(yī)院，全部學生都匹配到了其偏好序中前40位的醫(yī)院，該算法對于學生是最優(yōu)的穩(wěn)定匹配；但有相當一部分醫(yī)院匹配到了其偏好序中40位之后的學生，甚至部分醫(yī)院匹配到其偏好序中70位之后的學生，該算法對于醫(yī)院來說是最差的穩(wěn)定匹配。反之當設定醫(yī)院為申請方時（圖1（b）），結果對醫(yī)院最優(yōu)，對學生最差?？梢奊-S算法會使得整體上某一邊比另一邊更占優(yōu)，且部分參與主體的效用極差。

圖1 G-S算法的偏好位序滿足累積曲線

Roth發(fā)現(xiàn)住院醫(yī)生實習市場中穩(wěn)定匹配集合的基數(shù)很小，即無論哪方率先發(fā)出申請，得到的匹配結果相差不大，這主要是因為該場景中參與主體對于各自的優(yōu)劣排名認知較為一致，即每個醫(yī)院對畢業(yè)生的偏好相似度很高，同時每個畢業(yè)生對于醫(yī)院的偏好相似度也很高[4，21]。但是婚姻匹配等眾多雙邊匹配問題中，參與主體的偏好差異性很大，穩(wěn)定匹配集合的基數(shù)也會隨之增大，G-S算法的單邊占優(yōu)以及缺乏最低保障等問題就會凸顯，使得匹配結果較差的參與者積極性下降，降低市場厚度，進而導致市場設計失敗[21]。實際上即使在單邊占優(yōu)問題并不嚴重的住院醫(yī)生實習市場，NRMP采用醫(yī)院優(yōu)先的匹配算法也曾招致大量學生表達不滿甚至退出NRMP匹配系統(tǒng)，因此如何提高效用較差者的滿意度成為決定市場設計成敗的關鍵問題[3]。李銘洋、樊治平等關注到這一問題并提出了解決方案，將雙方主體匹配序值之和最小作為目標構建了多目標優(yōu)化模型，使得結果不再偏向于某一方，解決了單邊占優(yōu)問題[22]。但該方法并不能給予效用最差者以最低保障，仍然可能有個別參與主體效用過差，因此在維護市場厚度方面尚存在改進空間，另外其方案也只能調(diào)整參與匹配某一方整體的優(yōu)先級，而無法針對某個參與個體做出調(diào)整。

為了更好地解決單邊占優(yōu)問題、最低保障問題以及提供靈活調(diào)控個體優(yōu)先級的機制，本文提出了WYS算法。

3 WYS算法

一個典型的雙邊匹配問題中包含兩類主體集合，以醫(yī)學畢業(yè)生就業(yè)市場上醫(yī)院與學生的匹配為例，有學生集合S={S1,S2,…,Sn}和醫(yī)院集合H={H1,H2,…,Hm}，每個學生Si試圖尋找一個醫(yī)院簽約工作，每個醫(yī)院Hj試圖招聘qj個學生。每個學生Si對其可接受的醫(yī)院，以及每個醫(yī)院對其可接受的學生，都有一個完備的、可傳遞的、嚴格的偏好序。匹配結果為S×H的一個子集M，M中的每個元素是一個學生和一個醫(yī)院的匹配對，在M中每個學生只出現(xiàn)不超過1次，每個醫(yī)院出現(xiàn)不超過qj次。匹配結果穩(wěn)定意味著M中不存在阻礙對（blocking pairs），一個好的雙邊匹配算法總能找出穩(wěn)定的匹配結果。

WYS算法將學生和醫(yī)院都視為實體（Entity），全體學生和醫(yī)院構成的集合稱為實體全集ES。對于任一實體E來說，與E不同類型的實體稱之為對手實體。例如對一個醫(yī)院實體來說，所有的學生實體是對手實體。每個實體E擁有以下屬性（實體的屬性可以使用“E.屬性名”的方式來表示）：

（1）優(yōu)先級R：外生給定ES一個全序，用正整數(shù)表示，E.R為實體E對應的正整數(shù)，E.R越大意味著E的優(yōu)先級越高。

（2）偏好序P：每個實體E都有一個描述自己對于對手實體偏好程度的嚴格序列，在偏好序中越靠前則意味著越希望與對方匹配。例如某學生S1最心儀的醫(yī)院是H3，其次是H5，再次是H1，該學生只考慮與該偏好序中的醫(yī)院簽約，不考慮其余醫(yī)院，則S1.P={H3,H5,H1}。用E1.P(E2)＞E1.P(E3)表示在E1的偏好序中E2排在E3之前。

（3）匹配容量C：E能夠匹配的對手實體數(shù)量。例如某醫(yī)院E1欲招聘4個學生，則E1.C=4。在就業(yè)市場中，學生類型實體的容量恒為1，醫(yī)院類型實體的容量由每個醫(yī)院根據(jù)招聘計劃自定。

（4）已匹配列表M ：目前暫時與E匹配的對手實體列表。在算法運行過程中每個實體E的E.M都會不斷迭代更新，算法停止時E.M中的實體即為E的最終匹配對象。當E.M中的實體數(shù)量等于E.C時，稱“E已匹配滿”。

（5）最差實體WME（Worst Matched Entities）：E.M中最不被E偏好的實體。算法運行過程中E.WME會隨著E.M的變化而不斷更新。

WYS算法維護一個無序集合L和一個有序隊列T。初始時將ES中所有實體都加入L，將T置空，然后啟動第一輪外層循環(huán)，循環(huán)過程中會不斷調(diào)用Apply函數(shù)，每次調(diào)用Apply函數(shù)都意味著某個實體向另一個實體發(fā)出了匹配申請，在Apply執(zhí)行過程中有可能解除某些暫時的匹配，被解除匹配的實體會被放入T中，下一輪循環(huán)優(yōu)先讓T中的實體發(fā)出申請。算法框架參考圖2，算法具體細節(jié)參考偽代碼及注釋。

圖2 WYS算法框架

WYS算法偽代碼

WYS算法注釋

2：只要L和T任何一個非空，就不斷進行外層循環(huán)。

3：只要T非空，就不斷進行內(nèi)層循環(huán)，每次循環(huán)都從T中取出一個實體處理。

4：將T中排第一位的實體移出T，并將該實體作為變量E1。

5～7：E1按照偏好程度從大到小的順序依次向其偏好序中的實體發(fā)出申請，即調(diào)用Apply函數(shù)，Apply函數(shù)的具體定義見下文偽代碼。

9：判斷L是否為空，若不為空就從L中取出一個實體處理。

10：將L中R值最大的實體移出L，并將該實體作為變量E2。

11～13：E2按照偏好程度從大到小的順序依次向其偏好序中的實體發(fā)出申請。

15：算法結束，此時每個實體E的匹配列表E.M中的結果即為最終匹配結果。

Apply(E1,E2)函數(shù)定義偽代碼

Apply函數(shù)注釋

1～3：若E1不在 E2.P中，或 E2不在E1.P中，則E1和E2不可能匹配，直接結束函數(shù)。

4～6：若E1對于E2來說還不如E2已匹配的最差者，或E2對于E1來說還不如E1已匹配的最差者，則E1和E2不可能匹配，函數(shù)直接結束。

7：創(chuàng)建一個空的、有序的臨時隊列變量，命名為tmp_list。

8：若E1已匹配滿，則解除E1和E1.WME的暫時匹配狀態(tài)，并進行其他相關處理。

10～11：解除E1和E1.WME的暫時匹配狀態(tài)。

12～14：若實體w1曾發(fā)出過至少一次申請且w1目前不在T中，則將w1放入臨時隊列tmp_list中。

16：若E2已匹配滿，則解除E2和E2.WME的暫時匹配狀態(tài)，并進行其他相關處理。

17～19：解除E2和E2.WME的暫時匹配狀態(tài)。

20～22：若實體w2曾發(fā)出過至少一次申請且w2目前不在T中，則將w2放入臨時隊列tmp_list中。

24：按照R值從大到小的順序對tmp_list中的實體進行排序。

25～27：將tmp_list中的實體依序插入T中，插入每一個實體時若T非空，就將該實體插到T中現(xiàn)存的最后一個實體之前（這是為了保證最新被踢掉的實體在T中排在最前列，從而下一輪循環(huán)中可以率先嘗試發(fā)出申請）。

28～29：將E1和E2互相加入對方的暫時匹配列表中，E1和E2暫時成為互相匹配的實體。

4 實驗結果及討論

圖3 10次隨機實驗平均的醫(yī)院與學生偏好位序滿足累積曲線

進行與第2章中相同的隨機實驗10次，分別用醫(yī)院優(yōu)先的G-S算法、學生優(yōu)先的G-S算法和WYS算法對100個學生和100個醫(yī)院在隨機偏好序下進行匹配。其中WYS算法需要先設定優(yōu)先級R，優(yōu)先級高的實體會優(yōu)先發(fā)出申請并在最終匹配結果中相對占優(yōu)。實驗中參考對手實體的偏好序來確定優(yōu)先級R，將學生和醫(yī)院按照被偏好程度從大到小排序，占據(jù)醫(yī)院偏好序中第一名最多的學生為學生隊列的第一位，若兩學生占據(jù)醫(yī)院偏好序中第一名數(shù)量相同則根據(jù)占據(jù)醫(yī)院偏好序中第二名的數(shù)量排位，以此類推，對全體學生進行優(yōu)先級排序，醫(yī)院排序采用同樣方法操作。學生隊列排序結果為{SR1,SR2,…,SR100}，醫(yī)院隊列排序結果為{HR1,HR2,…,HR100}，設定優(yōu)先級結果為 SR1.R＞HR1.R＞SR2.R＞HR2.R＞…＞HR100.R。理論上優(yōu)先級可以隨意設置，優(yōu)先級越高的實體最終越占優(yōu)，不同的優(yōu)先級設定可能會產(chǎn)生不同的匹配結果，上述設定方式符合“最受歡迎者優(yōu)先”的一般常理。通過實驗可知WYS算法解決了第2章提出的傳統(tǒng)算法存在的問題。

（1）WYS算法非單邊占優(yōu)。圖3（a）展示了10次隨機實驗醫(yī)院的平均匹配結果：G-S算法中優(yōu)先發(fā)出申請一方的效用明顯好于另一方，而WYS算法的結果對于醫(yī)院和學生沒有明顯傾向性，多數(shù)參與主體都匹配到了其偏好序中前30位的對象，不會使某一方達成最差的穩(wěn)定匹配。G-S、Roth-Peranson等傳統(tǒng)算法中的劣勢一方由于只能被動選擇接受或拒絕，其自身偏好序中的部分對象永遠沒有機會嘗試匹配，理論上存在改善其效用的空間[23]。WYS算法為參與匹配的雙方主體設定一個外生優(yōu)先級，讓全部主體按照優(yōu)先級依次發(fā)出申請，每個主體都有機會遍歷自身偏好序中的全部對象，只要設置合理的優(yōu)先級，就可使得匹配雙方被同等對待。

（2）WYS算法提高了G-S等傳統(tǒng)算法中效用最差者的滿意度。如表1所示，10次隨機實驗中WYS算法的2 000個參與主體沒有任何一個匹配其偏好序67位之后的對象，而G-S算法匹配到偏好序67位之后的主體數(shù)量為41（學生優(yōu)先）和33（醫(yī)院優(yōu)先），WYS算法在偏好序位次30～100，40～100，50～100范圍內(nèi)匹配成功的主體數(shù)量也都明顯少于G-S算法，即效用過差者的數(shù)目有顯著減少。圖4展示了10次實驗中2 000個主體匹配結果的偏好位序分布情況，相對于G-S算法，WYS算法的過大異常值數(shù)目明顯較少且異常值的整體位序值不高，箱線圖上邊緣和上四分位較低，下四分位和中位較高，整體來看WYS算法上下四分位之間的分布較為集中。WYS算法相對于G-S算法來說犧牲了很少一部分效用極高者的利益，換取了效用最差者結果的顯著提升。

表1 10次實驗中2 000個主體匹配結果的偏好位序統(tǒng)計

圖4 10次實驗中2 000個主體匹配結果的偏好位序分布箱線圖

（3）WYS算法提升了參與者的總體效用。圖5為10次實驗平均之后的學生和醫(yī)院整體匹配結果偏好位次累積曲線，其中WYS算法曲線最凸，兩種G-S算法的曲線幾乎重合，較WYS算法更為平緩，意味著WYS算法的整體效用比G-S算法更高。WYS算法平均有191個主體匹配到了其偏好序中前30位的對象，有196.8個主體匹配到了其偏好序中前40位的對象，優(yōu)于G-S算法的匹配結果。實驗過程中生成偏好序的方式為0～1 000之間隨機打分，打分高者在偏好序中排名靠前，若以匹配對象的打分值作為主體獲得的效用，則WYS算法、學生優(yōu)先的G-S算法和醫(yī)院優(yōu)先的G-S算法給出的每個參與主體的平均效用分別為902.5、877.4和878.9，WYS算法的總體效用更高。

圖5 10次隨機實驗平均的學生和醫(yī)院整體偏好位次滿足累積曲線

（4）目前尚未從理論上證明算法的穩(wěn)定性，但大量隨機偏好序的一對一、一對多實驗發(fā)現(xiàn)隨著優(yōu)先級設定不同，WYS算法總能產(chǎn)生不同于經(jīng)典G-S算法的多種穩(wěn)定匹配結果，即WYS算法產(chǎn)生的結果不存在阻礙對。

在進行了多輪10次一組的實驗之后，發(fā)現(xiàn)上述（1）～（4）結論在每一輪實驗中都成立，另針對一對多、多對多匹配進行了實驗，上述（1）～（4）結論仍成立，說明算法具有相當?shù)姆€(wěn)健性。

5 結束語

本文針對傳統(tǒng)雙邊匹配算法存在的問題提出了全新的WYS算法，并按照Roth的經(jīng)濟工程學范式設計實驗對WYS算法的性質(zhì)進行了深入探討。WYS算法解決了G-S、Roth-Peranson等經(jīng)典雙邊匹配算法的單邊占優(yōu)問題，擴展了雙邊匹配算法的適用范圍，尤其有助于應對主體偏好一致性不強的場景，如婚姻匹配、銀行信貸與小微企業(yè)匹配、教育招生匹配、人崗匹配等問題，為相關領域基于雙邊匹配理論的市場設計實踐提供了更強的理論基礎。WYS算法對于傳統(tǒng)算法中效用最差的群體滿意度有顯著提高，對于提高主體參與意愿，維持市場厚度有重要意義。同時WYS算法通過外生指定不同優(yōu)先級，能夠傾向性地照顧不同主體，產(chǎn)生多種不同的穩(wěn)定匹配，而非如傳統(tǒng)算法只能選擇照顧參與雙方中的某一方，為匹配機構的宏觀調(diào)控和精細干預提供了可操作空間。WYS算法可通過設定匹配容量而用于一對一、一對多和多對多雙邊匹配問題，具有相當?shù)耐ㄓ眯浴?/p>

參考文獻：

[1]魏立佳.從微觀理論到社會實踐——市場設計的最新進展綜述[J].世界經(jīng)濟文匯，2013，56（3）：89-104.

[2]Che Y K，Gale I L.Market versus non-market assignment of ownership，1328984[R].Rochester，NY：Social Science Research Network，2009.

[3]Roth A E.The economist as engineer：Game theory，experimentation，and computation as tools for design economics[J].Econometrica，2002，70（4）：1341-1378.

[4]Roth A E，Peranson E.The redesign of the matching market for American physicians：Some engineering aspects of economic design[J].American Economic Review，1999，89（4）：748-780.

[5]Milgrom P.Critical issues in the practice of market design[J].Economic Inquiry，2011，49（2）：311-320.

[6]S?nmez T，ünver M U.Matching，allocation，and exchange of discrete resources[M]//Jess B，Jackson M O，Alberto B.Handbook of Social Economics.North Holland：Elsevier，2011：781-852.

[7]Budish E.Matching“versus”mechanism design[J].SIGecom Exchanges，2012，11（2）：4-15.

[8]Gale D，Shapley L S.College admissions and the stability of marriage[J].The American Mathematical Monthly，1962，69（1）：9-15.

[9]Roth A E.The economics of matching：Stability and incentives[J].Mathematics of Operations Research，1982，7（4）：617-628.

[10]Klumpp T.Two-sided matching with spatially differentiated agents[J].Journal of Mathematical Economics，2009，45（5）：376-390.

[11]Erdil A，Ergin H.Two-sided matching with indifferences[J].Journal of Economic Theory，2017，171（6）：268-292.

[12]Castillo M，Dianat A.Truncation strategies in two-sided matching markets：Theory and experiment[J].Games and Economic Behavior，2016，98（4）：180-196.

[13]Gharote M，Patil R，Lodha S，et al.Assignment of trainees to software project requirements：A stable matching based approach[J].Computers&Industrial Engineering，2015，87（9）：228-237.

[14]Byun J，Jang S.Effective destination advertising：Matching effect between advertising language and destination type[J].Tourism Management，2015，50（5）：31-40.

[15]Xu X，Wang C，Zeng Y，et al.Matching service providers and customers in two-sided dynamic markets[J].IFACPapersOnLine，2015，48（3）：2208-2213.

[16]Chen J，Song K.Two-sided matching in the loan market[J].International Journal of Industrial Organization，2013，31（2）：145-152.

[17]Silveira R，Wright R.Venture capital：A model of search and bargaining[J].Review of Economic Dynamics，2016，19（1）：232-246.

[18]Roth A E.Deferred acceptance algorithms：History，theory，practice，and open questions[J].International Journal of Game Theory，2008，36（3）：537-569.

[19]Roth A E.The evolution of the labor market for medical interns and residents：A case study in game theory[J].Journal of Political Economy，1984，92（6）：991-1016.

[20]Roth A E.What have we learned from market design?[J].The Economic Journal，2008，118（527）：285-310.

[21]Itai A，Yash K，Jacob D L.Unbalanced random matching markets：The stark effect of competition[J].Journal of Political Economy，2016，125（1）：69-98.

[22]李銘洋，樊治平，樂琦.考慮穩(wěn)定匹配條件的一對多雙邊匹配決策方法[J].系統(tǒng)工程學報，2013，29（4）：454-463.

[23]Kojima F，Pathak P A，Roth A E.Matching with couples：Stability and incentives in large markets[J].The Quarterly Journal of Economics，2013，128（4）：1585-1632.