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

2012-03-22 02:20:42楊涵新汪秉宏

上海理工大學學報 2012年2期

楊涵新，汪秉宏

（1.福州大學物理系，福州 350002；2.中國科學技術大學近代物理系，合肥 230026；3.上海理工大學復雜系統科學研究中心，上海 200093）

博弈論，又稱對策論，主要研究具有形式激勵結構的個體之間的相互作用.博弈論作為應用數學的一個分支，目前廣泛應用于生物學、經濟學、計算機科學、政治學、軍事戰略等諸多學科［1－2］.1944年，匈牙利數學家Neumann和經濟學家Morgenstern合作出版了劃時代巨著《博弈論與經濟行為》［3］，奠定了博弈論的基礎和理論體系.20世紀50年代，美國數學家Nash提出了著名的納什均衡［4］，它是指自私個體在相互作用過程中達到的一種均衡狀態，這種狀態下沒有個體可以通過單方面改變自己的策略而增加收益.納什均衡的提出極大地推動了博弈論的研究和發展.

通常博弈由4部分組成：至少有兩位博弈個體；每個博弈個體都有自己的博弈策略；當博弈個體選擇好策略后，按照一定的博弈規則進行博弈并據相應的收益函數獲得收益；在博弈過程中，博弈個體遵循自身收益最大化的最終目標，進行策略上的調整.

經典博弈理論認為個體具有完全的理性，它們根據對收益函數的分析，一步到位地選擇符合納什均衡的最佳策略.但是在現實復雜環境中，人的理性是有局限的，即使再聰明的人也會犯錯誤.同時，在生物的成長與漫長的進化過程中，個體通常無法清晰了解環境，它們只有通過不斷地試錯來適應環境，也就是說，均衡狀態不是一蹴而就達到的.因此，生物學家將生物進化論中的自然選擇和遺傳變異機制引入博弈論中，提出了演化博弈理論［5］，力圖解釋上述經典博弈論無法解答的問題.演化博弈理論著重研究有限理性的個體如何隨著時間的推移在不斷地重復博弈過程中去實現收益最大化.

在自然界和人類社會中，合作行為普遍存在，如獅群協作捕獵、人類社會大規模地生產活動等等.從大的方面來看，世界的和平與發展、地球的環境保護都離不開各國之間的相互協作.但是在一個群體中，并不是所有的個體都會采取合作的行為.由于個體存在一定的自私心理，有些人會采取不合作（背叛）的行為.如何理解自私個體之間合作行為的產生和維持受到了各領域科學家的廣泛關注［6－8］.目前，演化博弈理論被認為是研究合作行為的一個最有力的手段［9］.常見的研究合作行為的演化博弈模型有囚徒困境博弈［10］、鏟雪博弈［11］和公共品博弈［12］等.

長期以來，在演化博弈理論中通常假設個體以均勻混合的方式進行聯系，即所有個體全部相互接觸或者個體隨機接觸.然而，現實生活中個體之間的聯系并非是全耦合或者完全隨機的，而是具有特定的聯系方式.1992年，Nowak和May研究了二維方格上的囚徒困境博弈［13］，開創了網絡演化博弈研究的先河.最近十年來，隨著復雜網絡的興起［14－15］，復雜網絡上的演化博弈研究受到了廣泛的關注，取得了許多重要的進展［16－17］.本文將對前人這方面的工作做一綜述，以期對未來的研究有所啟迪.

1 復雜網絡上的演化博弈模型簡介

在復雜網絡上的囚徒困境博弈和鏟雪博弈中，初始時候每個個體（節點）以相同的概率1／2選擇合作或者背叛策略.每輪博弈中，每個個體同時和周圍的直接鄰居進行博弈獲取收益.如果兩個人都采取合作策略，則兩個人都得到R的收益.如果兩個人都采取背叛策略，則兩個人分別得到P的收益.如果一個合作一個背叛，那么合作者將得到收益S，背叛者得到收益T.在囚徒困境博弈中，這4個收益參數的排序為T＞R＞P＞S.但是在鏟雪博弈中，收益參數的排序變為T＞R＞S＞P.為了研究上的方便，囚徒博弈收益參數通常設定為［13］R＝1，P＝S＝0，T＝b＞1，鏟雪博弈收益參數通常設定為［18］R＝1，S＝1－r，T＝1＋r，P＝0 （0＜r＜1）.人們通常把b和r稱為“背叛誘惑”（temptation to defect）參數.

每輪博弈結束后，每個個體根據某種更新規則進行策略更新，并把更新后的策略作為自己下一輪博弈中采取的策略.在通常情況下，經過足夠長的時間演化后，系統會達到一個相對穩定狀態，即網絡中合作者的比例趨于穩定.穩定狀態網絡中合作者的比例通常被稱為合作頻率，是衡量系統合作水平的重要指標.

在復雜網絡的公共品博弈中，初始時候，網絡中給每個節點以相同的概率1／2隨機地賦予合作或者背叛策略.每個時間步，網絡上的每一個點i參與以它自己為中心及以它的鄰居為中心的ki＋1個群體的博弈.這里所說的一個群體是由一個中心節點及其周圍的鄰居構成.每個合作者i給每個群體分別投入1／（ki＋1）的資本（也就是說，合作者i投入的總資本為1），背叛者不投入任何成本.在每一個群體中，獲得的總資本為該群體中所有合作者投入資本的總和，群體的總資本會增值（增值系數設為r），升值后的收益平均分配給該群體中的每個點.根據這樣的收益分配規則，節點x參與以節點y為中心的群體時，從這個群體獲得的收益為

這里的i＝0代表節點y，si是與y相連的節點i的策略（si＝1表示節點i是合作者，si＝0表示節點i是背叛者），ki是節點i的度.節點x的總收益Mx為它從所參加的各個群體獲得的收益之和

這里的Ωx包括節點x及其周圍的鄰居.

與囚徒困境博弈和鏟雪博弈類似，在公共物品博弈中，個體也是根據某種更新規則不斷調整自己的策略.

網絡演化博弈中通常采用的策略更新規則有：

a.最優者替代［13］某個個體模仿周圍鄰居（包括他本人）在此輪博弈中獲得最高平均收益的個體，以其策略作為自己在下輪博弈的策略.

b.較好者擁有替代機會［18－19］每個個體隨機地選擇周圍一個鄰居進行收益比較.如果他的收益比被選擇的鄰居高，那么他保持自己策略不變.如果他的收益比被選擇的鄰居低，則他會以一定的概率選擇該鄰居的策略作為下一輪博弈的策略.

c.依賴收益差別的策略學習［20］每個個體隨機地選擇周圍一個鄰居進行收益比較.他的收益比被選擇鄰居的收益越高（越低），則他選擇該鄰居的策略作為下一輪博弈策略的概率就越低（越高）.

2 網絡結構的影響

在相同的策略更新規則下，不同的網絡結構會影響系統的合作水平.

在全連接網絡的囚徒困境博弈中，合作者的收益始終比背叛者低，因此群體的所有個體最終都會成為背叛者.Nowak和May發現，在二維格子的囚徒困境博弈中，合作者通過形成團簇結構可以有效地抵御背叛者的入侵［13］.在合作簇內部，合作者通過相互協作獲得很高的收益，從而保護合作簇內部的合作者不被外面的背叛者所取代.

Santos等發現，相比于規則網絡上比較低的合作頻率，無標度網絡上的囚徒困境、鏟雪和公共物品博弈都能出現非常高的合作水平［19－21］.他們的研究表明，無標度網絡上幾乎所有的大度節點在演化博弈過程中逐漸會被合作者所占據.由于大度節點通常擁有比小度節點更多的收益，無標度網絡中的許多小度節點將模仿大度節點的合作策略，從而導致很高的合作頻率.

Tang等研究了網絡平均度對于囚徒困境博弈中合作行為的影響［22］，發現適中的網絡平均度能最好地促進合作.當網絡平均度很大時候，系統近似于全連接的情況，這個時候合作者的收益始終比背叛者低，合作行為無法存在.當網絡平均度很小的時候，合作者周圍鄰居過少，導致合作簇內部合作者的收益不高，也抑制了合作.當網絡平均度適中的時候，合作簇內部合作者的收益比較高，能有效地抵御外部背叛者的入侵.

Rong等研究了度度相關性對于囚徒困境博弈中合作行為的影響［23］.發現相比于隨機相配網絡，在背叛誘惑參數值低的時候正配合網絡抑制合作，而在背叛誘惑參數值高的時候負配合網絡能夠促進合作.在正配合網絡中，大度節點之間的連接很多，在演化的初始階段，由于背叛的大度節點獲得比合作的大度節點更多的收益，因此合作的大度節點容易采取背叛大度節點的策略，導致網絡中所有的大度節點迅速被背叛者所占據，從而降低了網絡的合作水平.在負配合網絡中，大度節點之間的連接很少，合作的大度節點的周圍節點采取合作策略，而背叛的大度節點的周圍節點采取背叛策略，這樣一來，當背叛誘惑參數值高的時候，網絡中的合作者依然會在合作的大度節點周圍存活下來.

Rong等還研究了聚類系數可調的無標度網絡上的公共品博弈［24］.他們的研究發現，隨著聚類系數的增大，網絡的合作頻率提高.公共品博弈是一種群體性博弈，個體不僅參與以自己為中心的群體博弈，還參加以其鄰居為中心的群體博弈.因此在公共品博弈中，個體的收益不僅和鄰居的策略有關，而且和鄰居的鄰居策略有關.高聚類的網絡中會有大量的三角構造（一個節點及其周圍的兩個相互連接的鄰居），使得公共品博弈中的合作簇（相互連接的合作者組成的集團）獲得更高的收益，從而有效地促進合作行為在整個網絡中的擴散.

Ren等研究了均質小世界網絡上的囚徒困境博弈［25］.他們發現，當網絡的交叉換邊比例適中的時候（此時網絡中即有短程連邊也有遠程連邊），網絡的合作水平達到最高.網絡中短程連邊的存在，使相臨近的合作者能形成穩定的合作簇，同時，適當比例的長程邊，有利于合作者在網絡中進行大范圍擴散.

3 策略更新規則的影響

在相同的網絡結構上，設計不同的博弈策略演化規則會很大程度地影響系統合作行為的表現.

Wang等提出了基于記憶的鏟雪博弈［26］.每輪博弈結束后，每個個體會根據鄰居上一時刻的策略進行反思，即采取自己的反策略做一次虛擬博弈，從而得到虛擬收益，然后將真實收益與虛擬收益進行比較，得到所對應的最佳策略，并將其記錄到該個體的記憶中.在之后的博弈中，個體會根據前幾輪所存儲的記憶，決定采取何種策略.研究發現，二維網絡上合作頻率和收益參數r之間具有分段式的臺階關系，在某些r值附近，合作頻率會從一個值突變到另外一個值.

Szolnoki等［27］和Guan等［28］研究被模仿能力對復雜網絡演化博弈的影響.他們把個體分為A、B兩類.A類個體的被模仿能力比B類個體高，表示A類個體的策略比B類個體更容易被別人所模仿.在策略演化時，個體i采取鄰居j的概率，不但與兩者的收益差有關，而且正比于鄰居的被模仿能力.設網絡中A類個體的比例為v，他們發現存在適中比例的v，使得網絡的合作頻率達到最高.

Wang等提出了一種最差者改變策略的演化規則［29］.每輪鏟雪博弈結束后，網絡中收益最低的個體將會改變自己的策略，而網絡的其他個體保持策略不變.通過先逐漸增大后逐漸減小收益參數r，他們發現網絡的合作頻率與收益參數r之間的關系曲線呈現遲滯回線的形狀.

在通常的網絡演化博弈研究中，網絡中的節點隨機地選擇其中一個鄰居進行策略學習.也就是說，節點選擇哪個鄰居進行策略模仿是沒有任何偏好的.Yang等考慮社會差異性對于選擇鄰居的影響［30］.由于社會差異性的存在，每個節點的影響力是不同的.設定每個節點i的影響力為kαi，其中α是一個可調參數.當α＝0時候，網絡中每個節點的影響力都是相同的，當α＞0（或者α＜0）時候，度大（或者度小）的節點的影響力比較大.節點x選擇一個鄰居y進行策略更新的概率正比于節點y的影響力，即

節點x采取節點y的策略作為自己下一時間步策略的概率為

式中，κ為噪音參數（設定κ＝0.1）.節點x保持自己策略不變的概率為1－W（sx→sy）.研究發現，當α是一個適中的正值的時候，網絡的合作頻率最高.這個結果表明，當大度節點的影響力適當大的時候，能夠促進系統的合作.

此外，Szabó等研究策略更新規則中噪音κ的作用［31］，發現適中的噪音強度能使網絡的合作頻率達到最高.Wu等將博弈關系對象和策略學習對象分離開［32］，發現當博弈關系對象和學習對象之間存在一定的差異性的時候，可以最好地促進合作.

4 演化博弈動力學與網絡結構的共同演化

在通常的網絡博弈研究中，網絡結構是靜態不變的.近年來，人們開始關注在演化動力學的影響下，網絡的結構是如何變化的.

Zimmermann等提出了一個動態網絡囚徒困境博弈模型［33－34］：從一個ER隨機網絡開始，每輪博弈中個體與直接相連的鄰居進行囚徒困境博弈，它們會采納周圍鄰居（包含自己）中收益最高者的策略作為下一輪博弈.如果一個背叛者發現它模仿的鄰居是背叛者，并且收益比自己高，則這個不滿意的個體會以概率p斷開與被模仿的背叛者之間的邊，重新在網絡中隨機選擇一個節點連接.他們的研究結果顯示，只需要一個很小的概率p就可以使動態網絡的合作頻率達到一個很高的值.這是因為網絡中的節點會不斷拋棄那些背叛節點，而和合作節點建立聯系，從而使合作節點的度增大，成為網絡的中心節點，進而促進整個網絡合作水平的提高.

Li等提出了一種由演化博弈驅動生成的無標度網絡型［35］.初始時候，在一個方格網絡上，每個節點擁有一個活動的長程邊，每個節點可以控長程邊的另一端指向期望的節點.節點進行按照囚徒困境博弈，策略更新時個體x將它的收益與鄰居中收益最高者y進行比較，如果y鄰居收益高則采納其策略.同時，x把它擁有的長程邊連向y擁有的長程邊所指向的節點.隨著時間演化，網絡的度分布呈現無標度特性.

Helbing等提出的成功驅動的博弈模型［36］.在其模型中，博弈個體分布在一個二維方格上，個體會遷移到周圍中能使其收益最高的格點上.他們發現，即使初始所有人都是背叛者，在一定的噪音情況下（個體的策略會以一定概率重置），隨著時間演化，合作行為會出現突然爆發的現象，即在很短的一段時間內，合作者比例迅速增加.

Meloni等［37］在一個二維的連續空間上，考慮博弈個體隨機移動的情況.在他們研究的模型中，每個時間步，每個個體與其周圍一定距離內的其他個體進行囚徒困境博弈，隨后以速度v隨機地移動到另外一個地方.他們研究發現，隨著個體移動速度v的增大，合作頻率降低.

Yang等研究了預期導致的移動在演化博弈中的作用［38］.個體與周圍鄰居進行囚徒困境博弈獲得收益，當個體獲得的收益低于它的預期的時候，它將隨機地遷移到另外一個地方.研究發現，當預期適中的時候，背叛簇內部的背叛者由于收益低于預期產生移動，而合作簇內部的合作者由于收益高于預期保持不動，導致背叛簇的瓦解和合作簇的擴張，使合作行為在整個群體中得以蔓延.預期過低和過高的時候，都不利于合作行為的擴散.預期過低，個體很少進行移動，使得合作簇和背叛簇能同時穩定存在.預期過高，由于個體的頻繁移動，無法形成穩定的合作簇，導致合作者的滅亡.

5 展望

復雜網絡上的演化博弈研究是近年來隨著復雜網絡研究興起而逐漸引起關注的一個重要研究課題.基于前人研究工作的基礎，作者對未來復雜網絡上的演化博弈研究方向做一個展望.

a.前人主要利用數值仿真手段對復雜網絡上的演化博弈進行研究，缺乏嚴格的解析分析.目前的一些近似方法，如平均場方法、對估計方法無法解決異質網絡上的演化博弈問題.因此尋求有效的數學和統計物理方法，對數值模擬結果進行理論分析，是非常有意義的.

b.之前復雜網絡上的演化博弈研究中，個體通常單純地使用合作或者背叛策略.然而，演化博弈的研究，尤其是實驗研究表明，真實世界中的個體會采用更豐富的策略（如中立策略等），而不僅僅只限于純合作和純背叛兩種.多策略的演化博弈是未來研究的焦點.

c.目前，復雜網絡上的演化博弈研究絕大部分都是在單個網絡上進行的.實際上復雜系統是由許多具有不同結構與功能的網絡耦合而成的［39］.例如，在線社交網絡中的個體是通過互聯網進行聯系的，而互聯網又需要電力網提供的電力支持.多層耦合網絡上的演化博弈是一個創新型的研究課題，具有廣闊的發展空間.

d.大多數的復雜網絡演化博弈研究中，個體的策略演化不受外界人為的控制.如何通過調控復雜網絡中少數節點或者邊上的個體行為，從而使整個系統的合作水平得到提高，是一個具有實踐意義的研究課題.

e.演化博弈與其它動力學的結合是未來研究的焦點.例如，個體接種疫苗可以預防疾病的感染，但是接種疫苗也會帶來一定的經濟成本.可將是否選擇接種疫苗看作是兩種不同的策略，根據博弈理論的一些研究方法，對個體是否選擇疫苗進行分析［40］.再比如，利用演化博弈理論研究車輛是否搶道對交通的影響.

［1］ Smith J M.Evolution and the theory of games［M］.Cambridge：Cambridge University Press，1982.

［2］ Colman A M.Game theory and its applications in the social and biological sciences［M］.Oxford：Butterworth－Heinemann，1995.

［3］ Neumann J V，Morgenstern O.Theory of games and economic behavior［M］.Princeton：Princeton University Press，1944.

［4］ Nash J F.Equilibrium points in n－person games［J］.Proceedings of the National Academy of Sciences，1950，36：48－49.

［5］ Smith J M，Price G R.The logic of animal conflict［J］.Nature，1973，246（5427）：15－18.

［6］ Hofbauer J，Sigmund K.Evolutionary games and population dynamics［M］.Cambridge：Cambridge University Press，1998.

［7］ Hammerstein P.Genetic and cultural evolution of cooperation［M］.Cambridge：MIT Press，2003.

［8］ Axelrod R.The evolution of cooperation［M］.New York：Basic books，1984.

［9］ Gintis H.Game theory evolving［M］.Princeton：Princeton University，2000.

［10］ Axelrod R，Hamilton W D.The evolution of cooperation［J］.Science，1981，211（4489）：1390－1396.

［11］ Sugden R.The economics of rights，cooperation and welfare［M］.Oxford：Blackwell，1986.

［12］ Hardin G.The tragedy of the commons［J］.Science，1968，162：1243－1248.

［13］ Nowak M A，May R M.Evolutionary games and spatial chaos［J］.Nature，1992，359（6398）：826－829.

［14］ Albert R，Barabási A L.Statistical mechanics of complex networks［J］.Reviews of Modern Physics，2002，74（1）：47－97.

［15］ Newman M E J.The structure and function of complex networks［J］.SIAM Review，2003，45（2）：167－256.

［16］ SzabóG，Fath G.Evolutionary games on graphs［J］.Physics Reports，2007，446（4－6）：97－216.

［17］ Perc M，Szolnoki A.Coevolutionary games—a mini review［J］.Biosystems，2010，99（2）：109－125.

［18］ Hauert C，Doebeli M.Spatial structure often inhibits the evolution of cooperation in the snowdrift game［J］.Nature，2004，428（6983）：643－646.

［19］ Santos F C，Santos M D，Pacheco J M.Social diversity promotes the emergence of cooperation in public goods games［J］.Nature，2008，454（7201）：213－216.

［20］ SzabóG，To′′ke C.Evolutionary prisoner’s dilemma game on a square lattice［J］.Physical Review E，1998，58（1）：69.

［21］ 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）：098104.

［22］ Tang C L，Wang W X，Wu X，et al.Effects of average degree on cooperation in networked evolutionary game［J］.European Physical Journal B，2006，53（3）：411－415.

［23］ Rong Z，Li X，Wang X F.Roles of mixing patterns in cooperation on a scale－free networked game［J］.Physical Review E，2007，76（2）：027101.

［24］ Rong Z，Yang H X，Wang W X.Feedback reciprocity mechanism promotes the cooperation of highly clustered scale－free networks［J］.Physical Review E，2010，82（4）：047101.

［25］ Ren J，Wang W X，Qi F.Randomness enhances cooperation：a resonance－type phenomenon in evolutionary games［J］.Physical Review E，2007，75（4）：045101.

［26］ Wang W X，Ren J，Chen G，et al.Memory－based snowdrift game on networks［J］.Physical Review E，2006，74（5）：056113.

［27］ Szolnoki A，SzabóG.Cooperation enhanced by inhomogeneous activity of teaching for evolutionary prisoner’s dilemma games［J］.Europhysics Letters，2007，77（3）：30004.

［28］ Guan J Y，Wu Z X，Wang Y H.Effects of inhomogeneous activity of players and noise on cooperation in spatial public goods games［J］.Physical Review E，2007，76（5）：056101.

［29］ Wang W X，LüJ，Chen G，et al.Phase transition and hysteresis loop in structured games with global updating［J］.Physical Review E，2008，77（4）：046109.

［30］ Yang H X，Wang W X，Wu Z X，et al.Diversityoptimized cooperation on complex networks［J］.Physical Review E，2009，79（5）：056107.

［31］ SzabóG，Vukov J，Szolnoki A.Phase diagrams for an evolutionary prisoner’s dilemma game on twodimensional lattices［J］.Physical Review E，2005，72（4）：047107.

［32］ Wu Z X，Wang Y H.Cooperation enhanced by the difference between interaction and learning neighborhoods for evolutionary spatial prisoner’s dilemma games［J］.Physical Review E，2007，75（4）：041114.

［33］ Zimmermann M G，Eguíluz V M，Miguel M S.Coevolution of dynamical states and interactions in dynamic networks［J］.Physical Review E，2004，69（6）：065102.

［34］ Zimmermann M G，Eguíluz V M.Cooperation，social networks，and the emergence of leadership in a prisoner’s dilemma with adaptive local interactions［J］.Physical Review E，2005，72（5）：056118.

［35］ Li W，Zhang X，Hu G.How scale－free networks and large－scale collective cooperation emerge in complex homogeneous social systems［J］.Physical Review E，2007，76（4）：045102.

［36］ Helbing D，Yu W.The outbreak of cooperation among success－driven individuals under noisy conditions［J］.Proceedings of the National Academy of Sciences，2009，106（10）：3680－3685.

［37］ Meloni S，Buscarino A，Fortuna L，et al.Effects of mobility in a population of prisoner’s dilemma players［J］.Physical Review E，2009，79（6）：067101.

［38］ Yang H X，Wu Z X，Wang B H.Role of aspirationinduced migration in cooperation［J］.Physical Review E，2010，81（6）：065101.

［39］ Kurant M，Thiran P.Layered complex networks［J］.Physical Review Letters，2006，96（13）：138701.