第12講復雜網絡上的博弈演化

1、1、博弈2、復雜網絡上的演化博弈 2.1、網絡演化博弈的策略更新規(guī)則 2.2、網絡拓撲對合作的影響 2.3、記憶對網絡博弈中的影響 2.4、博弈動力學與網絡拓撲共演化 2.5、學習機制導致合作的涌現3、展望 博弈研究的對象是游戲(Game)，更確切的說，是指在具有雙方相互競爭對立的環(huán)境條件下，參與者依靠所掌握的信息，在一定的規(guī)則約束下，各自選擇策略并取得相應結果(或收益)的過程。博弈論就是使用數學模型研究沖突對抗條件下最優(yōu)決策問題的理論。 博弈論被認為是研究自然和人類社會中普遍存在的合作行為最為有力的手段。一、博弈論一、博弈論 博弈模型反映了自私的個體之間的合作競爭關系，能夠很好地刻畫生物系統

2、中生物體之間的相互作用關系及演化動力學。 不論在自然或是社會系統中，經典博弈論告訴我們自私個體博弈的結果必然是背叛。顯然是一個和實際情況不完全吻合結論。社會經濟活動中的絕大多數任務不可能由單人完成，需要群體的分工和合作。 問題問題: 為什么自私的個體組成的群體會產生合作行為，存在什么樣的機制，以及什么樣的條件才會有合作行為涌現？通常博弈由以下通常博弈由以下4個部分所組成個部分所組成:(l)博弈個體：在一個博弈中至少有兩位決策者(agent)參與博弈.(2)策略集：個體的博弈策略可以是純策略，也可以是混合策略博弈的策略集由參與博弈的個體所有可能采用的策略所組成.(3)收益矩陣：當博弈個體選定好自

3、己的策略后，其所獲取的收益由收益矩陣中的相應元素來確定.(4)策略演化: 在多輪博弈過程中，博弈個體遵循自身收益最大化的最終目標，即以此目標為指導原則來進行策略調整。納什均衡真實生活中的博弈問題是很復雜的，可能會有很多的參與者，每個參與者都有不同的策略。當參與者們在進行一項博弈的時候，他們應該選擇什么樣的策略?是否有辦法預言出他們的策略組合(s1，s2，sN)?納什(Nash)均衡：其核心思想是對于兩人或多人博弈，個體的策略演化會趨向于一個均衡態(tài)，在此均衡態(tài)下所有的個體會同時采取“納什均衡策略”。Nash認為，博弈問題的解應該是這樣的一組策略，在這組策略中，每一個參與者都無法通過單獨改變自己的

4、策略而獲得更多的收益。這樣的狀態(tài)就被稱作納什均衡態(tài).實際上納什均衡態(tài)對所有的參與者來說，不一定是最好的結局。實際上納什均衡態(tài)對所有的參與者來說，不一定是最好的結局。下面以囚徒困境博弈和雪堆博弈為例來闡述納什均衡經典博弈模型經典博弈模型囚徒困境博弈囚徒困境博弈: 兩個小偷A和B合伙作案，被捕后被隔離審訊.如果雙方都拒絕坦白同伴的罪行，兩人將會被輕判1年徒刑;為此，警方設計了一個機制:如果A揭發(fā)B的罪行，B拒不供認A的罪行，則A將無罪釋放，而B將被重判5年徒刑;如果A、B都揭發(fā)對方罪行，則雙方均被判刑3年. 在此情況下，自私的個體應如何做出抉擇?合作(Cooperate-C) or 背叛(defe

5、ct一D)不論對手采取哪種策略，選擇背叛策略都是最佳的，即理性的個體最終會處于相互背叛的狀態(tài)(注意到此時的集體收益低于兩人同時選擇合作時的情況). 這種相互背叛的狀態(tài)(D，D)就是系統的納什均衡態(tài)。對于兩人博弈，收益矩陣元通常用(R、S、T、P)來表示相互合作則二人同獲得較大收益R，相互背叛則同獲較小收益P，一方合作一方背叛，則背叛者獲得最高收益T，而合作者獲得最低收益S，即參數滿足關系:TR P S，此外2RT+S，即相互合作能獲得集體最高收益相互合作能獲得集體最高收益. 在一個風雪交加的夜晚，兩人開車相向而行，被一個雪堆所阻，如圖所示.白色和灰色分別表示合作策略與背叛策略.與囚徒困境博弈不

6、同，對于雪堆博弈，收益矩陣元滿足關系: TR S P 雪堆博弈雪堆博弈假設鏟除這個雪堆使道路通暢需要付出的勞動量為c，道路通暢則帶給每個人的好處量化為b(c)。 如果兩人一齊動手鏟雪，則他們的收益為R=b一c/2(分別承擔勞動量c/2);如果只有一人下車鏟雪，雖然兩人都能及時回家，但是背叛者逃避了勞動，它的收益為T=b，而合作者的收益為S=b一c;如果兩人都選擇不合作，則兩人都無法及時回家，其收益量化為P=0.雪堆模型的收益矩陣可表示為:那么，理性個體的最優(yōu)選擇是什么呢? 如果對方選擇背叛策略(呆在車中)，那么另一方的最佳策略是下車鏟雪(因為按時回家的利益b一c好于呆在車中的背叛收益0); 反

7、之，如果對方下車鏟雪，則自己的最佳策略是呆在舒服的車中.所以，不同于囚徒困境博弈，在雪堆博弈中存在兩個納什均衡態(tài)：(C，D)和(D，C).即雪堆博弈中的NE為兩人均以概率r選擇背叛，概率1-r選擇合作，其r=c/(2b-c)稱為損益比。 雪堆模型與囚徒困境不同：雪堆模型與囚徒困境不同：遇到背叛者時合作者的收益高于雙方相互背叛的收益.因此,一個人的最佳策略取決于對手的策略： 如果對手選擇合作， 他的最佳策略是背叛； 反過來， 如果對手選背叛， 那么他的最佳策略是合作。 這樣合作在系統中不會消亡， 而與囚徒困境相比， 合作更容易在雪堆博弈中涌現。 演化博弈論演化博弈論 傳統博弈論中，常常假定參與人

8、是完全理性的，且參與人在完全信息條件下進行。而演化博弈理論并不要求參與人是完全理性的，也不要求完全信息的條件。 演化博弈論是把博弈理論分析和動態(tài)演化過程分析結合起來的一種理論。根據演化博弈理論，博弈雙方的策略最終收斂到演化穩(wěn)定策略（evolutionarily stablestragegy，ESS）上。1. 1. 演化網絡博弈基本定義演化網絡博弈基本定義 要討論合作的涌現，必須涉及相當數量的個體（局中人），而且合理地認為這些局中人以及他們之間的關系構成一個復雜網絡，隨著時間的演化，每個局中人都在和他的鄰居進行博弈，這就稱為演化網絡博弈，它的定義可以表述為：（1）數量N的局中人位于一個復雜網絡上

9、。（2）每個時間演化步，按一定法則選取的一部分局中人以一定頻率匹配進行博弈。 （3）局中人采取的對策可以按一定法則更新，所有局中人的策略更新法則相同。這種法則稱為“策略的策略”。然而，法則更新比博弈頻率慢得多，使得局中人可以根據上一次更新對策成功與否選擇、調整下一次的更新。 （4）局中人可以感知環(huán)境、吸取信息，然后根據自己的經驗和信念，在策略更新法則下更新策略。 （5）策略更新法則可能受到局中人所在網絡拓撲結構的影響。2 2 演化網絡博弈研究內容演化網絡博弈研究內容第一，研究網絡拓撲結構對博弈演化動力學的影響。第二，探索一些可能的支持合作行為涌現的動力學機制。第三，研究博弈動力學和網絡拓撲結構

10、的共演化，即個體策略和網絡拓撲結構協同演化的情形。3. 促進合作行為涌現的機制 重復博弈（爭鋒相對、冷酷策略）、巴普洛夫策略、親緣選擇、直接互惠、間接互惠（聲譽）、網絡互惠以及群選擇。 公共利益博弈（復雜網絡基礎 P306） 演化穩(wěn)定策略的提出最初是為了精煉納什均衡 ,通過借助生物界進化論中優(yōu)勝劣汰的思想 ,丟棄參與者完全理性的假設 ,認為均衡是有限理性的個體隨時間的推移尋求優(yōu)化這一目標的長期結果。 因此 ,演化穩(wěn)定策略具有魯棒性演化穩(wěn)定策略具有魯棒性 ,可以抑可以抑制噪聲制噪聲 ,它是納什均衡的精煉。它是納什均衡的精煉。 演化博弈論著重研究著重研究是在一個動態(tài)過程中有限理性的個體如何在重復博

11、弈過程中，通過自適應學習來實現自身收益最大化的問題。它把均衡看作是過程調整的結果。它把均衡看作是過程調整的結果。 演化穩(wěn)定策略演化穩(wěn)定策略必須滿足的條件：如果幾乎所有的個體都采取該策略，那么該策略的個體適應度要比任何可能的變異策略要大。 經典博弈論到演化博弈論的3個關鍵概念的內涵式改變（演化博弈論與經典博弈論的區(qū)別）： （1）策略內涵的不同：不同行為 到生物系統中的不同類型物種本身，策略由物種的不同表現型來體現；（2）均衡意義的不同：納什均衡到演化穩(wěn)定策略(ESS)；（3）個體個體互相作用方式的不同（博弈個體與博弈次數）二、復雜網絡上的演化博弈二、復雜網絡上的演化博弈 復雜網絡理論為描述博弈個

12、體之間的博弈關系提供了方便的系統框架. 網絡上的節(jié)點表示博弈個體 ,邊代表與其鄰居的博弈關系.在每一時間步長 ,節(jié)點與其所有鄰居進行博弈 ,累積博弈獲得的收益 ,然后根據更新規(guī)則進行策略更新 ,如此這樣重復迭代下去. 在傳統的演化博弈理論中通常假設個體間以均勻混合的方式交互，即所有個體全部相互接觸，然而，現實情況中個體間的接觸總是有限的，個體僅與周圍的少數其他個體接觸.這樣我們就可以在博弈理論中引入網絡拓撲的概念。 網絡上的演化博弈研究主要集中于網絡上的演化博弈研究主要集中于3個基本的方向個基本的方向:(l)研究網絡拓撲結構對博弈動力學演化結果的影響;(2) 一定的網絡結構下，探討各種演化規(guī)則

13、對演化結果的影響;(3)網絡拓撲和博弈動力學的共演化，主要是自 適應網絡上博弈動力學 ,即網絡拓撲調整受博弈動力學影響. 每一個模型都可以分成幾個模塊，如使用的博弈模型、更新規(guī)則、網絡結構等。 (l)網絡中所有的參與者與其網絡上的鄰居進行博弈，并獲得收益。每個參與者的收益為與其所有鄰居發(fā)生博弈得到收益的總和。 (2)然后參與者將他的收益與他在網絡上鄰居的收益進行比較，按照一定規(guī)則改變自己的策略。 雖然使用的博弈模型和具體的模擬細節(jié)各不相同，但基本的模擬過程是類似的，這個模擬過程是分回合進行的，每個回合包含兩步:2.1網絡演化博弈的策略更新規(guī)則：網絡演化博弈的策略更新規(guī)則： (l)模仿最優(yōu)者：即

14、在每輪博弈過后，個體采取其鄰居中獲得最高收益的個體的策略進行下一輪博弈。 (2)模仿優(yōu)勝者：即個體在策略更新時，同時參考那些收益比自身高的鄰居的策略，以正比于他們所得收益的概率進行策略轉變。 以上兩種規(guī)則可以統稱為模仿策略. 模仿策略的模仿策略的基本思想是個體的更新策略，根據鄰居中收益最高的個體策略進行模仿，以期獲得更高的收益。每個節(jié)點(對應博弈者假設為P1)隨機的選取他的一個鄰居節(jié)點(對應博弈者假設為P2)，P1以一定概率W模仿P2的策略，常用的演化規(guī)則（統計力學的費米函數）如下：其中，Ui表示Pi的累積收益，參數0為噪音，代表了一種非理性行為的可能，一般是一個很小的值，常取0.1。當時，表

15、示所有的信息都被噪音淹沒，策略進行完全隨機的更新；當0時，表示確定的模仿規(guī)則，即當P2的累積收益高于P1時，P1則采取P2的策略。 (3)配對比較：即個體隨機選擇某一鄰居進行收益的比較，以某個概率(為此兩個體收益差的函數)轉變?yōu)閷Ψ降牟呗?其中，kmax為P1與P2中較大度節(jié)點的度，P,T,S,R為22收益矩陣元素。另一類演化規(guī)則 (4)隨機過程方法：通?？紤]Moran過程(birth一death) (或者death一birth過程) ， 即在策略更新時，以正比于個體適應度(由收益來衡量)的概率產生一個新的個體，然后隨機取代此個體的某個鄰居。 Moran過程是將Darwin的進化思想直接引入到

16、演化博弈中。一個實際背景是種群中的變異入侵，以下圖為例，種群中所有個體“C”，當某個個體發(fā)生變異后，變?yōu)椤盌”，以后每一步考慮隨機移去一個個體，并以正比于原種群中“C”個體適應度的概率生成一個新的“C”個體，否則生成一個新的“D”個體。在適應度函數滿足一定條件時，“D”個體可能完全侵占整個種群(Invade)， Martin A.Nowak等人研究了這類種群侵占問題，將某種策略從種群中僅存在一個變異個體時，最終能侵占整個種群的概率定義為策略的扎根概率扎根概率。當入侵策略的適應度為原策略的r倍時，則扎根概率：扎根概率：其中N為種群個體數量。死生過程是Moran過程的一個自然推廣，原始網絡中存在合

17、作“C”、背叛“D”兩種策略，按照連邊關系個體之間進行博弈，獲得一個累計收益，其中b表示合作收益，即遇到對手采取合作時獲得收益；c表示合作代價，即個體采取合作獲得負收益。隨機選擇選擇一個個體死亡(假設為位于中間位置的“D”節(jié)點)，則其所有的鄰居按照正比于個體適應度的概率產生一個后代，填補個體死亡后留下的空位。重復這一過程，種群中的策略將達到動態(tài)平衡。 探索由自私個體組成的群體中合作行為產生的機理是演化博弈研究關注的核心問題之一。 2.2 網絡拓撲對合作的影響網絡拓撲對合作的影響 當個體均勻混合，即個體間的接觸網絡為全連通圖時，相互背叛是唯一的穩(wěn)定態(tài)，合作無法出現，那么改變網絡結構能否導致合作行

18、為的出現呢? 一個影響深遠的工作是Nowak和May在1992年所做的“空間博弈”研究。（1）規(guī)則網絡上的博弈）規(guī)則網絡上的博弈 Nowak和May擴展了囚徒困境博弈模型，將參與博弈的個體置于二維格子上，每個個體與直接相鄰的4個鄰居進行博弈，并累計收益，然后在更新策略時，一個個體與它的鄰居比較本輪的收益，取收益最高者得策略作為下一輪博弈的策略，直到網絡進入穩(wěn)定狀態(tài)為止。規(guī)則網絡規(guī)則網絡囚徒困境模型：囚徒困境模型： 為了便于理論分析, Nowak采用了弱囚徒困境博弈，即令T = b 1, R = 1, P = S = 0。Nowak指出這種弱化囚徒困境所得的演化結果與-1S Py，下一輪博弈中，

19、x保持自己的策略不變，反之以概率 ： 采取y的策略。 其中，kmax是x，y兩節(jié)點中的最大度。 基于此得到更一般的結果：異質因素促進合作的涌現。異質因素促進合作的涌現。 1、小世界網絡中通過移邊產生的異質性使其比規(guī)則格子更利于合作的涌現； 2、具有度異質特征的WS小世界網絡與度均勻分布的小世界網絡比較，由于節(jié)點度變得異質導致了前者得合作頻率比后者高，而后者合作頻率的變化主要由長程邊使網絡中聚類系數的變化引起的。小世界網絡小世界網絡雪堆博弈雪堆博弈 Tomassini等應用不同的演化規(guī)則作用在不同的重連概率的小世界網絡上，細致地分析了小世界網絡上的鷹鴿博弈。發(fā)現小世界網絡的合作行為與博弈采用演化

20、規(guī)則，收益比以及小世界網絡的重連概率息息相關。三者的交互作用使得空間結構時而促進合作的涌現，時而抑制合作的產生。 尚麗輝等針對現實生活中朋友關系網絡的距離相關特性，研究了基于距離的空間小世界網絡上的雪堆博弈，發(fā)現與規(guī)則網絡相比，距離無關的小世界網絡促進了合作的涌現；而距離相關的小世界網絡中，冪指數增加導致了長程連接的減少和短程連接的增加，這使網絡在損益比較大時抑制合作的產生。不同冪律指數下距離相關的小世界網絡上的雪堆博弈合作曲線不同冪律指數下距離相關的小世界網絡上的雪堆博弈合作曲線（3）無標度網絡上的博弈）無標度網絡上的博弈無標度網絡無標度網絡囚徒困境囚徒困境 實際生活中很多網絡諸如因特網、航

21、空網等都具有無標度的特性，其節(jié)點的度分布滿足某種冪律的特性。 Santos對比了規(guī)則格子、隨機圖、隨機無標度網絡和BA無標度網絡對合作涌現的作用（下圖），認為由于無標度網絡中節(jié)點之間的度存在極大地差異，合作行為容易在大度節(jié)點之間的傳播，進而帶動了大量小度節(jié)點在無標度網絡中傳播，也就是說，無標度網絡是目前最有利于合作涌現的網絡結構。 Gomez-Gardenes根據個體的穩(wěn)定時的狀態(tài)，將其劃分為3類：純策略者、純背叛者和策略搖擺者。 Santos將研究無標度網絡上囚徒困境的方法移植到雪堆博弈上，觀察到類似于上圖的現象，這說明無標度特性同樣有利于雪堆博弈中合作的涌現。 通過對小規(guī)模網絡（128個節(jié)

22、點）進行仿真，弱化了影響合作涌現的無標度網絡其他統計學特性，著重突出了節(jié)點度的異質性的因素。再次驗證了關于異質因素促進合作涌現關于異質因素促進合作涌現的一般性結論。的一般性結論。,指出無標度網絡為研究演化博弈理論提供了統一的理論框架。無標度網絡無標度網絡雪堆博弈雪堆博弈 榮智海等研究了無標度網絡上的擴展雪堆博弈(即一種可從雪堆博弈連續(xù)變化到囚徒困境的博弈 ),發(fā)現無標度網絡異質性異質性的增加使得合作的穩(wěn)定性增強。 而且對于相同的純合作比例 ,純背叛者比例增加 ,策略搖擺者比例減少。 這說明越異質的網絡 ,個體越傾向于選擇穩(wěn)定策略.度相關性對兩類博弈的影響度相關性對兩類博弈的影響 Rong等首先

23、研究了無標度網絡的度一度相關性對合作行為的影響.研究表明 :在囚徒困境中 ,中性網絡 (即呈現度不相關特性的網絡 ,例如 BA網絡 )的中心節(jié)點對于大度鄰居與小度鄰居的選擇是最合理的 ,既與少量中心節(jié)點相連 ,又與他們共享很少量的鄰居。所以其較之同配或異配網絡的合作頻率更高 ,最利于合作的涌現。 當無標度的網絡結構呈現同配性質，即連接度大的節(jié)點傾向于和連接度大的節(jié)點建立連接時，由于中心節(jié)點和邊遠節(jié)點(連接度一般較小)的“通訊渠道”的減少，使得中心節(jié)點的合作策略難以傳播出去,網絡總體的合作頻率呈現下降的趨勢。 反之 ,如果無標度網絡呈現度異配性度異配性時 ,中心節(jié)點之間的聯系被切斷 ,一方面不利

24、于合作策略在中心節(jié)點之間擴散 ,抑制合作頻率的上升 ;另一方面被孤立的中心節(jié)點可以和周圍小度節(jié)點凝結成堅固的簇 ,即使背叛的誘惑非常大時也能有效抵御背叛策略的入侵。 對于雪堆博弈 ,越同配的網絡其背叛者擁有越小的平均度 ,這說明與囚徒困境博弈類似 ,由于網絡變得同配后中心節(jié)點對于小度節(jié)點的控制能力減弱 ,進行雪堆博弈的背叛者也主要集中在小度節(jié)點 。 異配網絡當 r較小時 ,雪堆博弈的合作頻率會低于均勻混合狀態(tài)的均衡頻率。 可見 ,度相關性對于度相關性對于囚徒困境博弈的結論完全適用于雪堆博弈囚徒困境博弈的結論完全適用于雪堆博弈.兩圖的橫坐標為背叛相對于合作的收益 b, 縱坐標為合作頻率 ,rk

25、為度相關性系數。2.3、記憶對網絡博弈中的影響、記憶對網絡博弈中的影響 在復雜網絡博弈演化模型中，參與者在模仿周圍鄰居收益的時候，一般都假設參與者，也就是說在模型中并不考慮記憶效應.而在現實生活中，人們的收益并不對時間進行累加是不可能不參考以往的經驗的，關于這些經驗的記憶也不會迅速遺忘.尤其是在人們選擇改變的時候，往往會更加謹慎的考慮這些經驗，歷史記憶的效應經常會扮演一種重要的角色。 考慮到了人的有限記憶的特性，也就是人不可能記錄以前發(fā)生的所有事情的信息，那么就需要記錄最有用的信息。另一方面，人只能記錄有限的時間段內所發(fā)生的事情，所以我們假設每個個體的記憶長度有限，長度為M，即為從上一時刻到M

26、時刻以前的歷史最佳策略.然后每個個體根據自身的歷史記憶進行決策.為了簡單起見，我們采用多數者規(guī)則，即采用C或D策略的概率正比于C和D在記憶中的數量:其中Nc和ND分別是C和D的數量.然后所有個體更新記憶。重復以上步驟，系統就會演化下去. Wang Wenxu等人考慮了一種基于記憶機制的空間雪堆博弈，并考察了記憶效應對有四個或者八個鄰居的二維周期性格子網絡和無標度網絡中的雪堆模型的作用.考慮個體根據過去的博弈結果的記憶，選擇最佳策略，記錄當前博弈結果并更新記憶庫。模擬的結果表明在不同的收益函數參數r下，記憶能力對網絡中合作態(tài)密度的影響是不同的.(i)合作頻率fc具有分段結構，分段個數對應節(jié)點的配

27、位數;(ii)圖像對于坐標點(0.5，0.5)呈180度旋轉對稱;(iii)記憶長度M并不影響分段點c的值，但是對不同段fc有很大影響;(iv)對于很大的收益參數r，系統仍然表現出較高的合作水平，這與Hauert等人得到的結果有很大不同.這表明即使自私的個體為了使自身利益最大化而做出決策，合作在欺騙者受益很高的情況下仍然能夠產生和持久。二維網格上的博弈行為二維網格上的博弈行為在在M=1的時候，系統中的合作行為表現出了大的震蕩，如左圖的插圖所示的時候，系統中的合作行為表現出了大的震蕩，如左圖的插圖所示4鄰居和8鄰居二維網格上合作水平與博弈模型參數的函數關系.插圖中為合作水平與歷史記憶長度的相關性

28、以及在歷史長度為1時的演化行為無標度網絡上的博弈行無標度網絡上的博弈行為為(i)與規(guī)則格子非常不同的是，fc是r的非單調函數，并存在一個最優(yōu)值.這個有趣的現象說明適當鼓勵自私的行為反而能夠更好地促進合作;(ii)與規(guī)則格子上的情況相同，fc曲線的連續(xù)性被一些突然的增加打斷。連續(xù)段的數目對應于平均度;(iii)兩幅圖都以坐標點(0.5，0.5)為180度旋轉對稱;(iv)記憶長度M不影響不連續(xù)點r的值，而只影響介的值。我們進一步細致研究了M如何影響fc。我們發(fā)現存在一段特殊的區(qū)域，在這段區(qū)域M對fc起不同的作用.當當M=1時，系統同樣存在大震蕩時，系統同樣存在大震蕩無標度網絡上的合作行為與博弈參

29、數的函數關系，在交叉點處合作水平與記憶長度的關系以及不同策略個體所占據的節(jié)點平均度和博弈參數的關系 模擬表明 ，基于記憶的空間雪堆博弈中隨著損益比的增加，合作頻率呈現階梯狀下降，并給出了突變點處的損益比與規(guī)則網格中節(jié)點鄰居數量的關系；而合作頻率與記憶長度之間則存在比較復雜的關系，通常來說，記憶長度的增加有利于合作頻率的提高，而嘗過一定長度后，記憶對合作的影響逐漸減弱，甚至不利于提高合作頻率.2.4、博弈動力學與網絡拓撲共演化、博弈動力學與網絡拓撲共演化 大多數復雜網絡上的演化博弈研究都是基于靜態(tài)網絡的，即網絡拓撲從博弈一開始就固定不變了.而實際上真實網絡是動態(tài)演化的，因此所考慮的靜態(tài)網絡只相當

30、于真實網絡的一張快照。 復雜系統最本質的特點就是反饋，并利用反饋信息實現自適應和自組織.真實社會中的博弈不但會受到社會人際關系結構的影響，而且反過來也可以影響社會關系結構。換句話說，一方面網絡的拓撲結構對其上的動力學過程會產生影響，另一方面這種影響又會反過來“塑造”網絡結構本身,調整網絡拓撲（或社會關系）。zimmermann等研究了動態(tài)網絡上演化博弈: 從一個隨機網絡開始，個體與鄰居進行囚徒困境博弈，個體按照模仿最優(yōu)者進行策略更新.在動力學的演化過程中，如果一個背叛者發(fā)現它模仿的背叛鄰居的收益比自己高，則這個不滿意的個體以概率p移走與被模仿的背叛者之間的作用邊，重新在網絡中隨機選擇一個節(jié)點連

31、接，這樣網絡中的邊數保持不變. 研究表明只需要一個小概率p(0.01)就可以使動態(tài)網絡中合作頻率達到一個高值，此時網絡呈現等級結構，而且隨著移邊概率p的增加，網絡的聚類系數增加，網絡異質性增強這是由于越來越多的背叛者因“失道”而寡助，合作者因“得道”可以成為中心節(jié)點.作者指出合作者占據中心節(jié)點具有很強的魯棒性:當網絡演化到穩(wěn)定狀態(tài)時強行把網絡中收益最高的合作者變?yōu)楸撑颜?，會使網絡合作頻率出現短暫震蕩，然而經過一段暫態(tài)過程后，網絡演化為一個新的等級網絡，合作者重新占據中心節(jié)點，動態(tài)網絡的合作水平與震蕩前相比沒有明顯變化. Pacheco等同樣研究了個體策略與網絡結構協同演化的網絡博弈模型.在他們

32、的模型中，結構演化和策略演化具有不同的時間尺度，分別記為Ta和Ts.當網絡結構演化時，采取不同策略的個體以相應的概率建立連接，通過這些連接進行博弈并獲取收益，策略演化則采取配對比較規(guī)則. 當網絡結構的演化速度遠遠慢于個體進行策略更新的速度時，此博弈模型等價于在靜態(tài)網絡結構上的博弈演化; 而當網絡結構演化速度遠遠快于個體策略更新速度時，上面的協同演化機制則導致博弈矩陣元的數值進行了不同標度的重整化.其直接的結果是矩陣元數值大小的排序關系發(fā)生改變，從而使得原先的博弈類型發(fā)生了本質性的轉變，所產生的博弈動力學相當于博弈個體在一個全連接圖上進行著另一種類型的博弈. 博弈類型轉變的直接結果是使得原先處于

33、弱勢的策略，例如囚徒困境博弈中的合作策略，有可能變成處于強勢的策略，從而有利于合作策略的涌現與維持. 考慮個體帶簡單記憶的網絡拓撲與博弈共同演化的簡單模型.初始網絡從規(guī)則隨機圖開始，每個節(jié)點與其所有鄰居連續(xù)進行囚徒困境博弈n輪，在每一輪，節(jié)點依據配對比較更新規(guī)則進行策略調整，同時記下鄰居作弊次數.博弈完n輪后，隨機選擇m個個體進行鄰居關系調整.被選中的個體將把連到作弊次數最多的鄰居的邊斷開，然后隨機重連到該鄰居的一個鄰居.參數n, m可以看成是博弈動力學和拓撲調整的時間尺度.在我們的模型中，策略更新采用同步方式，拓撲調整是異步的，因此，拓撲調整要比博弈動力學緩慢很多，這與現實是符合的.囚徒困境

34、模型囚徒困境模型 圖中給出了網絡拓撲隨著個體調整鄰居關系而變化的過程. 從圖(a)可以看出，演化的網絡是異配的，即度大的節(jié)點傾向于與度小的節(jié)點相連.由于我們的拓撲調整規(guī)則是斷開重連到鄰居的鄰居，在拓撲調整中度大的節(jié)點易于一般的節(jié)點被其它節(jié)點搜索連接上，因此網絡呈現出異配性.同時，拓撲調整也造成了網絡的異質性， 圖(b)顯示了網絡度的方差變化情況.可以看出，隨著網絡的演化，網絡變得越來越異質，而異質性是利于合作產生的.因此在拓撲和博弈共同作用下，合作水平會慢慢增強，如圖(c)所示. 圖(d)給出了網絡中C一C/C一D/D一D邊的比例變化情況.C一C邊數不斷增多，而C一D和D一D邊最終受到抑制而消失.這說明拓撲調整加強了合作者和合作者之間的同配連接，削弱了C一D和D一D之間的連接，從而使得整個網絡向有利于合作者的方向進行演化，最終使得合作者占上風.上圖給出了對應于不同b時，合作者的比例隨著調整拓撲次數m的變化結果. 可以發(fā)現，在保持平均度、博弈輪數不變的情況下，對于固定的b，存在調整拓撲次數的臨界值mc，當mmc時，合作者的比例將會演化到100%.同時，圖中的插圖給出了固定其它參數時mc隨著b的變化情形. 即隨著作弊收益b