公共品博弈的空間效應(yīng)研究

1、畢業(yè)論文開題報告理論物理公共品博弈的空間效應(yīng)研究一、選題的背景與意義無論對于生物界種群的進化述是人類社會的發(fā)展，合作都扮演著至關(guān)重要的 角色。然而，口私個體z間的無私利他行為與達爾文的物競天擇理論是相互抵觸 的。在尋求這一問題的答案的過程中，博弈論以及演化博弈論扮演了重要角色并 提供了強有力的理論框架。社會和自然界中復雜系統(tǒng)的結(jié)構(gòu)形態(tài)和系統(tǒng)結(jié)構(gòu)可以從網(wǎng)絡(luò)的角度進行描 述。近年來，復雜網(wǎng)絡(luò)研究的興起與發(fā)展，使得人們對各種現(xiàn)實網(wǎng)絡(luò)的結(jié)構(gòu)演化、 復雜性有了比較清晰的認識。而復朵網(wǎng)絡(luò)理論為描述博弈個體z間的博弈關(guān)系提 供了方便的系統(tǒng)框架。網(wǎng)絡(luò)上的節(jié)點表示博弈個體，邊代表與其鄰居的博弈關(guān)系。 這樣一來，

2、就可以利用復雜網(wǎng)絡(luò)拓撲關(guān)系，來研究一些復雜的博弈關(guān)系下的博弈。 由于真實系統(tǒng)中的個體或要素之間存在策略依賴關(guān)系，所以可在復雜網(wǎng)絡(luò)上建立 空間博弈模型。在復雜網(wǎng)絡(luò)上建立的空間博弈模型更加客觀真實，更加符合實際 的演化規(guī)則，更加貼切生活，使得復雜網(wǎng)絡(luò)的演化博弈方興未艾。隨著演化博弈 動力學行為與復雜網(wǎng)絡(luò)之間的關(guān)系逐漸清晰，空間博弈必定會推動復雜網(wǎng)絡(luò)中其 他領(lǐng)域的發(fā)展。而木文將在了解公共品模型的研究現(xiàn)狀和數(shù)值方法基礎(chǔ)上，通過 數(shù)值方法研究個體的各類空間效應(yīng)，探索各類空間效應(yīng)對公共品博弈中合作行為 的彩響，從而得到相應(yīng)的研究成果。二、研究的基木內(nèi)容與擬解決的主要問題1、對公共品模型的研究現(xiàn)狀和數(shù)值方法

3、進行文獻調(diào)研2、在了解前人的模型工作的基礎(chǔ)上，獨立進行模型建立3、對所建立的模型進行計算分析，得到研究結(jié)果4、對研究結(jié)果進行總結(jié)分析，撰寫出實驗論文三、研究的方法與技術(shù)路線1、在公共品模型框架下，分析各種町能的空間行為，基于相關(guān)文獻及前人模 型工作z上獨立建立模型2、對所建立模型通過數(shù)值方法研究個體的各類空間效應(yīng)從而得到研究結(jié)果四、研究的總體安排與進度2010.12.15完成基本文獻的閱讀，了解基本原理和研究背景2010.12.16-2011.1.15熟悉基本數(shù)值方法，并捉岀自己新的模型2011.2.-2011.3進行模型計算和分析2011.4進行總結(jié)并撰寫論文，準備答辯五、主要參考文獻1、n

4、owak m a and sigmund k, 2004 science 303, 7932、szabo g and fath g, 2007 phys. rep. 446, 973、doebeli m, hauert c and killingback t, 2004 science 306, 8594、nowak m a and may r m, 1992 nature 359, 8265、hauert c and doebeli m, 2004 nature 428, 6436、santos f c and pacheco j m, 2005 phys. rev. lett. 95, 0

5、981047、復雜網(wǎng)絡(luò)上的演化博弈 智能系統(tǒng)學報167324785 (2007)02200012108、復雜網(wǎng)絡(luò)上博弈行為的研究進展 電子測量技術(shù)第30卷第4期tp399、復雜網(wǎng)絡(luò)演化博弈理論研究綜述 復雜系統(tǒng)與復雜性科學第5卷第4期畢業(yè)論文文獻綜述物理學 公共品博弈的空間效應(yīng)研究 摘要：傅弈理論在社會、經(jīng)濟、生物以及生態(tài)等系統(tǒng)中存在著廣泛的應(yīng)用，復雜 網(wǎng)絡(luò)理論則是研究復雜系統(tǒng)全新而有力的工具，因此將博弈理論與復雜網(wǎng)絡(luò)理 論相結(jié)合成為研究復雜系統(tǒng)一個新的熱點概述國內(nèi)外當麗關(guān)于復雜網(wǎng)絡(luò)上博弈 動力學的研究情況和發(fā)展動態(tài)，包括基本的博弈模型、主要關(guān)注的問題、以及網(wǎng) 絡(luò)結(jié)構(gòu)和博弈動力學的相互作用等，

6、最后探討進一步的研究課題。關(guān)鍵詞：復雜網(wǎng)絡(luò) 演化傅弈 合作行為 正文：我閱覽了大量關(guān)于復雜網(wǎng)絡(luò)和博弈的相關(guān)文獻資料。不管是書目、期刊、論 文，在這兩方面的研究都始終是蓬勃發(fā)展碩果累累的。然而關(guān)于博弈的問題最終 都要歸結(jié)到對于合作的探究。根據(jù)博弈論，合作能給種群內(nèi)的其他成員帶來好處, 卻常常會損害個體自身的利益。根據(jù)達爾文進化論最適者生存的自然法則，有益 于種群內(nèi)所冇成員的合作行為應(yīng)該滅絕。然而，事實并非如此。在真實的生物、 社會等復雜系統(tǒng)中在生物和社會等科學領(lǐng)域，合作是一種普遍存在的現(xiàn)象。從單 細胞的微生物到高級哺乳動物，從社會性昆蟲到人類社會。生物個體之間的合作, 增加了整個種群的生存機會。

7、那么自私個體間合作是如何產(chǎn)生和維持的，成為人 們討論的熱點問題。為了理解合作行為是如何從自私的個體之間演化產(chǎn)生的，近 年來，一些可能的合作機理。如群體選擇、親緣選擇、直接（間接）互惠、空間 互惠、聲望與懲罰等得到一定的探討。口從alelrod利用迭代囚徒困境博弈研究合 作的演化以來，演化博弈論為研究合作演化提供了方便的數(shù)學框架，受到越來越 多的關(guān)注，1人i徒困境博弈和雪堆博弈是被研究者廣泛采用的研究合作行為的兩個 范例。在經(jīng)典博弈論屮，個體被假定是超理性的（所冇個體都知道英他個體也是理 性的，并且會按照理性行事），且個體對收益矩陣元的信息完全了解。在這種機 制下，所有個體最終都會采取納什平衡策

8、略。但是這種個體的超理性會導致機體 的非理性（因為相互合作時集體的收益最大）。一-般而言，在復雜的環(huán)境屮個體 沒有充分的能力去選擇最佳策略以最大化收益。此時，個體通常根據(jù)其所掌握的 局部信息采取啟發(fā)式的方法，做出令其“滿意”的決策，這種選擇過程表明個體 是有限理性的。演化博弈理論著重研究有限性的個體如何在重復博弈過程屮，通 過口適應(yīng)學習來實現(xiàn)口身收益的最大化問題。復雜網(wǎng)絡(luò)理論為描述博弈個體z間的博弈關(guān)系捉供給了方便的框架。由于真 實系統(tǒng)中的個體或要素z間存在策略依賴關(guān)系，所以可在復朵網(wǎng)絡(luò)上建立空間博 弈模型。這樣就可以利用復雜網(wǎng)絡(luò)拓撲關(guān)系來研究一些復雜博弈關(guān)系下的博弈。 由于真實的社會網(wǎng)絡(luò)比一

9、些模型網(wǎng)絡(luò)復雜，而后者通常只是前者的i個特性或某 些特性的反映，因此研究真實社會網(wǎng)絡(luò)上的演化博弈對揭示合作的演化具有重要 意義。而小世界效應(yīng)、無標度性質(zhì)等對網(wǎng)絡(luò)上演化博弈的影響自然受到了研究者 的關(guān)注，成為了有意義的課題。公共品博弈是以公共品為博弈對象的博弈，這種博弈廣泛存在于發(fā)雜網(wǎng)絡(luò)之 屮。一般來說，公共品是指在消費過程屮具有非競爭性和非排他性的物品。因為 公共品具有這樣的性質(zhì)，所以集體中的每個人都會希望由其他人來提供，而自己 坐享其成，這種行為被稱為搭便車。搭便車問題使集體行動變得難以實現(xiàn)每 個人都想搭便車的結(jié)杲，就是沒有便車可搭。搭便車問題的存在，解釋了很多 社會困境。例如，惡劣的環(huán)境無

10、人清理，不合理的制度人人抱怨卻無人抵制。公共品博弈的理論結(jié)果和現(xiàn)實的差異是巨大的。大量的實驗研究表明，集體 成員的搭便車動機是有限的，合作能夠達到一個客觀口穩(wěn)定的水平。這就表明， 在重復公共品博弈過程屮，個體不僅要考慮自身收益，還受到很多外在因素的影 響，如激勵與懲罰，而且社會系統(tǒng)中的個體還貝有某種異質(zhì)性稱為社會偏好, 這種社會偏好使得個體會考慮他人的選擇，具體表現(xiàn)為互惠、不平等厭惡、學習 和遷移等。很顯然，這些外在因素的存在會降低個體搭便車的動機，并提高合作 水平。關(guān)于公共品博弈的研究貫穿各個方而，在生物與科淫領(lǐng)域的研究尤為顯著。 我主要列舉了一卜三種說法：群體選擇學說：群體選擇學說將種群看

11、作一個進化的單位，在群體層次上考 慮公共詁博弈。在群體屮，那些對種群有利的特征之所以能夠保存下來，是因為 在進化過程中，雖然群選擇與個體選擇的方向是相反的，但是個體的選擇可能導 致種群的滅亡，這種來口于外部的壓力促使個體間相互合作。互惠和強互惠效應(yīng)：互惠機制包括直接互惠和間接互惠。直接互惠中的個體 之所以冒著可能會被背叛的風險去跟其他個體合作是因為希望在日后與該個體 再次進行i専弈時能夠取得更大的收益，所以冋報才是互惠利他主義者的真正目 的。間接互惠的基礎(chǔ)是“聲譽”。個體選擇跟英他個體進行合作是期望捉高自己 的聲譽，得到更多個體的合作，但是這種合作是不穩(wěn)定的。直接互惠和間接互惠 都無法很好的解

12、決公共品闿弈中的合作現(xiàn)象，這種情況下，強互惠理論應(yīng)運而生。強互惠理論認為，人類之所以能維持比其他物種更高度的合作關(guān)系，在于許 多人都具有這樣一種行為傾向：在i才i休中與別人合作，并不惜花費個人成本去懲 罰那些破壞群體規(guī)范的人，即使這些成本并不能被預期得到補償。強互惠能夠冇 效的抑制團體中的背叛、逃避責任和搭便車行為，提高合作水平。但實施這種行 為需要個人承扒成本，這樣就帶來一個新的問題，成本出誰來負擔？每一個合作 者都會寄希望于其它合作者承擔這個成木，即所謂“二階搭便車問題”。解決這 個問題乂產(chǎn)生了許多討論，包括合作懲罰以及制度的制定等?？臻g效應(yīng)：由丁真實系統(tǒng)中的個體或耍素z間存在策略依賴關(guān)系

13、，我們可 以在各種網(wǎng)絡(luò)上建立空間博弈模型，這樣又發(fā)現(xiàn)了許多空間因素的影響。比如說 公共品博弈中獨立者的引入獨立者是在公共品博弈模型中引入不參與博弈， 但會每局收到少而固定的收益的獨立者。這樣，在一定r下，就會出現(xiàn)-種動態(tài) 平衡。除此之外還有很多各種各樣的影響，如網(wǎng)絡(luò)的影響（不同的網(wǎng)絡(luò)對于合作 的促進作用也是不同的）、策略的改變（在博弈屮引入學習和遷移的策略，個體 在博弈中有一定的幾率改變策略和交換位置）等等，也會明顯影響博弈的結(jié)果。復雜網(wǎng)絡(luò)上的演化博弈研究是近年來隨著復雜網(wǎng)絡(luò)研究興起而逐漸引起關(guān) 注的一個重要研究領(lǐng)域?？谇按蟛糠止ぷ鞫技≡趇人i徒困境博弈或雪堆博弈研究 上，其他類型的傅弈還缺

14、乏系統(tǒng)的研究。因此有必要進一步考慮多人博弈的情形, 如公用品博弈本文所主要研究的課題，或多策略的博弈等。如石頭剪刀 布（rock-scissors-paper）博弈.近來一些學者開始關(guān)注這些問題，也得到了一些有 趣的結(jié)果。對于自然界中廣泛存在的合作行為的理解，以及如何又到自私個體之間產(chǎn)生 合作一直是數(shù)學、物理、生物、管理乃至工程學科的學者關(guān)注的話題。隨著復雜 網(wǎng)絡(luò)的興起，人們對于字兒按揭中復雜系統(tǒng)的組織結(jié)構(gòu)有了新的認識。從網(wǎng)絡(luò)結(jié) 構(gòu)的角度研究演化博弈行為是一個既具冇理論意義又冇工程實踐價值的課題?？谇昂芏喙ぷ髦皇且恍?shù)值仿真結(jié)果,由于數(shù)學工具的不足，對復雜網(wǎng)絡(luò)上的 i専弈動力學進行解析分析是非

15、常困難的，目前的一些近似方法，如平均場方法、對 估計方法在異質(zhì)程度很大的網(wǎng)絡(luò)很冇可能失效.因此尋求冇效的數(shù)學工具，探求 更好的理論結(jié)果，將一些數(shù)值結(jié)果命題化、嚴格化，將是十分有意義的。該課題將在了解公共品模型的研究現(xiàn)狀和數(shù)值方法基礎(chǔ)之上，通過數(shù)值方法 研究個體的各類空間效應(yīng)，探索各類空間效應(yīng)對公共品博弈屮合作行為的影響， 從而得出在各種因素之間多人i専弈情況下的合作行為的發(fā)生情況。現(xiàn)實中，公共 品博弈普遍存在，當然也存在很多社會困境?？紤]到影響公共品博弈的各種因素, 如何更有效的促進合作行為的產(chǎn)生成為我們現(xiàn)在研究的主要方向。希望該項研究 不僅能在理論方面，更能對真實系統(tǒng)中公共品博弈提供建設(shè)性的

16、意見和建議。參考文獻1> nowak m a and sigmund k, 2004 science 303, 7932、szabo g and fath g, 2007 phys. rep. 446, 973 doebeli m, hauert c and killingback e 2004 science 306, 8594、nowak m a and may r m, 1992 nature 359, 8265、hauert c and doebeli m, 2004 nature 428, 6436> santos f c and pacheco j m, 2005 ph

17、ys. rev. lett. 95, 0981047、復朵網(wǎng)絡(luò)上的演化博弈智能系統(tǒng)學報167324785 (2007) 02200012108、復雜網(wǎng)絡(luò)上博弈行為的研究進展電子測量技術(shù)笫30卷第4期tp399、復雜網(wǎng)絡(luò)演化博弈理論研究綜述復雜系統(tǒng)與復雜性科學笫5卷第4期10、博弈m白波，郭興文哈爾濱出版社2005.本科畢業(yè)設(shè)計（20 屆）公共品博弈的空間效應(yīng)研究【摘要】本文基于復雜網(wǎng)絡(luò)下的公共品博弈演化模型，研究各類空間效應(yīng)對合作演化動態(tài)的影響以及引入 獎勵機制后合作行為演化的方向。通過允許對合作個體的獎勵作為一種積極因素促進合作的產(chǎn)生，結(jié)果表 明獎勵可以通過提供一個避免相互背叛情況出現(xiàn)的方式

18、促進合作的產(chǎn)生。然而與懲罰相比，獎勵無法使合 作穩(wěn)定下來，卻提高了穩(wěn)定的合作者的數(shù)目。量后分析了復雜網(wǎng)絡(luò)上公共品演化博弈論的未來發(fā)展方向與 應(yīng)用前景?！娟P(guān)鍵詞】公共品；復雜網(wǎng)絡(luò)；演化博弈；獎勵機制abstractabstract based on the public goods game, this thesis presents a model in which individuals are rewarded who con tribute to the public goods .it is show n that reward is capable of promoti ng coo

19、perati on by providi ng an escape hatch out of states that we defect each other mutually. reward, contrast with punishment, is unable to stabilize cooperation although it gives rise to a persistent minority of cooperators finally unresolved open problems and future research directions and possible a

20、pplication areas for public evolutionary game on complex networks are pointed out.【keywords public goods： complex networks ； evoluti on ary games ； incen tive system摘要8abstract8h錄8i研究背景101. 1博弈論101. 1.1經(jīng)典博弈論、博弈模型與納什均衡101.1.2從經(jīng)典聘弈到演化聘弈121.2復雜網(wǎng)絡(luò)131.2. 1復雜網(wǎng)絡(luò)的特征度量141.2.2復雜網(wǎng)絡(luò)的分類141.2.3復雜網(wǎng)絡(luò)上的演化博弈152公共品博弈背

21、景簡介62.1背景簡介172.2群選擇學說172.3互惠與強互惠效應(yīng)182.4空間效應(yīng)193模型建立213. 1模型介紹213. 2現(xiàn)象及描述223. 3結(jié)語244結(jié)論與展望24參考文獻6致謝錯誤！未定義書簽。附錄： 錯誤！未定義書簽。1研究背景無論對于生物界種群的進化述是人類社會的發(fā)展，合作都扮演著至關(guān)重要的角色。自私 個休之間是如何產(chǎn)牛合作的一直是物理、牛物、數(shù)學乃至工程科學的學者關(guān)注的話題。然而, 依據(jù)達爾文主義，自然選擇是基于競爭的，個體將自私的最大化自身的利益，這顯然不能解 釋處處可見的合作行為。為了理解合作行為是如何從占私的個體z間演化產(chǎn)住的，近年來, 些可能的合作機理，如群體選擇

22、(group selection) >親緣選擇(kin selection) 直接(間 接)互惠(direct/indirectreciprocity) n 空間互惠(spatial reciprocity) > 聲望與懲罰 (reputation and punishment)等得到了一定的探討。而博弈論在尋求這一問題答案的過程 中扮演了重要角色并提供了強有力的理論框架。隨著計算機技術(shù)的飛速發(fā)展，対復雜網(wǎng)絡(luò)的 研究也不斷深入，人們對現(xiàn)實世界中復雜系統(tǒng)的組織結(jié)構(gòu)有了新的認識。在復雜網(wǎng)絡(luò)的基礎(chǔ) 上研究博弈行為成為一個既具有理論意義乂有現(xiàn)實價值的話題，受到人們越來越多的關(guān)注。1.1博弈

23、論1. 1. 1經(jīng)典博弈論、博弈模型與納什均衡博弈論，又稱對策論，主要是研究依據(jù)參與博弈的其他個體的策略悄況，理性個體所采 取的策略之間交互作用下的個體的行為演化。在交互作用屮，個體所獲得的收益不是純粹由 其自身所采取的策略決定，而是受到很多其他方面的影響，如其他個體的策略、博弈規(guī)則等 等。博弈論主要是由匈牙利數(shù)學家馮-諾依曼所創(chuàng)立的，在20世紀40年代作為一門正式的學 科發(fā)展起來。1944年馮-諾依曼和摩根斯坦出版的著作博弈論和經(jīng)濟行為，標志著現(xiàn)代系 統(tǒng)博弈論的初步形成。早期的博弈論過于抽彖，實川性不強，而h人們對博弈論的研究知z 浜少，影響力有限。隨著現(xiàn)代防弈論的不斷研究發(fā)展，它作為一種數(shù)

24、學理論被廣泛應(yīng)用于經(jīng) 濟、政治、住物、信息等許多領(lǐng)域，fi漸成為非常重要且有用的分析工具，為解決不同實體 的沖突和合作提供了一種冇效的方法。近十多年來，諾貝爾經(jīng)濟學獎先后授予研究博弈論的 科學家nash、selten等人也說明，博弈論越來越受到更多人的重視，也得到了越來越廣泛的 承認。通常一個博弈由以下5個部分所組成：(1)博弈主體，即陳弈過程屮進行獨立決策的個 體，在一輪i専弈小至少要有兩位決策者參與博弈(2)博弈信息，博弈個體所掌握的有利于 策略選擇的各方而信息，在i専弈中占重要地位，根據(jù)博弈個體對參與博弈所有個體收益信息 的掌握程度口j將博弈分為完全信息博弈與非完全信息博弈（3）策略集，

25、參與博弈的個體口j 選擇的所有可能策略的集合，根據(jù)該集合是有限還是無限，可分為有限聘弈和無限廨弈，其 小無限博弈乂表現(xiàn)為連續(xù)對策、更復博弈和微分對策等（4）收益矩陣，策略選定后，博弈 個體所獲得的收益是山相應(yīng)的收益函數(shù)或收益矩陣來確定的，根據(jù)博弈個體的不同收益情況 可以分為零和博弈與變和i専弈（5）策略演化，在重復i専弈過程中，i専弈個體以口身收益最 大化為冃標進行策略調(diào)整。就某一輪博弈而言，當所冇個體的策略選定以后，我們可以用集 合的形式來描述，s=（s1,s2,.）,其中每一項代表了所對應(yīng)個體采取的策略，進而得到某 種策略概況下個體所獲得的收益u。經(jīng)典博弈論中的一個重要概念納什均衡（nas

26、h equilibrium）,是美國科學家約翰-納什在二十世紀捉岀來的，從實質(zhì)上說是一種非合作博 弈狀態(tài)。所謂納什均衡指的是給定參與博弈的其他個體的策略時，任何一個個體都不能通過 單方面改變策略而使自身獲得更高的收益。換言z,在納什均衡中，個體所選的策略是該狀 態(tài)下個體的最優(yōu)策略。納什均衡在于解釋沒何外在約束條件下，參與博弈的個體均選擇其最 優(yōu)策略而形成的一種均衡結(jié)果。首先這種假設(shè)是基于參與博弈個體完全理性以及具有共同信 息的基礎(chǔ)之上的，但是真實系統(tǒng)的復朵性和界質(zhì)性使得這一點就很難達到；其次，納什均衡 是靜態(tài)的，其結(jié)果沒有受到其他任何因素的影響，所以在真實系統(tǒng)中形成的納什均衡可能是 不穩(wěn)定的；

27、最后，在很多博弈中包含不只一種均衡狀態(tài)，納什均衡不能解決多重均衡存在時 的選擇問題。下面我們以經(jīng)典的囚徒困境廨弈模型為例簡要的闡述下納什均衡的意義。囚徒困境博弈（prisoner，s dilemma game）:小偷甲和乙合伙作案,被捕后,警方將兩人分 別置于兩個房間內(nèi)進行審訊。警方給出的政策是：如果雙方都拒絕坦白同伴的罪行，兩人將 會被輕判1年徙刑；如果甲（乙）坦口（背叛）罪行，而乙（甲）拒不供認（合作）罪行, 則甲（乙）將無罪釋放，而乙（卩）將被重判5年徒刑；如果甲、乙互相揭發(fā)對方罪行，則 雙方均被判刑3年。該博弈的收益矩陣可列表如下：甲/乙合作背叛合作1,15,0背叛0,53,3從上表我

28、們可以看出，如果甲選擇坦白，即選擇“背叛”（defect-d）乙，則乙也應(yīng)該選擇坦 白因為如果此時乙選擇合作，甲將被無罪釋放，陽乙會被重判5年，而如果此時乙也選 擇背叛，則將會跟甲均判3年，顯然，對乙來說，廿叛總是最佳策略。反z,對甲來說也是 如此。但是整休來看，甲乙的最優(yōu)策略應(yīng)該是選擇跟對方合作，此時兩人均被判1年。這樣 就陷入了兩難困境，那么這種情況下，甲乙兩個體應(yīng)如何做出抉擇？從理性個體自身利益最 大化為冃標來看，相互合作的情況不會發(fā)生，對甲乙來說，因為不論對方采取哪種策略，背 叛始終是口身的最佳策略（注意到此時集體的收益最低）。所以當雙方都選擇背叛時，沒有 個體會主動選擇改變策略（i大

29、1為單方面改變策略使口身收益降低），此時這種相互巧叛的狀 態(tài)就是該系統(tǒng)的納什均衡狀態(tài)。現(xiàn)實生活中，類似囚徒困境的例子很多，也揭示出各種社會 困境。上面所述的是單次發(fā)生的貝徒困境，但是在重復囚徒困境中，參與醇弈的個體町以通 過記憶或?qū)W習、或者采取某種報復措施對背叛者進行懲罰，那么在合適的機制卜合作將會 作為均衡的結(jié)果出現(xiàn)并逐漸占據(jù)優(yōu)勢，從而有利于合作策略的涌現(xiàn)與維持。在接近無限次的 博弈屮，納什均衡會趨向于帕累托最優(yōu)（pareto optimality, pavlov策略是屬于更一般 的wsls的策略模型，指個體如果現(xiàn)在的策略獲得的收益人于某個期望水平，那么 下次博弈保持該策略不變，否則就改變策

30、略）。1.1.2從經(jīng)典博弈到演化博弈經(jīng)典博弈論屮，個體被假定是超理性的一一完全信息博弈，而且所有個體都知道其他 個體也是理性的，并u會按照理性行事。這種機制下，博弈最終會達到納什均衡狀態(tài)，即所 有的個體最終都會采取納什均衡策略。從囚徒困境的例子可以看出，這種個體的超理性會導 致集體的非理性（因為相互合作時集體的收益最大）。但是，在真實的復雜社會系統(tǒng)中，個 體沒有充分的能力去選擇能最大化其收益的最佳策略。此時，個體通常根據(jù)其掌握的局部信 息來做出具相對滿意的策略一一非完全信息博弈，這種選擇過程表明個體是有限理性 （bounded rationality）的。演化博弈理論（evolutionary

31、 game theory）著重研究重復博 弈過程中有限理性的博弈個體z間怎樣涌現(xiàn)出合作行為以及博弈個體如何通過口適應(yīng)學來 實現(xiàn)自身收益故大化的問題。演化博弈論（evolutionary game theory）以達爾文的進化論和拉馬克的遺傳基因理論為 思想基礎(chǔ)，將燭弈理論與動態(tài)演化過程分析結(jié)合起來，分析從個體到群體行為的行為機制, 研究種群的進化遇勢及穩(wěn)定性，為描述個體之間的相互作用提供了一種通用數(shù)學框架。參與 博弈的個體采取一定的策略，獲得一定的收益（該收益依賴于個體本身的策略跟參與博弈的 其他個體的策略）。在每一輪博弈中，博弈個體以某種策略更新規(guī)則更新自己的策略，最終 達到一種演化穩(wěn)定策略

32、（evolutionarily stable strategy,ess） 所有參與博弈的個體在重復 博弈中選擇的某個最優(yōu)的、穩(wěn)定的策略，即演化博弈中的均衡點。與經(jīng)典博弈中所討論的納 什均衡不同，演化穩(wěn)定策略是一種更加嚴格的均衡，該策略所對應(yīng)的收益相対變界者來說是 占優(yōu)勢的，而且演化穩(wěn)定策略只是-種初始狀態(tài)的優(yōu)勢策略，并不是演化的結(jié)果狀態(tài)。演化 穩(wěn)定策略最大的不足z處就在于它把影響系統(tǒng)的因索都看成是一個個的孤立事件，而在現(xiàn)實 屮系統(tǒng)常常會受到各種沖擊。復雜網(wǎng)絡(luò)上的演化博弈研究上要是在結(jié)構(gòu)化的群體結(jié)構(gòu)上，考慮復雜網(wǎng)絡(luò)上所刻畫的膊弈者z間的相互作用關(guān)系。正是由于這種復朵的拓撲結(jié)構(gòu)，使得復 雜網(wǎng)絡(luò)上的

33、演化博弈呈現(xiàn)出更為復雜的動力學性質(zhì)。博弈論最早體現(xiàn)在真實的生物學領(lǐng)域屮，也最早的應(yīng)用來解釋生物科學屮的問題。1973 年smith和price發(fā)表的動物沖突的邏輯，是燭弈論第一次被正式的應(yīng)用于牛物學屮，也是 演化穩(wěn)定策略的來源。該文運用博弈論的思想從個體選擇的角度解釋了動物間的爭斗為什么 從來都是有限幾非惡性的。從經(jīng)典i専弈論發(fā)展到演化旳弈論，其中有3個關(guān)鍵性的內(nèi)涵發(fā)生 了轉(zhuǎn)變。第一個是策略內(nèi)涵的轉(zhuǎn)變。經(jīng)典聘弈論中，博弈個體被假定是超理性的，所有可能選擇 的不同策略構(gòu)成策略集。在演化博弈論中個體的超理性被達爾文的“適者生存”規(guī)則所代替。 那些不采収“理性”策略的個體會在漫長的演化過程中趨于滅絕

34、。第二個是均衡意義的轉(zhuǎn)變。在演化|専弈論中，經(jīng)典博弈論中的納什均衡被演化穩(wěn)定策略 所代替。演化穩(wěn)定策略可以是純策略，也町以是混合策略。與納什均衡相比，演化穩(wěn)定策略 是一種更嚴格的均衡。第三個是個體交互作用內(nèi)涵的轉(zhuǎn)變。經(jīng)典博弈論小，博弈個體只進行一次燭弈，或者與 相同的個體進行多次博弈。而在演化博弈論中，博弈個體隨機選配成對進行多次博弈，且假 定再次遇到相同對手的概率很小。上述3個重要概念的內(nèi)涵轉(zhuǎn)變，使得演化博弈理論從一個靜態(tài)的過程成為一個動態(tài)演變 的理論，更著重于對演化穩(wěn)定策略的研究，能夠描述動態(tài)系統(tǒng)的局部動態(tài)性質(zhì)，預測個體行 為。1.2 復雜網(wǎng)絡(luò)最近二十多年來，網(wǎng)絡(luò)的研究有了突飛猛進的進展。

35、這主要得益于計算機和通信網(wǎng)絡(luò)技 術(shù)的巨大進步。借助于它們，我們可以收集和分析以往難以想彖的海量的網(wǎng)絡(luò)數(shù)據(jù)，并可以 研究數(shù)以百萬計英至數(shù)以億計大小的網(wǎng)絡(luò)。通過對真實肌界大最復雜系統(tǒng)的研究，人們發(fā)現(xiàn) 它們的結(jié)構(gòu)不能簡單的用規(guī)則圖或完全隨機圖來描述。但另一方面，這些復雜的結(jié)構(gòu)有很多 共性，比如小的平均距離，高成團系數(shù)以及連接度為幕律分布等拓撲性質(zhì)。人們把這類介于 規(guī)則圖和完全隨機圖z間的網(wǎng)絡(luò)稱z為復雜網(wǎng)絡(luò)(complex networks)。復雜網(wǎng)絡(luò)是研究復雜 系統(tǒng)的一門新興學科，近幾年受到研究學者的廣泛關(guān)注。自然界中的任何復雜系統(tǒng)都可以抽 象成為由相互作用的個體組成的網(wǎng)絡(luò)，如互聯(lián)網(wǎng)、萬維網(wǎng)、航空網(wǎng)

36、、電力網(wǎng)、蛋白質(zhì)相互作 用網(wǎng)以及各種合作網(wǎng)絡(luò)等。對于復雜網(wǎng)絡(luò)的研究極大的改變了人們對復雜外部世界的認識, 讓人們認識到了以前的理論尚未涉及到的問題，也迅速引起了諸多領(lǐng)域中科研工作者的興 趣，特別是物理學界、生物學界，復雜網(wǎng)絡(luò)理論得到了充分的探索和發(fā)展。研究這些網(wǎng)絡(luò)不 僅對于人們的工作和生活至關(guān)重要，而對于揭示自然界特別是生物系統(tǒng)的奧秘也金關(guān)重 要。1.2.1復雜網(wǎng)絡(luò)的特征度量隨著對復朵網(wǎng)絡(luò)研究的不斷深入，人們提出了許多概念和度量方法來表示復朵網(wǎng)絡(luò)，這 里主要主要介紹節(jié)點的度、簇系數(shù)和平均路徑長度。1、節(jié)點的度 度是描述網(wǎng)絡(luò)局部特性的基木參數(shù)，指的是與該節(jié)點連接的其他節(jié)點的 數(shù)量。度分布(deg

37、ree distribution),則表示節(jié)點度的概率分布。如果某一節(jié)點的度分 布函數(shù)為p(k),表示該節(jié)點恰好有k條邊的概率。目前度分布較為常見的有兩種，一種是指 數(shù)分布，另-種是幕律分布。度分布函數(shù)反應(yīng)了網(wǎng)絡(luò)系統(tǒng)的宏觀統(tǒng)計特征。2簇系數(shù) (clustering coefficient),又稱為集聚系數(shù)，指與同一個節(jié)點相連接的 一對節(jié)點相連接的概率，衡量網(wǎng)絡(luò)的集團化程度。全連通的網(wǎng)絡(luò)中，簇系數(shù)為1, 一般均小 于1。3、平均路徑長度(average path length, apl),指網(wǎng)絡(luò)中所有節(jié)點與節(jié)點之間平均的 最短距離。節(jié)點間的距離是通過從一個節(jié)點到另一個節(jié)點所經(jīng)歷的邊的最小數(shù)目來計

38、算的。 復雜網(wǎng)絡(luò)研究中一個重要發(fā)現(xiàn)就是大部分真實系統(tǒng)中的平均路徑程度都遠比想彖中小，我們 稱之.為小世界效應(yīng)。除上述度分布、簇系數(shù)和平均路徑長度三個最基木的結(jié)構(gòu)特性外，復雜網(wǎng)絡(luò)還有其他許 多度量特征，如介數(shù)(反映了相應(yīng)的節(jié)點或邊在整個網(wǎng)絡(luò)屮的作用和影響力，具有很強的現(xiàn) 實意義)、網(wǎng)絡(luò)彈性(指網(wǎng)絡(luò)節(jié)點的刪除對連通度的影響)等。1.2.2不同類型復雜網(wǎng)絡(luò)簡介根據(jù)復雜網(wǎng)絡(luò)的特性不同，衍生出很多不同的類型，由于真實社會網(wǎng)絡(luò)具冇小世界和無 標度等特性，所以這里我們也主要介紹這兩種網(wǎng)絡(luò)。隨機網(wǎng)絡(luò)是最簡單的復雜網(wǎng)絡(luò)，在20世紀50年代由匈牙利的兩位數(shù)學家提出的。在er 隨機網(wǎng)絡(luò)模型中，首先給定網(wǎng)絡(luò)中的節(jié)點數(shù)

39、目，然后讓任意兩節(jié)點之間以相同的概率連接在 一起完全隨機地構(gòu)成網(wǎng)絡(luò)。該模型口提出后被廣泛應(yīng)用于社會與生態(tài)學的研究。小世界網(wǎng)絡(luò)模型，由watts>flistrogatz提出的，這個模型構(gòu)建在一維格了基礎(chǔ)上，是對 一個臨近節(jié)點耦侖的規(guī)則網(wǎng)絡(luò)進行隨機化重連之麻所能生成的網(wǎng)絡(luò)模型。與隨機網(wǎng)絡(luò)相比, 其顯著特性是簇系數(shù)大、平均路徑長度小。小世界網(wǎng)絡(luò)上的空間純策略主耍分為兩類：一類 是基于環(huán)的小世界網(wǎng)絡(luò)，另一類是基于方格的小世界網(wǎng)絡(luò)。根據(jù)網(wǎng)絡(luò)中度的變化特性乂可將小世界網(wǎng)絡(luò)分為同質(zhì)與界質(zhì)。1.2.3復雜網(wǎng)絡(luò)上的演化博弈人們對網(wǎng)絡(luò)的研究由來己久，圖論是最早涉足網(wǎng)絡(luò)研究的數(shù)學理論。圖論屮網(wǎng)絡(luò)被稱為 圖，圖

40、是網(wǎng)絡(luò)的數(shù)學表達形式，它由頂點和邊構(gòu)成。圖論的起源很早，瑞士數(shù)學家eul目在 1736年解決了箸名的哥尼斯城堡七橋問題，從而使他成為圖論和拓撲學的創(chuàng)始人。此后開展 的研究工作大多基于網(wǎng)格等規(guī)則網(wǎng)絡(luò)，直到上世紀五十年代，匈牙利數(shù)學家efdos和rgyi 創(chuàng)造性的將概率論引入圖論并成功地捉出了第一個隨機圖模型一er模型。在過去幾十年中， er模型已成為隨機圖論的研究基礎(chǔ)并一玄占據(jù)著復雜網(wǎng)絡(luò)研究的主導地位。近年來，以還原 論和整體論相結(jié)合為重要特色的復雜性科學的興起，促便人們開始關(guān)注復雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu) 及其產(chǎn)牛:機理:諸如因特網(wǎng)等人量新型網(wǎng)絡(luò)的相繼出現(xiàn)使得人們對復雜網(wǎng)絡(luò)性質(zhì)的了解變得 越來越迫切；計

41、算機技術(shù)的飛速發(fā)展為大規(guī)模復朵網(wǎng)絡(luò)的研究提供了有效的丄具，使得人們 可以對那些包含上百萬乃至于上千萬個頂點的網(wǎng)絡(luò)進行分析，而這在若于年前還是不可想彖 的事情；不同領(lǐng)域屮反映復雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)的數(shù)據(jù)庫相繼出現(xiàn)為復雜網(wǎng)絡(luò)的研究提供了可靠 的實驗數(shù)據(jù)，使得研究者能夠?qū)Σ煌愋偷臄?shù)據(jù)進行分析進而發(fā)現(xiàn)復雜網(wǎng)絡(luò)所具有的共同特 征;上述因素加之各學科間的相互融合使得大規(guī)模復朵網(wǎng)絡(luò)的研究得以快速發(fā)展。總體來說, 對于復雜網(wǎng)絡(luò)上的演化弈的研究主要集中在三個方而：一是研究網(wǎng)絡(luò)拓撲結(jié)構(gòu)對陣弈演化 動力學的影響，即增加相互作用結(jié)構(gòu)的復雜性，研究其對合作行為的影響；二是在不同的網(wǎng) 絡(luò)結(jié)構(gòu)下探討各種演化規(guī)則對演化的動態(tài)影響

42、；三是網(wǎng)絡(luò)拓撲和博弈動力學的共同演化對合 作機制的彩響，主要是h適應(yīng)網(wǎng)絡(luò)上的博弈動力學，即網(wǎng)絡(luò)拓撲調(diào)整受博弈動力學的影響。 下而我們簡要的介紹兒種網(wǎng)絡(luò)系統(tǒng)中常用的策略演化規(guī)則。1、模仿最優(yōu)秀者(best-takes-over)：每一倫博弈過后，個體采取與其博弈的個體中 最大收益的個體的策略進行下一輪博弈；2、模仿優(yōu)勝者(proportional updating):個體在進彳亍策略更新時，與跟其進行陳弈的 其他個體比較，并以某種正比于收益的概率采取收益比白身高的個體的策略進行下一輪博 弈；3、配對比較(match-pairing comparision):個體隨機選擇參與博弈的其他個體進彳亍收

43、 益比較，并以某種概率(通常是兩個體收益差的函數(shù))轉(zhuǎn)變?yōu)閷Ψ降牟呗?。以上三種是復雜系統(tǒng)中比較常用的策略更新方法?，F(xiàn)在人部分研究屮采用的更科學的策略更新規(guī)則是:_ 1%_為1+5（甌一"）7丁式中：等號左邊表示的是節(jié)點x模仿鄰居節(jié)點y策略的概率，m代表節(jié)點的累計收益，t表示節(jié) 點的理性程度。當*0時，表示節(jié)點完全理性；當t趨向于無窮時，表示節(jié)點毫無理性，隨機 選擇；易知，存在一個適當?shù)膖使得合作達到最高水平。網(wǎng)絡(luò)屮參與博弈的個體比較多時，策略的更新又受到一個先后秩序的影響，我們稱之 為同步更新與隨機更新。同步更新是指所冇參與博弈的個體同時進行策略的更新，通常應(yīng)川 在生物模型中；隨機更新

44、也叫非同步更新，是指在網(wǎng)絡(luò)屮隨機選擇參與陳弈的個體進行策略 的更新，這種更新規(guī)則很好的反應(yīng)了真實社會系統(tǒng)，因而受到了更多的關(guān)注。但在很多情況 下，這兩種更新方式對博弈的結(jié)果并沒有明顯的影響。2公共品博弈背景簡介2.1背景簡介山于現(xiàn)實生活中往往不只是兩個個體間的博弈，而是多人之間的博弈，因此有必要將囚 徒困境模型擴展為一個多人博弈的模型，這就是本文研究的新的網(wǎng)絡(luò)模型z 公共品陣 弈模型。公共品聘弈是以公共品為聘弈對象的廨弈，這種博弈廣泛存在于復雜網(wǎng)絡(luò)之屮。一般來 說，公共品是指在消費過程屮具有非競爭性和非排他性的物品。因為公共品具有這樣的性質(zhì), 所以集體中的每個人都會希望由其他人來捉供，而自己坐

45、享其成，這種行為被稱為搭便車。 搭便年問題使集體行動變得難以實現(xiàn)集體成員存在搭便午的動機，隨著集體中社會成員 數(shù)量的增加，這種動機會更強烈，導致合作水平降低。搭便車問題的存在，解釋了很多社會 困境。例如，惡劣的環(huán)境無人清理，不合理的制度人人抱怨卻無人抵制。在公共品陳弈中， 合作者c的貢獻a經(jīng)過一個r倍的放人后在全體參與者n小平均分配，如果n二nc,這所有參 與者的收益都將提高r倍。但如果n中岀現(xiàn)了背叛者d,不貢獻a而同樣軒參與分配（搭便 車）,則可獲得比合作者更高的凈收益pd=a - r - nc/no從納什均衡的角度看，公共品博弈 中，背叛將始終是最佳策略。從演化均衡的角度看，d將侵入c所組

46、成的團體，并最終取代 co然而，公共品博弈的理論結(jié)果與現(xiàn)實的差異很大。人量的實驗研究表明，集體成員的搭 便車動機是有限的，合作能夠達到一個客觀11穩(wěn)定的水平。這就表明，在重復公共站博弈過 程中，個體不僅要考慮口身收益，述受到很多外在因素的影響，如激勵與懲罰（本文通過引 入一個積極因素獎勵，來研究其對合作演化的影響），而社會系統(tǒng)中的個體還具冇某 種異質(zhì)性稱為社會偏好，這種社會偏好使得個體會考慮他人的選擇，具體表現(xiàn)為互惠、 不平等厭惡、學習和遷移等。很顯然，這些外在因索的存在會降低個體搭便車的動機，并提 高合作水平。2. 2群選擇學說在群選擇學說中，把種群看做一個進化的單位在群體層次上起作川。那些

47、對種群冇利但 對個體不利的特征之所以能夠保存下來，是因為種群的選擇會使這一特征出現(xiàn)的頻率增加， 而個體選擇服從群體的利益，是為避免群體被淘汰。公共品博弈與此相似，搭便車行為雖然 使個體的收益提髙了，但是卻損害了集體的利益，導致集體被淘汰，于是，在外界壓力下，個體選擇合作來避免此情況的發(fā)生。2. 3互惠與強互惠效應(yīng)互惠機制包括肓接互惠和間接互惠。直接互惠屮的個體z所口目若氷背叛的風險去與其他個體合作是因為希望在fi后與受次利他是弛惠者再次相謂，以應(yīng)獲f是互惠利他主義者的真正目的，這乍的而建立,但也可能陷入相互背己。直接i叛的因境。,以期待笫三方c的幫助。在這jk間接互惠的基礎(chǔ)是“聲巻”。b幫助a

48、是為了提高聲譽個受背叛犁勺報復行為要 罰，合作是不穩(wěn)定的。種情況下，由于報復策略的制約，合作町能因為一個背信行為而導致合作的失敗。因為第一經(jīng)過許多回合之后才會打擊到始作傭者，這樣許多無辜者會受到懲直接互惠和間接互惠都無法很好的解決公共品博弈中的合作現(xiàn)彖，這種悄況下，強互惠 理論應(yīng)運而生。強互惠理論認為，人類z所以能維持比其他物種更高度的合作關(guān)系，在于許多人都具有這樣-種行為傾向：在團體中與別人合作，并不惜花費個人成木去懲罰那些破壞群體規(guī)范的人，即使這些成本并不能被預期得到補償。強互惠能抑制團體中的苗叛、逃避責任和搭便不 行為，從而冇效提高團體成員的福利水平，但實施這種行為需要個人承擔成木。這樣

49、就帶來 一個新的問題，既然這種強互惠行為所提高的是團隊的收益，那么這個成本由誰來負擔？每 一個合作者都會寄希望于其它合作者承擔這個成本，這就是所謂的“二階搭便車問題”。解 決這個問題乂產(chǎn)綸了許多討論，包括合作懲罰以及制度的制定等。9 4 牢問效 應(yīng) i- opbonalpubik a*i i j 八人 1 goods gimes m 葉，wmma “ popuu* tions the three equ»* 由于真實系綻關(guān)細湃或要蘆之期j存在策noting homoktn«om popubtions of coop*系，我們可以亦各種網(wǎng)絡(luò)上建立空間博弈模型，這樣換醐約多用間

50、if碾型中勸入不參寫博弈但會每局收到少而固定的收益的deurte the rcpinutordymmia i *心a)獨立者的引矗翩男砧 the mtcricr of獨立者。這樣，就g er only brief intennit* tent bursts o( cooper-群體較大時，背叛:蠶js刪地位 hum port q ippen surrounded by dosed orthts. (c) with perfect mfocmation.莓 t beu rcpty dynamkn現(xiàn)一種動態(tài)平衡。當群體較小時，合作者占優(yōu)勢地位;q txconwt an attrador tht d

51、瓠* lines5? into thr«rtgiom wh«e cooptcmaon dtfktton. and loners domte. (d) indiv kjsized simuutions confirm the subiuty of the cycles in finite populations, if the strite of a randomly pitted individual is imiuted whenever it perfofim better. parametefs：n - 5；(a)r - 0.5; (b) to(d)f - 3.<

52、;r - 1; (d)popuhbon size. sooft numbero( intmktiom, 10*.figire 1 population structure and local neiboirhoods. a, regular graphs studied so far. htiich mimic spatially extended systems, b, sok free graphs' in which small world effects cocast with a iwge heierogenehy in neighbourhood size, cjhe fo

53、al indrvidiul (large" sphere) bdongs to different groups (neighbourhoods) of afterent azo in a heterogeneous gr申h. given his/her connectivity r 4. we ident © five neighbourhoods each centred on one of the memben o( the focalderives from the piyoff峽靜爍的促進作川是aaumuuted in all fiveneighbourhood

54、s (x 仇 *6 and c).hoproductton <raco msetectkxi irate u)c）策略的改變:在博弈中引入學習和i策略。使中有一定幾率交換位置會叨excriango (rata r)向|° the rules of the stockastbc model individuals of three com pctiny*species a < red )w b (biuc)> and c (yd low) occupy *he $itc& of a iacttoc. a ll>cy interact with their

55、 nearest neighbours through selection or reproduction, both of whk h react ion% occurproceme at rutekt 、<!nr%p<v1 ively selection rrileds cyclic dommance: a can kill rv yielding an empty site (black). in the same way» b invadcs c. and c in l um oulcompctcs a. reproduction of individual is

56、 cvily allowed on empty n eaghboureng sites, to mimic a finite cjrrydnft capacity of the system. we also endow individuals with mobility: nl ex change rate r> they are able to $wap position with a neighbouring individual or hop onio an empty ncighhouringsilc (cxchiinge). an example of the three p

57、roccy膏.taking place* on a j < 3 square lattice3x h1 x 10-51 x lo-<mobifty. mbtodh/orsityunrformrty3模型建立3.1模型介紹木文所建立的模型是基于復雜網(wǎng)絡(luò)的公共品演化障弈模型。模型屮只考慮個體與其最近鄰的博弈。(i, j)模型人小為10x10的網(wǎng)絡(luò)，節(jié)點數(shù)n= 10000,其中每個節(jié)點分別與其最近鄰的8個節(jié)點(稱為節(jié)點的度，即博弈半徑r<2)發(fā)生陣弈，包括節(jié)點木身在內(nèi)的九個節(jié)點之間的博弈稱 為節(jié)點的博弈環(huán)境。初始時刻網(wǎng)絡(luò)中的節(jié)點等概率的隨機選擇策略c和d,在博弈的過程小 我們采取同步升級的博弈策略，即所有節(jié)點的新策略在下一吋刻同吋影響其他節(jié)點。我們模 擬時選擇的蒙特r羅步數(shù)為20000,并選擇最后500步的平均作為輸出結(jié)果。每個節(jié)點都有 兩種選擇，合作(cooperation)或者背叛(defect