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

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

［關鍵詞］ 博弈論；多主體仿真；Repast；演化

doi:10.3969/j.issn.1673-0194.2009.10.035

［中圖分類號］F224.32; N945.13［文獻標識碼］A［文章編號］1673-0194（2009）10-0105-03

1Repast與多主體仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）擁有Repast的類庫文件。這個條件容易實現(xiàn)，可在目標機上安裝Repast，或者在建模時將模型中用到的Repast類庫文件自動復制到模型所在目錄。

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

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

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

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

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

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

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

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

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

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

3.2 仿真程序建立

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

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

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

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

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

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

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

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

3.3仿真程序的運行

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

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

4仿真結果分析

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

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

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

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

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

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

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

5小結

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

主要參考文獻

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

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

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

［4］ Cohen， Riolo，and Axelrod. The Emergence of Social Organization in the Prisoner’s Dilemma［Ｒ］.SFI Working Paper， 1999.

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