演化博弈论课件

演化博弈论

演讲人：杜同学号：S2011110541演化博弈论演讲人：杜同1演化博弈论第一章演化博弈论的概述第二章演化稳定策略第三章复制子动态第四章应用案例第五章前沿介绍2演化博弈论第一章演化博弈论的概述2第一章演化博弈论概述3第一章演化博弈论概述3什么是演化博弈论（1）传统博弈理论的两个苛刻假设：（1）完全理性（2）完全信息与传统博弈理论不同，演化博弈理论并不要求参与人是完全理性的，也不要求完全信息的条件。演化博弈论（EvolutionaryGameTheory）把博弈理论分析和动态演化过程分析结合起来的一种理论。在方法论上，它不同于博弈论将重点放在静态均衡和比较静态均衡上，强调的是一种动态的均衡。演化博弈理论源于生物进化论。4什么是演化博弈论（1）传统博弈理论的两个苛刻假设：4什么是演化博弈论（2）为什么将演化思想引入到博弈论中？（1）博弈论对生物学的影响。博弈论的策略对应生物学中的基因，博弈论的收益对应生物学中的适应度。在生物学中应用的博弈论与经济学中的传统博弈论最大区别就是非完全理性的选择。（2）演化化思想对社会科学的影响。例如，在市场竞争中，我们不必要去理性的想那个策略才是最优的，最后能够在市场存活下来的企业，一定是适应能力最强的公司。5什么是演化博弈论（2）为什么将演化思想引入到博弈论中？5

演化博弈论理论的特征

第一，以参与人群体为研究对象，分析动态的演化过程，解释群体为何达到以及如何达到目前的这一状态。第二，群体的演化既有选择过程也有突变过程。第三，经群体选择下来的行为具有一定的惯性。6

演化博弈论理论的特征

第一，以参与人群体为研究对象，分析动演化博弈论的产生与发展（1）7演化博弈论的产生与发展（1）7演化博弈论的产生与发展（2）8演化博弈论的产生与发展（2）8演化博弈论的应用自演化博弈论诞生之日起，它就逐渐的被人们用来分析生物、经济等领域的问题。SeltenReinhard．ANoteonEvolutionaryStableStrategiesinAsymmetricAnimalConflicts[J]．JournalofTheoreticalBiology，1980，(84)．陈星光,周晶,朱振涛.

城市交通出行方式选择的演化博弈分析[J].管理工程学报,2009,23(2):140-142.DeokJooKim,SungwookKim.Adaptivepowercontrolalgorithmbasedontheevolutionarygametheory[J].JournalofKISS:InformationNetworking,2010,37(3):228-293.杨波,徐升华.虚拟企业知识转移激励机理的演化博弈析[J].情报理论与实践,2010,33(7):50-54.徐岩，胡斌，钱任.基于随机演化博弈的战略联盟稳定性分析和仿真[J].系统工程理论与实践,2011,31(5):920-926.9演化博弈论的应用自演化博弈论诞生之日起，它就逐渐的被人们用来第二章演化稳定策略10第二章演化稳定策略10演化稳定策略概述1974年，Smith和Price提出“演化稳定策略”。演化稳定策略(Evolutionarilystablestragegy,ESS)，是指如果占群体绝大多数的个体选择演化稳定策略，那么小的突变者群体就不可能侵入到这个群体。下面我们从最简单的情况入手：考察一个大但是有限的总体，这个总体中的个体被规定好了选取对称性两人博弈中的纯策略11演化稳定策略概述1974年，Smith和Price提出“演囚徒困境的演化稳定策略YabXa2，20，3b3，01，1策略a是否是演化稳定策略？有一个规模为E的策略b入侵策略b是否是演化稳定策略？有一个规模为E的策略a入侵纳什均衡NOYES12囚徒困境的演化稳定策略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的一个纳什均衡。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡可以通过划线法得出13纳什均衡纳什均衡的定义：13纳什均衡和演化稳定（1）YabXa0，01，1b1，10，0策略b是否是演化稳定的？如果(S,S)不是纳什均衡，那么S不是演化稳定策略有一个规模为E的策略a入侵14纳什均衡和演化稳定（1）YabXa0，01，1b1，10，0纳什均衡和演化稳定（2）YabXa1，10，0b0，00，0策略b是否是演化稳定的？如果（S,S）是严格的纳什均衡，那么S是演化稳定策略有一个规模为E的策略b入侵15纳什均衡和演化稳定（2）YabXa1，10，0b0，00，0演化稳定策略的定义（1）Definition1:x∈A是演化稳定策略，如果y∈A，y≠x，存在一个∈(0，1)，使不等式

u[x,εy

+(1−ε)x]>

u[y,εy

+(1−ε)x]

对任意ε∈(0，)都成立。A:群体中个体博弈时的支付矩阵；y:表示突变策略；

:是一个与突变策略y有关的常数，称之为侵入界限；εy+(1−ε)x:表示选择进化稳定策略群体与选择突变策略群体所组成的混合群体。单一群体16演化稳定策略的定义（1）Definition1:单一群体1演化稳定策略的定义（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是演化稳定策略

17演化稳定策略的定义（2）Definition2:17混合策略的演化稳定性Ya(q)b(1-q)Xa(p)0，02，1b(1-p)1，20，0胆小鬼博弈混合策略纳什均衡（（1/3,2/3）,（1/3,2/3））18混合策略的演化稳定性Ya(q)b(1-q)Xa(p)0，02N-群体的演化稳定策略定义1：策略组合是纳什均衡，如果x是演化稳定策略，如果对于任意的策略组合存在某个使得对于所有的和,有定义2：策略组合x是演化稳定策略，当且仅当x是一个严格的纳什均衡。19N-群体的演化稳定策略定义1：策略组合问题演化过程两个基本要素：变异，选择。很明显，演化稳定性强调变异的作用，它关注什么样的状态才是稳定状态。那么，这样的稳定状态又是通过怎样的过程演化而来的？20问题演化过程两个基本要素：变异，选择。20第三章复制子动态21第三章复制子动态21复制子动态的概述生物种群的繁衍或者社会现象的不断变迁，就会产生一个时间上连续的总体动态，这就是复制子动态（replicatordynamics）这里的复制子是指纯策略，它可以从父母无差别的传递给孩子，随着总体状态的改变，纯策略（复制子）的收益和其适应性也会相应的改变。22复制子动态的概述生物种群的繁衍或者社会现象的不断变迁，就会产一般的两人对称博弈复制子动态（1）分析一个简单的情景：总体很大但是有限，总体中的个体被规定好了选取对称性两人博弈中的纯策略K：纯策略集合

u：收益函数pi(t)：当前被规定好了采取纯策略i的个体数。∑pi(t)表示总体

x(t)=(x1(t),…,xk(t)):总体状态。每个分量xi(t)表示时间t采取纯策略i的个体占总体的比例xi(t)=pi(t)/p(t)

u(ei,x)：纯策略i在随机匹配中得到的期望收益总体平均收益23一般的两人对称博弈复制子动态（1）分析一个简单的情景：总体很一般的两人对称博弈复制子动态（2）假设1收益代表博弈对个人适应性影响的增量效应2每个个体继承父母的单一策略3假设人的死亡率相同采用策略i的个体在时间t的出生率，这里是背景适应性（与博弈结果无关），总体动态：

对恒等式

两边求t的导数

得：

将式（1）带入（2）中，稍加整理可得：

式（3）说明：采用策略i的总体比例的增长率

等于策略收益和总体平均收益之差24一般的两人对称博弈复制子动态（2）假设式（3）说明：采用策根据上述收益得到复制动态方程：

dx/dt=x(R1-Ra)

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

令：dx/dt=F(x)

F(x)为x的单元函数。一般两人对称博弈复制子动态和ESS

如表3是一个简单的2*2对称博弈，如果不给出收益的具体数值，在一个群体中，有比例为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根据上述收益得到复制动态方程：

dx/dt=x(R1因为F(x)=x(1-x)[(a-b-c+d)x+(b-d)]，该复制动态最多有3个稳定状态，分别为x＊=0、x＊=1、x＊=（b-d)/(a-b-c+d)。一个稳定状态必须对微小扰动具有稳健性才能称为进化稳定策略。这相当于要求当干扰使x出现高于x＊时，dx/dt=F(x)必须小于0，即F’(x＊)＜0。这就是微分方程的稳定性定理。如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。根据图2也可以看出只有1/6才是进化稳定策略。0X*1x26因为F(x)=x(1-x)[(a-b-c+d)x+(b-d标准的N总体复制子动态与一般的两人对称博弈相似，标准的N总体复制子动态：总体比例增长率等于策略平均收益和博弈方平均收益之差。27标准的N总体复制子动态与一般的两人对称博弈相似，标准的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的复制动态方程为

dx/dt=x(u1e–u1a)=x(1-x)(1-2y)(4)博弈方2的复制动态方程为

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

先对博弈方1的复制动态方程分析：

若y=1/2，那么dx/dt始终为0，这意味着所有x水平都是稳定状态；若y≠1/2，则x＊=0、x＊=1，是两个稳定状态，其中y>1/2时，x＊=0是ESS，y<1/2时，x＊=1是ESS。

再对博弈方2的复制动态方程分析：

若x=0，那么dy/dt始终为0，这意味着所有x水平都是稳定状态；若x≠0(此时必然x>0)，则y＊=0、y＊=1，其中y＊=0是ESS。两人非对称博弈（3）30(3)博弈方1的复制动态方程为两人非对称博弈（3）30第四章应用实例31第四章应用实例31两个生产商的逆向供应链演化博弈分析

摘要:采用演化博弈方法研究逆向供应链在企业供应链中的推广应用,结果表明:在市场机制下,只有当生产商实施RSC时能够获得额外收益,RSC才能逐渐被市场接受,反之,生产商将消极对待RSC,这时就需要政府采取一定措施进行干预,对于市场中生产具有负的外部效应的生产商采取惩罚机制迫使企业接受RSC,对于生产具有正的外部效应的生产商采用财政补贴激励企业实施RSC.最后用数值分析证实了研究结果的正确性.32两个生产商的逆向供应链演化博弈分析

摘要:采用演化博弈方供应链中企业的划分按照供应链企业中生产商企业生产过程中表现出来的行为特征,我们将其分为开放型企业和保守型企业.所谓开放型的生产商属于同行业中的领导者企业,它们能够敏锐地观察到商机,善于采用新技术,及时进行企业革新,走在时代前列的企业;而保守型生产商则是行业中的跟随者,不会主动采纳尚未推广的新技术,表现为因循守旧,规避风险的企业.两者的区别从其生产成本的不同也可体现出来(由于积极技术革新,开放型生产商的生产成本比保守型的成本要低).33供应链中企业的划分按照供应链企业中生产商企业生产过程中表现出收益矩阵34收益矩阵34复制动态方程假定生产商1、2可以随机独立地选择策略E和N,并在多次生产销售市场重复地进行博弈.生产商1选择策