（通信与信息系统专业论文）基于博弈论的cdma系统功率控制技术研究.pdf

西北f 业人学坝t 。论文：接于博毋；论的c d m a 系统功率控制技术研究 摘要 在c d m a 移动通信系统中，一个很重要的问题就是无线资源的有效利用。功 率控制则是无线资源管理中非常重要的组成部分，这在早期以话音业务为主的窄带 c d m a 系统中，已经做了很多研究。但随着无线数据业务日益增长的要求，就十分 迫切地需要建立一套新的功率控制算法来应对多媒体业务的迅速发展。 本文在博弈论的理论框架中对宽带c d m a 系统无线数据业务的功率控制问题 进行了研究。在这里，移动终端接收到的服务质量( q o s ) 可以认为是一种效用函 数，而分布式功率控制可以认为是每个用户参与其中并尽量最大化个人效用函数的 非合作式功率控制博弈。这种博弈的结果是其纳什均衡对于功率效用而言是无效的。 本文接着引入了发射功率的价格函数，从而得到了非合作式功率控制博弈的佩瑞多 ( p a r e t o ) 改进。最后给出了针对单小区c d m a 系统的数值分析结果。 【关键词】 博弈论码分多址功率控制无线数据服务质量 西北1 业大学硕i ：论文：基于博奔论的c d m a 系统功率控制技术研究 i i a b s t r a c t a m a j o rc h a l l e n g e i nt h eo p e r a t i o no fw i r e l e s sc d m ac o m m u n i c a t i o ns y s t e m si st h e e f f i c i e n th s eo fr a d i or e s o u r c e s o n ei m p o r t a n tc o m p o n e n to fr a d i or e s o u r c em a n a g e m e n t i s p o w e rc o n t r o l ，w h i c h h a sb e e ns t u d i e d e x t e n s i v e l y i nt h ec o n t e x to fv o i c e c o m m u n i c a t i o n s w i t ht h ei n c r e a s i n gd e m a n df o rw i r e l e s sd a t as e r v i c e s ，i ti sn e c e s s a r yt o e s t a b l i s hp o w e rc o n t r o la l g o r i t h m sf o ri n f o r m a t i o ns o u r c e so t h e rt h a nv o i c e w ep r e s e n ta p o w e rc o n t r o l s o l u t i o nf o rw i r e l e s sd a t ai nt h ea n a l y t i c a ls e t t i n go fag a m et h e o r e t i c f r a m e w o r k i nt h i sc o n t e x t ，t h eq u a l i t yo fs e r v i c e ( q o s ) aw i r e l e s st e r m i n a lr e c e i v e si s r e f e r r e dt oa st h eu t i l i t ya n dd i s t r i b u t e dp o w e rc o n t r o li san o n c o o p e r a t i v ep o w e rc o n t r o l g a m ew h e r eu s e r sm a x i m i z et h e i ru t i l i t y t h eo u t c o m eo f t h eg a m er e s u k si nan a s h e q u i l i b r i u m t h a ti si n e f f i c i e n t w ei n t r o d u c ep r i c i n go f t r a n s m i tp o w e r si no r d e rt oo b t a i n p a r e t o i m p r o v e m e n t o ft h e n o n c o o p e r a t i v ep o w e r c o n t r o l g a m e ，i e ，t o o b t a i n i m p r o v e m e n t i nu s e ru t i l i t i e sr e l a t i v et ot h ec a s ew i t hn op r i c i n g s p e c i f i c a l l y , w ec o n s i d e r ap r i c i n gf u n c t i o nt h a ti sal i n e a rf u n c t i o no ft h et r a n s m i tp o w e r t h es i m p l i c i t yo f t h e p r i c i n gf u n c t i o na l l o w sa d i s t r i b u t e di m p l e m e n t a t i o nw h e r et h ep r i c ec a nb eb r o a d c a s tb y t h eb a s es t a t i o nt oa l lt h et e r m i n a l s w es e et h a tp r i c i n gi se s p e c i a l l yh e l p f u li nah e a v i l y l o a d e d s y s t e m k e y w o r d s ： g a m e t h e o r y , c d m a ，p o w e rc o n t r o l ，q o s ，w i r e l e s s d a t a 西北，l 业火学硕上论文：基十博弈论的c d m a 系统功率控制技术研究 i 第1 章绪论 1 1 论文研究的背景和意义 在c d m a 移动通信系统中，由于所有的用户均使用相同频段的无线信道和相 同的时隙，用户间仅靠地址扩频码的不同，即靠它们之间互相关特性加以区分。若 用户问的互相关特性不为零，则用户之间就存在干扰多址干扰。由于c d m a 为一干扰受限系统，即干扰的大小直接影响系统容量，降低干扰可以直接增加 c d m a 系统的通信容量。因此有效地克服和抑制多址干扰就成为c d m a 系统中最 主要、最关键的问题之一i l 2 j 。 除了多址干扰本身直接的影响以外，在上行链路( u p l i f t ) 中，如果保持小区 内所有移动台的发射功率相同，由于小区内移动台用户的随机移动，使得移动台( m s m o b i l es t a t i o n ) 与基站( b s ，b a s es t a t i o n ) 间距离是不同的，离基站近的移动台的 信号强，离基站远的移动台信号弱，将会产生“以强压弱”的现象，使弱功率信号 用户的性能下降，甚至不能工作，这就是所谓的“远近效应( n e a r - f a rp r o b l e m ) ”。 在下行链路( d o w n l i n k ) 中，当移动台位于相邻小区的交界处时，收到所属基站的 有用信号功率很低，同时还会受到相邻小区基站较强的干扰，这就是所谓的“角效 应( c o m e r p r o b l e m ) ”。同时，电波传播中由于大型建筑物的阻挡，形成“阴影”效 应产生了慢衰落。这些现象将会导致系统容量下降和实际通信服务范围缩小等。解 决这些问题的一个最有效的方法是采用功率控制方法( p o w e rc o n t r 0 1 ) 。此外，c d m a 移动通信系统中通信链路的建立和用户所需的服务质量( q o s ，q u a l i t y o f s e r v i c e ) 的维护也在很大程度上依赖于功率控制技术。因此，功率控制对c d m a 移动通信 系统性能的影响很大i 3 “。 先前大量功率控制的研究工作都集中在针对话音业务5 - 7 】的研究。相对来讲，针 对数据业务的研究就少了很多。如何在数据通信的情况下提高蜂窝移动系统的性能 就变得十分急迫和紧要了。无论是第二代c d m a 系统i s 9 5 还是第三代c d m a 系 统w c d m a 、c d m a 2 0 0 0 ，由于小区内的用户是用相同的频谱资源。功率控制的作 西北f 业大学仁论文：基于博峁论的c d m a 系统功率控制技术研究 用就尤其重要了。 博弈论( g a m et h e o r y ) 在经济学中的是指博弈中的各个局中人理性的选取自 己的策略行为，从而在这个相互制约、相互影响、相互依从的关系中，尽可能地提 高自己的利益所得【8 j 。一个参与者将自己置身于其他参与者的位置并为他着想，从 而预测其他参与者将会选择的行为，在这个基础上，该参与者决定自己最理想的行 为，这就是博弈论方法的本质与精髓。 从经济学观点来看功率控制的过程就是一个博弈过程，从微观经济学的理论中 找到了支持，即可以在由数据业务的效用函数所构成的考察对象中，寻找到这个过 程的纳什均衡点。相对于微观经济学，数据通信中的q o s 指的就是效用函数( u t i l i t y f u n c t i o n ) 。在常规的功率控制过程中( 这晕考虑移动台基站的闭环功率控制) ， 都采用分布式的功率控制，每个移动台都根据由无线环境的干扰状况得到的功率控 制信号来决定自己的发射功率。这里引入了效用函数，通过实现效用函数的最大化， 以实现对移动台发射功率的优化。 效用函数( u t i l i t yf u n c t i o n ) 是指个人使用某种商品和服务所感受到的满意程 度。在无线通信中，q o s 和效用函数很相似。在第三代移动通信系统中，每个移动 台都对其他的用户产生共道干扰。每个移动台的用户就是博弈论中的一个局中人， 整个用户群对无线资源的使用和竞争就组成了一个博弈过程。既然把小区内的功率 控制过程作为一个博弈过程来研究，那么就可以利用经济学的方法来寻找这个工作 点。根据文献 9 】中引用的d e b r r e u 和c l i s c k s b e r g 的理论连续无限博弈中纳什均 衡的存在性，可以认为在功率控制这个博弈过程中存在一个纳什均衡点。纳什均衡 是这样的全局策略向量：为了极大化自己的盈利( 或者效用) 函数，每一个局中人所 采取的策略一定应该是关于其他局中人所采取策略的最佳反应，因此，没有一个局 中人会轻率地偏离这个策略组合向量，而使得自己蒙受损失。 由以上= 分析，我们就可以考虑将经济学领域中已经相对比较成熟的博弈理论引 入到目前移动通信中备受关注的功率控制问题中来。这是一个新的领域，包含了无 线蜂窝通信、控制理论和经济理论中的交叉问题，非常新颖，思想大胆而具实用性， 对目前已有的功率控制方法是个很好的补充。因此本文将基于博弈论的c d m a 系 统功率控制技术研究作为研究内容。 两北r 业大学颤卜论文：娃卡博亦论的c d m a 系统功牢控制技术研究 1 2国内外研究状况 近年来，国际学术界对通信技术、 叉投入了相当的热情，在建模、分析、 的高度。 计算机网络技术、控制技术等学科的相互交 控制与优化等问题的研究已经达到了一个新 目前，对于博弈论在通信领域中的运用，特别是无线网络功率控制领域的研究， 国际上以美国u n i v e r s i t yo fi l l i n o i s 的t a m e rb a a r 教授和p o l y t e c h n i cu n i v e r s i t y 的 d a v i dj g o o d m a n 教授各自领导的研究小组为主，同时贝尔实验室、r u t g e r s u n i v e r s i t y 国家科学基础研究中心的无线信息网络实验室( w i n l a b ) 等一些美国通 信信息理论方面的著名实验室都对此投入了相当的关注，自1 9 9 8 后相继发表了一系 列的高水平文章 1 01 3 “7 】。相对而言，国内学者在此方面的研究工作开展的较晚，目 前仅有清华贝尔中国联合实验室和上海交大开展了相应工作1 ”。 r o yd y a t e s 较早研究了在上行链路中影响功率控制问题的若干因素。 t a n s u a l p c a n 和t a m e r b a a r 在功率控制中引入了支付函数( c o s t f a n c t i o n ) ，并提出了 两种上行链路中的改进算法。c e mu s a r a y d a r 和n a r a y a nb m a n d a y a m 改进了用 于多小区的分布式功率控制技术，提出了发射功率的“价格”概念，并将之作为一 种影响用户传输数据行为的控制机制i l ”。d a v i dg o o d m a n 与m ls h a h 都讨论了基 于效用函数和价格函数的功率控制机制，并谈到了关于p a r e t o 有效性的问题f 1 6 1 7 1 。 1 3论文的内容与结构安排 本论文主要研究了基于博弈理论的c d m a 无线数据网络的功率控制技术。在 论文的内容结构上做了以下安排： 第一章即绪论，介绍了本次论文所研究的内容、研究背景和研究意义，国内外 在这个领域的研究状况，以及论文的结构安排。 第二章介绍了博弈论的基础知识。包括博弈论的定义、产生与发展、博弈理论 的一些基本概念、博弈论的分类方式、博弈论模型的建立。最后介绍了一个典型的 博弈论问题，并给出了求解思路。 两北丁业大学硕k 论文：箍于博弈论的c d m a 系统功率控制技术研究 第三章较系统地分析了无线通信网络的功率控制问题。分别介绍了功率控制的 目的、功率控制准则与基本方法，对窄带c d m a 系统和宽带c d m a 系统的功率控 制方法做了详细分析并对比了各自的不同性。 第四章是论文的重点，具体研究了基于博弈论的c d m a 系统功率控制方法。 首先，介绍了效用函数的概念，提出了普适的效用函数表达式，进而分析了效用函 数的性质，研究了数据通信系统的效用函数。接着，将效用函数引入到功率控制问 题中，提出了非合作博弈功率控制( n p g ) 的概念，求出了在n p g 中的纳什均衡， 并分析其特性。最后，提出价格函数的概念，建立价格函数模型，提出了净效用函 数的概念，从而对n p g 算法进行改进，并达到了p a r e t o 有效。 第五章为第四章的算法设计了一个仿真系统环境，分别对n p g 和n p g p 算法 进行了数值仿真，得到结果并分析，从而验证了理论的正确性。 第六章对整个论文进行了总结并提出了以后工作的发展方向。 西北t 业人学硕 j 论文：基于博负论的c d m a 系统功率控制技术研究 5 第2 章博弈论基础 博弈论是微观信息经济学的重要理论之一。博弈论源于奕者的战略思考，其思 想源远流长，能作为现代博弈论研究对象和研究内容的博弈思想与实践活动，从世 界范围来看，最早可追溯到中国古代。早在公元前5 1 2 年的我国春秋战国时代孙武 所著的孙子兵法一书中的军事思想，以及“田忌赛马”事例就是最早的博弈论 思想和博弈论应用案例。 大多数学者认为，博弈理论开始于1 9 4 4 年冯诺依曼( j o h n v o n n e u m a n n ) 和 经济学家摩根斯坦( o s k a rm o r g e n s t e m ) 合作的博弈论与经济行为( t h et h e o r yo f g a m e sa n de c o n o m i cb e h a v i o r ) 一书。经过几十年的发展，到了2 0 世纪8 0 年代后 期，博弈论进入繁荣时期，众多博弈论专家产生了许多研究成果，博弈论的应用范 围也不在只是经济学的一个分支，而成为一种方法论，在政治学、军事、外交、国 际关系、公共政策、犯罪学等领域都得到了广泛应用。 2 1博弈论的产生和发展 博弈论的英文是g a m et h e o r y 或t h e o r yo f g a m e s ，又译为对策论、游戏理论、 竞赛理论。g a m et h e o r y 被称为游戏理论是因为g a m e 的基本意义是游戏，不过“游 戏理论”是一种容易让人觉得浅薄的词汇，而博弈论或者对策论是一种学术味较浓 的词汇。g a m et h e o r y 被视为数学的一个分支时，一般译为对策论。“博弈论”的这 种译法来自于港台地区，由于它更贴近英语原文的风格以及更为直观，逐渐流行起 来。目前中国出版的多数g a m et h e o r y 著作都称为博弈论，本文也将g a m et h e o r y 称为博弈论。 严格地说，博弈论并不是经济学的一个分支。它是一种方法论，应用范围也不 限于经济学，政治学、军事、外交、国际关系、公共选择、犯罪学都涉及到博弈论。 但由于它在经济领域的应用最为成功、最为，。泛，经济学家对博弈论的贡献也越来 越大，因此一般把博弈论列为经济学范围。 两北丁业大学倾t 论文：基于博峁论的c d m a 系统功率控制技术研究 2 ，11 博弈论的定义 在关于博弈论的文献a t ”五2 1 ，给出的博弈论的定义不尽相同，如： ( i ) 搏弈论提供了一种在相互作用的决策条件下建模和分析的框架及语言，该决 策条件是指有着( 部分) 相互冲突目标的多个决策者互相产生影响”1 。 ( 2 ) 博弈论是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的 均衡问题，也就是说，当一个主体，好比一个人或一个企业的选择受到其他人、其 他企业选择的影响，同时反过来影响到其他人、其他企业选择时的决策问题和均衡 问题f 1 9 】。 ( 3 ) 博弈论是研究博弈情景下博弈参与者的理性行为选择的理论；或者说，它是 关于竞争者如何根据环境和竞争对手的情况变化，采取最优策略和行为的理论【2 0 】。 ( 4 ) j o h nc h a r s a n y i ( 因对非合作博弈论的杰出贡献，1 9 9 4 年诺贝尔经济学奖获 得者之一) 在诺贝尔奖辞中是这样定义博弈论的：“博弈论是关于相互作用的理论， 就是说，它是关于社会形势中理性行为的理论，其中，每个局中人对自己行动的选 择必须以他对其他局中人将如何反应的判断为基础。”【2 1 】 ( 5 ) 博弈论是一个分析工其包，它被设计用来帮助我们理解所观察到的决策主体 相互作用的现象【2 2 1 。 上述关于博弈论的定义虽然在描述上有所不同，但在本质上是基本一致的。这 里用一句话来概括什么是博弈论：博弈论是在决策者具有相互冲突目标或相互影响 条件下的一种策略选择理论。 2 1 2 博弈论的发展 对具有博弈性质的决策问题的零星研究可以上溯到1 8 世纪或者更早。但是系统 的博弈理论的建立和发展则是2 0 世纪中叶。j o l 1v o nn e u m a n n 和o s k a r m o r g e n s t e r n 合著的博弈论和经济行为( t h e o r y o f g a m e sa n de c o n o m i cb e h a v i o r ) 于1 9 4 4 年出版，标志着系统的博弈理论的初步形成。五六十年代是博弈论研究、发 展的重要阶段。合作博弈论在5 0 年代达到顶峰，非合作博弈论也开始创立。 约翰纳什( j o h n n a s h ) 在1 9 5 0 年和1 9 5 1 年发表了两篇关于非合作博弈的重 两北丁业人学坝卜论文：捧于博奔论的c d m a 系统功率控制技术研究 要文章，在非常一般的意义上定义了非合作博弈及其均衡解，并证明了均衡解的存 在，基本上奠定了现代非合作博弈论的基石。因而，该均衡以后被博弈理论称为“纳 什均衡”( n a s h e q u i l i b r i u m ) 。纳什均衡是指由所有参与者的最优策略组成的策略组 合。在这种策略组合中，给定其他参与者的策略，没有任何单个参与者有积极性选 择其他策略，也就没有人主动去打破这种均衡；相反，如果一种均衡或制度安排， 如果不是一种纳什均衡，即不是所有参与者的晟优策略组合，就不能成立或者至少 不能持续。这就是纳什均衡的哲学思想。合作搏弈强调团体理性、效率和公平；而 非合作博弈强调个人理性、个人最优决策，其结果可能是有效率的，也可能是无效 率的。现实中，大量的经济博弈问题是非合作博弈。非合作博弈理论的发展为其在 经济研究中的广泛应用创造了条件，而后者又反过来推动了前者的进一步发展。 纳什均衡假定博弈参与者选择自己的策略时，把其他参与者的策略当作给定的， 而不考虑自己的选择如何影响博弈对手的选择。这种假定在静态博弈下是成立的， 但在动态博弈下却不成立。在静态博弈中，所有参与者同时行动，不可能在自己采 取行动前观察到其他人的行动，因而就无法反应。但在动态博弈中，一方行动在先， 另一方行动在后，后者自然会根据前者的选择而调整自己的选择，前者也自然会理 性地预期到这一点，所以不能不考虑自己地选择对其他参与者的影响。由于决策者 不考虑自己的选择对其他人选择的影响，纳什均衡允许了不可置信威胁的存在。1 9 6 5 年，泽尔腾( s e l t e n ) 将纳什均衡的概念引入了动态分析，定义了“子博弈精练纳什 均衡”的概念，将不可置信的威胁策略从纳什均衡中剔除出去，从而解决了完全信 息动态博弈均衡求解的问题。将不可置信的威胁策略变成可置信策略的行动就是经 济学中的“承诺行动”。如果当事人不履行其承诺时将为之付出相应的代价，这种承 诺就是可置信的，否则就是不可置信的。该概念的提出，对于利用博弈论方法研究 许多经济政策问题奠定了基础。 但是，以上分析都是假定博弈参与者对博弈结构、博弈规则和博弈的得失均具 有完全的了解，即具有关于博弈的完全信息，而现实中，绝大多数博弈中的信息是 不完全的。对于这种不完全信息博弈，以上博弈论的方法是无能为力的。1 9 6 7 年， 海萨尼( h a r s a n y i ) 为解决此问题作出了巨大贡献。他引入了一个虚拟参与者 “自然”。博弈中，自然首先行动选择参与者的“类型”。各个参与者知道自己 两北丁业大学硕l 二论文：蛙于博夯论的c d m a 系统功率控制技术研究 的真实类型，却不知道其他参与者的真实类型，而仅知道各种可能类型的概率分布。 这种分布函数是“共同知识”，为每个参与者所了解。海萨尼的这一工作被称为“海 萨尼转换”。通过这一转换，把不完全信息博弈转换成为完全但不完美信息搏弈，从 而使得巧i 完全信息博弈变为可分析的了。在此基础上，他定义了“贝叶斯纳什均衡”， 作为纳什均衡在不完全信息博弈中的自然扩展；给定参与者自己和他人各自类型的 概率分布，每个参与者的期望效用达到最大化，因而，没有人有积极性去选择其他 策略。这是不完全信息静态博弈的均衡解。 不完全信息动态博弈的均衡则是泽尔腾等人的贡献。1 9 7 5 年，泽尔腾定义了“颤 抖手的均衡”( t r e m b l i n g h a n de q u i l i b r i u m ) ，克锐普斯( k r e p s ) 和威尔逊( w i l s o n ) 定义了“序贯均衡”( s e q u e m i a le q u i l i b r i u m ) ，弗得伯格( f u d e n b e r g ) 和泰勒尔( t i r o l e ) 则给出了“完美贝叶斯均衡”( p e r f e c tb a y e s i a ne q u i l i b r i u m ) 。这三个概念在许多情 况下是一致的。其要点为：博弈参与者要根据其观察到的他人行为来修正自己有关 后者类型的主观概率，并据此选择自己的策略行动。修正过程使用贝叶斯规则。现 实中许多经济决策问题都是一种不完全信息动态博弈问题。该博弈均衡解的给出， 为博弈论方法在经济学领域的应用开辟了更加广泛的前景。 上世纪7 0 8 0 年代，博弈论在经济理论中的应用得到迅速的发展，并逐步成为 西方经济学的一部分，在现代微观经济学、产业组织理论和宏观经济政镱分析方面 都得到广泛的应用。 1 9 9 4 年诺贝尔经济学奖授予了三位博弈论专家：纳什、泽尔腾和海萨尼；1 9 9 6 年又授予两位博弈论专家：詹姆斯米尔利斯( j a m e s a m i r r l e s s ) 和威廉维克里 ( w i l l i a m v i c k e r y ) ，以表彰他们对不对称信息条件下激励经济理论做出的开拓性和 奠基性贡献。这表明博弈论已经在经济学领域发挥了重大作用，产生了巨大影响。 博弈论作为一种专门研究参与者之间相互依赖、相互影响的决策行为及其结果 的方法，特别强调参与者的理性行为及其相互关系，强调决策信息和决策时序对决 策行为及其后果的影响。这与现代经济学发展的趋势相一致，而它严密的逻辑结构 和分析方法也为现代经济学的理论研究提供了一个有效的分析工具。 两北f 业人学坝 ：论文：基f 博弈论的c d m a 系统功率控制技术研究 9 2 21 有关术语的约定 2 2 博弈论的理论概述 在对博弈论进行分析之前，有必要先对博弈论中出现的相关术语给予一个统一 的约定。 2 2 1 1 博弈的基本要素 表述一个完整的博弈问题至少需要3 个基本要素，即博弈方( p l a y e r ) 、策略集合 f s t r a t e g ys e t ) 以及支付函数( p a y o f f f u n c t i o n ) 。 ( 1 ) 博弈方( p l a y e r ) 博弈方，或称局中人，是参预博奔的直接当事人，他是博弈的决策主体和策略 制定者。在不同的博弈中博弈方的含义是不同的，即可以是个人也可以是团体或者 集团，但这些团体或集团必须是为了一个共同的目标和利益参加博弈的。 博弈模型中要求博弈方是“理性”的。所谓“理性”，一般不是指道德标准。从 参加博弈的局中人的眼光来看，他们试图去实施自己认为可能最好的行为，尽管这 种行为有可能损害了其他的局中人。因此“理性行为”似乎有点“利己，不管是否 损人”。从博弈分析人员的“旁观”眼光来看，一般不会去擅自判断局中人的动机究 竟如何。由于局中人的相互依存性，博弈中一个理性的决策必定建立在预测其他局 中人的反应之上。一个局中人将自己雹身于其他局中人的位置并为他着想从而预测 其他局中人将选择的行动，在这个基础上该局中人决定自己最理想的行动，这就是 博弈论方法的本质和精髓。所以博弈方应该清楚的知道自己的目标和利益所在，在 博弈中总是采取最佳策略以实现其效用和利益的最大化。 ( 2 ) 策略组合( s t r a t e g ys e t ) 策略组合是指博弈方可能采取的全部策略的集合，它是博弈方进行博弈的工具 和手段，每个策略集合至少应该有两个不同的策略。 ( 3 ) 支付函数( p a y o f f f u n c t i o n ) 当所有的博弈方采取的策略确定后，他们就有各自的“支付函数”，或者称“盈 两北丁业人学倾 ：论文：甚于博穿论的c d m a 系统功率控制技术研究 利函数”。支付函数表达了搏弈方从博弈中能够得到的收益或效用水平，它是所有博 弈方策略的函数。不同的策略可能导致不同的收益，它是每个局中人真正关心的东 西。 搏弈论中的每一个局中人做出理性决策的重要依据之一是他的可能盈利有多 少，这就是一个局中人需要认真计算的盈利函数。对于每一个局中人，如果他们在 可供自己选择的镱略空闯中任取一策略作为自己的行动，既不会给自己带来盈利， 又不会使他们必须付出，这种失去了激励机制的游戏本身也就失去了“博”的意义， 在社会经济领域中尤其不太可能出现这类现象。盈利函数的结构与取值无疑将会影 响到局中人的行为，因而也影响到 弈论研究中是件非常重要的事情。 出发可以有形形色色的盈利函数， 2 2 1 2 博弈的分类方式 了博弈的最终结局。由此，盈利函数的确定在博 从对博弈的不同角度考虑，从局中人不同的观点 并不唯一。 博弈按照不同的角度有不同的分类。 按照博弈方之间的策略选择是否存在时间的先后次序，博弈可分为静态博弈和 动态博弈。如果博弈之间同时进行决策选择，或虽非同时但后行动者并不知道先行 动者采取了什么具体行动，则称为静态博弈；在动态博弈中，博弈方的策略选择有 先后次序，后行动者能够观察先行者的策略选择，并在此基础上采取自己最有利的 策略。 按博弈方是否捌有其它博弈方决策方面的信息，博弈可分为完全信息博弈 ( c o m p l e t eg 啪e ) 和不完全信息博弈( i n c o m p l e t eg a m e ) 。在完全信息博弈中，每一个博 弈方都拥有其它博弈方的特征、策略集合和支付函数等方面的正确信息：在不完全 信息博弈中，博弈方只能了解上述信息的一部分。 将e 述两个角度的分类结合起来，可得到四种不同类型的博弈：完全 博弈、完全信息动态博弈、不完全信息静态博弈和不完全信息动态博弈。 类博弈相对应的四个均衡概念是：纳什均衡( n a s he q u i l i b r i u m ) 、子博弈精 信息静态 与上述四 炼纳什均 衡( s u b g a m ep e r f e c t n a s he q u i l i b r i u m ) 、贝叶斯纳什均衡( b a y e s i a nn a s he q u i l i b r i u m ) f f t l 精炼贝叶斯纳什均衡( b a y e s i a n p e r f e c t n a s h e q u i l i b r i u m ) ，见表2 1 。 啊北r 业人学坝0 论文：捧卜博丹论的c d m a 系统功率控制技术研究 l l 表2 i | 尊奔的分类及其均衡 卜顺序 佶r 、 静态动态 完全信息静态博奔 完全信息动态博弈 完全信息 ( 纳什均衡) ( 予博弈精炼纳什均衡) 不完全信息静态博奔不完全信息动态博弈 不完全信息 【贝时斯纳什均衡)( 精炼贝叶斯纳什均衡) 应该指出的是，博弈论的均衡概念与我们一般均衡理论中讨论的均衡概念是不 同的。比如，在一般均衡理论中，价格均衡指的是由个人最优化行为导致的一组价 格，而在博弈论里，这样的一组价格只是均衡的结果而不是均衡本身。事实上，博 弈论里的均衡是指所有个人的买卖规则( 战略) 的组合，均衡价格是指这种战略组 合产生的结果。 此外，按照博弈方的策略是否有限，可以把博弈分为有限博弈与无限博弈。 按照博弈方之间是否达成一致的协议，博弈论可以划分为合作博弈( c o o p e r a t i v e g a m e ) 和非合作博弈( n o n - c o o p e r a t i v eg a m e ) 。如果在博弈过程中，博弈方之间的 协议、承诺或威胁具有完全的约束力并且能够强制执行，则称为合作博弈( c o o p e r a t i v e g a m e ) ：否则，称为非合作博弈( n o n - c o o p e r a t i v eg a m e ) 。 划分这两种博弈的标准主要在于当事人之间能否达成一个具有约束力的协议。 如果能达到这么一个协议，就是合作博弈；反之，则是非合作博弈。h a r s a n y i 指出， 如果一个博弈中，意愿表示( c o m m i t m e n t ) 如协议、承诺、威胁等具有完全的约束 力而且可以强制执行，则该博弈为合作博弈。如果意愿表示是不可强制执行的，即 使局中人之州在博弈前进行了交往、谈判和协商，该博弈也是非合作博弈。也就是 蜕，合作博弈与非合作博弈的区别在于意愿表示的可信与否。在合作博弈中存在强 制机制使得局中人不能反悔，局中人一旦发出了威胁或者一旦达到了协定就不能收 回、不能改变，必须执行。而在非合作博弈中，局中人完全从自己的利益出发采取 策略( 经济学假定人是理性的) ，即使答应对方要合作，也是不可信的，因为没有强 制力量保证他信守诺言。合作博弈强调的是集体理性( c o l l e c t i v er a t i o n a l i t y ) 、效率 堕! ! 王些点堂堡! 丝壅：苎堕堂堡堕! 里坚垒墨堑些兰塑型塾查 塑壅旦 ( e f f i c i e n c y ) 、公正( f a i r n e s s ) 、公平( e q u a l i t y ) 。而非合作博弈强调的是个人理性， 其结果通常不满足集体理性，而且可能是有效率的，也可能是没有效率的。 目前非合作博弈论在整个博弈论中占据着主导地位，在最近的一、二十年中， 以纳什均衡为核心的非合作博弈理论的发展明显快于合作博弈理论。当前很多的流 行博弈论教科书中甚至没有合作博弈论的位置。 按照博弈方之间冲突的性质，博弈可分为对抗性博弈与非对抗性博弈。在对抗 性博弈中，博弈方的收益或效用完全对立，一方所得必是另一方所失，一方的利益 增加必使另一方收益减少。在对抗性博弈中，如果博弈方不管采取何种策略，各自 的收益之和恒为零，则称之为零和博弈；如果各自的收益之和为常数，则称之为常 和博弈。在非对抗性博弈中，博弈方有各自的不同收益值，其和不再等于零或者常 数，博弈方之f n j 的收益既有冲突又一致。 2 2 2博弈论模型的基本表达形式 博弈论模型有三种基本表达形式，即标准型博弈、扩展型博弈和特征函数型博 弈。这是j o h nv o nn e u m a n n 和o s k a rm o r g e n s t e m1 9 4 4 年在他们的划时代巨著 t h e o r yo f g a m e s a n de c o n o m i cb e h a v i o r ) ) 中首先加以全面区分和描述的a 现代博 弈理论一般认为，标准型和扩展型博弈被用来表现非合作博弈局势，而特征函数型 博弈被看作合作博弈的基本研究工具。 2 2 2 1 标准型博弈 标准型( n o r m a l f o r m ) 博弈，又称为策略型( s t r a t e g i c f o r m ) 博弈或者矩阵型 f m a t r i x f o r m ) 博弈。标准型搏弈将现实博弈局势抽象为三个基本要素：局中人 ( p l a y e r s ) 、策略( s t r a t e g i e s ) 和支付函数( p a y o f f f i m c t i o n ) 。标准型博弈包括三个要素： ( 1 ) 博弈局中人的集合：i n ，n = ( 1 , 2 ，h ) ： ( 2 ) 每个局中人的策略集合：x 。，i = 1 , 2 ，”； ( 3 ) 每个局中人的支付函数：j f ：，f _ 1 , 2 ，h ： 一般用g = 留，x ”；# ，只 代表标准型博弈。标准型博弈假定各局中人同 堕! ! ! 些叁堂塑! ：堕兰：生堕堑堡堕兰里些垒墨堑些兰丝型垫查堑塑旦 时选择自己的策略，也就是说，每个局中人均在不知道其他人实际策略选择的情况 下做出自己的选择。标准型博弈表现的是所滑的静态博弈( s t a t i cg a m e ) 。 2 2 2 2 扩展型博弈 扩展型( e x t e n s i v e f o r m ) 博弈的描述包含六种要素： ( 1 ) 局中人的集合：i n ，n = ( 1 , 2 ，竹) ； ( 2 ) 局中人的行动顺序( t h eo r d e ro f m o v e s ) ；表明什么人在什么时候行动； ( 3 ) 局中人的行动空间( a c t i o ns e t ) ：在每次行动时，局中人有些什么行为可供 选择； ( 4 ) 局中人的“信息集”( i n f o r m a t i o ns e t ) ：每次行动时，局中人知道些什么； ( 5 ) 局中人的支付函数：在行动结束时，每个局中人得到些什么； ( 6 ) 外生事件( 即“自然”的选择) 的概率分布。 相对于标准型博弈，扩展型博弈引入了新的组成要素，即行动的先后次序，这 极大地扩展了博弈理论所能描述的范围，因为现实中往往存在人们选择的先后次序。 扩展型博弈中局中人在选择自己的策略时对在他之前行动的局中人所选择的策略有 着充分或者不充分的了解。扩展型博弈表现的是所谓的动态博弈( d y n a m i cg a m e ) 。 2 2 2 3 特征函数型博弈 特征函数型博弈又被称为联盟型博弈。也有人直接将联盟博弈( c o a l i t i o m a l g a m e ) 称为合作博弈。特征函数型博弈包括两大类，一类为可转移支付联盟博弈 ( c o a l i t i o n a lg a m ew i t h t r a n s f e r a b l e p a y o f f ) ，即有旁支付( s i d e p a y m e n t ) 假设( 各局 中人都用相同的尺度柬衡量他们的赢得，各联盟的赢得可以按任意方式分摊给各个 局中人) 的合作博弈：另一类为不可转移支付联盟博弈( c o a l i t i o n a lg a m e w i t h n o n t r a n s f e r a b l ep a y o f f ) ，即没有上述旁支付假设的合作博弈。 令局中人集合为= ( 1 ，2 ，n ) ，则称的任意子集s 为联盟( c o a l i t i o n ) ，所 有联盟的全体 i 三为州) 。可转移支付联盟博弈包括两个要素： ( 1 ) 一个有限集合n ( 局中人集合) ； 两北t 业大学碳l 二论文：摧于博弈论的c d m a 系统功率控制技术研究 ( 2 ) 将的每个非空子集s ( 即一个联盟) 与某个实数v ( s ) 相联系的一个特征 函数v 。 可转移支付联盟博弈可记为( ，y ) 。这旱特征函数v 是指定义在r ( ) 上的一 个实函数，其中y ( s ) 表示联盟s 通过协调其成员的策略所能保证得到的最大赢得。 不可转移支付联盟博弈包括下列要素： ( 1 ) 一个有限集合( 局中人集合) ； ( 2 ) 一个集合x ( 结果集合) ： ( 3 ) 一个对的每一非空子集c 一个联盟) 赋一个集合v ( s ) x 的函数n ( 4 ) 对每个局中人i n 有一个x 上的偏好关系。 不可转移支付联盟博弈可以记为( ，y ，x ，( 乏) 。) 。在可转移支付联盟博弈 中每个联盟s 是以唯一的一个数v ( s ) 为显著特点的：在不可转移支付联盟博弈中每 个联盟不必得到某个固定支付的所有分配；而且每个联盟s 是以一个任意的结果集 合矿( s ) 为显著特征的。 标准型博弈、扩展型博弈和特征函数型博弈这三种博弈模型的基本表达形式之 间存在着某种联系。扩展型博弈详细说明了博弈运行次序与信息结构细节，具有最 丰富的信息。在扩展型博弈的基础上省略掉扩展型博弈的行动次序，即可以简化出 标准型博弈，这当然在细节上有所损失。对标准型博弈，如果引入义务是有约束力 的，且可强制执行的假设( 即合作博弈的前提) ，省略掉策略细节，则可以进一步简 化为特征函数型博弈。 2 3经典博弈模型分析 本节中，将讨论一个经典的博弈问题“囚徒困境”( p r i s o n e r s d i l e m m a ) ， 借以展现博弈论问题的一般分析方法。 “囚徒困境”在博弈理论中拥有重要的地位，它是一个经典的、几乎每本博弈 论教材都必讲的博弈问题。这里介绍的是传统的两人“囚徒困境”问题。 “囚徒困境”描述了这样一个故事：甲、乙两个人共同作案而被警方抓获，他 们分别被关在不同的屋子里接受警察的审问，并获知警方向他们公开的有关政策( 两 西北丁业人学埘【：论文：鼎于博毋论的c d m a 系统功率控制技术研究 1 5 个局中入的共同知识) 。在互不知晓同伴怎样做的情况下，甲乙两人都面i 临两种选择 坦白与抗拒。如果甲乙双方互相合作而拒不坦白，那么由于证据不足从而在各 关个月后获得释放：如果他们都采取背叛对方的策略而坦白全部作案事实，那么 根据案情将被囚禁8 个月；如果两人中有一人拒不坦白，而另一个人却坦白罪行， 那么坦白者因立功而被释放，抗拒者则受到严惩被关1 5 个月。因此这构成个完全 信息的静态博弈。两个局中人的切身利益是关系囚禁多少时间而不是盈利多少，因 而称图2 1 所示的矩阵为效用矩阵或支付矩阵( p a y o f f m a t r i c e s ) 。 z 坦白 田 抗拒 坦白抗拒 一8 一8 0 ，一1 5 一1 5 ，0 1 一i 幽2 1 囚徒困境的效用矩阵 图2 1 中效用矩阵对于甲、乙两人是对称的，因此仅考虑从甲的角度出发，甲 坦白的效用向量( 一8 ，0 ) 显然大于甲抗拒的效用( 一1 5 一1 ) ( 因为 一8 一1 5 ，0 一1 ) 。因此抗拒是甲的最差策略，由对称性，抗拒也是乙的最差策略。 理性的甲与乙都会舍弃差的策略，于是( 坦白，坦白) 就成为博弈的最佳选择。博 弈双方为了自身利益导致了( 一8 ，一8 ) 效用的结局，可惜这是一个“无效”的结 局。具体分析思路如图2 2 所示。 如果乙坦白 厂1 r l 了7 孓一 坦白抗拒 如果乙抗拒 冥 l 叫l 、j l _ j ib 。s t 图2 2 凶徒困境的分析过程 在该博弈中，两个囚徒决策时都是以实现自己的最大利益为目标，但最终结果 却无法达到各自的最大利益甚至较大利益。由于个体的理性导致双方最终得益比可 茜 两北丁业大学硕士论文：基于博弈论的c d m a 系统功率控制技术研究 能得到的少，这就是囚徒的“困境”。 这罩引入了经济学中“有效”的术语。如果不存在其他的结局，使得某些局中 人的效用比在这个结局的效用好得多，同时又不会使其他局中人的效用变得更差， 则称博弈的这个结局是有效的( e f f i c i e n t ) 。反过来，如果一个结局不是有效的，则 一一定( 至少) 存在另外一个受到局中人一致欢