随机演化博弈算法研究及其在复杂网络中应用共49页文档

格式：ppt
大小：6.17 MB
文档页数：49

下载文档原格式

演化博弈论PPT课件

纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。
纳什均衡可以通过划线法得出
13
纳什均衡和演化稳定（1）
a
X b
a 0，0
Y b
1，1
1，1
0，0
策略b是否是演化稳定的？有一个规模为E的策略a入侵
策略b的平均适应度: (1 E)*0 E *1 E 策略a的平均适应度: (1 E)*1 E*0 1 E
Y/q(1p)2p0
p1/3
18
N-群体的演化稳定策略
定义1：策略组合 x{x1,x2,..x.n,}是纳什均衡，如果x是演化稳定策略，如果对于任意的策略组合 yx 存在某个 (0,1) 使得对于所有的
(0,
)
和y(1)x,有
ui(xi, i) ui(yi, i)
i I
i I
定义2：策略组合x是演化稳定策略，当且仅当x是一个严格的纳什均衡。
:是一个与突变策略y有关的常数，称之为侵入界限； εy + (1 − ε)x:表示选择进化稳定策略群体与选择突变策略群
体所组成的混合群体。
16
演化稳定策略的定义（2）
Definition 2: 对任意的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是演化稳定策略
➢ 自演化博弈论诞生之日起，它就逐渐的被人们用来分析生物、经济等领域的问题。
1. Selten Reinhard．A Note on Evolutionary Stable Strategies in Asymmetric Animal Conflicts [J]． Journal of Theoretical Biology， 1980，(84)．

演示文稿第八章演化博弈理论及其应用

第七章演化博弈理论及其应用
本节课程内容概述：
第一节传统博弈理性假设的局限第二节演化博弈理论的兴起
第三节演化博弈理论的有限理性假设和基本分析过程第四节演化博弈理论的不同动态模仿模型
第五节演化博弈理论的均衡分析方法第六节演化博弈理论的最新进展和局限性
——这是人类思想史上最气势磅礴的名言之一，它刻在康德的墓碑上，出自康德的《实践理性批判》最后一章。
2
第2页，共70页。
恒星的演化
新恒星的诞生
主序星（太阳）
红巨星
一颗恒星从诞生到死亡，要经过几百万年甚至上百亿年的时间。
恒星是太空星云在引力作用下坍缩而成，坍缩使内部变热，温度升高直到发生核聚变反应，释放热能并产生向外的压力以支持恒星对抗进一步坍缩。一颗恒星一旦开始燃烧核
19
第19页，共70页。
[资料夹] 社会学家格拉诺威特（Mark Granovetter）
中国象棋大师许银川 PK
浪潮天梭服务器
16
2006年08月15日，浪潮杯”中国象棋人机大战再次展开，两场对决中，均战成平局。
第16页，共70页。
第七章演化博弈理论及其应用
第一节传统博弈理性假设的局限性
作为一种数学分析方法，传统博弈对参与者的“理性”要求非常苛刻：目标理性(主观理性):参与者追求自身利益的最大化(经济学理性的内涵)
70年代他与彭罗斯一起证明了著名的奇性定理，为此他们共同获得了
1988年的沃尔夫物理奖。
9
第9页，共70页。
[资料夹]生命的演化 ——达尔文进化论
伟大的生物学家、进化论的创立者查理·达尔文，生于1809年，英国人。达尔文在剑桥大学获得学位后年仅22岁便乘“贝格尔”号随船考察。1859年，达尔文出版10《物种起源》。

复杂网络上的演化博弈研究_杨涵新

上海理工大学学报
４卷第２期第３Ｊ．ＵｎｉｖｅｒｓｉｔｏｆＳｈａｎｈａｉｆｏｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｙｇｇｙＶｏｌ．３４Ｎｏ．２２０１２
摘要：在自然界和人类社会中，合作行为是普遍存在的．如何理解自私个体之间合作行为的产生和目前，演化博弈理论被认为是研究合作行为的一个最有力的维持吸引了来自各领域科学家的注意．手段．随着复杂网络理论的迅速发展，复杂网络上的演化博弈受到广泛的关注．本文拟就复杂网络上的演化博弈研究做一综述，并对未来的研究提出展望．关键词：复杂网络；演化博弈；合作中图分类号：Ｎ９４文献标志码：Ａ
ｙｓｒｉｍｘ，＋ｙ＝－ ∑ ｋｘ＋１ｋｙ＋１ｉ＝０ｋｉ＋１这里的ｉ代表节点＝０ｓｉ的策ｙ，ｉ是与ｙ相连的节点略（ｓｓｉ＝１表示节点ｉ是合作者，ｉ＝０表示节点ｉ是
，力图解释上
演化博弈理论着重述经典博弈论无法解答的问题．研究有限理性的个体如何随着时间的推移在不断地重复博弈过程中去实现收益最大化．在自然界和人类社会中，合作行为普遍存在，如狮群协作捕猎、人类社会大规模地生产活动等等．从世界的和平与发展、地球的环境保护大的方面来看，但是在一个群体中，都离不开各国之间的相互协作．并不是所有的个体都会采取合作的行为．由于个体有些人会采取不合作（背叛）存在一定的自私心理，的行为．如何理解自私个体之间合作行为的产生和

复杂网络中的博弈

2．小世界网络上的囚徒窘境博弈
2001 年Abramson 和Kuperman 在期刊Physical Review E 第63 卷首先研究了WS 小世界网络上的囚徒窘境博弈。在他们的模型中，个体采用确定性策略更新规则：每个个体采用邻居中收益最高者的策略。底层的交互网络是一个由一维规则环进行断开重连得到的WS 小世界网络。
第八章复杂网络中的博弈
目录
8.1 引言 8.2 博弈论概述 8.3 复杂网络中的演化博弈 8.4 复杂网络的抗毁性分析 8.5 复杂网络的抗毁性优化和修复策略
8.1 引言
广义上讲，复杂网络中的博弈问题包括：网络的攻击和安全防护（包括抗毁性分析和优化）、网络中的流行病（病毒、谣言）传播和抑制、网络的同步和牵制控制、网络的拥塞和拥塞控制、网络的级联故障和故障预防控制、网络中个体的合作和竞争
这种情况下达到的精炼贝叶斯纳什均衡解及其求解过程一般也比较繁难，因此在此不做过多介绍。
8.3 复杂网络的演化博弈
8.3.1 演化博弈简介 8.3.2 演化网络博弈概述 8.3.3 基于囚徒窘境博弈模型的演化网络博弈 8.3.4 基于铲雪博弈模型的演化网络博弈
8.3.1 演化博弈简介
1973 年生态学家Smith 和Price 结合生物进化论与经典博弈论在研究生态演化的基础上提出演化博弈论的基本均衡概念—演化稳定策略（evolutionarily stablestragegy，ESS），标志着演化博弈理论的诞生。此后，演化博弈理论逐渐被广泛地用于生态学、社会学和经济学等领域。
如果参与博弈的局中人不能或者不被允许达成有约束力的合作协议，或者虽达成协议但不被遵守，则把这种博弈称为非合作博弈。
1. 合作博弈与非合作博弈

复杂网络演化博弈理论研究综述

复杂网络演化博弈理论研究综述一、本文概述Overview of this article随着信息技术的飞速发展，复杂网络作为一种描述现实世界中各种复杂系统的有效工具，已经引起了广泛关注。

而在复杂网络中，演化博弈理论则为我们提供了一种深入理解和分析网络动态行为的重要视角。

本文旨在全面综述复杂网络演化博弈理论的研究现状和发展趋势，以期能为相关领域的学者和研究人员提供有益的参考和启示。

With the rapid development of information technology, complex networks have attracted widespread attention as an effective tool for describing various complex systems in the real world. In complex networks, evolutionary game theory provides us with an important perspective to deeply understand and analyze the dynamic behavior of networks. This article aims to comprehensively review the research status and development trends of complex network evolutionary game theory, in order to provide useful reference and inspiration for scholars and researchers in related fields.本文首先回顾了复杂网络和演化博弈理论的基本概念和研究背景，阐述了两者结合的必要性和重要性。

接着，文章从网络结构、博弈规则、动态演化等多个方面对复杂网络演化博弈理论进行了深入的分析和讨论。

随机演化博弈的算法研究

演化博弈论的文献综述

溯源 1798，Malthus的“人口论”； 1887，Darwin的“物种起源”；

当代演化博弈论在生物学上的起源 Lewontin (1961) 物种与生存环境 Smith与Price(1973)生物之间的有限战争 Smith(1982) 专著; Taylor和Jonker(1978)
0 A0 ( ) 1 A1 ( ) 2 A2 ( ) 1 A0 ( )
A12 ( )
A02 ( ) A2M 2 ( ) A1M 2 ( ) A2M 1 ( ) A0M 2 ( ) A1M 1 ( ) A2M ( )
. A0M 1 ( ) A1M ( )
* k lim k .
0
两个独立群体的演化博弈

假设前提：
假设1：参与人采用近似最优反应机制规定的决策模式，即参
与人对市场的认知程度是有局限性的；假设2：参与人的决策是“近视”的，其决策基于参与人对当前市场结构的认识；假设3：参与人的决策具有不确定性，统称为“变异”。
a1 (k , 0) 2 (0) 2 2 (1) a ( k ,1) (1) 1 2 2 (2) a1 (k , 2) (2) A1k ( ) , 2 2 ( N 1) a1 (k , N 1) ( N 1) 2 ( N ) a ( k , N ) 1

严格占优策略：任意给定其他博弈参与人的纯策略选择组合，如果某一个特定的纯策略满足如下条件，则称这个纯策略为严格占优策略：
si , si' si* , ui (si* , si ) ui (si' , si )

复杂网络上的演化博弈

ｔｅｎｔｅｅｏｕｉｎｒｌｔｂｅｓｒｔｇｎｅｌａｏｙａｃｓｅｔｂｉｈｄｗｅｈｖｌｔａｉｓａｌｔａｅｙａｄｒｐｉｔｒｄｎｍｉｓｉｓａｌｅ．Ｔｈｎ，ｔｅｓｏｈｓｉｖｌ－ｏｙｃｓｅｈｔｃａｔｅｏｕｃ
ｔｏｎｒｙｍｉｓｏｉｉｅｗｅｌｍｉｄｐｏｌｔｏｎｄｔｉｅａｉｓｐｔｈｅｄｅｅｍｉｉｔｃｒｐｉａｏ — ｉａｙｄｎａｃｆｆｎｔｌ— ｘｅｐｕａｉｎｓａｈｅｒｒｌｔｏｎｈｉＯｔｔｒｎｓｉｅｌｃｔｒｄｙ— ‘ ｎｍｉｓａｅｐｒｓｎｅａｃｒｅｅｔｄ．Ｓｏｅｒｓｌｓｏｎｆｘｄｐｒｂａｉｉｙａｄｔｍｅａｅａｓｖｎｍｅｕｔｉｅｏｂｌｔｎｉｒｌｏｇｉｅ．Ｆｕｔｒｒ，ｓｍｅｒｃｎｒｈｅｍｏｅｏｅｅｔｒｓｌｓｏｖｌｉｎａｙｇｍｅｎｃｅｕｔｆｅｏｕｔｏｒａｓｏｏｍｐｌｘｎｔｅｅｗｏｒｕｃｓｓｌ— ｒｄａｃｌ－ｒｅｎｅｗｏｋｓａｅｉｒ－ｋｓｓｈａｍａｌｗｏｌｎｄｓａｅｆｅｔｒｒｎｔｏｄｕｅｃｄ．Ｆｉａｌｎｌｙ，ｕｎｅｏｌｅｅｒｌｍｓ，ｆｔｅｒｓａｃｉｅｔｏ，ａｏｓｉｅａｐｌａｉｒａｏｒｒｓｖｄｏｐｎｐｏｂｅｕｕｒｅｅｒｈｄｒｃｉｎｓｎｄｐｓｂｌｐｉｔｏｎａｅｓｆｃｅｏｕｔｏｎｒａｓＯｏｍｐｌｘｎｅｗｏｋｒｉｔｄｏ．ｖｌｉａｙｇｍｅｎｃｅｔｒｓａｅｐｏｎｅｕｔＫｅｗｏｄ：ｖｌｔｏｎｒｍｅ；ｒｐｉａｏｙｍｉｓｖｌｔｏｎｒｌｔｂｅｓｒｔｇｙｒｓｅｏｕｉａｙｇａｅｌｃｔｒｄｎａｃ；ｅｏｕｉａｉｙｓａｌｔａｅｙ；ｃｍｐｌｘｎｅｗｏｒ；ｆ－ｏｅｔｋｓｉ

演化博弈

基于历史记忆的雪堆博弈
1、模型规则将N个个体放置与某种网络的节点上每一轮相互连接的个体同时博弈个体的总收益是根据收益矩阵与所有邻居
博弈收益之和一轮博弈结束后个体选择最佳策略更新个体对于最佳策略具有记忆性，选择某个
策略取决于该策略在记忆中的数量
假设个体的记忆长度有限，长度为M，即上一时刻到M时刻以前的历史最佳策略，个体依据自身的历史记忆进行决策：
其中,pc为选择策略c的概率，NC和ND分别为策略C和D的数量个体不断更新记忆，不断重复博弈，整个系统就会演化下去。
2、二维网格上的演化博弈
（1）主要研究变量
合作频率 fc
记忆长度M 收益参数r
（2）二维网格模拟
网络规模为1000，初始策略C和D各占50%, 并且在网络中随机分配
每个个体的初始记忆随机分配，并且个体记忆对系统最终稳定行为没有任何影响
2、雪堆博弈
假设铲雪的代价为c, 每个人的好处量化为b，b>c,那么双方收益矩阵为：
合作
B 背叛
合作 A
背叛
b-c/2, b-c/2 b-c ,b
b ,b-堆博弈中，遇到背叛时选择合作的收益大于双方都背叛的收益，遇到背叛则选择合作；个体的最佳策略取决于对手的策略；相比囚徒困境，合作在雪堆博弈中更容易涌现。
复杂网络上的演化博弈
主要内容
1、群体博弈简介 2、基于历史记忆的雪堆博弈 3、演化博弈动力学与网络结构的共同演化
群体博弈简介
1、囚徒困境
囚徒的选择策略有：合作（坦白）、欺骗（抵赖）
我们可以得到的博弈矩阵为：
囚徒b
T>R>P>S
合作
欺骗
2R>T+S合作

随机演化博弈的算法研究及其在复杂网络中的应用

0 A0 ( ) 1 A1 ( ) 2 A2 ( ) 1 A0 ( )
A12 ( )
A02 ( ) A2M 2 ( ) A1M 2 ( ) A2M 1 ( ) A0M 2 ( ) A1M 1 ( ) A2M ( )
. A0M 1 ( ) A1M ( )
标准式博弈
• 标准式博弈由三种元素组成：参与人、纯策略、收益函数
纯策略；混合策略是在纯策略上的概率分布。

纳什均衡：如果博弈中的任意一个参与人选择的纯策略，都是对其他人选择的纯策略的最优反应，那么这样的纯策略组合为一个标准式博弈的纯策略纳什均衡：
* * si si* , ui (si* , s ) u ( s , s i i i i ).
• 演化博弈研究具有普遍意义的有限理性的参与人：惰性、近视、遗传、突变、变异。Kandori, Mailath和Rob (1993) • 演化博弈不仅关注博弈的稳定结构，还通过引入不同的动态机制研究博弈系统的稳定结构和演化过程之间的关系； • 演化博弈模型可以和个人学习机制相结合，可以探讨微观层面上参与人的互动和宏观层面上群体的均衡现象之间的关系； • 演化博弈的假设条件与建模方法更加有利于进行模拟实验来获得实证数据。
为了解决经典博弈论的以上三种缺陷，从二十世纪九十年代发展了演化博弈论的研究工作。
方法缺陷

假设缺陷
演化博弈论的产生背景
• 假设缺陷：完全理性假设，即假定参与人完全了解其对手的策略集合以及使用每个策略的概率，同时也了解博弈规则与收益结构。参与人也具有通过精确计算推理得到最优策略的能力。但现实中的参与人只具有有限理性(Bounded Rationality)。
其中：

复杂网络上的演化博弈及其学习机制与演化动态综述

Overview of Evolutionary Games and Their Learning Mechanisms and Evolutionary Dynamics on
Complex Networks
作者：王先甲[1]
作者机构： [1]武汉大学经济与管理学院
出版物刊名：阅江学刊
页码： 70-84页
年卷期： 2021年第3期
主题词：博弈论;演化博弈;复杂网络;复杂网络上的演化博弈;学习机制;演化动态
摘要：博弈论是在完全理性假设下研究多人相互作用的选择理论,演化博弈是在有限理性假
设下研究群体在相互作用过程中基于个体学习与选择的群体特征演化动态理论,网络上的演化博
弈是研究结构化群体的演化博弈理论.本文回顾了基于完全理性的博弈论,在对有限理性新的理解的基础上介绍了演化博弈理论的发展历程,着重论述了复杂网络理论与演化博弈理论交叉衍生的
复杂网络上的演化博弈的研究现状与发展趋势,特别分析和总结了演化博弈中最基本、最核心的
个体学习机制与群体演化动态特征,由此揭示演化博弈中从个体微观行为到群体宏观特征的演化
机理.。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。