大學錄取與婚姻的穩定性
一種沒有哪一對會雙雙背離的匹配——而且總有簡單演算法能找到它。
把一屋子人兩兩配對，配到沒有哪一對「私下裡」會雙雙甩掉各自的夥伴去投奔對方——蓋爾與夏普利證明：你總能做到。
核心思想
設想把人兩兩配對——求職者配雇主，學生配學校，伴侶配伴侶。一種配對是「穩定」的，是說不存在這樣兩個人：他們沒被配在一起，卻都更想在一起；沒有哪一樁誘惑強到能把它掀翻。1962 年，兩位數學家大衛·蓋爾與勞埃德·夏普利證明：無論眾人的偏好多麼糾纏，這樣一種穩定的安排總歸存在——而且他們給出了一套簡單的方法來找到它。
它是怎麼來的
蓋爾與夏普利把這篇七頁論文寫給一本教學期刊，並把它包裝成「穩定婚姻問題」：n 個男、n 個女，各執一份排好序的心願單。他們的方法，是一場分輪進行的「求偶」。人人向自己的最愛提議；接收的每一方，把目前最好的提議先攥在手裡，回絕其餘；被回絕者下一輪再試，往下降一個名次。誰都不會被永久卡住——接收的一方不斷「往上換」——而當音樂停下，便落在一個穩定匹配上。
他們當時並不知道：美國一家為新醫生安排去向的清算機構，早在十年前就已撞上了本質相同的程序，卻從未證明過它行得通。蓋爾與夏普利，補上了這套做法一直欠缺的那個證明。
它為什麼重要
這個結果是說：一種公平而可持續的安排，不只是一種指望，而是一種保證——並且可由一套既快又「誠實」的程序達成。幾十年後，經濟學家阿爾文·羅斯用它重新設計了：美國醫生如何被匹配到醫院的住院崗位、某些大城市的孩子如何被分配到公立學校、活體腎臟捐獻者又如何與患者兩兩接上。夏普利與羅斯憑此共享了 2012 年諾貝爾經濟學獎；蓋爾已於 2008 年去世，無法被列名。
一個日常畫面
把它想成一場「講禮貌的搶椅子」。每一輪，你走向自己最中意的椅子；坐在那兒的人把你和自己比一比，留下更合適的那個，輕輕把另一個推去繼續找。由於一把椅子只會把坐著的人換成它更喜歡的人，這遊戲不可能無限打轉——而當它結束，沒有哪兩個人會雙雙想要交換座位。有一個小機關，下方的小工具會讓你看見：走來走去的那一方，得的是更好的交易。提議者，最終得到他在穩定匹配中所能得到的最好夥伴；被提議者，得到的卻是最差的那個。
它在知識譜系中的位置
這篇論文落在本館的博弈論一脈，與馮·諾依曼和摩根斯坦（1944）、約翰·納什（1950）、肯尼斯·阿羅（1951）並肩。阿羅剛剛證明了一條著名的「不可能」——沒有任何投票規則，能把眾人的偏好公平地提煉成單一的社會排序。蓋爾與夏普利則報以一條「可能」：另一個更謙遜的目標——一個穩定匹配——總能達成，而且可以手工搭出來。兩相對讀，它們勾出了一條界線：哪些集體安排我們能夠保證，哪些不能。
There always exists a stable set of marriages.
any argument which is carried out with sufficient precision is mathematical, and the reason that your friends and ours cannot understand mathematics is not because they have no head for figures, but because they are unable to achieve the degree of concentration required to follow a moderately involved sequence of inferences.