中國高考招生錄取機制—— 一個巨大的協(xié)調博弈

1、中國高考招生錄取機制 一個巨大的協(xié)調博弈聶海峰內容摘要：本文分析了當前高考招生的考后報考錄取機制，刻畫了這個機制的性質和缺點，并介紹了一種改進的機制。當前中國高考招生制度使得招生過程成了一個百萬考生參加的巨大的顯示偏好博弈，這個博弈只有唯一的一個納什均衡結果，但是真實的偏好并不一定是每個考生的均衡策略。達到均衡結果需要參與人之間幾乎不可能的協(xié)調。使用galeshapley學生最優(yōu)機制，可以達到同樣的配置，并且真實偏好是學生的占優(yōu)策略，結果也是帕累托有效，公平的。如果高考招生制度進行改革，將會有巨大的效率改進。關鍵詞： 匹配 gale-shapley學生最優(yōu)機制 占優(yōu)策略 a titanic c

2、oordinating gamecollege admission in china nie haifeng (guanghua school of management, peking university)abstract: the college admission mechanism in china is a giant revealing preference game played by millions of students every year. unfortunately, the true preferences of students are not their op

3、timal equilibrium strategies. we prove that the equilibrium outcome is unique and pareto efficient, but it is hardly a possible mission to coordinate to equilibrium. fortunately, the admirable gale-shapley deferred mechanism in college admission model can be adapted to achieve the same outcome with

4、more advantages. a great of efficiency would be achieved if the existing college admission mechanism had been replaced. key words: gale-shapley mechanism match strategyproofjel classification： c78 ,d61,d78一、 引言現(xiàn)在的高考招生制度是從1978年恢復高等學校入學考試以來一直沿用至今，成為大學入學的基本方式。想進入大學學習的人員，參加由教育部統(tǒng)一組織的入學招生考試，然后各個招生學校根據(jù)考生的志

5、愿和考試分數(shù)的高低決定是否錄取。在當前的高考招生制度下，大學沒有了自主的權利，大學的招生名額成了通過高考分數(shù)分配的公共品。高考期間，考生和家長不但要了解各種大學的情況得到對學校的偏好，而且如何填報志愿也是家長們焦頭爛額的事情。在目前統(tǒng)一入學考試的制度下，各高校都強調分數(shù)的公平性，實際錄取的規(guī)則也是分數(shù)優(yōu)先。清華大學的招生簡章所有引用的2004年招生簡章，可從下面網(wǎng)址下載：/recruit/zszc_2004/moe/index.jsp。中寫道：“第十二條 清華大學按照考生的實際考分和報考志愿安排專業(yè)，各專業(yè)志愿之間存在一定的分數(shù)級差。分數(shù)級差的確定以調

6、檔線上該考區(qū)報考清華大學的所有考生的志愿滿足率最大為標準，一般在310分之間，同等條件下參考相關科目成績?！庇行W校使用的是按所有報考該校的考生成績排名錄取，如同濟大學招生專業(yè)錄取規(guī)則是在從高分到低分排序的前提下，再按專業(yè)志愿先后進行錄取，一般情況下，第一專業(yè)志愿優(yōu)先 2 分錄取專業(yè)，其他二、三等專業(yè)志愿之間考分高者先錄取，同等分數(shù)情況下，專業(yè)志愿在前者先錄取?！?但是，一個考生是否能進入大學學習，不僅需要一個好的分數(shù)，所填報的志愿也有重大影響。考生填報的志愿作為對大學專業(yè)的偏好，并不一定就是它對大學專業(yè)的真實偏好，這一點，任何考試咨詢人員都會提到，每個考生家長也都深刻領會的。在當前的招生制度

7、中，如果考生的志愿不當，就會面臨喪失這個優(yōu)勢的風險。在高考招生中，各個學校先錄取第一志愿的學生，只有當錄取不滿的時候才招收第二志愿的學生。如北京大學的錄取規(guī)則：“第十三條 在第一志愿生源不足的情況下，北京大學接收非第一志愿考生。但其分數(shù)應不低于已投檔的第一志愿考生的平均分?！?即使招收第二志愿的學校，也對考生的考分有規(guī)定。比如北京師范大學的招生簡章寫道：“第十五條 北京師范大學在部分省（自治區(qū)、直轄市）接收北京大學、清華大學的第二志愿考生（我校參加提前批錄取的省份除外），招生數(shù)控制在所在?。ㄗ灾螀^(qū)、直轄市）同類計劃的 10%以內，分數(shù)級差在40分以上，在考生保證服從專業(yè)調劑的情況下，按照實考分

8、數(shù)由高到低擇優(yōu)錄取。”這樣，如果志愿填寫不當，考生就會有喪失分數(shù)的優(yōu)先性的風險，甚至出現(xiàn)沒有被任何大學錄取的可能。因而，考生填寫的志愿，不一定是他對大學真實的偏好，而是他的分數(shù)有優(yōu)勢的學校。如何首選第一志愿是每個考生和他家庭都極為關注的事情，整個志愿填報過程成了所有考生尋求最優(yōu)策略的一個博弈。由于學生的考分和志愿事實上是決定是否被學校錄取的主要標準，這就使得在學生和高校組成的高校招生博弈中，填寫志愿的學生就是唯一的行動者，給定了學生的考分和志愿，根據(jù)高考招生制度，就可以的到高考的招生結果?，F(xiàn)在全國的各高等院校是按照省為單位進行招生，每年各省參加高考招生人數(shù)近百萬，整個高考志愿填報就成了一個百萬

9、人參加的巨大的博弈。每個家長如何尋找自己的最優(yōu)策略，并不是一件輕而易舉的事情。我們在下文中將證明,在完全信息下，這個巨大的協(xié)調博弈中，只存在唯一的一個納什均衡結果。這個結果是帕累托最優(yōu)的，公平的。但是在這個巨大博弈中，考生的真實偏好常常不是他的均衡策略。如何協(xié)調到均衡策略，對每個學生來說成了一個不可能的任務。自然，高考實際錄取的情況就不會是帕累托最優(yōu)的情況了，存在著可觀的無效率。在實際的招生中，出現(xiàn)的高分落榜和學生不去學校報到的現(xiàn)象就是證據(jù)。大學招生模型的文獻研究開始于gale和shapley 1的文章，他們研究了類似的大學招生問題，提出了galeshapley學生最優(yōu)機制。其后文獻的發(fā)展在r

10、oth和sotomayer2中有全面的總結和綜述。但是，中國的高考招生制度和gale和shapley研究的大學招生制度有一個顯著的不同。在gale和shapley的大學招生模型中，學生和學校都是積極的參與人，學生對要申請的大學有一個偏好，大學也對所有學生有偏好。但在當前中國的高考招生制度中，學生的偏好和學生的成績決定了學生是否能被學校錄取，學校是所有學生共同擁有的公共品，考生的成績和志愿決定了這些公共品如何在學生中間分配。 土耳其也是通過標準化考試來進行大學錄取的。但和中國不同，土耳其通過一個類似中央招生辦的機構對全體學生按照志愿和報考專業(yè)需要的單科成績排名來統(tǒng)一錄取的。michel bali

11、nski和tayfun snmez3研究了土耳其的大學招生制度，提出了用galeshapley學生最優(yōu)機制來替代。atila abdulkadiroglu和tayfun sonmez4首次從機制設計的角度研究了美國公立學校的擇校制度。其中的“波士頓機制”和高考的錄取機制類似，也是根據(jù)學生的志愿來進行錄取。在擇校問題中，學校所在地的法律使得所有學生在每個學校中都有一個優(yōu)先順序，在不同的學校中學生的排序不同，根據(jù)學生的志愿順序和優(yōu)先順序決定是否被中學錄取。galeshapley學生最優(yōu)機制也被作者提出作為當前機制的一種替代，并且論證了被代替機制的弊端。sonmez tayfun 等人56利用試驗經(jīng)

12、濟學的方法分析了“波士頓機制”，發(fā)現(xiàn)這個機制下會出現(xiàn)帕累托無效的配置，學生都和高考一樣操縱自己申報的偏好。在真實的世界中，galeshapley學生最優(yōu)機制現(xiàn)在被應用在美國進行全美實習醫(yī)生的實習分配 789。 如果把學生的考分排序解釋成學校對學生的偏好，高考的問題就成了一類特殊的gale-shapley大學招生問題。在這個大學招生問題中，所有學校對學生偏好是一樣的。在galeshapley大學招生問題中，galeshapley學生最優(yōu)機制可以達到學生最優(yōu)的學校配置，最優(yōu)配置對學生是帕累托最優(yōu)的。當前的高考制度下博弈的均衡結果，和執(zhí)行galeshapley學生最優(yōu)機制得到一樣的均衡結果。但是，在

13、執(zhí)行galeshapley學生最優(yōu)機制時，真實顯示偏好是每個學生的占優(yōu)策略，不需要同時和其他人的偏好進行協(xié)調。同時，在galeshapley學生最優(yōu)機制下，如果考生的高考成績提高，錄取他的大學在他的偏好次序上不會下降。并且，使用galeshapley學生最優(yōu)機制, 不論填報志愿是在考試前，考試后還是估計分數(shù)填報，真實偏好都是學生的占優(yōu)策略。這樣，galeshapley學生最優(yōu)機制使得考生無需費心進行策略操縱，也減少了高分低就的損失。本文其他部分的組織如下：第二部分是對高考招生問題和對應的gale-shapley大學招生問題的描述，第三部分證明了高考博弈均衡結果的唯一性。第四部分是作為替代的ga

14、le-shapley學生最優(yōu)機制和這個機制的性質。最后部分是總結。二、高考招生問題目前實際招生中是以省為單位進行的，每一個招生學校確定在不同省的招生名額和專業(yè)。本文的分析也是局限在各省的招生制度。下面的討論中，學校的招生名額是已經(jīng)劃分到省的招生名額。全國不同的地區(qū)使用不同的試卷進行標準化考試，也使得招生是按照各省的學校名額進行的。在實際錄取中，也是各個省內的考生錄取。高考招生的基本要素是學生的考分、學生的志愿和學校的招生計劃。志愿是每個學生對大學的偏好。在不同的省份，志愿遞交的時間和全國統(tǒng)一招生考試的時間并不一致。統(tǒng)一招生考試由法定統(tǒng)一時間進行，志愿遞交時間各省自己安排。根據(jù)學生填報志愿時對自

15、己分數(shù)的了解程度，共有三種制度安排：考前填報，這時考生沒有參加招生考試；估分填報，在招生考試結束的1-2日內填報，考生對自己的考分有一個預計；第三種是知分填報，所有考生的分數(shù)都確定下來，每個考生知道自己的分數(shù)和所有考生的分數(shù)分布。在2004年，北京、上海、重慶、吉林、廣東等5個?。ㄊ校榭记疤顖笾驹?，浙江、四川等十個省市是在得知考試分數(shù)后填報志愿，其他的地區(qū)是在考試結束后的1-2天內填報志愿。目前，知分填報的模式是主要的安排，我們的在本文的分析也是知分填報的模式下的招生制度。 給定全國所有學校在當?shù)氐恼猩媱潱魇≌猩k公室根據(jù)考生的高考成績和填報的志愿，負責組織高等學校的招生工作。高考招生工

16、作的一般流程如下。高考錄取機制：1 每一個想進入大學學習的人員都報名參加統(tǒng)一招生考試，分數(shù)出來后填報自己的志愿。2 根據(jù)全部考生的分數(shù)和各類型學校的總的招生計劃，各省招辦劃定各類型學校的高考分數(shù)線。在目前，學校類型分為本科、?？坪吐殬I(yè)學校，在本科學校中，被分為重點學校，一類本科和二類本科。學校的類型決定了學校在學生偏好中的順序，也決定了錄取學生的順序。 只有考試分數(shù)高過招生錄取分數(shù)線的學生，才有資格被相應類型的學校錄取。同時各省規(guī)定不同加分政策，由加分和考試總分數(shù)得到確定每個學生在錄取時的排序分數(shù)。根據(jù)學校的類型，招生辦公室通過控制批次根據(jù)考生偏好投遞考生的檔案，學校根據(jù)學生的考分排名錄取。3

17、 錄取過程是由省招生辦公室和學校共同完成的，這個過程可以描述如下：第一輪 考慮所有學生的第一志愿。根據(jù)學生的志愿，學生分配到相應的學校。各個學校根據(jù)考生的分數(shù)排序，根據(jù)招生計劃按照分數(shù)從高到低錄取。如果學生數(shù)超過招生計劃，則只錄取成績最高的招生計劃數(shù)學生，其他學生被拒絕。如果學生數(shù)小于招生計劃數(shù)，所有學生都被錄取。第二輪 接下來考慮所有沒有被錄取的學生的第二志愿。這一輪只考慮所有學生的第二志愿，根據(jù)第二志愿送到仍然招生的學校。如果該志愿的學校已經(jīng)招滿人數(shù)，該學生被拒絕。仍有空余名額的學校，根據(jù)第二志愿考生的成績排序后，一次一個從高到底錄取，直到用完所有名額或者所有學生都被招收。依此類推，一般來

18、說第k 輪。考慮所有還沒有被錄取的學生。在第k輪，只考慮所有未被錄取的學生的第k志愿。如果學校還有名額沒有招滿，根據(jù)第k志愿是該學校的學生的錄取成績排序，從高到低一次一個依次錄取，直到學校用完所有的招生名額或者所有的學生都被招收。在這樣的招生方式下，如果一個考生想要被一所學校錄取，他不但要分數(shù)足夠高，也要在填報志愿的時候把這所學校作為他的第一志愿來填寫。如果志愿填寫不恰當，有可能被所有的學校拒絕，雖然分數(shù)較高但是沒有學?？勺x。這時，每個學生有強的動機來操縱自己的偏好，使得他的分數(shù)可以發(fā)揮作用。這時的志愿偏好，就不是學生的真實偏好。在填報志愿的時候，學生的偏好是學校排序和學校內的專業(yè)排序，并且有

19、是否服從學校內專業(yè)調劑選項。這種志愿的填報方式，使得學生對學校和專業(yè)的志愿成為字典序形式的偏好。各省的實際的錄取過程是上面描述的過程的變形。由招生辦公室執(zhí)行學校偏好招收，而由學校來執(zhí)行專業(yè)偏好的招收。當學校執(zhí)行專業(yè)志愿滿足率最大和全校大排行招收的時候，學校志愿和（學校，專業(yè)）志愿的執(zhí)行一致。此外，各學校在招生的時候也是按照專業(yè)計劃招生人數(shù)來執(zhí)行招生，并且學校在招生后不分專業(yè)培養(yǎng)，因此，學校排序志愿和（學校，專業(yè)）志愿是一致的。我們在下文中不區(qū)分學校和（學校，專業(yè)），統(tǒng)一稱為學校。下面我們用符號來表示，一個高考招生問題由以下幾部分構成： 1 所有考生的集合 ； 2 所有學校的集合 ；3 一個招生

20、計劃人數(shù)向量 ，其中是學校的計劃招生人數(shù)；4 每個學生高考錄取分數(shù)的向量，其中是學生的高考分數(shù)和規(guī)定的加分后的錄取分數(shù)。我們假設考生的考分沒有相同的。在實際中考生的總分有大量的相同，但是可以使用一定的規(guī)則在總分相同的情況下額外排序，如是否有加分，單科成績優(yōu)先等方式。這樣，任意的，都有，所有的考生的錄取分數(shù)就得到一個完全的排序。5 學生的嚴格排序集合。每一個學生都在集合上有一個嚴格的偏好，這里表示不上大學的選擇，我們規(guī)定，表示不上大學的選擇可以容納所有的學生。我們用集合表示上所有嚴格偏好序的集合。是對任何由排序得到至少一樣好排序，即對于,我們有，當且僅當或者。如果，我們就說對于學生學校是可接受的

21、。對所有的，我們用表示除去學生外其它所有學生的偏好。在下面的文章中，和都是固定的，這樣，給定一個招生計劃，高考錄取成績和學生偏好的三元組就得到了大學招生的基本要素，我們稱其為一個高考招生問題。高考招生的目的就是給定三元組通過標準化統(tǒng)一考試成績和招生程序，使學生和學校配合，由于不能使的每個學生都被自己最偏好的大學錄取，因此高考招生制度根據(jù)學生的偏好和考試成績對學生的偏好進行滿足和選擇能夠進入大學學習的學生。我們把招生的結果稱為匹配。一個匹配（match）就把學校分配到所有考生的一個方案，方案中一個考生最多能夠得到一個大學的入學名額，每個大學招收的人數(shù)不超過它的招生計劃。形式上，一個匹配就是一個函

22、數(shù)使得對所有的，有，這表示大學招生不超過它的計劃。如果，就表示學生沒有被任何大學錄取。所有匹配的集合記為。學生的偏好是定義在，我們可以把它擴展到匹配的集合上：學生偏好匹配超過匹配，當且僅當，在下文中，我們仍用表示這個擴展了的偏好。一個匹配是個人理性的，如果對于所有的學生，不會被分配給比寧愿不上學還差的大學。對于所有的學生，他得到的學校都是可接受的。用符號來表示，就是對于所有的，我們都有。一個匹配被稱為是沒有浪費的，如果有一個學生偏好另一所學校而不是錄取他的學校，那么另一所學校必定已經(jīng)招滿了學生。用符號表示，就是對任意的和，如果，那么必然有。一個匹配帕累托占優(yōu)另一個匹配，如果所有的學生都不偏好超

23、過，而有些學生偏好超過。用符號來表示，匹配帕累托占優(yōu)匹配，如果對所有的，我們都有,存在，有。一個匹配是帕累托有效，如果不存在匹配帕累托占優(yōu)匹配。我們可以注意到，一個匹配是帕累托有效的，必然是個人理性并且沒有浪費的。在高考錄取中，分數(shù)高低決定了學生在學校錄取時的排序。balinski等（1999）分析土耳其的招生制度時，引入了分數(shù)公平的概念。一個匹配被稱為是公平的（fair），如果有一個學生偏好另一所學校超過錄取他的學校，那么另一所學校已經(jīng)招滿了學生而且所有的學生的分數(shù)都高于這個學生。用符號表示，就是對任意的和，如果，那么必然有，而且對任意的，必然有。公平匹配有如下的結構：定理1（michel

24、balinski；tayfun snmez,3) 一個匹配是公平的，當且僅當對每個學校存在一個最低分數(shù)線，對所有的學生和學校，如下的條件成立： 1） 如果，必然有； 2） 如果，必然有在公平的匹配中，一個學生不能被他喜歡的學校錄取，是由于這個學校已經(jīng)錄取的學生的成績都高于這個學生，這個性質反映了學生在分數(shù)面前的公平性，這個分數(shù)的公平性，也體現(xiàn)在實際錄取中學校和政府負責部門的要求中。一個機制（mechanism）就是一個系統(tǒng)的程序，對于每個給定的三元組，得到一個學生和學校的匹配。一個機制稱為直接機制，如果它需要每個學生報告他的偏好。一個機制是帕累托有效的，如果它對每個招生問題給出的匹配都是帕累托

25、有效的匹配。一個機制是公平的，如果對每一個高考問題的匹配結果都是公平的。三、高考招生博弈高考招生的結果就是一個學生和學校的匹配，這個匹配是通過我們上面描述的高考招生機制達到的。從機制設計的角度，對于每個學生，我們用表示學生的信號集合，用表示所有學生的信號空間，其中的每一個元素都是形如,這里對應學生的信號，是所有學生信號的組合的集合。從信號空間到匹配的函數(shù)稱為結果函數(shù)。任何信號空間和結果函數(shù)的二元組稱為稱為一個機制。如果每個學生的信號空間是上的所有嚴格偏好集合，這個機制就稱為直接機制。這樣，給定一個招生計劃，高考錄取成績和學生偏好的三元組，給定一個機制，就得到了一個考生的博弈。在實際的高考中，考

26、生向招生負責辦公室填報志愿，就是在一個直接機制里顯示自己的偏好。由于考生知道考分和填報志愿的時間不同，共有三種不同的信息結構。在考前報考的模式下，考生的信息只是自己的偏好。在估分報考的模式下，考生的信息是自己的偏好和對自己分數(shù)估計，而在考后成績出來報考的模式下，考生的信息是自己的偏好和所有考生的成績。我們在這里考慮知道分數(shù)時的報考博弈，這時所有學生的考分是公共信息，高考的志愿填報成了一個顯示偏好的博弈。下文我們將證明，在gale-shapley學生最優(yōu)機制下，三種填報模式中真實顯示自己的偏好都是學生的占優(yōu)策略。在知分報考的模式下，給定三元組和一個直接機制 ,就得到了考生間的一個博弈。每個考生的

27、純策略集合是信號集合，也是上的所有嚴格偏好集合。我們允許混合策略存在，每個考生的混合策略是表示上的所有嚴格偏好集合上的概率分布。這樣，高考志愿填報博弈就是，（，）。這里我們分析完全信息情況，所有考生的真實偏好是共同知識，在知分報考時每個考生也知道所有考生的考分。這個博弈的順序如下：首先，考試分數(shù)確定，進入填報志愿階段，所有考生同時行動。我們每個考生向招生辦公室報告一個偏好，不一定是他的真實偏好，所有人的信號組合就是信號空間的一個元素。接著，根據(jù)考生填報的志愿順序，招生辦公室和學校根據(jù)按照前面描述的機制進行錄取，得到最后的匹配。我們定義這個博弈的一個純策略納什均衡為，如果對所有的, 都有 ，對任

28、意的，表示學生均衡時的匹配，是給定其他人的均衡策略時學生填報按照高考招生機制得到的匹配。在納什均衡的時候，每個參與人填報志愿都是對其他人填報的志愿的最優(yōu)反應，每個人都不能單方面改善他的匹配。我們假設每個考生都是預期效用最大化，類似通常的做法，我們可以定義這個博弈的混合策略納什均衡。 在這個有百萬人參與的直接博弈中，每個人都尋求最優(yōu)的策略，努力使他的高考分數(shù)發(fā)揮最大的作用。我們在高考的實際招生中，看到許多高分落榜和學校沒有招滿的現(xiàn)象，是否在這個博弈中沒有均衡結果導致了這些現(xiàn)象。我們有如下的結果：定理2 在高考博弈，（，）的納什均衡是存在的。 證明：由于每個考生的純策略是對學校的嚴格偏好，由于學校

29、的數(shù)目是有限的，因而嚴格偏好也是有限的。同時，考生的數(shù)目是有限的。因此，這是一個有限博弈。根據(jù)納什定理，任何有限博弈都是存在均衡的（可能是混合策略均衡）。 雖然這個博弈存在均衡，但是我們更加關心是否存在純策略的均衡。顯然，混合策略的均衡不是一個很好的結果。在后邊我們將知道，確實存在純策略的均衡。這里，我們證明所有純策略均衡的均衡結果是相同的。定理3 在高考博弈，（，）中，純策略納什均衡結果是唯一的：令，是納什均衡，則證明：（1）如果一個匹配是均衡的匹配結果，它必然是個人理性的。否則，存在，有。這里，是在均衡時學生的策略，他的真實的偏好是，是除學生外其他所有人的策略。給定其他人的策略不變，學生的

30、策略變?yōu)槠?，偏好把選擇作為學生的第一志愿。在偏好組下，高考機制的結果必然有，這樣我們就得到 。這和匹配是均衡匹配結果相矛盾。（2）如果一個匹配是均衡的匹配結果，它必然是公平的。如果匹配不是公平的，那么存在和，有，或者或者存在，有。這里，是在均衡時學生的策略，他的真實的偏好是，是除學生外其他所有人的策略。給定其他人的策略不變，學生的策略變?yōu)槠?，偏好把學校作為學生的第一志愿。在偏好組下，高考機制的結果必然有這樣我們就得到 。這和是納什均衡結果矛盾。因此均衡結果必然是公平的。（3）如果，則存在兩個均衡，并且。必然存在，我們有，不妨設，這是根據(jù)偏好的嚴格性得來的。令，由于是公平的，我們必然有對于任

31、意的，并且。由于是公平的，我們必然對于任意的，有，不然就違反公平性。由于在中可以有個人被學校錄取，我們必然有，而且。由于偏好是嚴格的，我們必然有；這樣我們得到，且。對于任意的，和上面同樣的推理我們可以得到，并且。這個推理可以一直進行下去，這和學生人數(shù)有限相矛盾，因此前提不成立，只有一個納什均衡結果。 上面的定理表明，在知分報考的高考博弈中，博弈的純策略均衡結果是唯一的，這個結果是公平的。但是這個博弈的均衡策略不一定唯一，并且真實策略并不一定均衡策略。我們用下面的例子說明高考招生的過程和高考博弈。例： 這里有三個學生和兩所學校，表示不上學。每個學校的招生名額，學生的成績和偏好如下 如果考生都真實

32、的申報自己的志愿，在高考機制的錄取結果是：第一輪，考慮所有學生的第一志愿，學生投檔到學校，學生被投檔到學校。學校按照考分從低到高錄取。學校錄取學生，學生被拒絕；學生被學校錄取。兩所學校都用完了招生名額。第二輪 考慮沒有被錄取的學生的第二志愿。但是所有的學校都已經(jīng)錄取滿額，錄取結束，高考落榜。這樣，學生真實申報志愿的錄取結果是。但是真實申報志愿不是的最優(yōu)策略。給定其他人的真實志愿，可以填報，這樣錄取的結果是。可以驗證，志愿組合是一個納什均衡。在這個簡單的高考博弈中，所有的純策略納什均衡為志愿組合，其中的志愿是任意一個排列。所有這些納什均衡的結果都是。 上面的例子表明，在知分報考的高考博弈中，博弈

33、的純策略均衡結果是唯一的，這個結果是公平的。但是這個博弈的均衡策略不唯一，并且真實策略并不是均衡策略，這樣，協(xié)調到均衡就是一個艱巨的任務。在實際報考中也存在協(xié)調的努力，各學校，各市都舉辦考前志愿預報來協(xié)調本地區(qū)考生之間的志愿，避免報考志愿的過度集中。這些協(xié)調的規(guī)模與實際招生的規(guī)模相比很小，每個考生也仍然很難調整到均衡的策略。是否存在一種招生機制，使得每個學生的真實偏好是他的均衡策略呢？仍然以上面的例子，我們介紹下面的galeshapley學生最優(yōu)機制，在所有考生真實申報自己的偏好的情況時，可以達到當前的高考同樣的均衡結果。gale-shapley學生最優(yōu)機制：第一輪，所有學生向可接受的學校中的

34、第一志愿申請，學生投檔到學校，學生投檔到學校。學校按照考分從高到低錄取。學生被學校預錄取，學生被拒絕；學生被學校預錄取。兩所學校都用完了招生名額。第二輪 考慮上一輪被拒絕的學生，向沒有拒絕過他的可接受的學校中最偏好的學校申請。學生向學校申請。學校考慮新的學生和上一輪預錄取的學生，學生被拒絕，被學校預錄取。學校沒有申請的學生。第三輪 考慮上一輪被拒絕的學生。但是學生沒有可接受的學校，停止申請。沒有學校拒絕申請，學校錄取程序結束。在學校預錄取名單上的學生被正式錄取，沒有被任何學校錄取的學生落榜。最后的錄取結果是：。 我們看到上面的招生機制在所有考生真是顯示偏好的情況下，達到了和高考同樣的招生結果。

35、并且，我們在下面證明，在這種機制下每個考生真實顯示自己的偏好是他的占優(yōu)策略。四、galeshapley學生最優(yōu)機制大學招生模型（gale&shapley,1962）由組成，包括一組學生和一組學校的集合 ，每個學校有固定的招生人數(shù)向量 。每一個學生對所有學校和不上學的選擇有一個嚴格的偏好，同時，每個學校有一個對學生集合的嚴格偏好 關于學校的偏好討論，參見roth(1985)7。，這里，學校對所有學生組合包括空集的偏好，是定義在學生集合的子集上。對于任何，我們令表示其他學校的偏好。我們用和表示分別和相應的非嚴格偏好。在下文中，我們固定學生和學校的集合和。高考和大學招生模型有著一個重要的不同之處：在

36、大學招生模型中，學生和學校都是參與人，他們同時可以策略的表示自己的偏好。而在高考制度中，大學按照學生的考分高低錄取學生，幾乎沒有自己的選擇，大學是所有學生共同擁有的公共資源，按照考分高低和學生的志愿分配到學生，這里只有學生是積極行動的參與人。但是，我們可以通過考生的分數(shù)構造每個大學的偏好，就把高考問題轉化相應的大學招生模型。因為考生在學校的錄取是由他的考分排序決定的，給定一個高考我們通過考生的分數(shù)可以構造大學的偏好。對于所有的大學，它的偏好滿足：對所有的，當且僅當，并且對所有的，。這里，表示一個學生也不錄取的選擇。這樣，在高考相應的大學招生模型中所有的學校對考生有相同的偏好。 同樣，前面定義的

37、匹配和個人理性的概念仍適用于大學招生模型。在高考博弈中，高考招生程序對于給定的得到一個學生和學校的匹配方案。這里，一個機制就是一組程序，對于給定的大學招生問題得到一個學生和學校的匹配方案。在大學招生模型中，一個非常重要的概念是穩(wěn)定性（stable）。一個學生和學校的組合破壞（block）了一個匹配，如果：，并且；或者，并且存在，。如果一個匹配是個人理性的，并且不會被任何學生和學校的組合破壞，那么這個匹配是穩(wěn)定的。由定義我們看到穩(wěn)定性和公平有很大的關聯(lián)，一個匹配是穩(wěn)定的當且僅當它是個人理性的，沒有浪費和公平的。從我們前面的證明可知，高考博弈的納什均衡結果是一個穩(wěn)定的匹配。 gale和shaple

38、y（1962）證明了穩(wěn)定的匹配總是存在的，并且在所有的穩(wěn)定匹配中，存在一個匹配對于學生來說是帕累托最優(yōu)的，他們并提出了如下達到學生最優(yōu)匹配的機制，這個機制可以通過延遲接受學生申請機制達到。galeshapley學生最優(yōu)機制：第1輪 所有的學生向他接受的大學中的第一志愿學校申請。每一所大學從所有申請的學生中留下最好的個學生，其他的學生都被拒絕，進入下一輪申請。被留下的個學生計入預錄名單。如果申請學生不足個，就預錄所有的學生。第2輪 所有被拒絕的學生向他可接受并且沒有拒絕過他的大學中的最好的志愿學校申請。每一所大學考慮所有本輪申請的學生和上一輪留在預錄名單上的學生，從中留下最好的個學生，拒絕其他學

39、生。被拒絕的學生進入下一輪申請，留下的個學生計入預錄名單。一般來說，第k輪 所有在上一輪被拒絕的學生向他可接受并且沒有拒絕過他的大學中的最好的志愿學校申請。如果沒有可接受的學校，這各學生就停止申請。每一所大學考慮本輪所有申請的學生和上一輪留在預錄名單上的學生，從中留下最好的個學生，拒絕其他學生。被拒絕的學生進入下一輪申請，留下的個學生計入預錄名單。當沒有學生的申請被拒絕的時候，這個錄取程序就停止。由于學生和學校的數(shù)目有限這個過程一定會在有限步后停止，所有留在預錄名單上的學生就被學校正式錄取。如果一個學生被所有的學校拒絕，那么這個學生就落榜了。通過galeshapley學生最優(yōu)機制可以達到學生最

40、優(yōu)的穩(wěn)定匹配，我們在前文的例子中已經(jīng)見到這一點。在高考招生對應的特殊的大學招生模型中，所有的學校的偏好都相同。這時，只存在唯一的穩(wěn)定匹配。為了說明這一點，我們在前面已經(jīng)得到高考機制的納什博弈均衡結果是一個穩(wěn)定匹配。反過來，每一個穩(wěn)定的匹配都是一個納什均衡結果。定理4： 每一個穩(wěn)定的匹配都可以作為一個高考機制的均衡結果。證明: 設是一個穩(wěn)定的匹配，我們考慮如下的策略組合，其中學生的策略把他的匹配作為第一志愿，其他的學校都不可接受。這時，通過高考機制我們必然有。對于學生如果存在一個策略使得，這里是學生的真實偏好，必然有或者存在，但這和匹配穩(wěn)定矛盾。結合我們證明的高考博弈結果的唯一性，我們得到在高考

41、問題對應的大學招生模型中穩(wěn)定的匹配是唯一的。通過高考博弈的均衡和galeshapley學生最優(yōu)機制，我們都可以達到這個穩(wěn)定匹配。在galeshapley大學招生模型中，與學生最優(yōu)機制相應的還有大學最優(yōu)機制，這個機制和學生最優(yōu)機制的不同在于每一輪中是大學申請，由考生決定學校是否可以接受。gale和shapley（1962）證明學生最優(yōu)機制和學校最優(yōu)機制都可以達到穩(wěn)定的匹配。由于這里穩(wěn)定匹配集合的唯一性，我們知道galeshapley學校最優(yōu)機制也可以達到相同的穩(wěn)定匹配。這個機制也可以如下進行，現(xiàn)把所有考生按分數(shù)從高到低排序，然后從高分到低分一次一個依次錄取。第一個考生從所有招生學校中，選擇他最偏

42、好的學校。如果一個學校已經(jīng)招滿，就停止招生。一般來說，第k個考生從所有仍招生的學校中選擇他最偏好的學校，如果沒有愿意的學校，他選擇不上學。這樣下去，直到所有的考生都輪完或者所有的學校的招生名額用完，招生停止，剩下的考生落榜。這個招生機制也是北京市中考錄取的機制。但是和高考博弈相比，galeshapley學生最優(yōu)機制還有一些吸引人的特征：定理 5（dubins 和freedman12,;roth11）galeshapley學生最優(yōu)機制是strategyproof.在高考博弈中，每個人很難知道在這個博弈中自己的最優(yōu)策略是什么；在galeshapley學生最優(yōu)機制下，每個人的真實偏好就是他的占優(yōu)策略

43、，填報自己真實的偏好得到的結果不比任何其他的志愿來得差。在galeshapley學生最優(yōu)機制下，考生不需要擔心他由于填報志愿不當而喪失了他的考分的優(yōu)先性。這樣，就沒有考前，考后和估計分數(shù)報考的區(qū)別，考生的志愿和考試分數(shù)分開，使得考分真正的發(fā)揮分配的作用。在高考招生中，分數(shù)的面前的公平性是實際操作中基本要求，考分高的學生有更大的優(yōu)先性錄取到偏好的學校。高考招生博弈的均衡是公平的，但我們也有：定理 6（gale&shapley1，michel balinski;tayfun,snmez3）galeshapley學生最優(yōu)機制帕累托占優(yōu)任何公平機制。 這個定理得含義是給定一個招生問題，任何產生最后錄取

44、結果是公平匹配的機制得到結果都不會帕累托占優(yōu)按照galeshapley學生最優(yōu)機制錄取得到的結果。我們前文中的例子已經(jīng)看到，高考招生博弈的納什均衡結果和galeshapley學生最優(yōu)機制錄取得到的結果一致就是這個定理得一個說明，并且這個性質對于任何的公平機制都是成立的。因此，gale-shapley 學生最優(yōu)機制帕累托占優(yōu)當前的高考錄取機制。定理 7 (alcalde&barbera13)在大學招生問題中，gale-shapley學生最優(yōu)機制是唯一的個人理性，沒有浪費和公平，strategyproof的學生錄取機制。 這個定理刻畫了在大學招生問題中galeshapley學生最優(yōu)機制的唯一性。任

45、何要做到使得錄取結果滿足個人理性，沒有浪費和分數(shù)公平，并且考生真實申報自己的學校偏好是占優(yōu)策略的機制只能是galeshapley學生最優(yōu)機制。分數(shù)的公平性，一方面是在在高考錄取過程中，一個學生的考分是他能否被學校錄取的重要指標。公平性的另一方面，是學生錄取機制應當尊重學生的考分，當一個學生的考分提高時，他所能達到的學校不會比他分數(shù)低時所能達到的學校還差。這樣的機制就是尊重考分的機制。同樣，gale-shapley學生最優(yōu)機制具有這樣的優(yōu)點：定理 8：（balinski, michel; snmez, tayfun3）唯一的尊重學生考分進步，并且滿足個人理性，沒有浪費和公平的學生錄取機制是gal

46、e-shapley 學生最優(yōu)機制。 以上這些定理表明，如果高考制度仍然是用統(tǒng)一考試和分數(shù)公平來決定錄取，gale-shapley 學生最優(yōu)機制具有許多有些性質優(yōu)于當前的高考錄取機制。五、總結 在高考的分數(shù)公平原則下，由于錄取機制的第一志愿優(yōu)先，使得高考的錄取成了一個幾百完考生參加的協(xié)調博弈。雖然存在唯一的均衡結果，但考生的真實偏好并不總是他的均衡策略，多重均衡和巨大的參與人數(shù)使得如何協(xié)調到一個均衡對所有考生都幾乎不可能的事情。使用galeshapley學生最優(yōu)機制可以達到同樣的錄取結果。與當前的高考錄取制度相比，galeshapley學生最優(yōu)機制具有一系列的優(yōu)良性質，而且這個機制也已經(jīng)在實踐中

47、被使用（roth）。在galeshapley學生最優(yōu)機制的錄取機制下，考生的真實偏好是他的占優(yōu)策略，這個機制是唯一的滿足個人理性，沒有浪費和分數(shù)公平，并且尊重考生分數(shù)進步的學生錄取機制。滿足學生的真實志愿，是進一步最求知識的動力。如果改革錄取方式，必然帶來巨大的效率改進，省卻無數(shù)家庭的煩惱和焦慮。參考文獻：1 gale, david; shapley,lloyd, college admissions and the stability of marriage j. american mathematical monthly, 1962, 69(1): 9-152 roth, a. e.,sotomayor, m., two-sided matching: a study in game theoretic modeling and analysis m, cambridge univ. press, london/new york, 1