凌帠的管理世界

你真的以為各級學校聯招，統一分發是公正合理的；證券市場集中交易，電腦撮合是及時公平的；交友網站電腦擇友，配對的都是你的最愛？別傻了，否則怎會發生高分落榜的情形，又怎會發生以毫秒為單位的高頻交易，從跨交易所的股市中賺取價差。在這些看似簡單的配對交易中，背後其實隱藏了許多複雜多變的規則。令人訝異的是，想出一套解決這些配對難題的方法，竟可以得到諾貝爾獎，這可就稀奇了。

國中會考昨天放榜，教育部表示有6成的學生順利上第一志願，但聽在家長耳裡很不是滋味，因為家長認為大家怕被志願序被扣分，所以填順序都變得很保守，填得志願都不是原本心目中的排名，甚至有學生考了5A作文5級分，填了50個志願，但最後卻落得沒學校可念，家長痛批這叫15歲孩子情何以堪，決定下午上凱道抗議，幫孩子討公道。2014/06/21《TVBS新聞》

聯考放榜是一種配對的市場，一邊幫學校找到最優秀的學生，也同時一邊幫學生找到理想的學校。在這個社會上，不但求學要配對、比賽要配對、戀愛要配對、求職要配對、投資要配對、換腎要配對，幾乎人生中的所有重要里程碑都要靠配對。而配對要成功，必須要妳情我願，要我選妳，妳也選我才能配對。若我是妳的最愛，妳也是我的最愛，則天造地設；若妳不是我的最愛、我也不是妳的最愛，有時也能勉強湊合。

要做好配對並不容易，每所學校想招的學生各不相同，每位學生喜歡的學校也各自不同。要是放任雙方自行配對，最後必然怨氣沖天，多數無法達成心中的願望，但若改成集中配對（聯招），要是規則弄不好，也同樣是哀鴻遍野，情況好不到哪裡去。但是，只要能設計出一套好的配對方法，就有機會解決這影響人一生發展的重大問題。

獨立招生問題多

不知大家是否想過，既然高中、大學都已採聯招，那為何研究所不採聯招呢？

小張大學畢業後打算更上層樓，所以決定要考企管研究所。各校企研所的考試時間由各校自行決定，所以偶會發生衝堂考的狀況。要是衝堂的兩所學校都是自己很想就讀的，那麼取捨就成了一個頭痛的問題。就是萬一捨了A學校，結果發現考題都是自己的強項；若是選了B學校，考的卻都是自己不會的，這不是倒楣透了。只是，又有誰能早知道呢！

好吧！反正也無法事先知道，無論如何，總要做出取捨，小張最後終於決定了要考的學校後，很快的就開始了這趟考試之旅。

在這一連串的考試過程中，發生了一個有趣的事情，就是小張發現到，每到一所學校後，就會發現來考的人好像都似曾相似。乖乖，大家還真是有志一同啊！想考的學校都一樣，所以沒過幾天大家就會見面一次。剛開始小張還覺得頗感親切，但仔細一想後卻大感不妙，心想這下可糟糕了，本以為考上的機率還不小，但這下子恐怕是機會渺茫了。

怎會一下子差那麼大？因為每家研究所錄取的人數都不多，假設有5所學校，每校都錄取20人，所以總共可以錄取100人，也就是只要考到前100名就可以了，但仔細一想，卻完全不是這麼回事。

同一批人考同樣多的學校，會發生的結果有可能是，程度在前20名的人可能考取每所學校，而20名外的人，則可能全部都槓龜，而不是原來想的前100名的人會考取學校。當然這是極端的狀況，但是，一定有不少人考取多所學校，把名額都佔掉了，但是到了最後卻只能選一所學校就讀，就可能造成某些學校招生不足。

這點各校都很有經驗，所以會有備取名額，那要備取多少人呢？這就要憑經驗了，只是經驗經常不準就是了。

有備取還不夠，各校報到的時間也各不相同，就會導致是否該等待的問題。就像同時面試5家公司，若非自己心中首選的公司先通知你錄取，但要求你要在一星期內回覆是否報到，可是這時自己最中意的公司卻遲遲未通知是否錄取。這時就面臨要決定，到底是一鳥在手勝過十鳥在林呢？還是該堅持最愛，放棄到手的戰績。

萬一堅持所愛，最後卻落得一場空時，該怎麼辦？生活中常會發生這種令人討厭的情況，例如：眼前的男朋友不夠好，是否下一個男人會更好，但又怕石頭愈撿愈小；快到目的地想找停車位，看到一個距離較遠的停車位，是要停還是不要停；路旁半生熟的芒果該採不該採，先採了怕太生不能吃，晚採了又怕被別人捷足先登，自己就什麼都沒有。

事實上，每所學校確認報到的時間不同，開出備取的時間也不同，而且即使是備取，也要看排名前面的備取是否會報到，否則也未必輪得到。每個人的每個決定都要視別人的決定而定，這可該怎麼決定，沒辦法，最後只好聽天由命。所以最後的結果就是幾家歡樂幾家愁，有的學校可能招生不足，有些成績好的學生最後卻無校可讀，這就是缺乏一個集中配對市場的結果。

市場設計

要讓社會資源得到充分的利用，各取所需、各得其利，就需要創造一個有完善交易（配對）規則的市場，這可是非常的不容易。而配對市場事實上是無所不在，常見的聯招是配對市場，其他如股票交易、企業招募、婚姻、換腎、網拍、競標……，甚至是目前最熱門的Uber、Airbnb等等都是配對市場，其實買賣本身就是一種配對。

要建立一個完善的市場，首先要有一個集中交易的地方，以及規定的交易時間，還要有高度參與的成員，不可以有私下配對的情事，交易要能確保安全，市場的規律不得靠成員的自律來維持，也不能發生堵塞的狀況阻礙配對，否則就會發生市場失靈的狀況，嚴重的話，整個市場還可能就此瓦解。

在《創造金錢買不到的機會》一書中，作者艾文‧羅斯將此稱之為「市場設計」，作者本身就是市場設計的專家，也是諾貝爾經濟獎得主及史丹佛大學經濟學教授，曾發明羅斯—卜蘭森演算法，用以解決複雜的市場設計問題。

作者曾經實際設計改善了許多市場規則。例如：腎臟移植交換市場，讓原本只能直接配對的腎臟移植，改成循環式、連鎖式的配對方式，使得配對成功的數量擴大了數倍，造福許多洗腎患者；也改善了美國全國住院醫師配對計畫，協助全美幾十萬名醫師在幾千個住院實習計畫找到工作，更特別的是，有許多申請的醫師是夫妻檔，為了滿足夫妻檔對於區域的特殊要求，作者開發了特殊方法，稱之為羅斯—卜蘭森演算法，可以依照夫妻倆人共同決定的喜好順序排列，同時解決的夫妻醫師配對的問題；作者也曾幫紐約及波士頓高中招生重新設計配對規則，因為有些學校會給予住在學校附近或已有哥哥、姊姊就讀的學生優先權，新的演算法也能滿足這類特殊需求。

延遲接受演算法

市場設計並非由本書作者所首創，市場配對穩定性的概念最早是由大衛‧蓋爾和羅伊德‧夏普利在1962年在《大學招生及婚姻穩定性》這篇文章中所提出的，他們設計了一個演算法來尋找穩定配對，並將之稱為「延遲接受演算法」。羅伊德‧夏普利是賽局理論開山始祖之一，他寫過許多論文開創這個領域，但這一篇贏得2012年諾貝爾經濟學獎。

講起演算法，聽起來就令人肅然起敬、退避三舍，搞不清楚到底是個什麼東東，反正必非凡人能理解就是了。但這個配對演算法卻非常簡單易懂，簡單到用邏輯思考，簡單幾個步驟，不需繁複的數學運算大家就能了解，我們趕緊來看看這個「延遲接受演算法」到底長怎麼樣子。

假設場景為應徵者與雇主間的配對。

■      步驟0：應徵者和雇主向交換所遞交私密的志願表，按喜好順序排列。

■      步驟1：每個雇主向它的首選候選人提出工作合約，合約數量最多是所有工作職缺數。每名應徵者檢視自己收到的所有合約，暫時接受最好的一個。

■      步驟n：每個雇主將前個步驟被拒絕的工作合約轉而向下一個選擇的應徵者提出，而每位應徵者綜合考量自己保留的合約和新收到的合約，暫時接受最喜歡的一個，並拒絕其他合約。

■      當沒有合約被拒絕，因此沒有公司想提出更多合約時，演算法結束。

演算法實作

好吧！雖然演算法看起來很簡單，但只是文字敘述，看起來還是太抽象了些，以下我試著舉個最簡單的例子來實作這個演算法，這樣大家應該就更容易明白了。

假設有26名學生（A~Z）要申請甲、乙、丙三所學校，學生遞交志願表，每個人可填寫最多三個志願，各校一律依照聯考成績高低來錄取，並無特別加分項目。

基本資料如下：

<各校錄取名額>

<學生分數>

<學生志願表>

配對方式依據「延遲接受演算法」的邏輯，為求省事，我以T-SQL資料庫語言來實作此演算法，程式碼如下（若是程式碼看不懂沒關係，不重要！請跳過，直接看後面的說明）：

總共有四個資料表，其名稱與欄位說明如下：

■    School : SchoolID、SchoolName、Quota(錄取名額)

■    Student : StudentID、StudentName、Score、MatchPriority(分發時用來註記每位學生目前配對的志願)

■    Priority : StudentID、Priority、SchoolID

■    Match : Stop、SchoolID、StudentID、Priority、Score、ScoreRank

分發的方式是，首先每位學生都去申請自己第一志願的學校，而每個學校錄取申請者中分數最高的前幾位學生，錄取人數視各校的錄取名額而定，如：甲校5名、乙校4名、丙校6名。由第一輪的錄取名單中可以看到，丙校因為只有4位學生填第一志願，所以錄取未足額。

而這次的錄取只是暫時的，每位錄取的學生在下一輪分發時還要跟前次落榜的人比。

<第一輪錄取名單>

第二輪分發是以第一輪落榜者的第二志願，並加入第一輪的錄取者，來一同比較分數，同樣是高分者錄取。例如：學生H的第一志願是甲校，但因為分數93分過低在第一輪分發時落榜，但在第二輪的分發中，H的第二志願是乙校，乙校在第一輪錄取了B:99分、J:91分、K:90分、L:89分共四位，H與這四位以及其他與H相同在第二志願填寫乙校的人一起比分數，結果H位居第二名，所以第二輪H錄取了乙校，而原本第一輪錄取最低分的L則被踢掉，成為第二輪的落榜者，其餘類推。

<第二輪的錄取名單>

第三輪分發也是以第二輪的落榜者的下一個志願再加上第二輪錄取者一同比較分數。例如：在第二輪被H擠掉的L的下個志願是第二志願的丙校；第一第二輪皆落榜的Z的下個志願是第三志願的乙校。

L:89分在此輪申請丙校，並與丙校第二輪的六位錄取者（D:97分、I:92分、N:87分、O:86分、P:85分、R:83分）一併競爭，L分數比N、O、P、R高，也比在此輪志願同為丙校的其他人高，所以L在此輪錄取丙校，R因為分數最低所以在此輪被踢掉，成為落榜者。丙校在第三輪最後有兩名暫時錄取者P、R被擠掉，L、M則為新錄取者。

<第三輪錄取名單>

第四輪分發後因為每位落榜學生的每個志願都已配對過，已經沒有其他志願可以再進行配對，所以分發作業至此結束，最後一輪的分發結果就是最後的錄取名單。因為第四輪的分發結果與第三輪相同，在此就不重複列出。

求諸於外

「延遲接受演算法」只是最基本的配對演算法，真實世界中的情況千變萬化，面對這樣的情形就要適時地做出適當的調整，就如同本書作者依據延遲演算法，修正調整後開發出「羅斯—卜蘭森演算法」一樣。國內無論在聯招或是商業上，許多的配對市場都存在明顯的配對缺失，導致民眾天怒人怨，倒是可以多向專家請益，例如本書作者（向諾貝爾獎得主請益應該不丟臉吧），努力去建立一套完善的機制，才是全民之福。

書籍資料

■   書名：創造金錢買不到的機會—諾貝爾經濟學獎突破市場經濟賽局的思維

■   作者：艾文‧羅斯(Alvin E. Roth)

■   譯者：朱道凱

■   出版社：天下雜誌

■   出版日期：2016年10月5日

註：此篇應天下雜誌邀約，分享新書心得。