非完全信息偏好下一對一匹配問題的Gale—Shapley分配機制

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

關鍵詞：非完全信息；匹配問題；勞動力市場；Gale-Shapley分配機制

中圖分類號：O2211 文獻標識碼：A 文章編號：1006-8937（2014）9-0015-02

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

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

2 Gale-Shapley分配機制

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

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

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

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

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

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

不難分析出，一旦W收到第一份申請時，整個匹配過程結束。

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

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

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

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

3 結 語

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

參考文獻：

[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）.