每輪博弈結(jié)束后，每個個體根據(jù)某種更新規(guī)則進行策略更新，并把更新后的策略作為自己下一輪博弈中采取的策略。在通常情況下，經(jīng)過足夠長的時間演化后，系統(tǒng)會達到一個相對穩(wěn)定狀態(tài)，即網(wǎng)絡(luò)中合作者的比例趨于穩(wěn)定。穩(wěn)定狀態(tài)網(wǎng)絡(luò)中合作者的比例通常被稱為合作頻率，是衡量系統(tǒng)合作水平的重要指標。

在復(fù)雜網(wǎng)絡(luò)的公共品博弈中，初始時候，網(wǎng)絡(luò)中給每個節(jié)點以相同的概率1/2隨機地賦予合作或者背叛策略。每個時間步，網(wǎng)絡(luò)上的每一個點i參與以它自己為中心及以它的鄰居為中心的 個群體的博弈。這里所說的一個群體是由一個中心節(jié)點及其周圍的鄰居構(gòu)成。每個合作者i給每個群體分別投入 的資本（也就是說，合作者i投入的總資本為1），背叛者不投入任何成本。在每一個群體中，獲得的總資本為該群體中所有合作者投入資本的總和，群體的總資本會增值（增值系數(shù)設(shè)為r），升值后的收益平均分配給該群體中的每個點。根據(jù)這樣的收益分配規(guī)則，節(jié)點x參與以節(jié)點y為中心的群體時，從這個群體獲得的收益 為

，

這里的 代表節(jié)點y， 是與y相連的節(jié)點i的策略（ 表示節(jié)點i是合作者， 表示節(jié)點i是背叛者）， 是節(jié)點i的度。節(jié)點x的總收益 為它從所參加的各個群體獲得的收益之和：

，

這里的 包括節(jié)點x及其周圍的鄰居。

與囚徒困境博弈和鏟雪博弈類似，在公共物品博弈中，個體也是根據(jù)某種更新規(guī)則不斷調(diào)整自己的策略。

網(wǎng)絡(luò)演化博弈中通常采用的策略更新規(guī)則有：

（1）最優(yōu)者替代 ^[13]。某個個體模仿周圍鄰居（包括他本人）在此輪博弈中獲得最高平均收益的個體，以其策略作為自己在下輪博弈的策略。

（2）較好者擁有替代機會^[18,19]。每個個體隨機地選擇周圍一個鄰居進行收益比較。如果他的收益比被選擇的鄰居高，那么他保持自己策略不變。如果他的收益比被選擇的鄰居低，則他會以一定的概率選擇該鄰居的策略作為下一輪博弈的策略。

（3）依賴收益差別的策略學習^[20]。每個個體隨機地選擇周圍一個鄰居進行收益比較。他的收益比被選擇鄰居的收益越高（越低），則他選擇該鄰居的策略作為下一輪博弈策略的概率就越低（越高）。

2. 網(wǎng)絡(luò)結(jié)構(gòu)的影響

在相同的策略更新規(guī)則下，不同的網(wǎng)絡(luò)結(jié)構(gòu)會影響系統(tǒng)的合作水平。

在全連接網(wǎng)絡(luò)的囚徒困境博弈中，合作者的收益始終比背叛者低，因此群體的所有個體最終都會成為背叛者。Nowak和May發(fā)現(xiàn)，在二維格子的囚徒困境博弈中，合作者通過形成團簇結(jié)構(gòu)可以有效地抵御背叛者的入侵^[13]。在合作簇內(nèi)部，合作者通過相互協(xié)作獲得很高的收益，從而保護合作簇內(nèi)部的合作者不被外面的背叛者所取代。

Santos等人發(fā)現(xiàn)，相比于規(guī)則網(wǎng)絡(luò)上比較低的合作頻率，無標度網(wǎng)絡(luò)上的囚徒困境、鏟雪和公共物品博弈都能出現(xiàn)非常高的合作水平^[19,20]。他們的研究表明，無標度網(wǎng)絡(luò)上幾乎所有的大度節(jié)點在演化博弈過程中逐漸會被合作者所占據(jù)。由于大度節(jié)點通常擁有比小度節(jié)點更多的收益，無標度網(wǎng)絡(luò)中的許多小度節(jié)點將模仿大度節(jié)點的合作策略，從而導(dǎo)致很高的合作頻率。

唐傳龍等人研究了網(wǎng)絡(luò)平均度對于囚徒困境博弈中合作行為的影響^[22]，發(fā)現(xiàn)適中的網(wǎng)絡(luò)平均度能最好地促進合作。當網(wǎng)絡(luò)平均度很大時候，系統(tǒng)近似于全連接的情況，這個時候合作者的收益始終比背叛者低，合作行為無法存在。當網(wǎng)絡(luò)平均度很小的時候，合作者周圍鄰居過少，導(dǎo)致合作簇內(nèi)部合作者的收益不高，也抑制了合作。當網(wǎng)絡(luò)平均度適中的時候，合作簇內(nèi)部合作者的收益比較高，能有效地抵御外部背叛者的入侵。

榮智海等人研究了度度相關(guān)性對于囚徒困境博弈中合作行為的影響^[23]。發(fā)現(xiàn)相比于隨機相配網(wǎng)絡(luò)，在背叛誘惑參數(shù)值低的時候正配合網(wǎng)絡(luò)抑制合作，而在背叛誘惑參數(shù)值高的時候負配合網(wǎng)絡(luò)能夠促進合作。在正配合網(wǎng)絡(luò)中，大度節(jié)點之間的連接很多，在演化的初始階段，由于背叛的大度節(jié)點獲得比合作的大度節(jié)點更多的收益，因此合作的大度節(jié)點容易采取背叛大度節(jié)點的策略，導(dǎo)致網(wǎng)絡(luò)中所有的大度節(jié)點迅速被背叛者所占據(jù)，從而降低了網(wǎng)絡(luò)的合作水平。在負配合網(wǎng)絡(luò)中，大度節(jié)點之間的連接很少，合作的大度節(jié)點的周圍節(jié)點采取合作策略，而背叛的大度節(jié)點的周圍節(jié)點采取背叛策略，這樣一來，當背叛誘惑參數(shù)值高的時候，網(wǎng)絡(luò)中的合作者依然會在合作的大度節(jié)點周圍存活下來。

榮智海等人還研究了聚類系數(shù)可調(diào)的無標度網(wǎng)絡(luò)上的公共品博弈^[24]。他們的研究發(fā)現(xiàn)，隨著聚類系數(shù)的增大，網(wǎng)絡(luò)的合作頻率提高。公共品博弈是一種群體性博弈，個體不僅參與以自己為中心的群體博弈，還參加以其鄰居為中心的群體博弈。因此在公共品博弈中，個體的收益不僅和鄰居的策略有關(guān)，而且和鄰居的鄰居策略有關(guān)。高聚類的網(wǎng)絡(luò)中會有大量的三角構(gòu)造（一個節(jié)點及其周圍的兩個相互連接的鄰居），使得公共品博弈中的合作簇（相互連接的合作者組成的集團）獲得更高的收益，從而有效地促進合作行為在整個網(wǎng)絡(luò)中的擴散。

任捷等人研究了均質(zhì)小世界網(wǎng)絡(luò)上的囚徒困境博弈^[25]。他們發(fā)現(xiàn)，當網(wǎng)絡(luò)的交叉換邊比例適中的時候（此時網(wǎng)絡(luò)中即有短程連邊也有遠程連邊），網(wǎng)絡(luò)的合作水平達到最高。網(wǎng)絡(luò)中短程連邊的存在，使相臨近的合作者能形成穩(wěn)定的合作簇，同時，適當比例的長程邊，有利于合作者在網(wǎng)絡(luò)中進行大范圍擴散。

3. 策略更新規(guī)則的影響

在相同的網(wǎng)絡(luò)結(jié)構(gòu)上，設(shè)計不同的博弈策略演化規(guī)則會很大程度地影響系統(tǒng)合作行為的表現(xiàn)。

王文旭等人提出了基于記憶的鏟雪博弈^[26]。每輪博弈結(jié)束后，每個個體會根據(jù)鄰居上一時刻的策略進行反思，即采取自己的反策略做一次虛擬博弈，從而得到虛擬收益，然后將真實收益與虛擬收益進行比較，得到所對應(yīng)的最佳策略，并將其記錄到該個體的記憶中。在之后的博弈中，個體會根據(jù)前幾輪所存儲的記憶，決定采取何種策略。研究發(fā)現(xiàn)，二維網(wǎng)絡(luò)上合作頻率和收益參數(shù)r之間具有分段式的臺階關(guān)系，在某些r值附近，合作頻率會從一個值突變到另外一個值。

Szolnoki^[27]等人和關(guān)劍月等人^[28]研究被模仿能力對復(fù)雜網(wǎng)絡(luò)演化博弈的影響。他們把個體分為A、B兩類。A類個體的被模仿能力比B類個體高，表示A類個體的策略比B類個體更容易被別人所模仿。在策略演化時，個體i采取鄰居j的概率不但與二者的收益差有關(guān)，而且正比于鄰居的被模仿能力。設(shè)網(wǎng)絡(luò)中A類個體的比例為v，他們發(fā)現(xiàn)存在適中比例的v，使得網(wǎng)絡(luò)的合作頻率達到最高。

王文旭等人提出了一種最差者改變策略的演化規(guī)則^[29]。每輪鏟雪博弈結(jié)束后，網(wǎng)絡(luò)中收益最低的個體將會改變自己的策略，而網(wǎng)絡(luò)的其他個體保持策略不變。通過先逐漸增大后逐漸減小收益參數(shù)r，他們發(fā)現(xiàn)網(wǎng)絡(luò)的合作頻率與收益參數(shù)r之間的關(guān)系曲線呈現(xiàn)遲滯回線的形狀。

在通常的網(wǎng)絡(luò)演化博弈研究中，網(wǎng)絡(luò)中的節(jié)點隨機地選擇其中一個鄰居進行策略學習。也就是說，節(jié)點選擇哪個鄰居進行策略模仿是沒有任何偏好的。楊涵新等人考慮社會差異性對于選擇鄰居的影響^[30]。由于社會差異性的存在，每個節(jié)點的影響力是不一樣的。設(shè)定每個節(jié)點i的影響力為 ，其中 是一個可調(diào)參數(shù)。當 時候，網(wǎng)絡(luò)中每個節(jié)點的影響力都是相同的，當 （或者 ）時候，度大（或者度?。┑墓?jié)點的影響力比較大。節(jié)點x選擇一個鄰居y進行策略更新的概率正比于節(jié)點y的影響力，即：

，

節(jié)點x采取節(jié)點y的策略作為自己下一時間步策略的概率為：

，

其中 是噪音參數(shù)（設(shè)定 ）。節(jié)點x保持自己策略不變的概率為 。研究發(fā)現(xiàn)，當 是一個適中的正值的時候，網(wǎng)絡(luò)的合作頻率最高。這個結(jié)果表明，當大度節(jié)點的影響力適當大的時候，能夠促進系統(tǒng)的合作。

此外，Szabó等人研究策略更新規(guī)則中噪音 的作用^[31]，發(fā)現(xiàn)適中的噪音強度能使網(wǎng)絡(luò)的合作頻率達到最高。吳枝喜等人將博弈關(guān)系對象和策略學習對象分離開^[32]，發(fā)現(xiàn)當博弈關(guān)系對象和學習對象之間存在一定的差異性的時候，可以最好地促進合作。

4. 演化博弈動力學與網(wǎng)絡(luò)結(jié)構(gòu)的共同演化

在通常的網(wǎng)絡(luò)博弈研究中，網(wǎng)絡(luò)結(jié)構(gòu)是靜態(tài)不變的。近年來，人們開始關(guān)注在演化動力學的影響下，網(wǎng)絡(luò)的結(jié)構(gòu)是如何變化的。

Zimmermann等人提出了一個動態(tài)網(wǎng)絡(luò)囚徒困境博弈模型^[33,34]：從一個ER隨機網(wǎng)絡(luò)開始，每輪博弈中個體與直接相連的鄰居進行囚徒困境博弈，它們會采納周圍鄰居(包含自己)中收益最高者的策略作為下一輪博弈。如果一個背叛者發(fā)現(xiàn)它模仿的鄰居是背叛者，并且收益比自己高，則這個不滿意的個體會以概率p 斷開與被模仿的背叛者之間的邊，重新在網(wǎng)絡(luò)中隨機選擇一個節(jié)點連接。他們的研究結(jié)果顯示，只需要一個很小的概率p就可以使動態(tài)網(wǎng)絡(luò)的合作頻率達到一個很高的值。這是因為網(wǎng)絡(luò)中的節(jié)點會不斷拋棄那些背叛節(jié)點，而和合作節(jié)點建立聯(lián)系，從而使合作節(jié)點的度增大，成為網(wǎng)絡(luò)的中心節(jié)點，進而促進整個網(wǎng)絡(luò)合作水平的提高。

Li等人提出了一種由演化博弈驅(qū)動生成的無標度網(wǎng)絡(luò)型^[35]。初始時候，在一個方格網(wǎng)絡(luò)上，每個節(jié)點擁有一個活動的長程邊，每個節(jié)點可以控長程邊的另一端指向期望的節(jié)點。節(jié)點進行按照囚徒困境博弈，策略更新時個體x將它的收益與鄰居中收益最高者y進行比較，如果y鄰居收益高則采納其策略。同時，x把它擁有的長程邊連向y擁有的長程邊所指向的節(jié)點。隨著時間演化，網(wǎng)絡(luò)的度分布呈現(xiàn)無標度特性。

Helbing等人提出的成功驅(qū)動的博弈模型^[36]。在他們的模型中，博弈個體分布在一個二維方格上，個體會遷移到周圍中能使其收益最高的格點上。他們發(fā)現(xiàn)，即使初始所有人都是背叛者，在一定的噪音情況下（個體的策略會以一定概率重置），隨著時間演化，合作行為會出現(xiàn)突然爆發(fā)的現(xiàn)象，即在很短的一段時間內(nèi)，合作者比例迅速增加。

Meloni等人^[37]在一個二維的連續(xù)空間上，考慮博弈個體隨機移動的情況。在他們研究的模型中，每個時間步，每個個體與其周圍一定距離內(nèi)的其他個體進行囚徒困境博弈，隨后以速度v隨機地移動到另外一個地方。他們研究發(fā)現(xiàn)，隨著個體移動速度v的增大，合作頻率降低。

楊涵新等人研究了預(yù)期導(dǎo)致的移動在演化博弈中的作用^[38]。個體與周圍鄰居進行囚徒困境博弈獲得收益，當個體獲得的收益低于它的預(yù)期的時候，它將隨機地遷移到另外一個地方。我們研究發(fā)現(xiàn)，當預(yù)期適中的時候，背叛簇內(nèi)部的背叛者由于收益低于預(yù)期產(chǎn)生移動，而合作簇內(nèi)部的合作者由于收益高于預(yù)期保持不動，導(dǎo)致背叛簇的瓦解和合作簇的擴張，使合作行為在整個群體中得以蔓延。預(yù)期過低和過高的時候，都不利于合作行為的擴散。預(yù)期過低，個體很少進行移動，使得合作簇和背叛簇能同時穩(wěn)定存在。預(yù)期過高，由于個體的頻繁移動，無法形成穩(wěn)定的合作簇，導(dǎo)致合作者的滅亡。

5. 展望

復(fù)雜網(wǎng)絡(luò)上的演化博弈研究是近年來隨著復(fù)雜網(wǎng)絡(luò)研究興起而逐漸引起關(guān)注的一個重要研究課題?；谇叭搜芯抗ぷ鞯幕A(chǔ)，我們對未來復(fù)雜網(wǎng)絡(luò)上的演化博弈研究方向做一個展望。

（1）  前人主要利用數(shù)值仿真手段對復(fù)雜網(wǎng)絡(luò)上的演化博弈進行研究，缺乏嚴格的解析分析。目前的一些近似方法，如平均場方法、對估計方法無法解決異質(zhì)網(wǎng)絡(luò)上的演化博弈問題．因此尋求有效的數(shù)學和統(tǒng)計物理方法，對數(shù)值模擬結(jié)果進行理論分析，是非常有意義的。

（2）  之前復(fù)雜網(wǎng)絡(luò)上的演化博弈研究中，個體通常單純地使用合作或者背叛策略。然而，演化博弈的研究，尤其是實驗研究表明，真實世界中的個體會采用更豐富的策略（如中立策略等），而不僅僅只限于純合作和純背叛兩種。多策略的演化博弈是未來研究的焦點。

（3）  目前，復(fù)雜網(wǎng)絡(luò)上的演化博弈研究絕大部分都是在單個網(wǎng)絡(luò)上進行的。實際上復(fù)雜系統(tǒng)是由許多具有不同結(jié)構(gòu)與功能的網(wǎng)絡(luò)耦合而成的^[39]。例如,在線社交網(wǎng)絡(luò)中的個體是通過互聯(lián)網(wǎng)進行聯(lián)系的，而互聯(lián)網(wǎng)又需要電力網(wǎng)提供的電力支持。多層耦合網(wǎng)絡(luò)上的演化博弈是一個創(chuàng)新型的研究課題，具有廣闊的發(fā)展空間。

（4）  大多數(shù)的復(fù)雜網(wǎng)絡(luò)演化博弈研究中，個體的策略演化不受外界人為的控制。如何通過調(diào)控復(fù)雜網(wǎng)絡(luò)中少數(shù)節(jié)點或者邊上的個體行為，從而使整個系統(tǒng)的合作水平得到提高，是一個具有實踐意義的研究課題。

（5）  演化博弈與其他動力學的結(jié)合是未來研究的焦點。例如，個體接種疫苗可以預(yù)防疾病的感染，但是接種疫苗也會帶來一定的經(jīng)濟成本。我們可以把是否選擇接種疫苗看作是兩種不同的策略，根據(jù)博弈理論的一些研究方法，對個體是否選擇疫苗進行分析^[40]。再比如，利用演化博弈理論研究車輛是否搶道對交通的影響。

參考文獻：

[1]   J. Maynard Smith, Evolution and the Theory of Games (Cambridge University Press, Cambridge, England, 1982).

[2]   A. M. Colman, Game Theory and its Applications in the Social and Biological Sciences (Butterworth-Heinemann, Oxford, 1995).

[3]   J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944).

[4]   J. F. Nash, Equilibrium points in n-person games, Proceedings of the National Academy of Sciences 36 (1950) 48-49.

[5]   J. M. Smith and G. R. Price, The logic of animal conflict, Nature 246 (1973) 15-18.

[6]   J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics (Cambridge University Press, Cambridge, England, 1998).

[7]   Genetic and Cultural Evolution of Cooperation, edited by Peter Hammerstein (MIT, Cambridge, MA, 2003).

[8]   R. Axelrod, The Evolution of Cooperation (Basic books, New York, 1984).

[9]   H. Gintis, Game Theory Evolving (Princeton University, Princeton, NJ, 2000).

[10] R. Axelrod and W. D. Hamilton, The evolution of cooperation, Science 211 (1981): 1390-1396.

[11] R. Sugden, The Economics of Rights, Cooperation and Welfare (Blackwell, Oxford, England, 1986).

[12] G. Hardin, The Tragedy of the Commons, Science 162 (1968): 1243-1248.

[13] M. A. Nowak and R. M. May, Evolutionary games and spatial chaos, Nature (London) 359 (1992):826-829.

[14] R. Albert and A.–L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002): 47-97.

[15] M. E. J. Newman, The structure and function of complex networks, SIAM Review 45 (2003): 167-256.

[16] G. Szabó and G. Fath, Evolutionary games on graphs, Phys. Rep. 446 (2007) 97-216.

[17] M. Perc and A. Szolnoki, Coevolutionary games—A mini review, Biosystems 99 (2010): 109-125.

[18] C. Hauert and M. Doebeli, Spatial structure often inhibits the evolution of cooperation in the snowdrift game, Nature 428 (2004): 643- 646.

[19] F. C. Santos, M. D. Santos and J. M. Pacheco, Social diversity promotes the emergence of cooperation in public goods games, Nature 454 (2008): 213-216.

[20] G. Szabó and C. T?ke, Evolutionary prisoner’s dilemma game on a square lattice, Phys. Rev. E 58 (1998): 69.

[21] F. C. Santos and J. M. Pacheco, Scale-Free Networks Provide a Unifying Framework for the Emergence of Cooperation, Phys. Rev. Lett. 95 (2005) :098104.

[22] C.-L.Tang, W.-X. Wang, X. Wu, et al., Effects of average degree on cooperation in networked evolutionary game, European Physical Journal B 53 (2006): 411-415.

[23] Z. Rong, X. Li and X. F. Wang, Roles of mixing patterns in cooperation on a scale-free networked game, Physical Review E 76 (2007) :027101.

[24] Z. Rong, H.-X. Yang and W.-X. Wang, Feedback reciprocity mechanism promotes the cooperation of highly clustered scale-free networks, Phys. Rev. E 82 (2010) :047101.

[25] J. Ren, W.-X. Wang and F. Qi, Randomness enhances cooperation: A resonance-type phenomenon in evolutionary games, Phys. Rev. E 75 (2007) :045101.

[26] W.-X. Wang, J. Ren, G. Chen, et al, Memory-based snowdrift game on networks, Physical Review E, 74 (2006): 056113.

[27] A. Szolnoki and G. Szabó, Cooperation enhanced by inhomogeneous activity of teaching for evolutionary Prisoner's Dilemma games, EPL 77 (2007) 30004.

[28] J.-Y. Guan, Z.-X. Wu and Y.-H. Wang, Effects of inhomogeneous activity of players and noise on cooperation in spatial public goods games, Physical Review E 76 (2007) :056101.

[29] W.-X. Wang, J. Lü, G. Chen, and P. M. Hui, Phase transition and hysteresis loop in structured games with global updating, Phys. Rev. E 77 (2008): 046109.

[30] H.-X. Yang, W.-X. Wang, Z.-X. Wu, et al, Diversity-optimized cooperation on complex networks, Phys. Rev. E 79 (2009): 056107.

[31] G. Szabó, J. Vukov and A. Szolnoki, Phase diagrams for an evolutionary prisoner's dilemma game on two-dimensional lattices, Physical Review E 72 (2005) :047107.

[32] Z.-X. Wu and Y.-H. Wang, Cooperation enhanced by the difference between interaction and learning neighborhoods for evolutionary spatial prisoner's dilemma games, Physical Review E 75 (2007): 041114.

[33] M. G. Zimmermann, V. M. Eguíluz and M. S. Miguel, Coevolution of dynamical states and interactions in dynamic networks, Physical Review E 69 (2004):065102.

[34] M. G. Zimmermann and V. M. Eguíluz, Cooperation, social networks, and the emergence of leadership in a prisoner's dilemma with adaptive local interactions, Physical Review E 72 (2005):056118.

[35] W. Li, X.  Zhang, and G. Hu, How scale-free networks and large-scale collective cooperation emerge in complex homogeneous social systems, Physical Review E 76 (2007): 045102.

[36] D. Helbing and W.Yu, The outbreak of cooperation among success-driven individuals under noisy conditions, Proc. Natl. Acad. Sci. U.S.A. 106 (2009): 3680-3685.

[37] S. Meloni, A. Buscarino, L. Fortuna, et al, Effects of mobility in a population of prisoner’s dilemma players, Phys. Rev. E 79 (2009): 067101.

[38] H.-X. Yang, Z.-X. Wu and B.-H. Wang, Role of aspiration-induced migration in cooperation, Phys. Rev. E 81 (2010): 065101.

[39] M. Kurant, P. Thiran, Layered complex networks, Phys Rev Lett, 96 (2006) :138701.

[40] F. Fu, D. I. Rosenbloom, L. Wang, et al, Imitation dynamics of vaccination behaviour on social networks. Proc R Soc B 278 (2011): 42-49.