譚少林，呂金虎

(1.湖南大學電氣與信息工程學院，長沙 410082；2.中國科學院數學與系統科學研究院系統科學研究所，北京 100190)

0 引言

博弈論是研究多個自主性個體在利益相關情形下的決策行為的理論?，F實中下面這種情形常常會碰到：若干個稱為決策者或者玩家的個體，他們具備獨立決策的自主性，然而他們彼此之間的利益卻相互關聯或沖突。博弈論即是通過建立適當的數學模型和工具，來分析、預測和干預自主個體在利益相關情形下決策行為的一門學科[1]。通常，在經典博弈論中，玩家個體被假設具有完全理性和完全信息，即能夠依據對鄰居策略以及博弈的分析或預判，選擇最大化自身收益的策略[2]。

演化動力學則是用于刻畫群體演化過程的一個理論工具，它基于群體演化過程中的復制、選擇和變異等3個基本原則，來建立描述群體組成在給定適應度景觀下的演化數學模型[3]。最初，演化動力學用于描述不同適應度的表現型或行為在生物群體中的擴散過程。后來，鑒于演化動力學中隱含的自然選擇和隨機漂移機制的普適性，演化動力學也常常用于探索經濟、社會和工業(yè)系統中的各種不同的演化行為。

傳統博弈論與演化動力學理論的結合形成了演化博弈理論[4]。演化博弈以參與博弈的群體作為研究對象，通過分析群體中不同策略的個體組成在復制、選擇和突變的演化機制作用下的動態(tài)行為過程，來分析、解釋和預測個體在交互決策情境下的博弈行為。與經典博弈論不同，演化博弈論擯棄了關于個體的完全理性和完全信息假設，從動態(tài)的系統的視角探討個體決策到群體決策的形成機制，為研究群體決策的形成和演化提供了新的理論工具和方法論支持[5]。

長期以來，在演化博弈理論中，個體之間的交互通常被假定以均勻混合的方式進行的，即任意兩個個體之間都存在交互或者以同樣的概率發(fā)生交互。這種假設能夠極大地簡化描述群體演化過程的動力學方程，有助于后續(xù)的分析處理，但與實際中的個體間的交互模式不相符。事實上，在實際生物、社會、經濟和工業(yè)復雜系統中，個體之間的交互往往比均勻混合的形式更復雜，呈現出若干特定的拓撲特征，例如小世界特性、無標度特征、社團結構、層級特征等等[6-9]。為了刻畫生物、社會和工業(yè)系統中的錯綜復雜的連接結構，復雜網絡這一概念被抽象出來，它由節(jié)點和節(jié)點之間的連邊構成，節(jié)點代表系統的基礎組成單元，而連邊代表系統中各單元之間的交互關系。

復雜網絡上的演化博弈即是由復雜網絡和演化博弈的兩者結合而形成的新型交叉研究領域[10]。它以復雜網絡和演化博弈動力學分別刻畫個體間的交互關聯結構以及決策范式，通過網絡群體上策略的形成和演化來探討生物、社會等群體中的策略演化行為。復雜網絡上的演化博弈與傳統演化博弈的區(qū)別在于：前者采用了自下而上的科學范式，它通過對個體之間的交互方式和結構、以及個體的行為規(guī)則等進行建模，來探討由此衍生的群體行為的形成和演化機制[11]。復雜網絡上的演化博弈為理解和分析復雜交互環(huán)境下群體的決策行為提供了一個新的研究模式，對其展開深入的研究可以為理解集群行為的形成和演化模式，洞察文化變遷、社會規(guī)范、以及公共意見的形式和發(fā)展過程，提供新的幫助。同時其演化動力學中相關的原理對于分布式協同控制的設計也能提供有益參考。這些因素推動了國內外對于復雜網絡上演化博弈研究的熱潮[12-14]。

目前，從研究內容上看，復雜網絡上的演化博弈研究可以從兩方面出發(fā)：一方面以個體層面的視角，探討群體層面的策略演化機制，即通過對個體間的交互關系和策略更新規(guī)則進行分析和建模，來分析集群決策的動力學機制與演化行為[15]。另一方面以群體層面的需求的視角，來探討關于個體層面的策略更新方式的設計和干預。具體地說，依據對群體整體策略所需要達成的目標，來設計個體間的交互結構或者個體的決策方式以及調整干預方法，使得最終由個體組成的群體行為能夠達成預先設定的目標[16]。

而從研究形式上看，目前對于復雜網絡上演化博弈的研究可以分為模擬仿真研究、理論分析研究和實證研究3類。模擬仿真研究通過利用計算機程序，對復雜網絡上的演化博弈動力學進行仿真，來獲取對于網絡上演化博弈的理解。這種研究方式能夠適用于大規(guī)模結構復雜的網絡，同時對各種復雜的博弈或者更新規(guī)則都能適用，是研究復雜網絡上演化博弈的最常用的方式。國內外學者利用這種方式對復雜網絡上的演化博弈行為展開了大量的研究。各種不同類型的因素，如個體異質性、決策多樣性；個體的學習行為以及遷徙行為、收益的遺傳以及分配的不均勻性；策略信息的局限性以及網絡交互結構的動態(tài)特征等，對群體在演化博弈中決策行為的影響都得到了廣泛的探討。目前，已有多篇文章對這一研究方式及其取得的結果進行了綜述，感興趣的讀者可以參考文獻[17-20]。

對復雜網絡上演化博弈的實證研究，通常通過召集一些志愿參與實驗的個體，來參與所設計的博弈實驗，并根據參與博弈的個體在不同情境下的策略選擇，來獲取關于網絡演化博弈的理解。由于參與博弈的個體決策方式是不可控的，這種實證研究通常僅能獲取若干可觀可控因素對于網絡演化博弈的影響。例如，通過博弈實驗，Rand等[21]發(fā)現個體切斷和重建交互關系的能力有助于提高社交網絡中合作水平。在另一個博弈實驗中，他們發(fā)現，相比于懲罰背叛行為，獎勵合作行為更加有益于促進合作行為的涌現和保持[22]。

而對復雜網絡上演化博弈的理論分析研究則是利用數學工具，對網絡演化博弈的動力學展開分析，來得到關于復雜網絡上演化博弈動力學的一些基本性質。由于在復雜網絡上的演化博弈動力學中，每個個體的狀態(tài)通過網絡博弈以及網絡演化動力學耦合起來，這使得整個動力學所誘導的狀態(tài)空間的維度十分龐大且狀態(tài)之間的轉移十分復雜。因此，雖然對復雜網絡上的演化博弈動力學展開理論分析是深刻理解網絡演化博弈中交互、演化與決策之間關聯關系的必要，但卻由于其復雜性常常十分困難。不管怎樣，目前對于復雜網絡上演化博弈的理論研究雖然相對來說較為稀少，但一直在不斷推進。

本文主要是對目前復雜網絡上演化博弈動力學的理論分析方面獲得的主要結果進行一個綜述。主要內容包括：給出復雜網絡上演化博弈動力學基本模型的數學描述；分析網絡上演化博弈動力學的計算復雜性；概述復雜網絡上演化博弈動力學的若干主要解析結果等。鑒于目前對復雜網絡上演化博弈方面已有大量的仿真模擬研究，國內已有一些學者對這些研究進行了綜述，本文從計算的角度對復雜網絡上演化博弈動力學的綜述將是對目前仿真研究的一個有效補充。

1 復雜網絡上演化博弈動力學的數學描述

盡管復雜網絡上的演化博弈模型可以多種多樣，但其基本模型都由3個基本要素組成：1)一個給定的網絡；2)節(jié)點的狀態(tài)集合及其適應度；3)節(jié)點狀態(tài)的更新規(guī)則。接下來，我們分別介紹這些基本元素及其工作機理。

1.1 群體結構

具有復雜交互結構的群體常?？梢酝ㄟ^一個網絡來表示。其中網絡中的節(jié)點和連邊分別代表玩家個體和個體之間的鄰居關系。此外，每條連邊可以賦予一個權重來描述個體之間的相互作用強度。一般地，一個網絡G=(V,E,W)被用來表示博弈群體，其中V=(v1,v2,…,vn)表示節(jié)點集、E?V×V為邊集，W=(wij)n×n表示個體間交互的權重矩陣。

一些常用于刻畫演化博弈中個體交互結構的網絡包括完全圖、環(huán)狀、星狀圖、二分圖等對稱性較高的規(guī)則圖，也有Erdos-Renyi隨機圖[23]、Watt-Strogatz小世界網絡[24]、Barabasi-Albert無標度網絡[25]、隨機幾何圖[26]等局部交互比較復雜，具有一定典型拓撲特征的隨機圖。圖1展示這些圖的拓撲結構示意圖，其具體定義和生成算法可參考對應的文獻。

圖1 常見網絡的典型拓撲結構示意圖[1]

1.2 節(jié)點狀態(tài)集合及其適應度

網絡博弈是一類特殊的博弈形式。在網絡博弈中，玩家個體的博弈關系構成了一個網絡拓撲結構，而每個個體的收益與不相鄰的個體行動無關。而且在網絡上的演化博弈中，一般采用兩類基本的網絡博弈：對交互博弈和群組交互博弈。

群組交互網絡博弈是另一類常見的網絡博弈模型。相比于對交互網絡博弈，群組交互博弈中的每個個體與它所有相鄰個體形成一個局部多人博弈。也就是說，個體不再與每個鄰居進行單獨的兩人博弈，而是與它鄰居集合構成一個整體進行多人博弈[27]。圖2分別給出了網絡中的對交互和群組交互兩種博弈模型的示意圖。

圖2 博弈交互示意圖[28]Fig.2 Illustration of game

在網絡上的演化博弈動力學中，常常通過適當的映射方式，將個體的行動集合表示為一個合適的狀態(tài)集合，而個體通過博弈所獲取的收益則被轉化為個體的適應度[28]。一般地，個體適應度與收益之間的關系由式(1)轉化

fitness=exp(w×payoff)

(1)

這里，fitness和payoff分別指代個體的適應度和收益，參數0w稱為選擇強度，用于調節(jié)個體博弈收益對其適應度的影響。當w=0時，個體的適應度與其收益無關，在這種情形下，所有個體的適應度相等，其狀態(tài)演化過程與博弈無關，完全由更新規(guī)則中的隨機性決定，因此，稱這種情形下的演化動力學為隨機漂移。當w→0時，個體通過網絡博弈獲取的收益僅占其適應度的極小部分，此時，所有個體具有幾乎相同的適應度。這種情形稱為弱選擇。此時，其適應度與收益之間的關系也可簡化為：

fitness=1+w×payoff

(2)

在上述收益與適應度之間的關系中，隱含假設了每個狀態(tài)(策略)給予個體的基準適應度是相同的。即當w=0時，不管個體采取何種狀態(tài)，其適應度都相同。一種更一般的假定是不同狀態(tài)給予個體的基準適應度不相同，即當w=0時，個體采取不同的狀態(tài)，其適應度各不相同。此時，個體的適應度僅取決于自身的狀態(tài)，與其他個體的狀態(tài)無關，這種情形被稱為常數選擇。

1.3 狀態(tài)更新規(guī)則

狀態(tài)更新規(guī)則描述了每個個體根據其周圍鄰居的狀態(tài)和適應度來更新自己的狀態(tài)的過程，是刻畫復雜網絡上演化博弈動力學的關鍵要素。仿照自然或社會個體實際決策過程，各種不同類型的更新規(guī)則被提出來，如生滅過程、死生過程、模仿過程及其不同情形下的變化形式等。生滅過程和死生過程是生物數學中描述種群演化的兩類最基本的動力學模型，大量新的狀態(tài)更新規(guī)則也是在這兩類更新規(guī)則的基礎上進行調整變化的，因此，本文主要考察這兩類更新規(guī)則下的演化博弈過程，其相關分析方法和結果也可以推廣到其他類似演化過程中。

在經典生滅過程中，每一步，以正比于個體適應度的概率，一個個體從群體中被選擇出來；隨后，這個個體產生一個復制體，并隨機替代群體中剩余個體中的某一個，從而導致群體組成的變化。當考慮具有交互結構的群體時，這一經典生滅過程被推廣到網絡群體中[29]。此時同樣以正比于個體適應度的概率，個體從網絡群體中被選擇出來產生復制體，但此時復制體隨機替代其某一個鄰居，如圖3a所示。顯然，在網絡上的死生過程中，狀態(tài)的傳播擴散是通過個體間的交互進行的。特別地，對于加權網絡，選擇被替代鄰居節(jié)點的概率將與其連邊的權重成正比。例如，如果節(jié)點vi∈V被選擇出來產生復制，那么選擇鄰居節(jié)點vj∈Ni進行替代的概率正比兩點連邊的權重wij。

同樣地，在經典死生過程中，每一步，一個個體被隨機地從群體中淘汰，然后以正比于個體適應度的概率，從群體中剩余的個體中選擇出一個個體，這個個體產生一個復制體并替代被淘汰個體的位置。而在網絡上的死生過程中[30]，每一步，一個個體被隨機地從群體中淘汰，然后以正比于個體適應度的概率，從這個淘汰個體的鄰居中選擇出一個個體，這個個體產生一個復制體并替代被淘汰個體的位置，如圖3b所示。而當網絡是加權網絡時，如果節(jié)點vi∈V為淘汰節(jié)點，那么選擇其鄰居節(jié)點vj∈Ni產生復制的概率大小正比于fjwji，這里，fj指節(jié)點vj的適應度，而wji是連邊(vj,vi)∈E的權重值。

圖3 復雜網絡上的生滅過程以及死生過程示意圖Fig.3 Illustration of birth-death process and death-birth process on complex networks

1.4 演化過程的數學描述

一個網絡上的演化動力學過程完全可以由個體間的交互關系網絡、個體的狀態(tài)集及其適應度景觀、以及個體狀態(tài)的更新規(guī)則等3個元素確定。如圖4所示，給定上述3個要素確定了一個典型的網絡的演化博弈過程。在這個演化博弈過程中，初始時刻，所有節(jié)點都為B策略個體。某一時刻，由于個體的自由探索或者新策略的入侵，一個A策略個體占據了網絡中的某個節(jié)點，從而導致兩種策略的交互與競爭過程。在狀態(tài)更新規(guī)則的不斷作用下，網絡上的策略分布從一個狀態(tài)轉移到另一狀態(tài)，形成群體博弈策略的演化過程。

令M0={vi∈V|si(0)=1}為初始時刻網絡中的A策略節(jié)點集合，令ρM0=P(limt→Mt=V)為網絡中所有節(jié)點的策略在演化動力學的作用下最終收斂于A策略的概率。這一被稱為固定概率的變量，是反映演化博弈動力學行為的關鍵值。簡便起見，通常令ρi=ρ{vi}，表示單個A策略個體在入侵節(jié)點vi∈V后，最終占據了網絡中全部節(jié)點的概率。

圖4 網絡上兩策略博弈的演化過程[1]

求解網絡上演化博弈動力學中的固定概率是一個非常困難的問題。一般地，在具有n個節(jié)點的網絡上兩策略演化博弈過程中，由于每個節(jié)點具有兩個狀態(tài)可以選擇，那么整個網絡可能的狀態(tài)數目為2n。因此利用對應馬爾科夫鏈的吸收概率的計算方法，需要求解一個2n階次的方程組，其一般形式如下

ρX=∑Y∈2nP(Y|X)ρY

(3)

這里，X∈2n為網絡狀態(tài)，P(Y|X)指網絡狀態(tài)X到狀態(tài)Y的轉移概率。

值得注意的是，在生滅過程和死生過程中，每一步最多只有一個節(jié)點的狀態(tài)可能發(fā)生改變。因此，對應馬爾科夫鏈的轉移概率P(Y|X)不等于0，當且僅當1)Y=X，即網絡群體的狀態(tài)未發(fā)生改變；2)存在某一vi∈V且vi?X，使得Y=X∪{vi}，即網絡中節(jié)點vi從B策略變?yōu)锳策略；以及3)存在某一vi∈V且vi∈X，使得Y=X-{vi}，即網絡中節(jié)點vi從A策略變?yōu)锽策略。在這種情形下，上述方程組可以簡化為

(4)

其邊界條件為：ρ?=0以及ρV=1。

2 復雜網絡上的隨機漂移過程

復雜網絡上的隨機漂移過程是群體演化中一類特殊而基本的演化過程。在隨機漂移過程中，所有個體的適應度完全相等，此時策略在網絡上的競爭擴散過程完全與策略之間的博弈無關，而是由狀態(tài)更新過程本身的隨機性決定。隨機漂移是促使群體行為演化的一種基本作用力，也為一般的演化博弈動力學過程提供了一個對比參照標準[31]。特別地，雖然對于一般演化博弈動力學過程，求解其固定概率是一件計算復雜度非常高的難題，然而對于網絡上的隨機漂移過程，其固定概率可以通過解析的方式得到，下面簡述關于復雜網絡上隨機漂移過程的主要結果，其詳細討論詳見文獻[32-34]。

2.1 無向無權圖

在無向無權圖上的隨機漂移過程中，一個策略的固定概率完全有這個策略所在節(jié)點的度以及整個網絡的度分布決定。具體地，對于網絡上的生滅過程，一個策略入侵節(jié)點vi∈V后的固定概率為

(5)

而對于網絡上的死生過程，對應的固定概率為

(6)

這里，di是指節(jié)點vi∈V的度。由式(5)和(6)可知，在生滅過程中，鄰居數目較少的節(jié)點，其策略擴散至整個網絡的概率更大；相反地，在死生過程中，鄰居數目較多的節(jié)點，其策略擴散至整個網絡的概率更大。

2.2 一類特殊的加權圖

上述解析結果可以推廣到一類特殊的加權圖中。令c=(c1,c2,…cn)和z=(z1,z2,…zn)為兩列正向量?？紤]一類加權網絡，對所有vi,vj∈V，其權重為wij=ciaijzj，這里假設aij=aij。顯然，如果c和z是單位向量，那么由上述方法生成的加權網絡即為無向無權圖。

對于這一類加權圖，在生滅過程作用下，一個策略入侵節(jié)點vi∈V后的固定概率為

(7)

而在死生過程作用下，對應概率為

(8)

2.3 一般加權圖

對于一般加權圖上的演化過程，求解其固定概率的方法稍微復雜一些。譚少林等[33]提出來一個一般性的計算方法來求解不同更新動力學作用下的固定概率。具體地，考慮一個強連通的圖G=(V,E,W)，其中W=(wij)n×n為權重矩陣。他們證明了，在網絡上的隨機漂移過程作用下，一個策略入侵節(jié)點vi∈V后的固定概率對應于某一隨機矩陣平穩(wěn)分布的第i個元素，即ρi=π(i)，這里π為某一隨機矩陣的平穩(wěn)分布。

對于生滅過程，這個隨機矩陣為MBD=(mij)n×n，其中

(9)

而對于死生過程，這個隨機矩陣為MDB=(mij)n×n，其中

(10)

因此，對于一般加權網絡上的隨機漂移過程，雖然無法直接給出其固定概率的表達式，但是可以通過求解對應隨機矩陣的平穩(wěn)分布來求得其固定概率。注意到，求解隨機矩陣的平穩(wěn)分布的計算復雜度是線性時間的，因此與直接求解2n階的方程組相比，上述方法極大地簡化了求解固定概率的復雜度。

2.4 時序圖

具體地，令Mt=(mij(t))n×n為一個動態(tài)的隨機矩陣。對于時序圖上的生滅過程，這個矩陣中元素為

(11)

而對于死生過程，矩陣元素為

(12)

其中，aij(t)以及di(t)是t時刻個體交互網絡Git中節(jié)點vi與vj的鄰接關系以及節(jié)點vi的節(jié)點度。那么在網絡上的隨機漂移過程作用下，一個策略入侵節(jié)點vi∈V后的固定概率對應于某一平穩(wěn)分布的第i個元素，即ρi=π(i)，這里平穩(wěn)分布π由式(13)可得。

(13)

由上述計算方法可知，對于動態(tài)時序網絡上的隨機漂移過程，在計算固定概率的過程中，雖然增加了矩陣連乘的部分，但當動態(tài)時序網絡存在一定的周期性時，其固定概率仍然能夠在線性時間內由上述計算方法得到。

上面給出了不同類型網絡上隨機漂移作用下單個策略入侵某一節(jié)點后，最后占據整個網絡的概率的計算方法。值得注意的是，在隨機漂移這一特殊情形下，某個策略同時入侵多個節(jié)點后，其最后占據整個網絡的固定概率等于這一策略入侵各單個節(jié)點的固定概率之和。因此，通過上述方法，可以計算各種情形下兩策略隨機漂移過程中的固定概率。

3 復雜網絡上的常數選擇過程

常數選擇過程是一類比隨機漂移過程更加一般化的演化過程。在隨機漂移過程中，初始策略B與入侵策略A的適應度相同，沒有選擇性差異，演化過程決定于隨機性因素。而在常數選擇過程中，初始策略與入侵策略的適應度都是固定不變的常數，但不一定相同。常數選擇過程一般用于刻畫效用值不同的策略在網絡群體中競爭和擴散過程[35]。這類過程也可以視為一類特殊的網絡博弈：在這類博弈中，個體的收益是僅依賴自身策略的常數，與其他鄰居個體的策略無關。

不失一般性，在常數選擇過程中，一般令初始策略B的適應度為單位1，而令入侵策略A的適應度為r。這里，r為一個大于0的常數，用于刻畫策略A相對于策略B的選擇性差異。當r=1時，這一常數選擇過程即為隨機漂移過程；當01時，稱A策略為優(yōu)勢策略。

(14)

(15)

而對于死生過程，上述轉移概率為

(16)

對于復雜網絡上的常數選擇過程，目前尚沒有簡單可行的方法來求解其固定概率。實際上，Broom等[36]證明，除了一些高度對稱性的網絡外，對于一般的網絡，n階的網絡上的兩策略演化過程可能形成2n階的策略構型，因此，通過馬爾科夫鏈的方法來求解固定概率，需要求解2n階的方程組，其計算復雜度是指數時間的。

圖5 個體層面的策略更新與群體層面的策略選擇關系示意圖[1]

雖然無法獲得復雜網絡上常數選擇過程中固定概率的解析形式，但是目前仍然有一些文獻得到了其固定概率的一些基本性質，用以闡明網絡上常數選擇過程的一些基本特性。令ρ(M0,r)表示A策略的固定概率，其中M0是初始時刻網絡中A策略節(jié)點集合。如圖5所示，每個個體vi∈V對于策略的選擇由轉移概率p(Mt,r,vi)和q(Mt,r,vi)來刻畫，而整個網絡群體對于策略的選擇則由固定概率ρ(M0,r)刻畫。譚少林等人在文獻[37]中給出了個體層面的策略更新與群體層面的策略選擇之間的關聯關系。下面綜述其主要結果，詳細證明與討論可參考文獻[37]。

其次，如果對所有節(jié)點vi∈V和r>0，轉移概率p(C,r,vi)是關于集合C的單調遞增函數；并且對所有??C?V和vi∈V，轉移概率p(C,r,vi)是關于A策略個體適應度r的單調遞增函數，那么A策略的固定概率ρ(M0,r)也是關于適應度r的單調遞增函數。這一性質說明：在復雜網絡上的常數選擇過程中，如果每個個體在進行策略選擇時傾向于選擇適應度更高的策略，那么整個網絡最終傾向于選擇適應度更高的策略。簡言之，如果個體具有擇優(yōu)行為，那么由個體組成的群體也具有擇優(yōu)行為。

最后，如果對所有節(jié)點vi∈V，轉移概率p(C,r,vi)是關于集合C的單調遞增函數，并且對所有節(jié)點vi∈V，轉移概率p(C,r,vi)是關于集合C的次?；虺：瘮?，那么A策略的固定概率ρ(M0,r)也是關于集合C的次?；虺：瘮?。這一性質刻畫了常數選擇過程中，初始時刻A策略節(jié)點集合中新增一個節(jié)點對于其固定概率的邊際效應。當A策略的固定概率是關于其初始A策略集合的次模(超模)函數時，那么在初始時刻給A策略集合新增一個A策略節(jié)點，對其固定概率的邊際效應會隨著其初始A策略集合的增大而減小(增大)。

上述結果的好處在于，在無法得到復雜網絡上常數選擇過程中固定概率的解析解時，可以由常數選擇過程中的個體層面的相關性質，推斷出其群體層面的性質。例如，對于在復雜網絡上的死生過程中，容易證明其個體層面策略更新的轉移概率滿足1)-3)三個基本條件，而且是關于A策略個體適應度r的單調遞增函數，以及關于集合C的單調遞增函數，并且集合C的次模(若r≥1)或超模函數(若0

4 復雜網絡上的演化博弈

復雜網絡上的演化博弈由復雜網絡、博弈以及更新動力學三者組成。與常數選擇過程不同，在演化博弈過程中，個體之間會進行博弈并產生收益，這一收益影響了該個體的適應度，進而影響其策略更新過程。因此，在演化博弈過程中，個體間的博弈與個體策略的演化緊密聯系在一起，并基于演化過程來研究分析相互連接的個體對于博弈策略的選擇。

策略選擇是復雜網絡上演化博弈中的核心問題。當不考慮個體策略復制過程中的突變概率時，網絡上的演化博弈過程對應于吸收型馬爾科夫鏈。此時，為了比較網絡群體對于某兩個策略的偏好，一般考慮令一種策略隨機地入侵另一種策略后的演化情形。具體地，令A、B分別表示兩種策略。令ρA表示單個A策略從某個隨機的節(jié)點入侵到全為B策略節(jié)點的網絡中，最終占據整個網絡的固定概率。同樣，令ρB表示單個B策略從某個隨機的節(jié)點入侵到一個全為A策略節(jié)點的網絡中，最終占據整個網絡的固定概率。假定網絡中的節(jié)點數目為n。那么當ρA>1/n時，則稱選擇偏好策略A。這里，1/n是隨機漂移過程中一個隨機入侵的A策略的固定概率。而如果ρA>ρB，則稱與策略B相比，選擇更偏好策略A。

值得注意的是，與博弈學習動力學不同，通過上述演化動力學獲得的偏好策略不一定是網絡博弈的納什均衡策略。演化博弈動力學的核心魅力在于它基于自然演化的原理來分析群體的博弈行為。特別地，經典博弈理論無法解釋生物群體和社會群體中的合作行為，形成著名的合作困境問題。而演化博弈動力學提供了一種新的方式來闡釋合作行為的涌現。這也是合作行為的涌現研究成為復雜網絡上演化博弈研究的主要內容的原因。

顯然，在復雜網絡上的演化博弈過程中，個體間的交互結構、博弈以及個體策略的更新動力學都會新規(guī)則時，兩種典型網絡博弈模型下策略選擇的主要結果，相關詳細討論可參考對應的文獻[38],[39]。

4.1 對交互網絡博弈

考慮下面的兩人兩策略對稱博弈

ABAabBcd

其中a,b,c,d分別為策略對(A,A),(A,B),(B,A),(B,B)中第一個個體所能獲得的收益。在對交互網絡博弈中，每個個體分別與它每個鄰居分別進行上述兩兩博弈，所獲得的收益和稱為這個個體的總收益。在更新動力學中，每個個體的收益通過式(1)轉化為其適應度。如前文所述，w→0的情形稱為弱選擇。

與復雜網絡上的常數選擇過程一樣，對于一般網絡上的演化博弈，很難解得其固定概率，從而無法直接比較固定概率ρA與ρB的大小。但在文獻[38]中，Tarnita等人發(fā)現，在弱選擇的情況下，存在一個非常簡單的準則來判定群體對于策略的偏好。具體地，在上述網絡演化博弈過程中，選擇更偏好策略A而不是B，當且僅當

σa+b>c+σd

(17)

其中，參數σ稱為結構常數，僅取決于個體的狀態(tài)更新規(guī)則以及個體間的交互結構，與博弈參數a,b,c,d無關。

根據上述判定準則，現在只需計算一個網絡在給定更新規(guī)則下的結構常數σ，就能判定這一網絡上演化過程對于策略的偏好。例如，對于用來說明合作困境的囚徒博弈，其收益矩陣為

CDCb-c-cDb0

這里，C和D分別代表合作與背叛策略。在這個博弈中，個體采取合作策略需要付出c的代價，但能為對方產生b的收益；而如果個體采取背叛策略，它既不用付出代價也不會帶來收益。顯然，在上述博弈中，個體的最優(yōu)選擇是背叛策略；而對于整體來說，合作才是最佳策略，這形成了著名的囚徒博弈。在復雜網絡上的演化博弈中，在弱選擇的情況下，根據上述判定準則，合作策略優(yōu)于背叛策略的充要條件為

或等價地

將這一系數應用于囚徒博弈中，可得合作策略優(yōu)于背叛策略的條件為b/c>k，即囚徒博弈中的收益付出比大于網絡的平均度。在文獻[40]中，konno發(fā)現

是死生過程中網絡結構系數的一個更好的近似，因此，比較囚徒博弈中的收益付出比與網絡平均鄰接度的大小關系，是判定合作策略是否被選擇所偏好的更好準則。

表1 對交互博弈中一些簡單圖的結構系數[1]Tab.1 Structural Coefficients of some simple graphs with pairwise interactions

4.2 群組交互網絡博弈

群組交互網絡博弈中，以每個節(jié)點為中心，個體及其所有的鄰居組成一個群組進行多人博弈。考慮下面策略為A和B的兩策略群體博弈。假設一個群組中有i個A策略個體和j個B策略個體，那么A策略個體和B策略個體獲得的收益分別為(ia+jb)/(i+j)和(ic+jd)/(i+j)。對于這種群組交互網絡博弈，在弱選擇的情況下，式(17)的策略選擇條件同樣適用，只不過其中的結構系數σ與對交互網絡中的結構系數不同。

顯然，當a=r-1,b=-1,c=r,d=0，上述群體博弈即為著名的公共物品博弈。這個博弈可以理解如下：每個個體可以選擇是否往公共資金中投入單位資金(合作策略)或者不如此(背叛策略)。這筆公共資金乘以系數r>1后，平均分給所有個體。公共物品博弈也是研究群體中合作行為涌現的一類重要博弈。顯然，在公共物品博弈中，理性個體的最優(yōu)選擇是背叛策略。而在復雜網絡上的演化博弈中，在弱選擇的情況下，根據上述判定準則，合作策略優(yōu)于背叛策略的充要條件為

或等價地

表2給出了生滅過程和死生過程作用下，完全圖、環(huán)狀圖、以及星狀圖的結構系數[41]。顯然，當個體間的交互網絡為完全圖時，在生滅過程和死生過程下，完全圖的結構系數都是σ=1，此時合作行為不被偏好。而對于環(huán)狀圖和星狀圖，只要當公共物品的收益系數r大于一定的值時，合作行為能被演化過程所偏好。

表2 群組交互博弈中一些簡單圖的結構系數[1]Tab.2 Structural coefficients of some simple graphs with group interactions

5 總結與展望

復雜網絡上的演化博弈是研究具有復雜交互結構的群體決策行為，特別是合作行為涌現和演化的重要工具。其研究內容可以從多個方面展開，包括個體間交互結構對于群體決策行為的影響；個體策略的更新規(guī)則與群體整體策略演化之間的關系；以及個體間的博弈模型與群體最終策略的偏好之間的關系等。對復雜網絡上的演化博弈展開深入的研究對于理解生物和社會群體中集群行為的涌現過程，如公共觀點的形成、社會創(chuàng)新的傳播等具有重要的意義[42]。

本文對迄今為止復雜網絡上演化博弈動力學理論分析方面獲得的主要結果進行一個系統的綜述。給出了復雜網絡上演化博弈動力學基本模型的數學描述；分析了網絡上演化博弈動力學的計算復雜性；概述復雜網絡上演化博弈動力學的若干主要解析結果，包括復雜網絡上隨機漂移過程中固定概率的計算、復雜網絡上常數選擇中局部狀態(tài)更新與全局狀態(tài)選擇之間的關聯性質、以及復雜網絡上演化博弈過程中的策略選擇等。鑒于目前對復雜網絡上演化博弈方面已有大量的仿真模擬研究，這些理論分析方面的結果對于深入理解復雜網絡上演化博弈的動力學機制與原理將有所助益。

值得注意的是，為了達到主線簡明清晰的目的，本文綜述的結果僅針對兩種典型的更新過程：生滅過程和死生過程、以及兩策略博弈和不具有突變率的演化過程。從這些結果發(fā)散開去的更多分析內容可參考相關文獻。此外，上文已經提到，對于復雜網絡上演化博弈動力學展開理論分析十分困難，很多問題甚至不可能求解。特別是隨著復雜網絡上的演化博弈研究的深入開展，越來越多更加復雜的網絡演化博弈模型被提出來，如共演化博弈，其動力學行為更加復雜。如不進行系統的實驗設計，利用仿真模擬的方法對復雜網絡上的演化博弈模型展開研究多數僅能獲得某一角度甚至片面的結果。理論分析則是獲得對網絡博弈演化過程深入理解的必要工具。因此，利用新的數學工具，對復雜網絡上的演化動力學展開深入的分析討論，將是研究復雜網絡上演化博弈過程的一個重要課題。

[1]呂金虎，譚少林. 復雜網絡上的博弈及其演化動力學[M]. 北京: 高等教育出版社, 2018.

[2]Szabo G, Fath G. Evolutionary games on graphs [J]. Phys Rep, 2007, 446: 97-216.

[3]Nowak M. A. Evolutionary Dynamics: Exploring the Equation of Life [M]. Cambridge: Harvard University Press, 2006.

[4]Smith J. M. Evolution and the Theory of Games [M]. Cambridge: Cambridge University Press, 1982.

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

[6]Newman M E J, Barabási A L, Watts D J. The Structure and Dynamics of Networks [M]. Princeton: Princeton University Press, 2006.

[7]汪小帆，李翔，陳關榮. 復雜網絡理論及其應用[M]. 北京: 清華大學出版社, 2006.

[8]何大韌，劉宗華，汪秉宏. 復雜系統與復雜網絡[M]. 北京: 高等教育出版社, 2009.

[9]Newman M E J. Networks: An Introduction [M]. New York: Oxford University Press, 2010.

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

[11] Tan S, Lü J, Chen G, et al. When structure meets function in evolutionary dynamics on complex networks [J]. IEEE Circ Syst Mag, 2014, 14(4): 36-50.

[12] 王龍，伏峰，王靖，等. 復雜網絡上的演化博弈[J]. 智能系統學報, 2007, 2(2): 1-10.

Wang Long, Fu Feng, Wang Jing, et al. Evolutionary games on complex networks [J]. CAAI Transactions on Intelligent Systems, 2007, 2(2): 1-10.

[13] 吳枝喜，榮智海，王文旭. 復雜網絡上的博弈[J]. 力學進展，2008, 389(6): 794-804.

Wu Zhixi, RongZhihai, Wang Wenxu. Games on complex networks [J]. Advances In Mechanics, 2008, 389(6): 794-804.

[14] 楊陽，榮志海，李翔. 復雜網絡演化博弈理論研究綜述[J]. 復雜系統與復雜性科學，2008, 5(4)：47-55.

Yang Yang, RongZhihai, Li Xiang. A research survey of evolutionary game theory on complex networks[J]. Complex Systems and Complex Sciences, 2008, 5(4): 47-55.

[15] Antal T, Traulsen A, Ohtsuki H, et al. Mutation-selection equilibrium in games with multiple strategies [J]. J Theor Biol, 2009, 258(4): 614-622.

[16] Traulsen A, Nowak M A. Evolution of cooperation by multilevel selection [J]. Proc Natl Acad Sci USA, 2006, 103(29): 10952-10955.

[17] Du J, Wu B, Altrock P M, et al. Aspiration dynamics of multi-player games in finite populations [J]. J R Soc Interface, 2014, 11: 20140077.

[18] Pacheco J, Traulsen A, Nowak M A. Coevolution of strategy and structure in complex networks with dynamical linking [J]. Phys Rev Lett, 2006, 97: 258103.

[19] Perc M, Szolnoki A. Coevolutionary games-a mini review [J]. Biosystems, 2010, 99(2):109-125.

[20] Perc M, Gomez-Gardenes J, Szolnoki A, et al. Evolutionary dynamics of group interactions on structured populations: a review [J]. J Royal Soc Interface, 2013, 10(80): 20120997.

[21] Rand D G, Arbesman S, Christakis N A. Dynamic social networks promote cooperation in experiments with humans [J]. Proc Nat Acad Sci, 2011, 108: 19193-19198.

[22] Rand D G, Dreber A, Ellingsen T, et al. Positive interactions promote public cooperation [J]. Science, 2009, 325: 1272-1275.

[23] Erdos P, Renyi A. On random graphs I [J]. Publ Math Debrecen, 1959, 6:290-297.

[24] Watts D J, Strogatz S H. Collective dynamics of small-world networks [J]. Nature, 1998, 393: 440-442.

[25] Barabasi A L, Albert R. Emergence of scaling in random networks [J]. Science, 1999, 286: 509-512.

[26] Penrose M. Random Geometric Graphs [M]. New York: Oxford University Press, 2003

[27] Tan S, Lü J. Analysis and control of networked game dynamics via a microscopic deterministic approach [J]. IEEE Trans Autom Contr, 2016, 61(12): 4118-4124.

[28] Tan S, Lü J, Yu X, et al. Evolution and maintenance of cooperation via inheritance of neighborhood relationship [J]. Chin Sci Bull, 2013, 58(28-29): 3491-3498.

[29] Lieberman E, Hauert C, Nowak M A. Evolutionary dynamics on graphs [J]. Nature, 2005, 433(7023): 312-316.

[30] Ohtsuki H, Nowak M A. Evolutionary games on cycles [J]. Proc R Soc B, 2006, 273(1598): 2249-2256.

[31] Mesoudi A, Lycett S J. Random copying, frequecy-dependent copying and culture change [J]. Evol Hum Behav, 2009, 30(1): 41-48.

[32] Broom M, Hadjichrysanthou C, Rychtár J, et al. Addendum: two results on evolutionary processes on general non-directed graphs [J]. Proc R Soc A, 2010, 466(2121): 2795-2798.

[33] Tan S, Lü J, Hill D. Towards a theoretical framework for analysis and intervention of random drift on general networks [J]. IEEE Trans Automat Contr, 2015, 60(2): 576-582.

[34] Tan S, Wang Y, Chen Y. A unified tractable approach for random drifts on dynamical networks [J]. IEEE Trans Circ Syst II, 2016, 63(3): 299-303.

[35] Tan S, Lü J. Characterizing the effect of population heterogeneity on evolutionary dynamics on complex networks [J]. Sci Rep, 2014, 4: 05034.

[36] Broom M, Rychtár J. An analysis of the fixation probability of a mutant on special classes of non-directed graphs [J]. Proc R Soc A, 2008, 464(2098): 2609-2627.

[37] Tan S, Lü J, Lin Z. Emerging behavioral consensus of evolutionary dynamics on complex networks [J]. SIAM Journal Contr Optim, 2016, 54(6): 3258-3272.

[38] Tarnita C E, Ohtsuki H, Antal T, et al. Strategy selection in structured populations [J]. J Theor Biol, 2009, 259(3): 570-581.

[39] Ohtsuki H, Hauert C, Lieberman E, et al. A simple rule for the evolution of cooperation on graphs and social networks [J]. Nature, 2006, 441(7092): 502-505.

[40] Konno T. A condition for cooperation in a game on complex networks [J]. J Theor Biol, 2011, 269(1): 224-233.

[41] Tan S, Feng S, Wang P, et al. Strategy selection in evolutionary game dynamics on group interaction networks [J]. Bulletin of Mathematical Biology, 2014, 76(11): 2785-2805.

[42] Tan S, Wang Y, Chen Y, et al. Evolutionary dynamics of collective behavior selection and drift: flocking, collapse, and oscillation [J]. IEEE Trans Cy, 2017, 47(7): 1694-1705.