第_7_章_进化博弈论简介

进化博弈论简介（对应教材第7章）回顾上一讲（博弈论基础）• 博弈– 参与者（player）– 策略（strategy）– 收益，回报（payoff）• 收益矩阵－形象地描述一个博弈的结构• 在博弈论的分析中（决定采取什么策略）– 不是要考虑如何战胜对方，而是基于对对方的行为的预测，自己如何收益最大（尽可能大）。双方都如此态度。• 纯策略、混合策略（在可选纯策略集合上的一个概率分布）均衡（纳什均衡）• 均衡：互为最佳应对• 纳什均衡定理：在考虑混合策略条件下，任何有限参与人、有限纯策略的博弈都存在均衡• 一般来讲，找到均衡是很困难的，但在某些限定条件下可能有系统化方法– 例如，双人双（纯）策略1. 检查四个策略组合是否为纯策略均衡2. 利用无差异原理试求混合策略均衡若（1）为空，则（2）一定有；若（1）不空，（2）也可能有囚徒困境（协调）博弈的特征模式• • • • 双人双策略对称均衡出现在双方采用某一种相同的策略“最佳收益”不是均衡，因为参与人之一有动机改变策略鹰鸽博弈的特征模式• 双人双策略• 对称• 均衡出现在双方采用不同的策略双人双策略对称博弈均衡的一般条件• • • • 若（S,S）是均衡，a,b,c,d之间的关系？若（S,T）是均衡，…？若（T,S）是均衡，…？若（T,T）是均衡，…？经常会用到“期望”的概念• 一个随机的行为，会有多种（以两种为例）可能的结果（r1,r2），分别对应一个概率（p1,p2），p1+p2=1• 则这个行为的结果期望就是p1r1+p2r2• 概率常常用“比率”和“占比”来近似• 混合策略的收益：在纯策略集合上按概率分布选择的收益期望进化博弈论：谁有更强的适应性博弈与进化博弈若干概念的一种对比理解• 博弈，纯策略– 确定性策略，直接对应的收益• 博弈，混合策略– 概率性策略，期望收益• 进化博弈，纯策略– 对于个体：确定性策略，直接收益– 对于群体（策略）：适应性－其中个体与其他个体随机相遇的收益期望• 进化博弈，混合策略– 对于个体：概率性策略，期望收益– 对于群体（策略）：适应性－其中个体与其他个体随机相遇的收益期望均衡稳定性进化博弈的由来• 进化论的主要观点– 生物体的遗传基因在很大程度上决定了它的外部特征（行为方式等），因而决定了它是否能够适应给定的环境。– 适应性较强的生物体往往会繁衍较多的后代，于是使得适应性强的基因的物种在总体中的数量增加。– 一个物种的成功进化取决于它其中的个体和其他个体（同种或者不同种）的互动。进化博弈的由来• 1960s，从博弈论视角来解释生物进化论– 由基因决定的生物特征及行为可类比作博弈中的策略；– 将生物的适应性（的提高）类比为它的收益。• J.M.Smith和G.R.Price，提出“进化稳定均衡”，标志着进化博弈的诞生。– JohnM.Smith.OnEvolu)on.EdinburghUniversityPress,1972– J.M.SmithandG.R.Price,TheLogicofAnimalConflict,Nature,246,15-‐18,1973.生物适应性与种群变异• 例子：体态大小的博弈– 考虑一种甲虫种群– 假设每只甲虫对给定环境的适应能力取决于• 它是否可以发现食物• 能否有效地从食物中汲取营养– 假设一个特定的突变基因出现并开始蔓延，造成携带该突变基因的甲虫体型变大。– 因此，在该甲虫种群中，便分成两种不同的群体——小甲虫和大甲虫。生物适应性与新陈代谢• 对于大甲虫，维持新陈代谢实际上要比较困难些– 需要吃较多的食物才能维持较大的体态要求；即同样数量的食物，小甲虫从中可获得较多的收益（适应性）。• 直观结论是：大体态变异基因使适应性减弱，经过多次繁衍后，它极可能被淘汰。• 然而事实真的是这样吗？互动与生物适应性• 当两只甲虫为食物争夺时，可能的结果有：– 当争夺食物的两只甲虫大小相同时，它们会平分同样的食物– 当一只大甲虫和一只小甲虫争夺食物，则大甲虫会得到大多数的食物– 对于同样的食物量，大甲虫在适应性上得到的益处要少，因为所得到的食物中有一部分要转化用来维持它们消耗较高的新陈代谢收益矩阵• 每只甲虫从争夺一定量食物的互动中获得的生物适应性（不是食物量），可认为是双人博弈中的收益。• 每只甲虫有两个策略：大和小，由其基因决定。甲虫2小的大的甲虫1小的大的5,58,11,83,3与经典的博弈比较• 每只甲虫的策略都是由遗传基因硬性决定的– “策略选择”的概念在此是缺失的• 因此以策略选择为基础的纳什均衡思想在此没有直接的对应• 但我们可有一个平行的概念－－“进化稳定策略”的概念（下面我们先学习这个概念，然后看它和纳什均衡的关系）甲虫2小的大的甲虫1小的大的5,58,11,83,3进化稳定策略• 一个策略称为是进化稳定的，若当整个种群都采取这个策略时，任何采用不同策略的小规模“入侵”群体经过多代遗传后最终会消亡。• 形式化定义– 一种生物体的适应性是指它与一个随机遇到的生物体互动得到的收益期望– 称“策略T在x程度上（以x水平）入侵策略S”，指的是在总体中有x占比的生物体采用策略T，1-‐x占比采用策略S；其中x是一个小于1的小正数。– 若存在一个小正数y，当任何其他策略T以任何xy水平入侵策略S时，采用策略S的个体的适应性严格高于采取策略T的个体，则称策略S是进化稳定的（evoluVonarilystable）。• 考虑一个小正数x，总体中有x占比的个体使用策略“大体态”，有1-‐x占比的个体使用策略“小体态”。（甲虫们随机相遇争夺食物）– 一只小甲虫的期望收益是5(1-‐x)+1x=5-‐4x– 一只大甲虫的期望收益是8(1-‐x)+3x=8-‐5x• 可见，不存在y，使得xy时小甲虫的期望收益超过大甲虫。因此，策略“小体态”不是进化稳定的。考察小体态是否进化稳定策略甲虫2小的大的甲虫1小的大的5,58,11,83,3(1-x)x• 考虑一个很小的正数x，总体中x占比为小体态，1-‐x占比甲虫为大体态。– 大甲虫期望收益是8x+3(1-‐x)=3+5x– 小甲虫期望收益是5x+(1-‐x)=1+4x• 大甲虫的期望收益总是超过小甲虫的，所以，“大体态”是一个进化稳定策略。体态博弈中的进化稳定策略：考察大体态甲虫2小的甲虫1小的大的5,58,11,83,3大的(1-x)x进化博弈中的“军备竞赛”• 生物学家认为在自然界中存在具有囚徒困境结构的进化博弈现象– 例如：树木间高矮的关系；植物根系的竞争• 例子：病毒博弈– 噬菌体Φ6病毒。这种病毒感染细胞，而且产生自我复制（繁殖）所需的产物。– 它的一种基因变异体称为噬菌体ΦH2，自身繁殖能力较弱，但能够利用Φ6的化学产物，于是当和病毒噬菌体Φ6同时存在时，噬菌体ΦH2在适应性方面便有一个明显优势。• 具有类似囚徒困境博弈的结构：• 病毒有两个进化策略Φ6和ΦH2；• 在一个纯Φ6种群中，病毒行为收益（自我复制的能力）会优于纯ΦH2种群的病毒；• 但是，当病毒ΦH2与Φ6同时存在时，ΦH2的收益会比较高，甚至高于纯Φ6种群情形。• 因此，只有ΦH2是进化稳定的。– 结果就是，一旦Φ6种群中出现了少量变异ΦH2，则ΦH2病毒会越来越多，Φ6越来越少• 换句话说，ΦH2成功入侵了Φ6• 理性的选择与进化的力量有相似的取向病毒博弈的收益矩阵• 生物学家测量了两病毒在不同条件下复制行为的相对速率（体现适应性）病毒2Φ6ΦH2病毒1Φ6ΦH21.00,1.001.99,0.650.65,1.990.83,0.83进化稳定策略的一般描述• 如何用a，b，c，d写出S是进化稳定的条件？• 设对于一个很小的正数x，总体中有1-‐x部分使用策略S，有x部分使用策略T– 采取S策略的期望收益：a(1-‐x)+bx– 采取T策略的期望收益：c(1-‐x)+dx所以应满足a(1-‐x)+bxc(1-‐x)+dx• 结论：在双人双策略的对称博弈中，若(i)ac或(ii)a=c且bd，则S是进化稳定的。（注意“x很小”在其中的作用）生物体2生物体1STa,ac,bb,cd,dT(x)S(1-x)考虑双人对称博弈• 在双人双策略的对称博弈中，若(i)ac，或(ii)a=c且bd，则S是进化稳定的。这意味着：– 为了使S成为一个进化稳定策略，用策略S应对策略S的回报不能小于用策略T来应对策略S取得的回报。– 若策略S和T在应对策略S时的收益相等。为了保证S是一个进化稳定策略，采取策略S应对策略T的收益要严格优于采取策略T应对策略T的收益。生物体2ST生物体1STa,ac,bb,cd,d• S是进化稳定的条件：– (i)ac，或(ii)a=c且bd• (S,S)是纳什均衡的条件：a≥c• 因此，若策略S是进化稳定的，则(S,S)一定是一个纳什均衡。反之不一定成立。进化稳定策略与纳什均衡的关系生物体2ST生物体1STa,ac,bb,cd,d例子：猎鹿博弈• 猎鹿，猎兔都是进化稳定的– 因此（猎鹿,猎鹿）和（猎兔,猎兔）也都是纳什均衡猎人2猎鹿猎兔猎人1猎鹿猎兔4，43，00，33，3猎人2猎兔猎鹿猎人1猎兔猎鹿3，30，33，04，4例子：另一种猎鹿博弈• 猎鹿不是进化稳定的，尽管（猎鹿,猎鹿）是纳什均衡。• 猎兔是进化稳定的，于是（猎兔,猎兔）此时也是纳什均衡。猎人2猎鹿猎兔猎人1猎鹿猎兔4，44，00，43，3猎人2猎兔猎鹿猎人1猎兔猎鹿3，30，44，04，4• 不难看到：如果（S,S）是一个严格纳什均衡（即ac），则S是进化稳定的。反之不一定成立。进化稳定策略和严格纳什均衡• 在一个策略选择中，若每个参与人使用的都是唯一的最佳应对策略（即严格最佳应对），则称这个最佳应对策略组是一个严格纳什均衡。生物体2ST生物体1STa,ac,bb,cd,d• 可以验证：D，H都不是进化稳定的。– 这从（D，D）和（H，H）都不是纳什均衡即可推出进化稳定混合策略• 在有些情况下不存在进化稳定策略• 例子：鹰鸽博弈动物2鸽派D鹰派H动物1鸽派D鹰派H3，35，11，50，0进化稳定混合策略的场景• 一种生物个体，由其基因决定，按照概率分布（p,1-‐p）随机采用两个策略S和T之一。• 想像有一群这样的个体，在互动中繁衍• 突然，其中出现了一种变异：概率为q• 设变异种群在总体中初始占比x（很小），问：原来的种群是进化稳定的吗？– 也就是，在互动中，p种群能比q种群更具适应能力，从而能抑制q种群的蔓延吗？• 若是，则称p是进化稳定混合策略• 我们首先来看两个采用不同混合策略的生物体相遇互动时的收益期望（p,q的函数）• 然后再看根据在总体中的占比，两种生物体随机相遇所导致的收益期望（x,p,q的函数）• 讨论最后这两个期望的大小，判断是否进化稳定S（q）T（1-‐q）第一类生物S（p）T（1-‐p）a,ac,bb,cd,d进化混合策略下的收益第二类生物S（q）T（1-‐q）第一类生物S（p）T（1-‐p）a,ac,bb,cd,d两个采用不同混合策略者相遇的收益第二类生物• 第一种（p策略者）V(p,q)=pqa+p(1-q)b+(1-p)qc+(1-p)(1-q)d• 第二种（q策略者）V(q,p)=qpa+q(1-p)b+(1-q)pc+(1-q)(1-p)d由于收益矩阵的对称性，两者的收益是关于两个变量p，q对称的相遇的概率及其所导致的收益期望• 第一种（初始种群）E1(x,p,q)=(1-‐x)V(p,p)+xV(p,q)• 第二种（变异种群）E2(x,p,q)=(1-‐x)V(q,p)+xV(q,q)第一种1-‐x第二种x第一种第二种V(p,p)V(q,p)V(p,q)V(q,q)在种群混杂情况下不同种群中一个个体的平均收益p是一个进化稳定混合策略的判据：存在y，对任意xy及任意q≠p，有E1(x,p,q)E2(x,p,q)(1-x)V(p,p)+xV(p,q)(1-x)V(q,p)+xV(q,q)进化稳定混合策略的一个要点• 存在y，对任意xy，下面这个不