（运筹学与控制论专业论文）基于启发搜索的纳什均衡算法研究.pdf

摘要 摘要 纳什均衡是非合作博弈的核心理论，而在策略型有限策略博 弈中寻找的纳什均衡解至今仍是一个挑战性课题在这篇论文 中，我们首先回顾了博弈论的历史和纳什均衡算法发展现状然 后应用搜索博弈支持集和方程组求解技术，提出了一个计算单一 和全部纳什均衡解的启发搜索算法通过全面的测试集进行算法 测试，结果表明该算法与现有的几个纳什均衡算法相比具有优异 的性能 关键词：博弈论；纳什均衡；启发算法 a b s t m c l a b s t r a c t n a s he q u i l j b r i u mc o n s m u t e sac e n t r a ls o l u t i o nc o n c 印ti n n o n c o o p e r a t i v eg a m et h e o r yt 1 1 et a s ko fd e t e c t i n gn a s he q u j l i b d a o faf j n i t es t r a t e g j cg a m er e ma ：i n sac h a l l e n 西n gp m b l e mu p 。t o - d a t e i nt h i sp a p e r ，w ef j r s t 百v ear e v i e wo nt h eh i s t o r yo fg a m et h e o r ya n d t h ec u e n ts t a t eo ft h ea nd fm e t h o d sf b rn u m e r i c a ic o m p u t a t i o no f n a s he q u i l i 嘶a 1 1 l c nw ep r o p o s ean e wa l g o r i t l l mf o ras 砌p l ea i l d a l ln a s he q u i l i b r i ab yn s i n gh e n f i s t i cs e a r c hi ng 锄es u p p o f t sa n dt h e s o l u t i o nt e c t l n i q u e so fp 0 1 y n o m i a le q u a t i o ns y s t e m s 舢s o ，b ym a k i n g u s eo fac o m p r e h e l l s i v et e s t b e d w es h 吣rt h a tt l l i sa l g o r i t h mp e r f o 姗s b e t t e rt h a ns o m ea 1 9 0 r i t t l i s k e y w o r d s ：g a m et h e o r y ；n a s he q u j l i b i a ；h e u r i s t i ca l g 嘶t l l n l 第一章绪论 第一章绪论 1 1 研究背景和动机 博弈论又称对策论，是使用严谨的数学模型研究在冲突对抗 条件下最优决策问题的理论它起源于本世纪初，普遍认为起步 于1 9 4 4 年冯诺依曼和摩根斯坦恩合著的博弈论和经济行为， 它引入了这一想法：可以对冲突加以数学分析但这部著作主要 研究两人零和博弈和合作博弈，与当代博弈论关系不大1 9 5 0 年 美国斯坦福大学学者塔克( a w t u c k e r ) 发展了“囚徒困境” ( p r i s o n e r sd i l e m m a ) ，以及美国普林斯顿大学学者纳什( j f n a s h ) 1 9 5 0 年和1 9 5 1 年发表了关于均衡的定义与存在性的文章 【1 ，2 】在文章中他证明了非合作博弈及其均衡解，并证明了均衡 解的存在性，即著名的纳什均衡，从而揭示了博弈均衡与经济均 衡的内在联系，抓住了博弈论研究的关键所谓纳什均衡，是指 博弈的理性结果是这样一种策略组合，其中每一个局中人均不能 因单方面改变自己的策略而增加收益这两项工作也奠定了当代 非合作博弈理论的基石，是博弈论发展的一个重要里程碑，后来 的博弈论研究基本上都沿着这条主线展开的与此同时，纳什还 在论文中给出了谈判和讨价还价的理论模型 然而，纳什均衡的概念毕竟具有一定的局限性，它仅适用于 分析一些静态的非重复性博弈，当用它来分析动态的或重复性博 弈时，所得的结果往往过于含糊和笼统，因此，必须对纳什均衡 北京交通大学硕士论文 这一概念加以修正1 9 6 5 年，德国波恩大学的泽尔滕( r s e l t c n ) 提出了“子博弈纳什均衡”的概念，它剔除了那些缺乏说服力的 纳什均衡点，要求局中人在任何时点都是最优的，缩小了纳什均 衡的个数1 9 7 5 年，泽尔滕在国际博弈理论杂志上发表了关 于扩展性博弈中均衡完美概念的再检验一文，进一步提出了“颤 抖手完美纳什均衡”的概念以改进子博弈纳什均衡其基本思想 是：在博弈中，每一个局中人都有一定的可能性犯错误( 形象地说， 可能手会颤抖) 一个组合战略，只有当它在允许所有局中人都可 能犯错误时仍是每一个局中人的最优战略的组合时，才是一个均 衡泽尔滕提出的这两个概念是对人类理性的一种新理解，是对 博弈论深化的重大突破他开创了动态博弈研究的新领域，对博 弈论的后续发展有着极大的启发和指导作用 现实中许多博弈问题都是在不完全信息条件下进行的受纳 什等人影响，美国加州大学伯克利分校学者海萨尼( j c h a r s 孤y i ) 开辟了不完全信息博弈研究的新领域其基本思想是： 首先引入一个虚拟的参与人一“自然”，它不同于一般参与人之处 是它在所有后果之间是无差异的自然首先选择参与人的“类 型”，被选择的参与人知道自己的真实类型，而其他参与人不知道 被选择的参与人的类型，但知道各种可能类型的概率分布，上述 工作被称之为“海萨尼转换”通过此转换，就可以把“不完全 信息博弈”转换为“完全但不完美信息博弈”在此基础上，海 萨尼定义了“贝叶斯纳什均衡”，是纳什均衡在不完全信息博弈中 的自然扩展所谓贝叶斯纳什均衡是指这样一种类型依从战略组 合：在给定自己类型和别人类型的概率分布的情况下，每个参与 2 北京交通大学硕士论文 赖他们的支付函数一般采用如表格1 的矩阵形式来表示 乙 抵赖 坦白 抵赖 田 坦白 一1 ，11 0 ，o o ，1 0培，一8 表格1 囚徒困境 在该矩阵中，表格内的第一个数字表示局中人甲在对应策略 局势形成的结局中得到的支付，第二个数字表示局中人乙的相应 支付这种矩阵优势也被称为双支付矩阵矩阵形式能够很清晰 地表示只有两个局中人且每个局中人可选择的策略数目不多的博 弈局势，也可用于表示3 个局中人策略有限的局势( 列出若干个 矩阵) 但它很少用于4 个或更多局中人的情形在不宜使用矩阵 形式表示的情况下，只能使用数学公式进行描述 为了讨论策略型博弈的算法和其他一些问题，有必要讨论严 格劣势( 优势) 策略的概念 定义1 如果某一局中人的两个策略口；，a 有如下关系：对于其 他局中人的所有策略，均有采用口，的得到的支付大于采用4 ，得到 的支付，则称口，相对于口；是严格劣势策略：相应的，称4 ，相对于 n ：是严格优势策略 在囚徒困境的例子中，对局中人甲而言，无论局中人乙采取 何种策略，采用“坦白”策略得到的支付都大于采用“抵赖”策 r 第一章绪论 略的支付对局中人甲来讲“抵赖”策略相对于“坦白”策略是 严格劣势策略或者说“坦白”策略相对于“抵赖”策略是严格 优势策略从个人利益出发，显然严格劣势策略不应被局中人采 用，因此可以利用严格劣势( 优势) 策略的概念来简化博弈局势， 从而获得博弈的解 纳什均衡( s he q u j l i l b r i u m ，简称n e ) 概念是博弈论中的 核心内容和重要基础这个概念体现了博弈的稳定状态，在此状 态里每一个局中人都拥有对其他局中人行动的正确预期，并且能 理性行动它的思想很简单，博弈的理性结局是这样一种策略局 势，其中每个局中人均不能因为单方面改变自己的策略而获利 换一种说法就是，其中每个局中人选择的策略是对其他局中人所 选策略的虽佳反应正式定义如下： 定义2 一个混合策略局势p + p 是一个纳什均衡，如果： v f ，q 4 ：吩( q ，p 二) s 吩( 西，p 二) 这样p + 为一纳什均衡必须满足：对其中任何一个局中人f 而 言，当其他每个局中人，选择策略p ：时，局中人f 没有采用其他 策略得到的支付优于他采用p + 所得到的支付 纳什均衡的概念是纳什在1 9 5 0 年首先提出的 1 】，第二年纳 什又证明了混合策略中纳什均衡点一定存在【2 】 下面的定义对纳什均衡的重新表述是有用的设p 为任意混 合策略局势，我们定义三个辅助函数石，y 和g 对于任何f 和 9 北京交通大学硕士论文 口。4 ，定义 ( p ) = 峨( ，p 一，) 勺( p ) = ( p ) 一吩( p ) g i ( p ) = m a x 勺( p ) ，o 这三个函数使我们可以把纳什均衡问题转化为以下三种形 式 纳什均衡问题转化为函数不动点问题 定义y ：p 卜p ，它的第f ，j 个分量为 咖，= 送踹 从而p p 是一个纳什均衡当仅当存在一个不动点y ，换句 话说，p = y ( p ) 因为y 是紧集p 到p 上的连续函数，它遵从b r o u w e r 不动点 定理，所以y 是一个不动点这个论点曾被纳什用来证明有限肛人 博弈纳什均衡解的存在问题【2 】 纳什均衡转化为非线性互补问题 上面定义的函数z 满足对所有p 和每个 ，易五( p ) = o 点p p 是一个纳什均衡点当仅当z ( p ) s o 在p 上的非线性互 1 0 北京交通大学硕士论文 对于周末参加什么活动，男女双方往往各自有着自己的偏好假 定某周末，男方宁愿选择观看一场足球比赛，而女方宁愿去逛商 店再进一步假定：如果男方和女方分开活动，男女双方的效用 为o ：如果男方和女方一起去看足球赛，则男方的效用为5 ，而女 方的效用为1 ；如果男方和女方一起去逛商店，则男方的效用为l ， 女方的效用为5 根据上述假定，他们的支付函数如表格2 所示 女方 看足球逛商店 看足球 男方 逛商店 5 ，1o ，o o ，01 ，5 表格2 性别战 在这个博弈中剔除两个严格劣策略以后，剩下的新搏弈中， 无法再剔除严格劣势策略根据纳什均衡的定义可以看出，这里 有两个解，即男女双方一起去看足球赛和一起去逛商店除非有 进一步的信息，如男方或女方具有优先选择权，否则，我们无法 确定男女双方在上述博弈中会做出什么样的选择 我们最后给出博弈的支持集的概念 定义3 混合策略b 的支持集墨是其策略集4 的子集，满足口；4 并且p l ) o 我们用z - ( 毛，_ ) 表示一组支持集的局势，第f 个支持集中的元素数量为五 北京交通大学硕士论文 其中爿和口为小n 维支付矩阵，代表行局中人1 和列局中人2 的 支付局中人1 的混合策略x 为支付矩阵行上的概率分布，写作m 维概率向量类似的，局中人2 的混合策略v 为n 维列上的概率向 量，因此，x r ”，y r ”，支付矩阵一和b 属于r ”“ 我们用q ( i m ) 表示爿的行向量，用6 ，( j ) 表示曰的行 向量，其中口代表露的转置当局中人1 选择纯策略f ，局中人2 选择混合策略) ，时，局中人1 的期望支付就为n ，y ，类似的，岛x 就 是局中人1 选x ，局中人2 选f 的期望支付 为讨论方便，我们定义局中人2 的混合策略) ，的最佳回应是 局中人1 的混合策略x ，满足局中人1 最大化他的期望支付x y 类似的，局中人1 的混合策略z 的最佳回应是局中人2 的混合策 略y ，满足局中人2 最大化他的期望支付x 西，个纳什均衡是 一对混合策略( x ，) ，) ，满足x 和y 相互都为对方的最佳回应易得 定理1 一对混合策略( x ，) ，) 是二人博弈( 一，b ) 的纳什均衡，当且 仅当对于所有膨中的纯策略f 和所有中的纯策略，满足 鼍 oj q y 一学口主” y j ，o4 卟。搿以工 我们定义e = 仉，1 】r “，f n ，1 】r ，这时混合策 略空间z 和y 可以表示成 工= 工酽i 及一1 ，工，o ) ， 1 ，一仁r ”i 毋1 ，x ，o 1 4 北京交通大学硕士论文 其中爿和口为小n 维支付矩阵，代表行局中人1 和列局中人2 的 支付局中人1 的混合策略x 为支付矩阵行上的概率分布，写作m 维概率向量类似的，局中人2 的混合策略v 为n 维列上的概率向 量，因此，x r ”，y r ”，支付矩阵一和b 属于r ”“ 我们用q ( i m ) 表示爿的行向量，用6 ，( j ) 表示曰的行 向量，其中口代表露的转置当局中人1 选择纯策略f ，局中人2 选择混合策略) ，时，局中人1 的期望支付就为n ，y ，类似的，岛x 就 是局中人1 选x ，局中人2 选f 的期望支付 为讨论方便，我们定义局中人2 的混合策略) ，的最佳回应是 局中人1 的混合策略x ，满足局中人1 最大化他的期望支付x y 类似的，局中人1 的混合策略z 的最佳回应是局中人2 的混合策 略y ，满足局中人2 最大化他的期望支付x 西，个纳什均衡是 一对混合策略( x ，) ，) ，满足x 和y 相互都为对方的最佳回应易得 定理1 一对混合策略( x ，) ，) 是二人博弈( 一，b ) 的纳什均衡，当且 仅当对于所有膨中的纯策略f 和所有中的纯策略，满足 鼍 oj q y 一学口主” y j ，o4 卟。搿以工 我们定义e = 仉，1 】r “，f n ，1 】r ，这时混合策 略空间z 和y 可以表示成 工= 工酽i 及一1 ，工，o ) ， 1 ，一仁r ”i 毋1 ，x ，o 1 4 北京交通大学硕士论文 我们可以看出，定理2 将二人博弈纳什均衡问题最终转化为 一个线性互补问题线性互补问题至今已发展了许多算法，但其 中最重要的无疑就是k m k e h o w s o n 算法 k m k e - h o w s o n 算法的思想来源于线性规划中的对偶单纯型 法，因此也被称为互补转轴算法，于1 9 6 4 年被藁姆克和郝森首 先提出他们在文章中利用在一系列“几乎”均衡路径上转轴的 方法给出了一条一定能到达纳什均衡点的路径，构造型的证明了 二人博弈中纳什均衡点一定存在，这个证明本身就是著名的 k m k e h o w s o n 算法只要问题的数据是有理数，算法就能提供准 果夏普利(lsh印ley)在1974年描述了在非退化情况下一个 kmkehowson算法的几何的翻译【12】这不仅使得算法易于理解，也使二人博弈在双方策略数目都足够小的情况下计算简单易行伊夫斯(bceaves)在1971年对hmkehowson进行了修改，使得它能解决博弈是退化的情形【13】kmkehowson算法有时也能用于寻找多个纳什均衡，但不能保证所找到的均衡包括所有纳什均衡解132单纯型剖分算法单纯型剖分算法可以用来求解n人博弈纳什均衡问题，它是基于将纳什均衡转化为紧集上连续函数不动点问题求解的近似算法【5】16 第一章绪论 算法首先将混合策略空间按照单纯剖分的要求规则地分成规 则相同的许多小三角形( 子单纯型) ，从空间中的任意点开始沿着 一系列相邻接的几乎全标单纯形组成的有限序列穿越这些小三角 形，通过共有的几乎全标棱进行转轴，最后到达剖分中的一个全 标子单纯型，可以证明，这个全标子单纯型一定包含近似解 接着，取这个全标子单纯型内部的任意点，缩小之前剖分尺 寸，重新对这个子单纯型进行剖分，重复该步骤直到得到的子单 纯型满足所需要的精度 单纯型剖分算法保证至少求得一个纳什均衡解实验表明， 这个算法效果很好，对于中小规模博弈的求解速度很快，但也有 一些例子显示速度很慢原因是每次重新定义剖分尺寸后，虽然 起始点是解的一个近似点，但算法经常在收敛到近似解前先走到 单纯型的边界上，当这种情形发生时，虽然剖分尺寸比原先减少， 但要到达剖分中的全标单纯形花费的运算步数会多很多如果需 要获得高精度解，或者博弈规模很大，会导致算法运算时间很长， 甚至计算机不能承受 1 3 。3 函数极小化法 像我们在上文中讨论的那样，纳什均衡问题可以转化为一个 多面体上实值函数最小值问题这个函数的全局最小值点就是原 博弈问题的纳什均衡解 回忆我们之前定义的函数v ：p 卜r 1 7 北京交通大学硕士论文 如果矩阵 v 。，v 。f 每个地方都有阶是1 的零空间，对应 的曲线就是唯一确定的恰当构造的话，曲线在a = 1 处开始并一 定能穿过a = o 点，在这个点上对应的w 值就是原问题的一个解 同时，a = 1 点处解已知雅可比矩阵v ，的零空间在每一个解对 ( m ) 处定义了一个方向，沿着该方向a 可以移动到更小的值通 过重复这一过程，可以在曲线上追寻到a = o 的解这一过程计算 上的花费与雅可比矩阵的规模成立方关系 我们现在来看格文丹和威尔逊如何把延续方法应用到求解纳 始均衡上他们的全局牛顿法通过给原博弈所有局中人的支付加 上a 的一个倍数，这个固定的倍数作为局中人的奖励，并只依赖 于他自己的策略如果奖励足够大( 并且唯一) ，那么局中人所选 取的策略只依赖于最大奖励的策略，而不必考虑对手的策略因 此，当a 一1 时，扰动的博弈只有一个均衡解，即每个局中人选取 奖励最大的策略应 第二章基于启发搜索的纳什均衡算法 第二章基于启发搜索的纳什均衡 算法 近来，纳什均衡的计算问题受到人工智能学界的重视，人们 尝试利用模拟退火算法【1 4 】、禁忌搜索算法【1 7 】、进化算法【1 5 】来 求解纳什均衡点波特( r p o n e r ) 等人提出一种简单搜索算法 【1 8 】，他们通过遍历博弈支持集搜索纳什均衡解，并利用启发思 想根据博弈的结构制定搜索策略因为2 人博弈和n 人博弈的结 构有诸多不同，他们分别提出了对应这两种情况下的不同搜索技 术 在本章中，我们提出一种新的启发搜索算法，他综合上述简 单搜索算法中的两种不同的搜索技术，并改进了其搜索策略，允 许算法通过遍历过程中出现的错误信息进行动态调整同时，利 用方程组求解技术，使算法不但可以用来计算单一纳什均衡解， 还可以计算全部纳什均衡解 2 1 算法基础 我们知道，对每一个纳什均衡解，一定对应一个支持集局势： 而每一个支持集局势却可以含有o 个到多个纳什均衡解对n 人 有限策略博弈而言，包含的支持集局势一定为有限个因此，如 果我们能够遍历该博弈全部的支持集局势，对每一支持集局势求 北京交通大学硕士论文 因此，指定支持集局势s = ( 墨，只) 上检验纳什均衡解算法 1 求解以下多项式方程组，未知量为值组v = ( v 1 ，k ) ，混 合策略局势p ；( 见，n ) ，其中不在支持集内的策略对 应概率为o ，即，v 口；硭s ：n “) = o ： l ：? ：毒，p d 。h j 口p 口。h ，v 。 l 荟p l ( q ) 。1 ” 2 将求得的p ；( p l ，n ) 代入以下不等式： 第二章基于启发搜索的纳什均衡算法 v f ，口，s ：b ( 口i ) o v ( p ) s 其中为一个接近零的正数 在这里，方程组的第一项保证局中人f 无论选取其对应支持 集上何种纯策略，支付均相等，但不能保证局中人f 选取支持集 外面的策略不会提高支付因此我们用不等式v ( p ) cs 作验证， 这里y ( p ) 就是前文定义的纳什均衡问题转化成的全局极小函数， 保证了方程组求得的p 在合理精度范围内为一个纳什均衡解 从算法的构造来看，通过将原问题转化为带不等式约束的多 项式方程组，可以利用许多已有的多项式方程组求解技术进行求 解再对每一求得的实根，代入不等式约束，舍弃不满足约束的 项同时，利用多项式方程组求解算法可以求得方程组全部解， 我们就可以据此来求得指定支持集上全部纳什均衡解 2 2 求解单一纳什均衡解算法 有了在上部分描述的指定支持集局势纳什均衡解算法，剩下 的工作就是如何使支持集局势遍历过程更加快速有效 通过分析我们知道，支持集局势的数量随局中人数量的增长 成指数集增长即使对一小规模博弈，其数量也可以是巨大的如 5 x 5 博弈( 5 个局中人，每人有5 个策略) ，支持集局势的数量竟为 2 8 6 2 9 1 5 1 个! 对于如此大的支持集局势，如何快速有效的找到含 北京交通大学硕士论文 有博弈均衡点的支持集局势也就成了利用遍历支持集求解纳什均 衡解算法的核心问题 我们的算法也是一种基于启发思想的搜索算法在全部支持 集局势形成的空间中制定一种有效快速的遍历搜索策略它考虑 到三点：其一是在遍历开始之前如何选择较优的遍历策略，其二 是如何通过遍历过程得到的信息来动态调整遍历策略，其三是尽 可能缩小遍历空间 对于第一点，我们对要遍历的支持集局势按遍历先后顺序排 序，波特的简单搜索算法采用的策略是优先选择平衡的f 每个局中 人支持集中策略数目相等) 支持集局势和策略数目小( 每个局中人 支持集中策略数目尽可能少) 的支持集局势，因为有很好的实际应 用效果，我们也采取相同的策略这种遍历策略的思想来源于麦 克雷南( m c l 舳n a l l ) 等人【1 9 】对纳什均衡解性质的研究：对指定，1 人有限策略博弈，支持集局势存在纳什均衡解的概率受到支持集 包含策略的数量与支持集局势平衡性的影响，它随着每个支持集 策略的数量的增长而减少同时，当一= 2 时，不平衡的支持集局 势存在纳什均衡解的概率为o 对于第二点如何利用启发搜索的思想动态调整遍历策略，即 如何利用在搜索过程中的失败信息来决定下一步的搜索行为，以 使搜索过程尽量快的找到包含纳什均衡解地支持集局势在这 里，我们利用一种简单的优先级规则，为每个局中人的策略制定 优先级，优先把优先级高的策略选入将要遍历的支持集局势而 该优先级表在遍历过程中根据遍历的历史信息动态更改 第三点的实现依靠：首先，在遍历进行前，利用重复剔除劣 2 4 第二章基于启发搜索的纳什均衡算法 势策略缩小遍历空间；其次，有效地剔除不可能包含纳什均衡解 的支持集局势回忆我们关于劣势策略的定义，我们知道，如果 一个策略是严格劣势策略，那剔除该策略而不会影响原问题求解 仿照严格劣势策略定义，我们给出条件劣势化o n d j t i o n a l l v d o m i n a t e d l 策略的定义： 定义4 一个策略q 4 是条件劣势策略，如果给定其余局中人一 行动集组合足，以。，则以下条件成立： j 口j 4 ，讹一。r f ：h ；0 ，口一i ) ( 彰，4 一f ) 如果一个支持集局势中包含一个条件劣势策略，那么该支持 集局势必不包含纳什均衡解因此，我们可以在遍历过程中通过 对支持集局势是否包含条件劣势策略的检验来有效的剔除不可能 包含纳什均衡解的支持集局势 根据以上的分析，我们的算法形式描述如下： ( 1 ) 预处理： 重复剔除劣势策略 ( 2 ) 遍历支持集空间： f o r a l l 茸一h ，) ，对于2 人博弈，先以k 一屯i ， 后以+ 屯排序；对于甩( 一，2 ) 人博弈，先以墨， 后以盼( 薯一工) 排序，d 。 第二章基于启发搜索的纳什均衡算法 重复剔除条件劣势策略域子程序：i r s d s ( d ) 输入：d = ( d l ，d 2 ，d ) 支持集定义域局势 输出：更新了的d ，或者，n f f “r e n p e a t c h n n g e d 一 n t s 2 f o ra l l f d o f o r a l l q 旦4d o f b ra l l 口；4d o i f 口i s 咖d i t i o n a l l yd o m i n a t e db y 嚷，g i v e n 二厶吐曲e n 皿- d f 一 4 d i ：啊吐 c h 口托g e d - t r l l e i f 皿；彩t h 蛆 r e t 哪m 加m i ，e u n 伽曲口 g 耐= 如b 已 r e t l l l l md 算法所使用两个子程序的作用解释如下： 回溯搜索子程序是算法的回溯过程，当我们指定了一组支持 集数量局势x h ，) 后，我们求得对应每一个t 的s 的定义 域d f ，之后从1 到月依据搜索优先级列表依次从其中选取i 当选 取完全部s 后，我们对选出的该组支持集局势用前文描述的指定 支持集局势纳什均衡解算法进行求解，根据求解结果更新搜索优 先级列表 2 7 北京交通大学硕士论文 重复剔除条件劣势策略域子程序和文献f 1 8 】所使用的方法相 同，作用是每当确定了一个s 后，使用重复剔除条件劣势策略域 子程序对d f 。，见进行精炼，剔除其中包含条件劣势策略的支持 集局势，从而缩小q 。，乜若剔除过程出现某个q 变为空的情 况，说明该组支持集定义域局势不存在包含纳什均衡的支持集局 势，子程序返回丘f m ，e ，告诉主程序进行下次迭代 启发搜索算法可以看作为一种求解c s p ( 约束满足问题) 的 回溯算法该问题的约束为必须存在一个满足指定支持集局势纳 什均衡解算法的解同时，我们还添加了一个附加的约束，即也 要满足没有局中人使用条件劣势策略要注意的是，虽然是否添 加该附加约束不影响问题解集的大小但通过满足该附加约束， 我们可以减少对许多支持集局势进行指定支持集局势纳什均衡解 算法的执行，从而很大程度的减少了算法的运算时间 算法对2 人博弈与咒人博弈支持集局势排序的不同是因为在 h ，2 时候，在非平衡支持集局势上存在纳什均衡解的概率不为o ， 不同于h 一2 时非平衡支持集局势上存在纳什均衡解的概率为0 n ，2 时支持集选取的平衡性也比n = 2 时次要的多 2 3 求解全部纳什均衡解算法 求解全部纳什均衡解算法就是对上一部分求解单一纳什均衡 解算法的改进在这里我们要完全遍历支持集局势空间，并且对 第二章基于启发搜索的纳什均衡算法 每一支持集局势，求解其包含的全部纳什均衡解具体做法是对 求解单一纳什均衡解算法中的停机条件加以改动，每当在某一支 持集局势中找到纳什均衡解后算法先不立刻停止，而是继续查找 该支持集局势中其他均衡解，当求得所有均衡解后，算法继续遍 历支持集空间中下一个支持集局势，查找它包含的全部纳什均衡 解当所有支持集局势全部遍历完毕后，算法停止 这里，求解全部纳什均衡解算法也可以用于求解多数纳什均 衡精炼解，也就是满足某些附加条件的纳什均衡解，对算法求得 的每一个解利用附加条件进行验证即可 虽然启发搜索算法可以求得全部纳什均衡解，但是注意，因 为完全遍历支持集局势空间，并对每一支持集局势求解全部纳什 均衡点，这个算法运算速度慢，运算时间与博弈规模成指数关系， 并且失去了任何启发搜索的特性在实际中即使是中等规模博弈 问题运算时间可能都无法接受 北京交通大学硕士论文 3 2 实例测试 这里，我们的测试环境为p e n t i u m 43 0c p u ，1 5 g 内存i b m n i l l l ( c c n t e r 台式机为测试方便，我们设定超时时长4 0 0 秒：若 某算法在该时间内未计算出结果，则判定该算法计算失败 3 2 1 单一纳什均衡解测试 我们将启发搜索算法( h s ) 与求解2 人博弈纳什均衡的 k m k e ，h a w s o n 算法( l h ) 【4 】，n 人博弈纳什均衡的全局牛顿算 法( g n m ) 【6 】，多矩阵迭代算法( a ) 【8 】，单纯型剖分算法 ( s i m p d i v ) 【5 1 进行比较 首先，剔除g j 蝴u t 产生的2 人2 2 型博弈，共以下2 5 种 博弈类型参与比较这里，2 人博弈选用2 1 0 0 博弈，n 人博弈 选用5 5 博弈进行测试，详见表格3 ： 博弈类型 代号博弈类型 代号 a r m s r a c e g lm i n i m u m e f f o r t g a m eg 1 4 b e r t r a f l d 0 1 i 聃d 0 1 y g 2n p l a y e r c h ic i 【e ng 1 5 b i d i r e c t i o n a l l e gg 3n p l a y e r p r i s o n e r s d i l e t 帅a g 1 6 c 0 1 1 8 b o r a t i o n g a m e g 4p 0 1 v m a t r i x g 蛳eg 1 7 c o n g e s t i o n i 细e g 5r a n d o l g a m eg 1 8 c o o r d i n a t i o n 6 哪e g 6r a n d o l i l c o m o o u n d g 蚰e g 1 9 c o u r n o t 【) u o d o l vg 7r a n d o m l e g g 2 0 c o v a r i a n t g 鲫e g 8r a n d o 船a d h i c a l g a m eg 2 1 d i s d e r s i o n g a m e g 9r a n d o m z e r o s u m g 2 2 g r a b n l e d 0 1 1 a rg 1 0t r a v e l e r s d i1 e 嗍 g 2 3 g u e s s t w o t h i r d s a v eg 1 1 u n i f o r m l b gg 2 4 l o c a t i o n g a 时 g 1 2冒a r o f a t t r i t i o ng 2 5 m a j o r i t y v o t i n g g 1 3 表格3 博弈类型 3 2 第三章计算问题与实例测试 随机博弈算法测试比较图 图表3 随机博弈算法测试结果 从测试的结果来看，启发搜索算法除了一种情况运算超时， 其他情况都在规定时限求得纳什均衡解，并且平均运算速度也是 最快的在某些情况，i p a 算法运算时间会优于启发搜索算法， 但是i p a 算法是利用多矩阵博弈来逼近原博弈的近似算法，不具 备全局收敛性，因此受到一定局限性 3 2 2 求解全部纳什均衡解测试 这里，因为参与比较的算法都是求解单一纳什均衡解的算法， 无法进行比较测试，所以只列出我们自己的算法在随机博弈上的 测试结果结果详见表格6 ： 参考文献 8 】 g o v i n d a ns ，w j l s o nr c o m p u t i n gn a s he q u j l j b r i ab yi t e r a t e d p 0 1 y m a 伍xa p p r o x h n a t i o n 【j 】j o u m a l o fe c o n o m i cd y n a m i c s a n dc o n i m 】，2 0 0 4 ，2 8 ：1 2 2 9 1 2 4 1 【9 】 m c k e l v e yr ，m c l e n n a na ，1 1 u r o c yt g a m b j t ：s o