配對理論是由 Gale 和 Shapley (1962) 討論大學入學時學生與學校的配對以及婚姻市場的男女配對開始的。每當出現兩個群體要相互配對時，配對理論可以告訴我們要如何配對，才可以滿足一些良好的性質，像是配對有沒有公平？有沒有效率？或能不能讓大家給出自己真實的偏好？婚姻市場、腎臟捐獻的分配、中學和大學的入學制度等都有為數不少的研究者在研究什麼樣的配對方式可以滿足這些良好性質。

每次配對中，我們希望配對的結果是參與者能夠接受的，所以會有一些配對結果希望達成的目標。第一個目標是穩定配對 (stable matching)：我們希望不會有人在配對結果出來後可以私下又去配對來得到更好的結果；第二個目標是效率 (Pareto efficient)，也就是不會有另外一種配對使得所有人都配到跟先前至少一樣好的人，而其中又有人的確得到更想要的人；第三個目標是誠實公布自己的偏好 (truthful-telling) ，我們不希望大家在公布偏好的過程中還要思考自己要如何公布偏好才能得到更好的配對結果，而是只要配對者真實公布自己的偏好後，配對結果就是最好的。因此，為了要達到這三大性質，研究者們設計出各種不同的配對機制來盡可能地滿足這些目標。

其中，最廣為人知的配對機制叫做延遲遞移演算法 (Deferred Acceptance Algorithm)，本文將用一個三男三女互相配對的例子來解釋延遲遞移演算法，並且討論穩定配對、效率、和誠實公布偏好這三種性質。例子如下：

假設有三位男生 {Alex, Bob, Charles} 、 三位女生 {Daisy, Emma, Fiona} 要配對，同時假設男生只偏好女生不然就維持單身、女生只偏好男生不然就維持單身、而且一個人只能配對到一個人或單身。男生們的偏好如下：

同時女生也會有對男生和單身的偏好，女生們的偏好如下：

現在我們先讓男生主動去邀約女生。第一回合，Alex 和 Charles 邀請 Daisy 、Bob 邀請 Emma，此時，因為 Daisy 喜歡 Alex 勝過 Charles，Daisy 會暫時接受Alex 的邀約，拒絕 Charles；而 Emma 會暫時接受 Bob 的邀約，第一回合結束。 第二回合，只有 Charles 沒有暫時配對到任何人，所以他會轉而邀約 Fiona。此時因為 Fiona 喜歡 Charles 勝過單身，Fiona 會暫時接受 Charles；同時 Daisy 跟 Alex 暫時配對成功、Emma 暫時跟 Bob 配對成功，第二回合結束。 因為沒有人被拒絕，演算法到此結束，最終配對為：

{Alex, Daisy} 、{Bob, Emma} 、{Charles, Fiona}

從偏好表格來看大家配對到自己的第幾順位，表格顯示如下，配對到的人以粗體字表示：

接著，我們轉變情境，讓女生提出邀約，我們來看看結果會不會有所不同。第一回合，Daisy和Emma 邀請Alex，Fiona邀請 Bob，此時，因為Alex喜歡 Daisy 勝過 Emma，Alex 會暫時接受 Fiona的邀約，拒絕 Emma；而Bob會暫時接受Fiona的邀約，第一回合結束。 第二回合，只有Emma沒有暫時配對到任何人，所以她會轉而邀約Charles。此時Charles喜歡Emma勝過單身，所以Charles會暫時接受Emma。同時Daisy跟Alex暫時配對成功、Fiona跟Bob暫時配對成功，第二回合結束。 因為沒有人被拒絕，演算法到此結束，最終配對為：

{Alex, Daisy} 、{Bob, Fiona} 、{Charles, Emma}

我們再從偏好表格來看大家配對到自己的第幾順位，表格顯示如下，配對到的人以粗體字表示：

有了配對結果後，我們就可以來討論延遲遞移演算法有沒有辦法達到上文所述的三大目標。

穩定配對 (Stable Matching)

這兩組配對是不是穩定配對 (Stable matching) 呢？穩定配對的意思是說沒有辦法找到一組配對讓這組人都配到更想要的人。我們舉男生邀約配對的例子，此時Alex跟Bob都已經配對到最想要的人了，所以不可能再配對到更想要的人；而Charles如果去嘗試跟Daisy配對，Daisy也不會答應他。Emma和Fiona雖然都配對到最不喜歡的人，可是他們也沒辦法去邀約比較喜歡的人，因為那些人不會答應他們。因此，延遲遞移演算法給出的這兩種配對都能達成穩定配對的要求。

而男生邀約的配對結果會是男生最佳結果 (Men optimal stable matching) 、女生邀約的配對結果是女生最佳結果 (Women optimal stable matching) 。我們可以發現主動邀約的那方可以得到對那方最適的結果，然而被動接受方雖然配對到的對象還是穩定的，但是會有另外的穩定配對能夠給被動接受方更好的結果。用上述的例子來看，男生邀約的配對能夠讓三位男生都配對到對他們來說最好的選擇，而這個結果對女生來說儘管配對是穩定的，但是有不同的配對方式可以讓 Emma 跟 Fiona 都配到更喜歡的人，所以這個配對是男生最佳結果，同時也是女生最差結果。女生邀約配對就會是相反的情況，所以提出邀約的那一方會有主動的優勢，達到對主動方最適的結果。

效率 (Pareto Efficient)

那我們找出的配對有沒有效率 (Pareto Efficient) 呢？效率在這邊的意思是：我們能夠找到某兩組配對交換以後，讓每個人的滿足程度不降低，並且其中有人的滿足程度會提升。以女生邀約配對為例，由於此時 Daisy 和 Fiona 都已經配對到最喜歡的人了，所以沒辦法找到一種配對讓他們配到更喜歡的人，且 Emma 也不能配對到 Alex； Bob 跟 Charles 雖然可以互換女伴來得到更高的滿足程度，可是他們互換會降低 Emma 跟 Fiona 的效用，不符合效率的精神，所以配對方式是有效率的。男生邀約配對也會導出一樣是有效率的結果喔！所以，延遲遞移演算法在這個框架下是有效率的。

但是要注意！如果我們今天關心的是單邊有沒有效率的時候，延遲遞移演算法儘管可以找出男方最佳配對結果，但這個結果不一定是男生最有效率的結果喔。這個例子可以在第三篇參考文獻中找到，有興趣的人可以看第三篇參考文獻的Theorem 5。

誠實公布個人偏好 (Truthful-telling)

延遲遞移演算法有沒有辦法讓大家都說實話 (truthful-telling) 呢？先說結論，很抱歉，沒辦法！我們以男生邀約配對為例，此時因為配對結果是男生最佳配對，沒有男生沒有意願說謊，但是我可以找到一個女生謊報偏好來讓她配到更高順位的人選。如果 Emma 謊報偏好為：喜歡 Alex 勝過 Charles 勝過單身，其他人的偏好都不變的情況下，我們做延遲遞移演算法得到的結果會變成 {Alex, Daisy} 、{Bob, Fiona} 、{Charles, Emma}。此時 Emma 藉由謊報偏好來配對到優於 Bob 的選擇，所以 Emma 有謊報偏好的誘因。在女生邀約配對的情況中，我們也可以找到存在至少一個男生有謊報偏好的誘因。因此，延遲遞移演算法只能保證一邊的人會說實話，沒辦法同時讓兩邊的人說實話。

雖然延遲遞移演算法達到了穩定配對的良好性質，但是他沒辦法做到讓兩方都說實話，事實上，Alvin Roth 在1982年就證明了不存在任何穩定配對機制方法可以讓兩方都說實話 (Alvin Roth 1982)。但是如果我們能夠保證一方不說謊，那延遲遞移方法就可以同時達到穩定配對和說實話。而這樣的例子其實是存在的，大家可以想像選擇學校的情境，學校的偏好通常會被政府要求要滿足一些特定的條件，而這些條件能夠確保學校不謊報偏好。舉例來說，如果學校以成績高低為標準，那他就不能謊報說他喜歡某位成績比較低的學生，勝過另一位成績高於他的學生。

如果捨棄掉穩定配對的話，我們也可以找到滿足效率跟說實話的配對機制，其中最有名的是最佳交易循環 (Top Trading Cycle)。現正研究中的配對機制通常是以這兩種配對機制為基礎去變形出來的，所以相信各位讀者學會這兩種配對機制後，對於配對理論的研究會有初步的了解。然而究竟 Top Trading Cycle 是什麼？請待下回分解。

參考資料

最後附上四篇相關的文獻，有興趣的讀者可以參考：

• Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
• Roth, A. E. (1982). The economics of matching: Stability and incentives. Mathematics of operations research, 7(4), 617-628.
• Roth, A. E. (2008). Deferred acceptance algorithms: History, theory, practice, and open questions. international Journal of game Theory, 36(3-4), 537-569.
• [Shapley, A. R. L., & Roth, A. (2012). Stable matching: Theory, evidence, and practical design.](http://www. nobelprize. org/nobel _ prizes/economic-sciences/laureates/2012/popular-economicsciences2012. pdf)

來點習題吧！

如果你還想練習看看怎麼操作延遲遞移演算法，可以試試看以下的例子。

在這個偏好組合下，不管是由男生邀請或是女生邀請，最後使用延遲遞迴演算法所得出的配對結果都是：

{Alex, Daisy} 、{Bob, Fiona} 、{Charles, Emma}

這也告訴我們，確實是有可能得出同時是雙邊最佳的穩定配對。事實上，這也是這組偏好下唯一的一個穩定配對。你能直覺說出為什麼嗎？