雙邊匹配理論研究綜述

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

關鍵詞：雙邊匹配

1 雙邊匹配的概念

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

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

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

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

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

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

2 “雙邊匹配”經典婚姻模型與GS算法概述

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

2.1 模型與算法構建

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

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

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

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

……

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

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

2.2 “穩定匹配”問題

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

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

2.3 “策略行為”問題

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

更進一步，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].經濟學（季刊），2007（03）：899-916.

[5]張衛東，黃春華.雙邊匹配理論及其應用研究新進展——對諾貝爾經濟學獎獲獎成就的進一步闡發[J].經濟學動態，2015（06）：137-147.

作者簡介

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