摘要：博弈論是研究個體之間相互作用的，演化博弈論能夠很好地解釋現(xiàn)實中的網(wǎng)絡(luò)，因而博弈演化理論的研究越來越來得到關(guān)注。本文對常見的復(fù)雜網(wǎng)絡(luò)博弈理論做了介紹，然后我們探討了這一領(lǐng)域的研究趨勢。

關(guān)鍵詞：網(wǎng)絡(luò)結(jié)構(gòu)；囚徒困境；合作行為

中圖分類號：TP3 文獻標(biāo)識碼：A 文章編號：1007-9599 （2012） 22-0000-02

博弈論（Game theory）主要是研究個體在相互作用過程中如何獲得最大利益的理論，是對合作與競爭關(guān)系的一種反映。一般而言，一個博弈通常由以下幾個組成部分：a參與博弈的個體至少兩個b.博弈個體可以從策略集中選取自己的博弈策略c.博弈結(jié)束后博弈個體可以得到得收益d.博弈個體進行策略更新的目的是為了達到最大收益。

經(jīng)典博弈論認為博弈個體是非常理性的，博弈目的都是追求自己的最大收益，而且也知道其它博弈個體也是完全理性的；而演化博弈論以種群為研究對象，認為博弈個體是有限理性的，博弈個體的策略可能因變異而改變。

演化博弈論的特征與實際網(wǎng)絡(luò)較為符合，使得復(fù)雜網(wǎng)絡(luò)上的博弈演化研究得到越來約多學(xué)者的參與和研究，在這里主要綜述一下復(fù)雜網(wǎng)絡(luò)上的網(wǎng)絡(luò)結(jié)構(gòu)是如何對博弈產(chǎn)生影響的。

1 復(fù)雜網(wǎng)絡(luò)中的經(jīng)典網(wǎng)絡(luò)模型

當(dāng)策略更新規(guī)則相同時，網(wǎng)絡(luò)結(jié)構(gòu)不一樣，對博弈的影響也不一樣。在這里先介紹一下對演化博弈有影響的網(wǎng)絡(luò)：規(guī)則網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)。

1.1 規(guī)則網(wǎng)絡(luò)：網(wǎng)絡(luò)中節(jié)點間按某種規(guī)則連接的網(wǎng)絡(luò)稱之為規(guī)則網(wǎng)絡(luò)。規(guī)則網(wǎng)絡(luò)中每個節(jié)點的邊數(shù)都是一樣的有，即有相同的鄰居數(shù)或者度（一般用K來表示節(jié)點的度），規(guī)則網(wǎng)絡(luò)節(jié)點之間聚成團的趨勢比較大并且節(jié)點間平均最短路徑比較大。

1.2 小世界網(wǎng)絡(luò)：節(jié)點間平均路徑長度比較短而聚集系數(shù)比較大是小世界網(wǎng)絡(luò)的重要特征。小世界網(wǎng)絡(luò)分為兩種，一種是WS小世界網(wǎng)絡(luò)，在規(guī)則網(wǎng)絡(luò)上進行隨機化重連得到的；另一種是NW小世界網(wǎng)絡(luò)，在規(guī)則網(wǎng)絡(luò)上隨機化加邊得到的。

1.3 無標(biāo)度網(wǎng)絡(luò)：由于沒有一個確定的參量來描述的網(wǎng)絡(luò)而被稱作無標(biāo)度網(wǎng)絡(luò)。無標(biāo)度網(wǎng)絡(luò)的度分布不同于小世界網(wǎng)絡(luò)，呈冪律分布，最著名的有Barabasi和Albert于1999年提出的BA模型。無標(biāo)度網(wǎng)絡(luò)中網(wǎng)絡(luò)節(jié)點數(shù)越大聚集系數(shù)越小。BA無標(biāo)度網(wǎng)絡(luò)節(jié)點總數(shù)具有增長性（即每個時間步都有新的節(jié)點加入）和優(yōu)先連接性（即新加入的節(jié)點優(yōu)先與原網(wǎng)絡(luò)中節(jié)點度大的節(jié)點連接）。

2 典型的博弈模型

2.1 囚徒困境博弈：囚徒困境博弈模型中，每個個體都有一半的機會選擇背叛策略或者合作策略。若兩個個體都合作，那么每個個體得到的收益為R；若兩個個體都采取背叛策略，那么每個個體收益為p；若一方采取合作策略另一方采取背叛策略，則合作者收益為S，背叛者收益為T，且收益之間的關(guān)系滿足T>R>P>S和R+R>T+S。囚徒困境認為每個博弈者（即“囚徒”）都尋求自身利益的最大化，每個博弈者都會選擇能達到收益最大的策略——背叛策略。

2.2 雪堆博弈：與囚徒困境博弈相比，雪堆博弈中一個博弈個體選擇的策略會影響其它個體所選的策略。若對方采取背叛策略（即呆在車中），那自己就要采取合作策略（鏟雪），相反，若對方鏟雪（即合作策略），自己就可以采取背叛策略（即等待）。雪堆模型與囚徒困境的主要區(qū)別在于收益大小不同。在囚徒困境博弈中T>R>P>S，而在雪堆模型中T>R>S>P。

3 網(wǎng)絡(luò)演化博弈的策略更新規(guī)則

3.1 模仿最優(yōu)者：認為博弈個體都是完全理性的，每輪博弈結(jié)束后，博弈個體比較自己和鄰居的收益，選取收益最大的那個鄰居的策略做為下一次博弈所采取的策略。

3.2 模仿優(yōu)勝者：認為個體有限理性，即個體在更新策略時，以一定概率采取某些收益比自身高的鄰居的策略。

3.3 配對比較：即個體在每輪博弈結(jié)束后根據(jù)收益的情況隨機某個概率選擇某一鄰居的策略。

4 網(wǎng)絡(luò)結(jié)構(gòu)對博弈模型的影響

當(dāng)網(wǎng)絡(luò)的策略更新規(guī)則相同，網(wǎng)絡(luò)結(jié)構(gòu)的不同會對網(wǎng)絡(luò)的博弈合作產(chǎn)生不同的影響。

4.1 規(guī)則網(wǎng)絡(luò)—囚徒困境模型：在規(guī)則網(wǎng)絡(luò)上，認為每個博弈個體與它的4個鄰居進行博弈，并累計總收益。每輪博弈結(jié)束后，把博弈個體的本輪總收益與其所有鄰居的收益相比較，取收益最高的鄰居策略作為下一輪博弈的策略。令囚徒困境博弈中參數(shù)T=b>1，R=1，P=S=0。證實當(dāng)b在1≤b≤2范圍內(nèi)波動時，采取合作策略的博弈者之間形成緊密的簇來抵御選擇背叛策略的入侵者。這種合作簇不會消失，但會受時間的影響而改變形狀，并且網(wǎng)絡(luò)中合作者的比例（被稱為合作頻率，是衡量系統(tǒng)合作涌現(xiàn)程度的重要指標(biāo)）會趨于穩(wěn)定。對有空間結(jié)構(gòu)的網(wǎng)絡(luò)（如二維方格網(wǎng)絡(luò)），合作行為能夠在囚徒困境博弈中出現(xiàn)并且穩(wěn)定維持。這是由于空間結(jié)構(gòu)的存在使得合作者容易形成緊密的簇來抵御背叛者的入侵。

4.2 規(guī)則網(wǎng)絡(luò)—雪堆博弈模型：規(guī)則網(wǎng)絡(luò)上雪堆博弈的合作者比例比納什均衡態(tài)下博弈個體的低——說明空間結(jié)構(gòu)阻礙了合作的產(chǎn)生。比較雪堆博弈和囚徒困境博弈的模擬圖相比，可以發(fā)現(xiàn)雪堆博弈更有利于合作者聚成絲狀簇。當(dāng)博弈者的付出的代價和獲得的收益相差不大時，就會使背叛者容易入侵，從而導(dǎo)致系統(tǒng)合作頻率下降，雪堆博弈與囚徒困境在合作演化上的根本區(qū)別也就在此。也就是對同一種規(guī)則網(wǎng)絡(luò)而言，一種博弈促進合作，另外一種博弈中抑制合作。

4.3 小世界網(wǎng)絡(luò)—囚徒困境：Hauert和Szabo對均勻小世界網(wǎng)絡(luò)和隨機均勻網(wǎng)絡(luò)在保持度分布相同的前提下進行了研究。采用一種隨機演化策略：一個博弈者以一定概率隨機選取它的一個鄰居的策略作為下一輪博弈的策略。結(jié)果表明：由于小世界網(wǎng)絡(luò)長程邊的作用，使得均勻小世界網(wǎng)絡(luò)和隨機均勻網(wǎng)絡(luò)比規(guī)則網(wǎng)絡(luò)更能促進合作的涌現(xiàn)。由此得出結(jié)論即節(jié)點度的差異能促進合作的涌現(xiàn)：

（1）小世界網(wǎng)絡(luò)節(jié)點度的差異性使其比規(guī)則格子更利于合作的涌現(xiàn)；

（2）WS小世界網(wǎng)絡(luò)度存在異質(zhì)性，使得它比度均勻分布的小世界網(wǎng)絡(luò)合作頻率更高。

4.4 小世界網(wǎng)絡(luò)—雪堆博弈：研究發(fā)現(xiàn)網(wǎng)絡(luò)的重連概率，收益的比較以及博弈演化規(guī)則同時作用于網(wǎng)絡(luò)時，發(fā)現(xiàn)空間結(jié)構(gòu)時而促進合作的涌現(xiàn)，時而抑制合作的產(chǎn)生.一些學(xué)者研究了基于距離的空間小世界網(wǎng)絡(luò)上的雪堆博弈，發(fā)現(xiàn)與規(guī)則網(wǎng)絡(luò)相比，在小世界網(wǎng)絡(luò)中，距離無關(guān)能夠促進合作行為涌現(xiàn)；而距離相關(guān)則抑制了合作的產(chǎn)生。這是因為冪指數(shù)增加引起了短程連接的增加和長程連接的減少，這使網(wǎng)絡(luò)在損益比較大時阻礙了合作的產(chǎn)生。

4.5 無標(biāo)度網(wǎng)絡(luò)——囚徒困境：大量現(xiàn)實網(wǎng)絡(luò)節(jié)點的度分布具冪律的特點。Santos研究了BA無標(biāo)度網(wǎng)絡(luò)、隨機圖、規(guī)則格子和隨機無標(biāo)度網(wǎng)絡(luò)對合作涌現(xiàn)的影響，認為無標(biāo)度網(wǎng)絡(luò)中節(jié)點之間的度大小差異性太大，使得度比較大的節(jié)點之間的合作行為傳播更容易更頻繁，進而帶動了大量小度節(jié)點在無標(biāo)度網(wǎng)絡(luò)中傳播。研究認為，無標(biāo)度網(wǎng)絡(luò)是合作行為是最容易涌現(xiàn)的網(wǎng)絡(luò)結(jié)構(gòu)。

4.6 無標(biāo)度網(wǎng)絡(luò)——雪堆博弈：Santos研究了無標(biāo)度網(wǎng)絡(luò)上的雪堆博弈，證實促雪堆博弈中合作行為的涌現(xiàn)也是無標(biāo)度特性導(dǎo)致的。通過對無標(biāo)度網(wǎng)絡(luò)上的擴展雪堆博弈的研究，發(fā)現(xiàn)網(wǎng)絡(luò)博弈者之間的合作水平會因無標(biāo)度網(wǎng)絡(luò)異質(zhì)性的增加而增強。當(dāng)采取合作策略的博弈者比例恒定時，采取背叛策略的博弈者比例增加，采取搖擺策略的博弈者比例減少。這說明網(wǎng)絡(luò)的節(jié)點的度差異性越大，選擇穩(wěn)定策略的個體就越多。

5 復(fù)雜網(wǎng)絡(luò)博弈演化發(fā)展方向與展望

復(fù)雜網(wǎng)絡(luò)上的演化博弈研究是近幾年研究的熱門領(lǐng)域，目前研究的都是比較簡單的博弈演化，多數(shù)科學(xué)家已經(jīng)開始朝更復(fù)雜與實際網(wǎng)絡(luò)更接近的方向去研究，復(fù)雜網(wǎng)絡(luò)上的博弈演化趨勢主要在以下幾個方面：

5.1 目前對囚徒困境博弈和雪堆博弈模型的研究較深入和透徹，其它博弈模型的研究較少。為了構(gòu)造更加貼近實際情況的博弈模型。需要增加或提煉新的博弈模型。

5.2 大部分學(xué)者在對博弈演化進行研究時都認為博弈者只能采取背叛策略或者合作策略，但在現(xiàn)實世界網(wǎng)絡(luò)中有的個體有可能采取中立策略或者搖擺策略等策略，有必要深入研究博弈個體在采取多策略時對網(wǎng)絡(luò)博弈演化的影響

5.3 現(xiàn)今的網(wǎng)絡(luò)上的博弈演化研究主要是通過計算機仿真模擬的，這些仿真結(jié)果的分析還不夠具體和深入，如果可以找到一些數(shù)學(xué)物理的方法研究演化博弈動力學(xué)，有利于更深刻地認識和理解博弈演化。

5.4 為了更好地模擬真實的動態(tài)復(fù)雜系統(tǒng)，把網(wǎng)路結(jié)構(gòu)對博弈演化的影響和博弈演化對網(wǎng)絡(luò)結(jié)構(gòu)的影響結(jié)合起來，研究他們彼此之間的協(xié)同演化關(guān)系很有必要。

參考文獻：

[1]王文旭.復(fù)雜網(wǎng)絡(luò)的演化動力學(xué)及網(wǎng)絡(luò)上的動力學(xué)過程研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2007.

[2]Wang X F，Chen G R.Complex networks：Small-world，scale-free and beyond，IEEE Circuits Syst.Mag，2003，3（1）：6-20.

[3]Szabo G，toke C.Evolutionary prisoner’s dilemma game on a square lattice[J].Physical Review E，1998，58（1）：69.

[4]Wang W X，Ren J，Chen G.et al.Metmory-based snowdrift game on networks[J].Physical Review E，2006，74（5）：056113.

[5]Von Neumann J，Morgenstern O.Theory of games and economic behavior[M].Princeton，NJ：Princeton University Press，1953.

[6]Abrameon G，Kuperman M.Social games in a social network[J].Phys.Rev.E，2001，63：030901.