非完全信息偏好下一對(duì)一匹配問題的Gale—Shapley分配機(jī)制

摘 要：在非完全信息狀態(tài)下，匹配問題中的參與人可以選擇謊報(bào)偏好，來使得自己能夠獲得更好的結(jié)果。文章的目的是以非完全信息偏好下的勞動(dòng)力市場為例，提出了一種Gale-Shapley分配機(jī)制以約束參與人不要說謊，并證明了在此機(jī)制下，任何工人都無法通過說假話使得自己的匹配結(jié)果得到改善。

關(guān)鍵詞：非完全信息；匹配問題；勞動(dòng)力市場；Gale-Shapley分配機(jī)制

中圖分類號(hào)：O2211 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8937（2014）9-0015-02

1 一對(duì)一匹配問題及其穩(wěn)定性簡介

在一對(duì)一匹配問題中，最典型的就是婚姻匹配問題。

2 Gale-Shapley分配機(jī)制

現(xiàn)在考慮這樣一個(gè)勞動(dòng)力市場問題（S-U），我們在這里不妨考慮這樣一種特殊情況：工人和企業(yè)的數(shù)量是等同的，工人用集合S表示，企業(yè)用集合U表示，并且規(guī)定每個(gè)企業(yè)的招工人數(shù)為1；每個(gè)工人對(duì)所有的企業(yè)有自己的一個(gè)偏好排序，每個(gè)企業(yè)對(duì)所有的工人同樣也有一個(gè)偏好排序，雙方參與人均認(rèn)為對(duì)方每個(gè)人（企業(yè)）是可接受的。現(xiàn)在需要將工人和企業(yè)一一配對(duì)并形成一個(gè)穩(wěn)定匹配。

設(shè)計(jì)如下場景：所有的企業(yè)都在一個(gè)房間里，同時(shí)，所有的工人都在房間的外面。現(xiàn)在，某個(gè)工人S1進(jìn)入房間，并開始對(duì)他最喜歡的企業(yè)提出申請，由于所有工人對(duì)企業(yè)來說，都是可接受的，所以被申請的企業(yè)U1必然接受工人S1的申請，雙方暫時(shí)形成配對(duì)，但是企業(yè)仍然可以接受其他工人的申請。下一步，另一個(gè)工人S2進(jìn)入房間并對(duì)其最喜歡的企業(yè)提出申請，考慮這樣一種特殊情況，如果S2和S1申請的是同一個(gè)企業(yè)U1，那么此時(shí)U1先后收到了2個(gè)工人的申請，U1必須作出選擇，根據(jù)偏好從S2和S1中選擇自己更喜歡的工人留下，同時(shí)拒絕另外一個(gè)，被拒絕的工人則回到房間外面繼續(xù)等待下一次申請的機(jī)會(huì)。之后以此類推，即每個(gè)工人Sj向之前沒有拒絕過他的最好企業(yè)提出申請。

3 參與人中存在一個(gè)說謊者的匹配問題

在工人S集合中，存在一個(gè)特殊的參與人M，M對(duì)所有的企業(yè)有一個(gè)確定的偏好排序。若M采用真實(shí)偏好參與GS分配并被某個(gè)企業(yè)錄取，這樣的分配過程稱為公平分配；若允許M使用虛假偏好參與GS分配并被某個(gè)企業(yè)錄取，此分配過程稱為違規(guī)分配。

定理2：假設(shè)M使用虛假偏好參與GS分配，則M在此違規(guī)分配下得到的結(jié)果不會(huì)比他在公平分配中的結(jié)果更好（結(jié)果的好壞根據(jù)M的真實(shí)偏好排序來確定）。

為了證明上述定理，我們不妨先假設(shè)這樣的場景，M在房間外一直等待，直到所有其他工人先后進(jìn)入房間并和企業(yè)一對(duì)一匹配，為了后面描述方便，將這階段過程命名為序章。在序章結(jié)束時(shí)候，房間內(nèi)會(huì)剩下一個(gè)從未收到過任何申請的企業(yè)，稱其為W?，F(xiàn)在M進(jìn)入房間并根據(jù)規(guī)則開始提出申請，需要注意，此時(shí)M是使用的虛假偏好。

不難分析出，一旦W收到第一份申請時(shí)，整個(gè)匹配過程結(jié)束。

從定理1的結(jié)論可以得知，在GS分配下，工人進(jìn)入房間的順序不會(huì)影響最后的結(jié)果，所以不失一般性，可以假設(shè)M最后進(jìn)入房間。為了方便證明，下面先給出兩個(gè)定義：

定義1（方案的定義）：方案是工人M的一組申請序列，是M偏好序列的初始階段。例如有這樣一個(gè)方案，包含三個(gè)企業(yè)：A，B，C。

該方案解釋如下：M將首先向企業(yè)A提出申請，若被拒絕，則嘗試向企業(yè)B申請，若再被拒絕則申請C。通常來說，方案其實(shí)就是一串企業(yè)的序列，但是任何企業(yè)都不可能在同一個(gè)方案中出現(xiàn)兩次或更多。

通過上述分析，可知，在一方參與人S先提出申請的情況下，S中的單個(gè)說謊者無法通過采用虛假偏好參與違規(guī)分配來使自己獲得更好的結(jié)果。

3 結(jié) 語

綜上所述，GS分配機(jī)制能夠有效的約束一方參與人不說謊話，但是對(duì)于另一方參與人并無有效約束。下一步研究方向不妨考慮在此基礎(chǔ)上能否找到一個(gè)更好的方法，對(duì)另一邊參與人說謊情況也能形成有效的約束。

參考文獻(xiàn)：

[1] D.Gale，L.S.Shapley.College admissions an the stability of ma-rriage[J].this MONTHLY，1962，（69）.

[2] A.E.Roth.Deferred acceptance algorithm：history，theory，practi-ce and open questions[J].Game Theory，2008，（36）.