復雜網絡上演化博弈動力學研究綜述

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

關鍵詞：網絡結構；囚徒困境；合作行為

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

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

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

演化博弈論的特征與實際網絡較為符合，使得復雜網絡上的博弈演化研究得到越來約多學者的參與和研究，在這里主要綜述一下復雜網絡上的網絡結構是如何對博弈產生影響的。

1 復雜網絡中的經典網絡模型

當策略更新規(guī)則相同時，網絡結構不一樣，對博弈的影響也不一樣。在這里先介紹一下對演化博弈有影響的網絡：規(guī)則網絡、小世界網絡和無標度網絡。

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

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

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

2 典型的博弈模型

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

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

3 網絡演化博弈的策略更新規(guī)則

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

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

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

4 網絡結構對博弈模型的影響

當網絡的策略更新規(guī)則相同，網絡結構的不同會對網絡的博弈合作產生不同的影響。

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

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

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

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

（2）WS小世界網絡度存在異質性，使得它比度均勻分布的小世界網絡合作頻率更高。

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

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

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

5 復雜網絡博弈演化發(fā)展方向與展望

復雜網絡上的演化博弈研究是近幾年研究的熱門領域，目前研究的都是比較簡單的博弈演化，多數科學家已經開始朝更復雜與實際網絡更接近的方向去研究，復雜網絡上的博弈演化趨勢主要在以下幾個方面：

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

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

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

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

參考文獻：

[1]王文旭.復雜網絡的演化動力學及網絡上的動力學過程研究[D].合肥：中國科學技術大學，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.