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

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

随机演化博弈的算法研究1汇报提纲2进化博弈的基本内容我们的研究工作随机进化博弈所面临的理论困难在计算机网络中的应用在复杂网络中的应用我们的未来研究工作汇报提纲2进化博弈的基本内容演化博弈论的产生背景1990-Present1980-19901950-195119441944,J.von.Neumann和Oskar.Morgenstern奠定了经典博弈理论的基础。1950-1951,J.Nash提出了非合作博弈的纳什均衡的概念。二十世纪八十年代，博弈论成为经济学领域当中的通用理论工具，例如：分析不同厂商的合作、联盟、竞争与冲突；工业组织的形成；经济契约的签订；拍卖机制的设计；不对称信息的市场分析等等。演化博弈论的产生背景1990-Present1980-1993标准式博弈标准式博弈由三种元素组成：参与人、纯策略、收益函数纯策略；混合策略是在纯策略上的概率分布。纳什均衡：如果博弈中的任意一个参与人选择的纯策略，都是对其他人选择的纯策略的最优反应，那么这样的纯策略组合为一个标准式博弈的纯策略纳什均衡：严格占优策略：任意给定其他博弈参与人的纯策略选择组合，如果某一个特定的纯策略满足如下条件，则称这个纯策略为严格占优策略：标准式博弈标准式博弈由三种元素组成：参与人、纯策略、收益函数4演化博弈论的产生背景经典博弈论实证缺陷方法缺陷假设缺陷二十世纪八十年代之后，研究工作围绕着修正经典博弈论中的完全理性假设展开研究，并试图为纳什均衡的概念寻找动态结构下的解释。研究表明：经典博弈论在应用中遇到困难，主要是存在三种缺陷：假设缺陷、方法缺陷、实证缺陷。为了解决经典博弈论的以上三种缺陷，从二十世纪九十年代发展了演化博弈论的研究工作。演化博弈论的产生背景经典博弈论实证缺陷方法缺陷假设缺陷二十世5演化博弈论的产生背景假设缺陷：完全理性假设，即假定参与人完全了解其对手的策略集合以及使用每个策略的概率，同时也了解博弈规则与收益结构。参与人也具有通过精确计算推理得到最优策略的能力。但现实中的参与人只具有有限理性(BoundedRationality)。方法缺陷：经典博弈论关注的重点是如何求解博弈的平衡结构，但不能解释博弈的各参与方是如何通过参与博弈而趋向于这些均衡状态的(H.P.Young)。实证缺陷：多数解析型博弈论的预测都是基于理想的假设和精确的数学推导，需要实证的经验规律来充实经典博弈论(ColinCamerer)。演化博弈论的产生背景假设缺陷：完全理性假设，即假定参与人完全6演化博弈论的研究意义演化博弈研究具有普遍意义的有限理性的参与人：惰性、近视、遗传、突变、变异。Kandori,Mailath和Rob(1993)演化博弈不仅关注博弈的稳定结构，还通过引入不同的动态机制研究博弈系统的稳定结构和演化过程之间的关系；演化博弈模型可以和个人学习机制相结合，可以探讨微观层面上参与人的互动和宏观层面上群体的均衡现象之间的关系；演化博弈的假设条件与建模方法更加有利于进行模拟实验来获得实证数据。演化博弈论的研究意义演化博弈研究具有普遍意义的有限理性的参与7演化博弈论的文献综述溯源1798，Malthus的“人口论”；1887，Darwin的“物种起源”；当代演化博弈论在生物学上的起源Lewontin(1961)物种与生存环境Smith与Price(1973)生物之间的有限战争Smith(1982)专著;Taylor和Jonker(1978)个体相互作用内涵的转变策略内涵的转变均衡内涵的转变演化博弈论的文献综述溯源个体相互作用内涵的转变策略内涵的转变8演化稳定策略（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可以是纯策略，也可以是混合策略。微分方程的稳定性马氏链的稳定性演化稳定策略（ESS）用J（p,q）来表示一9相关研究的文献综述确定性的演化博弈模型（微分方程）：Friedman(1991,1998);Hofbauer和Sigmund(1988,1998);Weibull(1995).随机性的演化博弈模型：扰动的生灭过程：Fudenberg和Imhof(2006);Fudenberg等人(2006)。扰动的拟生灭过程：Tadja和Touzene(2003);Q.L.Li(2008)。

扰动图的马氏链：Young(1993)相关研究的文献综述确定性的演化博弈模型（微分方程）：Fri10相关研究的文献综述探讨演化稳定策略的定义和求解方法，以及演化稳定策略与纳什均衡策略之间关系：Friedman(1991,1998);Hofbauer和Sigmund(1988,1998);Samuelson(1997);Weibull(1995).演化博弈和学习机制的交叉研究：Fudenberg和Levine(1997);Foster和Young(2003);Milgrom和Robert(1991);Young(1998,2000,2002).Nash均衡ESS相关研究的文献综述探讨演化稳定策略的定义和求解方法，以及演化11Quan-LinLiConstructiveComputationinStochasticModelswithApplications：TheRG-FactorizationsSpringerChapter11SensitivityAnalysisandEvolutionaryGamesQuan-LinLiConstructiveComput12我们的研究工作针对策略状态空间是离散的、群体的人口规模是有限的、决策具有随机性的演化博弈模型。对两个群体的演化博弈问题，研究了两类模型：两个群体间接相关，博弈只在每个群体内部进行，但是两个群体通过策略相关性因子互相影响；两个群体直接相关，博弈的双方每次分别从两个不同的群体中随机抽取。针对任意多个群体的演化博弈问题，研究了三类模型：间接相关、直接相关、混合相关。多个群体演化博弈问题的建模及其求解演化稳定策略，为演化博弈论在经济学、运筹学领域的广泛应用提供了一定的理论基础；同时，通过一系列数值算例，定性与定量相结合地研究不同建模参数对演化稳定策略分布的影响，为设计实验、提供实验数据的实证支持打下了基础。我们的研究工作针对策略状态空间是离散的、群体的人口规模是有限13演化博弈的基本要素123有限人口-无限人口：离散的策略-连续的策略：参与人的匹配方式：单对模型、总体统计模型、随机匹配模型同质群体的对称二人博弈；不同质群体的非对称二人博弈。自然选择机制（复制子动态）；模仿机制；强化学习机制；最优反应机制；几种机制的混合：虚拟行动。演化博弈的基本要素123有限人口-无限人口：同质群体的对称二14对称的（）演化博弈假设前提：假设1：参与人采用近似最优反应机制规定的决策模式，即参与人对市场的认知程度是有局限性的；假设2：参与人的决策是“近视”的，其决策基于参与人对当前市场结构的认识；假设3：参与人的决策具有不确定性，统称为“变异”。模型描述：两个互相独立的群体P1、P2，人口规模分别为M,N.设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：和：群体P1、P2内部的博弈方式是“随机匹配”，阶段博弈矩阵为：对称的（）演化博弈假设前提：模型描述：和：群体P1、15对称的（）演化博弈给出参与人的期望收益函数：定义参与人选择其第一类策略的转移率为：对称的（）演化博弈给出参与人的期望收益函数：定义参与16两个独立群体的演化博弈假设前提：假设1：参与人采用近似最优反应机制规定的决策模式，即参与人对市场的认知程度是有局限性的；假设2：参与人的决策是“近视”的，其决策基于参与人对当前市场结构的认识；假设3：参与人的决策具有不确定性，统称为“变异”。模型描述：两个互相独立的群体P1、P2，人口规模分别为M,N.设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：和：群体P1、P2内部的博弈方式是“随机匹配”，阶段博弈矩阵为：两个独立群体的演化博弈假设前提：模型描述：和：群体P1、P217两个独立群体的演化博弈给出参与人的期望收益函数：定义参与人选择其第一类策略的转移率为：定义拟生灭过程的状态空间为：两个独立群体的演化博弈给出参与人的期望收益函数：定义参与人选18两个独立群体的演化博弈拟生灭过程的无穷小生成元为：其中：两个独立群体的演化博弈拟生灭过程的无穷小生成元为：其中：19两个独立群体的演化博弈两个独立群体的演化博弈20两个独立群体的演化博弈令如果将这个拟生灭过程的极限平稳分布记作：

其中那么为马氏链的平稳概率向量，并满足.两个独立群体的演化博弈令如果将这个拟生灭过程的极限平稳分布记21演化稳定策略的计算演化稳定策略的计算22策略相关两个互动群体的演化博弈模型描述：两个相对独立的群体P1、P2，人口规模分别为M,N.设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：和：群体P1、P2内部的博弈方式是“随机匹配”，阶段博弈矩阵为：策略相关性因子为：引入策略相关性因子后，参与人策略的转移率定义为：策略相关两个互动群体的演化博弈模型描述：和：群体P1、P223策略相关性两个互动群体的演化博弈无穷小生成元为：其中策略相关性两个互动群体的演化博弈无穷小生成元为：其中24策略相关性两个互动群体的演化博弈其中策略相关性两个互动群体的演化博弈其中25新技术的市场进入研究问题描述：假设构成群体P1的是某工业领域的技术提供方，他们提供相似性很强可以互相替代的成熟技术。构成群体P2的是技术的使用方。当有某种新技术出现时，我们假设群体P1和群体P2均同时获悉将有新的技术进入。群体P2中的参与人有两种战略选择：采用市场上成熟的通用技术，或者采用新技术。面对这种新形势，群体P1中的参与人将试图通过市场营销手段继续维持现有技术的优势地位，而尽量排斥新技术的进入，他们的目标是群体P1中的参与人继续采用流行的成熟技术。则两个群体的策略集合为：两个群体内部博弈的收益矩阵定义新技术的市场进入研究问题描述：假设构成群体P1的是某工业领域26新技术的市场进入研究定义策略相关性因子为：考查以下三组数值算例：新技术的市场进入研究定义策略相关性因子为：考查以下三组数值算27新技术的市场进入研究新技术的市场进入研究28新技术的市场进入研究我们使用策略相关因子分析新技术进入成熟市场问题有如下结论：1、如果技术使用者对于已有技术没有明显偏好、

没有从众心理，同时也不受技术提供方的营销手段影响，则他们有可能根据新技术的先进性

和占优条件来选择新技术。2、如果技术使用者有较强的从众心理，则新技术一般比较难进入市场。新技术的市场进入研究我们使用策略相关因子分析新29两个直接相关群体的演化博弈模型描述：两个互相博弈的群体P1、P2，人口规模分别为M,N.设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：和：群体P1、P2之间的博弈方式是“随机匹配”，互相博弈的收益矩阵为：则收益函数为：两个直接相关群体的演化博弈模型描述：和：群体P1、P2之间30两个直接相关群体的演化博弈转移率定义拟生灭过程的转移率矩阵如下两个直接相关群体的演化博弈转移率定义拟生灭过程的转移率矩阵如31两个直接相关群体的演化博弈其中两个直接相关群体的演化博弈其中32两个直接相关群体的演化博弈如果两个群体中有一个群体具有严格占优的策略，则这个群体的演化稳定策略分布将以概率1收敛于这个严格占优的策略；而另外一个群体的所有参与人将以概率1选择针对其对方群体策略的最优反应策略；如果两个群体的阶段博弈具有两个纯策略的纳什均衡以及一个混合策略的纳什均衡，则两个群体将共同协调收敛于严格风险占优策略构成的纳什均衡；如果两个群体的阶段博弈只具有一个混合策略的纳什均衡，则演化博弈不存在演化稳定策略。两个直接相关群体的演化博弈如果两个群体中有一个群体具有严格占33多个群体的独立演化博弈各个群体的参与人收益函数如下所示：拟生灭过程的转移率定义如下：多个群体的独立演化博弈各个群体的参与人收益函数如下所示：拟生34多个群体的独立演化博弈拟生灭过程的无穷小生成元为：多个群体的独立演化博弈拟生灭过程的无穷小生成元为：35多个群体的独立演化博弈多个群体的独立演化博弈36多个群体策略相关性的演化博弈设策略相关性因子为：把带有策略相关性因子的模型对应的最小生成元矩阵记为：多个群体策略相关性的演化博弈设策略相关性因子为：把带有策略相37多个群体策略相关性的演化博弈根据矩阵推导带有策略相关性的矩阵算法多个群体策略相关性的演化博弈根据矩阵推导带有策略相关性的矩阵38多群体直接博弈的演化博弈多群体直接博弈的演化博弈39多群体直接博弈的演化博弈多群体直接博弈的演化博弈40多群体直接博弈的演化博弈模型多群体直接博弈的演化博弈模型