演化博弈論課件

演化博弈論

演講人：杜同學號：S2011110541演化博弈論演講人：杜同1演化博弈論第一章演化博弈論的概述第二章演化穩(wěn)定策略第三章復制子動態(tài)第四章應用案例第五章前沿介紹2演化博弈論第一章演化博弈論的概述2第一章演化博弈論概述3第一章演化博弈論概述3什么是演化博弈論（1）傳統(tǒng)博弈理論的兩個苛刻假設：（1）完全理性（2）完全信息與傳統(tǒng)博弈理論不同，演化博弈理論并不要求參與人是完全理性的，也不要求完全信息的條件。演化博弈論（EvolutionaryGameTheory）把博弈理論分析和動態(tài)演化過程分析結合起來的一種理論。在方法論上，它不同于博弈論將重點放在靜態(tài)均衡和比較靜態(tài)均衡上，強調的是一種動態(tài)的均衡。演化博弈理論源于生物進化論。4什么是演化博弈論（1）傳統(tǒng)博弈理論的兩個苛刻假設：4什么是演化博弈論（2）為什么將演化思想引入到博弈論中？（1）博弈論對生物學的影響。博弈論的策略對應生物學中的基因，博弈論的收益對應生物學中的適應度。在生物學中應用的博弈論與經(jīng)濟學中的傳統(tǒng)博弈論最大區(qū)別就是非完全理性的選擇。（2）演化化思想對社會科學的影響。例如，在市場競爭中，我們不必要去理性的想那個策略才是最優(yōu)的，最后能夠在市場存活下來的企業(yè)，一定是適應能力最強的公司。5什么是演化博弈論（2）為什么將演化思想引入到博弈論中？5

演化博弈論理論的特征

第一，以參與人群體為研究對象，分析動態(tài)的演化過程，解釋群體為何達到以及如何達到目前的這一狀態(tài)。第二，群體的演化既有選擇過程也有突變過程。第三，經(jīng)群體選擇下來的行為具有一定的慣性。6

演化博弈論理論的特征

第一，以參與人群體為研究對象，分析動演化博弈論的產(chǎn)生與發(fā)展（1）7演化博弈論的產(chǎn)生與發(fā)展（1）7演化博弈論的產(chǎn)生與發(fā)展（2）8演化博弈論的產(chǎn)生與發(fā)展（2）8演化博弈論的應用自演化博弈論誕生之日起，它就逐漸的被人們用來分析生物、經(jīng)濟等領域的問題。SeltenReinhard．ANoteonEvolutionaryStableStrategiesinAsymmetricAnimalConflicts[J]．JournalofTheoreticalBiology，1980，(84)．陳星光,周晶,朱振濤.

城市交通出行方式選擇的演化博弈分析[J].管理工程學報,2009,23(2):140-142.DeokJooKim,SungwookKim.Adaptivepowercontrolalgorithmbasedontheevolutionarygametheory[J].JournalofKISS:InformationNetworking,2010,37(3):228-293.楊波,徐升華.虛擬企業(yè)知識轉移激勵機理的演化博弈析[J].情報理論與實踐,2010,33(7):50-54.徐巖，胡斌，錢任.基于隨機演化博弈的戰(zhàn)略聯(lián)盟穩(wěn)定性分析和仿真[J].系統(tǒng)工程理論與實踐,2011,31(5):920-926.9演化博弈論的應用自演化博弈論誕生之日起，它就逐漸的被人們用來第二章演化穩(wěn)定策略10第二章演化穩(wěn)定策略10演化穩(wěn)定策略概述1974年，Smith和Price提出“演化穩(wěn)定策略”。演化穩(wěn)定策略(Evolutionarilystablestragegy,ESS)，是指如果占群體絕大多數(shù)的個體選擇演化穩(wěn)定策略，那么小的突變者群體就不可能侵入到這個群體。下面我們從最簡單的情況入手：考察一個大但是有限的總體，這個總體中的個體被規(guī)定好了選取對稱性兩人博弈中的純策略11演化穩(wěn)定策略概述1974年，Smith和Price提出“演囚徒困境的演化穩(wěn)定策略YabXa2，20，3b3，01，1策略a是否是演化穩(wěn)定策略？有一個規(guī)模為E的策略b入侵策略b是否是演化穩(wěn)定策略？有一個規(guī)模為E的策略a入侵納什均衡NOYES12囚徒困境的演化穩(wěn)定策略YabXa2，20，3b3，01，1策納什均衡納什均衡的定義：在博弈G=﹛S1,…,Sn：u1,…，un﹜中，如果由各個博弈方的各一個策略組成的某個策論組合（s1*,…，sn*）中，任一博弈方i的策論si*，都是對其余博弈方策略的組合（s1*,…s*i-1,s*i+1,…，sn*）的最佳對策，即不等式

ui（s1*,…s*i-1,si*,s*i+1,…，sn*）≥ui（s1*,…s*i-1,sij,s*i+1,…，sn*）對任意sij∈Si都成立，則稱（s1*,…，sn*）為G的一個納什均衡。納什均衡指的是這樣一種戰(zhàn)略組合，這種策略組合由所有參與人最優(yōu)策略組成。即在給定別人策略的情況下，沒有人有足夠理由打破這種均衡。納什均衡可以通過劃線法得出13納什均衡納什均衡的定義：13納什均衡和演化穩(wěn)定（1）YabXa0，01，1b1，10，0策略b是否是演化穩(wěn)定的？如果(S,S)不是納什均衡，那么S不是演化穩(wěn)定策略有一個規(guī)模為E的策略a入侵14納什均衡和演化穩(wěn)定（1）YabXa0，01，1b1，10，0納什均衡和演化穩(wěn)定（2）YabXa1，10，0b0，00，0策略b是否是演化穩(wěn)定的？如果（S,S）是嚴格的納什均衡，那么S是演化穩(wěn)定策略有一個規(guī)模為E的策略b入侵15納什均衡和演化穩(wěn)定（2）YabXa1，10，0b0，00，0演化穩(wěn)定策略的定義（1）Definition1:x∈A是演化穩(wěn)定策略，如果y∈A，y≠x，存在一個∈(0，1)，使不等式

u[x,εy

+(1?ε)x]>

u[y,εy

+(1?ε)x]

對任意ε∈(0，)都成立。A:群體中個體博弈時的支付矩陣；y:表示突變策略；

:是一個與突變策略y有關的常數(shù)，稱之為侵入界限；εy+(1?ε)x:表示選擇進化穩(wěn)定策略群體與選擇突變策略群體所組成的混合群體。單一群體16演化穩(wěn)定策略的定義（1）Definition1:單一群體1演化穩(wěn)定策略的定義（2）Definition2:對任意的s'∈S×S，滿足

(i)

f(s,s)≥f(s',s)；(ii)如果f(s,s)=f(s',s)，那么對任意的s≠s'有f(s,s)>f(s',s')；則s是演化穩(wěn)定策略

17演化穩(wěn)定策略的定義（2）Definition2:17混合策略的演化穩(wěn)定性Ya(q)b(1-q)Xa(p)0，02，1b(1-p)1，20，0膽小鬼博弈混合策略納什均衡（（1/3,2/3）,（1/3,2/3））18混合策略的演化穩(wěn)定性Ya(q)b(1-q)Xa(p)0，02N-群體的演化穩(wěn)定策略定義1：策略組合是納什均衡，如果x是演化穩(wěn)定策略，如果對于任意的策略組合存在某個使得對于所有的和,有定義2：策略組合x是演化穩(wěn)定策略，當且僅當x是一個嚴格的納什均衡。19N-群體的演化穩(wěn)定策略定義1：策略組合問題演化過程兩個基本要素：變異，選擇。很明顯，演化穩(wěn)定性強調變異的作用，它關注什么樣的狀態(tài)才是穩(wěn)定狀態(tài)。那么，這樣的穩(wěn)定狀態(tài)又是通過怎樣的過程演化而來的？20問題演化過程兩個基本要素：變異，選擇。20第三章復制子動態(tài)21第三章復制子動態(tài)21復制子動態(tài)的概述生物種群的繁衍或者社會現(xiàn)象的不斷變遷，就會產(chǎn)生一個時間上連續(xù)的總體動態(tài)，這就是復制子動態(tài)（replicatordynamics）這里的復制子是指純策略，它可以從父母無差別的傳遞給孩子，隨著總體狀態(tài)的改變，純策略（復制子）的收益和其適應性也會相應的改變。22復制子動態(tài)的概述生物種群的繁衍或者社會現(xiàn)象的不斷變遷，就會產(chǎn)一般的兩人對稱博弈復制子動態(tài)（1）分析一個簡單的情景：總體很大但是有限，總體中的個體被規(guī)定好了選取對稱性兩人博弈中的純策略K：純策略集合

u：收益函數(shù)pi(t)：當前被規(guī)定好了采取純策略i的個體數(shù)?！苝i(t)表示總體

x(t)=(x1(t),…,xk(t)):總體狀態(tài)。每個分量xi(t)表示時間t采取純策略i的個體占總體的比例xi(t)=pi(t)/p(t)

u(ei,x)：純策略i在隨機匹配中得到的期望收益總體平均收益23一般的兩人對稱博弈復制子動態(tài)（1）分析一個簡單的情景：總體很一般的兩人對稱博弈復制子動態(tài)（2）假設1收益代表博弈對個人適應性影響的增量效應2每個個體繼承父母的單一策略3假設人的死亡率相同采用策略i的個體在時間t的出生率，這里是背景適應性（與博弈結果無關），總體動態(tài)：

對恒等式

兩邊求t的導數(shù)

得：

將式（1）帶入（2）中，稍加整理可得：

式（3）說明：采用策略i的總體比例的增長率

等于策略收益和總體平均收益之差24一般的兩人對稱博弈復制子動態(tài)（2）假設式（3）說明：采用策根據(jù)上述收益得到復制動態(tài)方程：

dx/dt=x(R1-Ra)

=x(1-x)[(a-b-c+d)x+(b-d)].

令：dx/dt=F(x)

F(x)為x的單元函數(shù)。一般兩人對稱博弈復制子動態(tài)和ESS

如表3是一個簡單的2*2對稱博弈，如果不給出收益的具體數(shù)值，在一個群體中，有比例為x的人采用策略1，（1-x）的人采用策略2。采用兩種策略的博弈方的期望收益和群體平均收益分別為：

R1=x*a+(1-x)b①

R2=x*c+(1-x)d②

Ra=xR1+(1-x)R2③乙方策略1策略2甲方策略1a,ab,c策略2c,bd,d25根據(jù)上述收益得到復制動態(tài)方程：

dx/dt=x(R1因為F(x)=x(1-x)[(a-b-c+d)x+(b-d)]，該復制動態(tài)最多有3個穩(wěn)定狀態(tài)，分別為x＊=0、x＊=1、x＊=（b-d)/(a-b-c+d)。一個穩(wěn)定狀態(tài)必須對微小擾動具有穩(wěn)健性才能稱為進化穩(wěn)定策略。這相當于要求當干擾使x出現(xiàn)高于x＊時，dx/dt=F(x)必須小于0，即F’(x＊)＜0。這就是微分方程的穩(wěn)定性定理。如F(x)=x(1-x)(1-6x)

，不難解出x＊=0、x＊=1、x＊=1/6。進一步證明，只有1/6才是ESS。因為F’(1/6)＜0,而F’(0)＞0,F’(1)＞0。根據(jù)圖2也可以看出只有1/6才是進化穩(wěn)定策略。0X*1x26因為F(x)=x(1-x)[(a-b-c+d)x+(b-d標準的N總體復制子動態(tài)與一般的兩人對稱博弈相似，標準的N總體復制子動態(tài)：總體比例增長率等于策略平均收益和博弈方平均收益之差。27標準的N總體復制子動態(tài)與一般的兩人對稱博弈相似，標準的N總體兩人非對稱博弈（1）如果一個群體中成員之間的地位不一樣，那么博弈方之間進行就是非對稱博弈。非對稱博弈是用兩個（或多個）有差別的有限理性博弈方群體的成員，相互之間隨機配對博弈。以市場阻入博弈為例。12（0，0）（2，2）（1，5）進入不進打擊容忍2打擊y容忍1-y1進入x0,02,2不進1-x1,51,528兩人非對稱博弈（1）如果一個群體中成員之間的地位不一樣，那么（1）博弈方1的收益計算設“進入”、“不進”兩類博弈方的期望收益以及平均收益分別為u1e、u1n、u1a：

u1e=y*0+(1-y)*2=2(1-y)u1n=y*1+(1-y)*1=1u1a=xu1e+(1-x)u1n=2x(1-y)+(1-x)（2）博弈方2的收益計算設“打擊”、“容忍”兩類博弈方的期望收益以及平均收益分別為u2s、u2n、u2a：

u1e=x*0+(1-x)*5=5-5xu1n=x*2+(1-x)*5=5-3xu1a=yu2s+(1-y)u2n=5-2xy-3x兩人非對稱博弈（2）2打擊y容忍1-y1進入x0,02,2不進1-x1,51,529（1）博弈方1的收益計算兩人非對稱博弈（2）2打擊y容忍1-(3)博弈方1的復制動態(tài)方程為

dx/dt=x(u1e–u1a)=x(1-x)(1-2y)(4)博弈方2的復制動態(tài)方程為

dy/dt=y(u2s–u2a)=y(1-y)(-2x)

先對博弈方1的復制動態(tài)方程分析：

若y=1/2，那么dx/dt始終為0，這意味著所有x水平都是穩(wěn)定狀態(tài)；若y≠1/2，則x＊=0、x＊=1，是兩個穩(wěn)定狀態(tài)，其中y>1/2時，x＊=0是ESS，y<1/2時，x＊=1是ESS。

再對博弈方2的復制動態(tài)方程分析：

若x=0，那么dy/dt始終為0，這意味著所有x水平都是穩(wěn)定狀態(tài)；若x≠0(此時必然x>0)，則y＊=0、y＊=1，其中y＊=0是ESS。兩人非對稱博弈（3）30(3)博弈方1的復制動態(tài)方程為兩人非對稱博弈（3）30第四章應用實例31第四章應用實例31兩個生產(chǎn)商的逆向供應鏈演化博弈分析

摘要:采用演化博弈方法研究逆向供應鏈在企業(yè)供應鏈中的推廣應用,結果表明:在市場機制下,只有當生產(chǎn)商實施RSC時能夠獲得額外收益,RSC才能逐漸被市場接受,反之,生產(chǎn)商將消極對待RSC,這時就需要政府采取一定措施進行干預,對于市場中生產(chǎn)具有負的外部效應的生產(chǎn)商采取懲罰機制迫使企業(yè)接受RSC,對于生產(chǎn)具有正的外部效應的生產(chǎn)商采用財政補貼激勵企業(yè)實施RSC.最后用數(shù)值分析證實了研究結果的正確性.32兩個生產(chǎn)商的逆向供應鏈演化博弈分析

摘要:采用演化博弈方供應鏈中企業(yè)的劃分按照供應鏈企業(yè)中生產(chǎn)商企業(yè)生產(chǎn)過程中表現(xiàn)出來的行為特征,我們將其分為開放型企業(yè)和保守型企業(yè).所謂開放型的生產(chǎn)商屬于同行業(yè)中的領導者企業(yè),它們能夠敏銳地觀察到商機,善于采用新技術,及時進行企業(yè)革新,走在時代前列的企業(yè);而保守型生產(chǎn)商則是行業(yè)中的跟隨者,不會主動采納尚未推廣的新技術,表現(xiàn)為因循守舊,規(guī)避風險的企業(yè).兩者的區(qū)別從其生產(chǎn)成本的不同也可體現(xiàn)出來(由于積極技術革新,開放型生產(chǎn)商的生產(chǎn)成本比保守型的成本要低).33供應鏈中企業(yè)的劃分按照供應鏈企業(yè)中生產(chǎn)商企業(yè)生產(chǎn)過程中表現(xiàn)出收益矩陣34收益矩陣34復制動態(tài)方程假定生產(chǎn)商1、2可以隨機獨立地選擇策略E和N,并在多次生產(chǎn)銷售市場重復地進行博弈.生產(chǎn)商1選擇策