進(jìn)化博弈論讀書(shū)心得

1、進(jìn)化博弈論讀書(shū)報(bào)告汪波1973年，梅拉德史密斯和普瑞斯將博弈論的思想引入到生物演化的分析中，二人提 出了進(jìn)化穩(wěn)定策略(ESS)，隨著1978年，Taylor和Jonker發(fā)現(xiàn)了進(jìn)化穩(wěn)定策略和復(fù)制 動(dòng)力學(xué)之間的關(guān)系，標(biāo)志著進(jìn)化博弈理論的誕生，因?yàn)榕c復(fù)制動(dòng)力學(xué)之間的關(guān)系，進(jìn)化穩(wěn) 定策略也因此成為進(jìn)化博弈理論最經(jīng)典的概念。1982年，梅拉德史密斯出版了演化與 博弈論，該書(shū)揭示動(dòng)物群體的行為變化的動(dòng)力學(xué)機(jī)制，也因此書(shū)他被稱(chēng)為進(jìn)化博弈論之 父，1995 年，Weibull 著作了Evolutionary Game Theory,2009 年初，Sandholm 出版 TPopulation Game a

2、nd Evolutionary Dynamics專(zhuān)著，這篇讀書(shū)報(bào)告是在看了這三 本著作的很少的一部分內(nèi)容之下，理解其中一些淺顯的內(nèi)容后完成的。一、進(jìn)化穩(wěn)定策略最初的模型進(jìn)化博弈理論是將博弈論引入到生物學(xué)背景下產(chǎn)生的，當(dāng)生物的特定表現(xiàn)型的適應(yīng)度依 賴(lài)于群體中的頻率分布時(shí)，進(jìn)化博弈論就是從這個(gè)角度來(lái)思考生物演化的問(wèn)題的一種方法， 古典博弈中，參與者根據(jù)自利的原則表現(xiàn)出理性行為，但在生物進(jìn)化的背景下是不合適的， 由此，理性原則被群體的動(dòng)態(tài)性和穩(wěn)定性取代，而自利原則則被達(dá)爾文的適應(yīng)度所取代。在 一些重要的假設(shè)下，將會(huì)得到博弈的一個(gè)新形式解：進(jìn)化穩(wěn)定策略。它是這樣一個(gè)策略，如 果整個(gè)群體的每個(gè)成員都采取

3、這個(gè)策略，那么在自然選擇的作用下，不存在一個(gè)具有突變特 征的策略能夠侵犯這個(gè)種群。最初的簡(jiǎn)化的模型由梅拉德史密斯和普瑞斯給出，他和普瑞斯也給出了進(jìn)化穩(wěn)定策略 的數(shù)學(xué)式的描述定義，這一模型的本質(zhì)特征是假設(shè)該群體有無(wú)限大的規(guī)模，繁衍以無(wú)性生殖 的方式進(jìn)行，競(jìng)爭(zhēng)只在兩個(gè)不存在任何差異的對(duì)手間展開(kāi)即是成對(duì)的競(jìng)爭(zhēng)。生物學(xué)中價(jià)值是 指兩個(gè)動(dòng)物為了爭(zhēng)奪資源而增加的或者減少的達(dá)爾文適應(yīng)度。故我們用適應(yīng)度作為最后個(gè)體 的收益的衡量，假想在這個(gè)無(wú)限的種群中，有兩個(gè)策略/、J，每一個(gè)成員都采取這兩個(gè)策 略之一，且策略的選擇是隨機(jī)的，在有競(jìng)爭(zhēng)前個(gè)體的初始適應(yīng)度為巧0，再假設(shè)整個(gè)群體中 選擇1的概率為p，w(I)、w(

4、J)分別表示選擇相應(yīng)策略帶來(lái)的適應(yīng)度，而E(L J)表示 個(gè)體選擇策略1而對(duì)手選擇J時(shí)的收益，其他E(I,I)等表示類(lèi)同的意義。若每一個(gè)個(gè)體都參與到競(jìng)爭(zhēng)當(dāng)中，則有w( I )=w0+(1-p) E (I, I) + pE (I, J)(1-1)w( J )=w0+(1-p) E (J, I) + pE (J, J)(1-2)穩(wěn)定的策略具有下列性質(zhì)：整個(gè)種群中幾乎所有的個(gè)體都采取了這個(gè)策略，且這些個(gè)體的 適應(yīng)度必將高于競(jìng)爭(zhēng)對(duì)手或者可能出現(xiàn)的突變異種的適應(yīng)度，否則競(jìng)爭(zhēng)對(duì)手或者產(chǎn)生的突變 異種會(huì)侵害整個(gè)種群，以致種群的削弱或者毀滅等，這時(shí)此策略便不可能是穩(wěn)定的策略。若 I是進(jìn)化穩(wěn)定策略，則w(I)

5、w( J)，且p = 1，所以當(dāng)I豐J，有E(I, I) E(J, I)(1-3)當(dāng) E(I, I) = E(J, I)時(shí)有 E(I, J) E(J, J)(1-4)滿(mǎn)足上述條件(1-3)、(1-4)的策略就稱(chēng)為進(jìn)化穩(wěn)定策略，而上述的兩個(gè)條件1-3、1-4也被 認(rèn)為是判別ESS的標(biāo)準(zhǔn)條件。上述的策略是在純策略情形下考慮的，當(dāng)策略I是從一個(gè)可能策略集合中隨機(jī)的選擇而構(gòu)成的，此時(shí)的策略稱(chēng)為混合策略。此時(shí)/若是一個(gè)混合進(jìn)化穩(wěn)定策略，假設(shè)*,s2,.,sk 等是該群體的純策略，賦予這些純策略非零的概率值，那么/必須滿(mǎn)足如下條件：E (s1) = E (s2) =. = E (七)二E (I, I)(1

6、-5)保證所有純策略的回報(bào)是相等的，群體中的個(gè)體才不會(huì)選擇偏離的策略。此時(shí)起滿(mǎn)足的條件 和上述是相同的形式。二、對(duì)稱(chēng)博弈1.對(duì)稱(chēng)博弈的定義兩人對(duì)稱(chēng)博弈對(duì)于許多進(jìn)化博弈論內(nèi)容而言是基礎(chǔ)的，而且，許多進(jìn)化博弈論中的深刻 見(jiàn)解都可以從二人對(duì)稱(chēng)博弈這種特殊情形中得到，這也是單獨(dú)列出對(duì)稱(chēng)博弈內(nèi)容的主要原因。一個(gè)二人對(duì)稱(chēng)博弈G = (I,S,u)，可假設(shè)有兩個(gè)玩家的位置，每個(gè)位置上有相同的純策略，而任意的策略的支付則依賴(lài)于玩家所選的位置，因此有如下的定義：博弈G = (I,S,u)稱(chēng)為二人對(duì)稱(chēng)博弈，如果I = 1,2，S = S1 = S2 = 1,2,n且對(duì) 于任意的(s , s ) e S有u (s

7、,s ) = u (s , s )成立。12112221為第二個(gè)人的支付矩陣e A, b該對(duì)稱(chēng)博弈要求兩個(gè)位置上的支付矩陣是互為轉(zhuǎn)置的，即若為第二個(gè)人的支付矩陣e A, baa.aaa.a11121n11212naa.aaa.a21222n則B =12221n.aa.aaa.aL n1n2nn1n2nnn即，=At也即有若a ij j例如：囚徒困境情形就是一個(gè)非常好的對(duì)稱(chēng)博弈的例子。上述是在純策略下的情形，現(xiàn)在描述混合策略情形：S = S1 = S2 = 1,2, , n，用 (氣,x,.,七)表示策略集上的一個(gè)概率分布，即為該博弈的一個(gè)混合策略，用表示其混 合策略集，則混合策略組合空間為 E

8、=?，此時(shí)任意的純策略i e S在對(duì)手選擇混合策略x eA 時(shí)的支付為u(ei,x) = ei - Ax = (Ax).。2.對(duì)稱(chēng)博弈的特點(diǎn)對(duì)稱(chēng)博弈是一種很特殊情形，它有自己的特征，一是對(duì)稱(chēng)博弈的最優(yōu)回應(yīng)對(duì)應(yīng)P *和通 常的最優(yōu)回應(yīng)對(duì)應(yīng)階一樣，通常的俠是策略組合空間到策略組合空間之間的映射，而6* 是策略集到策略集之間的映射，即6 *(y) = x eA : u(x, y) u(z, y), Vz eA(1-6)這是對(duì)稱(chēng)博弈策略集相同所決定的。二是對(duì)稱(chēng)博弈有更特殊的形式：雙對(duì)稱(chēng)博弈。此時(shí)在其 他條件滿(mǎn)足下當(dāng)且僅當(dāng)B = A時(shí)稱(chēng)為雙對(duì)稱(chēng)博弈。例如：協(xié)調(diào)博弈就是一個(gè)很好的雙對(duì)稱(chēng)博弈的例子。三是對(duì)稱(chēng)

9、博弈的納什均衡的形式也有所不同，對(duì)稱(chēng)博弈具有不對(duì)稱(chēng)的納什均衡，也具有 對(duì)稱(chēng)的納什均衡。策略組合(x, y) eA2被稱(chēng)為對(duì)稱(chēng)博弈的納什均衡，當(dāng)且僅當(dāng)尤ep *( y), y ep ，其中：AA ,這與通常的納什均衡的定義是一致的，用。海表 示納什均衡集合。當(dāng)x = y時(shí)我們稱(chēng)該納什均衡為對(duì)稱(chēng)的，此時(shí)納什均衡可以表示為Ane = x e A: (x, x) e。 NE (1-7)對(duì)稱(chēng)的情形下，它本質(zhì)是一個(gè)策略空間，不同于往常的策略組合空間，當(dāng)然，對(duì)稱(chēng)博弈的納 什均衡并非都要求是對(duì)稱(chēng)的，但也可以證明任意的對(duì)稱(chēng)博弈一定能夠存在至少一個(gè)對(duì)稱(chēng)的納 什均衡，即對(duì)于任意的二人有限對(duì)稱(chēng)博弈，ANE。例如：鷹-

10、鴿博弈、石頭-剪刀-布等博弈都是具有混合策略均衡的且是對(duì)稱(chēng)的。以鷹鴿博弈為例：不是一般地，下面支付矩陣為一方甲的支付矩陣：(v (v - c)/2v0v/2_B = AT其中v表示一定價(jià)值的資源適應(yīng)度，在此表示獲得的支付，雙方甲、乙都選擇鷹策略則各自 獲得(v-c).，2，c表示雙方爭(zhēng)斗產(chǎn)生的適應(yīng)度的下降或者說(shuō)是損失，若甲選擇鷹策略乙選 擇鴿策略，則甲獲得全部資源v而乙獲得0，若都選鴿策略則平分資源。當(dāng)v c時(shí)，則鷹 策略是納什均衡，因?yàn)榇藭r(shí)雙方都寧愿冒著受傷的風(fēng)險(xiǎn)獲得大于零的資源適應(yīng)度，而當(dāng)v a和a a，兩個(gè)的 2121支付一正一負(fù)，此時(shí)博弈都存在嚴(yán)格占優(yōu)的策略，故都存在純策略納什均衡。第

11、I類(lèi)的解為2,2 u S，納什均衡集合為N = (e2,e2)和Ane = e2 o第IV類(lèi)的解為1,1 u S，納什均衡集合為NE = (e1,e1)和ANE = e1。當(dāng)博弈是第II類(lèi)或者第iii類(lèi)時(shí)，支付函數(shù)值同號(hào)，此時(shí)不僅僅存在對(duì)稱(chēng)的純策略的納 什均衡，也存在對(duì)稱(chēng)的混合策略納什均衡。第II類(lèi)博弈，二者支付都為正數(shù)。有兩個(gè)對(duì)稱(chēng)的嚴(yán)格占優(yōu)的納什均衡，還有一個(gè)對(duì)稱(chēng)的 混合策略納什均衡，故它的解為1,2u S，納什均衡集合為ne = (e1,e1),(e2,e2),(x*,x*)，Ane = e1,e2,x*。其中x* = (a /(a + a ),a /(a + a )。這一類(lèi)博弈常見(jiàn)的例子

12、如調(diào)和博弈。221121第IV類(lèi)博弈，二者的支付都為負(fù)數(shù)，沒(méi)有嚴(yán)格占優(yōu)的策略。它的解為1,2 u S，納 什均衡集合為ne = (e1,e2),(e2,e1),(x*,x*)，Ane = x*。其中x* = (a /(a + a ),a /(a + a )。這一類(lèi)常見(jiàn)的博弈如鷹鴿博弈3 u(y, w)=uy,8y + (1-8)x, Vy。x(3-1)其中 u (x, w) = xTAw。策略x eA在任意的策略j eA下的最優(yōu)回應(yīng)集合為6*( y)。此時(shí)若x是該博弈的進(jìn)化 穩(wěn)定策略，則它必須滿(mǎn)足x e6*( y)，即x必須是該博弈的納什均衡即x eA ne，但還需要 滿(mǎn)足另外的條件才能保證x

13、是進(jìn)化穩(wěn)定的策略，由此可知，若用Aess表示博弈的進(jìn)化穩(wěn)定 策略集合，那么有Aess uAne，由進(jìn)化穩(wěn)定策略的含義可以更詳細(xì)的表示Aess的形式如下:A ess = x e A ne : u (x, y) u (y, y) Vy e 6 *( x)，y 豐 x(3-2)由此我們又回到了進(jìn)化穩(wěn)定策略的第一種定義的形式：稱(chēng)x是該博弈的進(jìn)化穩(wěn)定策略，若滿(mǎn)足如下兩個(gè)條件：u(x, x) u(x, y), Vy(3-3)當(dāng)存在 y 滿(mǎn)足 u(x, x) = u(x, y)時(shí)有 u(x, y) u(y, y), Vy。x。( 3-4)這兩個(gè)條件就如我們一開(kāi)始所說(shuō)的是判斷一個(gè)策略是不是進(jìn)化穩(wěn)定策略的標(biāo)準(zhǔn)。

14、2.兩種等價(jià)定義的作用將上述(3-1)式在定義計(jì)數(shù)函數(shù)：f ：，1xk R下可寫(xiě)為f餌，y)，且其等于 f (, y) = u(x- y,y + (1-)x)由x是進(jìn)化穩(wěn)定的可知當(dāng)足夠小且y。x時(shí)，f (,y) 0，由于函數(shù)u是雙線(xiàn)性的，f (, y)可寫(xiě)為：f (, y) = u(x y, x) + u(x y, y x)當(dāng)x,y eA固定時(shí)，計(jì)數(shù)函數(shù)f(,y)是一個(gè)關(guān)于的仿射函數(shù)，它的截距為 u(x y, x)斜率為u(x y, y x)，如下圖所示：f( ,y 1u (x - y, x)斜率為 u(x - y, y - x)條件(3-3)等價(jià)于截距是非負(fù)的，而條件(3-4)則等價(jià)于當(dāng)截距

15、為零時(shí)斜率是正值。因此當(dāng)兩個(gè)條件都滿(mǎn)足時(shí)，則存在廠(chǎng)e(01)使得對(duì)于所有的 e(0,)都有 f ( , y) 0成立，因此x eAess。對(duì)于進(jìn)化穩(wěn)定策略說(shuō)明兩個(gè)地方：一是并非所有的 博弈都有進(jìn)化穩(wěn)定策略，有部分博弈是沒(méi)有進(jìn)化穩(wěn)定策略的，例如石頭-剪刀-布博弈就 不具有進(jìn)化穩(wěn)定策略，不然隨著時(shí)間的推移，就沒(méi)有玩的意義了，因?yàn)橥婕抑滥莻€(gè)策 略是對(duì)自己最好的。二是進(jìn)化穩(wěn)定性并不意味著群體平均支付是最優(yōu)的。3.進(jìn)化穩(wěn)定策略集、ESS的結(jié)構(gòu)從3-1、3-3可知，一個(gè)進(jìn)化穩(wěn)定策略的支撐不可能包含另外一個(gè)進(jìn)化穩(wěn)定策略的支 撐，更進(jìn)一步說(shuō)不可能包含對(duì)稱(chēng)的納什均衡策略的支撐。例如：假設(shè)x eA ess，存在

16、 C(j) u C(x), y。x，那么 u(x,x) = u(x, y)，因?yàn)?x eAne，所以 u(x, y) u(y, y)， 所以y wAne，與C(y) u C(x), y。x矛盾。因此有如下推論：若 x eAess 且 C(y) u C(x), y。x，那么 y wAne。另外，如果博弈的一個(gè)進(jìn)化穩(wěn)定策略是本質(zhì)的(即完全混合策略)，那么它是該博弈的唯 一的進(jìn)化穩(wěn)定策略，而且在有限博弈中，支集是有限的，所以進(jìn)化穩(wěn)定策略也總是有限 的，甚至可能為零。因此有下面的引理：集合AESSu A是有限的，且如果x e AESS cint(A)，那么Aess = x。4. ESS與非合作博弈中的NE、pe等之間的關(guān)系從進(jìn)化穩(wěn)定策略的定義可以知道一個(gè)博弈的進(jìn)化穩(wěn)定策略必定是該博弈的納什均 衡，反之則不然，即Aess uANE。劣策略肯定不會(huì)是進(jìn)化穩(wěn)定的，因?yàn)樗旧聿豢赡艹蔀榧{什均衡，弱劣策略也不 會(huì)是進(jìn)化穩(wěn)定策略，就算