随机图与复杂网络（PPT讲稿）随机演化博弈的算法研究及其在复杂网络中的应用

2009年随机图与复杂网络学术会议 随机演化博弈的算法研究 及其在复杂网络中的应用 李泉林博士

2009年随机图与复杂网络学术会议 李泉林 博士 随机演化博弈的算法研究 及其在复杂网络中的应用

汇报提纲 口进化博弈的基本内容 口我们的研究工作 口随机进化博弈所面临的理论困难 口在计算机网络中的应用 口在复杂网络中的应用 口我们的未来研究工作

汇报提纲 2  进化博弈的基本内容  我们的研究工作  随机进化博弈所面临的理论困难  在计算机网络中的应用  在复杂网络中的应用  我们的未来研究工作

演化博弈论的产生背景 口1944,J.von. Neumann和 Oskar Morgenstern奠定了经典博弈理论的基础。 1944 口1950-1951,J.Nash提出了非合作博弈的纳 什均衡的概念。 1950-195 口二十世纪八十年代,博弈论成为经济学领 域当中的通用理论工具,例如:分析不同 厂商的合作、联盟、竞争与冲突;工业组 织的形成;经济契约的签订;拍卖机制的 1980-1990 设计;不对称信息的市场分析等等。 1990-Present

演化博弈论的产生背景 1990-Present 1980-1990 1950-1951 1944  1944, J. von. Neumann和Oskar. Morgenstern奠定了经典博弈理论的基础。  1950-1951, J. Nash提出了非合作博弈的纳 什均衡的概念。  二十世纪八十年代，博弈论成为经济学领 域当中的通用理论工具，例如：分析不同 厂商的合作、联盟、竞争与冲突；工业组 织的形成；经济契约的签订；拍卖机制的 设计；不对称信息的市场分析等等

标准式博弈 口标准式博弈由三种元素组成:参与人、纯策略、收益函数 C纯策略; 混合策略是在纯策略上的概率分布。 口纳什均衡:如果博弈中的任意一个参与人选择的纯策略,都是对其他人 选择的纯策略的最优反应,那么这样的纯策略组合为一个标准式博弈的 纯策略纳什均衡: Vs1≠S,l1(S1,S)≥l1(S,S) 口严格占优策略:任意给定其他博弈参与人的纯策略选择组合,如果某 个特定的纯策略满足如下条件,则称这个纯策略为严格占优策略: Vs,Vs,+S,u (S,S>u(S,S_)

标准式博弈  标准式博弈由三种元素组成：参与人、纯策略、收益函数  纯策略；  混合策略是在纯策略上的概率分布。  纳什均衡：如果博弈中的任意一个参与人选择的纯策略，都是对其他人 选择的纯策略的最优反应，那么这样的纯策略组合为一个标准式博弈的 纯策略纳什均衡： * * * * , ( , ) ( , ). i i i i i i i i s s u s s u s s    − −  严格占优策略：任意给定其他博弈参与人的纯策略选择组合，如果某 一个特定的纯策略满足如下条件，则称这个纯策略为严格占优策略： ' * * ' , , ( , ) ( , ) i i i i i i i i i s s s u s s u s s     − − −

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

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

演化博弈论的产生背景 口假设缺陷:完全理性假设,即假定参与人完全了解其对手 的策略集合以及使用每个策略的概率,同时也了解博弈规 则与收益结构。参与人也具有通过精确计算推理得到最优 策略的能力。但现实中的参与人只具有有限理性( Bounded Rationality 口方法缺陷:经典博弈论关注的重点是如何求解博弈的平衡 结构,但不能解释博弈的各参与方是如何通过参与博弈而 趋向于这些均衡状态的(HP. Young)。 口实证缺陷:多数解析型博弈论的预测都是基于理想的假设 和精确的数学推导,需要实证的经验规律来充实经典博弈 论( Colin camerer)

演化博弈论的产生背景  假设缺陷：完全理性假设，即假定参与人完全了解其对手 的策略集合以及使用每个策略的概率，同时也了解博弈规 则与收益结构。参与人也具有通过精确计算推理得到最优 策略的能力。但现实中的参与人只具有有限理性(Bounded Rationality)。  方法缺陷：经典博弈论关注的重点是如何求解博弈的平衡 结构，但不能解释博弈的各参与方是如何通过参与博弈而 趋向于这些均衡状态的(H.P. Young)。  实证缺陷：多数解析型博弈论的预测都是基于理想的假设 和精确的数学推导，需要实证的经验规律来充实经典博弈 论(Colin Camerer)

演化博弈论的研究意义 口演化博弈研究具有普遍意义的有限理性的参与人:惰性、 近视、遗传、突变、变异。 Kandori, Mailath和Rob(193) 口演化博弈不仅关注博弈的稳定结构,还通过引入不同的动 态机制研究博弈系统的稳定结构和演化过程之间的关系 口演化博弈模型可以和个人学习机制相结合,可以探讨微观 层面上参与人的互动和宏观层面上群体的均衡现象之间的 关系; 口演化博弈的假设条件与建模方法更加有利于进行模拟实验 来获得实证数据

演化博弈论的研究意义  演化博弈研究具有普遍意义的有限理性的参与人：惰性、 近视、遗传、突变、变异。Kandori, Mailath和Rob (1993)  演化博弈不仅关注博弈的稳定结构，还通过引入不同的动 态机制研究博弈系统的稳定结构和演化过程之间的关系；  演化博弈模型可以和个人学习机制相结合，可以探讨微观 层面上参与人的互动和宏观层面上群体的均衡现象之间的 关系；  演化博弈的假设条件与建模方法更加有利于进行模拟实验 来获得实证数据

演化博弈论的文献综述 口溯源 c1798, Malthus的“人口论” cx1887, Darwin的“物种起源”; 口当代演化博弈论在生物学上的起源 Lewontin(1961)物种与生存环境 Smith与Prce(1973)生物之间的有限战争 Smith1982)专著; Taylor和 Jonker(1978) 个体相互作用内涵的转变 策略内涵的转变 均衡内涵的转变

演化博弈论的文献综述  溯源  1798，Malthus的“人口论”；  1887，Darwin的“物种起源”；  当代演化博弈论在生物学上的起源 Lewontin (1961) 物种与生存环境 Smith与Price(1973)生物之间的有限战争 Smith(1982) 专著; Taylor和Jonker(1978) 个体相互作用内涵的转变 策略内涵的转变 均衡内涵的转变

演化稳定策略(ESS) 用J(,q)来表示一个物种的策略p遇到策略q时 的收益函数。 策略ρ被称为是一个ESS,如果「微分方程的稳定性 J(p*p*))J(p,p*) 或者当J(p*,p*)=J(Pp,p*)时, 马氏链的稳定性 J(p*,p)〉J(p,p)。 Ess可以是纯策略,也可以是混合策略

演化稳定策略（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); Weibu(1995) 口随机性的演化博弈模型: 扰动的生灭过程: Fudenberg和ImhO(2006); Fudenberg等人(2006) 扰动的拟生灭过程: Nadja和 Couzens(2003);Q.L Li(2008)。 扰动图的马氏链: Young(1993)

相关研究的文献综述  确定性的演化博弈模型（微分方程）： Friedman(1991,1998); Hofbauer和Sigmund(1988, 1998); Weibull(1995).  随机性的演化博弈模型： 扰动的生灭过程：Fudenberg和Imhof(2006); Fudenberg等人(2006)。 扰动的拟生灭过程：Tadja和Touzene(2003); Q.L. Li(2008)。 扰动图的马氏链：Young(1993)