配對理論：從穩定婚姻到諾貝爾獎的數學之旅

每年九月，數十萬高中畢業生透過聯合分發系統進入大學；每年三月，數萬名醫學院畢業生透過全國住院醫師配對計畫（NRMP）進入教學醫院；在美國，每年有數千名腎臟衰竭患者透過腎臟交換計畫獲得新生。這些看似迥異的制度，背後卻有著共同的數學基礎——穩定配對理論（Stable Matching Theory）。這個始於 1962 年的數學問題，最終在 2012 年獲得諾貝爾經濟學獎的肯定，成為數學如何改善社會制度最優雅的典範。

一、穩定婚姻問題：當「跳槽」成為威脅

1962 年，美國數學家 David Gale 與 Lloyd Shapley 在《美國數學月刊》發表了一篇僅 9 頁的論文，標題是「大學入學與婚姻穩定性」（College Admissions and the Stability of Marriage）。這篇看似不起眼的論文，卻開創了整個配對理論領域。^[1]

他們提出的問題極為簡潔：假設有 n 位男士和 n 位女士，每個人對異性都有一個偏好排序（從最喜歡到最不喜歡）。我們的任務是將所有人配成 n 對，使得配對結果是「穩定」的。但什麼是「穩定」？

定義：一個配對是不穩定（unstable）的，若且唯若存在一對男女（比如小明和小美），他們沒有被配在一起，但雙方都寧願拋棄現在的伴侶、轉而與對方在一起。這樣的一對稱為「阻塞對」（blocking pair）。一個穩定配對就是不存在任何阻塞對的配對。

用白話來說，穩定配對意味著：沒有人可以「跳槽」到更好的對象，因為那個更好的對象不會接受他們。這聽起來像是一種「各安其位」的社會秩序——每個人都可能沒有配到最愛的對象，但至少不會有一對私奔者破壞整個系統。

Gale 和 Shapley 提出了一個關鍵問題：穩定配對是否總是存在？ 他們不僅證明了答案是肯定的，還給出了一個優雅的演算法來找到它。

二、延遲接受演算法：數學的優雅

Gale-Shapley 演算法，也稱為「延遲接受演算法」（Deferred Acceptance Algorithm），是配對理論的核心。它的運作方式如下：

男方求婚版本

1. 第一輪：每位男士向自己偏好名單上排名最高的女士求婚。
2. 每位女士審視所有向她求婚的男士，暫時「保留」她最喜歡的那位（但尚未最終接受），拒絕其他人。
3. 後續輪次：被拒絕的男士向偏好名單上的下一位女士求婚。女士可以「升級」——如果新的求婚者比她目前保留的更好，她就拋棄原本保留的，改為保留新的。
4. 終止：當所有男士都已配對（或已被所有女士拒絕）時，演算法終止，此時每位女士最終接受她保留的對象。

這個演算法之所以稱為「延遲接受」，是因為女士從不立即接受求婚，而是保持選項開放，等待可能更好的對象出現。這種「貨比三家」的策略，正是演算法能夠達成穩定配對的關鍵。

存在性證明

為什麼這個演算法總能產生穩定配對？證明的核心在於反證法：

假設最終配對中存在一個阻塞對（小明，小美），即小明和小美都寧願與對方在一起。這意味著：

• 小明更喜歡小美，勝過他最終配到的對象。
• 小美更喜歡小明，勝過她最終配到的對象。

但根據演算法，小明在求婚過程中一定曾向小美求過婚（因為他會按偏好順序求婚，而他更喜歡小美）。既然小明曾向小美求婚，為什麼小美最終沒有選擇他？只有兩種可能：

1. 小美當時拒絕了小明，因為她保留了一個更好的對象。
2. 小美後來「升級」，拋棄了小明，因為出現了更好的人選。

無論哪種情況，小美最終配到的對象都比小明好（因為女士只會升級，不會降級）。這與「小美更喜歡小明」矛盾。因此，阻塞對不可能存在，配對必然穩定。^[2]

男方最優 vs 女方最優

這裡有一個關鍵的不對稱性：當男方求婚時，演算法產生的穩定配對是男方最優（man-optimal）的，意即每位男士都得到他在所有穩定配對中可能得到的最佳結果。同時，這個配對也是女方最劣（woman-pessimal）的。

反之，如果讓女士求婚、男士保留，則結果是女方最優、男方最劣。這個發現揭示了一個深刻的事實：演算法的設計選擇隱含著權力的分配。誰來求婚、誰來等待，決定了誰是贏家。這不僅是數學定理，更是市場設計的政治經濟學。^[3]

三、兩位數學家的故事

David Gale（1921–2008）是柏克萊加州大學的數學家，以博弈論和線性規劃聞名。Lloyd Shapley（1923–2016）則是加州大學洛杉磯分校的數學家與經濟學家，被公認為博弈論的奠基人之一。

兩人的合作始於一個簡單的問題：大學入學制度能否設計得更公平？當時美國的大學招生混亂無序——學校發出錄取通知的時間不一，學生被迫在沒有完整資訊下做出決定，結果是大量的「反悔」與「毀約」。Gale 和 Shapley 意識到，這本質上是一個配對問題。

有趣的是，這篇論文的題目雖然提到「大學入學」，但全文幾乎都在討論「婚姻穩定性」。這是 Shapley 的風格——他喜歡用簡單的隱喻來闡述深刻的數學結構。「穩定婚姻」這個名稱從此成為這個領域的標誌。^[4]

Shapley 的另一項重大貢獻是「Shapley 值」（Shapley Value）——一種公平分配合作博弈收益的方法。如果說穩定配對解決的是「如何匹配」，Shapley 值解決的是「如何分錢」。這兩項工作共同奠定了現代市場設計的數學基礎。

四、Alvin Roth：從理論到實踐的橋樑

如果說 Gale 和 Shapley 創造了理論，那麼 Alvin Roth 就是將理論帶入現實世界的人。Roth 是哈佛大學（現為史丹佛大學）的經濟學家，他的貢獻在於：發現現實世界中許多看似無關的制度，其實都是配對問題，而且可以用 Gale-Shapley 框架來分析與改進。

美國住院醫師配對系統（NRMP）

Roth 最著名的發現之一，是關於美國住院醫師配對系統的研究。1950 年代，美國醫學教育面臨嚴重問題：醫學院學生畢業前就被各醫院搶先錄取，有些甚至在大二就收到 offer。這種「提前錄取競賽」導致雙方都沒有足夠資訊做出好的決定，怨聲載道。

1952 年，全國住院醫師配對計畫（National Resident Matching Program, NRMP）成立，採用了一種集中配對機制。令人驚訝的是，Roth 在 1984 年證明，NRMP 所使用的演算法本質上就是 Gale-Shapley 演算法的變體——儘管 NRMP 的設計者並不知道 Gale-Shapley 的論文！這是獨立發現的精彩案例。^[5]

然而，Roth 也發現了 NRMP 的問題：原始設計是「醫院求婚」版本，這意味著結果對醫院最優、對學生最劣。1990 年代，Roth 重新設計了 NRMP，改為「學生求婚」版本，使結果對學生更有利。這項改革至今仍在運作，每年配對超過 4 萬名住院醫師。^[6]

紐約市高中入學系統

2003 年，Roth 受邀重新設計紐約市高中入學系統。原本的制度是「混亂市場」：學生只能申請 5 所學校，學校可以策略性地優先錄取「把本校列為第一志願」的學生。結果是：超過 3 萬名學生每年被分配到沒有申請的學校。

Roth 的團隊引入了延遲接受演算法，讓學生可以列出最多 12 個志願（後來放寬為無限制），學校不再知道自己是學生的第幾志願。這個設計有兩個關鍵優點：

1. 策略防禦性（strategy-proofness）：學生不需要策略性地隱藏真實偏好，誠實報告就是最佳策略。
2. 穩定性：不存在學生和學校雙方都想「跳槽」的情況。

改革後，未被配對到任何志願的學生從 3 萬人降至約 3 千人。這是市場設計改善公共政策的經典案例。^[7]

腎臟交換配對

Roth 最具人道主義意義的貢獻，或許是腎臟交換計畫。假設 Alice 願意捐腎給她的丈夫 Bob，但血型不合。同時，Carol 願意捐腎給她的兄弟 Dan，但也血型不合。如果 Alice 的腎與 Dan 相容，Carol 的腎與 Bob 相容，他們就可以「交換」——Alice 捐給 Dan，Carol 捐給 Bob，四個人都獲益。

Roth 與他的合作者設計了一套演算法，能夠在全國範圍內尋找這樣的「交換鏈」。這不是標準的穩定配對問題（因為腎臟交換涉及「同時性」約束——所有手術必須同時進行，否則有人可能反悔），但 Roth 創造性地調整了理論框架來解決這個問題。

至今，這套系統已經挽救了數千條生命。這或許是數學最直接拯救生命的例子之一。^[8]

五、2012 年諾貝爾經濟學獎

2012 年，瑞典皇家科學院將諾貝爾經濟學獎頒給了 Lloyd Shapley 和 Alvin Roth，表彰他們「在穩定配對理論與市場設計實踐的貢獻」。這是配對理論的最高榮譽，也是「市場設計」（Market Design）這個新興領域的正式確立。^[9]

頒獎詞特別強調了這項研究的獨特之處：它不是關於傳統的價格市場，而是關於「沒有價格的市場」。在大學入學、住院醫師配對、器官捐贈這些場景中，我們不能用金錢來買賣位置或器官（這既不道德也違法）。但配對問題依然存在，而且同樣需要有效的機制來解決。Gale-Shapley 框架提供了這樣的工具。

值得一提的是，David Gale 於 2008 年去世，未能見證這一榮譽。諾貝爾獎不頒給已故者，但所有人都承認他的開創性貢獻。

六、數學的深度：三個定理

對於想要深入理解配對理論的讀者，以下是三個核心定理：

定理一：穩定配對的存在性

定理：對於任意有限的雙邊配對問題，穩定配對總是存在。

證明：Gale-Shapley 演算法在有限步驟內終止，且產生穩定配對（如前所述）。由於演算法是構造性的，這同時證明了存在性。

定理二：求婚方最優性

定理：延遲接受演算法（求婚方為男方）產生的配對，是所有穩定配對中對每位男士最優的；同時，它也是所有穩定配對中對每位女士最劣的。

這個定理的意涵是：穩定配對不唯一（通常有很多個），但延遲接受演算法會選出其中對求婚方最有利的那一個。^[10]

定理三：策略防禦性

定理：在延遲接受演算法中，對求婚方而言，誠實報告偏好是佔優策略（dominant strategy）。也就是說，無論其他人如何報告，求婚方都沒有動機謊報自己的偏好。

這是市場設計的黃金標準：一個好的機制應該讓參與者不需要「玩遊戲」，誠實就是最佳策略。然而，這個定理有一個重要的但書：接受方沒有策略防禦性。女士有時可以透過策略性地修改偏好清單來獲得更好的結果，這也是為什麼現實中的配對系統設計需要小心處理。^[11]

七、延伸議題：超越一對一配對

現實世界的配對問題往往比「穩定婚姻」更複雜。以下是幾個重要的延伸：

多對一配對：學校招生

在大學招生中，一所學校可以錄取多名學生，但每位學生只能進入一所學校。這是「多對一配對」（many-to-one matching）問題。Gale-Shapley 演算法可以直接推廣：我們只需讓每所學校有一個「配額」（quota），在演算法中保留最多該數量的申請者。穩定性的定義相應調整為：沒有學生和學校雙方都想「交換」現有配對。

帶有配偶的配對

住院醫師配對的一個特殊問題是「情侶配對」：兩位醫學生是夫妻，希望被分配到同一城市的醫院。這大大增加了問題的複雜性，甚至可能導致穩定配對不存在。Roth 和他的同事發展了專門處理這種情況的演算法，但必須接受「近似穩定」而非完美穩定。^[12]

腎臟交換的特殊性

腎臟交換不是標準的雙邊配對，而是涉及「交換環」（exchange cycles）。一個 3-way 交換意味著三對捐贈者-受贈者同時交換；更長的鏈條可以幫助更多人，但手術的同時性要求也更難滿足。Roth 的創新之一是引入「非指定捐贈者」（non-directed donor）——一位願意無私捐腎的陌生人——作為交換鏈的起點，大幅增加了配對的可能性。

八、台灣的應用與啟示

台灣的大學聯合分發制度，本質上也是一個配對問題。現行制度採用的是「學生優先」的志願序分發（類似於延遲接受的學生求婚版本），這對學生相對有利。然而，台灣制度有其特殊性：

• 考試成績作為唯一排序標準：不同於美國的多元審查，台灣傳統上以考試成績決定錄取，這簡化了學校的「偏好」，但也犧牲了其他考量。
• 繁星推薦與個人申請：這些管道引入了更多「雙邊選擇」的元素，更接近 Gale-Shapley 框架。
• 策略性行為：學生在填寫志願時仍存在策略性考量（例如「落點分析」），這表明制度尚未達到完全的策略防禦性。

從配對理論的視角，台灣的升學制度仍有改進空間——特別是在讓學生能夠更誠實地表達偏好、減少「賭志願」的焦慮方面。

九、結語：數學如何改善社會制度

配對理論的故事，是數學與社會科學完美結合的典範。一個 1962 年的純數學問題，經過數十年的發展，最終改變了數百萬人的人生軌跡——從進入夢想的學校，到獲得救命的器官。

這個故事給我們幾個深刻的啟示：

1. 好的制度設計可以減少「內卷」：當規則清晰、誠實報告是最佳策略時，參與者不需要花費精力在「遊戲規則」上，可以專注於真正重要的事。
2. 數學不只是計算，更是設計工具：Gale-Shapley 演算法不只是解決問題，它還告訴我們哪些問題是可解的、解有哪些性質、設計選擇會帶來哪些後果。
3. 理論與實踐的橋樑需要有人去搭建：Shapley 創造了理論，Roth 將它帶入現實。學術研究的價值，往往要透過這樣的「轉譯者」才能實現。

回顧這段歷史，最令人感動的或許是：當我們精心設計制度時，數學可以成為正義的工具。在沒有價格的市場中，穩定配對提供了一種公平——每個人都得到他們在這個系統中所能得到的最好結果，沒有人會被不公平地拋下。

這正是「市場設計」這個領域的核心信念：我們不必被動接受現有的制度，我們可以用數學與經濟學的工具，設計出更好的遊戲規則。