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

王 健 趙 凱

(華僑大學(xué)，廈門 361000)

?

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

王 健 趙 凱

(華僑大學(xué)，廈門 361000)

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

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

引 言

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

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

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

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

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

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

其中Ωx表示x的鄰居構(gòu)成的集合。

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

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

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

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

1 模 型

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

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

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

1.1 種群博弈模型(Population Game)

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

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

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

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

1.2 基于Agent的演化博弈模型

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

為了反映博弈的動態(tài)演化，在每輪的階段博弈結(jié)束后，每位參與人可以對自己與鄰居們的收益進行比較，如果鄰居的收益高于自己的收益，則把自己的策略改變?yōu)樗奈秽従又惺找孀罡叩牟呗?，否則就保持原有的策略不變。

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

1.2.1 合作者入侵背叛者

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

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

(2)當(dāng)3b-4c

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

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

由此可見，合作者入侵背叛者，并最終在群體中占據(jù)主導(dǎo)地位的條件是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)當(dāng)3b-4c>2b時，c/b<0.25，背叛者的數(shù)量將在下期縮減為1個，并最終保持在4個。

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

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

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

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

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

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

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

(1)當(dāng)c/b>0.5時，演化的均衡結(jié)果是群體完全由背叛者構(gòu)成。

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

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

圖1展現(xiàn)了c/b分別為0.2與0.4時的情況。

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

圖1 網(wǎng)格上囚徒困境博弈的仿真

2 結(jié) 論

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

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

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

CDCD16,160,1919,03,3

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

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

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

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

注釋：

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

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

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

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

[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]丁絨，孫延明．企業(yè)競合行為的演化博弈試驗與集群聯(lián)盟群體行為研究[J]．工業(yè)技術(shù)經(jīng)濟，2013，(4)：68～77

[16]費孝通.鄉(xiāng)土中國[M].北京：外語教學(xué)與研究出版社,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

(責(zé)任編輯：史 琳)

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

中央高?；究蒲袠I(yè)務(wù)費資助項目·華僑大學(xué)哲學(xué)社會科學(xué)青年學(xué)者成長工程“‘承諾’的可信性和宏觀經(jīng)濟政策的動態(tài)不一致——一個博弈論的視角”(項目編號：12SKGC-QG17)。

王健，華僑大學(xué)數(shù)量經(jīng)濟研究院助理研究員，經(jīng)濟學(xué)博士。研究方向：博弈論、計算經(jīng)濟學(xué)。趙凱，華僑大學(xué)數(shù)量經(jīng)濟研究院講師，經(jīng)濟學(xué)博士。研究方向：博弈論、計量經(jīng)濟學(xué)。

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

F224.32；F270

A