基于Ｒｅｐａｓｔ．ＮＥＴ的演化囚徒博弈仿真

張登兵

［摘 要］ 本文介紹了多主體仿真的基本理論，對(duì)新一代仿真平臺(tái)Repast進(jìn)行了闡述。通過對(duì)演化囚徒困境的進(jìn)一步理論分析和仿真研究，揭示出多主體博弈的演化機(jī)制和規(guī)律。同時(shí)對(duì)影響博弈演化的因素進(jìn)行了分析，比如博弈重復(fù)的次數(shù)、博弈者的適應(yīng)系數(shù)、博弈鄰居的選擇等。并結(jié)合客觀現(xiàn)實(shí)，對(duì)仿真結(jié)果進(jìn)行了解析。仿真結(jié)果進(jìn)一步揭示了Repast仿真工具在多主體演化博弈分析中的高效性和可靠性。

［關(guān)鍵詞］ 博弈論；多主體仿真；Repast；演化

doi:10.3969/j.issn.1673-0194.2009.10.035

［中圖分類號(hào)］F224.32; N945.13［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］1673-0194（2009）10-0105-03

1Repast與多主體仿真

復(fù)雜適應(yīng)系統(tǒng)（Complex Adaptive System，CAS）理論是由圣塔菲研究所(SFI)的霍蘭教授于1994年提出的。它是當(dāng)前最具代表性且應(yīng)用最廣泛的復(fù)雜系統(tǒng)理論。而基于 Agent建模與仿真是CAS理論的重要研究方法與手段。在系統(tǒng)和管理科學(xué)中，Agent是一種自身具有“主動(dòng)行為能力”的個(gè)體。它和以前習(xí)慣使用的元素、部件、子系統(tǒng)等概念有著本質(zhì)的區(qū)別。在多主體的情況下， Agent能夠主動(dòng)處理所處環(huán)境中發(fā)生的事件，作出反應(yīng)，并且改變自身的結(jié)構(gòu)和行為規(guī)則。從人工智能和軟件開發(fā)的角度來看， Agent是一個(gè)能夠完成某項(xiàng)或一系列任務(wù)的實(shí)體?？傊M管側(cè)重點(diǎn)不同，各學(xué)科對(duì)于Agent這個(gè)概念都是強(qiáng)調(diào)了主動(dòng)性、適應(yīng)性、演化、發(fā)展這樣一些思想。這是基于主體的建模思想的核心。使用 Agent的建模方法是盡可能使微觀個(gè)體與實(shí)際個(gè)體特征一致，然后觀察在不同實(shí)驗(yàn)條件下系統(tǒng)可能的演化特征。

在復(fù)雜適應(yīng)系統(tǒng)仿真（Complex Adaptive System Simulation，CASS）中，ABM方法是極其重要和有效的。在這一領(lǐng)域有許多MABS（多主體仿真）工具，SWARM 和 Repast就是其中最杰出的代表。

SWARM 起源于著名的美國圣塔菲研究所(Santa Fe Institute，SFI)，是一組由 Objective C 語言寫成的類庫，也有用于 Java語言的編程接口，是應(yīng)用最為廣泛的 MABS 平臺(tái)。

Repast（Recursive Porous Agent Simulation Toolkit）是芝加哥大學(xué)社會(huì)科學(xué)計(jì)算研究中心研制的“循環(huán)多主體仿真工具”。而且Repast 3.0支持Java，Python，DotNet3種編程接口。Repast 在CAS理論研究、社會(huì)系統(tǒng)仿真、經(jīng)濟(jì)系統(tǒng)仿真等領(lǐng)域有著廣泛的應(yīng)用。特別是在基于 Agent 的計(jì)算經(jīng)濟(jì)學(xué)（Agent-based Computational Economics，ACE）這一新興的經(jīng)濟(jì)學(xué)分支領(lǐng)域中，Repast 正在發(fā)揮越來越重要的作用。

本文之所以選擇Repast.NET版本，主要考慮3個(gè)原因：一是微軟的視窗系統(tǒng)在國內(nèi)有著最龐大的用戶群；二是用于Repast.NET編程的C#語言是一種全新的、易用的、高效的跨平臺(tái)語言，具有良好的發(fā)展前景；三是因?yàn)镽epast在多主體重復(fù)行為處理中有著極其強(qiáng)大的功能，使得它在演化博弈建模中能夠大顯身手。

2Repast.NET建模環(huán)境和運(yùn)行環(huán)境

2.1Repast.NET建模環(huán)境

構(gòu)造Repast.NET建模環(huán)境，主要有以下兩個(gè)步驟：

首先，要安裝Microsoft VS.NET。這主要為Repast.NET建模提供一個(gè)編輯、編譯和運(yùn)行的集成開發(fā)環(huán)境。

其次，要安裝Repast.NET。從Repast網(wǎng)站上獲取免費(fèi)的名為Repast_.NET_1.1_Installer.exe的安裝程序后，可直接安裝。

完成上述步驟后，我們就建立了一個(gè)Repast.NET建模環(huán)境。這時(shí)，運(yùn)行Microsoft VS.NET，在新建C#項(xiàng)目時(shí)，就會(huì)發(fā)現(xiàn)有兩個(gè)Repast的模板可供選擇：一個(gè)是Base Repast Model；另一個(gè)是Default Repast Model。

2.2Repast.NET運(yùn)行環(huán)境

實(shí)際上，在完成Repast.NET建模環(huán)境的構(gòu)造后，也就建立了Repast.NET模型的運(yùn)行環(huán)境。不過，更多的時(shí)候，我們可能要將編譯后的模型帶到其他機(jī)器上運(yùn)行。此時(shí)，目標(biāo)計(jì)算機(jī)必須至少符合兩個(gè)條件：

（1）安裝了.NET Framework 。 這個(gè)框架，一般XP以上的系統(tǒng)都默認(rèn)安裝了。如果沒有，安裝一個(gè)微軟的dotnetfx.exe即可。

（2）擁有Repast的類庫文件。這個(gè)條件容易實(shí)現(xiàn)，可在目標(biāo)機(jī)上安裝Repast，或者在建模時(shí)將模型中用到的Repast類庫文件自動(dòng)復(fù)制到模型所在目錄。

3基于Repast.NET的演化博弈仿真過程

我們將基于Repast.NET的博弈仿真過程，分為模型背景和規(guī)則分析、仿真程序建立、仿真程序運(yùn)行3個(gè)基本步驟。本文中，以“重復(fù)博弈囚徒困境”（Ｉterated Ｐrisoners Ｄilemma，IPD）模型為例， 來介紹如何創(chuàng)建Repast仿真程序。

3.1模型背景和規(guī)則分析

我們先來看一下博弈論中的經(jīng)典模型：“囚徒困境”。模型中有兩個(gè)參與者A和B，可采取的行動(dòng)有兩個(gè)C（合作）和D（不合作）。在一次博弈中，雙方根據(jù)博弈規(guī)則，選擇利益最大化行為，不可避免地導(dǎo)致了行動(dòng)組合（D，D）的發(fā)生。

上述模型存在幾個(gè)問題：首先，它是一個(gè)基于雙主體的對(duì)陣局面，沒有考慮多方博弈的情形；其次，這種博弈不是重復(fù)的；第三，所有博弈參與人都被設(shè)定為“利益驅(qū)動(dòng)”類型，他們僅僅依賴博弈規(guī)則選擇行動(dòng)方案，沒有考慮參與人類型對(duì)行動(dòng)的影響。為此，對(duì)該模型進(jìn)行如下修改，使其更加切合實(shí)際。

首先，我們認(rèn)為，參與人是有類型的，也就是“他有自己的行動(dòng)信念”。他傾向于哪一種行動(dòng)呢？這取決于對(duì)手的選擇。假設(shè)對(duì)手合作，參與人合作的概率為p；而對(duì)手不合作時(shí)，參與人合作的概率為q。對(duì)應(yīng)一組確定的p和q將決定一個(gè)參與者類型。因此，如果p和q連續(xù)分布，則參與者有無數(shù)類型。為了研究的可行性，取其中的4種特殊類型作為研究對(duì)象。

結(jié)合現(xiàn)實(shí)情況，我們認(rèn)為上述４種類型的博弈參與者是非常典型的：ALLC，即all cooperation，“吃虧也笑的人”；TFT，即tit－for－tat，對(duì)方合作，我也合作，也就是“吃軟不吃硬的人”；ATFT，anti TFT，即“欺軟怕硬的人”；ALLD，all defect，就是所謂“軟硬不吃的頑固分子”。

其次，考慮另一個(gè)現(xiàn)實(shí)情形，就是“人”總有學(xué)習(xí)的傾向。通過學(xué)習(xí)，他可能改變自身類型，以獲取較高的效用。當(dāng)然，每個(gè)人的“學(xué)習(xí)”能力和適應(yīng)傾向是不一樣的。因此，在模型中引入適應(yīng)系數(shù)的概念，表示參與者改變類型的傾向程度。

現(xiàn)在，假設(shè)有一組參與者進(jìn)行博弈。群體中的每個(gè)成員和隨機(jī)選擇（或者按特定規(guī)律選擇）的一組“鄰居”進(jìn)行重復(fù)博弈，博弈行動(dòng)由他們的類型決定。每一輪博弈中，每兩個(gè)參與者均進(jìn)行多次博弈。在每一輪博弈結(jié)束時(shí)，參與者對(duì)這一輪博弈的所有行為者中最有效的戰(zhàn)略進(jìn)行模仿，每個(gè)參與者進(jìn)行類型適應(yīng)性改變。也就是說，在模型運(yùn)行過程中，參與者類型是變化的。

在這樣一個(gè)“多主體，重復(fù)，演化”博弈環(huán)境中，博弈將呈現(xiàn)出什么樣的規(guī)律呢？通過單純的數(shù)學(xué)分析顯然是不夠的。下面，我們就用Repast.NET來進(jìn)行仿真模擬。

3.2 仿真程序建立

根據(jù)上述模型背景，使用C#.NET為語言工具，借助于Repast.NET的強(qiáng)大類庫，我們將仿真程序分為３個(gè)類：模型類、主體類和圖形類。模型類負(fù)責(zé)控制模型的創(chuàng)建和運(yùn)行，主體類描述主體的行為，而圖形類則主要負(fù)責(zé)以圖形方式輸出仿真過程中的相關(guān)結(jié)果。我們建立其Repast 模型。具體思路如下：

現(xiàn)在有一群參與者（256人），參與者類型type有4種。在模型運(yùn)行過程中，參與者類型是變化的。現(xiàn)設(shè)定50個(gè)全局回合（即模型中的step方法執(zhí)行50次）。每個(gè)全局回合中，執(zhí)行如下任務(wù)：

（1）每個(gè)全局回合開始時(shí)，將列表中的參與者部分屬性重置。如博弈次數(shù)累計(jì)、收益累計(jì)，它們的初始值為0。并且，將博弈對(duì)象列表（也就是博弈鄰居）清空。

（2）每個(gè)全局回合中進(jìn)行一次相互作用，每個(gè)參與者都與隨機(jī)的一組鄰居（本例中是4人）進(jìn)行若干次重復(fù)博弈。在每一次兩兩博弈中，雙方均將對(duì)手加入博弈鄰居列表中，并將自己的收益進(jìn)行累加。

（3）每個(gè)全局回合結(jié)束后，每個(gè)參與者進(jìn)行類型適應(yīng)性改變。首先，所有參與者計(jì)算出自身的適應(yīng)類型。計(jì)算依據(jù)是，對(duì)某參與者的博弈鄰居列表中的每個(gè)主體在其若干次博弈中平均收益進(jìn)行比較。博弈鄰居列表中收益最大者的類型就是該參與者的新類型。然后，再據(jù)此對(duì)該參與者的類型進(jìn)行更新。這樣，所有參與者都依據(jù)此原理進(jìn)行類型更新。

（4）輸出相關(guān)結(jié)果。這里，輸出的是每一全局回合后各種類型的人數(shù)。

在模型類的模型的step（在這里，一個(gè)step步進(jìn)就是一個(gè)全局回合）方法代碼中，可以看到模型執(zhí)行的上述思路。

限于篇幅，我們不再對(duì)模型的代碼編制過程進(jìn)行詳細(xì)描述和分析。主要分析的是模型的運(yùn)行結(jié)果，以及模型中相關(guān)參數(shù)的變化對(duì)運(yùn)行結(jié)果的影響。

3.3仿真程序的運(yùn)行

模型運(yùn)行后，我們就可以看到動(dòng)態(tài)的演化效果。如果主體總數(shù)為256，４種類型的主體數(shù)平均分配，適應(yīng)系數(shù)為0.2。當(dāng)博弈回合數(shù)為50時(shí)，演化結(jié)果如圖１所示。

如果修正模型的相關(guān)參數(shù)，我們就可得到不同的演化結(jié)果。在下面，將對(duì)不同參數(shù)下的仿真結(jié)果進(jìn)行詳細(xì)分析。

4仿真結(jié)果分析

通過上述模型參數(shù)的修改，我們可以發(fā)現(xiàn)一定的運(yùn)行規(guī)律。現(xiàn)分析如下：

（1）如果初始戰(zhàn)略組合各占1/4，當(dāng)兩個(gè)參與者一次博弈時(shí)的回合數(shù)為 4時(shí)，隨機(jī)的兩個(gè)參與者的博弈行為是一種短期行為，這個(gè)演化模型將很快全部采取ALLD （總是不合作）的策略。通過調(diào)整4種類型的比例，我們發(fā)現(xiàn)只要存在ALLD類型，哪怕是很小的比例，也會(huì)導(dǎo)致可怕的結(jié)果。這一點(diǎn)也說明了這樣一個(gè)事實(shí)，在市場中，如果不合作者能夠賺取較多的利益，那么他有可能影響到整個(gè)市場。當(dāng)一次博弈時(shí)的回合數(shù)為10或更大時(shí)，每一次博弈的兩個(gè)參與者取得的就不是一種短期效益了。此時(shí)，TFT（針鋒相對(duì)的戰(zhàn)略）將是一種較優(yōu)策略。參與者觀察到這種優(yōu)勢，因此，最終所有的參與者將演化成TFT。我們從中不難體會(huì)到“近墨者黑，近朱者赤”的哲學(xué)真諦。

（2）另外，第2，3兩種類型的首次選擇，可能也會(huì)給最終結(jié)果帶來直接影響。特別是持“針鋒相對(duì)”戰(zhàn)略者在一開始博弈時(shí)的首次選擇，也會(huì)給最終結(jié)果帶來重要影響。TFT戰(zhàn)略持有者，在一開始的博弈行動(dòng)實(shí)際上表明了他更傾向于哪一種行動(dòng)。他這種行為會(huì)直接影響其他參與者的后續(xù)戰(zhàn)略改變，引起連鎖反應(yīng)。因此，參與者須充分考慮首次行為對(duì)整個(gè)博弈鏈的影響，不能因眼前利益而影響長期利益。也就是說，一次所謂的“理性”博弈的有效性，可能會(huì)導(dǎo)致重復(fù)博弈的長期無效。

（3）此外，參與者的類型分布也是決定演化方向的關(guān)鍵因素。如果只有前兩種類型（比如，pALLC = 0.5，pTFT = 0.5，pATFT = 0.0，pALLD = 0.0），演化結(jié)果就不會(huì)出現(xiàn)后兩種類型。換句話講，在給定的環(huán)境中，如果本來就沒有某種類型，不管怎么演化，也不會(huì)生成這種類型。這個(gè)仿真結(jié)果也帶給我們非常重要的啟示。要防止系統(tǒng)的惡性演化，必須“防微杜漸”，只有徹底杜絕負(fù)面類型，才能完全遏制其負(fù)面影響。

（4）模型中的適應(yīng)系數(shù)pAdapt = 0.2，表示參與者改變類型的傾向程度。此系數(shù)一般較小，表示大多數(shù)參與者傾向于維持原有類型不變，這主要是由于人的“慣性力”所造成的。調(diào)整適應(yīng)系數(shù)的取值，可以改變博弈演化的進(jìn)程。正是因?yàn)檫@個(gè)原因，我們從中明白了這樣的事實(shí)，那就是為什么在開放的現(xiàn)代都市中，改革進(jìn)步的步伐要比落后閉塞的地區(qū)要快得多。

（5）還有，收益矩陣的改變，也是影響博弈結(jié)果的關(guān)鍵因素。對(duì)于規(guī)則制定者來講，應(yīng)充分考慮各種主體類型，制定有明顯指導(dǎo)意義的、體現(xiàn)系統(tǒng)主旋律的博弈規(guī)則。這樣，與系統(tǒng)主旋律背道而馳的主體類型，在博弈中就不可能獲取高于其他博弈者的效用。因此，這些與社會(huì)主旋律相違背的類型就不可能成為其他主體效仿的對(duì)象。同樣，那些在社會(huì)中應(yīng)倡導(dǎo)的主體類型，就應(yīng)該在一個(gè)具有激勵(lì)作用的博弈規(guī)則下，獲取高于一般主體的效用。因此，對(duì)于一個(gè)社會(huì)來講，法律、規(guī)章、道德公約都應(yīng)該有明確的“頌善抑惡”的指導(dǎo)思想?？梢赃@樣講，制度問題可能是博弈結(jié)果的核心決定因素。

（6）現(xiàn)在，我們?cè)賮砜紤]博弈鄰居的選擇規(guī)則給博弈結(jié)果帶來的影響。前面的模型，主體在兩兩博弈中，選擇的是“隨機(jī)”鄰居。將所有參與者放置于一個(gè)空間網(wǎng)格中。博弈時(shí)，參與者通過Repast類庫中空間類的getVonNeumannNeighbors方法獲取其馮-諾依曼(Von. Neumann)鄰域。這樣，參與者只與他們的諾依曼相鄰者發(fā)生博弈交互。這里的馮-諾依曼鄰域指的是一個(gè)主體的上、下、左、右4個(gè)相鄰主體。這種改變使得合作戰(zhàn)略在群體中具有更強(qiáng)的生存力。該模型的運(yùn)行結(jié)果說明，在大多數(shù)情況下，TFT比ALLD更加有利。這一仿真結(jié)果非常精確地解釋了這樣一個(gè)普遍存在的社會(huì)現(xiàn)象：當(dāng)博弈主體間的聯(lián)系比較固定時(shí)，博弈參與者更傾向于采取合作的戰(zhàn)略。而對(duì)于主體聯(lián)系的“隨機(jī)”性較強(qiáng)的博弈，參與者可能會(huì)存有較大的“機(jī)會(huì)主義”傾向，以期博取不合作所帶來的“一次性”利潤。

5小結(jié)

從簡單主體和簡易規(guī)則出發(fā)來研究系統(tǒng)的復(fù)雜性是CAS 理論研究的重要方法。而剛剛興起的Repast.NET則是對(duì)這種研究進(jìn)行計(jì)算機(jī)仿真的重要工具。相信，隨著多主體演化博弈理論的深化發(fā)展，也隨著微軟DOTNET技術(shù)的迅速普及，Repast.NET將會(huì)在這一領(lǐng)域扮演越來越重要的角色。同時(shí)，多主體演化博弈理論也會(huì)得以更快地發(fā)展。

主要參考文獻(xiàn)

［1］陳禹. 復(fù)雜性研究的新動(dòng)向——基于主體的建模方法及其啟迪［J］. 系統(tǒng)辯證學(xué)學(xué)報(bào)，2003（1）.43-50.

［2］ 姜昌華，韓偉，胡幼華. REPAST—— 一個(gè)多Agent仿真平臺(tái)[J]. 系統(tǒng)仿真學(xué)報(bào),2006（8）.2319-2322.

［3］ 童慧驊,屠文川. 一種基于CAS的代理主體行為仿真模型［J］. 計(jì)算機(jī)仿真,2006（9）:272-276.

［4］ Cohen, Riolo,and Axelrod. The Emergence of Social Organization in the Prisoners Dilemma［Ｒ］.SFI Working Paper, 1999.

［5］ 張江.基于Agent 的計(jì)算經(jīng)濟(jì)學(xué)建模方法及其關(guān)鍵技術(shù)研究［D］.北京：北京交通大學(xué)，2006.