李建榮，吳欲波

（1.華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，廣州510631；2.景德鎮(zhèn)陶瓷學(xué)院學(xué)報期刊社，景德鎮(zhèn)333000)

引言

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

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

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

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

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

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

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

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

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

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

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

每一個企業(yè)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在所有企業(yè)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，每一個企業(yè)f都能夠確定它在S中最想聘用哪些工人，用Cf（S）表示，稱為 f在 S 中的選擇集。 即 Cf（S）?S，且對任意的 S'?S，Cf（S）R（f）S'。 下面定義匹配的穩(wěn)定性。

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

（二）拒絕接受算法

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

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

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

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

當沒有拒絕發(fā)生時，算法結(jié)束；屆時，每一個企業(yè)聘用它在算法最后一步驟中接受的所有工人，算法產(chǎn)生了一個匹配μw。

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

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

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

當沒有拒絕發(fā)生時，算法結(jié)束；屆時，每一個企業(yè)聘用它在算法最后一步驟中發(fā)出申請的所有工人，算法產(chǎn)生了一個匹配μF。

二、匹配博弈理論的應(yīng)用

（一）學(xué)校招生錄取

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

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

（二）勞動力市場的失靈及構(gòu)建

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

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

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

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

在Roth的研究基礎(chǔ)上，學(xué)者們從多方面拓展了匹配博弈理論在勞動力市場的應(yīng)用研究：

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

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

（三）機制設(shè)計

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

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

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

三、未來的研究方向

匹配博弈理論關(guān)注的是一個經(jīng)濟學(xué)的中心問題：如何盡可能恰當?shù)仄ヅ洳煌氖袌鲋黧w。2012年諾貝爾經(jīng)濟學(xué)獎頒發(fā)給匹配博弈理論的創(chuàng)立者和推廣應(yīng)用者，也說明了匹配博弈理論在經(jīng)濟學(xué)研究領(lǐng)域的重要地位，以及其對于現(xiàn)實問題研究的重要意義。在過去的半個世紀里，已經(jīng)出現(xiàn)了大量的匹配博弈理論和應(yīng)用的研究成果。未來的匹配博弈理論和應(yīng)用研究也必將進一步深化。理論研究方面，主要存在以下幾個研究方向：

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

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

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

而在應(yīng)用研究方面，匹配博弈理論更是擁有廣闊的發(fā)展空間。既有的研究文獻多是關(guān)注發(fā)達國家的現(xiàn)實經(jīng)濟問題，鮮有對發(fā)展中國家現(xiàn)實經(jīng)濟問題的探討。就中國而言，高校擴招及經(jīng)濟下滑帶來就業(yè)壓力劇增；房價波動引發(fā)地產(chǎn)商與購房者之間的矛盾加劇；婚姻市場艾滋病感染人數(shù)、離婚率逐年上升；通貨膨脹下工資因素引發(fā)“用工荒”；中小民營企業(yè)融資困境問題......如何運用匹配博弈理論來研究這些現(xiàn)實問題，并為雙方市場提供穩(wěn)定發(fā)展的機制設(shè)計和政策建議，這也將成為匹配博弈理論未來研究的一個方向。

注釋：

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

②這里的穩(wěn)定在匹配理論文獻中被稱為對穩(wěn)定。

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

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

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

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

⑦如果企業(yè) 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-字典偏好與穩(wěn)定匹配[J].南方經(jīng)濟，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]張五常.佃農(nóng)理論[M].商務(wù)印書館，2002：28.