（计算机软件与理论专业论文）基于行为图博弈的nash均衡算法研究.pdf

郑州大学硕士学位论文 摘要 博弈论( g a m et h e o r y ) 是研究竞争条件下决策分析的科学。它研究的典型问题 是若干个利益冲突者在同一环境中进行决策以求自己的利益得到满足。近年来， 博弈理论模型已经在计算机科学和人工智能领域产生了深远的影响。尤其是在多 a g e n t s 领域，很多学者作出了大量工作，其方向主要集中在：博弈模型研究、博 弈算法研究等。 行为图博弈模型是一种新型的博弈模型。它涵盖已有的结构化博弈模型，图 型博弈，阻塞博弈和局部效用博弈。求解n a s h 均衡是行为图博弈模型的核心问 题。本文重点研究行为图博弈模型上从效用函数到n a s h 均衡求解的相关问题。 首先，在本文中我们详细分析了博弈中a g e n t 的有关问题，简要介绍了规范 型博弈，具有结构化博弈模型的图型博弈，以及阻塞博弈和局部效用博弈。并且 分析了当前一些学者们提出的算法。然后着重考察了行为图博弈，在行为图博弈 中求解期望收益是通过动态规划来完成的，分析了如何在行为图博弈中求期望收 益。我们把连续方法应用到行为图博弈中，我们不仅给出如何在行为图博弈中进 行扰动操作、回溯、效用雅克比的计算及其消除累积错误，而且，更新混合策略 剖面将其应用到下一次迭代中。紧接着分析了如何在行为图博弈中求解n a s h 均 衡。 我们用基g a m e t r a c e r 的规范型博弈求解期望收益，和本算法进行比较。 用动态规划求行为图博弈的存储数目，给出了一个五乘五的博弈来进行实验。证 明行为图博弈成多项式增长，而规范型博弈成指数增长。 其次，我们通过两个实验来验证本算法的有效性，通过固定行、改变列以及 固定列、改变行来进行实验。 最后，运用i p a 作为快速启动，利用全局牛顿算法求解n a s h 均衡的c p u 利用 时间。实验结果表明本文算法是令人满意的。 关键词：a g e n t ；m a s ；行为图博弈；博弈论；纳什均衡 郑州大学硕士学位论文 a b s t r a c t g a m et h e o r yi sas c i e n c ew h i c hr e s e a r c h sd e c i s i o na n a l y s i so nt h ec o n d i t i o n so ft h ec o m p e t i t i o n t h et y p i c a lp r o b l e mi tr e s e a r c h si st h a tac o n f i l i c to fi n t e r e s ti nt h es a m ee n v i r o n m e n tf o rd e c i s i o n - m a k i n g 、析t hav i e wt ot l l e i ro w ni n t e r e s t sa r em e t i nr e c e n ty e a r s g a m et h e o r ym o d e l sh a v eap r o f o u n di m p a c ti n t h ef i e l do fc o m p u t e rs c i e n c ea n da r t i f i c i a li n t e l l i g e n c e a g e n t s ，e s p e c i a l l yi nm u f f - a g e n ts y s t e m ，m a n y s c h o l a r sh a v em a d eal o to fw o r k ，a n di t sd i r e c t i o nf o c u s e do i l ：t h eg a m em o d e l ，t h eg a m ea l g o r i t h m r e s e a r c h a c t i o ng r a p hg a m e si san e wr e p r e s e n t a t i o no fg a m et h e o r y i ti n c l u d e ss t r u c t u r e dg a m e s ， e s p e c i a l l y , g r a p h i c a lg a m e s ，c o n g e s t i o ng a m e s ，l o c a le f f e c tg a m e s f i n d i n gn a s he q u i l i b r i u mi st h ec o l t a s ki fa c t i o ng r a p hg a m e s i nt h i sp a p e r , w ef o c u so nt h ep r o b l e m sf r o mu t i l i t yf u n c t i o n st of i n d i n gn a s h e q u i l i b r i u m w ea p p l yc o n t i n u o u sm e t h o dt oa c t i o ng r a p hg a m e ，w eh a v en o to n l yg i v e nh o wt h eg a m ep l a n c a r r i e do u ta c t so fd i s t u r b a n c eo p e r a t i o n s ，b a c k , u t i l i t yj a c o b i a nc a l c u l a t i o na n de l i m i n a t et h ea c c u m u l a t e d b i t o r s ，b u ta l s ou p d a t et h em i x e ds t r a t e g yp r o f i l eo fi t sa p p l i c a t i o nt ot h en e x ti t e r a t i o n o nt h eo t h e rh a n d w ea n a l y s i sh o wt oc o m p u t ea c t i o ng r a p hg a m e sn a s he q u i l i b r i a f i r s t l y , i nt h i sp a p e rw ea n a l y z et h ep r o b l e ma b o u ta g e n ti nt h eg a m e n t r o d u c et h en o r m a lg a m e s b r i e f l y , g r a p h i c a lg a m ew i t hs t r u c t u r e dg a m e s ，c o n g e s t i o ng a m ea n dl o c a le f f e c tg a m e a l s o ，w ea n a l y z e s o m ea l g o r i t h m ss o m el e a r n e r sp r o p o s e d t h e nw ef o c u so i la c t i o ng r a p hg a m e ，w eg i v ea l le x a m p l ea n d a n a l y z eh o wt of i n de x p e c t a t i o np a y o f fi na c t i o ng a m e w ef i n de x p e c t a t i o np a y o f fo fn o r m a lg a m e sb a s e d o ng a m e t r a c e r a l s o ，w em a k ec o m p a r i s o n sw i t ht h ea l g o r i t h m w ef m dt h en u m b e r so fa c t i o ng r a p hg a m e s w i t hd y n a m i cp r o g r a m m i n ga n dm a k ee x p e r i m e n t a t i o n s 谢t hg i v e ng a m e s w ep r o v ea l g o r i t h mc a ng r o w s l i 郑州大学硕i ：学位论文 i nt i m ep o l y n o m i a li nt h es i z eo ft h ea c t i o ng r a p hg a m e s e c o n d l y , w ep r o v et h ev a l i d i t yo fa l g o r i t h mt h r o u g ht w oe x p e r i r a e n t s w ec a nf i xt h er o wa n da l t e r c o l u m n ，a n dw ec a nf i xt h ec o l u m na n da l t e rt o w f i n a l l y , w em a k eaf a s ts t a r t 丽t hi p aa n df i n d i n gt h et i m eo fc p un a s he q u i l i b r i u mw i t hg r i m t h e s e a l g o r i t h m sw o u l dc o v e rp r o b a b l yi nt h ef u t u r e k e y w o r d s ：a g e n t ，m a s ，a c t i o ng r a p hg a m e ，g a m et h e o r y ，n a s he q u i l i b r i u m i i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：杏宗奇f 1 期：中脚驷 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者：夕宗卉 日期：如。( j 年f 2 月归 郑州大学硕士学位论文 1 1 研究背景 第一章绪论 从1 9 9 4 年v o nn e u m a n n 和m o r g e n s t e r n 的开创性研究开蝌1 1 ，经过5 0 多年 的迅速发展，博弈论已经成为- - f 3 成熟的学科。博弈论( g a m et h e o r y ) 【2 】是研究竞 争条件下决策分析的科学。它研究的典型问题是若干个利益冲突者在同一环境中 进行决策以求自己的利益得到满足；是当今经济学乃至整个社会科学中极为重要 的一门理论学科，它利用数学工具对种种社会经济现象进行深入的规范分析，获 得了丰硕的研究成果。 博弈论研究的是人与人之间利益相互制约下策略选择时的理性行为及相应 结局。博弈论是关于策略相互作用的理论，也就是说，它是关于社会形势中理性 行为的理论，其中每个局中人对自己行动的选择必须以他对其他局中人将如何反 应的判断为基础。当人们的利益存在冲突时，每个人所获得的利益不仅取决于自 己所采取的行动，还有有赖于其他人采取的行动，因此每个人都需要针对对方的 行为选择作出对自己最有利的反应。它提供了一种研究人类理性行为的通用方 法，运用这些方法可以更为清晰完整分析各种冲突与合作的形势，因此，博弈论 在经济学、社会学、心理学、政治学等各类社会科学中得到了广泛运用，对进化 生物学、计算机科学和人工智能等学科也产生了重要影响并且形成了新的研究热 点，称作为：“计算博弈论”( c o m p u t a t i o n a lg a m et h e o r y ) 。博弈论研究的典型问 题是若干个利益冲突者在同一环境中进行决策以求自己的利益得到满足。在目前 的计算机领域中，博弈论的理论原则、思想方法已经应用到计算机科学当中。特 别地，在机器学习和人工智能的交叉领域中也产生了重要影响，成为学术界的又 一热门话题。 1 2 研究现状 从博弈论诞生之同起，博弈模型的相关计算问题就成为经济学、数学领域的 研究者所关注。近年来，博弈理论模型已经在计算机科学和人工智能领域产生了 郑州大学硕士学位论文 深远的影响。尤其是在多a g e n t s 领域，很多学者作出了大量工作，其方向主要 集中在：博弈模型研究、博弈算法研究等。特别地，同时行动博弈已经得到相当 广泛的关注，因为同时行动博弈在某种意义上说是最根本的。为了分析这些模型， 从效用函数到那什均衡的计算就变得非常必要。 n a s h 均衡是博弈论文中重要的概念。j n a s h 早在5 0 年代初就给出了n a s h 均衡的存在性定理，但如果没有相应的算法求解它会影响到理论的实际应用。经 典博弈论中两种主要的博弈表示模型是效用矩阵和博弈树。这两种表示方法都便 于我们对博弈进行描述和分析，但她们的表示复杂程度与a g e n t 数目成指数关系 增长的。近年来，许多学者提出了一些更为简洁有效的结构化博弈表示模型，并 且给出了这些模型的n a s h 均衡的求解算法，这些模型都是基于现实环境中存在 的a g e n t 策略间的效用独立关系。 l e m k e ( 1 9 6 4 ) 等人【4 给出了n a s h 均衡的算法。该算法用于求解双矩阵表示 的2 人博弈。其算法主要用于解决l i n e a rc o m p l e m e n t a r i t y 问题，把2 人博弈n a s h 均衡看作是解决l i n e a rc o m p l e m e n t a r i t y 问题的一个特例。 v a nd e rl a a n ( 1 9 8 7 ) 等人【5 】提出了用于求n 个a g e n t s 的博弈。求解n a s h 均衡 就不能用上述方法来求解。其思想是：把求解n a s h 均衡看作是求一个固定点的 解。它给出的是n 个a g e n t s 的博弈的解，由于不能得到很精确的解并且与a g e n t s 的数目还成指数关系。这两种计算方法对于经典博弈表示的模型还是可以的。 在经典博弈的表示中常常用到效用矩阵和博弈树。这两种方法对于进行数学 描述和分析是非常方便的，但是当a g e n t s 比较多时，该方法不是很有效的。 m k e a m s ( 2 0 0 1 ) 等人 6 】首先提出了用图型博弈模型。来描述含多个a g e n t s 之间的博弈。对于一个含有1 1 个a g e n t s 的博弈，效用矩阵要记录a g e n t 的每一 个策略在其余n 1 个a g e n t 的各种策略组合下的效用，此时n 个a g e n t s 间的效 用关系可以表示为含有n 个节点的完全图。分析n 个a g e n t s 间策略效用独立的 关系，用n 节点的稀疏图表示博弈的效用信息。 d k o l l e r ( 2 0 0 2 ) 等人 7 】用约束满足算法来求解n a s h 均衡。首先把目标n a s h 均衡看作是约束满足问题，然后用动态规划算法来求解此问题。该算法利用到了 a g e n t 的混合策略，在全部变量形成的混合策略空间上来求解。它可以应用到任 意结构的图型博弈模型上，并且对于局中人所用的纯策略数目不进行限制。 2 郑州大学硕上学位论文 图型博弈提出以后，一些学者提出了基于该表示模型的n a s h 均衡的求解算 法。k e a m s 等人提出图型博弈的类似于贝叶斯网推理的p o l y t r e e 算法。 l e y t o n ( 2 0 0 3 ) 等人 9 】提出了局部效用博弈，讨论了上下文独立的结构化博弈 模型。之上所说到的博弈是从博弈到n a s h 均衡的计算中，在效用函数上具有统 一的性质，也就是效用函数是彼此独立的。这里效用函数是上下文联系的。任何 一个局中人的收益都会受到其他局中人的影响。 m i l c h t a i c h ( 2 0 0 6 ) 等人【1 l ，1 2 ，1 3 ，1 4 】提出了阻塞博弈论指出了阻塞博弈的匿名 性，也即，a g e n t 的收益依赖于选取相同行动的其它a g e n t s 的数目，不依赖与a g e n t 的属性；资源的附加性。阻塞博弈是一个四元组( ，e ，( ，) 洲，( z ) 。“) ，其中 n = 1 ，n ) 是局中人集合，e 是设施集合，2 e 是局中人f 的纯策略集合：纯 策略4 ，是设施集合，最终z 是与设施相关的成本函数。在阻塞博弈中大部 分的工作与线性成本函数相关。 b l u m ( 2 0 0 3 ) 等人【1 5 】提出了在结构化的博弈中用连续的方法来求解。 g o v i n d a n ( 2 0 0 3 ，2 0 0 4 ) 等人 1 6 ，1 7 用全局牛顿方法来求解n a s h 均衡。 1 3 研究内容 在博弈理论模型中，a g e n t 与外界之间，a g e n t s 之间都是相互作用相互影响 的。在这样很复杂的状况下，要很方便解决需要解决的问题，我们就要看a g e n t 的博弈的特性，在一个复杂的环境中，我们可以将许多a g e n t s 的行为重新考虑， 建立能够表示a g e n t 行为的模型，在模型当中我们要考虑到单个a g e n t 总是通过 自己的最大努力来最大化自己的收益，而自身策略的选择总是依赖于其它a g e n t 所选择的策略，其它a g e n t s 所选择的行动或者策略总会对它有影响，尽管影响的 程度是不同的。一旦对别的a g e n t 有影响，它的当前策略又会影响到对未来策略 的选择上。 为此，人们利用了很多方法和理论来解决复杂的系统。在此文当中，我们利 用行为图博弈表示模型来进行。 本文中首先探讨了在动态规划算法的指导下，超市博弈的数学特征，详细的 阐述了j i a n g 等人【2 0 】所得出的结论。根据他们的成果继续讨论了在规范型博弈 郑州大学硕士学位论文 和行为图博弈中，复杂度的讨论，博弈的特征，并且证明了动态规划算法是正确 的。接着，从效用函数到n a s h 均衡的计算过程中，利用动态规划算法计算联合 策略，而计算期望收益的实验，并在此基础上对实验作出了推广。 然后，根据本文中得到的性质对算法进行修改，提出了一个新的算法( 本文 算法) ，在行为图博弈的入度是有限的情况下，利用算法进行改变行和列，给出 这两组实验，计算n a s h 均衡的c p u 计算时间，进而作出对比。 1 4 论文结构及主要内容 本文结构安排如下： 第一章绪论 在本章中，介绍了博弈论的背景、博弈论模型的研究现状和研究内容；并概 述了本文的内容、结构和主要工作。 第二章博弈模型理论概述 对规范型博弈，图型博弈，阻塞博弈和局部效用博弈等进行了描述。主要描 述了能以上的博弈都是基于在效用函数上做的一些假定，要么是效用函数严格独 立，要么是上下文独立，要么是匿名结构，不能完全表达效用函数。由此给出了 能完全表达效用函数，不对效用函数做假定的行为图博弈。 第三章求解期望收益的动态规划算法 详细描述了从期望收益到n a s h 均衡的计算中具体的算法，在此的基础上， 给出了算法的一个具体实例，且用理论证明了求解该算法的有效性。将我们得出 的结论与n a s h 均衡中算法相结合，在这样的算法中来证明收益存储数目的加快 和运行时间。 第四章行为图博弈中n a s h 均衡的计算 根据上一章得出的结论以及实用算法，对现有算法进行改造，提出本文算法， 使之具备更加优良的属性。详细描述本算法的思想和算法形式，最后通过大量的 实验验证该算法的有效性。 第五章总结与展望 对本文进行总结，提出了下一步需要进行的工作。 4 郑州大学硕士学位论文 第二章博弈模型理论综述 2 1a g e n t 的概念及特征 a g e n t 的概念最初形成于分布式人工智能领域，最早出现于上世纪7 0 年代 并于8 0 年代后期得到深入研究。著名的a g e n t 理论研究者j e n n i n g s ( 19 9 8 ) 等人 【2 2 ，2 3 ，2 4 和w o o l d r i d g e ( 1 9 9 7 ) 等人 2 5 ，2 6 ，2 7 教授甚至把它誉为是“软件开发的又 一重大突破 。w o o l d r i d g e 和j e n n i n g s 认为a g e n t 应具有反应性、自主性、社会 交互性、反应能力和欲动能力。j e n n i n g s ( 1 9 9 8 ) 等人【2 2 】还使用“有弹性的 这个 词来描述a g e n t 的特性，它是指社交能力、反应性和适应性三者的综合。 j e n n i n g s ( 1 9 9 7 ) 等人 2 4 】给出了一个按照a g e n t 的应用领域来分类的方法。 j e n n i n g s 等将a g e n t 的应用主要：工业应用商业应用医疗应用博弈游戏。 2 1 1a g e n t 的定义 r u s s e l l ( 1 9 9 5 ) 等人 2 9 】指出，“a g e n t 定义是一个分析系统的工具，而不是用 来将世界分为a g e n t 和非a g e n t 两大类 ，而且精确的定义只能采用数学或逻辑 等精确的描述手段来实现，而这样做将会陷入一个个具体的a g e n t 模型。 一般说来，以下一些定义概括t a g c t l t 应具备的一些基本能力： a g e n t 就是这样一种计算机系统，它能够适应一定的环境，并且能够根据 环境特点自发行动，以达至l j a g e n t 身的设计目的5 0 1 。 a g e n t 就是一种能够通过传感器感知所处环境信息，并对环境施以一定影 响的事物【5 i 】。 a g e n t 是一类处于复杂动态环境中的计算系统，它为了实现设计目标、任 务，可以感知并影响自身所处的环境【5 2 1 。 杨鲲( 1 9 9 9 ，2 0 0 0 ) 等人 3 3 ，3 4 在分析了一些典型的a g e n t 研究报告和应用系统 中有关a g e n t 的描述和定义之后，提出一个a g e n t 的最基本特性应当包括：反应 性、自治性、面向目标性和针对环境性。 杨鲲教授根据a g e n t 的特性给出一个a g e n t 的简单定义如下：a g e n t 是一类 在特定环境下能感知环境，并能自治地运行以代表其设计者或使用者实现一系列 郑州大学硕士学位论文 目标的计算实体或程序。 2 1 2 多a g e n t 系统的特性及应用 自7 0 年代后期以来，随着计算机网络、计算机通信和并行程序设计技术的 发展，分布式人工智能d a i ( d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n c e ) 的研究逐渐成为一个 热点，早期的研究主要是分布式问题求解，其目标是要建立大粒度的协作群体， 他们之间共同工作以对某一问题进行求解；9 0 年代，a g e n t 系统m a s ( m u l t i a g e n t s y s t e m ) 的研究成为分布式人工智能的热点，实际系统的分布性、负载性和动态 性有望通过对单个个体能力的有效分工、协调和组织而达到系统整体优化的目 的。 m a s 可以定义为这样一个松散耦合的问题求解系统：系统个体成员( a g e n t ) 的 能力不足以单独解决整个问题，以至于必须通过a g e n t 的交互才能完成全部问题 的求解。 随着m a s 研究的深入，自8 0 年代中期以来，m a s 在实际工程中的应用也越 来越广泛，涵盖了从敏捷制造【3 5 】、过程控制【3 6 1 、交通控制【3 刀到信息处理【3 8 1 等等 领域。 “博弈论 译自英文“g a m et h e o r y 一。也就是“游戏理论 。博弈论关注的 是意识到其行动将相互影响的决策者们的行为。 2 2 静态完全信息博弈 完全信息静态博弈理论是整个非合作博弈理论的基础，它抽象出现实博弈形 势中最基本的组成部分构成数学模型，由此对参与者的理性行为形成规范描述， 在此基础上进一步可扩展为更复杂的博弈模型。 我们先给出一个博弈的实例，从而引出博弈论相关概念的介绍。 例2 1 性别大战博弈 有一对夫妻，男人要去看足球比赛，妻子要去看芭蕾舞，妻子要去看芭蕾舞 的收益要大于丈夫看足球比赛的收益；而丈夫看足球比赛的收益要大于妻子看足 球的收益；当妻子看足球并且丈夫看芭蕾舞时每个人的收益都是最小的，为此两 个人为看足球或者芭蕾舞展开了博弈。 6 郑州大学硕士学位论文 上例虽然简单，但它给出了一个博弈情形的生动实例。博弈问题一般含有五 个要素：局中人、每个局中人的可行方案集、局中人决策的先后顺序、每个局中 人的收益函数、信息。 所谓局中人，即博弈的参与者，他们是博弈的决策主体，根据自己的利益要 求决定自己的行为，局中人可以是自然人，也可以是各种社会组织等。如上例中 的两个人。局中人记为f ，局中人集合n = l ，2 ，n ) ，即共有1 1 个局中人，如果 参与博弈的人数无限，则n 为整个自然数集。为了讨论的方便，我们将某个局 中人i 之外的其他局中人称为“f 的对手 ，记为一f 。特别地，在后文中我们把局 中人称作a g e n t 。 所谓策略，即策略型博弈中有两种策略概念。最基本的称为纯策略，简称策 略，指每个局中人在博弈中可以选择采用的行动方案，每个局中人均有可供其选 择的多种策略。记局中人i 的策略为墨，岛墨，其中墨为局中人f 可选择的策略 组成的策略集合，又称为策略空间。n 个局中人各选择一个策略形成的向量 s = ( _ ，屯，) 被称为策略组合( s t r a t e g yp r o f i l e ) ，策略组合的集合为s = x ，墨。 另一种策略概念为在纯策略基础上形成的混合策略( m i x e ds t r a t e g y ) ，局中人f 的 混合策略q 是其纯策略空间墨上的一种概率分布，表示局中人实际博弈时根据 这种概率分布在纯策略中随进选择加以实施。q ( 墨) 表示q 分配给纯策略墨的概 率，局中人i 的混合策略空间记为，混合策略组合空间为= ，。可以看出， 纯策略可视为混合策略的特例，也就是对某个纯策略赋予概率1 而对其他纯策略 赋予概率o 的混合策略。 为了下文讨论的方便，记局中人i 之外其他局中人( 即f 的对手) 所采取的 策略为s 一，屯，由于我们常常要讨论只有一个局中人改变策略的情况，因 此我们将策略组合( s ，墨，s i + ，) 记为( s ；，s 一，) 或者s i 表示策略组合s 中 局中人i 改变策略墨为后形成的新策略组合。对于混合策略，也有类似记法。 所谓支付，即每个局中人从各种策略组合中获得的收益，其中收益往往采用 效用的概念，由于它是策略组合j 的函数，所以也被称为支付函数，记局中人i 得 支付函数为u i ( s ) 。对应于混合策略，局中人的支付为得到的期望效用，局中人i 7 郑州大学硕士学位论文 对应于混合策略组合仃的支付为：嘶( 盯) = 兀a j ( s j ) u ，( j ) 以上三种基本要素 j 西户l 构成了策略型博弈。由此可对博弈局势进行分类，如果局中人只有两个，则称其 为双人博弈，如果是多人，常称其为n 人博弈。如果局中人的支付之和在任何情 况下均为零，那么这种博弈被称为零和博弈。显然零和博弈表现的是局中人的利 益完全对立的情况。另外，某些博弈被称为有限博弈，是指博弈的局中人个数与 每个局中人的策略数均是有限的。 可行方案集是a g e n t 可以采取的行动方案的全体，如上例中每个人都有个可 选的行动“看芭蕾舞”、“足球比赛”。在博弈问题中，a g e n t 在其可行方案上的 选择，便是决策分析。许多学者把g a m e t h e o r y 称为对策论，就是由于在对抗冲 突的条件下进行决策分析。 决策的先后顺序是实际问题动态性质的反映，任何一种博弈的规则都要明确 各个a g e n t 进行决策分析的时间先后。如果各个a g e n t 是同时进行决策，问题便 是静态博弈。还有一种情形也是静态博弈，那就是不同a g e n t 决策时间由先后顺 序，但后决策的a g e n t 并不知道前于其决策的a g e n t 选择了什么行为方案。 除 开上述两种情形，问题都是动态博弈。性别大战就是一个静态博弈的例子。 收益函数是博弈最后结果中各个a g e n t 利益的表示。在上面的性别大战中， 我们用效用矩阵来表示每种博弈结果下两个人的收益。当问题中出现不确定性 时，收益通常是估值，比方说行为结果的数学期望。 信息指的是a g e n t 在决策时对其决策条件的知识。信息包括两类， 一类是 有哪些a g e n t s ，他们的可行方案集是什么，所有a g e n t s 的收益函数是怎样的； 另一类是a g e n t 决策前已作过的决策结果在博弈中，如果所有a g e n t s 对前一类 信息有确切的了解，就称之为完全信息的博弈，否则称之为不完全信息博弈。而 在博弈中如果所有a g e n t s 对后一类信息有确切的了解，就称之为完美信息博弈， 否则称之为不完美信息博弈。上面的性别大战是一个静态完全信息博弈的实例。 设c 为某类事件所有可能结果的集合。如果存在c 上二元关系尺，满足以下 三个条件【3 9 】： 完备性。即对任何五y c ，关系x r y 或y r x 至少有一个成立； 自反性。即对任何工c ，关系x r x 总成立； 郑州大学硕士学位论文 可传递性。即对任何z ，y ，z c ，如果x r y 与y r z 都成立，则x r z 必成 立。则称r 为c 上的弱序( w e a ko r d e r ) 。如果对所有x ，y c ，关系x r y 意味着 认为“结果z 不比j ，差 ，则称弱序r 为cl = 的偏好关系，并记作工 _ y 。如果对 于偏好关系 _ ，恰好有a g e n t 对c 中结果的看好程度的比较结果与之相合，即对 所有的z ，y c ，有x - y c 该么g e i l t 认为x 不差于y ，则称此 为该a g e n t 的偏 好序。 在决策论中已经证明：在一定条件下存在效用函数“，满足 j c - y c “( x ) 2u ( y ) ，毛y c 称二元组( c - ) 为一个偏好结构，其中c 是结果集， ，是c 上的偏好序。称四元组( s ，c ，厂 ) 为一个理性选择结构，其中s 是可行方 案集，c 是可能结果集，：s _ c 是可行方案集到可能结果集的映射， - 是c 上 的偏好关系，如果决策者有理性的选择结构，并且在决策分析中通过最优化来审 慎地选择自己的行为方案，则称此决策者是理性的。 在博弈分析中，我们假定所有局中人都是理性的决策者，即要求他们通过最 优化来进行决策。 下面我们给出博弈的形式化定义。 定义1 1 t 3 明称三元组 为策略博弈( s 仃a t e 西cg a m e ) ，或正规博弈 ( n o r m a lg a m e ) ，其中 = a g e n t , ，a g e n t 2 ，锄乙夕为局中人集，共n 个局中人。 ( s ) = 墨，是9 o0 9 最) ，s i 是a g e n t i 的可行方案集，i = 1 ，z ，n ，其中，不失 一般性，我们假设任意一个a g e n t i 有七个行动( 或称作纯策略) ，即s = 墨。，墨：， ) 。 ( 嘶) = u i ，u 2 ，u 。) ，是a g e n 的收益函数，i = j ，z ，n ，比较具体地吩 ( 墨，j 2 ，s 。) 是在纯策略组合( 毛，s 2 ，毛) 之下，a g e n t i 收益值，0 墨。 a g e n t ，在 博弈中理性化的表现是使u i 极大化。且我们又称( 墨，s 。) 为对策局势或称作博 9 郑州大学硕士学位论文 弈的一个纯策略剖面( p u r es t r a t e g yp r o f i l e ) 。 n = 局中人1 ，局中人2 ； s = 岛= 看芭蕾，看足球) 一般地，在策略博弈中，我们总是用效用矩阵来表示局中人在各种对策格 局下的收益值。每一个a g e n t ，对应一个纯策略效用矩阵m ，矩阵的行是a g e n t ； 的纯策略，矩阵的列是其余a g e n t s 纯策略的每一种组合。m ，的值实际上给出了 a g e n t ，的纯策略在博弈的每一种对策局势下获得的效用。显然，对于一个含n 个 a g e n t s ，每个a g e n t 有2 个纯策略的博弈，我们需要给出n 个矩阵必，( 1 i ，z ) ， 每一个m 的大小为2 “。 我们可以直观地理解一些个人、团体或者其他组织，在一定的环境条件及其 一定的规则下，同时或者先后，一次或者多次，从各自允许选择的行为或者策略 中进行选择并加以实施，各自取得相应结果的过程。 描述一个博弈需要设定以下四个方面：局中人( p l a y e r s ) 。在具有多个a g e n t 组成的系统中，每个a g e n t 可以看成一个局中人，优势在多个a g e n t 组成的团体 中，由于具有共同的目标利益，往往也可以将其整体看成一个局中人。各个博 弈者各自可以选择的全部行为( a c t i o n s ) 或策略( s t r a t e g i e s ) 的集合。进行博弈的顺 序( o r d e r s ) 。在现实的各种决策活动中，存在多个独立的决策方进行决策时，有 时候需要这些局中人同时作出选择，有时，各局中人的决策又有先后之分，这也 就是次序问题。局中人的支付( p a y o f f s ) 。在所有局中人都选择了各自策略且博 弈已经完成之后，局中人获得的效用。局中人获得的期望效用，该期望效用是局 中人以及其他局中人选择的策略的函数。另外，博弈的结果( o u t c o m e ) 是指在博 弈结束之后，建模者从行动、支付和其他变量的取值中挑选出来的他所感兴趣的 要素的结合。对一个博弈的描述至少必须包括博弈方、策略和支付，而行动和信 息则是建筑的材料。 行动和结果合起来成为博弈的规贝j j ( r u l e so f t h eg a m e ) ，建模者的目的在于运 用博弈的规则来确定均衡。 纳什均衡的思想很简单，博弈的理性结局是这样一种策略组合，其中每一个 l o 郑州大学硕士学位论文 局中人均不能因为单方面改变自己的策略而获利。换一种说法就是，其中每个局 中人选择的策略是对其他局中人所选择策略的最佳反应。 一种混合策略盯为纳什均衡的条件是对所有f ，所有s 墨，下述不等式均 成立：( 一，矿，) 坼( i ，矿，) 。纯策略纳什均衡就是满足以上条件的纯策略组合 s 。在纳什均衡定义的基础上，可以进一步定义强纳什均衡，强纳什均衡是指每 个局中人对于对手的策略有唯一的最佳反应，即s 为严格纳什均衡，当且仅当对 所有f 和所有非i 的墨s ，均有( i ，) 坼( i ，) 成立。 原则上强纳什均衡是一个更具说服力的均衡概念，它具有稳定性，即使支付 中出现微小的扰动，强纳什均衡仍保持不变。而且由于局中人改变策略会使其利 益受损，所以局中人有维持均衡策略的动力。而纳什均衡中可能有的局中人会认 为均衡策略与其他策略之间是无差异的。所以并不能保证局中入一定会选择均衡 策略。强纳什均衡的弱点是，即使在混合策略意义下也不能保证存在性，相当多 的博弈局势中没有强纳什均衡。 纳什均衡的意义在于，它是关于博弈结局的一致性预测，如果所有局中人预 测一个特定的纳什均衡会出现，那么这种均衡就会出现，预测之间没有矛盾，不 会因为有的局中人认为不符合自己的利益要求而失败。只有纳什均衡才能使每个 局中人均认可这种结局，而且他们均知道其他局中人也认可这种结局。而非纳什 均衡的解决并非一致性预测，如果局中人预测会出现非纳什均衡，那么或者是局 中人的预测相互不统一，或者是局中人在估计别人的策略选择或极大化自己的支 付时犯了错误。 纳什均衡最重要的性质是“自我强制性”，如果局中人就纳什均衡结局达成 协议，那么不需要任何外力的帮助，它自身就蕴含着保障实现的力量。任何非纳 什均衡的结局要成为协定都需要外在强制力量的帮助，否则有的局中人将会有动 机背叛协定。纳什均衡的弱点在于，它并不能保证唯一性，存在多个纳什均衡时 哪一个会在现实中出现实个难以解决的问题。另外，引入其他理性考虑以后， 还需要详细考虑。 郑州大学硕士学位论文 2 2 1 规范型博弈 为了更清楚地说明一个博弈，有必要详细地介绍一下规范型博弈。规范型博 弈是表示形式上最简单的一种博弈。n 人的策略型博弈【5 9 】指定了n 个局中人 ( a g e n t i ) ，每个局中人有一个纯策略( 行动) 集s 和效用函数。墨是局中人 a g e n t i 的纯策略空间。墨给出了局中人a g e n t i 在进行博弈时可选择的行动集合。 a g e n t i 的混合策略为一个映射，以某种概率选取纯策略。每一个局中人对应一个 纯策略效用矩阵，矩阵的行是该局中人的纯策略，矩阵的列是其余局中人纯策略 的每一种组合。效用矩阵的值实际上给出了局中人的纯策略在每一种纯策略博弈 的可能结局上的效用。很明显地，对于一个含有n 个局中人，每个局中人有两个 纯策略的博弈，需要给出i 1 个矩阵，每一个矩阵的大小为2 ”。可见，博弈表示 的复杂程度是很高的。总之，一般地，是用效用矩阵来表示规范型博弈。 一个规范型博弈定义一个同时行动多a g e n t 的语义。每个局中人独立地选择 一个行动并且然后接受到一个依赖于所有局中人选择的行动的收益。更确切地 说，用g 表示一个具有1 1 个局中人集合的规范型博弈。每个局中人n n 有一个 离散的行动集合a n 和在彳= 1 1 “4 中的每个行动剖面入口的收益数组g n ，也 就是所有局中人的联合行动a - - ( a n t ，a t a ，娜1 ) 。我们用k 代指在m n ) 中局 中人的联合行动。 如果局中人在选择行动方面有决定性的限制，并不能保证一个均衡的存在。 然而，如果允许局中人能独立随机的选择行动，那么博弈论的核心结果保证混合 策略n a s h 均衡的存在( n a s h ，1 9 5 1 ) 。一个混合策略盯。是基于a 。上的一个概率 分布。 策略集n 被定义为所有混合策略的概率。混合策略的支持集是在a n 中具有 非零概率的行动的集合。局中人n 的混合策略仃。是一个纯策略，如果在它的支 持集中它只有一个纯策略在a 。中与决定性的行动相对应的纯策略。混合策 略剖面的集合是i - i 。a 。，单纯型的叉积。一个单独局中人的混合策略可以被表 示为概率向量，每一个行动一个向量。为了以后简单地表示我们串联这些向量并 郑州大学硕士学位论文 且把混合策略剖面盯作为一个m 维的向量，其中m = 膳ia 。ii 。在u 。彳。 中向量是由行动索引的，对于一个行动a 以，仃。是局中人1 1 选择行动a 的概率。 为了表示的方便，每一个行动是和特定的局中人使相联系的，不同的局中人不能 采取相同的行动。 一个混合策略剖面是由行动剖面的联合分布推导出的，我们能计算出与关于 这个分布的期望收益。让g 。( 仃) 表示局中人n 的期望收益当所有局中人按照策略 剖面盯行动时。我们能计算出这种值g 。( 盯) = g 。p ) u 盯址 a e 爿k e 在最一般的情况下也就是完全混合策略剖面，这种和包括博弈数组g 。的每 一个入口，和局中人的数目成指数大小。 2 2 2 图型博弈 在许多实际的博弈环境中，局中人策略间存在效用独立关系，也就是说，某 个局中人策略的效用并不是与其余的局中人都相关，往往只与有限的几个局中人 有关系。基于这样的思想：k e a r n s ( 2 0 0 1 ) 等人【3 】提出了一种博弈的无向图表示模 型：图型博弈。 在图型博弈中每一个结点表示一个a g e n t 也就是每一个结点表示一个局中 人，每个a g e n t i 与其它影响该a g e n t i 收益的a g e n t s 之间有一条边。每个a g e n t 都 有一个效用矩阵，它表示了邻域的a g e n t s 的局部博弈。在原有的静态博弈的表示 中，我们总是假设任何一个结点其策略效用是与其余n 1 个结点相关的，在这样 的情况下是n 个节点的完全图。在许多实际博弈环境中，节点之间的相关关系往 往是稀疏的，一个节点其策略效用往往只与几个其它节点相关，而非与其余n 一 1 个节点。图型模型的表示比规范型表示更加简洁，不论在何种情况下，无向图 都不会是一个团。模型中的图形拓扑能自然地表示出许多现实环境中博弈的内在 结构，例如具有层次关系的人类组织结构中的多人博弈可表示为一棵五向树，树 中的每一个节点对应一个局中人，行为间存在直接影响的局中人之间有线段连 接。 一个a g e n t 的策略效用可能只