演化博弈論課件

演化博弈論

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

演化博弈論理論的特征

第一，以參與人群體為研究對象，分析動態(tài)的演化過程，解釋群體為何達(dá)到以及如何達(dá)到目前的這一狀態(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演化博弈論的應(yīng)用自演化博弈論誕生之日起，它就逐漸的被人們用來分析生物、經(jīng)濟(jì)等領(lǐng)域的問題。SeltenReinhard．ANoteonEvolutionaryStableStrategiesinAsymmetricAnimalConflicts[J]．JournalofTheoreticalBiology，1980，(84)．陳星光,周晶,朱振濤.

城市交通出行方式選擇的演化博弈分析[J].管理工程學(xué)報(bào),2009,23(2):140-142.DeokJooKim,SungwookKim.Adaptivepowercontrolalgorithmbasedontheevolutionarygametheory[J].JournalofKISS:InformationNetworking,2010,37(3):228-293.楊波,徐升華.虛擬企業(yè)知識轉(zhuǎn)移激勵(lì)機(jī)理的演化博弈析[J].情報(bào)理論與實(shí)踐,2010,33(7):50-54.徐巖，胡斌，錢任.基于隨機(jī)演化博弈的戰(zhàn)略聯(lián)盟穩(wěn)定性分析和仿真[J].系統(tǒng)工程理論與實(shí)踐,2011,31(5):920-926.9演化博弈論的應(yīng)用自演化博弈論誕生之日起，它就逐漸的被人們用來第二章演化穩(wěn)定策略10第二章演化穩(wěn)定策略10演化穩(wěn)定策略概述1974年，Smith和Price提出“演化穩(wěn)定策略”。演化穩(wěn)定策略(Evolutionarilystablestragegy,ESS)，是指如果占群體絕大多數(shù)的個(gè)體選擇演化穩(wěn)定策略，那么小的突變者群體就不可能侵入到這個(gè)群體。下面我們從最簡單的情況入手：考察一個(gè)大但是有限的總體，這個(gè)總體中的個(gè)體被規(guī)定好了選取對稱性兩人博弈中的純策略11演化穩(wěn)定策略概述1974年，Smith和Price提出“演囚徒困境的演化穩(wěn)定策略YabXa2，20，3b3，01，1策略a是否是演化穩(wěn)定策略？有一個(gè)規(guī)模為E的策略b入侵策略b是否是演化穩(wěn)定策略？有一個(gè)規(guī)模為E的策略a入侵納什均衡NOYES12囚徒困境的演化穩(wěn)定策略YabXa2，20，3b3，01，1策納什均衡納什均衡的定義：在博弈G=﹛S1,…,Sn：u1,…，un﹜中，如果由各個(gè)博弈方的各一個(gè)策略組成的某個(gè)策論組合（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的一個(gè)納什均衡。納什均衡指的是這樣一種戰(zhàn)略組合，這種策略組合由所有參與人最優(yōu)策略組成。即在給定別人策略的情況下，沒有人有足夠理由打破這種均衡。納什均衡可以通過劃線法得出13納什均衡納什均衡的定義：13納什均衡和演化穩(wěn)定（1）YabXa0，01，1b1，10，0策略b是否是演化穩(wěn)定的？如果(S,S)不是納什均衡，那么S不是演化穩(wěn)定策略有一個(gè)規(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）是嚴(yán)格的納什均衡，那么S是演化穩(wěn)定策略有一個(gè)規(guī)模為E的策略b入侵15納什均衡和演化穩(wěn)定（2）YabXa1，10，0b0，00，0演化穩(wěn)定策略的定義（1）Definition1:x∈A是演化穩(wěn)定策略，如果y∈A，y≠x，存在一個(gè)∈(0，1)，使不等式

u[x,εy

+(1?ε)x]>

u[y,εy

+(1?ε)x]

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

:是一個(gè)與突變策略y有關(guān)的常數(shù)，稱之為侵入界限；εy+(1?ε)x:表示選擇進(jìn)化穩(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)定策略，如果對于任意的策略組合存在某個(gè)使得對于所有的和,有定義2：策略組合x是演化穩(wěn)定策略，當(dāng)且僅當(dāng)x是一個(gè)嚴(yán)格的納什均衡。19N-群體的演化穩(wěn)定策略定義1：策略組合問題演化過程兩個(gè)基本要素：變異，選擇。很明顯，演化穩(wěn)定性強(qiáng)調(diào)變異的作用，它關(guān)注什么樣的狀態(tài)才是穩(wěn)定狀態(tài)。那么，這樣的穩(wěn)定狀態(tài)又是通過怎樣的過程演化而來的？20問題演化過程兩個(gè)基本要素：變異，選擇。20第三章復(fù)制子動態(tài)21第三章復(fù)制子動態(tài)21復(fù)制子動態(tài)的概述生物種群的繁衍或者社會現(xiàn)象的不斷變遷，就會產(chǎn)生一個(gè)時(shí)間上連續(xù)的總體動態(tài)，這就是復(fù)制子動態(tài)（replicatordynamics）這里的復(fù)制子是指純策略，它可以從父母無差別的傳遞給孩子，隨著總體狀態(tài)的改變，純策略（復(fù)制子）的收益和其適應(yīng)性也會相應(yīng)的改變。22復(fù)制子動態(tài)的概述生物種群的繁衍或者社會現(xiàn)象的不斷變遷，就會產(chǎn)一般的兩人對稱博弈復(fù)制子動態(tài)（1）分析一個(gè)簡單的情景：總體很大但是有限，總體中的個(gè)體被規(guī)定好了選取對稱性兩人博弈中的純策略K：純策略集合

u：收益函數(shù)pi(t)：當(dāng)前被規(guī)定好了采取純策略i的個(gè)體數(shù)。∑pi(t)表示總體

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

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

對恒等式

兩邊求t的導(dǎo)數(shù)

得：

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

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

等于策略收益和總體平均收益之差24一般的兩人對稱博弈復(fù)制子動態(tài)（2）假設(shè)式（3）說明：采用策根據(jù)上述收益得到復(fù)制動態(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ù)。一般兩人對稱博弈復(fù)制子動態(tài)和ESS

如表3是一個(gè)簡單的2*2對稱博弈，如果不給出收益的具體數(shù)值，在一個(gè)群體中，有比例為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ù)上述收益得到復(fù)制動態(tài)方程：

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

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

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

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

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

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

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

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

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

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