陳曉婷, 朱 標(biāo)

(溫州大學(xué)物理與電子信息工程學(xué)院, 浙江 溫州 325035)

0 引 言

從生物進(jìn)化論到人類社會的各種經(jīng)濟(jì)行為，博弈論都扮演了重要的角色,它為分析和解決各種沖突提供了方法論的指導(dǎo)并能預(yù)測各種可能出現(xiàn)的危機.博弈論現(xiàn)已廣泛應(yīng)用于生物學(xué)、心理學(xué)、計算機科學(xué)、政治學(xué)、軍事學(xué)及經(jīng)濟(jì)學(xué)[1-8]中，它從真實的自然界、人類社會和經(jīng)濟(jì)行為中抽象出的各種博弈模型能很好的模擬現(xiàn)實中的各種問題，這也為具體問題能通過一致的方法抽象出模型得以重塑和分析創(chuàng)造了統(tǒng)一的框架.

隨著復(fù)雜網(wǎng)絡(luò)研究的興起，人們對網(wǎng)絡(luò)的結(jié)構(gòu)演化和復(fù)雜性等都有了清晰的認(rèn)識，而具有良好拓?fù)浣Y(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)能更好的反映真實的人們之間的關(guān)系，于是掀起了在復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)下研究博弈的熱潮，其中Nowak和May首先研究了規(guī)則網(wǎng)絡(luò)上的囚徒困境模型[9]，首次指出了網(wǎng)絡(luò)結(jié)構(gòu)對博弈演化所起的重要作用.隨后，大量的研究結(jié)果表明[10]，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)在很大程度上影響了博弈的合作水平.Hauert和Doebeli研究了規(guī)則網(wǎng)絡(luò)上的雪堆博弈模型[11]，得出與囚徒困境不一樣的結(jié)論.其后Szabo等研究了均勻小世界網(wǎng)絡(luò)的囚徒困境模型[12]，對比規(guī)則網(wǎng)絡(luò)，得出更一般的結(jié)論：異質(zhì)因素促進(jìn)合作的涌現(xiàn).Tomassini研究了WS小世界網(wǎng)絡(luò)上的雪堆博弈模型[13]，發(fā)現(xiàn)合作行為與博弈采用的演化規(guī)則、收益比以及小世界網(wǎng)絡(luò)的重連概率密切相關(guān).Santos研究了無標(biāo)度網(wǎng)絡(luò)上的囚徒困境和雪堆博弈模型[14]，再次驗證了異質(zhì)因素促進(jìn)合作涌現(xiàn)的一般性結(jié)論，并指出無標(biāo)度網(wǎng)絡(luò)是目前最利于合作涌現(xiàn)的網(wǎng)絡(luò)結(jié)構(gòu).

本文的工作即為在無標(biāo)度網(wǎng)絡(luò)模型下考察收益系數(shù)、平均度、記憶長度等因素對雪堆博弈中合作頻率的影響，通過Monte-Carlo數(shù)值模擬方法研究了無標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)下它們與合作頻率的變化關(guān)系，著重分析了收益系數(shù)變化導(dǎo)致的合作頻率的非單調(diào)現(xiàn)象，并發(fā)現(xiàn)平均度的增加在一定范圍內(nèi)對合作頻率的增長具有促進(jìn)作用，當(dāng)超過一定值時，在記憶長度和收益系數(shù)的共同影響下，合作頻率漸漸趨于穩(wěn)定，并指出記憶長度對合作頻率影響的不確定關(guān)系.

1 模型描述

首先我們選擇BA無標(biāo)度網(wǎng)絡(luò)模型進(jìn)行博弈演化，BA無標(biāo)度網(wǎng)絡(luò)最初是Barabási 和Albert為了解釋許多真實相互作用網(wǎng)的度分布具有冪律形式而提出的一個無標(biāo)度網(wǎng)絡(luò)模型[15]，他們認(rèn)為許多實際網(wǎng)絡(luò)具有增長特性和優(yōu)先連接這兩個重要性質(zhì)，即網(wǎng)絡(luò)的規(guī)模是不斷擴(kuò)大的，網(wǎng)絡(luò)中新的節(jié)點更傾向于連接度較大的節(jié)點.BA無標(biāo)度網(wǎng)絡(luò)的構(gòu)造算法如下：由一個具有m0個節(jié)點的網(wǎng)絡(luò)開始，每次引入一個新的節(jié)點，連接到m個已存在的節(jié)點上，這里m

(1)

經(jīng)過t步后，這種算法產(chǎn)生了一個有N=t+m0個節(jié)點、mt條邊的網(wǎng)絡(luò).通過引入新的節(jié)點和優(yōu)先連接構(gòu)造出來的網(wǎng)絡(luò)，度分布具有許多真實網(wǎng)絡(luò)具有的冪律形式，它具有小的平均距離和小的聚集系數(shù).

對于博弈模型，我們選擇Wang等考慮到個體的決策過程與記憶和經(jīng)驗密切相關(guān)，提出的關(guān)于歷史記憶的雪堆博弈模型[16]，該模型的基本規(guī)則為：(1)將N個博弈參與者置于網(wǎng)絡(luò)的節(jié)點上，每一輪所有相互連接的參與者同時博弈，某個參與者的總收益為根據(jù)一定的收益矩陣與所有鄰居分別進(jìn)行博弈后的收益之和；(2)當(dāng)一輪博弈結(jié)束后，所有參與者更新自己的策略庫，同時根據(jù)某個規(guī)則更新自身策略，然后進(jìn)行下一輪的博弈；(3)重復(fù)(1)、(2)步驟.本文采用簡化的雪堆博弈收益矩陣如表1所示，(1)當(dāng)兩個參與者都合作時，他們的收益皆為R=1；(2)其中一個參與者合作而另一個參與者背叛時，合作者的收益S=1-r,背叛者的收益T=1+r；(3)當(dāng)兩個參與者都選擇背叛時，他們的收益均為P=0，其中參數(shù)r稱為收益系數(shù).參與者的策略庫更新及策略更新方案如下：參與者會根據(jù)周圍鄰居上一時刻的策略進(jìn)行反思，即采用自己的反策略做一次虛擬的博弈，從而得到虛擬的總收益，然后將真實收益與虛擬收益進(jìn)行比較，得到所對應(yīng)的最佳策略，并將這個最佳策略記錄到該參與者的記憶中，那么每個參與者記憶中所記錄的都是歷史時刻最佳的策略，以上規(guī)則考慮到了人的有限記憶的特性，也就是人不可能記錄以前發(fā)生的所有事情的信息，那么就需要記錄最有用的信息.另一方面，人只能記錄有限的時間段內(nèi)所發(fā)生的事情，所以假設(shè)每個參與者的記憶長度有限(設(shè)長度為M)，即為從上一時刻到M時刻以前的歷史最佳策略,然后每個參與者根

表1 雪堆博弈的收益矩陣

2 結(jié)果分析

采用Monte-Carlo方法進(jìn)行數(shù)值模擬，選取網(wǎng)絡(luò)節(jié)點總數(shù)為10 000，初始網(wǎng)絡(luò)中合作者和背叛者各占50%，隨機進(jìn)行分布，合作頻率fc為合作者所占的比例，每次模擬均是在網(wǎng)絡(luò)穩(wěn)定(t=8 000步)之后進(jìn)行，合作頻率fc為80 000

在BA無標(biāo)度網(wǎng)絡(luò)中，為了研究合作頻率隨收益系數(shù)的變化關(guān)系，固定網(wǎng)絡(luò)的平均度為6，分別取節(jié)點的記憶長度為2、7、30，得到結(jié)果如圖1所示，它具有如下的特點：(1)fc并不是隨著r的增大而減小，相反，在某些區(qū)域，fc隨著r的增加反而出現(xiàn)大幅上升，并且存在一個最優(yōu)的合作頻率值；(2)與規(guī)則網(wǎng)絡(luò)相同(如圖2，節(jié)點的度均為4，節(jié)點的記憶長度分別取2、7、30)，fc曲線是不連續(xù)的，被分為不同的幾段，分段的數(shù)目對應(yīng)于節(jié)點的平均度；(3)圖1和圖2都以坐標(biāo)點(0.5，0.5)為180°旋轉(zhuǎn)對稱；(4)M不影響分段點的r值，只影響fc的值，這些結(jié)論和文獻(xiàn)[16]一致.當(dāng)M=1時，為了避免出現(xiàn)文獻(xiàn)[16]的策略振蕩，本文的仿真均是在M≥2時進(jìn)行的.

相對于規(guī)則網(wǎng)絡(luò)，BA無標(biāo)度網(wǎng)絡(luò)的度分布發(fā)生了明顯的變化，網(wǎng)絡(luò)中具有少部分的節(jié)點的度很大，而大部分小度節(jié)點與此大度節(jié)點相連，所以每個節(jié)點不再像規(guī)則網(wǎng)絡(luò)一樣具有相同的連接度，這使得不同節(jié)點與鄰居博弈時獲得的收益存在差別，每個節(jié)點為了獲得最大化的收益，會根據(jù)節(jié)點的鄰居的策略選擇合作或背叛策略，如果一旦大度的節(jié)點選擇合作策略，那么與此連接的大部分的小度節(jié)點為了利益最大化就會選擇欺騙策略，從而導(dǎo)致fc偏低；當(dāng)度大節(jié)點選擇背叛策略時，度小的節(jié)點不得不選擇合作策略從它的鄰居那里獲得1-r的收益，這樣小度節(jié)點的被動選擇實際上是導(dǎo)致分段處fc升高的主要原因.由此可見，即使是r增大，也會出現(xiàn)圖1所示的fc升高的現(xiàn)象.然而，當(dāng)r變的很大時，選擇合作時非常低的收益會導(dǎo)致系統(tǒng)中絕大多數(shù)的節(jié)點選擇背叛行為，因此會使此時的系統(tǒng)中的fc創(chuàng)新低，出現(xiàn)如圖1所示的突然下降.

圖1 BA無標(biāo)度網(wǎng)絡(luò)中合作頻率fc與收益系數(shù)r的關(guān)系圖 圖2 規(guī)則網(wǎng)絡(luò)中合作頻率fc與收益系數(shù)r的關(guān)系圖

細(xì)致觀察圖1，發(fā)現(xiàn)記憶長度M對合作頻率大小有影響，且不同的r對合作頻率的影響不同，文[16]考察了相同平均度不同r時的fc隨記憶長度的變化關(guān)系，如圖3((a)中取網(wǎng)絡(luò)的為4，r分別取為0.35、0.42、0.48;(b)中取網(wǎng)絡(luò)的平均度為8，收益系數(shù)r分別為0.41、0.45、0.48)所示，記憶長度對不同平均度的網(wǎng)絡(luò)結(jié)構(gòu)、不同的收益系數(shù)具有不同的作用，如平均度=4的情況下，對于r=0.42，fc不依賴于M；而0.34=8的情況，r=0.45是分界點，當(dāng)r<0.45和r>0.45時，fc分別表現(xiàn)為隨M增加時的減小和增加.同時觀察圖1、圖2還能發(fā)現(xiàn)記憶長度在r較大或者較小時對fc影響較大，而r處于0.5附近時,M對其影響最弱，甚至不起作用.r較小時，M對fc的作用是積極的，即M的增加能促進(jìn)合作頻率的提高，這也說明，誘惑較小時，人們更易于理性；r較大時，M對fc的作用是消極的，即M的增加降低了合作頻率，這也在一定程度上說明了誘惑足夠大時，人們更易于趨于不理智，從而導(dǎo)致整體的利益受到損失.

圖3 BA無標(biāo)度網(wǎng)絡(luò)中合作頻率fc隨記憶長度M的關(guān)系

下面繼續(xù)考察網(wǎng)絡(luò)的平均度對合作頻率fc的影響，由對稱性，模擬選取收益系數(shù)r=0.1進(jìn)行，如圖4((a)圖M取為2，(b)圖M分別取4、5、6、7、15)所示，分別給出了不同的記憶長度下的fc隨的變化關(guān)系.首先觀察圖4(a)，發(fā)現(xiàn)fc不是的單調(diào)函數(shù)，初始時，隨著的增加，fc單調(diào)上升，上升到一定值時，fc近似變?yōu)閱握{(diào)平滑的直線；與圖4(a)不同的是，圖4(b)隨著記憶長度的增加，fc經(jīng)歷單調(diào)上升之后，不再變?yōu)榻破交本€，而是有一定的起伏之后到達(dá)近似均衡狀態(tài).

圖4 BA無標(biāo)度網(wǎng)絡(luò)中合作頻率fc隨平均度的變化關(guān)系圖

當(dāng)記憶長度很小時，很容易出現(xiàn)策略振蕩，即在連續(xù)兩次博弈中，很大一部分節(jié)點的策略同時發(fā)生轉(zhuǎn)變.本文所有的模擬均是在多次取平均時計算得到的，所以M較小時由于策略振蕩造成fc曲線比較平滑.逐漸增大記憶長度發(fā)現(xiàn)，fc隨變化的曲線會出現(xiàn)小幅振蕩而后漸趨于均衡狀態(tài)而達(dá)到收斂.這種小幅的震蕩主要是由于圖1中的分段造成的，隨著r的增大，fc達(dá)到一定高度后會突然下降，這種下降與M無關(guān)，當(dāng)我們選定了r之后，網(wǎng)絡(luò)的的不同造成的分段就確定了.同時，M稍小時，隨著網(wǎng)絡(luò)的的增大，每個節(jié)點的鄰居也會增多，參與博弈時的個體增多，加之M較小，容易出現(xiàn)策略振蕩，多次取平均之后，fc突然增大后不再出現(xiàn)小幅振蕩而是趨近于平滑直線也就不難理解了.

通過以上分析，得出無標(biāo)度網(wǎng)絡(luò)上的博弈行為不同于規(guī)則網(wǎng)絡(luò)，由于節(jié)點異質(zhì)性導(dǎo)致的整個網(wǎng)絡(luò)的合作頻率隨收益系數(shù)的變化比較明顯，與預(yù)期不同的是，一定程度上的收益系數(shù)的增大并不是總是降低合作頻率.記憶長度的作用在特定段的影響是顯然的，但是也出現(xiàn)了對合作頻率不起作用的真空段，這也表明在收益系數(shù)的作用下，人們有時候是不理性的.后來考察無標(biāo)度網(wǎng)絡(luò)的平均度對合作頻率的影響，發(fā)現(xiàn)了平均度較小時對合作頻率增加的積極作用，隨著平均度的增加，這種積極作用逐漸被收益系數(shù)、記憶長度等的綜合作用消減.

3 結(jié) 論

本文在BA無標(biāo)度網(wǎng)絡(luò)上研究了基于記憶的雪堆博弈模型的合作行為，深入分析了收益系數(shù)r、記憶長度M、網(wǎng)絡(luò)的平均度對合作頻率fc的影響，仿真模擬結(jié)果表明：(1)合作頻率fc是收益系數(shù)r的非單調(diào)函數(shù)；(2)記憶長度M對合作頻率fc的作用是不確定的;(3)合作頻率fc是網(wǎng)絡(luò)的平均度的非單調(diào)函數(shù)，對較小的r(如為0.1)時，發(fā)現(xiàn)一定的平均度的增加對合作頻率的增長具有促進(jìn)作用，當(dāng)平均度繼續(xù)增大時，合作頻率會出現(xiàn)小幅振蕩進(jìn)而達(dá)到收斂.通過本文的分析，為了提高合作頻率，可以適當(dāng)增大r的值，也就是說適當(dāng)?shù)墓膭钭运降男袨榉炊赡芨诤献?；記憶長度對不同r時所起的作用是不同的，所以我們要取得最優(yōu)的合作頻率，一定要綜合考慮收益系數(shù)和記憶長度之間的關(guān)系.網(wǎng)絡(luò)結(jié)構(gòu)也在一定程度上著影響合作頻率，所以選擇合適的網(wǎng)絡(luò)也是未來工作的著眼點.

參考文獻(xiàn)

[1] J.Hofbauer,K.Sigmund.Evolutionary Games and Population Dynamics[M].Cambridge: Cambridge University Press,1998.

[2] R.Cressman.Evolutionary Dynamics and Extensive Form Games[M].Cambridge:MIT Press,2003.

[3] L.A.Dugatkin.Cooperation Among Animals: an Evolutionary Perspective[M].Oxford: Oxford University Press,1997.

[4] H.Gintis.Game Theory Evolving[M]. Prineeton:Princeton University,2000.

[5] A.M.Colman.Game Theory and Its Applications in the Social and Biological Scienees[M]. Oxford:Butterworth-Heinemann,1995.

[6] B.Skyrms.The Stag Hunt and the Evolulion of Social Structure[M]. Cambridge: Cambridge University Press,2004.

[7] K.G.Binmore.Playing Fair:Game Theory and the Social Contract[M].Cambridge:MIT Press,1994.

[8] 王 龍,伏 峰,陳小杰,等.復(fù)雜網(wǎng)絡(luò)上的演化博弈[J].智能系統(tǒng)學(xué)報,2007,2(2):1-10.

[9] M.A.Nowak,R.M.May.Evolutionary games and spatial chaos[J].Nature,1992, 359:826-829.

[10] B.Kerr,M.A.Riley,M.W.Feldman,etal.Local dispersal promotes biodiversity in a real-life game of rock-paper-scissors[J]. Nature(London), 2002,418:171-174.

[11] C.Hauert, M.Doebeli.Spatial atructure often inhibits the evolution of cooperation in the snowdrift game[J].Nature(London),2004,428:643-646.

[12] F.C.Santos,J.F.Rodrigues,J.M.Pacheco.Epidemic spreading and cooperation dynamics on homogeneous small-world networks[J].Phys. Rev.E.,2005,72:056128.

[13] M.Tomassini,L.Luthi,M.Giacobini.Hawks and doves on small-world networks[J]. Phy.Rev.E., 2006,73:016132.

[14] F.C.Santos, J.M.Pacheco. Scale-free networks provide a unifying framework for the emergence of cooperation[J]. Phys. Rev. Lett.,2005, 95:098104.

[15] A.L.Barabási,R.Albert.Emergence of scanling in random networks[J]. Science, 1999, 286(5439):509-512.

[16] W.X.Wang,J.Ren,G.Chen,etal.Memory-based snowdrift game on networks[J]. Phys.Rev.E., 2006,74:056113.