演化博弈论课件.ppt

1,演化博弈论,演讲人： 杜 同 学 号：S201111054,2,演化博弈论,第一章 演化博弈论的概述第二章 演化稳定策略第三章 复制子动态第四章 应用案例第五章 前沿介绍,3,第一章 演化博弈论概述,4,什么是演化博弈论（1）,传统博弈理论的两个苛刻假设： （1）完全理性（2）完全信息与传统博弈理论不同，演化博弈理论并不要求参与人是完全理性的，也不要求完全信息的条件。演化博弈论（Evolutionary Game Theory）把博弈理论分析和动态演化过程分析结合起来的一种理论。在方法论上，它不同于博弈论将重点放在静态均衡和比较静态均衡上，强调的是一种动态的均衡。演化博弈理论源于生物进化论。,5,什么是演化博弈论（2）,为什么将演化思想引入到博弈论中？（1）博弈论对生物学的影响。博弈论的策略对应生物学中的基因 ，博弈论的收益对应生物学中的适应度。在生物学中应用的博弈论与经济学中的传统博弈论最大区别就是非完全理性的选择。（2）演化化思想对社会科学的影响。例如，在市场竞争中，我们不必要去理性的想那个策略才是最优的，最后能够在市场存活下来的企业，一定是适应能力最强的公司。,6,演化博弈论理论的特征,第一，以参与人群体为研究对象，分析动态的演化过程，解释群体为何达到以及如何达到目前的这一状态。第二，群体的演化既有选择过程也有突变过程。第三，经群体选择下来的行为具有一定的惯性。,7,演化博弈论的产生与发展（1）,8,演化博弈论的产生与发展（2）,9,演化博弈论的应用,自演化博弈论诞生之日起，它就逐渐的被人们用来分析生物、经济等领域的问题。Selten ReinhardA Note on Evolutionary Stable Strategies in Asymmetric Animal Conflicts J Journal of Theoretical Biology，1980，(84)陈星光,周晶,朱振涛. 城市交通出行方式选择的演化博弈分析J. 管理工程学报,2009,23(2):140-142.DeokJoo Kim,Sungwook Kim. Adaptive power control algorithm based on the evolutionary game theoryJ. Journal of KISS: Information Networking,2010,37(3):228-293.杨波,徐升华.虚拟企业知识转移激励机理的演化博弈析J. 情报理论与实践,2010,33(7):50-54.徐岩，胡斌，钱任. 基于随机演化博弈的战略联盟稳定性分析和仿真J. 系统工程理论与实践,2011,31(5):920-926.,10,第二章 演化稳定策略,11,演化稳定策略概述,1974年，Smith和Price提出 “演化稳定策略”。演化稳定策略(Evolutionarily stable stragegy,ESS)，是指如果占群体绝大多数的个体选择演化稳定策略，那么小的突变者群体就不可能侵入到这个群体。下面我们从最简单的情况入手：考察一个大但是有限的总体，这个总体中的个体被规定好了选取对称性两人博弈中的纯策略,12,囚徒困境的演化稳定策略,策略a 是否是演化稳定策略？,有一个规模为E的策略b入侵,策略b 是否是演化稳定策略？,有一个规模为E的策略a入侵,纳什均衡,NO,YES,13,纳什均衡,纳什均衡的定义： 在博弈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*）对任意sijSi都成立，则称（s1*,，sn*）为G的一个纳什均衡。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡可以通过划线法得出,14,纳什均衡和演化稳定（1）,策略b是否是演化稳定的？,如果(S,S)不是纳什均衡，那么S不是演化稳定策略,有一个规模为E的策略a入侵,15,纳什均衡和演化稳定（2）,策略b是否是演化稳定的？,如果（S,S）是严格的纳什均衡，那么S是演化稳定策略,有一个规模为E的策略b入侵,16,演化稳定策略的定义（1）,Definition 1: xA是演化稳定策略，如果yA，yx，存在一个 (0，1)，使不等式 ux,y+ (1 )x uy,y+ (1 )x 对任意 (0，)都成立。A:群体中个体博弈时的支付矩阵；y:表示突变策略； :是一个与突变策略y有关的常数，称之为侵入界限；y + (1 )x:表示选择进化稳定策略群体与选择突变策略群体所组成的混合群体。,单一群体,17,演化稳定策略的定义（2）,Definition 2:对任意的sSS，满足 (i) f(s,s)f(s,s)； (ii)如果f(s,s)=f(s,s)，那么对任意的ss有 f(s,s)f(s,s)； 则s是演化稳定策略,18,混合策略的演化稳定性,胆小鬼博弈,混合策略纳什均衡（1/3,2/3）,（1/3,2/3）,19,N-群体的演化稳定策略,定义1：策略组合 是纳什均衡，如果x是演化稳定策略，如果对于任意的策略组合 存在某个 使得对于所有的 和 ,有定义2：策略组合x是演化稳定策略，当且仅当x是一个严格的纳什均衡。,20,问题,演化过程两个基本要素：变异，选择。很明显，演化稳定性强调变异的作用，它关注什么样的状态才是稳定状态。那么，这样的稳定状态又是通过怎样的过程演化而来的？,21,第三章 复制子动态,22,复制子动态的概述,生物种群的繁衍或者社会现象的不断变迁，就会产生一个时间上连续的总体动态，这就是复制子动态（replicator dynamics）这里的复制子是指纯策略，它可以从父母无差别的传递给孩子，随着总体状态的改变，纯策略（复制子）的收益和其适应性也会相应的改变。,23,一般的两人对称博弈复制子动态（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在随机匹配中得到的期望收益总体平均收益,24,一般的两人对称博弈复制子动态（2）,假设1收益代表博弈对个人适应性影响的增量效应2每个个体继承父母的单一策略3假设人的死亡率 相同采用策略i的个体在时间t的出生率 ，这里 是背景适应性（与博弈结果无关），总体动态： 对恒等式 两边求t的导数 得： 将式（1）带入（2）中，稍加整理可得：,式（3）说明：采用策略i的总体比例的增长率 等于策略收益和总体平均收益之差,25,根据上述收益得到复制动态方程：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 ,26,因为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才是进化稳定策略。,27,标准的N总体复制子动态,与一般的两人对称博弈相似，标准的N总体复制子动态： 总体比例增长率 等于策略平均收益和博弈方平均收益之差。,28,两人非对称博弈（1）,如果一个群体中成员之间的地位不一样，那么博弈方之间进行就是非对称博弈。非对称博弈是用两个（或多个）有差别的有限理性博弈方群体的成员，相互之间随机配对博弈。以市场阻入博弈为例。,29,（1）博弈方1的收益计算设“进入”、“不进”两类博弈方的期望收益以及平均收益分别为u1e、u1n、u1a： u1e= y*0 +(1-y)*2 =2(1-y) u1n= y*1 +(1-y)*1 =1 u1a = x u1e +(1-x) u1n =2x(1-y)+(1-x)（2）博弈方2的收益计算设“打击”、“容忍”两类博弈方的期望收益以及平均收益分别为u2s、u2n、u2a： u1e= x*0 +(1-x)*5 =5-5x u1n= x*2 +(1-x)*5 =5-3x u1a = y u2s +(1-y) u2n =5-2xy-3x,两人非对称博弈（2）,30,(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水平都是稳定状态； 若y1/2，则x=0、 x=1，是两个稳定状态，其中y1/2时， x=0是ESS，y0)，则y=0、 y=1，其中y=0是ESS。,两人非对称博弈（3）,31,第四章 应用实例,32,两个生产商的逆向供应链演化博弈分析,摘要: 采用演化博弈方法研究逆向供应链在企业供应链中的推广应用, 结果表明: 在市场机制下, 只有当生产商实施RSC 时能够获得额外收益, RSC 才能逐渐被市场接受, 反之, 生产商将消极对待RSC, 这时就需要政府采取一定措施进行干预, 对于市场中生产具有负的外部效应的生产商采取惩罚机制迫使企业接受RSC, 对于生产具有正的外部效应的生产商采用财政补贴激励企业实施RSC. 最后用数值分析证实了研究结果的正确性.,33,供应链中企业的划分,按照供应链企业中生产商企业生产过程中表现出来的行为特征, 我们将其分为开放型企业和保守型企业. 所谓开放型的生产商属于同行业中的领导者企业, 它们能够敏锐地观察到商机, 善于采用新技术, 及时进行企业革新, 走在时代前列的企业; 而保守型生产商则是行业中的跟随者, 不会主动采纳尚未推广的新技术, 表现为因循守旧, 规避风险的企业. 两者的区别从其生产成本的不同也可体现出来( 由于积极技术革新, 开放型生产商的生产成本比保守型的成本要低) .,34,收益矩阵,35,复制动态方程,假定生产商 1、2 可以随机独立地选择策略 E 和N , 并在多次生产销售市场重复地进行博弈. 生产商 1选择策略 E 的比例是p , 选取策略 N 的比例是 1- p . 生产商 2 选择策略 E 的比例是 q, 选取策略 N 的比例 是 1- q. 根据 Malthusian 方程, 生产商 1 选取策略 E 的数量的增长率应等于其适应度减去其平均适应度：同理，可得生产商2选择策略E的平均增长率：令 ， 可得系统的平衡点,36,演化稳定策略,37,38,39,第五章 前沿介绍,40,理论,应用,41,演化博弈论和随机微分方程,现有的演化博弈论分析，基本上采用的是确定性的复制动态方程，而在复杂的演化过程中，随机现象是难以避免的。将随机因素考虑进演化过程中，将会给演化稳定策略的判断带来新的挑战，需要借助随机微分方程解的稳定性理论。,复制动态方程,随机因素,随机微分方程,42,演化博弈论和复杂网络,复杂网络（Complex Network），具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。将演化博弈论和复杂网络相结合，研究特定的网络结构中合作的涌现，以及稳定的实现问题。,43,演化博弈论和供应链管理,供应链整体的发展和竞争力的提升依赖于供应链节点间的协助与合作，节点之间既竞争又合作的关系, 成为供应链经久不衰的创新动力, 从而保持供应链整体竞争优势.近年来，有一些学者用演化博弈论来分析供应链节点之间的竞争与合作关系，探讨供应链实现稳定合作的条件,44,谢谢！,