第12講復(fù)雜網(wǎng)絡(luò)上的博弈演化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、模型囚徒困境模型 圖中給出了網(wǎng)絡(luò)拓?fù)潆S著個(gè)體調(diào)整鄰居關(guān)系而變化的過程. 從圖(a)可以看出，演化的網(wǎng)絡(luò)是異配的，即度大的節(jié)點(diǎn)傾向于與度小的節(jié)點(diǎn)相連.由于我們的拓?fù)湔{(diào)整規(guī)則是斷開重連到鄰居的鄰居，在拓?fù)湔{(diào)整中度大的節(jié)點(diǎn)易于一般的節(jié)點(diǎn)被其它節(jié)點(diǎn)搜索連接上，因此網(wǎng)絡(luò)呈現(xiàn)出異配性.同時(shí)，拓?fù)湔{(diào)整也造成了網(wǎng)絡(luò)的異質(zhì)性， 圖(b)顯示了網(wǎng)絡(luò)度的方差變化情況.可以看出，隨著網(wǎng)絡(luò)的演化，網(wǎng)絡(luò)變得越來越異質(zhì)，而異質(zhì)性是利于合作產(chǎn)生的.因此在拓?fù)浜筒┺墓餐饔孟拢献魉綍?huì)慢慢增強(qiáng)，如圖(c)所示. 圖(d)給出了網(wǎng)絡(luò)中C一C/C一D/D一D邊的比例變化情況.C一C邊數(shù)不斷增多，而C一D和D一D邊最終受到抑制而消失.這說明拓?fù)湔{(diào)整加強(qiáng)了合作者和合作者之間的同配連接，削弱了C一D和D一D之間的連接，從而使得整個(gè)網(wǎng)絡(luò)向有利于合作者的方向進(jìn)行演化，最終使得合作者占上風(fēng).上圖給出了對(duì)應(yīng)于不同b時(shí)，合作者的比例隨著調(diào)整拓?fù)浯螖?shù)m的變化結(jié)果. 可以發(fā)現(xiàn)，在保持平均度、博弈輪數(shù)不變的情況下，對(duì)于固定的b，存在調(diào)整拓?fù)浯螖?shù)的臨界值mc，當(dāng)mmc時(shí)，合作者的比例將會(huì)演化到100%.同時(shí)，圖中的插圖給出了固定其它參數(shù)時(shí)mc隨著b的變化情形. 即隨著作弊收益b