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

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

1 雙邊匹配的概念

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

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

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

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

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

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

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)識，雙方都希望尋找到心儀的另一半。在匹配開始前，每一位男士對所有的n位女士都有一個心中的嚴(yán)格偏好排序，每一位女士同樣對n位男士有一個嚴(yán)格偏好排序。雙邊匹配理論研究的，便是通過怎樣的機制，能夠讓雙方獲得穩(wěn)定的匹配結(jié)果，并且讓雙方都滿意。

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

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

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

……

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

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

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

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

值得說明的是，在這個模型中，因為每次都是男方提出主動邀請，所以最后的匹配結(jié)果對男方是最優(yōu)的，而對女方僅僅只是可接受的。相反，如果算法每一輪都是女方提出邀請，而男方只有接受與拒絕的權(quán)力，那么最后的匹配結(jié)果對女方是最優(yōu)的。

2.3 “策略行為”問題

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

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

參考文獻

[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īng)濟學(xué)（季刊），2007（03）：899-916.

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

作者簡介

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