匹配博弈理論及其發展*

李建榮，吳欲波

（1.華南師范大學數學科學學院，廣州510631；2.景德鎮陶瓷學院學報期刊社，景德鎮333000)

引言

2012年諾貝爾經濟學獎授予了美國哈佛大學教授埃爾文·羅斯(Alvin Roth)與美國洛杉磯加州大學教授羅伊德·夏普利(Lloyd Shapley)，獲獎原因是兩位在“穩定匹配理論和市場設計實踐”方面所作出的貢獻。

匹配是市場的重要功能之一。誰得到了哪一份工作，誰進了哪一所學校，誰同誰結了婚，誰在哪里買了房產等等，都是匹配的結果。Gale and Shapley （1962）[1]年發表在 《美國數學月刊》(American Mathematical Monthly)上的文章“College admissions and the stability ofmarriage”，標志著匹配博弈理論的誕生。匹配博弈理論運用博弈理論研究現實雙方市場的穩定、及因缺乏穩定而失靈問題。該文研究了兩個現實的雙方市場：婚姻市場和大學招生市場；以這兩個市場為模型，定義了一對一和多對一匹配、理性匹配、穩定匹配；還給出了一個尋找穩定匹配的算法：拒絕-接受算法。后繼文獻將它們統稱為Gale-Shapley模型(GS模型)。GS模型成為匹配理論和匹配機制領域的奠基性模型，拒絕-接受算法不僅成為修復市場失靈和構建新市場的必須工具，還日漸成為檢驗市場設計的“經濟工程師”。

作為博弈理論的一個獨立分支，匹配博弈理論自創立至今已有半個世紀，從未淡出經濟學家的視野，始終處在經濟學研究的前沿，并被廣泛地應用于現實市場的研究。然而，國內經濟學界對匹配博弈理論的研究和運用卻極為欠缺。

鑒于此，本文系統介紹了匹配博弈理論的基本模型及其發展與應用，指出其未來的發展方向，希望能彌補國內相關研究的空白，為后繼者進一步深入研究匹配博弈理論并應用于中國現實經濟問題提供參考。

一、匹配博弈理論的基本模型及算法

（一）匹配博弈理論的基本模型

市場由n個機構和m個個體組成，為了敘述的便利，沿用既有文獻慣于的術語，分別稱他們為企業和工人， 并用兩個不相交的集合F=｛f1， L ，fn｝和 W=｛w1， L，wm｝表示。 一個匹配是從工人一方到企業一方的一個映射，確定了每一個工人到哪一家企業工作，每一個企業招聘了哪些工人，及哪些工人與哪些企業沒有發生匹配①。一個匹配是穩定的指，每一個參與者的匹配對象都是可接受的，且不存在一對未發生匹配的參與者，他們互相偏好與對方發生匹配②。

如果每一個工人最多能到一家企業工作，每一個企業最多能招聘一個工人，這樣的匹配被稱為一對一匹配（如婚姻市場）；如果每一個工人最多能到一家企業工作，而一個企業卻可以招聘多個工人，這樣的匹配被稱為多對一匹配（如勞動力市場）；如果一個工人可以到多家企業工作，一個企業可以招聘多個工人，這樣的匹配被稱為多對多匹配（如勞動力市場中有些工人身兼數職）。于是，多對一匹配是一對一匹配的一般化，多對多匹配是多對一匹配的一般化，是最一般化的匹配模型；在一對一和多對多市場，工人與企業具有對稱的地位，但在多對一市場，不存在這種對稱性。

因為多對一匹配應用最廣泛，所以側重以多對一匹配作為介紹標的。規范地，我們給出如下多對一匹配定義。

定義1.一個匹配μ是從集合F∪W到由F∪W的所有子集構成的集合的一個映射，滿足對所有工人w?W 和所有企業 f?F，有

條件（i）表明μ是一個映射③，條件（ii）表明匹配的雙方特性：一個工人到一家企業工作，意味著這家企業招聘了這個工人。

每一個企業f?F在W的所有子集上有一個嚴格的、完備的、具有傳遞性的偏好P（f），具有如下形式：P（f）=S1，S2，φ，S3，表示如果讓 f在所有工人中作選擇，那么它的第一選擇是聘用 S1中的所有工人；如果 S1中有工人拒絕被它聘用，即S1對f是不可獲得，那么它將聘用S2中的所有工人；如果S2也不可獲得，那么它將選擇不招聘任何工人，即便其他工人集合，如S3是可獲得。這時稱S1和S2是可接受的對象，S3是不可接受的對象。 用 SP（f）S'表示 f偏好 S 勝于 S'，SR（f）S'表示 f偏好 S 不少于 S'，SR（f）φ 表示 S 是 f的可接受的對象。

每一個工人w?W在所有企業F上有一個嚴格的、完備的、具有傳遞性的偏好P（w）；用fP（w）f'表示w偏好 f勝于 f'，fR（w）f'表示 w 偏好 f不少于 f'，fR（w）φ 表示 f是 w 的可接受的對象。

用P=｛f1,L,fn,w1,L,wm｝表示所有參與者偏好的集合，稱為偏好束。

給定一群工人S?W和一個偏好束P，每一個企業f都能夠確定它在S中最想聘用哪些工人，用Cf（S）表示，稱為 f在 S 中的選擇集。 即 Cf（S）?S，且對任意的 S'?S，Cf（S）R（f）S'。 下面定義匹配的穩定性。

定義 2.如果匹配 μ 滿足：對所有的個體 k?F∪W，μ(k)R(k)φ；對所有的企業 f?F，Cf(μ(f))=μ(f)；稱 μ 是一個穩定匹配①。

（二）拒絕接受算法

匹配博弈理論的首要和核心工作是考證所研究的市場是否存在穩定匹配。當企業在所有工人個體上具有嚴格偏好時，Gale and Shapley(1962)利用拒絕接受算法證明了，市場一定存在穩定匹配。在匹配穩定性的研究上，拒絕接受算法至今仍是一個有效的算法。

拒絕接受算法分工人求職和企業招聘兩種，算法程序相同，不同的是由哪一方提議哪一方做選擇。給定偏好束P，由工人提議的拒絕接受算法程序如下：

● 第一步：每一個工人向他可接受的最偏好的企業遞交求職申請；每一個企業在它收到的所有申請中留下它選擇集中的申請，拒絕掉所有其它的申請。

● 第k步：每一個工人向還未拒絕過他的他可接受的最偏好的企業遞交求職申請；每一個企業在他收到的所有申請中留下它選擇集中的申請，拒絕掉所有其它的申請。

當沒有拒絕發生時，算法結束；屆時，每一個企業聘用它在算法最后一步驟中接受的所有工人，算法產生了一個匹配μw。

由企業提議的拒絕接受算法程序如下：

● 第一步：每一個企業向它在所有工人集合上的選擇集中的每一個工人發聘用申請；每一個工人在他收到的所有申請中，留下他可接受的最偏好的企業申請，拒絕掉所有其它的申請。

● 第k步：每一個企業向它在所有還未拒絕過它的工人集合上的選擇集中的每一個工人發聘用申請；每一個工人在他收到的所有申請中，留下他可接受的最偏好的企業申請，拒絕掉所有其它的申請。

當沒有拒絕發生時，算法結束；屆時，每一個企業聘用它在算法最后一步驟中發出申請的所有工人，算法產生了一個匹配μF。

二、匹配博弈理論的應用

（一）學校招生錄取

匹配博弈理論形成的一個動因，就是解決學校招生這類現實問題。Gale and Shapley(1962)提出的大學招生模型及拒絕接受算法，證明大學招生市場會產生一個穩定匹配，且對提議方來說是最優穩定匹配。

隨后，匹配博弈理論也被廣泛運用于學校招生市場的分析。如Abdulkadiroglu et al(2005)[7]和Abdulkadiroglu et al(2006)[8]研究了美國紐約市高中和波士頓市的公立學校，采用拒絕接受算法完成招生錄取工作。Teo(2001)[9]討論了新加坡的部分學校采用拒絕接受算法來完成擇校-錄取工作。

（二）勞動力市場的失靈及構建

匹配博弈理論最主要的一個應用，是用于解決勞動力市場的失靈與構建。在雙方市場上，同方參與者之間處于競爭狀態：企業互相競爭優秀的工人，工人互相競爭好的企業；對立方的參與者之間處于合作狀態。

Roth(1984a)[10]運用匹配理論研究美國醫學畢業生市場。該論文的重要意義在于，它揭示了匹配博弈理論所闡述的模型符合現實勞動力市場真實表現，而匹配博弈理論的方法也能夠較好地解決現實勞動力市場失靈的問題。

Roth(1984b)[11]證明了，當企業具有替代偏好⑤時，由工人提議的拒絕接受算法產生一個穩定匹配，并且，產生一個工人最優穩定匹配；即每一個工人對該匹配的偏好都不少于對任何其它穩定匹配的偏好；由企業提議的拒絕接受算法產生一個企業最優穩定匹配。

Roth(1985)[12]進一步定義了穩定匹配的一致性：給定兩個不同的穩定匹配，讓每一個企業（工人）從它（他）在這兩個匹配下的匹配對象的集合中選出它（他）最偏好的對象來；如果這樣選擇的結果依然是個穩定匹配，稱之為穩定匹配的一致性。穩定匹配的一致性自然地解釋了市場具有企業（工人）最優穩定匹配，揭示了競爭激烈的雙方市場存在合作的可能。Roth在替代偏好和嚴格偏好下，證明了穩定匹配的一致性對企業一方成立；同時，穩定匹配集合在企業公共偏好偏序下是一個完備格。

在Roth的研究基礎上，學者們從多方面拓展了匹配博弈理論在勞動力市場的應用研究：

其一是同事效應。在Roth的模型中，并未考慮同事效應所帶來的影響。Dutta and Masso(1997)[13]首次引入同事效應，研究匹配博弈理論，提出了DM模型。文中表明，工人的偏好定義在企業與工人集合的組合上；反映了工人不僅僅在意誰將是他的老板，還在意誰將是他的同事。DM模型還證明了在F-字典偏好和W-字典偏好下市場的穩定性。 Echenique and Oviedo(2006)[3]，Echenique and Yenmez(2007)[14]，Kominer(2010)[15]分別在具有同事效應的市場，構造了尋找穩定匹配的算法。Pycia(2012)[16]在兩兩聯盟和分割法則下，研究具有同事效應匹配市場的穩定性。李建榮(2012)[17]在工人工人偏好中引入外生的同事效應，用拒絕接受算法直接證明了穩定匹配的存在；并定義了F-對應偏好，在F-對應偏好下，證明了具有同事效應的市場具有與傳統市場類似的性質。

其二是穩定匹配的一致性。盡管Roth證明了穩定匹配的存在和穩定匹配的一致性。Li(2013)[18]分析了Roth證明中的邏輯漏洞，并以具體例子表明，Roth的上述兩個結論在給定條件下都不一定成立。

（三）機制設計

匹配理論對市場設計產生了深刻的影響，不僅被直接應用于匹配機制的實證研究中，還對機制設計提出了一些新的理論問題。

Immorlica and Mahdian(2005)[19]和Kojima and Pathak(2007)[20]研究了匹配市場中，參與者提供虛假偏好獲利的問題；分析了提供虛假偏好獲利是有限度的，提供虛假偏好獲利的機會隨著市場容量的增大而減少；而且在拒絕接受算法下，提供真實偏好是每一個申請者的占優策略⑥。

Hatfield and Milgrom (2005)[21]（HM模型）在匹配模型中引入契約，研究帶契約匹配市場的穩定性；在LAD偏好⑦假設下，證明了穩定匹配一定存在。Hatfield and Kojima(2010)[22]在HM模型基礎上，引入雙向替代和一致替代偏好，研究帶契約匹配市場的穩定性和穩定匹配集合的格結構。Hatfield and Kominers(2012)[23]研究了雙方契約匹配市場的穩定性；一份雙方契約綁定了一個賣方、一個買方、和一個交易品。因此，雙方契約匹配中，匹配雙方考慮的不僅僅是交易的標的，還考慮了交易對象；這類似于引入同事效應的匹配模型。

三、未來的研究方向

匹配博弈理論關注的是一個經濟學的中心問題：如何盡可能恰當地匹配不同的市場主體。2012年諾貝爾經濟學獎頒發給匹配博弈理論的創立者和推廣應用者，也說明了匹配博弈理論在經濟學研究領域的重要地位，以及其對于現實問題研究的重要意義。在過去的半個世紀里，已經出現了大量的匹配博弈理論和應用的研究成果。未來的匹配博弈理論和應用研究也必將進一步深化。理論研究方面，主要存在以下幾個研究方向：

1.非替代偏好。既有研究文獻，很大一部分建立在替代偏好的假設上；但當工人之間存在不可忽視的互補性（如正常運作一個R&D實驗室所需的所有專家），替代偏好就將失效。與之相關的問題是，在這種復雜的偏好下穩定匹配的存在性。這將使模型的微觀結構復雜許多，從而增加了分析和應用的難度。

2.成本問題。正如張五常[24]批評博弈論“博弈理論漠視了真實世界的交易費用的調查，誤入歧途，行不通也”⑧；匹配模型假設博弈參與人在博弈開始之前，就有一個關于對方市場的明確的偏好。而現實市場上很多參與人在匹配之前對對方市場的了解并不十分清楚，而偏好會隨著博弈的進行發生變化。為了有一個更精確的偏好，需要了解更多的信息，有些重要信息的獲取是需要成本的；這將影響匹配的結果，但在理論和實證上更準確地刻畫了現實經濟。所以，在匹配博弈模型中引入成本問題，是一個很有前景的研究方向。

3.市場設計。到目前為止，市場設計主要集中在能用某種中心化的匹配機制修復市場失靈上，而問題的背后往往有一個非中心化的市場或者一個潛在的市場需要理解。那么，如何在非中心化市場中處理什么提供了市場稠密，如何處理市場消化，和如何使市場安全的問題就成為一個很有希望的研究領域。建立在拒絕接受算法上的匹配機構，如何能在市場中運作，及這樣的匹配機構能解決什么類型的市場失靈，這需要掌握大量的關于市場微觀結構的博弈理論。

而在應用研究方面，匹配博弈理論更是擁有廣闊的發展空間。既有的研究文獻多是關注發達國家的現實經濟問題，鮮有對發展中國家現實經濟問題的探討。就中國而言，高校擴招及經濟下滑帶來就業壓力劇增；房價波動引發地產商與購房者之間的矛盾加?。换橐鍪袌霭滩「腥救藬?、離婚率逐年上升；通貨膨脹下工資因素引發“用工荒”；中小民營企業融資困境問題......如何運用匹配博弈理論來研究這些現實問題，并為雙方市場提供穩定發展的機制設計和政策建議，這也將成為匹配博弈理論未來研究的一個方向。

注釋：

①對于找不到工作的工人，把他們映射到空集；于是，我們有時把空集看作一個（啞）企業。類似地，有時把空集看作一群工人，與那些招不到工人的企業匹配。

②這里的穩定在匹配理論文獻中被稱為對穩定。

③僅滿足條件（i）的映射在 Adachi(2000)[2]和 Echenique and Yenmez(2006)[3]中被稱為“準匹配(prematching)”。

④這里定義的穩定在最近文獻中被稱為對穩定 （pairwise stability），Sotomayor (1999a,1999b)[4,5]，Echenique and Oviedo(2006)[3]和Konishiand Unver(2006)[6]討論了其它穩定概念。

⑤對任意一個工人聯盟S及工人w?S，如果w?Cf(S)，則對任意的S'?S，有w?Cf(S'∪{w})，就稱企業f具有替代偏好。

⑥這一問題的相關文獻還有Dubins and Freedman(1981)，Roth(1982a)，Demange,Gale,and Sotomayor(1987)。

⑦如果企業 f的偏好 P(f)滿足：對所有的 S"?S'?W，|Cf(S")|≤|Cf(S')|，就稱 f具有 LAD(Law of Aggregate Demand)偏好。

⑧張五常[24]，p.28。

[1]GALE,D.and L.SHAPLEY,1962,College Admissions and the Stability of Marriage[J].American Mathematical Monthly,69:9-15.

[2]ADACHI,H.,2000,On a Characterization of Stable Matchings[J].Economics Letters.68:43-49.

[3]ECHENIQUE,F.and J.OVIEDO,2006,A Theory of Stability in Many-to-Many Matching Markets[J].Theoretical Economics.1(2):233-273.

[4]SOTOMAYOR,M.,1999a,Three Remarks On the Many-to-Many Stable Matching Problem[J].Mathematical Social Sciences.38:55-70.

[5]SOTOMAYOR,M.,1999b,The Lattice Structure of the Set of Stable Utcomes of the Multiple Partners Assignment Game[J].International Journal of Game Theory.28:567-583.

[6]KONISHI,H and M.U.UNVER,2006,Credible Group Stability in Many-to-Many Matching Problems[J].Journal of Economic Theory.129:57-80.

[7]ABDULKADIROGLU A,PATHAK PA and ROTH A.E.The New York City High School Match[J].American Economic Review,Papers and Proceedings,2005,95(2):364-367.

[8]ABDULKADIROGLU A,PARAG PA,ROTH A.E and SONMEZ T.Changing the Boston School Choice Mechanism.Harvard University,Unpublishedmimeo,2006.

[9]TEO CP,SETHURAMAN J and WEE-PENG T.Gale-Shapley Stable Marriage Problem Revisited:Strategic issues and Applications[J].Management Science,2001,47:1252-1267.

[10]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.1984a,92:991-1016.

[11]ROTH A.E.Stability and Polarization of Interests in Job Matching[J].Econometrica,1984b,52:47-57.

[12]ROTH,A.E.Common and Confliction Interests in Two-sided Matching Markets[J].European Economic Review,1985,27:75-96.

[13]DUTTA B.and MASSO J.Stability of MatchingsWhen Individuals Have Preferences over Colleagues[J].Journal of Economic Theory,1997,75(2):464-475.

[14]ECHENIQUE F and YENMEZM.B.A Solution to MatchingWith Preferences Over Colleagues[J].Games and Economic Behavior,2007,59:46-71.

[15]KOMINERSS.D.Matching with Preferences over Colleagues Solves Classical Matching[J].Games and Economic Behavior,2010,68:773-780.

[16]PYCIA M.Stability and Preference Alignment in Matching and Coalition Formation[J].Econometrica,2012,80(1):323-362.

[17]李建榮.F-字典偏好與穩定匹配[J].南方經濟，2012（5）：54-60.

[18]Li J.A Note on Roth's Consensus Property of Many-to-one Matching[J].Mathematics of Operations Research,2013,38(2):389-391.

[19]IMMORLICA N and MOHAMMADM.Marriage,Honesty,and Stability[R].SODA 2005,53-62.

[20]KOJIMA F and PARAG P.Incentives and Stability in Large Two-Sided Matching Markets.working paper,2007.

[21]HATFIELD J.W and PAULM.Matching with Contracts[J].American Economic Review,2005,95(4):913-935.

[22]HATFIELD J.W and KOJIMA F.Substitutes and Stability for Matching with Contracts[J].Journal of Economic Theory,2010,145:1704-1723.

[23]HATFIELD J.W and KOMINER S.D.Stability and Competitive Equilibrium in Matching Marketswith Transfers.Workering paper,2012.

[24]張五常.佃農理論[M].商務印書館，2002：28.