----- 郵件 -----
日期: Sun, 07 Dec 2014 23:17:10 +0800
寄件人: Kun-Mao Chao
主旨: Matching Problem
收件人: ACB Matchers
Dear Matchers,
Here's a report that you might be interested in.
http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html?action=click&pgtype=Homepage®ion=CColumn&module=MostEmailed&version=Full&src=me&WT.nav=MostEmailed&_r=0
紐約市的高中入學比較像stable marriage problem，是雙向的。我們的十二年國教比較像popular matching
problem，是單向的。這說法不精準，聽聽就好。
只是在論文之外，也希望你們能看到一些活生生的例子。
Later,
Kun-Mao
----- 轉寄的郵件 -----
日期: Mon, 08 Dec 2014 11:09:17 +0800
寄件人: Yen-Wei Wu
主旨: Re: matching problem
收件人: Kun-Mao Chao
摘要及補充幾個數字
(1) 1960年代早期，stable marriage problem的解法被提出 (David Gale and Lloyd Shapley)
(2) 1995年，一般化許可polygamous後，又稱hospitals/residents problem，首度在現實生活中應用於National
Resident Matching Program (Alvin Roth)
1999年發表的演算法內容 (精神與1960年代的解法相符)
http://kuznets.fas.harvard.edu/~aroth/papers/rothperansonaer.PDF
(3) 2004年，紐約市開始在高中入學方案中採納這種做法，有效將配對落榜學生人數從過往的31,000，降到約3,000。
(4) 2012年，Lloyd Shapley及Alvin Roth共獲諾貝爾經濟學獎，表彰他們在理論及應用上的貢獻。
(5) 今年的紐約市高中入學配對方案，共服務75,000的學生，426所學校，每位學生的preference list長度至多12。以簡化版問題為linear
time solvable看起來，程式應當不需要執行太久。
A video of stable matching algorithm
https://www.youtube.com/watch?v=w1leqkpDaRw
A study of stable marriage problem (加拿大、蘇格蘭、日本也採用類似的醫學生實習系統)
http://148.204.64.201/paginas%20anexas/ALGORITMICA/papers/preg1/scfu_21_paper.pdf
A paper discussing how hard to cheat in stable matching algorithm
http://cs.dartmouth.edu/reports/TR2005-565.pdf
A practcal research: Hospitals/Residents problem with couples
http://www.dcs.gla.ac.uk/publications/PAPERS/8905/hrs.pdf