如何用「延遲接受演算法」解決擇校問題？

11-26

讀到了這樣一篇文章
諾貝爾經濟學獎得主替紐約解決了高中擇校問題
查了下，這裡面提到的「延遲接受演算法」和大家提到了在戀愛中有哪些博弈？ - 戀愛心理中提到的「stable matching」好像是同一個演算法。能不能具體解釋下，如何可以用「延遲接受演算法」解決擇校問題？真實的應用情況是怎樣的？在中國有運用的可能性嗎？

謝 @Zampeli Diana 邀。基於目前已經有的回答，我爭取結合跟國內招生來談談。

1. 擇校問題和招生問題是同一個問題，主要包括中小學招生和大學招生。招生問題的基本模型是一個雙邊匹配模型：把學校的座位和學生一對一地匹配起來。學生對學校可以有不同的喜好（術語為偏好），學校對學生也一樣。不同國家不同招生問題可能還包括基本模型之外的考慮（例如少數民族照顧政策，平權法案等等），但基本框架都一樣。

2. 我們談演算法的時候談的是招生中的集中錄取機制。國內大學招生是集中錄取而中小學招生很大意義上不是（美國是反過來的），男女婚姻匹配在任何地方都不是。集中錄取（分配）指的是把學校和學生都集中到一起，雙方都只需要向錄取機構彙報自己的偏好，然後錄取機構跑一下演算法決定學生和學校怎麼匹配。非集中錄取的的典型例子有解放前後的大學錄取和申請美國研究生院：學生申請多所學校，學校根據自己偏好錄取一部分拒絕一部分學生，學生有多個offer 可以拒絕掉不會去的學校，這樣那些學校可以繼續給替補的學生髮offer。但通常學生不會輕易拒絕不要的offer （可能會拖上一個月）同時想等更好的，導致事實上每所學校能發的offer 輪次往往不過兩三輪。很多學生等不到心儀的學校而被迫接受差的，匹配效率很低。

3. 平行志願和志願優先機制。現在大部分省份高考招生用的是平行機制，該機制是Gale-Shapley 的延遲接受演算法（Deferred acceptance algorithm; DA）的一個簡單修改版。而直到十多年前，高考招生都用的是志願優先機制（文獻中稱作Boston Mechanism; Boston）。這兩個機制的最顯著區別在於前者不根據志願順序歧視考生，但後者絕對地歧視。

例子： 假定有兩所學校 $s_{1}$ 和 $s_{2}$ ，每所只招一個學生；假定有三個學生 $i, j, k$ ；用 $emptyset$ 代表社會大學。學生和學校的偏好以及平行志願和志願優先機制運算的過程如下：
（每個步驟描述的是學生申請學校和學校的接受/拒絕。看懂這兩個運算過程並且理解演算法的定義不需要額外的文字說明。如果把雙方理解為男人/女人，容易看出這是個多角戀關係。）

平行志願機制（DA）和志願優先機制（Boston）的差異從第二步開始，當 $k$ 被 $s_{1}$ 拒絕轉而以第二志願投檔到 $s_{2}$ 的時候。儘管 $k$ 比第一志願申請 $s_{2}$ 的 $i$ 在 $s_{2}$ 優先權更高，在志願優先機制下 $k$ 由於是第二志願申請而被歧視。

4. 錄取機制的優劣。不同的錄取機制有不同的性質，例如平行志願的結果是穩定的 (stable)，意思是不會有學生更想去某個大學而該大學卻錄取了比他分數低的人。而志願優先機制下，高分落榜的例子比比皆是（上例中的 $k$ ）。同時，平行志願下學生沒有「謊報」志願的激勵，而在志願優先的情形下，學生報志願需要非常小心地估計自己能考分夠上什麼學校，按照真實喜好順序填志願是很危險的。換言之，志願優先機制的最大缺點是帶給人的不安全感太高，填志願的時候學生很可能過度謹慎。平行志願機制本身的一個問題是其匹配結果對於學生可能不是帕累托最優的（上例中 $i$ 和 $k$ 交換學校兩個人都會變好），但這不會在高考招生中發生，因為國內大學對學生的偏好排序都是一樣的--高考分數越高就越好。

5. 國內高考招生和中小學招生改革。個人認為，高考錄取機制有兩個需要注意的地方：一，分批錄取會帶來一定的效率損失，應該整合（似乎正在朝這個方向做）；二，平行志願填報時候平行的個數可以適當放寬（當然，這是個實證問題）。更重要的是中小學招生改革，對此的實際操作我了解得很少，只能想當然地談一下。目前國內正在推行的是就近入學，這本身不是不合適，但簡單推行的結果是學生和家長的偏好基本沒有被考慮，相信有一部分效率損失可以通過設計得到改進。民辦學校的集中錄取和公辦民辦之間的協調也是值得考慮的問題。另一相關的問題是教師輪崗的機制設計。

最後，列一篇關於國內高考機制研究的參考文獻，作者之一是密歇根大學的Chen Yan 教授。該文在附錄里詳細回顧了中國高考改革的歷史。其他相關研究可參見該文的參考文獻。

References:

Chen Yan and Onur Kesten (2014), "Chinese College Admissions and School Choice Reforms: Theory and Experiments", working paper, University of Michigan.

這是同一個演算法。事實上deferred acceptance algorithm, 在1962年被Gale and Shapley從理論上提出的時候，論文的標題就叫"College Admissions and the Stability of Marriage". 由於婚姻匹配問題是簡單的一對一匹配問題，之後對deferred acceptance algorithm的許多研究就以婚姻匹配為背景。比如高德納於1976年用法文寫了一本書叫Mariages Stables, 總結了截至當時的結果。

2003年改革前，紐約公立高中招生採用的是這樣一種機制：每個申請者填寫自己最想進的五所高中作為第一至第五志願，他們的志願列表會發給學校，學校決定接收、拒絕還是放進waiting list. 這個過程重複三次，三輪過後仍未被錄取的學生接受統一分配，這時候就不看志願了，基本只看離家遠近。學校決定是否招收某個學生時，不僅要看學校對學生的偏好，也看學生把學校列在第幾志願。學校更喜歡招收把它列為第一志願的學生。

這篇文章（http://economics.mit.edu/files/3962）的附錄AII（從pdf的19頁開始）描述了改革後的招生機制。總體來說，它的核心就是一個簡單的由學生propose的deferred acceptance algorithm, 運作與戀愛中有哪些博弈？ - 戀愛心理中給的相同。大體上說，DA演算法的核心步驟如下：

第一步：每個學生向他最想去的學校申請。每個學校暫時接收所有申請者，學校最想要的那些學生，直至用完招生名額。並拒絕沒有被暫時接收的申請者；

第k(k&>=2)步：前一步被某一所學校拒絕的學生申請去所有尚沒有拒絕他的學校中，他最想去的那一所。每一所學校將這一步的申請者與以前暫時接收的學生放在一起，從中挑出最想要的學生，直至用完招生名額。並將其餘學生拒絕；

演算法停止於再沒有學生被拒絕。

要討論改革後的機制相對於原有機制有哪些優點，就要討論這樣一個two-sided matching問題裡面，評判機制好壞的幾個標準。

1. 穩定性(stability)：穩定性要求，演算法跑完之後得到的配置滿足個人理性（individual rationality, 舉例來說，男生得到的女朋友不能讓他覺得「還是單身好啊」），同時滿足不存在blocking pair（舉例來說，不存在兩對couple中的一男一女想見異思遷組成新家庭）。
紐約公立高中的招生舊機制是不穩定的。表現為有些學校不喜歡這個機制派給它的學生，所以寧可迴避掉這個機制。比如說，一個高中校長說，假設學校有100個招生名額，它寧可告訴當局他只要40個，等跑完三輪志願填報後再通過其他程序招完餘下名額。而對於deferred acceptance algorithm就比較簡單了，理論證明這個演算法必定生成穩定匹配。

2. 學生的福利(student welfare): Gale Shapley(1962)證明了一個非常有意思的結果：假設所有男女的偏好是嚴格的（不存在無差異的情形），由男生表白的deferred acceptance algorithm所生成的配置結果是在所有穩定匹配中，對於所有男生都最好的匹配；這個匹配同時也是在所有穩定匹配中，對於所有女生都最差的匹配。（這裡的「最好」和「最壞」都是指雙方申報的偏好而言。如果申報的偏好與真實的偏好不同，那麼產生的匹配有可能不是對於真實偏好最好或最壞的結果。）
招生匹配中，機制設計者的目的是找出對於學生來說最好的穩定匹配。公立學校的偏好一般是被政府抑制的，波士頓機制更甚，學校對於學生本身沒有偏好差異，只有政府外生給定的一些排序。比如說家離學校近的排在家離學校遠的前面，有兄弟姐妹在校的排在沒有兄弟姐妹在校的前面，等等。紐約學校對學生本身有偏好，也存在學業水平考試，政府同樣在新機制中壓抑了學校偏好的表達，比如說將學生學業成績粗略地分級排序。總而言之，此類機制的設計目的一般是最大化學生的福利，也就是說，挑選出對於學生來說最優（往往就是對於學校來說最差）的穩定匹配。
原有的機制在學生福利方面做得不夠好。有很大比例的學生最後是被分配到自己根本沒有填報過志願的學校去的。在改革後，被分配到未曾表達過志願的學校的學生數量下降了90%（http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/popular-economicsciences2012.pdf 第4頁）。
（必須指出DA機制理論上並不一定能產生對學生來說帕累托最優的匹配結果，除非對學生偏好和學校生源排序結構施加額外的假設。）

3. 學生說真話(students" strategy proofness) : 要求學生真實地表達自己的偏好是他們的佔優策略(dominant strategy)。舊機制下是不可能的，原因很簡單，既然學校招生看志願次序，學生就不敢把自己最喜歡，但希望渺茫的學校填在前面。而在新機制下，學生是會說真話的。原因不難理解：students proposing deferred acceptance algorithm產生的是對於所有學生來說，對於他們申報的偏好而言最好的穩定匹配，那麼當然申報真實的偏好最好。注意學生說真話不代表學校有說真話的動機，事實上有證明說不存在所有方面都說真話的穩定匹配。但由於學校的偏好表達被政府規制，學校說假話的機會也不太多。

謝邀。
由於以下內容將按照與題述的邏輯關聯程度論述，而非重要程度列出，因此首先貼出提綱，以便抓住重點。

1. 延遲接受演算法（或簡稱DA演算法）在一對多雙邊市場上的拓展，以及該拓展與一對一雙邊市場的相互關係；
2. 雙邊市場（婚姻市場）與單邊市場（房屋市場）的差異；
3. （重點）原本的模型：Boston Mechanism；
4. Boston Mechanism的相關性質；
5. （重點）進一步分析：Boston Mechanism 與 Deferred Acceptance Algorithm的聯繫。
附：相關閱讀

摘要：
延遲接受演算法可以從一對一雙邊市場（婚姻市場）拓展到一對多雙邊市場（學校招生），前提是學校方對於學生的偏好建立在學生個體而非學生的組合上；新的一對多市場等價於將學校拆分成入學名額個學校，學生對於這些拆分後的「學校」偏好相同的一對一市場；
在引入DA演算法之前，美國教育系統採用的模型之一是Boston Mechanism，這個演算法實際上將學校招生視為單邊市場，對於學校來說，它的偏好稱為priority而非preference，受到政府限制，不一定代表學校的喜好，這導致單邊市場只考慮一邊（在這裡是學生）的效用，學校的priority本身並沒有說明效用。Boston Mechanism的結果滿足（對於學生的）帕累托優，即每個學生不可能得到更好的學校，但是不滿足stable的條件，同時也不滿足strategy proof，也就是說學生有激勵去改變自己填報的志願，假裝自己喜歡或者不喜歡某所學校，使得自己能去的學校更好；
但如果將學生選擇志願視為一場博弈的話，非常神奇的是，這個博弈的所有納什均衡解恰好是所有穩定匹配，而我們又知道穩定匹配對於學生的最優解可以由DA演算法由學生方propose來得出，因此，一切又回歸到DA演算法，將學校招生視為雙邊市場，考慮學生propose的DA演算法，得到的解滿足stable（穩定性），M-optimal（學生最優）以及strategy-proof（學生沒有激勵去偽造自己的真實意願）；
文中穿插了關於中國高考志願填報模式的討論以及DA演算法仍然存在的一些不足。
最後，相關閱讀包括了一系列有關學校招生的著名論文。

-----------------------------------這裡是目錄和摘要的分割線---------------------------------
背景閱讀-婚姻市場上的DA演算法：戀愛中有哪些博弈？ - Richard Xu 的回答

1. 延遲接受演算法在一對多雙邊市場上的拓展，以及該拓展與一對一雙邊市場的相互關係；
正如 @瞻彼淇奧所說，只需將在一對一雙邊市場上的延遲接受演算法稍作修改，就能夠得到一對多雙邊市場上的延遲接受演算法，這些修改大致包括如下幾項：
（1）在婚姻市場上，男性對於所有女性進行排序，女性對於所有男性進行排序，這是非常直觀的；在學校招生時，學生只能去一所學校，所以學生對於學校的排序也是很容易理解的；但是，學校對於學生的排序就有兩種不同的情況：一種是，學生與學生之間是相互獨立的，學校對於單個的學生建立偏好；另一種是，學生與學生之間是有關聯的，學校招生的時候對於學生的組合建立偏好。
舉例來說，如果一共有3個學生1,2,3，那麼前一種情況是，學校覺得1比2好2比3好，或是3比2好2比1好，這是建立在「單個的學生」上的偏好；另一種情況是，學校覺得同時招1和2最好，其次是1和2和3，再次是2和3，再次是1和2，等等，這是建立在「學生的組合」上的偏好。後一種情況在什麼時候會發生呢？舉個例子，清華每年都要參加首都高校長繩比賽，長繩需要12名隊員，選拔長繩隊員的時候，並不是從各個院隊里一個一個選拔出來（單個的學生的偏好），而是選拔了最好的一個院隊（學生的組合的偏好），因為這些學生已經經過長期的磨合和練習，把他們組合在一起將會有協同效應，換上別的院跳得好的同學，反而有可能拖後腿。
後一種情況，正如我在上述另一題的回答中所說，存在反例說明可能並不存在stable matching。然而，對於前一種情況，stable matching總是存在的，原因在下面進一步闡述。
（2）引入quota，即學校的招生名額。這是很自然的，因為是一對多的緣故。
（3）由於quota的存在，對於穩定性的要求也發生了變化：
I.R.: 學生不會選擇unacceptable的學校，學校不會選擇unacceptable的學生
Pairwise Stability:不存在如下情況：
i. 學校S有空位，且學生s對於學校S是acceptable的，且對於學生s學校S比目前的情況（沒有學上或是被另一學校S"錄取）更好；
ii. 學校S沒有空位，但在錄取的學生中有一名學生s"，對於學校S學生s比學生s"更好，且對於學生s學校S比目前的情況更好；

回到上面這個問題，為什麼stable matching總是存在的呢？在一對一雙邊市場上，穩定匹配的存在性是由DA演算法構造出來的，因為構造出來的這個匹配是穩定的，所以穩定匹配存在。而對於一對多雙邊市場，我們不需要再按照證明一對一雙邊市場上那樣完全走一遍，實際上，當學校的偏好建立在「單個的學生」上時（也稱為responsive或者separable preference），我們完全可以這樣做：
學校A有三個名額，那麼我就把學校A拆成學校A1、A2、A3，分別只有一個名額，它們對於學生的偏好和學校A是一樣的，而學生認為學校A1、A2和A3是一樣好的；對其它學校也是一樣處理。DA演算法並不要求偏好是strict的（偏好strict的意思是任意兩所學校都能分出好壞，或者用報道中的話說，「在最優情況下，這群男女中不會有人同時對兩個人喜愛程度相當」，這個要求對於穩定匹配的存在性並沒有影響，隻影響了最後的穩定解是否是Lattice），這樣一拆，相當於構造了一個一對一雙邊市場，新市場上的穩定匹配存在（由DA演算法給出），則原市場上的穩定匹配只需要將A1、A2、A3重新合併回學校A即可。

2. 雙邊市場（婚姻市場）與單邊市場（房屋市場）的差異；
實際上，對於學校招生，還有另外一種模型，即單邊市場模型。在單邊市場中其實還是存在兩邊，但是一邊是人，另一邊是東西，由於我們更關注人的行為，所以稱為「單邊」。在單邊市場上，重要的是將人和東西匹配起來，也就是一個分配的問題。
最基本的單邊市場是房屋市場，每個人對於房屋都有自己的偏好，房屋自己不會挑人，隨便誰住都可以；但是，當我們考慮學校招生這樣一個單邊市場模型時，學校對於學生是可以有偏好的，這個偏好不是通常意義上的preference，而被稱為priority（兩者在形式上接近一致的），原因在 @榮健欣的答案中也有提到，即這個priority是受限制的。事實上，在學校招生模型中（比如即將提到的BM），學校的priority只能根據一系列的規則來進行，而規則是由政府決定的，例如，政府規定，學校優先招納距離學校近的學生，在距離差不多的情況下，招納學分績更高的學生，在學分績也相同的情況下，優先招納女性學生，這樣一來政府完全可以不需要學校參與決定這個priority，在這個priority中也完全沒有體現出學校自己的意願，相應地，當我們考慮此時市場的效率（efficiency）時，我們就不需要將priority考慮進來，而只考慮學生對於學校的preference所產生的效用。
由於priority的存在，對於穩定性的要求有了一個新的名詞，叫作respecting priority，基本上等價於雙邊市場中的pairwise stability。

3. （重點）原本的模型：Boston Mechanism；
在DA演算法之前，有一個模型在美國學校招生中非常流行，這個模型稱為Boston Mechanism，因為其最先在波士頓試水並推廣而得名。如果沒有猜錯的話，紐約在2003年之前使用的就是BM或者BM的變種，因為報道中有兩句話非常符合BM的實際情況：「所以有些目標高遠、填報了多家熱門學校的學生，一旦被寫在第一欄的學校拒收，就會在選校表中一落千丈。」（這是BM機制中常有的，參見下面的例子中的學生6）「家長們擔心如果選錯了，他們的孩子會「浪費」至關重要的首選位置。」（這句話雖然寫在新機制運作之後，但表達的是BM的流毒，即浪費首選位置的想法，同樣參見下面的例子中的學生6）

首先我來描述一下這個模型，它和DA演算法的描述其實只差一句話：

在BM中，如果學生s被學校S錄取，那麼之後不會被替換掉；而在DA演算法中，如果後面有更好的學生，學校S會踢掉學生s。

簡單地說，DA演算法對於BM最重要也是最神奇的改進只在於：允許「見異思遷」。

是不是覺得這個模型很熟悉？答對了，這其實非常接近目前中國高考的錄取模式（當然還有一些小的變動，比如考前填還是考後填還是知道分數填等等執行細則問題），學生填報志願，高校根據分數提檔，如果你被一志願的高校提檔並錄取了，沒有問題，如果你被提檔了但沒有錄取，那麼你基本上沒有機會被二三志願的高校再挑走，它們也差不多招滿了，不會再接受提檔，即使接受了也不會把前面的學生踢掉，這時候你就得考慮徵求平行志願或者再往下一批次了。

（在這裡說明一下題主對於相關模型在中國運用的可能性分析，昨天我和一名博士生學長聊天時，他就提到，中國高考其實並沒有表現出很多下面即將提到的BM的弊病，因為BM在一種非常特殊的情況下，和DA（無論由學生還是由學校propose）的結果是完全一致的，那就是所有學生對於學校的偏好一樣（而且strict），所有學校對於學生的偏好一樣；而我們來看中國的高考，當我們討論高考分數論英雄的時候，其實恰恰說明學校對於學生的偏好高度標準化，就是按照高考成績，就是按照分數從高到低，而學生對於學校的偏好也大致相同，清華北大，211、985或者C9，可以看出實際上大家對於學校的偏好也是從高到低排的，當然因為種種原因，填志願本身仍然構成下面所述的BM機制下的博弈，但是其複雜程度已經被大大削弱了。相比之下，層出不窮的自主招生、體育/競賽保送生或加分反而是使得BM問題更加嚴重的原因，這並不是替BM或者中國高考填志願的模式洗地，也不是反對自主招生或保送（答主對於競賽保送持強烈支持態度），而恰恰說明中國的確有必要考慮DA演算法作為高校錄取的辦法。）

4. Boston Mechanism的相關性質；

對於機制的考量主要分為三個方面，efficiency效率，stability穩定性，和strategy-proofness是否存在偏離的激勵（其實對應於激勵相容Incentive Compatibility中的一種，即Bayes-Nash IC）。
efficiency效率的意思是，學生是否得到了可能獲得的最好的學校？在DA演算法中，我們說學生得到了最好的學校，是指在所有穩定匹配中最好的學校，如果我們考慮不穩定匹配，實際上可能存在不穩定匹配使得學生都能夠更好（這裡的更好是指帕累托優，即在新的不穩定匹配中，每個人至少和在最好的穩定匹配中的處境一樣好，且至少有一個人匹配到了比穩定匹配中他更喜歡的學校），這種現象就發生在了BM模型中，它給出了一個最優但是不穩定的匹配。

考慮下面這樣一個例子，有六個學生1~6，四個學校a~d，學校ab各有兩個招生名額，cd各有一個招生名額。
學生對於學校的偏好是
R1:a 後略
R2:a 後略
R3:a b 後略
R4:c 後略
R5:c a b d 後略
R6:c a b d 後略

學校對於學生的priority是
a: 6 1 2 3 後略
b: 5 6 3 後略
c: 4 5 6 後略
d: 5 6 後略

根據BM，得到的匹配是
a: 1和2
b: 3和5
c: 4
d: 6

匹配的最優性是由BM的機制決定的，因為每一輪它都把每個學生匹配到了最好的學校，對於任何一個學生來說，他比BM所匹配的學校更喜歡的那些學校在任何匹配中都不可能招收他，這一點是不難證明的。而其不穩定性在上面這個例子就展現出來了，a喜歡學生6勝過1和2，而6喜歡學校a勝過d，說明上面的這個匹配不是穩定匹配。

觀察一下6的偏好，可以發現6在第一輪選擇了自己最喜歡但是卻並不是那麼喜歡自己的學校c，這是一個嚴重的失誤，因為同時本來最喜歡他的學校a已經招滿了學生，即使6試圖在第二輪挽回（選擇了a），仍然一再錯失機會，最後只得到了排在最後的學校d。這就是「一旦拒收，一落千丈」和「浪費首選位置」的真實體現。

在這裡，又不得不提到最後一個考量標準，就是strategy-proofness。這個要求的意思是，任何學生（因為學校的priority是不能更改的）都沒有激勵不按照自己真實的意願來報告自己的偏好。而BM給出的模型顯然不滿足這一點，仍以上面這個例子為例，如果6意識到自己可能被c拒絕並最終不得不進入d，那麼他完全可以謊報自己喜歡a勝過喜歡c，這樣在第一輪他就把2擠走成功進入了a，儘管他沒能進入最想進入的學校c，但是仍然比進入d要高了兩檔。

綜上所述，BM雖然能夠給出帕累托優的匹配，但是這個匹配是不穩定的，而且不是激勵相容的，學生有謊報自己偏好以獲取更高的學校的可能。

5. （重點）進一步分析：Boston Mechanism 與 Deferred Acceptance Algorithm的聯繫。
不過拍腦袋一想，不對啊，既然你可以改自己的志願，我也可以改嘛。因此，在BM真正開始分配之前，也就是學生們填報志願的時候，就已經開始了一場沒有硝煙的戰爭，學生們都會調整自己的志願，使得能夠上到更符合自己偏好的學校，這構成了一場博弈，每個學生是一名玩家player，每個人的策略就是不同的志願填報順序R，最終的結果outcome就是根據每個人填報的志願進行BM分配所得到的學校，相應的payoff就是和自己偏好的相符程度，能得到自己更偏好的學校效用就更高。
在這個博弈中，存在著一系列的納什均衡，而神奇的是，這些納什均衡的結果outcome恰好就是所有的穩定匹配，這一點的證明可以在這裡稍微表述一下：
首先要證明所有的納什均衡結果都是穩定匹配，這是顯然的，如果存在納什均衡的結果是不穩定匹配，那麼也就意味著有學校S想要學生s來踢掉別人或者填補空位，學生s也想要學校S而非現在匹配的學校，那麼s只需要把學校S提到自己志願的第一位就可以了，也就是他有進一步改變自己志願的激勵，不滿足納什均衡的要求。
其次要證明所有的穩定匹配都是納什均衡的結果，這就更顯然了，只要每個人都把自己在這個穩定匹配中匹配到的學校填在第一位，第一輪百分之百全部錄取；任何人單方面的背離都不能是他更好，因為其他人把所有別的坑都填滿了，他要麼最後還是回去填了自己的坑，要麼就沒學上。
根據集合的性質，如果集合A和集合B互相包含，那麼這兩個集合相等，因此所有的納什均衡結果就是所有的穩定匹配。

這告訴我們什麼呢？如果將學生在BM機制下選擇志願視為一場博弈的話，非常神奇的是，這個博弈的所有納什均衡解恰好是所有穩定匹配，而我們又知道穩定匹配對於學生的最優解可以由DA演算法由學生方propose來得出，因此，一切又回歸到DA演算法，將學校招生視為雙邊市場，考慮學生propose的DA演算法，得到的解滿足stable（穩定性），M-optimal（在所有穩定匹配中對於學生來說最優）以及strategy-proof（學生沒有激勵去偽造自己的真實意願，可以證明，此處略去）；

這也正是報道中提到的一句話，「按真實的偏好順序來排列學校。」

順帶說一句，其實這篇報道的記者對於DA演算法還不夠了解，最重要的是這樣一句話「那一年以及之後的每一年，這種演算法大致將所有學生中的一半人數分配到他們的首選學校；另外大概三分之一的學生被分配到他們的次優選擇或是第三選擇的學校。」 DA演算法關注的並非是首選學校或是非首選學校，這恰恰是BM所關注的重點，BM就是盡量將學生都儘可能分配到首選或者靠前的學校。但是事實上，這個關注重點又是非常無關緊要的，按照給我們授課的教授的說法，如果大家都按照DA演算法給出的最優穩定匹配來填，那麼BM將會100%的將學生安排到第一志願，但這有什麼意義嗎？
其次，在報道中出現了所謂心儀學校、失望的學生這樣的說法；如果DA演算法沒有給學生分配到某所更好的學校，絕不是因為演算法故意讓你去不成，而恰恰說明在所有的穩定匹配中，都不存在讓你去這所學校的可能；甚至回到BM的志願選擇博弈中，無論你如何努力地去調整自己的志願，最終的均衡結果中（也就是穩定匹配中）同樣沒有讓你去這所學校的可能。這樣的失望是沒有意義的，就好像分數只有本一線附近的學生指望通過填志願就進入清北一樣，就算你進不了，也不能怪中國的高考志願填報方式吧。

當然，DA演算法也並不是沒有問題，最關鍵的地方在於，strategy-proof還是太不能滿足人們的要求了，它假定的是別人如果不偏離，那麼你也不應當偏離，但是在別人偏離的情況下，你不是還應當不偏離呢？不一定，要滿足這種情況，要求的是dominant strategy incentive compatibility，無論別人選擇什麼，按照自己真實的偏好填寫志願都是最好的選擇（之一），這是比strategy-proof或者說Bayes-Nash incentive compatibility更高的要求，而DA演算法並不滿足。

-----------------------------------這裡是正文和相關閱讀的分割線--------------------------
相關閱讀：（引用規範暫時先不管了……）
核心內容：
[1]AbdulkadirogluSonmez(2003, AER) "School Choice: A Mechanism Design Approach"
[2]Abdulkadiroglu, Pathak Roth(2009, AER) "Strategy-proofness versus efficiency in matching with indifferences: redesigning the New York City high school match"

Efficient Resource Allocation under Priorities:
[3]ErdilEhlers(2010, JET) "Efficient assignment respecting priorities"
[4]A series of papers by Kumano that "generalize to subtitutable priority ranking"

Boston Mechanisms:
[5]PathakSonmez(2008, AER) "Leveling the playing field: Sincere and sophisticated players in the Boston mechanism"（老師給我們寫的是「NaiveStrategic students」……）
[6]A series of papers by Kojima that "generalize to substitutable priority structure"
[7]Abdulkadiroglu, CheYosuda(2011, AER) "Resolving Conflicting Preferences in School Choice: The" Boston Mechanism" Reconsidered"

不樂意看英文的請繞路，這個問題下就好幾個不錯的回答，不一定非看我的。

需要譯文的請出門右拐看評論區。

再有糾結語言問題的評論將不再回復。

—————原答案的分割線—————
謝邀。（第一次被邀請回答問題，心裡還有點小激動呢（≧?≦））

先上演算法：Defered Acceptance Algorithm

Begin with every woman marked as rejected.
While there exist a rejected woman, do as following:

(1) Each woman marked as rejected choose a man whom she ranks highest among all those men who has not yet rejected her.
(2) Each man picked out the woman whom he ranks highest among all those women who have chosen him and whom he has not yet rejected, defers decision on her (and removes her rejection status), and now rejects the others.

From Introductory Combinatorics 5ed, page 332.

這個是穩定婚姻問題中，女性主動求婚的延遲接受演算法。
在求職、擇校等等問題中（相當於一夫多妻/一妻多夫的穩定婚姻），上述演算法稍作修改後即可給出一個stable mathching.

題主給出的鏈接里給出了一個學生擇校的例子，我們拿它做分析：
（原例圖表很清晰了，無奈ipad貼不上圖片。。。只好文字敘述）
有三所學校1，2，3，和十名學生A，B，…，J。每所學校列出它想接收的學生並為其排序（學校1：ABCD；學校2：EFGD；學校3：ADHI），每名學生列出自己的志願學校並為其排序（A：123；B：21；C：132；D：132；E：321；F：12；G：132；H：32；I：123；J：213），每所學校最多接收三名學生。

我們把演算法改成：學生主動申請（求婚）的（一夫多妻）延遲接受演算法，和原演算法的差別是：學校會拒掉其接收名單之外的學生；當有三名以上學生申請同一所學校時，學校會按照預先給出的排序，保留排位最高的三名學生，同時拒掉其他人；存在學校名額招不滿或學生沒學上的可能性。

第一步，所有學生都申請了自己的志願中排名最靠前的學校，即A、C、D、F、G、I申請學校1；B、J申請學校2；E、H申請學校3。
由於F、G和I不在學校1的接收名單之內，因此這三名學生悲傷的收到了拒信，同理B，E，和J也收到了拒信。

第二步：被拒的六名學生繼續申請自己的第二志願，即B和J申請學校1；E，F和I申請學校2；G申請學校3。
對學校1而言，J不在接收名單內，拒掉。此時學校1有A，B，C，D四名申請者，於是選擇排位靠前的A，B，C，拒掉D。
學校2和3同理。這一輪中D，G，I，J收到拒信。

第三步：D申請第二志願；G，I，J申請第三志願：G申請學校2，D，I，J申請學校3。J因為不在名單內而被拒，其餘學生全部拿到offer。由於J已經被全部三個志願拒掉，演算法結束。

和穩定婚姻類似，可以證明延遲接受演算法給出的擇校安排是穩定的，即不會出現你情我願的轉學現象。

樓上的 @Richard Xu是嘉神么。。

題主如果感興趣，可以瀏覽一下我在Quora上回答過的一個類似的問題，部分內容和上面答案類似，有一些補充以供參考：
Xiaoyu Cheng"s answer to How can game theory improve high school universities application process?

邀請錯人了.不好意思我對這個問題沒興趣.
但是下面這篇paper介紹比較詳細

http://www.nber.org/papers/w13225.pdf

最近寫了一篇school matching的簡略的文獻綜述，先手機占坑，回頭補上。
========================================================
May 20 2015
關於school mathching文獻綜述的傳送門在此：
https://docs.google.com/viewer?a=vpid=sitessrcid=ZGVmYXVsdGRvbWFpbnxoYXJyeXpodXl1aGFvfGd4OjQ1ZDMyZDI5MzAwMzdhZTQ
這篇文章是英語的，如果樓主不介意的話可以看一下原版。文章介紹了三種不同的演算法，演算法的一些特點，演算法的應用，以及對演算法的實驗。完全可以回答樓主的問題。
不過還是簡單用中文解答一下樓主的疑問：

問題1：「延遲接受演算法」（deferred acceptance mechanism）和婚姻配對中提到的「stable matching」好像是同一個演算法嗎？
答案：是。或者更專業的說：延遲接受演算法提供的matching是stable的。

問題1（引申）：學校配對問題和婚姻配對問題的區別於聯繫？
答案：婚姻配對問題是學校配對問題的一個特例。學校配對問題中，一個學校可以有多個名額，而在婚姻問題中，每一方都只有一個名額。所以，我們可以通過先研究婚姻配對，拓展到學校配對（這也是1966年的Shapley Gale最早的論文的方法）。我們也可以通過研究學校配對問題，把性質直接繼承給婚姻配對。

問題1（引申）：學校配對的方法有什麼評價標準？符合什麼樣標準的配對法是好的？
答案：三個要求最重要。
1、穩定性（stability）。對，就是婚姻配對中的那個stable matching的意思。什麼叫不穩定呢？比如男一和女一結婚了，男二和女兒結婚了。可是男一更喜歡女二，女二也更喜歡男一。這樣這兩個人都更喜歡對方勝過當前配偶。那麼他們就能各自離婚，然後在一起。這就叫做不穩定。
穩定性就是排除了這個問題。當然日本經濟學家小島先生則也將它認為成公平性。舉個例子：如果學生一被清華錄取，學生二被北大錄取。可是學生一更喜歡北大，北大也更喜歡學生一。那麼學生一肯定會嫉妒學生二：「憑什麼北大更喜歡我卻錄取了你？」這就是不公平了。
2、帕累托最優。意思是說，一旦配對完成，我想進行一下改變使得學生一得到更喜歡的學校，那麼這樣做必然會讓另外一個（一群）學生得到了更差的學校。
如果我改變了配對使得學生一得到更好的學校，並且其他的人不會變差。那麼我完全可以進行改變，這樣社會總的福利會提高。
學校配對的一個要求便是讓配對達到帕累托最優。更具體一點，我們更希望讓學生這一邊達到帕累托最優。
3、說真話（truth-telling）。意思是說，在我所有的策略當中，將我真實的偏好展現出來是最佳策略。為什麼我會隱藏我的偏好呢？舉個例子：
一個錄取法只有一輪，由學生向最喜歡的學校遞交申請，學校同意或者拒絕。
我最喜歡的學校是學校一，然後是學校二。
張三最喜歡學校一，並且大學一也更喜歡張三。李四最喜歡學校二，但大學二最喜歡我。
如果我說真話，申請了我最喜歡的學校：大學一。那麼我就被張三打敗，開始了家裡蹲生活。
如果我這時候隱藏我真實的偏好，申請了學校二。那麼我可以打敗其他所有人，能夠進入一所大學學習。這對我肯定是最佳的策略。
說真話為什麼重要？因為一旦大家都沒表達出真實的偏好，那麼配對方法的一些好的性質其實都無法達到了。

問題二：能不能具體解釋下，如何可以用「延遲接受演算法」解決擇校問題？
以下介紹三種配對方法：1、延遲接受演算法。2、波士頓方法。3、Top trading cycle mechanism （中文不知道）
1、延遲接受演算法。
我們進行假設：有N個學校，每個學校都有一定的名額。有M個學生。
每個學校和每個學生都會給對方進行優先順序的排序，也就是偏好。

第一輪：每個學生給最喜歡的學校發出申請。學校根據偏好挑選學生，直到名額滿。如果名額不滿，那麼就保留所有申請；如果名額滿了，拒絕超出名額的那些申請。
第二輪：每個在上一輪被拒絕的學生，向第二個喜歡的學校提出申請。收到申請的學校，會將這輪收到的申請，和上輪留下的請放在一起比較，根據偏好留下學生，並且拒絕掉排在名額外的學生。
……
最後一輪：每個學生都向所有的偏好列表的學校提出了申請，或者學校名額滿了。配對結束。
當我們將學校的名額換成1的時候，其實這就是個婚姻配對問題了。延遲接受演算法的特點是：
1、穩定。
2、帕累托不最優。
3、說真話不一定是最佳策略。

今天寫到這，明天繼續填坑。

不就是備胎演算法么？

你情我願 &> 我情你隨便 &> 你情我隨便 &> 不情不願

是同一個演算法。
問題：Stable marriage problem
演算法： Gale–Shapley algorithm (a.k.a. 延遲接受演算法)

好想答這個問題…考完試就把小論文粘過來

不可行，擇校問題對應的是hospitals/residents problem

這個問題在有大量ties和preference list不完整的情況下是一個np問題，至少目前不存在多項式時間內的解。

謝腰
是同一個問題

這是一個選擇分配的問題，即所有學校都參與到分配中而不是以各個學校自己為中心進行分配……

在中國恐怕有關部門不會同意

謝邀，不過有人回答過了我就不說了。倒是被激起新idea啦，開論文去。