2009年随机图与复杂网络学术会议 .ppt

1、2009年随机图与复杂网络学术会议李泉林 博士随机演化博弈的算法研究及其在复杂网络中的应用 汇报提纲2进化博弈的基本内容我们的研究工作随机进化博弈所面临的理论困难在计算机网络中的应用在复杂网络中的应用我们的未来研究工作演化博弈论的产生背景1990-Present1980-19901950-19511944 1944, J. von. Neumann和Oskar. Morgenstern奠定了经典博弈理论的基础。 1950-1951, J. Nash提出了非合作博弈的纳什均衡的概念。 二十世纪八十年代，博弈论成为经济学领域当中的通用理论工具，例如：分析不同厂商的合作、联盟、竞争与冲突；工业组织的

2、形成；经济契约的签订；拍卖机制的设计；不对称信息的市场分析等等。标准式博弈 标准式博弈由三种元素组成：参与人、 、 ； 合 在 的概 分 。 纳什均衡：如 博弈中的 参与人 的 ， 对 人的 的 应， 的 组合为 标准式博弈的纳什均衡：* * * *, ( , ) ( , ).i i i i i i i is s u s s u s s- -“ 钩 ： 定 博弈参与人的 组合，如 定的 如，currency1称 为 ： * * , , ( , ) ( , )i i i i i i i i is s s u s s u s s- - -“ “ 演化博弈论的产生背景经典博弈论实证缺陷方法缺陷假设缺

3、陷 二十世纪八十年代“，研究工作fifl经典博弈论中的 理设 研究，为纳什均衡的概念” 的 。研究：经典博弈论在应用中困难， 在三种 ：设 、 、 。 为了经典博弈论的 三种 ，二十世纪 十年代 了演化博弈论的研究工作。演化博弈论的产生背景 设 ： 理设， 定参与人 了 对 的 合 用 的概 ，同 了博弈 currency1与 。参与人 具 通 计算 理 的 。 中的参与人 具 理(Bounded Rationality。 ：经典博弈论的 如 博弈的 衡 ， 不 博弈的 参与 如 通 参与博弈均衡 的(H.P. Young)。 ： 析博弈论的 基 理的设和 的 学 ， 的经 来充 经典博弈论(

4、Colin Camerer)。演化博弈论的研究 义 演化博弈研究具 普遍 义的 理的参与人：惰、近视、遗传、突变、变异。Kandori, Mailath和Rob (1993) 演化博弈不仅博弈的稳定 ，还通 引入不同的机制研究博弈系统的稳定 和演化 程间的系； 演化博弈模可和 人学习机制相合，可探讨微观层面 参与人的互和宏观层面 群体的均衡 象间的系； 演化博弈的设与建模更加 利 进行模拟 来获 据。演化博弈论的文献综述 溯源 1798，Malthus的“人口论”； 1887，Darwin的“物种起源”； 当代演化博弈论在生物学 的起源Lewontin (1961) 物种与生环境Smith与P

5、rice(1973)生物间的 战争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(2006); Fudenberg等人(2006)。扰的拟生灭 程：Tadja和Touzene(2003); Q.L. Li(2008)。扰的马氏链：Young(1993)