基于Agent的演化博弈下的合作行為研究

王 健 趙 凱

(華僑大學，廈門 361000)

?

基于Agent的演化博弈下的合作行為研究

王 健 趙 凱

(華僑大學，廈門 361000)

文章在演化博弈的視角下，利用重復囚徒困境博弈(IPD)對合作的演化進行分析。在平均場假設下，合作策略無法在競爭中生存。而在基于Agent的演化博弈中，合作策略有可能獲得成功。其原因在于通過限制合作行為的范圍，可以使合作者聚集成簇狀，從而防止合作的紅利被背叛者占有。通過理論推導與計算機仿真，文章證明了利他策略獲得成功的條件是c/b/1/m，并對此結果做出了解釋。

合作 演化博弈 IPD Agent 種群博弈模型

引 言

合作行為意味著合作者付出一定的成本以期獲得共贏的局面，但機會主義者卻可以逃避付出并享受別人的合作行為帶來的好處。在達爾文主義的視角下，自然選擇并不會垂青于合作者。人類文明的產生和發展都依賴于大規模的合作，因此合作行為如何得以產生并持續發展壯大就成為了自然科學和社會科學領域的一個重大問題，不少學者也對此進行了研究。其中Trivers(1971)的互惠理論認為合作行為類似于投資，目的是為了在可預見的將來得到相應的回報[1]；Boyd和Richerson(1982)從文化傳播的角度對合作的產生和演化進行了解釋[2]；Zahavi(1975)的昂貴信號理論表明，合作行為可以被看作一種信號，讓發送者表明自己的類型以提高自己的社會地位[3]；除此之外，Alexander(1987)的間接互惠(Indirect Reciprocity)[4]以及Nowak和Sigmund(1998)基于聲譽(Image Scoring)機制的模型[5]等都從不同的視角對合作行為的產生和維持進行了有益的探索。

合作產生于人與人之間的互動，因此博弈論便成為了研究合作行為的強大工具。其中囚徒困境博弈(PD)經常被用來研究合作的產生和演化。在經典博弈論①下對囚徒困境博弈進行分析可知。雙方都選擇背叛是唯一的納什均衡，這個結果對有限次IPD也是適用的。在無限次IPD中，根據無名氏定理(Folk Theorem)，合作可以構成一個SPNE的結果。Kreps等(1982)通過把不完全信息引入動態博弈，論證了當參與人的理性不是共同知識的情況下，合作可以在有限次IPD中出現[6]。

演化博弈論(Maynard Smith，1982)的發展也為合作行為提供了新的視角[7]。演化博弈論不再將人模型化為超級理性的博弈方，認為人類通常是通過試錯的方法達到博弈均衡的。依賴于平均場(Mean-field)假設的演化博弈也稱為種群博弈(Population Game)。種群博弈認為種群中的個體總是以相同概率與其他個體進行博弈，因此不同策略的收益完全取決于種群中不同類型個體的比例。種群博弈的核心概念是策略的演化穩定性。Maynard Smith和Price(1973)提出的演化穩定策略(ESS)的概念認為種群中的ESS可以抵擋小部分突變策略的入侵，因而具有演化穩定性[8]。Taylor和Jonker(1978)把個體的繁殖率與其在博弈中的收益聯系在一起，通過復制者動態方程來研究模型的動態演變過程[9]。Foster和Young(1990)提出了隨機穩定性(Stochastic Stability)的概念[10]，Cabrales(2000)采用了隨機微分方程來建立隨機復制者動態模型[11]。

與種群博弈不同的是，有些時候個體之間的相互作用與它們之間的距離存在密切關系，此時種群的微觀結構就會對博弈的結果產生影響，這種模型通常被稱為基于Agent的演化博弈模型②，這個概念最早由諾瓦克等人(Nowak和May，1992；Nowak等，1994)提出[12，13]。在基于Agent的演化博弈模型中，博弈參與者被置于網絡中的節點上，并與臨近的個體(Neighborhood)進行博弈，在每輪博弈結束后，每個參與人根據一定的更新規則來改變自身的狀態，大量參與人通過簡單的相互作用構成動態系統的演化。

在一個典型的基于Agent的演化博弈模型中，網絡中每個節點表示一個參與人，所有的參與人都是同質的。每個參與人與其鄰居③分別進行二人矩陣博弈(Matrix Game)，博弈的收益矩陣為A。位于節點x的參與人可以使用Q種純策略中的一種，每種純策略都可表示為一個Q維向量。

x與其鄰居分別進行二人博弈，并累計每次博弈的收益，構成x的收益函數Ux。

其中Ωx表示x的鄰居構成的集合。

在博弈結束之后，參與人會通過一定的更新規則選擇性地改變自己的策略。如果每個參與人都同時進行策略更新，這種更新過程就稱之為同步更新(SynchronousUpdate)，反之就稱為異步更新(AsynchronousUpdate)。常用的更新規則包括變異(Mutation)、模仿(Imitation)、WSLS(Win-Stay-Lose-Shift)等。以下僅簡要介紹本文將使用的更新規則——模仿。

模仿的更新規則可被看作是一種Moran過程，在這個規則下，在每輪博弈結束之后，參與人x將從其鄰居Ωx中隨機選出參與人y。x把策略sx改變為sy當且僅當y的收益大于x。

如果我們用w(sx→sx′)表示單位時間內x的策略的變化率，則有下式成立：

在基于Agent的演化博弈模型中，計算機仿真是經常被使用的。本文在演化博弈的框架下，通過囚徒困境博弈研究合作的演化：(1)在平均場假設下，建立一個種群博弈模型，用復制者動態方程研究模型的均衡解。(2)在二維網絡建立一個基于Agent的演化博弈模型，并使用Netlogo軟件進行計算機仿真。(3)對兩個模型的結果進行比較，得出相應的結論。

1 模 型

我們通過一個囚徒困境博弈來闡述合作行為的演化問題。在演化博弈中存在兩種參與人，合作者C與背叛者D。合作者付出c的成本，并給對方帶來b的收益(在本文中我們始終假設b>c，即合作的收益大于成本，否則合作就沒有意義了)。而背叛者不付出任何成本，也不給對方帶來任何收益。博弈的收益矩陣如下表所示：

CDCDb-c,b-c-c,bb,-c0,0

下面我們分別建立種群博弈模型與基于Agent的演化博弈模型，并對二者進行理論推導和計算機仿真。

1.1 種群博弈模型(Population Game)

在種群博弈模型中，我們只需要考慮不同類型的個體在群體中的比例。以下使用復制者動態方程的方法分析模型的動態演變。

UC=Pt*(b-c)+(1-Pt)*(-c)=bPt-c

UD=Pt*b+(1-Pt)*0=bPt

在演化博弈中，我們假設每個參與人的繁殖率等于它在博弈中的收益，且后代的類型與親代相同。經過dt的時間，合作者在群體中所占的比例Pt+dt可由下式算出：

1.2 基于Agent的演化博弈模型

我們在一個二維規則網絡中建立演化博弈模型。每位參與人占有一個網格，在每輪博弈中，它與上下左右的四位鄰居(Von Neumann Neighborhood)進行囚徒困境博弈，并累計博弈的收益。

為了反映博弈的動態演化，在每輪的階段博弈結束后，每位參與人可以對自己與鄰居們的收益進行比較，如果鄰居的收益高于自己的收益，則把自己的策略改變為四位鄰居中收益最高的策略，否則就保持原有的策略不變。

我們研究的重點是：合作者是否可以入侵由背叛者占據的群體，或是反過來背叛者是否可以入侵合作者的群體。由于合作者與背叛者的分布可能出現的不同情況非常之多，很難用解析方法進行求解(Nowak，2006)[14]。以下我們分別分析這兩個問題。

1.2.1 合作者入侵背叛者

我們用不同顏色網格表示不同的參與人：其中灰色表示合作者，白色表示背叛者。下圖展現的是一個由背叛者構成的群體中出現了一小部分的合作者，其中合作者占據了群體中3*3的網格。根據分析的需要，我們只畫出了合作者與部分背叛者，并寫出它們在博弈中的收益。

(1)當b>4b-4c時，0.75

(2)當3b-4c

(3)當b=3b-4c時，c/b=0.5，合作者的數量保持在9個不變。

(5)當b<2b-4c時，c/b<0.25，合作者的數量將在下期擴張為21個，并持續擴張。

由此可見，合作者入侵背叛者，并最終在群體中占據主導地位的條件是c/b<0.25。

1.2.2 背叛者入侵合作者

采用類似的方法，我們畫出被合作者包圍的背叛者在博弈中的收益。

4b-4c3b-4c3b-4c3b-4c4b-4c3b-4c2bb2b3b-4c3b-4cb0b3b-4c3b-4c2bb2b3b-4c4b-4c3b-4c3b-4c3b-4c4b-4c

(1)當3b-4c>2b時，c/b<0.25，背叛者的數量將在下期縮減為1個，并最終保持在4個。

(2)當3b-4c≤2b≤4b-4c時，0.25≤c/b≤0.5，背叛者的數量保持不變。

(3)當b<4b-4c≤2b時，0.5

(4)4b-4c0.75，合作者的數量將在下期擴張為21個，并持續擴張。

我的畫：有位畫家說過，“好的繪畫在你面前是往后退的。”多年的繪畫實踐更明白了其中的道理。優秀的繪畫呈現的是一種整體的氛圍，吸引你去感受畫面背后的一種精神性的東西，而不是停留在表面的技法、色彩等物質性上。精神性的呈現，需要你對物的持續關注和體驗，才能在最為熟悉的物上得到靈感。因此我畫身邊的人與物，通過和諧的色調，細膩的手法，書寫的筆意，努力營造畫面的氛圍，給物以升華，如同打開一扇窗。

由此可見，背叛者入侵合作者，并最終在群體中占據主導地位的條件是c/b>0.5。

1.2.3 對基于Agent的演化博弈的仿真

以下考慮合作者和背叛者在二維網格中分布的一般情況，我們使用Netlogo軟件進行計算機仿真。首先在100*100的網格中隨機生成合作者與背叛者，網格的邊緣被設為回環(Torus)以避免出現邊界問題。博弈的收益矩陣和其他設定都與前文一致。仿真的結果印證了我們在此之前的分析：

(1)當c/b>0.5時，演化的均衡結果是群體完全由背叛者構成。

(2)當0.25≤c/b≤0.5，演化的均衡結果是群體中合作者與背叛者并存，且背叛者占大多數。

(3)當c/b<0.25時，演化的均衡結果是群體中合作者與背叛者并存，且合作者占大多數。

圖1展現了c/b分別為0.2與0.4時的情況。

圖1表明，網絡中囚徒困境博弈的動態演化可以很快達到均衡，在適當的參數下，合作者與背叛者共同存在。圖1的左半部分和右半部分分別表示在0.25≤c/b≤0.5(以c/b=0.4為例)和c/b<0.25(以c/b=0.2為例)的條件下，博弈達到均衡狀態下合作者與背叛者的情況。在圖1a和圖1b中，黑色的點表示合作者，白色的點表示背叛者。當c/b=0.4時，合作的成本較高，此時合作者通過結成簇狀以避免被淘汰。而當c/b=0.2時，合作者可以迅速擴張，并在總體中占據較大的比例。圖1c與圖1d顯示了在兩種情況下，博弈的均衡狀態中合作者(虛線)和背叛者(實線)所占的比例。

圖1 網格上囚徒困境博弈的仿真

2 結 論

合作是人類社會存在和發展的必要條件。在演化博弈的平均場假設下，每個參與人等概率與其他參與人進行博弈，此時合作行為無法抵御背叛者的剝削，只能在競爭中被淘汰。而在基于Agent的演化博弈中，我們限制了合作的范圍(讓每個參與人僅和其鄰居進行博弈)，這樣可以防止合作紅利的外溢，從而使合作行為有機會得到發展。

通過理論推導和計算機仿真，我們證明了在二維規則網絡中合作策略獲得成功的條件：c/b<0.25。從表面上看，這個結果缺乏直觀含義。但如果我們將博弈中鄰居的數量從4改成8(Moore Neighborhood)，并對這種情況進行仿真，我們可以發現合作策略獲得成功的條件變成了c/b<1/8。不僅如此，當我們改變鄰居的數量m，讓每個參與人與不同數量的鄰居進行博弈，并分別進行仿真。我們可以證明二維規則網絡中合作策略獲得成功的條件是c/b<1/m，且這個結果對于任意數量的m都是適用的。這個式子的含義是：當合作者的合作成本c可以由足夠多合作者的合作收益b來補償的話，合作者在群體中的頻率就將上升。在網絡博弈中，這也就意味著合作者必須“扎堆”，保證自己的鄰居中有足夠多的合作者，才能保證合作策略的成功。在我們的仿真中，均衡狀態下總可以看到合作者結成塊狀或是簇狀區域，就是對此的最好證明。

以下我們用一個例子表明c/b<1/m這個公式的應用，假設二人囚徒困境博弈的收益矩陣如下：

CDCD16,160,1919,03,3

在這個博弈中，b與c的數值分別為16和3，此時1/8

值得指出的是，以上結論并不是孤立的。我們暫時借用生物學的思維：漢密爾頓(1964)在研究動物行為時發現，個體之間合作的原因之一在于雙方存在親緣關系，進而提出了漢密爾頓法則：即個體之間達成合作的條件是c/b

本研究在現實生活中也有廣泛的應用。c/b<1/m這個式子清晰地表明了網絡結構對于合作產生和維持的重要性。根據費孝通(2013)[16]，傳統社會很大程度上依賴于血親和熟人之間自發產生的合作，而在現代社會中人與人之間的關系卻日益淡漠，鄰里之間“老死不相往來”的情況并不少見。這種情況并不難通過本文得到的理論來進行解釋，因為m可以表示人與社會互動的程度，在傳統社會中較小的人口流動率導致人們的交際面較窄，此時人們更容易和有限的幾個朋友達成合作。而現代社會發達的通訊技術降低了人們的通訊成本，隨著人們社交網絡的日益發達，單個的朋友對人們而言卻變得越來越不重要，人們之間的關系就越疏遠，從而要達成合作就更難④。

對基于Agent的演化博弈的研究在學術界方興未艾，例如Chiong和Kirley(2011)對均勻小世界網絡和隨機均勻網絡下N人重復博弈的研究[17]，Ichinose等人(2014)對無標度網絡中合作涌現的分析[18]等。然而目前大部分工作都集中在囚徒困境博弈或雪堆博弈(Snow-drift Game)研究上，其它類型的博弈還缺乏系統地研究。對基于Agent的演化博弈在多人領域和其他類型博弈上的擴展的研究是很有前景的。

注釋：

①本文所說的經典博弈論依賴于兩個假設：(1)參與人具有“超級理性”(Hyper-rational)；(2)參與人的理性是共同知識。

②這事實上就是上世紀50年代馮諾依曼提出的元胞自動機(Cellular Automata)的概念。

③如果網絡中兩個節點之間的距離為1，則它們互為鄰居。在二維規則網絡中，常用的概念包括Moore Neighborhood和Von Neumann Neighborhood。節點x的Moore Neighborhood包括x周圍的8個節點，而其Von Neumann Neighborhood只包括它周圍的4個節點。

④現代社會是以大范圍的合作為標志的，這似乎與本文的結論不符合。但事實上現代社會中的合作依賴于法律、道德的外在約束，以及由間接利他作為保障的聲譽機制。而由于篇幅的原因，這并不在本文的研究范圍內。但如果一旦剝離這些外在約束，我們會發現現代社會中人們之間的合作鏈條是很脆弱的。

[1]Trivers R L.The Evolution of Reciprocal Altruism[J].Quarterly Review of Biology,1971:35～57

[2]Boyd R,Richerson P J.Cultural Transmission and the Evolution of Cooperative Behavior[J].Human Ecology,1982,10(3):325～351

[3]Zahavi A.Mate Selection—a Selection for a Handicap[J].Journal of Theoretical Biology,1975,53(1):205～214

[4]Alexander R D.The Biology of Moral Systems[M].Transaction Publishers,1987

[5]Nowak M A,Sigmund K.Evolution of Indirect Reciprocity By Image Scoring[J].Nature,1998,393(6685):573～577

[6]Kreps D M,Milgrom P,Roberts J,et al.Rational Cooperation in the Finitely-Repeated Prisoners’ Dilemma[R].Stanford Univ Ca Inst For Mathematical Studies In The Social Sciences,1982

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

[8]Smith J M,Price G R.lhe Logic of Animal Conflict[J].Nature,1973,246:15

[9]Taylor P D,Jonker L B.Evolutionary Stable Strategies and Game Dynamics[J].Mathematical Biosciences,1978,40(1):145～156

[10]Foster D,Young P.Stochastic Evolutionary Game Dynamics?[J].Theoretical Population Biology,1990,38(2):219～232

[11]Cabrales A.Stochastic Replicator Dynamics[J].International Economic Review,2000,41(2):451～481

[12]Nowak M A,May R M.Evolutionary Games and Spatial Chaos[J].Nature,1992,359(6398):826～829

[13]Nowak M A,Bonhoeffer S,May R M.Spatial Games and the Maintenance of Cooperation[J].Proceedings of the National Academy of Sciences,1994,91(11):4877～4881

[14]Nowak M A.Evolutionary Dynamics[M].Harvard University Press,2006

[15]丁絨，孫延明．企業競合行為的演化博弈試驗與集群聯盟群體行為研究[J]．工業技術經濟，2013，(4)：68～77

[16]費孝通.鄉土中國[M].北京：外語教學與研究出版社,2013

[17]Chiong R,Kirley M.Iterated N-player Games on Small-world Networks[C].Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation.ACM,2011:1123～1130

[18]Ichinose G,Sayama H.Invasion of Cooperation in Scale-free Networks:Accumulated vs.Average Payoffs[C].ALIFE 14:The Fourteenth Conference on the Synthesis and Simulation of Living Systems，14:398～399

(責任編輯：史 琳)

Cooperation under Agent-based Evolutionary Games

Wang Jian Zhao Kai

(Huaqiao University，Xiamen 361000，China)

This article used IPD to analyze the evolution of cooperative behavior in the field of evolutionary game theory.Under the mean-field assumption,cooperator cannot survive in competition with defectors.However,in agent-based evolutionary game theory,cooperators can thrive.The reason for that is by restricting the scope of cooperation,cooperators can survive by living in clusters,thereby preventing the benefit of cooperation from being exploited by defectors.This article not only compares the difference between spatial evolutionary theory and classical theory,but also analyzes the conditions needed for the emergence and maintenance of cooperation using PD game simulation on a regular network.

cooperation;evolutionary game;IPD;Agent;population game

2016—01—05

中央高校基本科研業務費資助項目·華僑大學哲學社會科學青年學者成長工程“‘承諾’的可信性和宏觀經濟政策的動態不一致——一個博弈論的視角”(項目編號：12SKGC-QG17)。

王健，華僑大學數量經濟研究院助理研究員，經濟學博士。研究方向：博弈論、計算經濟學。趙凱，華僑大學數量經濟研究院講師，經濟學博士。研究方向：博弈論、計量經濟學。

10．3969/j．issn．1004-910X．2016．05．002

F224.32；F270

A