雙邊匹配理論研究綜述

摘 要：“匹配”是人類社會(huì)常見的現(xiàn)象，而“雙邊匹配”便是理解該問題的重要理論。該理論創(chuàng)始人憑借在該領(lǐng)域的研究奉獻(xiàn)獲得了2012年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)，該理論也充分應(yīng)用在了高考匹配、勞動(dòng)力市場(chǎng)匹配等領(lǐng)域。本文通過對(duì)雙邊匹配概念、算法進(jìn)行詳述，幫助讀者更全面的了解該理論。

關(guān)鍵詞：雙邊匹配

1 雙邊匹配的概念

“匹配”是人類社會(huì)常見的現(xiàn)象，在婚姻中男女雙方需要匹配，在市場(chǎng)上買方與賣方需要匹配，在勞動(dòng)力市場(chǎng)上雇主與雇員需要匹配。而匹配理論便是從這些現(xiàn)象出發(fā)，研究其內(nèi)在機(jī)制與相關(guān)問題。2012年，諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授給授予學(xué)者埃爾文·羅斯（Alvin E. Roth）及加州大學(xué)羅伊德·沙普利（Lloyd S. Shapley），得獎(jiǎng)的理由是“以鼓勵(lì)他們?cè)诜€(wěn)定配置理論及市場(chǎng)設(shè)計(jì)實(shí)踐上所作出的貢獻(xiàn)”。 “雙邊匹配理論”便是理論的核心。

雙邊匹配的概念，最早是由Roth（1985）總結(jié)提出，“雙邊”強(qiáng)調(diào)市場(chǎng)中的參與者屬于兩個(gè)不相交的集合，“匹配”強(qiáng)調(diào)了市場(chǎng)交換的雙邊性質(zhì)，雙方都具有穩(wěn)定性偏好。雙邊匹配理論，就是以雙邊匹配為研究對(duì)象，研究具有穩(wěn)定偏好的不相交的雙方的匹配過程。

雙邊匹配通常按照其雙邊匹配對(duì)象的數(shù)目，分為一對(duì)一匹配、一對(duì)多匹配、多對(duì)多匹配。

一對(duì)一（1：1）匹配是指一方是一個(gè)個(gè)體，另一方也是一個(gè)個(gè)體的匹配。如男女婚姻匹配，最后匹配結(jié)果是一位男士匹配到一位女士。

一對(duì)多（1：n）匹配是指匹配雙方一方是個(gè)體，另一方是組織（招收多個(gè)個(gè)體）的匹配。如雇員雇主匹配，最后結(jié)果每個(gè)雇主招到多個(gè)雇員，而每個(gè)雇員只匹配到一個(gè)雇主。其他的例子還有學(xué)校-學(xué)生匹配。

多對(duì)多（n：n）匹配是指雙方都可以和多個(gè)對(duì)方匹配的情況。常見的是顧客與電商平臺(tái)的匹配，單個(gè)顧客可以選擇多個(gè)電商平臺(tái)購買商品，而單個(gè)電商平臺(tái)也同時(shí)服務(wù)多個(gè)顧客。

2 “雙邊匹配”經(jīng)典婚姻模型與GS算法概述

Gale 和 Shapley在1962年提出的男女婚姻匹配模型與經(jīng)典的GS遞延接受算法，本模型是該領(lǐng)域許多其他研究的基礎(chǔ)，包括模型與算法構(gòu)建、穩(wěn)定性（核）的討論以及策略行為的討論。

2.1 模型與算法構(gòu)建

設(shè)有n位男士和n位女士，假設(shè)他們彼此都相互認(rèn)識(shí)，雙方都希望尋找到心儀的另一半。在匹配開始前，每一位男士對(duì)所有的n位女士都有一個(gè)心中的嚴(yán)格偏好排序，每一位女士同樣對(duì)n位男士有一個(gè)嚴(yán)格偏好排序。雙邊匹配理論研究的，便是通過怎樣的機(jī)制，能夠讓雙方獲得穩(wěn)定的匹配結(jié)果，并且讓雙方都滿意。

首先，我們可以把問題抽象化，設(shè)n位女士的集合為M={w1，w2，……，wn}，n位男士的集合為W={m1，m2，……，mn}，目標(biāo)是要找到一個(gè)穩(wěn)定的匹配集合C={（w1，mk1），（w2，mk2），……，（wn，mkn）}，其中ki屬于M（i=1，2，…，n）。Gale 和 Shapley最早提出的是男士先選的遞延接受算法，這種算法對(duì)男士有利。算法的過程如下：

第一輪：每個(gè)男士都向自己最喜歡的女士發(fā)出邀請(qǐng)。此時(shí)女士會(huì)存在三種情況，沒有收到邀請(qǐng)，收到一份邀請(qǐng)，收到多份邀請(qǐng)。如果收到多份邀請(qǐng)，那么該女士需要按照自己的排序，選擇最喜歡的那個(gè)男士，然后拒絕其他人。

第二輪：所有被拒絕的男士向他下一位喜歡的女士發(fā)出邀請(qǐng)，上一輪沒有被拒絕的男士再次向他上一輪發(fā)出邀請(qǐng)的那位女士發(fā)出邀請(qǐng)。同第一步，收到多份邀請(qǐng)的女士選擇最喜歡的那個(gè)男士，然后拒絕其他人。

……

第k輪：不斷重復(fù)第二步，被拒絕的男士向他偏好列表的下一位女士發(fā)出邀請(qǐng)，其他均相同

直到：所有男士都沒有被拒絕，算法結(jié)束。

2.2 “穩(wěn)定匹配”問題

只要滿足每個(gè)個(gè)體對(duì)對(duì)方都有嚴(yán)格偏好，且所有人的匹配都是可接受的（即有另一半總比單身好），那么該算法通過至多n2-2n+2輪后便會(huì)結(jié)束，并且Gale 和 Shapley證明了其結(jié)果是最優(yōu)穩(wěn)定匹配。這里的穩(wěn)定匹配（stable matching）是指當(dāng)算法結(jié)束后，對(duì)于任意男士mk，設(shè)其最終匹配了wp，在女士集合中，無法再找到一個(gè)女士wq，設(shè)wq匹配的mi，而這位女士的優(yōu)先級(jí)列表中，是mk優(yōu)先于mi的。通俗的來講，所有男性已經(jīng)和在考慮其他男士競(jìng)爭(zhēng)的情況下不會(huì)拒絕他的，列表中最靠前的女性進(jìn)行了匹配。Vate（1989）進(jìn)一步指出，整個(gè)穩(wěn)定匹配問題，其本質(zhì)上就是一個(gè)線性規(guī)劃問題。

值得說明的是，在這個(gè)模型中，因?yàn)槊看味际悄蟹教岢鲋鲃?dòng)邀請(qǐng)，所以最后的匹配結(jié)果對(duì)男方是最優(yōu)的，而對(duì)女方僅僅只是可接受的。相反，如果算法每一輪都是女方提出邀請(qǐng)，而男方只有接受與拒絕的權(quán)力，那么最后的匹配結(jié)果對(duì)女方是最優(yōu)的。

2.3 “策略行為”問題

“策略行為”是指市場(chǎng)的參與者通過策略性的提交自己虛假的偏好序列，來使自己情況得到改善的行為。Roth（1982）對(duì)策略行為進(jìn)行了詳細(xì)的探討，證明了策略行為在婚姻模型中是有效的。婚姻模型中，不存在穩(wěn)定的機(jī)制，使所有人申明最優(yōu)偏好都是占優(yōu)策略。在男士先選的M-最優(yōu)中，對(duì)每一個(gè)男士而言，申明真實(shí)偏好排序是占優(yōu)策略，而對(duì)女士而言，策略行為便可能有效。相反，在女士先選的W-最優(yōu)中，對(duì)每一個(gè)女士而言，申明真實(shí)偏好是占優(yōu)策略，此時(shí)男士的策略行為便可能有效。

更進(jìn)一步，Roth 和 Sotomayor（1990）證明了至少有一個(gè)參與人能通過表達(dá)虛假的偏好而獲益。不過，策略行為不總是有效的，也可能適得其反，所以對(duì)于被動(dòng)方而言，申明真實(shí)偏好也并不一定是劣策略。

參考文獻(xiàn)

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

[2]Roth A.E. New Physicians： a natural experiment in market organization[J]. Science，1990，250（4987）：1524-1528.

[3]王塑，李西平，王新，李珊.基于雙邊匹配理論的人員-崗位適配性研究[J].人力資源管理，2013（12）：343-347.

[4]聶海峰.高考錄取機(jī)制的博弈分析[J].經(jīng)濟(jì)學(xué)（季刊），2007（03）：899-916.

[5]張衛(wèi)東，黃春華.雙邊匹配理論及其應(yīng)用研究新進(jìn)展——對(duì)諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)獲獎(jiǎng)成就的進(jìn)一步闡發(fā)[J].經(jīng)濟(jì)學(xué)動(dòng)態(tài)，2015（06）：137-147.

作者簡(jiǎn)介

范偉珂（1995-），男，漢族，四川成都人，學(xué)生，管理學(xué)碩士研究生，中央財(cái)經(jīng)大學(xué)商學(xué)院人力資源管理專業(yè)，研究方向：人力資源管理。