李建榮

博弈模型涉及多個(gè)利益相沖突的決策者。多個(gè)目標(biāo)收益一般難以同時(shí)達(dá)到最大，所以在博弈論的研究中缺少運(yùn)籌與管理科學(xué)其它領(lǐng)域所取得的最優(yōu)化結(jié)論。但在雙方市場(chǎng)中定義的博弈概念，卻可以使市場(chǎng)同方參與者的收益同時(shí)達(dá)到最大。Roth研究了多對(duì)一市場(chǎng)中的這種最優(yōu)化及其路徑問題，但作者證明了Roth的結(jié)論是錯(cuò)誤的，從而使優(yōu)化理論成為匹配理論研究中的一個(gè)缺口、一個(gè)有待解決的問題。鑒于此，梳理了雙方市場(chǎng)中資源的優(yōu)化配置、探討了解決方法并指出未來的研究方向。

博弈論的研究模型涉及多個(gè)利益相沖突的決策者。因?yàn)槎鄠€(gè)目標(biāo)收益一般難以同時(shí)達(dá)到最大，所以在博弈論的研究中極度缺乏運(yùn)籌與管理科學(xué)其它領(lǐng)域所取得的最優(yōu)化結(jié)論；而且，博弈模型的理論分析一般不注重確定“最優(yōu)”結(jié)果，而是首先注重確定在一些恰當(dāng)定義下的穩(wěn)定結(jié)果，如納什均衡。于是，在以雙方市場(chǎng)為研究對(duì)象的博弈理論—匹配理論—中研究最優(yōu)化及其路徑問題，就顯得尤為重要與迫切。

“匹配”是市場(chǎng)的重要功能之一。誰得到了哪一份工作，誰進(jìn)了哪一所學(xué)校，誰同誰結(jié)了婚，誰在哪里買了房產(chǎn)等等，都是匹配的結(jié)果。匹配博弈理論運(yùn)用博弈論的分析方法研究現(xiàn)實(shí)雙方市場(chǎng)的穩(wěn)定、及因缺乏穩(wěn)定而失靈問題，為現(xiàn)世經(jīng)濟(jì)現(xiàn)象的分析提供可靠的理論依據(jù)。Gale and Shapley 1962年發(fā)表在《美國(guó)數(shù)學(xué)月刊》（American Mathematical Monthly）上的文章“College admissions and the stability of marriage”，標(biāo)志著匹配博弈理論的誕生。

2012年，諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授予美國(guó)匹配博弈理論學(xué)家埃爾文·羅斯（Alvin E. Roth）與羅伊德·夏普利（Lloyd S. Shapley），使匹配博弈理論成為近期國(guó)際與國(guó)內(nèi)同行高度關(guān)注的一個(gè)熱點(diǎn)問題。巧合的是，作者在2012年證明了Roth （1985）關(guān)于多對(duì)一雙方匹配市場(chǎng)中的最優(yōu)化及其路徑問題的結(jié)論都是不正確的；作者的論文在運(yùn)籌與管理類國(guó)際一流學(xué)術(shù)期刊Mathematics of Operations Research上刊發(fā)后，立刻引起了國(guó)際同行的高度重視與關(guān)注，使該問題成為近期國(guó)際同行高度關(guān)注、博弈論學(xué)界急切想要解決的一個(gè)重大的、具有挑戰(zhàn)性的前沿問題。鑒于此，本文梳理了雙方市場(chǎng)中資源的優(yōu)化配置、探討了解決方法并指出未來的研究方向。

一、發(fā)展?fàn)顩r

在雙方市場(chǎng)中定義的博弈概念（如匹配、穩(wěn)定匹配等），可以使市場(chǎng)同方參與者（如企業(yè)或工人）的收益同時(shí)達(dá)到最大，這種最優(yōu)化存在的理論依據(jù)是選擇匹配的穩(wěn)定性，選擇匹配的穩(wěn)定性賦予穩(wěn)定匹配集合一定的格結(jié)構(gòu)，而穩(wěn)定匹配集合的格結(jié)構(gòu)給出了達(dá)到這種最優(yōu)化的具體路徑。

Knuth （1976）解決了一對(duì)一雙方匹配市場(chǎng)中的最優(yōu)化及其路徑問題。Li （2013）證明了Knuth的結(jié)論在替代偏好下不能推廣到多對(duì)一市場(chǎng)。因?yàn)槎鄬?duì)多市場(chǎng)是最一般化的雙方匹配市場(chǎng)，企業(yè)與工人具有完全對(duì)稱的地位，所以最優(yōu)化及其路徑問題在多對(duì)多市場(chǎng)也是一個(gè)未解難題。多年來不斷有經(jīng)濟(jì)學(xué)家嘗試解決這一問題，但都沒有得到肯定的結(jié)論。

1.選擇匹配的穩(wěn)定性

給定兩個(gè)不同的穩(wěn)定匹配，讓每一個(gè)企業(yè)從它在這兩個(gè)穩(wěn)定匹配下的匹配對(duì)象的并集中，選出它最偏好的工人集合來。這樣選擇的結(jié)果，定義了一個(gè)選擇函數(shù)，稱為由企業(yè)作選擇的選擇匹配。作者已經(jīng)證明了，在替代偏好下，是一個(gè)匹配但不一定是穩(wěn)定匹配。類似地，讓每一個(gè)工人從他在這兩個(gè)穩(wěn)定匹配下的匹配對(duì)象中，選出他最偏好的企業(yè)來。這樣選擇的結(jié)果，定義了一個(gè)匹配，稱為由工人作選擇的選擇匹配。

Gale and Shapley （1962）證明了：第一，當(dāng)每一個(gè)參與者在市場(chǎng)對(duì)方個(gè)體上有一個(gè)嚴(yán)格的偏好時(shí)，一對(duì)一和多對(duì)一穩(wěn)定匹配一定存在；第二，由拒絕接受算法產(chǎn)生的是一個(gè)提議方最優(yōu)穩(wěn)定匹配。Knuth （1976）在一對(duì)一市場(chǎng)中研究了這種最優(yōu)化的理論依據(jù)：給定兩個(gè)不同的穩(wěn)定匹配，讓每一個(gè)企業(yè)（工人）從它（他）在這兩個(gè)匹配下的匹配對(duì)象中選出它（他）偏好的那個(gè)來。當(dāng)參與者具有嚴(yán)格偏好時(shí)，Knuth證明了這樣選擇的結(jié)果依然是個(gè)穩(wěn)定匹配。Knuth的成果給Gale and Shapley最優(yōu)穩(wěn)定匹配的存在一個(gè)自然的解釋。

Roth （1984）推廣了Gale and Shapley關(guān)于多對(duì)一穩(wěn)定匹配的成果：一是當(dāng)企業(yè)在所有工人集合上有一個(gè)完備的、具有傳遞性的和嚴(yán)格的替代偏好時(shí)，多對(duì)一穩(wěn)定匹配一定存在；二是由拒絕接受算法產(chǎn)生的是一個(gè)提議方最優(yōu)穩(wěn)定匹配。 Roth （1985）在多對(duì)一市場(chǎng)嘗試推廣Knuth （1976）的結(jié)論：給定兩個(gè)不同的穩(wěn)定匹配，讓每一個(gè)企業(yè)（工人）從它（他）在這兩個(gè)匹配下的匹配對(duì)象的并集中選出它（他）最偏好的對(duì)象來，這一選擇的結(jié)果被稱為這兩個(gè)穩(wěn)定匹配的選擇函數(shù)。Roth 在替代偏好下證明了：由企業(yè)作選擇的選擇函數(shù)是個(gè)穩(wěn)定匹配，由工人作選擇的選擇函數(shù)不一定是個(gè)穩(wěn)定匹配。

Martinez et al （2001）在可分離偏好下研究了由工人作選擇的多對(duì)一選擇匹配的穩(wěn)定性，他們直接引用Roth的結(jié)論來完成他們的主要證明。Blair （1988）提到了，在替代偏好下，由企業(yè)作選擇的多對(duì)多選擇匹配不一定是穩(wěn)定匹配。因?yàn)樵诙鄬?duì)多市場(chǎng)中，工人與企業(yè)具有完全對(duì)稱的地位，所以由工人作選擇的多對(duì)多選擇匹配也不一定是穩(wěn)定匹配。

由企業(yè)作選擇的多對(duì)一選擇匹配的穩(wěn)定性自Roth （1985）提出后，歷經(jīng)28年，Li （2013）指出Roth的結(jié)論是不正確的。Li從選擇匹配的構(gòu)造入手，分析了選擇匹配的基本屬性，指出Roth的證明忽略了選擇匹配的一個(gè)重要性質(zhì)，從而存在嚴(yán)重的邏輯漏洞；并以具體實(shí)例表明Roth的結(jié)論不一定成立。因?yàn)镸artinez et al （2001）關(guān)于由工人作選擇的選擇匹配穩(wěn)定性的證明建立在Roth的結(jié)論之上，Li的結(jié)論顯示他們的成果有待重新考證。又因?yàn)槎鄬?duì)多市場(chǎng)是多對(duì)一市場(chǎng)的一般化，特殊市場(chǎng)不成立的性質(zhì)在一般化市場(chǎng)一定也不成立。于是，Li（2013）昭示了多對(duì)一和多對(duì)多市場(chǎng)選擇匹配的穩(wěn)定性成為匹配理論研究中的一個(gè)缺口、一個(gè)有待解決的問題。

2.穩(wěn)定匹配的格

格（lattice）是一個(gè)數(shù)學(xué)概念，但被廣泛地應(yīng)用于運(yùn)籌與管理學(xué)的研究中，特別是在勞動(dòng)力市場(chǎng)的研究中，給現(xiàn)實(shí)經(jīng)濟(jì)現(xiàn)象的分析提供一個(gè)理論依據(jù)。因?yàn)楦窬哂械牧己眯再|(zhì)，如任意兩個(gè)元素都有一個(gè)最小上界（上確界）和一個(gè)最大下界（下確界）。因此，在匹配理論的研究中格具有重要的地位。任意兩個(gè)穩(wěn)定匹配是否具有一個(gè)上確界和下確界？如果有，那么市場(chǎng)同方參與者之間除了競(jìng)爭(zhēng)還可以合作，共同達(dá)到利益的提高。但在匹配理論中研究格，難點(diǎn)是選取一個(gè)恰當(dāng)?shù)钠蜿P(guān)系。

Knuth （1976）研究了一對(duì)一市場(chǎng)穩(wěn)定匹配的格結(jié)構(gòu)。在一對(duì)一市場(chǎng)中，企業(yè)的偏好定義在工人個(gè)體上。因此，在由企業(yè)作選擇的選擇匹配下，企業(yè)是在工人個(gè)體上作比較和選擇；而企業(yè)公共偏好偏序也是定義在工人個(gè)體上；所以容易證明是穩(wěn)定匹配集合在企業(yè)公共偏好偏序下的上確界算子，是下確界算子。Knuth利用和的穩(wěn)定性，證明了一對(duì)一穩(wěn)定匹配集合是一個(gè)滿足分配律的完備格。

Roth （1985）嘗試把Knuth在一對(duì)一市場(chǎng)的格結(jié)論推廣到多對(duì)一市場(chǎng)。他首先證明了由企業(yè)作選擇的多對(duì)一選擇匹配的穩(wěn)定性，然后聲稱是多對(duì)一穩(wěn)定匹配集合在企業(yè)公共偏好偏序下的上確界算子，進(jìn)一步聲稱穩(wěn)定匹配集合是一個(gè)完備格。Roth將Knuth結(jié)論的一部分推廣到了多對(duì)一市場(chǎng)，但較之Knuth的結(jié)論，他的不足之處在于：Roth的格缺少一個(gè)定義自然的下確界；第二，Roth的格不存在一個(gè)對(duì)偶的結(jié)論，即穩(wěn)定匹配集合在工人公共偏好偏序關(guān)系下是否是一個(gè)格；最后，Roth沒有對(duì)格進(jìn)行分配律的證明。

Martinez et al （2001）在可分離偏好下研究了多對(duì)一穩(wěn)定匹配集合在工人公共偏好偏序下的格問題。他們引用Roth的結(jié)論（是穩(wěn)定匹配），證明了由工人作選擇的選擇匹配的穩(wěn)定性，然后證明了多對(duì)一穩(wěn)定匹配集合在工人公共偏好偏序下是一個(gè)完備格，和分別是上確界和下確界算子。但他們沒有討論格的分配律問題。

Blair （1988）研究了多對(duì)多市場(chǎng)上當(dāng)參與者具有替代性選擇函數(shù)時(shí)，穩(wěn)定匹配集合的格問題。他證明了穩(wěn)定匹配集合在一個(gè)“恰當(dāng)”的偏序 （后繼文獻(xiàn)將之稱為“Blair偏序”）下是一個(gè)完備格，但在企業(yè)公共偏好偏序下不一定是個(gè)格。但Blair格的上確界沒有一個(gè)明確的定義，并缺少下確界，因而無法自然地解釋多對(duì)多市場(chǎng)存在最優(yōu)穩(wěn)定匹配。而且，Blair的格不滿足分配律。

Li （2013）指出Roth （1985）關(guān)于多對(duì)一穩(wěn)定匹配的格結(jié)論是不正確的。在多對(duì)一市場(chǎng)中，企業(yè)與工人具有不對(duì)稱的地位（這與一對(duì)一市場(chǎng)不同），工人的偏好依然定義在企業(yè)個(gè)體上，而企業(yè)的偏好定義在工人集合上。企業(yè)公共偏好偏序由企業(yè)在兩個(gè)工人集合間擇優(yōu)選取定義，而選擇函數(shù)卻是由企業(yè)在兩個(gè)工人集合的并集中選出最偏好的工人集合定義，這兩個(gè)定義的結(jié)果是不一致的（這與一對(duì)一市場(chǎng)不同）。因此，不能簡(jiǎn)單地把Knuth在一對(duì)一市場(chǎng)的結(jié)論不加證明地推廣到多對(duì)一市場(chǎng)。Li以具體實(shí)例表明，不一定是企業(yè)公共偏好偏序的上確界算子。Li分析了Roth的錯(cuò)誤不僅僅是他關(guān)于穩(wěn)定性的證明是錯(cuò)誤的，還在于他選擇了一個(gè)不恰當(dāng)?shù)钠蜿P(guān)系。因?yàn)镸artinez et al （2001）的證明依賴于Roth的結(jié)論，所以多對(duì)一穩(wěn)定匹配在工人公共偏好偏序下的格問題有待重新研究。

鑒于Li （2013）的證明，結(jié)合Blair （1988），多對(duì)一與多對(duì)多雙方匹配市場(chǎng)中的格問題成為近期匹配理論研究中一個(gè)引人矚目和有待解決的問題。

二、研究方向

Li證明了在替代偏好下不一定是穩(wěn)定匹配，Roth （1985）證明了在替代偏好下不一定是穩(wěn)定匹配。Li證明了，在替代偏好下，和不是企業(yè)公共偏好偏序的上確界和下確界算子。于是，勞動(dòng)力市場(chǎng)中的資源優(yōu)化配置研究有如下幾個(gè)方向：多對(duì)一選擇匹配的穩(wěn)定性；多對(duì)一穩(wěn)定匹配的格；多對(duì)多選擇匹配的穩(wěn)定性和穩(wěn)定匹配的格，在前兩個(gè)研究成果的基礎(chǔ)上，解決最一般化匹配市場(chǎng)的優(yōu)化研究。

三、研究意義

博弈論的研究模型涉及多個(gè)利益相沖突的決策者。因?yàn)槎鄠€(gè)目標(biāo)收益一般難以同時(shí)達(dá)到最大，所以在博弈論的研究中極度缺乏運(yùn)籌與管理科學(xué)其它領(lǐng)域所取得的最優(yōu)化結(jié)論。但在雙方市場(chǎng)中定義的博弈概念（如匹配、穩(wěn)定匹配等），卻可以使市場(chǎng)同方參與者（如企業(yè)或工人）的利益同時(shí)達(dá)到最大；Roth（1985）研究了多對(duì)一市場(chǎng)中的這種最優(yōu)化及其路徑問題，但作者在2012年證明了Roth的結(jié)論是錯(cuò)誤的。鑒于Roth榮獲2012年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)桂冠，作者的論文及雙方匹配市場(chǎng)中的最優(yōu)化及其路徑問題引起了廣泛的社會(huì)效應(yīng)與關(guān)注。因此，該問題的研究不僅具有重要的理論與現(xiàn)實(shí)意義，還具有重要的社會(huì)影響與深遠(yuǎn)意義。

1.理論意義

作者已經(jīng)證明了Roth（1985）關(guān)于雙方匹配市場(chǎng)中的最優(yōu)化及其路徑問題的結(jié)論都是不正確的，使該問題成為匹配博弈理論研究中的一個(gè)缺口。所以該問題的研究成果有望彌補(bǔ)與完善匹配博弈理論研究。

該問題的成果有助于解決“多對(duì)多匹配市場(chǎng)核的存在”這一匹配理論研究中的重大難題，同時(shí)為供應(yīng)鏈匹配的最優(yōu)化問題提供理論依據(jù)與支撐。

2.現(xiàn)實(shí)意義

鑒于選擇匹配的穩(wěn)定性與穩(wěn)定匹配的格問題在最優(yōu)化理論、市場(chǎng)機(jī)制設(shè)計(jì)與市場(chǎng)管理方面的廣泛應(yīng)用，該問題的研究有望促進(jìn)這些相關(guān)領(lǐng)域的研究與發(fā)展。

該問題的研究成果有助于我國(guó)雙方匹配市場(chǎng)現(xiàn)存問題的解決，如高校擴(kuò)招及經(jīng)濟(jì)下滑帶來的就業(yè)壓力、房?jī)r(jià)波動(dòng)引發(fā)地產(chǎn)商與購(gòu)房者之間的矛盾、中小民營(yíng)企業(yè)融資困境等問題。

3.深遠(yuǎn)影響

匹配理論作為博弈論的一個(gè)獨(dú)立分支，一直是運(yùn)籌與經(jīng)濟(jì)管理研究中的一個(gè)熱點(diǎn)與難點(diǎn)，是計(jì)算數(shù)學(xué)、生物工程學(xué)和社會(huì)科學(xué)研究中的一個(gè)重要工具，但國(guó)內(nèi)對(duì)該理論的研究和應(yīng)用卻極為欠缺。2012年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)?lì)C給了匹配博弈理論學(xué)家，使該理論受到國(guó)內(nèi)同行的關(guān)注。鑒于國(guó)內(nèi)對(duì)匹配博弈理論的研究比較欠缺，該問題的研究，將會(huì)引起國(guó)內(nèi)外同行的興趣與關(guān)注，促進(jìn)國(guó)內(nèi)學(xué)界在匹配博弈理論方面的研究與發(fā)展應(yīng)用。

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（No. 71301056），廣東省自然科學(xué)基金項(xiàng)目（No. S2013040016469）。

（作者單位：華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院金融數(shù)學(xué)系）