Gale Shapley 學(xué)生最優(yōu)機(jī)制摘抄

Gale—Shapley學(xué)生最優(yōu)機(jī)制（本文簡稱GS機(jī)制）就具有公平和抗策略的特性，并且相對于其他公平的機(jī)制而言，它是帕累托最優(yōu)的。GS機(jī)制最早是在大學(xué)招生模型中提出來的（GaleandShapley,1962⑼），在大學(xué)招生模型中，學(xué)生和學(xué)校都是積極參與人。Gale和Shapley證明，在大學(xué)招生模型中穩(wěn)定匹配總是存在的，并且在所有的穩(wěn)定匹配中，存在一個(gè)匹配對于學(xué)生來說是帕累托最優(yōu)的，一個(gè)匹配對于所有學(xué)校帕累托最優(yōu)。他們提出了達(dá)到學(xué)生（學(xué)校）最優(yōu)穩(wěn)定匹配的機(jī)制，這個(gè)機(jī)制通過延遲接受學(xué)生（學(xué)校）申請來達(dá)到。由于我們關(guān)注的是學(xué)生利益，因此考慮學(xué)生最優(yōu)機(jī)制，該算法過程如下：第1輪：每個(gè)學(xué)生申報(bào)其第一志愿，每個(gè)學(xué)校根據(jù)其偏好將第一志愿報(bào)考本校的前qc（qc為招生名額）個(gè)學(xué)生納入考查名單，拒絕其他學(xué)生。第2輪：上輪被拒絕的學(xué)生申報(bào)第二志愿，每個(gè)學(xué)校將第二志愿報(bào)考本校的學(xué)生和列入考查名單的學(xué)生一起比較，將前qc個(gè)學(xué)生納入第二輪考查名單。第k輪：上輪被拒絕的學(xué)生申報(bào)第k志愿，每個(gè)學(xué)校將第k志愿報(bào)考本校的學(xué)生和列入考查名單的學(xué)生一起比較，將前qc個(gè)學(xué)生納入第k輪考查名單。當(dāng)沒有學(xué)生被拒絕，所有學(xué)生都分配到最終位置時(shí)，該算法結(jié)束。定理1（H.ErginandT.Sonmez，2006〔10〕）:給定考生的真實(shí)偏好以及考生在“波士頓機(jī)制”下的顯示偏好博弈。這個(gè)博弈的納什均衡結(jié)果與學(xué)生最優(yōu)機(jī)制下真實(shí)申報(bào)偏好所得到的匹配結(jié)果是相同的。定理2（GaleandShapley，1962〔9〕;BalinskiandSon-mez，1999〔11〕）:GS機(jī)制帕累托優(yōu)于其他任何公平機(jī)制。定理3（DubinsandFreedman，1981〔12〕;Roth，1982〔13〕）:GS機(jī)制是抗策略的。定理4（AlcaldeandBarbeia，1994〔14〕）在高考招生問題中，GS機(jī)制是唯一滿足個(gè)人理性、公平、沒有浪費(fèi)和抗操縱的學(xué)生錄取機(jī)制。由此看來，GS機(jī)制具有三大優(yōu)點(diǎn)：（1）它能夠促使考生真實(shí)申報(bào)其偏好，避免了考生之間的志愿博弈，完全解決了填志愿難的問題，節(jié)約了大量不必要的社會(huì)成本，志愿填報(bào)時(shí)間問題也迎刃而解。（2）在考生真實(shí)填報(bào)其志愿的前提下，最終的錄取結(jié)果對所有學(xué)生而言都是最優(yōu)的，并且不會(huì)出現(xiàn)不公平或資源浪費(fèi)的現(xiàn)象。（3）它能夠化解統(tǒng)一高考與自主招生之間的矛盾（關(guān)于堅(jiān)持統(tǒng)一高考必要性的討論參見劉海峰，1997〔15〕，2006〔16〕;張亞群，2005〔17〕等）。即便是高校有自己不同的評價(jià)標(biāo)準(zhǔn)，這種機(jī)制依然能夠得到一個(gè)公平的匹配。這就意味著，這種機(jī)制能夠在保證考生利益的同時(shí)，賦予高校更充分的自主招生權(quán)力，促進(jìn)“多元化評價(jià)”的實(shí)施與推行。不過，該機(jī)制的運(yùn)作效率較低，它最多要用步才能完成整個(gè)算法，這無疑是對招生工作的一種挑戰(zhàn)，也是高考改革中常常面臨的效率與公平之間的矛盾。在實(shí)踐過程中，為了減少算法步驟，每所高?？梢粤谐銎湔猩淖畹蜆?biāo)準(zhǔn)，比如限定某門學(xué)科的最低分?jǐn)?shù)，以減少錄取工作量?？傮w而言，高考改革的發(fā)展趨勢是從效率優(yōu)先走向公平優(yōu)先，繼而走向公平與效率的兼顧與平衡（劉海峰，2002〔18〕）。因此，要想獲得讓考生滿意，高校滿意、社會(huì)滿意的良好效果,再大的挑戰(zhàn)都應(yīng)該迎難而上。事實(shí)上,這種機(jī)制也并非難以實(shí)施。2005年7月，波士頓和紐約就進(jìn)行了公立學(xué)校擇校機(jī)制改革，為減少父母們的志愿策略博弈，波士頓學(xué)校委員會(huì)投票決定將當(dāng)前的波士頓學(xué)校錄取機(jī)制改為GS學(xué)生最優(yōu)機(jī)制。。但和中國不同，它通過一個(gè)類似中央招生辦公室的機(jī)構(gòu)，對全體學(xué)生按照志愿和報(bào)考專業(yè)需要的單科成績排名來統(tǒng)一錄取。在擇校問題中，學(xué)校所在地的法律使得所有學(xué)生在每個(gè)學(xué)校中都有一個(gè)優(yōu)先順序，不同的學(xué)校中學(xué)生的排序不同,學(xué)生的志愿順序和在學(xué)校的優(yōu)先順序決定他是否被錄取。他們研究的“波士頓機(jī)制”和咼考的錄取機(jī)制類似，也有因第一志愿不當(dāng)而喪失排序優(yōu)勢的風(fēng)險(xiǎn)。他們提出Gale2Shapley機(jī)制是一個(gè)改進(jìn)的替代機(jī)制。SnmezandErgin(2006)研究了“波士頓機(jī)制”下的各種博弈。SnmezandChen(2006)利用試驗(yàn)經(jīng)濟(jì)學(xué)的方法分析了“波士頓機(jī)制”，發(fā)現(xiàn)這個(gè)機(jī)制下學(xué)生會(huì)操縱自己申報(bào)的偏好，與Gale2Shapley學(xué)生最優(yōu)機(jī)制相比有較大的效率損失。在Roth等博弈論專家的咨詢協(xié)助下，波士頓和紐約的公立學(xué)校擇校機(jī)制改革為Gale2Shapley學(xué)生最優(yōu)機(jī)制。“波士頓機(jī)制”與高考錄取機(jī)制類似也是“第一志愿優(yōu)先”，AtilaAbdulkadroglu,ParagA.Pathak,AlvinE.Roth和TayfunSnmez(2006)分析了這個(gè)機(jī)制下學(xué)生填報(bào)的志愿數(shù)據(jù)。他們發(fā)現(xiàn)并不是所有的考生和家長都意識(shí)到或者有能力在這個(gè)機(jī)制下操縱自己的偏好，一些家長沒有避免明顯的錯(cuò)誤。和經(jīng)濟(jì)理論中的均衡分析不同,在實(shí)際中可能并不是所有家長都有同樣的能力和資源計(jì)算出均衡策略。因而錄取機(jī)制無操縱也是一種公平的要求，使所有考生在同一平臺(tái)上競爭。各地區(qū)的志愿填報(bào)方式(或機(jī)制)都是“志愿優(yōu)先”，這一機(jī)制存在著“高分低就”的可能，在文獻(xiàn)中也被稱為公平性(fairness)或穩(wěn)定性(stability)問題。學(xué)生可能不會(huì)將其最喜歡但是競爭激烈的學(xué)校放在第一志愿，而是把不太喜歡但風(fēng)險(xiǎn)較小的學(xué)校放在第一志愿，即不會(huì)按照自己真實(shí)的偏好序進(jìn)行填報(bào)，這被稱為抗操縱性(strategy-proof)問題?！捌叫兄驹浮钡囊雱t是試圖將“志愿優(yōu)先”改為“分?jǐn)?shù)優(yōu)先”以克服上述兩種弊端。填報(bào)志愿的時(shí)序，包括考前和考后填報(bào)志愿，后者又包括考后估分和考后知分填報(bào)志愿兩種方式。兩個(gè)不同維度上的組合可以產(chǎn)生不同的機(jī)制，與國外擇校機(jī)制文獻(xiàn)中研究的典型機(jī)制存在某種對應(yīng)關(guān)系。概括來說，考后知分填報(bào)在沒有平行志愿時(shí)對應(yīng)于文獻(xiàn)中的波士頓機(jī)制(BostonMechanism，BOS機(jī)制)，在具有“完全"平行志愿時(shí)對應(yīng)于首位交易環(huán)機(jī)制(TopTradingCyclesMechanism，TTC機(jī)制；或稱分?jǐn)?shù)優(yōu)先的系列獨(dú)裁機(jī)制,SerialDictatorshipMechanism，SD機(jī)制)以及Gale—Shapley機(jī)制(GS機(jī)制，又稱延遲錄取機(jī)制，DeferredAcceptance，或DA機(jī)制)。已經(jīng)證明，考后有平行志愿的填報(bào)機(jī)制是公平的、有效率的和抗操縱的。傳統(tǒng)的擇校機(jī)制文獻(xiàn)認(rèn)為BOS機(jī)制在抗操縱性、效率和公平等方面均無法與TTC機(jī)制或GS機(jī)制抗衡。正是在這些理論的指導(dǎo)下，BOS機(jī)制的命名地 美國波士頓地區(qū)公共學(xué)校 的政府管理部門從2005年開始將其擇校機(jī)制改為了GS機(jī)制。不過具有諷刺意味的是，在這之后文獻(xiàn)開始反思這些理論結(jié)果，一個(gè)核心的想法是：當(dāng)存在學(xué)生偏好序或者學(xué)校優(yōu)先序的不確定性時(shí)，BOS機(jī)制從事前效率和公平的角度講，并不劣于甚至在一定條件下優(yōu)于其他機(jī)制。國外的實(shí)證研究大都基于實(shí)驗(yàn)數(shù)據(jù)，ChenandSonmez（2007）比較了BOS、GS、TTC三種擇校機(jī)制特征，發(fā)現(xiàn)BOS機(jī)制下確實(shí)有更多的偏好操縱，這使得BOS機(jī)制下的效率更低。不過，F(xiàn)eatherstoneandNiederle（2008）從事前角度、用實(shí)驗(yàn)方法考察了GS（或DA）機(jī)制和BOS機(jī)制，發(fā)現(xiàn)在學(xué)生偏好是私人信息以及學(xué)校對學(xué)生的優(yōu)先序存在不確定性時(shí)，BOS機(jī)制可能比DA機(jī)制更有效率。在已有的少數(shù)利用實(shí)際數(shù)據(jù)的研究中，Abdulkadiroglu，Pathak,RothandSonmez（2006）利用美國波士頓地區(qū)擇校結(jié)果的實(shí)際數(shù)據(jù)分析發(fā)現(xiàn)，在BOS機(jī)制下，進(jìn)行偏好操縱的參與者比沒有進(jìn)行偏好操縱甚至錯(cuò)誤填報(bào)偏好的參與者獲得更大利益。Abdulkadiroglu，PathakandRoth（2009）依據(jù)紐約市2006-2007年8年級（即升高中）學(xué)生提交的偏好，用實(shí)驗(yàn)?zāi)M比較了不同擇校機(jī)制的匹配結(jié)果。這可能是目前唯一一篇基于實(shí)際數(shù)據(jù)比較不同機(jī)制的研究，但由于無法觀察到實(shí)際偏好，他們只能將學(xué)生提交偏好假定為真實(shí)偏好。本文的另一個(gè)貢獻(xiàn)在于選取了一個(gè)獨(dú)特的角度來衡量匹配質(zhì)量。匹配質(zhì)量的衡量是擇校機(jī)制經(jīng)驗(yàn)研究的一個(gè)難點(diǎn)。首先，任何評價(jià)方法都要求了解每個(gè)考生的偏好，而這通常是觀察不到的。其次，雖然從理論上定義匹配質(zhì)量——效率與公平——并不困難，但從經(jīng)驗(yàn)數(shù)據(jù)中衡量匹配結(jié)果的質(zhì)量仍然是仁者見仁的事。最后，評價(jià)完整的匹配質(zhì)量對數(shù)據(jù)可得性要求很高，需要掌握所有考生的偏好、分?jǐn)?shù)排序以及最終錄取結(jié)果的完整信息。本文通過只考察國內(nèi)某一頂級大學(xué)學(xué)院所招收的學(xué)生群體的變化大大簡化了問題。作為一個(gè)頂級大學(xué)