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

1、随机演化博弈的算法研究随机演化博弈的算法研究及其在复杂网络中的应用及其在复杂网络中的应用 汇报提纲2进化博弈的进化博弈的基本内容基本内容我们的我们的研究工作研究工作随机进化博弈所面临的随机进化博弈所面临的理论困难理论困难在在计算机网络计算机网络中的应用中的应用在在复杂网络复杂网络中的应用中的应用我们的我们的未来研究工作未来研究工作演化博弈论的产生背景1990-Present1980-19901950-19511944 1944, J. von. Neumann和和Oskar. Morgenstern奠定了奠定了经典博弈理论的基础经典博弈理论的基础。1950-1951, J. Nash提出了非合

2、作博弈的提出了非合作博弈的纳纳什均衡什均衡的概念。的概念。二十世纪八十年代，博弈论成为二十世纪八十年代，博弈论成为经济学领经济学领域当中的通用理论工具，域当中的通用理论工具，例如：分析不同例如：分析不同厂商的合作、联盟、竞争与冲突；工业组厂商的合作、联盟、竞争与冲突；工业组织的形成；经济契约的签订；拍卖机制的织的形成；经济契约的签订；拍卖机制的设计；不对称信息的市场分析等等。设计；不对称信息的市场分析等等。标准式博弈 标准式博弈由三种元素组成：标准式博弈由三种元素组成：参与人参与人、纯策略纯策略、收益函数收益函数纯策略纯策略；混合策略混合策略是在纯策略上的概率分布。是在纯策略上的概率分布。纳什

3、均衡纳什均衡：如果博弈中的任意一个参与人选择的纯策略，都是对其他人：如果博弈中的任意一个参与人选择的纯策略，都是对其他人选择的纯策略的最优反应，那么这样的纯策略组合为一个标准式博弈的选择的纯策略的最优反应，那么这样的纯策略组合为一个标准式博弈的纯策略纳什均衡：纯策略纳什均衡：*,(,)(,).iiiiiiiissussus s严格占优策略严格占优策略：任意给定其他博弈参与人的纯策略选择组合，如果某：任意给定其他博弈参与人的纯策略选择组合，如果某一个特定的纯策略满足如下条件，则称这个纯策略为严格占优策略：一个特定的纯策略满足如下条件，则称这个纯策略为严格占优策略：*,(,)( ,)iiiiiii

4、iisss u s su s s演化博弈论的产生背景二十世纪八十年代之后，研究工作围二十世纪八十年代之后，研究工作围绕着修正经典博弈论中的绕着修正经典博弈论中的完全理性假完全理性假设设展开研究，并试图为展开研究，并试图为纳什均衡纳什均衡的概的概念寻找念寻找动态结构下的解释动态结构下的解释。研究表明：。研究表明：经典博弈论在应用中遇到困难，主要经典博弈论在应用中遇到困难，主要是存在三种缺陷：是存在三种缺陷：假设缺陷假设缺陷、方法缺方法缺陷陷、实证缺陷实证缺陷。为了解决经典博弈论的以上三种缺陷，为了解决经典博弈论的以上三种缺陷，从从二十世纪九十年代发展了二十世纪九十年代发展了演化博弈演化博弈论的论

5、的研究工作。研究工作。演化博弈论的产生背景 假设缺陷假设缺陷：完全理性假设，即假定参与人完全了解其对手：完全理性假设，即假定参与人完全了解其对手的策略集合以及使用每个策略的概率，同时也了解博弈规的策略集合以及使用每个策略的概率，同时也了解博弈规则与收益结构。参与人也具有通过精确计算推理得到最优则与收益结构。参与人也具有通过精确计算推理得到最优策略的能力。但现实中的参与人只具有策略的能力。但现实中的参与人只具有有限理性有限理性(Bounded Rationality)。 方法缺陷方法缺陷：经典博弈论关注的重点是如何求解博弈的平衡：经典博弈论关注的重点是如何求解博弈的平衡结构，但不能解释博弈的各参

6、与方是如何通过参与博弈而结构，但不能解释博弈的各参与方是如何通过参与博弈而趋向于这些均衡状态的趋向于这些均衡状态的(H.P. Young)。 实证缺陷实证缺陷：多数解析型博弈论的预测都是基于理想的假设：多数解析型博弈论的预测都是基于理想的假设和精确的数学推导，需要实证的经验规律来充实经典博弈和精确的数学推导，需要实证的经验规律来充实经典博弈论论(Colin Camerer)。演化博弈论的研究意义 演化博弈研究具有普遍意义的演化博弈研究具有普遍意义的有限理性有限理性的参与人：的参与人：惰性惰性、近近视视、遗传遗传、突变突变、变异。变异。Kandori, Mailath和和Rob (1993) 演

7、化博弈不仅关注博弈的演化博弈不仅关注博弈的稳定结构稳定结构，还通过引入，还通过引入不同的动态不同的动态机制机制研究博弈系统的研究博弈系统的稳定结构稳定结构和和演化过程演化过程之间的关系；之间的关系； 演化博弈模型可以和演化博弈模型可以和个人学习机制个人学习机制相结合，可以探讨相结合，可以探讨微观层微观层面上参与人的互动面上参与人的互动和和宏观层面上群体的均衡现象宏观层面上群体的均衡现象之间的关系之间的关系； 演化博弈的假设条件与建模方法更加有利于进行演化博弈的假设条件与建模方法更加有利于进行模拟实验模拟实验来来获得获得实证数据实证数据。演化博弈论的文献综述 溯源溯源1798，Malthus的的

8、“人口论人口论”；1887，Darwin的的“物种起源物种起源”； 当代演化博弈论当代演化博弈论在生物学上的起源在生物学上的起源 Lewontin (1961) 物种与生存环境物种与生存环境 Smith与与Price(1973)生物之间的有限战争生物之间的有限战争 Smith(1982) 专著专著; Taylor和和Jonker(1978)个体相互作用个体相互作用内涵的转变内涵的转变策略策略内涵的转变内涵的转变均衡均衡内涵的转变内涵的转变演化稳定策略（演化稳定策略（ESSESS） 用用J（p, q）来表示一个物种的策略来表示一个物种的策略p遇到策略遇到策略q时时的收益函数。的收益函数。 策略策

9、略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). 随机性随机性的演化博弈模型：的演化博弈模型：

10、 扰动的生灭过程：扰动的生灭过程：Fudenberg和和Imhof(2006); Fudenberg等人等人(2006)。 扰动的拟生灭过程：扰动的拟生灭过程：Tadja和和Touzene(2003); Q.L. Li(2008)。 扰动图的马氏链：扰动图的马氏链：Young(1993)相关研究的文献综述 探讨探讨演化稳定策略的定义和求解方法演化稳定策略的定义和求解方法，以及，以及演化演化稳定策略与纳什均衡策略之间关系稳定策略与纳什均衡策略之间关系：Friedman(1991,1998); Hofbauer和和Sigmund(1988, 1998); Samuelson(1997); Weib

11、ull(1995). 演化博弈和学习机制的交叉研究演化博弈和学习机制的交叉研究：Fudenberg和和Levine(1997); Foster和和Young(2003); Milgrom和和Robert(1991); Young(1998, 2000,2 002).Nash均衡均衡ESSQuan-Lin LiConstructive Computation in Stochastic Models with Applications：The RG-FactorizationsSpringerChapter 11 Sensitivity Analysis and Evolutionary Gam

12、es我们的研究工作 针对策略状态空间是离散的、群体的人口规模是有限的、决策具有随机性针对策略状态空间是离散的、群体的人口规模是有限的、决策具有随机性的演化博弈模型。的演化博弈模型。 对两个群体的演化博弈问题，研究了两类模型：对两个群体的演化博弈问题，研究了两类模型：两个群体两个群体间接相关间接相关，博弈只在每个群体内部进行，但是两个群体通过策略，博弈只在每个群体内部进行，但是两个群体通过策略相关性因子互相影响；相关性因子互相影响；两个群体两个群体直接相关直接相关，博弈的双方每次分别从两个不同的群体中随机抽取。，博弈的双方每次分别从两个不同的群体中随机抽取。 针对任意多个群体的演化博弈问题，研究

13、了三类模型：针对任意多个群体的演化博弈问题，研究了三类模型：间接相关、直接相间接相关、直接相关、混合相关关、混合相关。 多个群体演化博弈问题的建模及其求解演化稳定策略，为演化博弈论在经多个群体演化博弈问题的建模及其求解演化稳定策略，为演化博弈论在经济学、运筹学领域的广泛应用提供了一定的理论基础；同时，通过一系列济学、运筹学领域的广泛应用提供了一定的理论基础；同时，通过一系列数值算例，定性与定量相结合地研究不同建模参数对演化稳定策略分布的数值算例，定性与定量相结合地研究不同建模参数对演化稳定策略分布的影响，为设计实验、提供实验数据的实证支持打下了基础。影响，为设计实验、提供实验数据的实证支持打下

14、了基础。演化博弈的基本要素123有限人口-无限人口：离散的策略-连续的策略：参与人的匹配方式：单对模型、总体统计模型、随机匹配模型同质群体的对称二人博弈；不同质群体的非对称二人博弈。自然选择机制（复制子动态）；模仿机制；强化学习机制；最优反应机制；几种机制的混合：虚拟行动。对称的（对称的（ ）演化博弈）演化博弈 假设前提：假设假设1：参与人采用近似近似最优反应机制规定的决策模式，即参与人对市场的认知程度是有局限性的；假设假设2：参与人的决策是“近视”的，其决策基于参与人对当前市场结构的认识；假设假设3：参与人的决策具有不确定性，统称为“变异”。模型描述：两个互相独立的群体P1、P2，人口规模分

15、别为M, N. 设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：11112,Sss22122,Sss和：群体P1、P2 内部的博弈方式是“随机匹配”，阶段博弈矩阵为：12,abacAAcdbd2 2对称的（对称的（ ）演化博弈）演化博弈 给出参与人的期望收益函数给出参与人的期望收益函数：2 211( )( )( ( ),saz tb Mz tfz tM12( )( )( ( ).scz td Mz tfz tM定义参与人选择其第一类策略的转移率为定义参与人选择其第一类策略的转移率为：1112( )max( )( ),0,0,1,.1.ssififiiM1211( )max( )( )

16、,0,1,2,.ssififiiM *01*1*QN *00 ,1 ,2 ,; lim.Nkk2 2两个独立群体的演化博弈 假设前提：假设假设1：参与人采用近似近似最优反应机制规定的决策模式，即参与人对市场的认知程度是有局限性的；假设假设2：参与人的决策是“近视”的，其决策基于参与人对当前市场结构的认识；假设假设3：参与人的决策具有不确定性，统称为“变异”。模型描述：两个互相独立的群体P1、P2，人口规模分别为M, N. 设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：11112,Sss22122,Sss和：群体P1、P2 内部的博弈方式是“随机匹配”，阶段博弈矩阵为：1122121

17、122,ababAAcdcd两个独立群体的演化博弈 给出参与人的期望收益函数给出参与人的期望收益函数：1111 111( )( )( ( ),sa z tb Mz tfz tM1211 111( )( )( ( ).sc z td Mz tfz tM2122222( )( )( ( );sa z tb Nz tfz tN2222222( )( )( ( ).sc z tdNz tfz tN定义参与人选择其第一类策略的转移率为定义参与人选择其第一类策略的转移率为：11121111( )max( )( ),0,0,1,.1.ssififiiM12111111( )max( )( ),0,1,2,.

18、ssififiiM21222222( )max( )( ),0,0,1,.1.ssjfjfjjN22212222( )max( )( ),0,1,2,. .ssjfjfjjN定义拟生灭过程的状态空间为定义拟生灭过程的状态空间为：(0,0),(0,1),.(0,);(1,0),(1,1),.(1,);.;(,0),(,1),.(,)NNMMM N 两个独立群体的演化博弈 拟生灭过程的无穷小生成元为：拟生灭过程的无穷小生成元为：001011121022221022221011121021( )( )( )( )( )( )( )( ).( )( )( )( )( )( )( )( )MMMMMMM

19、MAAAAAAAAQAAAAAAAA其中：其中：1101( )( )( ),( )mmmAm1121( )( )( ).( )nnnAn两个独立群体的演化博弈21221221122121( ,0)(0)(1)( ,1)(1)(2)( ,2)(2)( ),(1)( ,1)(1)()( ,)ka ka ka kANa k NNNa k N 11221( , )( )( )( )( ),0,0.a k lkkllkMlN 两个独立群体的演化博弈1( ),MMUA111102( )( )( );kkkkkUAAUA110( ) .kkkRAU011( )( ),( ),.,( ),( ),MM 011

20、( )( ),( ),.,( ),( ).NNkkkkk 0011( )( )( )( )( ).( ),0.kkvRRRkM 0( )v0U000( )0( )1vUve令令如果将这个拟生灭过程的极限平稳分布记作：如果将这个拟生灭过程的极限平稳分布记作：其中其中那么那么为马氏链为马氏链的平稳概率向量，并满足的平稳概率向量，并满足.演化稳定策略的计算 *0lim,0kkkN策略相关两个互动群体的演化博弈模型描述模型描述：两个相对独立的群体两个相对独立的群体P1、P2，人口规模分别为，人口规模分别为M, N. 设每一设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：个参与人只具有两个纯策

21、略，则两个群体的策略集分别为：11112,Sss22122,Sss和：和：群体群体P1、P2 内部的博弈方式是内部的博弈方式是“随机匹配随机匹配”，阶段博弈矩阵，阶段博弈矩阵为：为：1122121122,ababAAcdcd策略相关性因子为策略相关性因子为：1122( , )( , ),( , ),( , ),( , ),0,0D i jD i j D i jD i j D i jiMjN 引入策略相关性因子后，参与人策略的转移率定义为引入策略相关性因子后，参与人策略的转移率定义为：111( , )( )( , ),0,0;i jiD i jiMjN 111( , )( )( , ),0,0i

22、 jiD i jiMjN 222( , )( )( , ),0,0;i jjD i jiMjN 222( , )( )( , ),0,0i jjD i jiMjN 策略相关性两个互动群体的演化博弈 无穷小生成元为：无穷小生成元为：001011121022221022221011121021( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )MMMMMMMMAAAAAAAAQAAAAAAAA1101( ,0)( ,1)( );( , )mmmAm n1121( ,0)( ,1)( ).( , )nnnAn n其中其中策略相关性两个互动群体的演化博弈21

23、221221122121( ,0)( ,0)( ,1)( ,1)( ,1)( ,2)( ,2)( ,2)( )( ,1)( ,1)( ,1)( ,)( ,)ka kkka kkka kkAk Na k Nk Nk Na k N 其中其中11221( , )( , )( , )( , )( , )a k lk lk lk lk l11112222( )( , )( )( , )( )( , )( )( , )k D k lk Dk ll D k ll Dk l新技术的市场进入研究 问题描述：假设构成群体问题描述：假设构成群体P1的是某工业领域的技术提供方，他们提供相的是某工业领域的技术提供方，他

24、们提供相似性很强可以互相替代的成熟技术。构成群体似性很强可以互相替代的成熟技术。构成群体P2的是技术的使用方。当的是技术的使用方。当有某种新技术出现时，我们假设群体有某种新技术出现时，我们假设群体P1和群体和群体P2均同时获悉将有新的技均同时获悉将有新的技术进入。群体术进入。群体P2中的参与人有两种战略选择：采用市场上成熟的通用技中的参与人有两种战略选择：采用市场上成熟的通用技术，或者采用新技术。面对这种新形势，群体术，或者采用新技术。面对这种新形势，群体P1中的参与人将试图通过中的参与人将试图通过市场营销手段继续维持现有技术的优势地位，而尽量排斥新技术的进入，市场营销手段继续维持现有技术的优

25、势地位，而尽量排斥新技术的进入，他们的目标是群体他们的目标是群体P1中的参与人继续采用流行的成熟技术。则两个群体中的参与人继续采用流行的成熟技术。则两个群体的策略集合为：的策略集合为：两个群体内部博弈的收益矩阵定义两个群体内部博弈的收益矩阵定义11.02.5;0.50A25.02.08.06.0A新技术的市场进入研究 定义策略相关性因子为：定义策略相关性因子为：1( , )(1) (1) ;ijiijiD i jdd1( , )(1) (1) .ijiijiD i jdd2( , )(1) (1) ;ijijjjD i jdd2( , )(1) (1) .ijijjjD i jdd考查以下三组

26、数值算例：考查以下三组数值算例：1( , )(1) (1) ;ijiijiD i jdd1( , )(1) (1) .ijiijiD i jdd2( , )(1) (1) ;ijijjjD i jdd1( , )(1) (1) ;ijiijiD i jdd1( , )(1) (1) .ijiijiD i jdd2( , )(1) (1) .ijijjjD i jdd2( , )(1) (1) ;ijijjjD i jdd1( , )(1) (1) ;ijiijiD i jdd1( , )(1) (1) .ijiijiD i jdd0246800.10.20.30.40.50.60.70.80.

27、91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.91新技术的市场进入研究0246800.10.20.30.40.50.60.70.80.9102468100

28、0.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.

29、70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.2

30、0.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.

31、91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30.40.50.60.70.80.910246800.10.20.30.40.50.60.70.80.91024681000.10.20.30

32、.40.50.60.70.80.91新技术的市场进入研究 我们使用策略相关因子分析新技术进入成熟市我们使用策略相关因子分析新技术进入成熟市场场问题有如下结论：问题有如下结论：1、如果技术使用者对于已有技术没有明显、如果技术使用者对于已有技术没有明显偏好偏好、 没有没有从众心理从众心理，同时也不受技术提供方的，同时也不受技术提供方的营销营销 手段手段影响，则他们有可能根据新技术的先进性影响，则他们有可能根据新技术的先进性 和占优条件来选择新技术。和占优条件来选择新技术。2、如果技术使用者有较强的、如果技术使用者有较强的从众心理从众心理，则新技术，则新技术 一般比较难进入市场。一般比较难进入市场。

33、两个直接相关群体的演化博弈模型描述模型描述：两个互相博弈的群体两个互相博弈的群体P1、P2，人口规模分别为，人口规模分别为M, N. 设每一设每一个参与人只具有两个纯策略，则两个群体的策略集分别为：个参与人只具有两个纯策略，则两个群体的策略集分别为：11112,Sss22122,Sss和：群体群体P1、P2 之间的博弈方式是之间的博弈方式是“随机匹配随机匹配”，互相博弈的收，互相博弈的收益矩阵为：益矩阵为：1122121122,.ababAAcdcd 则收益函数为则收益函数为：1121211( )( )( ( );sa z tb Nz tfz tN11 21212( )( )( ( ).sc

34、z td Nz tfz tN22 12121( )( )( ( );sa z tb Mz tfz tM22 12122( )( )( ( ).sc z tdMz tfz tM两个直接相关群体的演化博弈 转移率定义转移率定义11121111( )max( )( ),0,0,1,. ,2;ssjfjfjjNjP12111111( )max( )( ),0,0,1,2,. ,2.ssjfjfjjNjP21222222( )max( )( ),0,0,1,.,1;ssififiiMiP22212222( )max( )( ),0,1,2,. ,1.ssififiiNiP拟生灭过程的转移率矩阵如下拟生灭

35、过程的转移率矩阵如下001011121022221022221011121021( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )MMMMMMMMAAAAAAAAQAAAAAAAA两个直接相关群体的演化博弈其中其中21221221122121( ,0)( )( )( ,1)( )( )( ,2)( )( ).( )( ,1)( )( )( ,)ka kkka kkka kkAka k Nkka k N 1101(0)(1)( );()mAN1121(0)(1)( ).()nAN两个直接相关群体的演化博弈 如果两个群体中有如果两个群体中有一个群体具有

36、严格占优的策略一个群体具有严格占优的策略，则这个，则这个群体的演化稳定策略分布将以概率群体的演化稳定策略分布将以概率1收敛于这个严格占优收敛于这个严格占优的策略；而另外一个群体的所有参与人将的策略；而另外一个群体的所有参与人将以概率以概率1选择选择针针对其对方群体策略的对其对方群体策略的最优反应策略最优反应策略；如果两个群体的阶段博弈具有两个纯策略的纳什均衡以及如果两个群体的阶段博弈具有两个纯策略的纳什均衡以及一个混合策略的纳什均衡，则两个群体将一个混合策略的纳什均衡，则两个群体将共同协调共同协调收敛于收敛于严格风险占优策略构成的纳什均衡严格风险占优策略构成的纳什均衡；如果两个群体的阶段博弈只

37、具有一个混合策略的纳什均衡，如果两个群体的阶段博弈只具有一个混合策略的纳什均衡，则演化博弈则演化博弈不存在演化稳定策略不存在演化稳定策略。多个群体的独立演化博弈1122121122,.,.KKKKKabababAAAcdcdcd各个群体的参与人收益函数如下所示：1( )( )( ( );kkkkkkkksa z tb Mz tfz tM2( )( )( ( ).kkkkkkkksc z tdMz tfz tM拟生灭过程的转移率定义如下：12( )max( )( ),0,0,1,.1.1,2,3;kkkkkksskififiiMk21( )max( )( ),0,1,2,.1,2,3.kkkkk

38、ksskififiiMk多个群体的独立演化博弈多个群体的独立演化博弈 拟生灭过程的无穷小生成元为：111(1)0001(1)12102(1)2220( )2(1)22201(1)1210(1)2( )( )( )( )( )( )( )( )( ).( )( )( )( )( )( )( )( )KKKKMKMMMKMMMKMQAAQAAQAQAQAAQAAQ1101( )( )( ).( )mmmAm1121( )( )( ).( )nnnAn多个群体的独立演化博弈多个群体策略相关性的演化博弈1122121122,.,KKKKKabababAAAcdcdcd 设策略相关性因子为：1212(

39、, ,.,),( , ,.,),1,2,3,.,mmiiKKDDi iiDi iimK把带有策略相关性因子的模型对应的最小生成元矩阵记为：111(1)00,0,1(1)12,1,0,2(1)22,2,0,( )2(1)22,2,0,1(1)12,1,0,(1)2,( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )KDDKDDDKDDDKDMKMDMDDMKMDMDDMKDM DQAAQAAQAQAQAAQAAQ多个群体策略相关性的演化博弈 根据矩阵()( )KQ推导带有策略相关性的矩阵()( )KDQ算法1(1)(1)(3),11( )0,0

40、,1,2,.(1)(1)KMMDi jKjQiMM 多群体直接博弈的演化博弈11212122( ,.,.,).( ,.,.,)kkKkkkKxs sssAxs sss11111( ( )( ,., ,.,);kkkkKksfz tfiiii11122( ( )( ,., ,.,).kkkkKksfz tfiiii多群体直接博弈的演化博弈12( ,)max( ,)( ,),0;kkkkkkkkkkkkssiifiifii21( ,)max( ,)( ,),0.kkkkkkkkkkkkssiifiifii111(1)0001(1)12102(1)2220()2(1)22201(1)1210(1)2

41、( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )KKKKMKMMMKMMMKMQAAQAAQAQAQAAQAAQ多群体直接博弈的演化博弈模型11,211,20121,2( ,0,)( ,1,)( );( ,)miiAMi11,2,311,2,311,2131,2,3( ,0,0,)( ,0,1,)( ,0,).( ,0,)iiiMi多群体直接博弈的演化博弈11,211,2211,2( ,0,)( ,0,)( );( ,0,)niiAi11,2,311,2,311,2131,2,3( ,0,0,)( ,0,1,)( ,0,).( ,0,)ii

42、iMi多群体直接博弈的演化博弈多群体直接博弈的演化博弈(1)1(1)211,2(1)1(1)211,2(1)2(1)31,21,2,3(1)2(1)21,21,2( ):( ,)( ):( , ,),( ):( ,)( ):( , ,),( ):( , ,)( ):( , , ,),( ):( , ,)( ):( , , ,KKkKKkKKkKKkQiQkiQiQkiQxiQk xiQxiQk xi,3),(1)1(1)1212(1)1(1)1212( ):( , )( ):( , ),( ):( , )( ):( , ).KKKKkKKKKkQx xQk x xQx xQk x x 我们研究

43、工作的总结 将一个多群体进化博弈模型可以归结为一个多维将一个多群体进化博弈模型可以归结为一个多维的的QBD过程，过程，面临两个实质性的理论困难面临两个实质性的理论困难: （1）怎样写出多维的）怎样写出多维的QBD过程；过程； （2）怎样计算扰动的平稳概率向量，以及对于扰）怎样计算扰动的平稳概率向量，以及对于扰动求极限。动求极限。 哈佛大学哈佛大学D. Fudenberg教授等人解决了教授等人解决了对称多策略对称多策略进化博弈模型进化博弈模型。 Takayuki Osogami（）Carnegie Mellon University 研究了一些研究了一些特殊的多维特殊的多维QBD过程过程。进化博

44、弈在计算机网络中的应用无线网络的能量管理无线网络的能量管理无线网络的拥挤控制协议设计无线网络的拥挤控制协议设计无线网络中用户的偏好行为无线网络中用户的偏好行为无线网络的自适应路径策略无线网络的自适应路径策略复制子动态复制子动态微分方程进化博弈在计算机网络中的应用基于非合作博弈的无线网络路由机制基于非合作博弈的无线网络路由机制研究研究 计算机学报计算机学报, 2009年1期进化博弈在复杂网络中的应用鹰鸽模型鹰鸽模型囚徒困境模型囚徒困境模型循环博弈模型循环博弈模型性别战模型性别战模型斗鸡模型斗鸡模型智能猪模型智能猪模型进化博弈模型进化博弈模型进化空间博弈模型进化空间博弈模型复杂网络复杂网络基本性质基本性质进化博弈在我国汽车工业中的应用