進化博弈論讀書心得

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

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

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

4、J)分別表示選擇相應(yīng)策略帶來的適應(yīng)度，而E(L J)表示 個體選擇策略1而對手選擇J時的收益，其他E(I,I)等表示類同的意義。若每一個個體都參與到競爭當(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ì)：整個種群中幾乎所有的個體都采取了這個策略，且這些個體的 適應(yīng)度必將高于競爭對手或者可能出現(xiàn)的突變異種的適應(yīng)度，否則競爭對手或者產(chǎn)生的突變 異種會侵害整個種群，以致種群的削弱或者毀滅等，這時此策略便不可能是穩(wěn)定的策略。若 I是進化穩(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)時有 E(I, J) E(J, J)(1-4)滿足上述條件(1-3)、(1-4)的策略就稱為進化穩(wěn)定策略，而上述的兩個條件1-3、1-4也被 認為是判別ESS的標(biāo)準條件。上述的策略是在純策略情形下考慮的，當(dāng)策略I是從一個可能策略集合中隨機的選擇而構(gòu)成的，此時的策略稱為混合策略。此時/若是一個混合進化穩(wěn)定策略，假設(shè)*,s2,.,sk 等是該群體的純策略，賦予這些純策略非零的概率值，那么/必須滿足如下條件：E (s1) = E (s2) =. = E (七)二E (I, I)(1

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

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

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

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

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

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

12、如調(diào)和博弈。221121第IV類博弈，二者的支付都為負數(shù)，沒有嚴格占優(yōu)的策略。它的解為1,2 u S，納 什均衡集合為ne = (e1,e2),(e2,e1),(x*,x*)，Ane = x*。其中x* = (a /(a + a ),a /(a + a )。這一類常見的博弈如鷹鴿博弈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)。此時若x是該博弈的進化 穩(wěn)定策略，則它必須滿足x e6*( y)，即x必須是該博弈的納什均衡即x eA ne，但還需要 滿足另外的條件才能保證x

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

14、2.兩種等價定義的作用將上述(3-1)式在定義計數(shù)函數(shù)：f ：，1xk R下可寫為f餌，y)，且其等于 f (, y) = u(x- y,y + (1-)x)由x是進化穩(wěn)定的可知當(dāng)足夠小且y。x時，f (,y) 0，由于函數(shù)u是雙線性的，f (, y)可寫為：f (, y) = u(x y, x) + u(x y, y x)當(dāng)x,y eA固定時，計數(shù)函數(shù)f(,y)是一個關(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)等價于截距是非負的，而條件(3-4)則等價于當(dāng)截距

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

16、 C(j) u C(x), y。x，那么 u(x,x) = u(x, y)，因為 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。另外，如果博弈的一個進化穩(wěn)定策略是本質(zhì)的(即完全混合策略)，那么它是該博弈的唯 一的進化穩(wěn)定策略，而且在有限博弈中，支集是有限的，所以進化穩(wěn)定策略也總是有限 的，甚至可能為零。因此有下面的引理：集合AESSu A是有限的，且如果x e AESS cint(A)，那么Aess = x。4. ESS與非合作博弈中的NE、pe等之間的關(guān)系從進化穩(wěn)定策略的定義可以知道一個博弈的進化穩(wěn)定策略必定是該博弈的納什均 衡，反之則不然，即Aess uANE。劣策略肯定不會是進化穩(wěn)定的，因為它本身不可能成為納什均衡，弱劣策略也不 會是進化穩(wěn)定策略，就算