进化博弈论读书心得



《进化博弈论读书心得》由会员分享,可在线阅读,更多相关《进化博弈论读书心得(7页珍藏版)》请在装配图网上搜索。
1、进化博弈论读书报告 汪波 1973年,梅拉德·史密斯和普瑞斯将博弈论的思想引入到生物演化的分析中,二人提出了进化稳定策略(ESS),随着1978年, Taylor和Jonker发现了进化稳定策略和复制动力学之间的关系,标志着进化博弈理论的诞生,因为与复制动力学之间的关系,进化稳定策略也因此成为进化博弈理论最经典的概念。1982年,梅拉德·史密斯出版了《演化与博弈论》,该书揭示动物群体的行为变化的动力学机制,也因此书他被称为进化博弈论之父,1995年,Weibul
2、l著作了《Evolutionary Game Theory》,2009年初,Sandholm 出版了《Population Game and Evolutionary Dynamics》专著,这篇读书报告是在看了这三本著作的很少的一部分内容之下,理解其中一些浅显的内容后完成的。 一、进化稳定策略最初的模型 进化博弈理论是将博弈论引入到生物学背景下产生的,当生物的特定表现型的适应度依赖于群体中的频率分布时,进化博弈论就是从这个角度来思考生物演化的问题的一种方法,古典博弈中,参与者根据自利的原则表现出理性行为,但在生物进化的背景下是不合适的,由此,理性原则被群体的动态性和稳定性取代,而自利
3、原则则被达尔文的适应度所取代。在一些重要的假设下,将会得到博弈的一个新形式解:进化稳定策略。它是这样一个策略,如果整个群体的每个成员都采取这个策略,那么在自然选择的作用下,不存在一个具有突变特征的策略能够侵犯这个种群。 最初的简化的模型由梅拉德·史密斯和普瑞斯给出,他和普瑞斯也给出了进化稳定策略的数学式的描述定义,这一模型的本质特征是假设该群体有无限大的规模,繁衍以无性生殖的方式进行,竞争只在两个不存在任何差异的对手间展开即是成对的竞争。生物学中价值是指两个动物为了争夺资源而增加的或者减少的达尔文适应度。故我们用适应度作为最后个体的收益的衡量,假想在这个无限的种群中,有两个策略、,每一个成员
4、都采取这两个策略之一,且策略的选择是随机的,在有竞争前个体的初始适应度为,再假设整个群体中选择的概率为,、分别表示选择相应策略带来的适应度,而表示个体选择策略而对手选择时的收益,其他等表示类同的意义。 若每一个个体都参与到竞争当中,则有 (1-1) (1-2) 稳定的策略具有下列性质:整个种群中几乎所有的个体都采取了这个策略,且这些个体的 适应度必将高于竞争对手或者可能出现的突变异种的适应度,否则竞争对手或者产生的突变 异种会侵害整个种群,以致种群的削弱或者毁
5、灭等,这时此策略便不可能是稳定的策略。若 是进化稳定策略,则,且,所以当,有 (1-3) 当时有 (1-4) 满足上述条件(1-3)、(1-4)的策略就称为进化稳定策略,而上述的两个条件1-3、1-4也被认为是判别的标准条件。 上述的策略是在纯策略情形下考虑的,当策略是从一个可能策略集合中随机的选择而构成的,此时的策略称为混合策略。此时若是一个混合进化稳定策略,假设等是该群体的纯策略,赋予这些纯策略非零的概率值,那么必须满足如下条件:
6、(1-5) 保证所有纯策略的回报是相等的,群体中的个体才不会选择偏离的策略。此时起满足的条件和上述是相同的形式。 二、对称博弈 1.对称博弈的定义 两人对称博弈对于许多进化博弈论内容而言是基础的,而且,许多进化博弈论中的深刻见解都可以从二人对称博弈这种特殊情形中得到,这也是单独列出对称博弈内容的主要原因。 一个二人对称博弈,可假设有两个玩家的位置,每个位置上有相同的纯策略,而任意的策略的支付则依赖于玩家所选的位置,因此有如下的定义: 博弈称为二人对称博弈,如果,且对于任意的有成立。 该对称博弈要求两个位置上的支付矩阵是互为转置的,即若为第一人的支付矩阵
7、,为第二个人的支付矩阵,则,即 则 也即有若,则。 例如:囚徒困境情形就是一个非常好的对称博弈的例子。 上述是在纯策略下的情形,现在描述混合策略情形:,用表示策略集上的一个概率分布,即为该博弈的一个混合策略,用表示其混合策略集,则混合策略组合空间为,此时任意的纯策略在对手选择混合策略时的支付为。 2.对称博弈的特点 对称博弈是一种很特殊情形,它有自己的特征,一是对称博弈的最优回应对应和通常的最优回应对应不一样,通常的是策略组合空间到策略组合空间之间的映射,而是策略集到策略集之间的映射,即 (1-6) 这是对称博弈策略集相同所决定的。
8、二是对称博弈有更特殊的形式:双对称博弈。此时在其他条件满足下当且仅当时称为双对称博弈。 例如:协调博弈就是一个很好的双对称博弈的例子。 三是对称博弈的纳什均衡的形式也有所不同,对称博弈具有不对称的纳什均衡,也具有对称的纳什均衡。策略组合被称为对称博弈的纳什均衡,当且仅当,其中,这与通常的纳什均衡的定义是一致的,用表示纳什均衡集合。当时我们称该纳什均衡为对称的,此时纳什均衡可以表示为 (1-7) 对称的情形下,它本质是一个策略空间,不同于往常的策略组合空间,当然,对称博弈的纳什均衡并非都要求是对称的,但也可以证明任意的对
9、称博弈一定能够存在至少一个对称的纳什均衡,即对于任意的二人有限对称博弈,。 例如:鹰-鸽博弈、石头-剪刀-布等博弈都是具有混合策略均衡的且是对称的。 以鹰鸽博弈为例:不是一般地,下面支付矩阵为一方甲的支付矩阵: 其中表示一定价值的资源适应度,在此表示获得的支付,双方甲、乙都选择鹰策略则各自获得,表示双方争斗产生的适应度的下降或者说是损失,若甲选择鹰策略乙选择鸽策略,则甲获得全部资源而乙获得,若都选鸽策略则平分资源。当时,则鹰策略是纳什均衡,因为此时双方都宁愿冒着受伤的风险获得大于零的资源适应度,而当时,则存在对称的混合纳什均衡,假设此混合策略组合为,则要满足
10、 解得,则知,故。 四是二人对称博弈的分类,根据支付我们可以将对称博弈分为四类.以 为例。将第一列减去,第二列减去变形得 再令得正规化形式 构造如下所示的图: I II III IV 用表示该图中平
11、面上的点,若当点在图中的北西象限时,我们说此时的对称博弈是第I类的,当若当点在图中的北东象限时,我们说此时的对称博弈是第II类的,当若当点在图中的南西象限时,我们说此时的对称博弈是第III类的,当若当点在图中的南东象限时,我们说此时的对称博弈是第IV类的。 很容易发现,当博弈是第I类或者是第IV类的时候,分别有和,两个的支付一正一负,此时博弈都存在严格占优的策略,故都存在纯策略纳什均衡。 第I类的解为,纳什均衡集合为和。 第IV类的解为,纳什均衡集合为和。 当博弈是第II类或者第III类时,支付函数值同号,此时不仅仅存在对称的纯策略的纳什均衡,也存在对称的混合策略纳什均衡。 第II类
12、博弈,二者支付都为正数。有两个对称的严格占优的纳什均衡,还有一个对称的混合策略纳什均衡,故它的解为,纳什均衡集合为 ,。 其中。这一类博弈常见的例子如调和博弈。 第IV类博弈,二者的支付都为负数,没有严格占优的策略。它的解为,纳什均衡集合为 ,。 其中。 这一类常见的博弈如鹰鸽博弈(的情形)。 三、对称博弈下看进化稳定策略 1.进化稳定策略的定义 结论仍然集中二人对称博弈上,,纯策略集为,混合策略集为,当选择而选择时,参与者的支付矩阵为,则此时支付函数为。 在对称博弈的下,进化稳定策略有两种等价的定义。由于对称博弈可以很好的解释单群体博弈,所以此时是在单群体情形下来讨
13、论,假设有一个数量规模很大的群体,里面出现一组规模很小的突变者,他们选择的策略集是相同的且成对竞争,群体主体现在的策略为,这组小规模的突变者选择策略,并假设这组小规模突变族所占群体的份额为。同时假设群体里每个代理人都参与竞争,每个代理人选择现任策略的概率为,选择突变策略的概率为,在此时的生物群体下的支付可以看作与其中一个代理人选择策略时竞争产生的支付。那么相应的,代理人选择现任策略的支付函数值为,同理有。在这样的生物情形下,直觉告诉我们,群体要能抵抗外来的入侵或者应对突变者的袭击,那么现任策略所能得到的支付必须高于入侵者或者突变者的策略的支付。因此,进化稳定策略除了本文第一部分的定义形式外,有
14、另外一种等价的定义形式: 若策略是进化稳定策略(),如果存在实数,使得对于所有的,都满足下面的不等式条件: (3-1) 其中。 策略在任意的策略下的最优回应集合为。此时若是该博弈的进化稳定策略,则它必须满足,即必须是该博弈的纳什均衡即,但还需要满足另外的条件才能保证是进化稳定的策略,由此可知,若用表示博弈的进化稳定策略集合,那么有,由进化稳定策略的含义可以更详细的表示的形式如下: (3-2) 由此我们又回到了进化稳定策略的第一种定义的形式: 称是该博弈的进化稳定策略,若满足如下两个条件:
15、 (3-3) 当存在满足时有。 ( 3-4) 这两个条件就如我们一开始所说的是判断一个策略是不是进化稳定策略的标准。 2.两种等价定义的作用 将上述(3-1)式在定义计数函数:下可写为,且其等于 由是进化稳定的可知当足够小且时,,由于函数是双线性的, 可写为: 当固定时,计数函数是一个关于的仿射函数,它的截距为斜率为,如下图所示: 1 斜率为
16、 1 条件(3-3)等价于截距是非负的,而条件(3-4)则等价于当截距为零时斜率是正值。因此当两个条件都满足时,则存在使得对于所有的都有成立,因此。对于进化稳定策略说明两个地方:一是并非所有的博弈都有进化稳定策略,有部分博弈是没有进化稳定策略的,例如石头--剪刀--布博弈就不具有进化稳定策略,不然随着时间的推移,就没有玩的意义了,因为玩家知道那个策略是对自己最好的。二是进化稳定性并不意味着群体平均支付是最优的。 3.进化稳定策略集的结构 从3-1、3-3可知,一个进化稳定策略的支撑不可能包含另外一个进化稳定策略的支撑,更进一步说不可能包含对称的纳什均衡策
17、略的支撑。例如:假设,存在 ,那么,因为,所以,所以,与矛盾。因此有如下推论: 若且,那么。 另外,如果博弈的一个进化稳定策略是本质的(即完全混合策略),那么它是该博弈的唯一的进化稳定策略,而且在有限博弈中,支集是有限的,所以进化稳定策略也总是有限的,甚至可能为零。因此有下面的引理: 集合是有限的,且如果,那么。 4. 与非合作博弈中的、等之间的关系 (1)从进化稳定策略的定义可以知道一个博弈的进化稳定策略必定是该博弈的纳什均衡,反之则不然,即。 (2)劣策略肯定不会是进化稳定的,因为它本身不可能成为纳什均衡,弱劣策略也不会是进化稳定策略,就算它是纳什均衡集合中的元
18、素,也不可能成为进化稳定的。例如若且为弱劣策略,则存在,使得,与进化稳定策略的标准中的第二个矛盾,故若是弱劣策略,则。 (3)由上可知,若,则策略组合是该博弈的纳什均衡,即,且是占优的纳什均衡,因此是对纳什均衡的一种精炼,它是完美的纳什均衡即有如下的结论:若,则。由此,可以知道:。 (4) 若,那么是一个真平衡。 5. 的特征 (1)进化稳定策略的第一个特征便是“稳定”,它能保证该群体在遭遇其他物种入侵或者群体内发生突变个体时维持群体的稳定,从支付角度看就是进化稳定策略所能获得的支付优于其他的策略,从3-1可明显看出。 (2)的第二个特征是它存在统一的入侵屏障。即存在一个入侵屏障
19、使得对于任意的有3-1成立。 (3)的第三个特征是它是局部占优的,且如果该进化稳定策略是本质的(完全混合策略),那么它还是全局占优的。 6、条件削弱下的进化稳定的标准 (1)中度稳定策略 称为一个中度稳定策略(),如果对于任意一个,存在使得对于任意的都有下式成立: 它与进化稳定策略相差仅在于前者只能是严格大于而后者可以取到等号成立。所以有第二种等价的方式定义,也是最初梅拉德·史密斯给出的定义形式.,只需将进化稳定策略中的第二个条件弱化即可,。 综上,进化稳定策略和中度稳定策略都是博弈的纳什均衡的一种精炼,在群体博弈下也可以看成是对群体博弈纳什均衡的一种选择。
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 专题党课讲稿:以高质量党建保障国有企业高质量发展
- 廉政党课讲稿材料:坚决打好反腐败斗争攻坚战持久战总体战涵养风清气正的政治生态
- 在新录用选调生公务员座谈会上和基层单位调研座谈会上的发言材料
- 总工会关于2025年维护劳动领域政治安全的工作汇报材料
- 基层党建工作交流研讨会上的讲话发言材料
- 粮食和物资储备学习教育工作部署会上的讲话发言材料
- 市工业园区、市直机关单位、市纪委监委2025年工作计划
- 检察院政治部关于2025年工作计划
- 办公室主任2025年现实表现材料
- 2025年~村农村保洁员规范管理工作方案
- 在深入贯彻中央8项规定精神学习教育工作部署会议上的讲话发言材料4篇
- 开展深入贯彻规定精神学习教育动员部署会上的讲话发言材料3篇
- 在司法党组中心学习组学习会上的发言材料
- 国企党委关于推动基层党建与生产经营深度融合工作情况的报告材料
- 副书记在2025年工作务虚会上的发言材料2篇