|
沙普利於1950及60年代提出「蓋爾—沙普利演算法」，解決不以價格分配資源時，如何達致配對穩定。
1.婚姻配對：
穩定配對意味沒夫婦會離婚。「蓋爾—沙普利演算法」提出「延後接納」原則，以數學證明算法能恆常達致分配穩定。
假設女士有抉擇權，每名女士均向首選的一位男士求婚，每名男士會選取最佳選項(如有)並拒絕其他女士(如有)；餘下女士再向次選求婚，如此類推，直至沒有女士願意求婚。若抉擇權在女士，配對結果較男士擁有抉擇權為佳；反之亦然。
2.醫生與醫院配對：
美國醫院在1940年代擁有抉擇權，醫院為爭奪數量稀少的醫科畢業生，紛紛提前數月甚至數年招攬。羅思在1984年發表論文，指1950年代面世的「全國駐院醫生配對系統(NRMP)」大獲成功，源於無意中採用「蓋爾—沙普利演算法」。
在NRMP下，醫生擁有抉擇權。醫科生收到聘書時，系統根據意願自動將他歸入首選，並拒絕其他職位，如此類推，直至每個學生獲工作。羅思1995年改善系統，兩年後獲NRMP應用。
3.學生與高中配對：
紐約市學生早年報讀公立高中時，須選出首5家心水中學，再由中學決定錄取、拒絕或排在候補名單。因兩方均無壓倒性抉擇權，導致每年近3萬名學生被派往未有選擇的中學。
羅思在2003年定出以申請人為本的派位系統，應用「蓋爾—沙普利演算法」後，獲派心水名單以外學府的學生大減9成。
4.腎臟與病人配對：
沙普利提出以「首選交換循環(Top Trading Cycle)」配對，作出第一輪分配後，容許資源不斷交換，直至配對穩定。但因器官與病人可能出現排斥反應，且多重交換耗時，增加配對難度。■瑞典皇家科學院網站/程序員網站
|
