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