标签动态信息实时管理软件的研究与开发整理.ppt

《标签动态信息实时管理软件的研究与开发整理.ppt》由会员分享，可在线阅读，更多相关《标签动态信息实时管理软件的研究与开发整理.ppt（50页珍藏版）》请在金锄头文库上搜索。

1、2009年随机图与复杂网络学术会议 李泉林博士 随机演化博弈的算法研究及其在复杂网络中的应用 汇报提纲 2 进化博弈的基本内容我们的研究工作随机进化博弈所面临的理论困难在计算机网络中的应用在复杂网络中的应用我们的未来研究工作 演化博弈论的产生背景 1944 J von Neumann和Oskar Morgenstern奠定了经典博弈理论的基础 1950 1951 J Nash提出了非合作博弈的纳什均衡的概念 二十世纪八十年代 博弈论成为经济学领域当中的通用理论工具 例如 分析不同厂商的合作 联盟 竞争与冲突 工业组织的形成 经济契约的签订 拍卖机制的设计 不对称信息的市场分析等等 标准式博弈

2、标准式博弈由三种元素组成 参与人 纯策略 收益函数纯策略 混合策略是在纯策略上的概率分布 纳什均衡 如果博弈中的任意一个参与人选择的纯策略 都是对其他人选择的纯策略的最优反应 那么这样的纯策略组合为一个标准式博弈的纯策略纳什均衡 严格占优策略 任意给定其他博弈参与人的纯策略选择组合 如果某一个特定的纯策略满足如下条件 则称这个纯策略为严格占优策略 演化博弈论的产生背景 二十世纪八十年代之后 研究工作围绕着修正经典博弈论中的完全理性假设展开研究 并试图为纳什均衡的概念寻找动态结构下的解释 研究表明 经典博弈论在应用中遇到困难 主要是存在三种缺陷 假设缺陷 方法缺陷 实证缺陷 为了解决经典博弈论的

3、以上三种缺陷 从二十世纪九十年代发展了演化博弈论的研究工作 演化博弈论的产生背景 假设缺陷 完全理性假设 即假定参与人完全了解其对手的策略集合以及使用每个策略的概率 同时也了解博弈规则与收益结构 参与人也具有通过精确计算推理得到最优策略的能力 但现实中的参与人只具有有限理性 BoundedRationality 方法缺陷 经典博弈论关注的重点是如何求解博弈的平衡结构 但不能解释博弈的各参与方是如何通过参与博弈而趋向于这些均衡状态的 H P Young 实证缺陷 多数解析型博弈论的预测都是基于理想的假设和精确的数学推导 需要实证的经验规律来充实经典博弈论 ColinCamerer 演化博弈论的研

4、究意义 演化博弈研究具有普遍意义的有限理性的参与人 惰性 近视 遗传 突变 变异 Kandori Mailath和Rob 1993 演化博弈不仅关注博弈的稳定结构 还通过引入不同的动态机制研究博弈系统的稳定结构和演化过程之间的关系 演化博弈模型可以和个人学习机制相结合 可以探讨微观层面上参与人的互动和宏观层面上群体的均衡现象之间的关系 演化博弈的假设条件与建模方法更加有利于进行模拟实验来获得实证数据 演化博弈论的文献综述 溯源1798 Malthus的 人口论 1887 Darwin的 物种起源 当代演化博弈论在生物学上的起源Lewontin 1961 物种与生存环境Smith与Price 1

5、973 生物之间的有限战争Smith 1982 专著 Taylor和Jonker 1978 演化稳定策略 ESS 用J p q 来表示一个物种的策略p遇到策略q时的收益函数 策略p 被称为是一个ESS 如果J p p J p p 或者当J p p J p p 时 J p p J p p ESS可以是纯策略 也可以是混合策略 微分方程的稳定性 马氏链的稳定性 相关研究的文献综述 确定性的演化博弈模型 微分方程 Friedman 1991 1998 Hofbauer和Sigmund 1988 1998 Weibull 1995 随机性的演化博弈模型 扰动的生灭过程 Fudenberg和Imhof

6、2006 Fudenberg等人 2006 扰动的拟生灭过程 Tadja和Touzene 2003 Q L Li 2008 扰动图的马氏链 Young 1993 相关研究的文献综述 探讨演化稳定策略的定义和求解方法 以及演化稳定策略与纳什均衡策略之间关系 Friedman 1991 1998 Hofbauer和Sigmund 1988 1998 Samuelson 1997 Weibull 1995 演化博弈和学习机制的交叉研究 Fudenberg和Levine 1997 Foster和Young 2003 Milgrom和Robert 1991 Young 1998 2000 2002 Na

7、sh均衡 ESS Quan LinLi ConstructiveComputationinStochasticModelswithApplications TheRG Factorizations Springer Chapter11SensitivityAnalysisandEvolutionaryGames 我们的研究工作 针对策略状态空间是离散的 群体的人口规模是有限的 决策具有随机性的演化博弈模型 对两个群体的演化博弈问题 研究了两类模型 两个群体间接相关 博弈只在每个群体内部进行 但是两个群体通过策略相关性因子互相影响 两个群体直接相关 博弈的双方每次分别从两个不同的群体中随机抽取

8、针对任意多个群体的演化博弈问题 研究了三类模型 间接相关 直接相关 混合相关 多个群体演化博弈问题的建模及其求解演化稳定策略 为演化博弈论在经济学 运筹学领域的广泛应用提供了一定的理论基础 同时 通过一系列数值算例 定性与定量相结合地研究不同建模参数对演化稳定策略分布的影响 为设计实验 提供实验数据的实证支持打下了基础 演化博弈的基本要素 有限人口 无限人口 离散的策略 连续的策略 参与人的匹配方式 单对模型 总体统计模型 随机匹配模型 同质群体的对称二人博弈 不同质群体的非对称二人博弈 自然选择机制 复制子动态 模仿机制 强化学习机制 最优反应机制 几种机制的混合 虚拟行动 对称的 演化博弈

9、 假设前提 假设1 参与人采用近似最优反应机制规定的决策模式 即参与人对市场的认知程度是有局限性的 假设2 参与人的决策是 近视 的 其决策基于参与人对当前市场结构的认识 假设3 参与人的决策具有不确定性 统称为 变异 模型描述 两个互相独立的群体P1 P2 人口规模分别为M N 设每一个参与人只具有两个纯策略 则两个群体的策略集分别为 和 群体P1 P2内部的博弈方式是 随机匹配 阶段博弈矩阵为 对称的 演化博弈 给出参与人的期望收益函数 定义参与人选择其第一类策略的转移率为 两个独立群体的演化博弈 假设前提 假设1 参与人采用近似最优反应机制规定的决策模式 即参与人对市场的认知程度是有局限

10、性的 假设2 参与人的决策是 近视 的 其决策基于参与人对当前市场结构的认识 假设3 参与人的决策具有不确定性 统称为 变异 模型描述 两个互相独立的群体P1 P2 人口规模分别为M N 设每一个参与人只具有两个纯策略 则两个群体的策略集分别为 和 群体P1 P2内部的博弈方式是 随机匹配 阶段博弈矩阵为 两个独立群体的演化博弈 给出参与人的期望收益函数 定义参与人选择其第一类策略的转移率为 定义拟生灭过程的状态空间为 两个独立群体的演化博弈 拟生灭过程的无穷小生成元为 其中 两个独立群体的演化博弈 两个独立群体的演化博弈 令 如果将这个拟生灭过程的极限平稳分布记作 其中 那么 为马氏链 的平

11、稳概率向量 并满足 演化稳定策略的计算 策略相关两个互动群体的演化博弈 模型描述 两个相对独立的群体P1 P2 人口规模分别为M N 设每一个参与人只具有两个纯策略 则两个群体的策略集分别为 和 群体P1 P2内部的博弈方式是 随机匹配 阶段博弈矩阵为 策略相关性因子为 引入策略相关性因子后 参与人策略的转移率定义为 策略相关性两个互动群体的演化博弈 无穷小生成元为 其中 策略相关性两个互动群体的演化博弈 其中 新技术的市场进入研究 问题描述 假设构成群体P1的是某工业领域的技术提供方 他们提供相似性很强可以互相替代的成熟技术 构成群体P2的是技术的使用方 当有某种新技术出现时 我们假设群体P

12、1和群体P2均同时获悉将有新的技术进入 群体P2中的参与人有两种战略选择 采用市场上成熟的通用技术 或者采用新技术 面对这种新形势 群体P1中的参与人将试图通过市场营销手段继续维持现有技术的优势地位 而尽量排斥新技术的进入 他们的目标是群体P1中的参与人继续采用流行的成熟技术 则两个群体的策略集合为 两个群体内部博弈的收益矩阵定义 新技术的市场进入研究 定义策略相关性因子为 考查以下三组数值算例 新技术的市场进入研究 新技术的市场进入研究 我们使用策略相关因子分析新技术进入成熟市场问题有如下结论 1 如果技术使用者对于已有技术没有明显偏好 没有从众心理 同时也不受技术提供方的营销手段影响 则他

13、们有可能根据新技术的先进性和占优条件来选择新技术 2 如果技术使用者有较强的从众心理 则新技术一般比较难进入市场 两个直接相关群体的演化博弈 模型描述 两个互相博弈的群体P1 P2 人口规模分别为M N 设每一个参与人只具有两个纯策略 则两个群体的策略集分别为 和 群体P1 P2之间的博弈方式是 随机匹配 互相博弈的收益矩阵为 则收益函数为 两个直接相关群体的演化博弈 转移率定义 拟生灭过程的转移率矩阵如下 两个直接相关群体的演化博弈 其中 两个直接相关群体的演化博弈 如果两个群体中有一个群体具有严格占优的策略 则这个群体的演化稳定策略分布将以概率1收敛于这个严格占优的策略 而另外一个群体的所

14、有参与人将以概率1选择针对其对方群体策略的最优反应策略 如果两个群体的阶段博弈具有两个纯策略的纳什均衡以及一个混合策略的纳什均衡 则两个群体将共同协调收敛于严格风险占优策略构成的纳什均衡 如果两个群体的阶段博弈只具有一个混合策略的纳什均衡 则演化博弈不存在演化稳定策略 多个群体的独立演化博弈 各个群体的参与人收益函数如下所示 拟生灭过程的转移率定义如下 多个群体的独立演化博弈 拟生灭过程的无穷小生成元为 多个群体的独立演化博弈 多个群体策略相关性的演化博弈 设策略相关性因子为 把带有策略相关性因子的模型对应的最小生成元矩阵记为 多个群体策略相关性的演化博弈 根据矩阵 推导带有策略相关性的矩阵

15、算法 多群体直接博弈的演化博弈 多群体直接博弈的演化博弈 多群体直接博弈的演化博弈模型 多群体直接博弈的演化博弈 多群体直接博弈的演化博弈 多群体直接博弈的演化博弈 我们研究工作的总结 将一个多群体进化博弈模型可以归结为一个多维的QBD过程 面临两个实质性的理论困难 1 怎样写出多维的QBD过程 2 怎样计算扰动的平稳概率向量 以及对于扰动求极限 哈佛大学D Fudenberg教授等人解决了对称多策略进化博弈模型 TakayukiOsogami CarnegieMellonUniversity研究了一些特殊的多维QBD过程 进化博弈在计算机网络中的应用 无线网络的能量管理 无线网络的拥挤控制协议设计 无线网络中用户的偏好行为 无线网络的自适应路径策略 复制子动态 微分方程 进化博弈在计算机网络中的应用 基于非合作博弈的无线网络路由机制研究计算机学报 2009年1期 进化博弈在复杂网络中的应用 鹰鸽模型 囚徒困境模型 循环博弈模型 性别战模型 斗鸡模型 智能猪模型 进化博弈模型 进化空间博弈模型 复杂网络基本性质 进化博弈在我国汽车工业中的应用 谢谢大家