基于復雜網絡與演化博弈的群體行為策略分析

摘 要：在對演化博弈理論和復雜網絡研究的基礎上，根據現實社會網絡的特性，選取囚徒博弈作為范例，對復雜網絡基礎上的演化博弈進行研究。分析了網絡中個體間協作關系的演化過程、網絡收益和個體收益的分布狀況，以期為網絡結構和群體行為間互動關系作出定性分析，并在一定程度上對復雜網絡的形成原因進行解釋。

關鍵詞：復雜網絡； 演化博弈； 合作； 群體行為

中圖分類號：TP301.5； TP393 文獻標志碼：A 文章編號：1001-3695(2008)08-2352-03

Collective behaviors and strategies analysis

based on complex network and evolutionary game

TIAN Wei， DENG Gui-shi， WU Pei-jian

(Institute of System Engineering， Dalian University of Technology， Dalian Liaoning 116023， China)

Abstract:Combined with the properties of real social network， this paper made an analysis in evolutionary game on complex network using prisoner dilemma based on the research of complex network and evolutionary game. It studied the evolve process of collaboration relation between individual， network payoff and the distribution of individual’s payoff in order to present qualitative analysis on the relation between network structure and collective behaviors. The paper also presented some qualitative explanation on the formation of the complex network.

Key words：complex network; evolutionary game; cooperation; collective behaviors

博弈論主要研究決策主體的行為發生直接相互作用時所進行的決策以及這種決策的均衡問題^[1]。作為一種數學分析方法，博弈論已經被廣泛地運用在經濟、政治、軍事、社會等領域。在傳統的博弈理論中，一般假定具有完全理性的個體在完全信息條件下進行博弈，參與博弈的各方知道博弈的所有細節，包括彼此對博弈結果的偏好。但是在現實社會中，這種理想狀態是基本不可獲得的。為了加強博弈論的現實應用基礎，J. Maynard-Smith^[2，3]、R.Selten^[4，5]等人結合博弈理論和動態演化理論過程提出了演化博弈論，用于研究生物在不同環境中的行為與進化過程，并隨后將演化式的博弈模型過渡到了經濟和社會行為，用于模擬和分析現實的經濟、社會問題。

隨著對技術、生物和社會等復雜系統的研究，人們提出了復雜網絡這一理論框架來研究顯示網絡拓撲結構和動力學特征。復雜網絡的相關研究表明，經濟和社會網絡結構具有獨特的統計特性， 對于復雜網絡的研究能夠更真實地描述現實社會網絡的結構和演化過程^[6~8]。網絡是個體的聚集與交互，個體是網絡的構成元素。因此，結構和個體之間的關系、復雜網絡的統計特性與個體策略和行為之間的相互影響與制約是一個非常值得研究的問題。本文將演化博弈理論與復雜網絡理論相結合，分析個體在復雜網絡結構中的策略選擇與行為模式，研究個體的行為對于網絡結構的影響，以圖找到一種對復雜網絡生成原因的解釋框架，并希望能夠依托這個框架去分析社會、經濟網絡中個體行為的變化趨勢。

1 演化博弈與復雜網絡

演化博弈論（evolutionary game theory）以達爾文生物進化論和拉馬克的遺傳基因理論為思想基礎，將博弈理論與動態演化過程分析結合起來，分析從個體到群體行為的形成機制，研究種群的進化趨勢及穩定性^[9]。演化博弈理論認為，由于參與博弈的個體的有限理性，其博弈的最優均衡不能在初始時就找到，必須通過大量反復的博弈過程去修正和改進個體策略。所有參與博弈的個體在經過反復博弈后選擇的某個最優的、穩定的策略即為演化穩定策略（ESS）^[10]。

與經典的博弈理論相比，演化博弈論放棄了參與人完全理性假設，認為參與人非完全理性，其決策需要經歷一個非常復雜的調整過程；并從系統論角度出發，將群體的調整過程看做是一個動態系統在各種影響因素的共同作用下達到均衡的過程，認為均衡是均衡過程的函數。相對于經典博弈論對靜態的博弈均衡的集中討論，演化博弈論更著重于對演化穩定策略的研究，能夠描述動態系統的局部動態性質，預測個體行為。

一般來說，演化過程是兩個基本要素的結合，即多樣性變異機制和偏好選擇機制。演化穩定性強調了變異的作用，而復制動態則強調了選擇的作用。演化穩定策略意味著種群選擇的策略能夠獲得最佳的收益并消除任何小的突變群體的擾動。在演化博弈模型中，隨機(突變)因素起著關鍵的作用，演化過程常被看成是一種試錯的過程。行為人會嘗試各種不同的行為策略，并且每一次都將發生部分替代；復制動態是指使用某一純策略的人數所占比例的增長與使用該策略所得收益和群體平均收益的差成正比。復制動態模型能夠較好地描繪出有限理性個體的群體行為變化的趨勢，從而更準確地預測個體的群體行為^[11]。

最簡單的復雜網絡是20世紀50年代匈牙利數學家PErdǒs和A. Rényi定義的“無明確設計原理的、具有隨機連接關系的大規模隨機網絡”。在其建立的ER隨機網絡模型中，首先給定網絡中的定點數目，然后任意兩點之間以相同的常數概率連接在一起完全隨機地構成網絡。該模型自提出后一直在網絡研究中扮演重要的角色，被廣泛應用于社會學和生態學的研究。隨機網絡的拓撲結構與度分布狀態如圖1所示。

但是近年來，對一些大規模的復雜網絡的統計研究表明，大量的真實網絡（包括社會、技術、生物網絡等）并不符合隨機網絡模型的定義如普遍存在的動態演化系統表現出的“馬太效應”（即“富者愈富”現象）。為了解釋許多現實網絡中的冪律分布的產生機理，1999年Barabasi和Albert結合實際網絡中的兩個重要特性，即增長（growth）和優先連接（preferential attachment），提出了無標度網絡模型（BA）^[6]，其后有很多學者對該模型進行了變形和改進。無標度網絡的拓撲結構和度分布狀態如圖2所示。

2 復雜網絡上的演化博弈研究

現有的復雜網絡研究一般將節點的度作為新增節點擇優的主要因素，而從網絡的演化角度上看，節點的擇優機制應該考慮節點的度和節點的效用（收益）兩方面，而不應該僅僅從統計特性上去考慮節點的連接狀況^[12，13]。復雜網絡為大量個體間博弈關系的描述提供了基礎，即用復雜網絡中的節點表示參與博弈的個體，邊表示個體間的博弈關系。因此筆者考慮在復雜網絡上進行演化博弈來分析網絡節點間的合作和節點的效用（收益）狀況。在每一代中，所有的節點按照更新規則更新自己所選擇的策略，并同步進行新一輪博弈，節點在博弈中獲得的收益累計作為策略選擇的依據，如此重復迭代直到獲得演化穩定均衡狀態。

對于現實社會而言，個體行為的選擇大多基于自身收益的考慮。而囚徒博弈已經成為了一個世人皆知的用于研究由自私的個體構成的集團中的合作現象的范例。筆者選擇在復雜網絡上進行演化的囚徒博弈。在囚徒博弈中，博弈個體可以選擇cooperation（合作者）或者defection（背叛者）。當博弈雙方均選擇合作時，每方都會獲得相等的收益且此時總收益最大；當某一個體選擇背叛而對方選擇合作時，背叛方將獲得最高的個體收益。對于經典的理性博弈理論來說，博弈雙方都將選擇背叛，這是一個占優策略均衡（DSE）。但是這樣的均衡將會導致博弈雙方的總收益并非可能的最高收益，從而會導致社會福利的損失，使決策者陷入兩難境地。如果把囚徒博弈一般化到有n個參與者的情況，所謂的即“公有的悲劇”。從大衛·休謨起，這個問題便在經濟學中研究公共產品時產生，經濟學家們意識到只要人們按照私利的驅使去行事，就會引起公共產品提供的不足和公共資源的過度使用^[14]。

任何對稱性2×2博弈通過標準化都可以表示為平面中的一個點^[10]。因此，對博弈的收益矩陣進行標準化，使得博弈僅依賴于一個參數。在囚徒博弈中，雙方均采取合作策略時各自獲得的收益為R，雙方彼此背叛時各自獲得的收益為P；一方選擇合作而另一方選擇背叛時，背叛者獲得T收益，而合作者獲得收益為S，且T>R>P>S。令T=b>1， R=1， 且 P=S=0。為了避免背叛者相對于合作者的優勢過大而影響仿真結果，令1<b<2^[15]。初始時，cooperation和defection在網絡上隨機均勻分布，即各占到總節點數的50%。在每一代演化中，所有直接相連的節點個體間進行一輪給定的博弈，并按照收益矩陣獲取相應收益，個體的收益可以累積。當本代演化結束后，各節點個體通過當前鄰域（其直接相連的鄰居群體）內個體收益的比較，選擇收益最高者的策略作為自己下一輪演化中所采取的策略。

在規則網絡上，由于囚徒博弈的納什均衡是雙方的背叛，經過一段時間的演化博弈后，個體間合作的概率在短時間內就降到較低的水平。本文僅考慮在隨機網絡上與無標度網絡上進行節點間演化博弈，并比較演化穩定后節點間關系與收益的情況^[16]。

隨機網絡上節點間演化博弈的結果如圖3、4所示。仿真中網絡的節點數目為1 000，演化博弈500代，且圖中所示為多次仿真結果的平均值。

多次的演化博弈仿真結果表明，在隨機網絡上，當背叛者相對于合作者優勢較小時（如b=1.2），由于隨機網絡結構具有一定的局域連通性與小世界特征，網絡上各節點間將以較高頻率進行合作。當b逐漸增大時，背叛者相對于合作者優勢增加，整個網絡上節點的策略選擇和收益分布均逐漸趨近于隨機分布狀態。

采用BA無標度模型來建立一個演化博弈的網絡基礎。節點代表網絡中的個體，個體將參與博弈；邊代表網絡上節點間的連接關系。初始具有m0個相連接的節點，每步新增一個具有m條邊的節點（m＜m0）。其連接到現有節點i的概率與該節點的度數有關，即∏i=ki/∑jkj，j包含所有現存節點。圖5為所建立的無標度網絡度分布的對數圖。本文所建立的網絡節點度分布概率為P（k）=652.4k-2.03，置信區間為95%。

無標度網絡上節點間演化博弈的結果如圖6所示。節點數、演化博弈次數與更新規則等同隨機網絡下的仿真。

圖中的仿真結果表明，在無標度網絡的情況下無論b∈(1，2)如何選擇，即使在背叛者的收益接近于合作者兩倍時(b=1.8)，整個網絡上的節點的策略仍然會逐漸趨近于選擇合作，而且合作概率最終都接近于90%。不過對于不同的b的取值，可以看出b越大，博弈個體選擇合作的過程越漫長，需要經過一段時間的反復之后，節點的策略才會逐漸調整為合作。經過多次的模擬，這種合作涌現現象依然存在。將b的取值增大再進行仿真，筆者發現即使在b=3左右時，無標度網絡中仍然有可能會涌現出大量的合作現象，但也有可能會出現合作概率非常低的情況。對于背叛者收益遠大于合作者收益的情況，演化博弈的均衡合作概率會降低到10%左右。對于b在取值稍大時出現的有可能合作也有可能背叛的情況，筆者給出一個啟發式解釋：當初始時，如果大量連通性較高的節點隨機選擇了合作，則演化博弈結果將出現合作的大量涌現；反之如果大量連通性較高的節點隨機選擇了背叛，則演化博弈結果將扼殺節點間的合作。

將網絡中節點數量減少至500甚至200時，上述仿真結果仍然會出現。本文考察了網絡節點數為200時非合作現象減少的過程，并抽取了其中的若干代圖例，如圖7所示（各圖相對應的節點間合作概率依次為0.49、0.57、0.76、0.89）。從圖中可以看到，隨著演化過程的進行，背叛者的概率會大幅度降低，最終使合作頻率到達一個演化穩定狀態。

根據博弈收益矩陣可以確定本文所選用的博弈的復制子動態方程為F(x)=x(x-1)[(x+b)x-b]。求解復制子動態方程的不動點，得x1=0，x2=1和x3=b/(1+b)。其中：x1和x2意味著群體成員趨近于相同策略（cooperation或defection）的選擇；x3是一個混合策略納什均衡值。從任何內點初始位置出發，總體狀態都會收斂到兩個演化穩定策略x1和x2之一；在b取1.2、1.4、1.6、1.8時，混合策略納什均衡點x3分別為0.545、0.583、0.615和0.64。按照復制子動態對于均衡點的分析，在個體策略選擇均勻分布的情況下（x≈0.5），群體的選擇將會向x1靠攏，即選擇背叛^[17]。但事實上，仿真結果表明，在復雜網絡環境下，群體的選擇最終將趨近于合作。

為了揭示合作涌現的原因，本文對各次演化博弈中收益的分布進行分析。圖8顯示了無標度網絡下節點進行演化博弈的個體收益分布圖。由圖中可以明顯看出網絡上節點收益的冪律分布特性，分析同時還證明了個體收益的分布符合帕累托法則，即少數個體占據了整個社會絕大部分的財富。在復雜網絡環境下，計算表明大約7%的節點占有的收益超過了總收益的90%，且這7%的節點都是網絡中連通性較高的節點^[18]。由于在博弈中個體的趨利行為，個體都爭相去追逐鄰域內收益最高者的策略，以圖獲得更多的收益和信息。對網絡總收益進行分析后可以看出，合作所占比例越大，網絡節點的總收益越大，隨著演化博弈的進行，合作概率更高的網絡的總收益遠遠大于普通網絡演化博弈的總收益。換言之，傾向于背叛者的經濟政策與規則將阻止合作的出現并最終造成社會福利的大量喪失。在更改網絡節點數量和b值后，仿真仍然可以得到相同的收益分布結果。

3 結束語

從本文中的仿真結果可以推斷出，個體間協作關系的確定與網絡規模無關，在正常取值范圍內與背叛者相對合作者的優勢b也無關，而僅與網絡的拓撲結構相關。在與隨機網絡中的仿真結果比較可以進一步認為，演化博弈中合作涌現的原因主要來源于網絡成長的擇優機制，即網絡的無標度特性是合作涌現的根本原因。同時，合作的概率與網絡總收益相關，在合作概率較高的網絡基礎上，總收益會達到一個較高的水平，而合作概率的降低將帶來福利的大量損失。

正如前文所述，現有的復雜網絡研究一般將節點的度作為新增節點擇優的主要因素，而從網絡的演化角度上看，節點的擇優機制應該考慮節點的度和節點的效用兩方面。本文的研究也證明了這一點，在演化過程中，節點的效用、收益在網絡演化過程中才是真正的“優”。正因為這種“優”的存在，收益大、效用大的節點才能在網絡中脫穎而出，獲得更高的連通性并成為鄰近區域內的中心節點。這一點也就是傳統意義上的“馬太效應”，即富者愈富、貧者愈貧。本文的分析將有可能從演化的角度上對馬太效應的機理進行解釋，并在一定程度上揭示復雜網絡形成的原因。

參考文獻：

[1]張維迎.博弈論與信息經濟學[M]. 上海: 上海人民出版社，2004.

[2]MAYNARD-SMITH J， PRICE G R. The logic of animal conflicts[J]. Nature， 1973，246(5427):15-18.

[3]MAYNARD-SMITH J. The theory of games and the evolution of animal conflicts[J]. Journal of Theoretical Biology， 1974，47(1):209-221.

[4]SELTEN R. A note on evolutionarily stable strategies in asymmetric animal contests[J]. Journal of Theoretical Biology， 1980，84:93-101.

[5]SELTEN R. Evolutionary stability in extensive two-person games correction and further development[J]. Mathematical Social Scien-ces， 1988，16(3):223-266.

[6]ALBERT R， BARABASI A L. Statistical mechanics of complex networks[J]. Review of Modern Physics， 2002，74(1):47-97.

[7]NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review， 2003，45(2):167-256.

[8]WATTS D J， STROGATZ S H. Collective dynamics of small world networks[J]. Nature， 1998，393(6684):440-442.

[9]MAYNARD SMITH J. Evolution and the theory of games[M]. Cambridge: Cambridge University Press，1982.

[10]WEBULL J. Evolutionary game theory[M]. New Jersey: Princeton University Press，1995.

[11]TAYLOR P， JONKER L. Evolutionary stable strategies and game dynamics[J]. Mathematical Biosciences， 1978，16:76-83.

[12]LI Meng-hui， WANG Da-hui，FAN Ying， et al. Modeling weighted networks using connection count[J]. New Journal of Physics， 2006，72(8):36-38.

[13]LI Meng-hui， WU jin-shan， WANG Da-hui， et al. Evolving model of weighted networks inspired by scientific collaboration networks[J]. Physical A， 2007，375(1):355-364.

[14]MONTER C， SERRA D. Game theory and economics[M]. Hampshire: Palgrave Macmillan，2003.

[15]SANTOS F C， PACHECO J M. Scale-free networks provide a unifying framework for the emergence of cooperation[J]. Physical Review Letters， 2005，95(9):98-104.

[16]PACHECO J M， SANTOS F C. Network dependence of the dilemmas of cooperation[C]// Proc of International Conference on Science of Complex Networks: from Biology to the Internet and WWW. New York: American Institute of Physics， 2005:90-100.

[17]TAYLOR C， FUDENBERG D， SASAKI A， et al. Evolutionary game dynamics in finite populations[J]. Bulletin of Mathematical Biology， 2004， 66(6):1621-1644.

[18]HU Mao-bin， WANG Wen-xu， JIANG Rui， et al. A unified framework for the Pareto law and Matthew effect using scale-free networks[J]. The European Physical Journal B， 2006，53(2):273-277.

[19]OHTSUKI H， NOWAK M A. Evolutionary games on cycles[J]. Proc of the Royal Society B: Biological Sciences，2006，273(1598):2249-2256.

[20]SANTOS F C， RODRIGUES J F， PACHECO J M. Graph topology plays a determinant role in the evolution of cooperation[J]. Proc of the Royal Society B: Biological Sciences， 2006，273(1582):51-55.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文