1、成績（采用四級記分制） 本科畢業(yè)論文（設(shè)計）題目：匹配市場原理研究與算法實現(xiàn)學(xué)生姓名 學(xué) 號 指導(dǎo)教師 院 系 專 業(yè) 年 級 教務(wù)處制誠信聲明本人鄭重聲明：本人所呈交的畢業(yè)論文（設(shè)計），是在導(dǎo)師的指導(dǎo)下獨立進行研究所取得的成果。畢業(yè)論文（設(shè)計）中凡引用他人已經(jīng)發(fā)表或未發(fā)表的成果、數(shù)據(jù)、觀點等，均已明確注明出處。除文中已經(jīng)注明引用的內(nèi)容外，不包含任何其他個人或集體已經(jīng)發(fā)表或在網(wǎng)上發(fā)表的論文。特此聲明。論文作者簽名： 日 期： 2013年6月1日摘 要匹配市場理論是博弈論在經(jīng)濟學(xué)中的應(yīng)用，在雙向選擇問題領(lǐng)域應(yīng)用廣泛，該理論對參與市場匹配的雙方具有指導(dǎo)意義。該理論可以應(yīng)用在投標報價、城市地下空間規(guī)

2、劃、公眾聚集場所的消防工作部署、供應(yīng)鏈的利潤分配、商品住宅定價、信貸市場、自主招生擇校、畢業(yè)生勞動市場、證券交易、器官交易、醫(yī)療保險計劃等等問題。本文研究了匹配市場理論的基本原理，并展開分析了匹配市場理論在工作市場中用人單位與應(yīng)聘者間的匹配問題、高考錄取市場的高校與考生間的匹配問題。最后，在理論分析的基礎(chǔ)上，用程序模擬實現(xiàn)了整個市場匹配算法。關(guān)鍵詞：匹配市場：博弈論；匹配市場的應(yīng)用 AbstractMatch Market Theory is Game Theory in economics; it has a very important role to the parties involv

3、ed in matching the market as well as a wide range of application of problem areas in the two-way choice. It can be applied in the tender offer, urban underground space planning, public gathering places for fire work arrangements, supply chain profit distribution, commercial housing choice, graduate

4、labor market, securities trading and organ trading, health care insurance pans and so on. In this paper, the basic principle of matching market theory and market theory to analyze the match in the job market between the employer and the candidate matching problem, university and college admission ma

5、rket matching problem between the candidates have been discussed. Finally, we program it, based on theoretical analysis.Keywords：Match Market Theory； Game Theory; the application of Match Market Theory 序言經(jīng)濟學(xué)是研究人類行為以及如何將有限或者是稀缺的資源進行有效合理的配置的一門社會學(xué)科。傳統(tǒng)的經(jīng)濟學(xué)長期以來解決的是稀缺資源配置“靜態(tài)均衡”的比較研究。隨著社會、經(jīng)濟的發(fā)展，該類研究已經(jīng)無法滿足學(xué)

6、者們對資源配置問題的探索以及無法有效解決稀缺資源配置問題中遇到的問題，因此，學(xué)者們自20世紀以來，開始逐漸由這種“靜態(tài)均衡”的研究轉(zhuǎn)向資源配置問題中的“黑匣子”的研究，從而達到稀缺資源配置的“動態(tài)均衡”，這就產(chǎn)生了匹配理論。該理論是博弈論的一個分支，最先對匹配理論進行研究的是Gale和Shapley在他們1962年發(fā)表的大學(xué)錄取和婚姻的穩(wěn)定性一文，目前，經(jīng)過近五十年的發(fā)展，匹配理論在西方國家的勞動力市場和公共學(xué)校的擇校問題中已經(jīng)得到了廣泛的運用。我國傳統(tǒng)的統(tǒng)考統(tǒng)招自從1979年恢復(fù)高考以來，已經(jīng)運行了30多年，但是由于招生環(huán)境的復(fù)雜性的存在，使得統(tǒng)考統(tǒng)招存在很多的弊病，諸如“一考定終身”、學(xué)校

7、招生自主性弱等等。因此，國家與2001年提出并開始實行并且逐步推廣了一種新的招生機制自主招生擇校機制。然而，在這新興的自主招生擇校機制中仍然存在諸多問題：如“腳踏兩只船”、“另覓高枝”等現(xiàn)象普遍存在。因此，利用匹配理論對該機制進行研究進而進一步指導(dǎo)參與者行為將有很大的實際價值。1 匹配市場簡介1.1 博弈論簡介匹配市場其實就是博弈論思想在經(jīng)濟學(xué)方面的實際應(yīng)用。博弈論（Game Theory），博弈論是指研究多個個體或者團隊之間在特定條件制約下的對局中利用相關(guān)方的策略，而實施對應(yīng)策略的學(xué)科。有時也稱為對策論，或者賽局理論，是研究具有斗爭或競爭性質(zhì)現(xiàn)象的理論和方法。 1.2 穩(wěn)定匹配理論：匹配市場

8、在很多市場上，貨物是私人的，但他們是不可分割和非同性質(zhì)的，因此傳統(tǒng)假定的充分競爭條件并不滿足。如熟練技工市場，由于沒有兩名特征完全相同的技術(shù)工人，特定工種的技術(shù)工人服務(wù)市場相當(dāng)小。在這些市場中，參與者通過相互交換實現(xiàn)大致的匹配。1.2.1 雙向匹配假設(shè)有兩組市場，參與者是相互分離的，如買方、工人、學(xué)生和賣方、雇主、學(xué)校，他們必須匹配，然后才能履行相應(yīng)的職能。1962年，蓋爾和沙普利對雙向匹配市場進行了研究，他們排除了單邊支付（私下交易）情形，認為工資以及其他匹配特征并非通過協(xié)商完成的。1.2.2 穩(wěn)定匹配具體來說，假定市場是由一方是醫(yī)學(xué)院學(xué)生和另一方是醫(yī)院科室構(gòu)成，每個醫(yī)院科室只需要一名實習(xí)醫(yī)

9、生，而每名醫(yī)學(xué)院學(xué)生只需要一個實習(xí)機會。匹配就是將實習(xí)機會分配給申請的學(xué)生。很自然，學(xué)生對科室偏好不同，科室對不同學(xué)生偏好也不同。為了方便研究，假定偏好是嚴格的，當(dāng)參與者匹配后狀況惡化則匹配將不被接受。一般而言，當(dāng)不能通過聯(lián)盟改進參與者效用時，匹配就是穩(wěn)定的。在這個特定的模型中，一個穩(wěn)定的匹配必須滿足一下兩個條件：沒有參與者認為這個匹配不可接受，沒有科室和學(xué)生聯(lián)盟希望重新匹配而不愿保持現(xiàn)狀。第一個條件是個人理性條件，而第二個條件則是指成對匹配是穩(wěn)定的。這兩個條件暗示著沒有任何聯(lián)盟和“科室-學(xué)生”組合可以對匹配進行改進。1.2.3 可調(diào)整的價格與工資沙普利等人認為分配博弈的核心并非空集，匹配競爭

10、對一系列核心配置形成了嚴格限制。通過可轉(zhuǎn)移效用，任何核心配置必須滿足經(jīng)濟剩余最大化目標。總之，這種匹配是唯一的。然而，工資通常不是單一決定的，會產(chǎn)生利益的兩極分化。當(dāng)雇主最優(yōu)或者工人最優(yōu)穩(wěn)定匹配時，相應(yīng)的特征是市場以最低工資或最高工資水平出清。分配博弈緊扣自由競爭概念傳承了傳統(tǒng)的競爭分析，事實上，這個模型是連接核心理念與競爭均衡間的橋梁。研究發(fā)現(xiàn)，在雇主發(fā)起機制下，每個雇主開始都想聘用的求職者報出低工資，每個求職者都收到多分聘書，將滿意的通知保留，其他的予以拒絕。遭到拒絕的雇主繼續(xù)發(fā)放聘書，要么對原來的求職者提高待遇，要么向新求職者發(fā)放聘書。這個過程最終會實現(xiàn)雇主最優(yōu)的穩(wěn)定匹配。1.3 匹配市

11、場的場景 ·某一類商品（例如房子），一群買房和一群賣方，賣方和買方數(shù)量相同 ·商品的質(zhì)量不同，大家的認識也有差別 ·買方對商品各有一個低價，都追求利益最大化 ·市場按照供需關(guān)系自動調(diào)整價格，試圖達成買賣雙方的某種匹配 ·我們關(guān)心最終能否大家都滿意 -賣方：市場清倉，商品在底價之上都賣出去了 -買方：得到差價最大的商品1.4 匹配市場基本模型匹配市場的基本模型：二部圖偏好賣家圖 調(diào)整價格后的偏好賣家圖1.5 匹配市場操作的一般過程第一步，初始價格為0，形成偏好賣家圖，看其中是否存在一個買家受限組：第二步，與受限買家關(guān)聯(lián)的賣家調(diào)整價格，形成新的偏好

12、賣家圖，再看是否存在買家受限組：第三步，與受限買家關(guān)聯(lián)的賣家調(diào)整價格，形成新的偏好賣家圖，再看是否存在買家受限組：第四步，與受限買家關(guān)聯(lián)的賣家調(diào)整價格，形成新的偏好賣家圖，此時已經(jīng)沒有受限組，即存在完美匹配：此時，實現(xiàn)了最大估值之和，即實現(xiàn)了社會最優(yōu)。1.5 市場清倉價格算法以上過程其實可以看成是計算市場清倉價格的算法，可以歸納如下：給定買方估值，賣方從初始價格（0，0，0）開始，按照輪次進行下屬操作：a. 構(gòu)造偏好賣家圖b. 識別是否存在買方受限組（S）。若沒有，則偏好賣家圖存在完美匹配，結(jié)束；否則，將受限組對應(yīng)的賣方集合N（S）中的價格都+1.若因此使得所有賣方價格都大于0，則統(tǒng)一約減最低

13、價至0。c. 開始下一輪。（統(tǒng)一約減不影響偏好賣家圖關(guān)系）因為市場勢能每一輪都是單點遞減的，但總不會小于0，因此上述過程是一定能結(jié)束的。所以始終存在完美匹配的偏好賣家圖，不會出現(xiàn)來回“震蕩”的情況。2 匹配市場的應(yīng)用匹配市場有著很廣泛的應(yīng)用，如：投標報價、城市地下空間規(guī)劃、公眾聚集場所的消防工作部署、供應(yīng)鏈的利潤分配、商品住宅定價、信貸市場、自主招生擇校、畢業(yè)生勞動市場、證券交易、器官交易、醫(yī)療保險計劃等等。可以說，生活中任何涉及到雙方選擇的問題都可以利用匹配市場理論來解決。這些都是現(xiàn)實生活中非常重要的問題，由此我們也可以看出諾貝爾獎委員會希望以經(jīng)濟學(xué)推動社會發(fā)展的良苦用心。2.1 就業(yè)市場中

14、的實際應(yīng)用假定應(yīng)聘者數(shù)目和用人單位數(shù)目相等，各自對對方有明確的偏好或者說排名，而且只能一一配對。以應(yīng)聘者為主動方來構(gòu)造匹配市場模型，假設(shè)有四家用人單位以及四個求職者，求職者a，b，c，d對用人單位A，B，C，D的估值分別為（2，9，6，3）、（8，1，4，6）、（5，3，7，2）、（9，6，4，1）。經(jīng)過1.5小節(jié)中市場清倉價格算法運算后可得到完美匹配圖如下：由此我們可知，求職者a選B公司，b選D公司，c選C公司，d選A公司是比較合適的。按這個算法，雙方一定能一次性達成穩(wěn)定的組合，絕不會發(fā)生配對之后求職者覺得另一所用人單位更好、同時那所用人單位也覺得這個求職者更好，于是兩情相悅跳槽的情況；也絕

15、不會有剩下沒人要的用人單位或者求職者。這個辦法的結(jié)果必然是穩(wěn)定的，但是不能保證所有參與的人都挑選到他的第一選擇。那么總有相對占便宜和相對吃虧的一方。該算法指出，主動的一方總是能得到較好的結(jié)果。其實，在相互選擇，確定最優(yōu)匹配圖后，會出現(xiàn)結(jié)果不為一的情況。這是由哪一方主動選擇造成的。同時，利用匹配市場主動地一方能得到較好的結(jié)果這一特性，我們也可以用之于對弱勢群體的保護，如：學(xué)校自主招生時候讓學(xué)生來做主動的一方，器官捐獻時，讓病人來做主動的一方。2.1 自主招生中的實際應(yīng)用假設(shè)有按學(xué)習(xí)成績從高到低排列的學(xué)生a、b、c，d，e，f，按公眾心中排名由高到低的學(xué)校A，B，C，D，E，F(xiàn)。學(xué)校自主招生名額均

16、為1，若學(xué)生通過自主招生考試則獲得擬錄取資格，則其在報考志愿時如果選擇獲得擬錄取資格的學(xué)校，則其成績相應(yīng)上升一檔。同時，自主招生考試也是學(xué)校獲得對學(xué)生水平的估值的途徑。 現(xiàn)假設(shè)自主招生時學(xué)校采取主動（現(xiàn)實中也確實是這樣的）。自主招生后，A學(xué)校對學(xué)生a，b，c，d，e，f的估值分別（7，8，6，3，8，2），B學(xué)校對學(xué)生a，b，c，d，e，f的估值分別為（8，5，4，6，1，8），依此類推，偏好賣家圖如下：假設(shè)只有b通過了A學(xué)校的自主招生考試，則其在A學(xué)校的估值加一，也就是說A學(xué)校對學(xué)生a，b，c，d，e，f的估值變?yōu)椋?，9，6，3，8，2），偏好賣家圖變?yōu)椋鹤詈螅?.5節(jié)市場清倉算法可得出

17、，完美匹配圖如下：則可知，當(dāng)A學(xué)校選擇e學(xué)生，B學(xué)校選擇f學(xué)生，C學(xué)校選擇c學(xué)生時會形成完美匹配，即不會發(fā)生學(xué)校覺得哪個學(xué)生更好、同時學(xué)生也覺得該學(xué)校更好，從而兩廂情悅發(fā)生跳槽的事情。若把學(xué)生自主招生的成績作為一個標準來看，那么由此，可以給學(xué)校招生時分數(shù)定義做出指導(dǎo)。若是學(xué)生采取主動的方式，則可對學(xué)生選取學(xué)校的標準做出指導(dǎo)。由匹配市場的特性可知，本假設(shè)是由學(xué)校采取主動的方式，因此對學(xué)校是有利的，由此可以看出，處于社會主義初級階段的中國在該方面是不夠成熟的，由弱勢群體學(xué)生來采取主動的自主招生將會是以后的主流。3 匹配市場原理實現(xiàn) 估值矩陣為：12，4，2 8，7，6 7，5，2 時，程序運行結(jié)果

18、如下： 估值矩陣為：2，9，6，3 8，1，4，6 5，3，7，29，6，4，1 時，程序運行結(jié)果如下： 估值矩陣為：7，9，6，3，8，2 8，5，4，6，1，8 5，3，7，2，6，76，4，1，2，6，38，4，5，2，1，66，3，2，9，7，4 時，程序運行結(jié)果如下：總結(jié)與展望盡管沙普利和羅斯的穩(wěn)定理論及市場設(shè)計實踐并不如金融市場的泡沫理論、套利理論般炙手可熱，但從克服市場失靈，提升資源配置效率角度看，這些理論及其應(yīng)用具有巨大現(xiàn)實意義和深遠的影響，尤其是對像中國這樣的發(fā)展中國家更是如此。致謝在本人畢業(yè)設(shè)計的完成和論文的撰寫中，指導(dǎo)老師XXX老師給了我很大的幫助，以及指導(dǎo)。從開始資料的查閱和后來的畢業(yè)設(shè)計大體框架的定稿，再到后來論文的修改，X老師給我指明了方向，讓我在畢業(yè)設(shè)計的完成上事半功倍，這樣我才能順利完成本次畢業(yè)設(shè)計。在此，我表達對X老師最誠摯的祝福以及感謝。 同時，我也要感謝在畢業(yè)設(shè)計完成過程中我的室友和同學(xué)對我的輔導(dǎo)以及支持，對他們給我提出的各種建議以及意見表示感謝。最后，在大學(xué)即將畢業(yè)之際，我對XX大學(xué)XX學(xué)院