復(fù)雜網(wǎng)絡(luò)上的演化博弈動(dòng)力學(xué)
——一個(gè)計(jì)算視角的綜述

譚少林，呂金虎

(1.湖南大學(xué)電氣與信息工程學(xué)院，長(zhǎng)沙 410082；2.中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院系統(tǒng)科學(xué)研究所，北京 100190)

0 引言

博弈論是研究多個(gè)自主性個(gè)體在利益相關(guān)情形下的決策行為的理論?，F(xiàn)實(shí)中下面這種情形常常會(huì)碰到：若干個(gè)稱為決策者或者玩家的個(gè)體，他們具備獨(dú)立決策的自主性，然而他們彼此之間的利益卻相互關(guān)聯(lián)或沖突。博弈論即是通過(guò)建立適當(dāng)?shù)臄?shù)學(xué)模型和工具，來(lái)分析、預(yù)測(cè)和干預(yù)自主個(gè)體在利益相關(guān)情形下決策行為的一門學(xué)科[1]。通常，在經(jīng)典博弈論中，玩家個(gè)體被假設(shè)具有完全理性和完全信息，即能夠依據(jù)對(duì)鄰居策略以及博弈的分析或預(yù)判，選擇最大化自身收益的策略[2]。

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

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

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

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

目前，從研究?jī)?nèi)容上看，復(fù)雜網(wǎng)絡(luò)上的演化博弈研究可以從兩方面出發(fā)：一方面以個(gè)體層面的視角，探討群體層面的策略演化機(jī)制，即通過(guò)對(duì)個(gè)體間的交互關(guān)系和策略更新規(guī)則進(jìn)行分析和建模，來(lái)分析集群決策的動(dòng)力學(xué)機(jī)制與演化行為[15]。另一方面以群體層面的需求的視角，來(lái)探討關(guān)于個(gè)體層面的策略更新方式的設(shè)計(jì)和干預(yù)。具體地說(shuō)，依據(jù)對(duì)群體整體策略所需要達(dá)成的目標(biāo)，來(lái)設(shè)計(jì)個(gè)體間的交互結(jié)構(gòu)或者個(gè)體的決策方式以及調(diào)整干預(yù)方法，使得最終由個(gè)體組成的群體行為能夠達(dá)成預(yù)先設(shè)定的目標(biāo)[16]。

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

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

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

本文主要是對(duì)目前復(fù)雜網(wǎng)絡(luò)上演化博弈動(dòng)力學(xué)的理論分析方面獲得的主要結(jié)果進(jìn)行一個(gè)綜述。主要內(nèi)容包括：給出復(fù)雜網(wǎng)絡(luò)上演化博弈動(dòng)力學(xué)基本模型的數(shù)學(xué)描述；分析網(wǎng)絡(luò)上演化博弈動(dòng)力學(xué)的計(jì)算復(fù)雜性；概述復(fù)雜網(wǎng)絡(luò)上演化博弈動(dòng)力學(xué)的若干主要解析結(jié)果等。鑒于目前對(duì)復(fù)雜網(wǎng)絡(luò)上演化博弈方面已有大量的仿真模擬研究，國(guó)內(nèi)已有一些學(xué)者對(duì)這些研究進(jìn)行了綜述，本文從計(jì)算的角度對(duì)復(fù)雜網(wǎng)絡(luò)上演化博弈動(dòng)力學(xué)的綜述將是對(duì)目前仿真研究的一個(gè)有效補(bǔ)充。

1 復(fù)雜網(wǎng)絡(luò)上演化博弈動(dòng)力學(xué)的數(shù)學(xué)描述

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

1.1 群體結(jié)構(gòu)

具有復(fù)雜交互結(jié)構(gòu)的群體常常可以通過(guò)一個(gè)網(wǎng)絡(luò)來(lái)表示。其中網(wǎng)絡(luò)中的節(jié)點(diǎn)和連邊分別代表玩家個(gè)體和個(gè)體之間的鄰居關(guān)系。此外，每條連邊可以賦予一個(gè)權(quán)重來(lái)描述個(gè)體之間的相互作用強(qiáng)度。一般地，一個(gè)網(wǎng)絡(luò)G=(V,E,W)被用來(lái)表示博弈群體，其中V=(v1,v2,…,vn)表示節(jié)點(diǎn)集、E?V×V為邊集，W=(wij)n×n表示個(gè)體間交互的權(quán)重矩陣。

一些常用于刻畫演化博弈中個(gè)體交互結(jié)構(gòu)的網(wǎng)絡(luò)包括完全圖、環(huán)狀、星狀圖、二分圖等對(duì)稱性較高的規(guī)則圖，也有Erdos-Renyi隨機(jī)圖[23]、Watt-Strogatz小世界網(wǎng)絡(luò)[24]、Barabasi-Albert無(wú)標(biāo)度網(wǎng)絡(luò)[25]、隨機(jī)幾何圖[26]等局部交互比較復(fù)雜，具有一定典型拓?fù)涮卣鞯碾S機(jī)圖。圖1展示這些圖的拓?fù)浣Y(jié)構(gòu)示意圖，其具體定義和生成算法可參考對(duì)應(yīng)的文獻(xiàn)。

圖1 常見(jiàn)網(wǎng)絡(luò)的典型拓?fù)浣Y(jié)構(gòu)示意圖[1]

1.2 節(jié)點(diǎn)狀態(tài)集合及其適應(yīng)度

網(wǎng)絡(luò)博弈是一類特殊的博弈形式。在網(wǎng)絡(luò)博弈中，玩家個(gè)體的博弈關(guān)系構(gòu)成了一個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，而每個(gè)個(gè)體的收益與不相鄰的個(gè)體行動(dòng)無(wú)關(guān)。而且在網(wǎng)絡(luò)上的演化博弈中，一般采用兩類基本的網(wǎng)絡(luò)博弈：對(duì)交互博弈和群組交互博弈。

群組交互網(wǎng)絡(luò)博弈是另一類常見(jiàn)的網(wǎng)絡(luò)博弈模型。相比于對(duì)交互網(wǎng)絡(luò)博弈，群組交互博弈中的每個(gè)個(gè)體與它所有相鄰個(gè)體形成一個(gè)局部多人博弈。也就是說(shuō)，個(gè)體不再與每個(gè)鄰居進(jìn)行單獨(dú)的兩人博弈，而是與它鄰居集合構(gòu)成一個(gè)整體進(jìn)行多人博弈[27]。圖2分別給出了網(wǎng)絡(luò)中的對(duì)交互和群組交互兩種博弈模型的示意圖。

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

在網(wǎng)絡(luò)上的演化博弈動(dòng)力學(xué)中，常常通過(guò)適當(dāng)?shù)挠成浞绞?，將個(gè)體的行動(dòng)集合表示為一個(gè)合適的狀態(tài)集合，而個(gè)體通過(guò)博弈所獲取的收益則被轉(zhuǎn)化為個(gè)體的適應(yīng)度[28]。一般地，個(gè)體適應(yīng)度與收益之間的關(guān)系由式(1)轉(zhuǎn)化

fitness=exp(w×payoff)

(1)

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

fitness=1+w×payoff

(2)

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

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

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

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

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

圖3 復(fù)雜網(wǎng)絡(luò)上的生滅過(guò)程以及死生過(guò)程示意圖Fig.3 Illustration of birth-death process and death-birth process on complex networks

1.4 演化過(guò)程的數(shù)學(xué)描述

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

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

圖4 網(wǎng)絡(luò)上兩策略博弈的演化過(guò)程[1]

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

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

(3)

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

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

(4)

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

2 復(fù)雜網(wǎng)絡(luò)上的隨機(jī)漂移過(guò)程

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

2.1 無(wú)向無(wú)權(quán)圖

在無(wú)向無(wú)權(quán)圖上的隨機(jī)漂移過(guò)程中，一個(gè)策略的固定概率完全有這個(gè)策略所在節(jié)點(diǎn)的度以及整個(gè)網(wǎng)絡(luò)的度分布決定。具體地，對(duì)于網(wǎng)絡(luò)上的生滅過(guò)程，一個(gè)策略入侵節(jié)點(diǎn)vi∈V后的固定概率為

(5)

而對(duì)于網(wǎng)絡(luò)上的死生過(guò)程，對(duì)應(yīng)的固定概率為

(6)

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

2.2 一類特殊的加權(quán)圖

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

對(duì)于這一類加權(quán)圖，在生滅過(guò)程作用下，一個(gè)策略入侵節(jié)點(diǎn)vi∈V后的固定概率為

(7)

而在死生過(guò)程作用下，對(duì)應(yīng)概率為

(8)

2.3 一般加權(quán)圖

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

對(duì)于生滅過(guò)程，這個(gè)隨機(jī)矩陣為MBD=(mij)n×n，其中

(9)

而對(duì)于死生過(guò)程，這個(gè)隨機(jī)矩陣為MDB=(mij)n×n，其中

(10)

因此，對(duì)于一般加權(quán)網(wǎng)絡(luò)上的隨機(jī)漂移過(guò)程，雖然無(wú)法直接給出其固定概率的表達(dá)式，但是可以通過(guò)求解對(duì)應(yīng)隨機(jī)矩陣的平穩(wěn)分布來(lái)求得其固定概率。注意到，求解隨機(jī)矩陣的平穩(wěn)分布的計(jì)算復(fù)雜度是線性時(shí)間的，因此與直接求解2n階的方程組相比，上述方法極大地簡(jiǎn)化了求解固定概率的復(fù)雜度。

2.4 時(shí)序圖

具體地，令Mt=(mij(t))n×n為一個(gè)動(dòng)態(tài)的隨機(jī)矩陣。對(duì)于時(shí)序圖上的生滅過(guò)程，這個(gè)矩陣中元素為

(11)

而對(duì)于死生過(guò)程，矩陣元素為

(12)

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

(13)

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

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

3 復(fù)雜網(wǎng)絡(luò)上的常數(shù)選擇過(guò)程

常數(shù)選擇過(guò)程是一類比隨機(jī)漂移過(guò)程更加一般化的演化過(guò)程。在隨機(jī)漂移過(guò)程中，初始策略B與入侵策略A的適應(yīng)度相同，沒(méi)有選擇性差異，演化過(guò)程決定于隨機(jī)性因素。而在常數(shù)選擇過(guò)程中，初始策略與入侵策略的適應(yīng)度都是固定不變的常數(shù)，但不一定相同。常數(shù)選擇過(guò)程一般用于刻畫效用值不同的策略在網(wǎng)絡(luò)群體中競(jìng)爭(zhēng)和擴(kuò)散過(guò)程[35]。這類過(guò)程也可以視為一類特殊的網(wǎng)絡(luò)博弈：在這類博弈中，個(gè)體的收益是僅依賴自身策略的常數(shù)，與其他鄰居個(gè)體的策略無(wú)關(guān)。

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

(14)

(15)

而對(duì)于死生過(guò)程，上述轉(zhuǎn)移概率為

(16)

對(duì)于復(fù)雜網(wǎng)絡(luò)上的常數(shù)選擇過(guò)程，目前尚沒(méi)有簡(jiǎn)單可行的方法來(lái)求解其固定概率。實(shí)際上，Broom等[36]證明，除了一些高度對(duì)稱性的網(wǎng)絡(luò)外，對(duì)于一般的網(wǎng)絡(luò)，n階的網(wǎng)絡(luò)上的兩策略演化過(guò)程可能形成2n階的策略構(gòu)型，因此，通過(guò)馬爾科夫鏈的方法來(lái)求解固定概率，需要求解2n階的方程組，其計(jì)算復(fù)雜度是指數(shù)時(shí)間的。

圖5 個(gè)體層面的策略更新與群體層面的策略選擇關(guān)系示意圖[1]

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

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

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

上述結(jié)果的好處在于，在無(wú)法得到復(fù)雜網(wǎng)絡(luò)上常數(shù)選擇過(guò)程中固定概率的解析解時(shí)，可以由常數(shù)選擇過(guò)程中的個(gè)體層面的相關(guān)性質(zhì)，推斷出其群體層面的性質(zhì)。例如，對(duì)于在復(fù)雜網(wǎng)絡(luò)上的死生過(guò)程中，容易證明其個(gè)體層面策略更新的轉(zhuǎn)移概率滿足1)-3)三個(gè)基本條件，而且是關(guān)于A策略個(gè)體適應(yīng)度r的單調(diào)遞增函數(shù)，以及關(guān)于集合C的單調(diào)遞增函數(shù)，并且集合C的次模(若r≥1)或超模函數(shù)(若0

4 復(fù)雜網(wǎng)絡(luò)上的演化博弈

復(fù)雜網(wǎng)絡(luò)上的演化博弈由復(fù)雜網(wǎng)絡(luò)、博弈以及更新動(dòng)力學(xué)三者組成。與常數(shù)選擇過(guò)程不同，在演化博弈過(guò)程中，個(gè)體之間會(huì)進(jìn)行博弈并產(chǎn)生收益，這一收益影響了該個(gè)體的適應(yīng)度，進(jìn)而影響其策略更新過(guò)程。因此，在演化博弈過(guò)程中，個(gè)體間的博弈與個(gè)體策略的演化緊密聯(lián)系在一起，并基于演化過(guò)程來(lái)研究分析相互連接的個(gè)體對(duì)于博弈策略的選擇。

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

值得注意的是，與博弈學(xué)習(xí)動(dòng)力學(xué)不同，通過(guò)上述演化動(dòng)力學(xué)獲得的偏好策略不一定是網(wǎng)絡(luò)博弈的納什均衡策略。演化博弈動(dòng)力學(xué)的核心魅力在于它基于自然演化的原理來(lái)分析群體的博弈行為。特別地，經(jīng)典博弈理論無(wú)法解釋生物群體和社會(huì)群體中的合作行為，形成著名的合作困境問(wèn)題。而演化博弈動(dòng)力學(xué)提供了一種新的方式來(lái)闡釋合作行為的涌現(xiàn)。這也是合作行為的涌現(xiàn)研究成為復(fù)雜網(wǎng)絡(luò)上演化博弈研究的主要內(nèi)容的原因。

顯然，在復(fù)雜網(wǎng)絡(luò)上的演化博弈過(guò)程中，個(gè)體間的交互結(jié)構(gòu)、博弈以及個(gè)體策略的更新動(dòng)力學(xué)都會(huì)新規(guī)則時(shí)，兩種典型網(wǎng)絡(luò)博弈模型下策略選擇的主要結(jié)果，相關(guān)詳細(xì)討論可參考對(duì)應(yīng)的文獻(xiàn)[38],[39]。

4.1 對(duì)交互網(wǎng)絡(luò)博弈

考慮下面的兩人兩策略對(duì)稱博弈

ABAabBcd

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

與復(fù)雜網(wǎng)絡(luò)上的常數(shù)選擇過(guò)程一樣，對(duì)于一般網(wǎng)絡(luò)上的演化博弈，很難解得其固定概率，從而無(wú)法直接比較固定概率ρA與ρB的大小。但在文獻(xiàn)[38]中，Tarnita等人發(fā)現(xiàn)，在弱選擇的情況下，存在一個(gè)非常簡(jiǎn)單的準(zhǔn)則來(lái)判定群體對(duì)于策略的偏好。具體地，在上述網(wǎng)絡(luò)演化博弈過(guò)程中，選擇更偏好策略A而不是B，當(dāng)且僅當(dāng)

σa+b>c+σd

(17)

其中，參數(shù)σ稱為結(jié)構(gòu)常數(shù)，僅取決于個(gè)體的狀態(tài)更新規(guī)則以及個(gè)體間的交互結(jié)構(gòu)，與博弈參數(shù)a,b,c,d無(wú)關(guān)。

根據(jù)上述判定準(zhǔn)則，現(xiàn)在只需計(jì)算一個(gè)網(wǎng)絡(luò)在給定更新規(guī)則下的結(jié)構(gòu)常數(shù)σ，就能判定這一網(wǎng)絡(luò)上演化過(guò)程對(duì)于策略的偏好。例如，對(duì)于用來(lái)說(shuō)明合作困境的囚徒博弈，其收益矩陣為

CDCb-c-cDb0

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

或等價(jià)地

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

是死生過(guò)程中網(wǎng)絡(luò)結(jié)構(gòu)系數(shù)的一個(gè)更好的近似，因此，比較囚徒博弈中的收益付出比與網(wǎng)絡(luò)平均鄰接度的大小關(guān)系，是判定合作策略是否被選擇所偏好的更好準(zhǔn)則。

表1 對(duì)交互博弈中一些簡(jiǎn)單圖的結(jié)構(gòu)系數(shù)[1]Tab.1 Structural Coefficients of some simple graphs with pairwise interactions

4.2 群組交互網(wǎng)絡(luò)博弈

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

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

或等價(jià)地

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

表2 群組交互博弈中一些簡(jiǎn)單圖的結(jié)構(gòu)系數(shù)[1]Tab.2 Structural coefficients of some simple graphs with group interactions

5 總結(jié)與展望

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

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

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

[1]呂金虎，譚少林. 復(fù)雜網(wǎng)絡(luò)上的博弈及其演化動(dòng)力學(xué)[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]汪小帆，李翔，陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2006.

[8]何大韌，劉宗華，汪秉宏. 復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)[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] 王龍，伏峰，王靖，等. 復(fù)雜網(wǎng)絡(luò)上的演化博弈[J]. 智能系統(tǒng)學(xué)報(bào), 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] 吳枝喜，榮智海，王文旭. 復(fù)雜網(wǎng)絡(luò)上的博弈[J]. 力學(xué)進(jìn)展，2008, 389(6): 794-804.

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

[14] 楊陽(yáng)，榮志海，李翔. 復(fù)雜網(wǎng)絡(luò)演化博弈理論研究綜述[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，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.