（应用数学专业论文）几类重复对策的合作与非合作解决方案及其算法研究.pdf

擒要 摘要 本文所研究的对策类型均是具有完全信息的。本文针对合作、部分合作、完全 合作情形下的重复扩展型对策的最优解展开研究工作。研究对象包括对策树上的重 复对策以及具有状态支付的连通图上的重复对策。 本文第一章主要研究对策树上的重复对策，研究了非合作的重复对策，同时我 们知道不完全合作的重复对策进程通常伴随着联盟结构的变化，某些局中人因为某 种原因可能离开上一阶段的联盟而加入更有利于自己利益的新联盟。本章给出了具 有变化联盟结构的重复扩展型对策的p m s 值的完整算法，并以此作为最优准则探索 对策进程中的最优含作方式，并希望在特定最优准则的基础上探索最优联盟结构形 成所遵循的法则。 本文第二章通过在连通图的每个状态节点处引入状态支付向量，在有限图上研 究考察动态重复对策。运用c b e r g e 关于图上对策中策略的概念，主要考虑菲合 作情形，证明了在简单策略意义下具有状态支付向量的连通图上重复对策中绝对均 衡的存在性定理，给出其完整的算法以及在一个三维连通网格图上的计算示例。 本文第三章在第二章的基础上研究具有状态支付向量的有限图上合作动态重 复对策。绘嵩了在简单策略意义下特征函数的完整求解算法以及在一个三维连通嬲 格图上的计算示例。同时探讨了在特定条件下三维连通网格图上对策的些基本性 质，最后求解具有状态支付翔量的有陵图上动态合作重复对策，并给出个三维连 通网格图上的计算示例。 关键词：重复对策；连通图；状态支付向量；绝对均衡；p m s 值 a b s t r a c t a b s t r a c t t h eg a m e sr e s e a r c h e di n t h i sp a p e ra r ea l lw i t hc o m p l e t ei n f o r m a t i o n t h ew o r ki s f o c u s e do no p t i m a ls o l u t i o no ft h er e p e a t e dg a m ei ne x t e n s i v ef o r mo nt h es i t u a t i o n so f c o o p e r a t i o n ，p a r t i a lc o o p e r a t i o na n dc o m p l e t ec o o p e r a t i o n r e s e a r c h i n go b j e c t si n c l u d e t h er e p e a t e dg a m eo ng a m et r e ea n dg a m ew i t hs t a t ep a y o f f so nc o n n e c t e dg r a p h 0 nt h ef i r s tc h a p t e r , w em a i n l yd i s c u s st h er e p e a t e dg a m eo nt h eg a m et r e e m e a n w h i l e ，w eg e tt h ef a c tt h a tp a r t i a lc o o p e r a t i v ep r o g r e s so ft h eg a m eo f t e nc a u s e st h e c h a n g i n go ft h ec o a l i t i o n ss t r u c t u r e ，w h i c hi sf o rs o m er e a s o n s ，p l a y e r sm a yl e a v et h e c o a l i t i o ni nt h el a s ts t a g ea n dg e ti n t ot h en e wc o a l i t i o nt h a ti sm o r ef a v o r a b l e t h e c o m p l e t ea l g o r i t h m f o rt h ep m sv a l u eo ft h er e p e a t e dg a m ei ne x t e n s i v ef o r mw i t h c h a n g i n gc o a l i t i o n s t r u c t u r ei s g i v e ni n t h i sc h a p t e r f u r t h e r m o r e ，w er e s e a r c h t h e o p t i m a lc o o p e r a t i v ef o r mo nt h eb a s eo ft h ep m sv a l u e ，w i t ht h ee x p e c t a t i o nt oa c h i e v e t h er u l ef o l l o w e db yt h ef o r m a t i o no fo p t i m a lc o a l i t i o n a ls t r u c t u r e o nt h es e c o n dc h a p t e r , b yi n t r o d u c i n gt h es t a t ep a y o f fv a l u eo ne a c hp o i n to ft h e c o n n e c t e dg r a p h ，w er e s e a r c ht h ed y n a m i cr e p e a t e dg a m eo nt h ef i n i t eg r a p h b a s e do n c b e r g e sc o n c e p to ft h eg a m es t r a t e g y o ng r a p h - t h en o n c o o p e r a t i v es i t u a t i o ni s c o n s i d e r e d a l s o ，t h ee x i s t e n c et h e o r e mo fa b s o l u t ee q u i l i b r i u ma b o u tg a m e so n c o n n e c t e dg r a p hw i t hs t a t ep a y o f fv e c t o ri sp r o v e d a tl a s t ，t h ec o m p l e t ea l g o r i t h ma n d a ni l l u s t r a t i o no nt h et h r e e d i m e n s i o nm e s h l i k ec o n n e c t e dg r a p ha r eg i v e n o nt h eb a s eo ft h es e c o n dc h a p t e r , t h ec o o p e r a t i v e - d y n a m i c r e p e a t e dg a m ew i t h s t a t ep a y o f fv e c t o ro nt h ef i n i t eg r a p hi ss t u d i e do nt h et h i r dc h a p t e r t h ec o m p l e t e a l g o r i t h mo ft h es o l u t i o nf o rt h ec h a r a c t e rf u n c t i o no nt h es e n s eo ft h es i m p l es t r a t e g y , a n da ni l l u s t r a t i o no nt h et h r e e - d i m e n s i o nm e s h l i k ec o n n e c t e dg r a p h a r eg i v e n m e a n w h i l e ，s o m eb a s i cn a t u r eo ft h et h r e e d i m e n s i o nm e s h l i k ec o n n e c t e dg r a p ho n s p e c i f i c c o n d i t i o nw a se x p l o r e d a tl a s t ，w eg e t t h es o l u t i o no ft h e c o o p e r a t i v e - d y n a m i c r e p e a t e dg a m ew i t h s t a t ep a y o f fv e c t o ro nt h ef i n i t eg r a p h ，a n d g i v ea ni l l u s t r a t i o no nt h r e e d i m e n s i o nm e s h l i k ec o n n e c t e dg r a p h k e yw o r d s ：r e p e a t e dg a m e ；c o n n e c t e dg r a p h ；s t a t ep a y o f fv e c t o r ；a b s o l u t e e q u i l i b r i u m ；p m sv a l u e 青岛大学硕士学位论文 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品。知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密瓯 ( 请在以上方框内打“”) 论文作者签名： 导师签名： ( 本声明的 狄j i f 夕平 日期：埘年乡月，舌日 日期：厶岖年月，日 所有，未经许可，任何单位及个人不得擅自使用) 5 6 雩| 言 霹l 吉 0l目 对策论是一门以严格的数学模型来研究和规范描述人与人之间利益相互制约下 策略选择时的理性行为及相应结局，并在统一框架下加以严整的数学分析的理论。 它是在2 0 世纪4 0 年代形成并发展起来的一门年轻而极富生命力的科学。 按对策中局中人的行为方式是否有先后之分可将对策划分为动态对策和静态对 策；而根据髑中人行为的出发点是维护集体利益或个人利益又可将对策划分为合作 对策和非合作对策。囱对策论学科诞生以来，非合作对策( 包括静态和动态) 得到 了广泛而深入的研究。非合作对策理论的核心问题是策略选择，研究人们如何在利 益榷互影响的情况下徽塞最有利于自己的选择。合作对策理论的核心问题是利益分 配，研究人们达成合作之后如何分配利益。目前，非合作对策理论体系已趋于完善 并在社会经济生活中褥到极为成功的应用。 近年来，对合作对策的研究经历了由完全合作到部分合作的演变。在静态的或 者动态的完全合作对策熬研究中人们已经习攒了所谓的合作假设，即对策规则中约 定局中人为了各自所属联盟的最大和利益而采取策略；局中人在对策进程中自始至 终参与所属的联盟，并且觏定某个局中入的联盟一旦形成则在整个对策进程中不会 发生变化。 ： 联盟割分型的对策鲍思想源鲁a r n o l dt 和w o o d e r sm 的工作醛。p e t r o s y a nl 与m a m k i n as 在乜3 中研究了具有变化联盟结构的动态对策，在对策树的一些固定结 点处弓| 入了联盟结构隧机变化分割的机铡，并弓| 入了此类对策新的最优解雕s 向量。 i o p o ) i ( k h hk 8 考察了具有变化联盟剖分的3 入重复静态对策嗨3 ，运用因子对策的方 法给出了在重复对策的不同阶段具有不同的联盟剖分情形的重复对策的求解算法。 r p a y 3 p 月b 。在强3 中，通过运用合作r l 入囚徒困境对策核心中的分配建立半合作对策， 并针对具有贴现支付的无限次重复对策证明了强纳什均衡的存在性。 具有变化联盟结构的重复扩展型对策中不完全合作的重复对策进程通常伴随着 联盟结构的变化，某些局中人因为某种原因可能离开上一阶段的联盟两加入更有利 于自己利益的新联盟。 图上对策最初的类型是有限树上的对策( e 。z e m e l o ，1 9 6 1 ) ，图上对策一般形 式的定义则是由c b e r g e 嘲给出的。文渊讨论了目标结构由终端状态集合上的拟序 关系给定的图上对策，作者推广了c 。b e r g e 的策略概念，即在图上每一个给定的状 青岛大学硕士学位论文 态处，下一个状态的选择取决于之前所经历的状态，而不仅仅是之前所经过的最后 一个状态。文阻一3 的结果均是在平面图上针对具有终端支付的对策给出。本文拟在有 限连通图的每个状态结点处引入状态支付向量，运用c b e r g e 的关于图上对策中策 略的概念研究考察动态重复对策中的绝对均衡。 ， 图上的对策与对策树之间具有紧密的联系，主要用于描述动态对策进程的对策 树是结构简单的图，因此图上对策的研究结果可以直接推广到动态对策的范畴。在 预先给定图上对策局中人的策略集合的前提下，图上的状态结点可能表现为有序的。 在本文中我们约定，图上的任一状态结点均可作为初始状态，而一个可以用对策树 表述的有限动态对策进程通常具有唯一的初始状态。 参与者在对策中获得收益( 或者支付费用) 的方式对于动态对策最优准则的确 定尤其重要。根据支付方式的不同可以将图上的动态对策区分为具有状态支付向量 的、具有终端支付向量的( 包括仅给定终端状态集合上的拟序关系的) 以及具有局 支付向量的三种类别。状态支付向量是指图上的每个状态结点处预先给定的支付向 量，局中人的最终支付将在某个局的终端状态处通过累加( 或者加权) 这个局所经 历的所有状态处的支付向量来实现。具有状态支付向量的情形更适合于图上的动态 对策以及网络系统控制理论的研究，它不仅有利于描述网络系统中收益( 或费用) 的发生的瞬时性，并且将为局中人在网络中选择“最优”初始状态以及“最优”路 径提供决策上的便利。在特定的对策类中如果终端支付可以完全取代状态支付的作 用，那么结果的阐述将变得简洁。 本文给出了图上对策中的符号体系、局中人的策略和状态支付的定义；同时证 明了在具有状态支付向量的连通图上重复对策中绝对均衡的存在性定理；再归纳出 绝对均衡的完整算法；最后给出了一个具有状态支付向量的三维连通网格图上对策 中绝对均衡的计算示例。 在平面网格状有限图上研究考察了完全合作动态对策。具体地，局中人在对策 进程中采取完全合作行为，而部分合作的主要特征是每个局中人的行为是合作行动 与单独行动的结合。同时给出了平面有向图上完全合作对策的值以及最优路径的算 法。 2 第一章具有变化联盟结构的重复扩展型对策的求解 第一章具有变化联盟结构的重复扩展型对策的求解 本章研究具有变化联盟结构的重复扩展型对策，不完全合作的重复对策进程通 常伴随着联盟结构的变化，某些局中人因为某种原因可能离开上一阶段的联盟而加 入更有利于自己利益的新联盟。本章给出了具有变化联盟结构的重复扩展型对策的 p m s 值的完整算法，并以此作为最优准则探索对策进程中的最优合作方式，并希望 在特定最优准则的基础上探索最优联盟结构形成所遵循的法则。 联盟剖分型的对策的思想源自a r n o l dt 和w o o d e r sm 的工作口3 。p e t r o s y a nl 与m a m k i n as 在乜3 中研究了具有变化联盟结构的动态对策，在对策树的一些固定 结点处引入了联盟结构随机变化分割的机制，并引入了此类对策新的最优解p m s 向 量。口, o p o k k h hk b 考察了具有变化联盟剖分的3 人重复静态对策瞄1 ，运用因子对策 的方法给出了在重复对策的不同阶段具有不同的联盟剖分情形的重复对策的求解 算法。r p a y 3 p 几b 在哺1 中，通过运用合作，1 人囚徒困境对策核心中的分配建立半合作 对策，并针对具有贴现支付的无限次重复对策证明了强纳什均衡的存在性。 本章考察局中人个数为以伽3 ) 的具有变化联盟结构的重复扩展型对策，尝试 研究联盟剖分的变化的原因，并希望在特定最优准则的基础上探索最优联盟结构形 成所应遵循的内在法则。 1 1 符号和定义 考察非合作对策g ( ， u 】脚，饵b ) ，这里= 仉2 ，l 】是局中人的集合；以 是局中人f 的策略集合：z 是局中人f 定义在全体局势集合上的支付函数。 假设可以对局中人集合= 仉2 ，z 做任意的剖分得到虬= 似，4 】- ，这里 ，s ，l ，4n 彳2 乃，f ，譬4 f = ，视4 ，七l1 ，厂为新的局中人，那末相应的 青鹞大学硕士学位论文 策略集合和支付函数会发生变化，局中人4 的策略集合为玩= 兀q ，支付函数为 毫 一h k ：y 皿。 赶 定义1 1 1 称r 一帆， 玩域， 万t k 或) 为对策g 生成的因子对策。 定义1 1 2 重复对策是指同样结构的对策重复多次，其中的每次对策称为“阶段对 策 。 定义1 1 3 设一氆2 ，。，n 是对策f 的所有局孛入的集合，针对任意的联盟割分 心2 墨，- ，母) ，这里厂s 月，s , n s j g ，f 书如；u ：，s k = n ，如果用最( ) 表示第七个 联盟，同时针对每个联盟瓯( ) ，k = 万在联盟& ( ) 内部使用s h a p l e y 值来分配联盟所 获得的收益，然后按照局中人由1 到咒的顺序将上述的分配结果重新排列成一个彪 维向量，即p m s ( ) = ( 嬲，( ) ，- ，p m s ( ，称之为对策f 的p m s 恕量。 假设我们研究的重复对策是一个m 步的有限扩展型重复对策，规定在每一步对 策进程中局中入按照由l 到n 的顺序进行决策，且每个局中入只进行一次决策。 王。2 具有变化联盟结构的重复扩展型对策的求解算法 给定对策r = ，置，置，爆，致 ，其中n 一0 , 2 ，刀 是局中人的集合， 置为第f 个局中人的策略集合，e 0 ) 为第f 个局中人的支付函数，x x = 二。x i 。 记对策f 的因子对策司为 m 这里七帮 。) 意味着盈螽 。) 所对应的下标。对策的迸程中会形成局势 霉1 量1 一疆t 爵悸。) x a t l ，按照联盟割分将随着对策上一步变化了的局势而变化的法则， 在第二步上联盟剖分变为齑辑1 ) ，那么 z 一 zz f 类似地可以建立重复对策孕的全部掰步，在第麟一l 步上有匿子对策 # - - i m l m l f - = ，a 乞= l 2 ) ， 3 ，4 ) ) ， l = 2 ，3 ) ， u ， 4 ，n o = 1 ，2 ，3 ，4 ) ) 情形1 第2 步因子对策的联盟剖分为齑 1 ) = l = u ， 2 ，3 ，4 ) ) 的情形 首先考虑第2 步因子对策于2 ( ) ，此时联盟剖分为螽 1 ) = 1 = “1 ， 2 ，3 ，4 1 ， 因子对策p 2 ( c o o ) 的最优路径为y 2 = p ，p ，c ，d ) ) 。 可求得对应的特征函数为 妒( 1 ) = 2 ，y ( 2 ) = 3 ，y ) = 1 ，v ( 4 ) = 1 ，v ( 2 ，3 ) 一5 ，v ( 2 ，4 ) = 5 ，v 0 ，4 ) = 2 ，v ( 2 ，3 ，4 ) 一l o 按前面所述的算法可求得因子对策p 2 ( c o o ) 的嬲向量为： p m s 2 ( ) 一( p m s ? ( o o ) ，p m s 2 ( w o ) ，p m s 2 a ( t o o ) ，p m s 2 ( t o o ) ) = ( 2 ，5 ，5 2 ，5 2 ) 其次考虑第1 步，因子对策f 1 ( ) 转化为对策- l ，此时联盟剖分为 齑 8 ) = = 氆2 ，3 餐 ，把按1 一( 1 ) 式定义的支付函数虿：附加到对策树k ( ) 的 各个终端节点处，得到图1 2 n ) ( 3 ，最 可求得对应的特征涵数为 图1 2 9 ，1 1 2 ) 青岛大学硕士学位论文 v ( 1 ) = 4 ，v ( 2 ) = 8 ，v ( 3 ) = 7 2 ，v ( 4 ) ；7 2 ，v ( 1 , 2 ) - - 1 3 ，v ( 1 , 3 ) = 2 1 2 ，v ( 1 ，4 ) = 1 9 2 ， v ( 2 ，3 ) = 2 5 2 ，v ( 2 ，4 ) = 2 5 2 ，v ( 3 ，4 ) = 7 ，v ( 1 , 2 ，3 ) = 3 9 2 ，v ( 1 ，2 ，4 ) = 3 7 2 ， v ( 1 , 3 ，4 ) = 1 6 ，v ( 2 ，3 ，4 ) = 1 6 ，v ( 1 ，2 ，3 ，4 ) = 2 5 进一步求得对策f 1 的p m s 向量为 p m s l ( ) = ( 用牺：( ) ，p m s ：( t o o ) ，删( ) ，e m s ：( w o ) ) = ( 7 9 1 2 ，1 0 5 1 2 ，6 1 1 2 ，5 5 1 2 ) 我们得到重复对策g ( 2 ，r ( ) ) 中局中人的最终支付为( 7 9 1 2 ，1 0 5 1 2 ，6 1 1 2 ，5 5 1 2 ) 。 此时因子对策亍1 的最优路径为y 1 = ( ( d ，d ，d ，d ) ) 。那么得到重复对策g ( 2 ，r ( ) ) 的 最优路径为( y 1 ，y2 ) 。 情形2 第2 步因子对策的联盟剖分为两 1 ) ；n 2 = 1 ，2 ) ， 3 ，4 ) ) 的情形 首先考虑第2 步因子对策p 2 ( ) ，此时联盟剖分为丙 1 ) = n 2 = 1 ，2 ， 3 ，4 】， 因子对策f 2 ( ) 的最优路径为y 2 = ( ( d ，c ) ，( c ，c ) ) 。 可求得对应的特征函数为 v ( 1 ) = 2 ，v ( 2 ) = 3 ，v ( 3 ) = 1 ，v ( 4 ) = 1 ，l ，( 】，2 ) = 6 ，v ( 3 ，4 ) = 6 按前面所述的算法可求得因子对策f 2 ( ) 的嬲向量为： p m s 2 ( ) = ( p m s 2 ( t o o ) ，p m s 2 ( w o ) ，p m s ；( 0 4 ) ，e m s 2 ( o a o ) ) = ( 5 2 ，7 2 ，3 ，3 ) 其次考虑第1 步，因子对策p ，( ) 转化为对策亍1 ，此时联盟剖分为 齑 。) ：0 ； 仉2 ，3 ，4 ) ，把按1 一( 1 ) 式定义的支付函数玩附加到对策树k ( ) 的 各个终端节点处，得到图l - 3 1 0 第一章具有变化联盟结构的重复扩展型对策的求解 c o o c 纰 ( 7 芝， 可求得对应的特征函数为 图1 3 v ( 1 ) = 9 2 ，v ( 2 ) = 1 3 2 ，v ( 3 ) = 4 ，1 ，( 4 ) = 4 ，v ( 1 ，2 ) = 1 2 ，v o , 3 ) = 2 3 2 ，v ( a ，4 ) = 2 1 2 ， v ( 2 ，3 ) = 2 3 2 ，v ( 2 ，4 ) = 2 3 2 ，v ( 3 ，4 ) = 8 ，y ( 1 ，2 ，3 ) = 1 9 ，v ( 1 ，2 ，4 ) = 1 8 ，v ( 1 , 3 ，4 ) = 3 5 2 ， v ( 2 ，3 ，4 ) = 3 1 2 ，v ( 1 ，2 ，3 ，4 ) = 2 5 进一步求得对策f 1 的膦向量为 p m s l ( ) = ( 删( ) ，e m s ：( w o ) ，p m s ；( w o ) ，p m s l ( w o ) ) = ( 8 5 1 2 ，8 7 1 2 ，6 7 1 2 ，6 1 1 2 ) 我们得到重复对策g ( 2 ，r ( ) ) 中局中人的最终支付为( 8 5 1 2 ，8 7 1 2 ，6 7 1 2 ，6 1 1 2 ) 。 此时因子对策f 1 的最优路径为y 1 ：( p ，d ，d ，d ) ) 。那么得到重复对策g ( 2 ，r ( ) ) 的 最优路径为( y 17 y 2 ) 。 情形3 第2 步因子对策的联盟剖分为丙 1 ) = 3 ；“2 ，3 ) ， 1 ) ， 4 ) 的情形 首先考虑第2 步因子对策f 2 ( ) ，此时联盟剖分为匆 1 ) = 3 = ( 2 ，3 ) ， 1 ) ， 4 ) ， 因子对策p 2 ( ) 的最优路径为y 2 = p ，( c ，c ) ，c ) 。 可求得对应的特征函数为 v ( 1 ) = 3 ，v ( 2 ) = 3 ，v ( 3 ) = 1 ，v ( 4 ) = 2 ，v ( 2 ，3 ) = 7 青岛大学硕士学位论文 按前面所述的算法可求得因子对策f 2 ( ) 的p k i s 向量为： p m s 2 ( ) = ( p m s ? ( w 。) ，p m s ；( e o o ) ，p m s ；( w 。) ，p m s ；( w o ) ) = ( 3 ，9 2 ，5 2 ，2 ) 其次考虑第1 步，因子对策f 1 ( ) 转化为对策f 1 ，此时联盟剖分为 齑 。) ；0 。“1 ，2 ，3 ，4 ) ，把按卜( 1 ) 式定义的支付函数玩附加到对策树k ( ) 的 各个终端节点处，得到图1 4 c 及l u ，翻| 。 d 嘭d锡 o 略 o rr ccc ( 8 ，1 5 2 ， i1 l 可求得对应的特征函数为 图1 4 ，9 2 ，5 ) v ( 1 ) = 5 ，v ( 2 ) = 1 5 2 ，v ( 3 ) = 7 2 ，v ( 4 ) = 3 ，v o , 2 ) = 2 7 2 ，v ( 1 ，3 ) = 2 3 2 ，v o ，4 ) = 1 0 ， v ( 2 ，3 ) = 1 2 ，v ( 2 ，4 ) = 2 3 2 ，v ( 3 ，4 ) = 1 3 2 ，v ( 1 ，2 ，3 ) = 2 0 ，l ，( l2 ，4 ) = 3 7 2 ， ，l ，( l 3 ，4 ) = 3 3 2 ，v ( 2 ，3 ，4 ) = 1 5 ，v o , 2 ，3 ，4 ) = 2 5 进一步求得对策亍1 的嬲向量为 p m s l ( w o ) - ( p m s ：( w o ) ，p 煅：( ) ，p m s ；( m o ) ，p m s ：( w o ) ) 一( 9 1 1 2 ，9 9 1 2 ，6 6 1 2 ，4 9 1 2 ) 我们得到重复对策g ( 2 ，r ( ) ) 中局中人的最终支付为( 9 1 1 2 ，9 9 1 2 ，6 6 1 2 ，4 9 1 2 ) 。 此时因子对策亍1 的最优路径为y 1 = ( p ，d ，d ，d ) ) 。那冬得到重复对策g ( 2 ，r ( ) ) 的 最优路径为( y 1 ，y 2 ) 。 情形4 第2 步因子对策的联盟剖分为 1 ) = o = n 2 ，3 ，4 ) ) 的情形 1 2 第一章具有变化联盟结构的重复扩展型对策的求解 首先考虑第2 步因子对策f 2 ( ) ，此时联盟剖分为齑 1 ) = n o = 扎2 ，3 ，4 ) ) ， 因子对策f 2 ( 的最优路径为j ) ，2 = ( ( d ，d ，d ，d ) ) 。 可求得对应的特征函数为 v ( 1 ) = 2 ，v ( 2 ) = 3 ，v ( 3 ) = 1 ，v ( 4 ) = 1 ，v ( 1 ，2 ) = 6 ，v ( 1 ，3 ) = 6 ，v ( l 4 ) = 5 ，v ( 2 ，3 ) = 5 ， v ( 2 ，4 ) = 5 ，v ( 3 ，4 ) = 2 ，v ( 1 , 2 ，3 ) = 1 0 ，v ( 1 ，2 ，4 ) = 9 ，v ( 1 ，3 ，4 ) = 9 ，v ( 2 ，3 ，4 ) = 6 ， v ( 1 ，2 ，3 ，4 ) = 1 3 按前面所述的算法可求得因子对策f 2 ( ) 的用络向量为： p m s 2 ( ) = ( 脚船? ( ) ，p m s ；( w o ) ，p m s ；( w 。) ，p m s ；( o ) 。) ) = ( 5 5 1 2 ，4 5 1 2 ，3 1 1 2 ，2 5 1 2 ) 其次考虑第1 步，因子对策f 1 ( c o o ) 转化为对策亍1 ，此时联盟剖分为 丙 。) ；0 ： 1 ，2 ，3 ，q ) ，把按卜( 1 ) 式定义的支付函数万：附加到对策树k ( ) 的 各个终端节点处，得到图1 5 o qo 鸭 o 鸭o(07 c ( 1 1 5 1 ,! ，8 1 1 2 ，5 5 1 2 ， ccc i l l i l i n l ( 9 1 1 2 ，8 1 , 1 2 ，7 9 1 2 ，4 9 1 2 ) ( 1 0 3 1 2 ，5 7 1 2 ，5 5 1 2 ，7 3 1 2 ) 图1 5 可求得对应的特征函数为 1 1 2 ) v ( 1 ) = 7 9 1 2 ，v ( 2 ) = 8 1 1 2 ，v ( 3 ) = 4 3 1 2 ，v ( 4 ) = 3 7 1 2 ，v ( 1 ，2 ) = 1 7 2 1 2 ， y ( 1 ，3 ) = 1 5 8 1 2 ，v ( 1 ，4 ) = 1 4 0 1 2 ，v ( 2 ，3 ) ；1 3 6 1 2 ，v ( 2 ，4 ) = 1 3 0 1 2 ，v ( 3 ，4 ) = 8 0 1 2 ， 1 3 劲 青岛大学硕士学位论文 ，( l 2 ，3 ) = 2 5 1 1 2 ，v ( 1 , 2 ，4 ) = 2 3 3 1 2 ，y ( l 3 ，4 ) = 2 1 9 1 2 ，v ( 2 ，3 ，4 ) = 1 7 3 1 2 ， l ，( 1 ，2 ，3 ，4 ) ；2 6 进一步求得对策f 1 的嬲向量为 p m s l ( ) = ( p m s ( w o ) ，p m s ：( w o ) ，p m s j ( w o ) ，p m s ：( w o ) ) = ( 1 1 0 1 2 ，9 0 1 2 ，6 2 1 2 ，5 0 1 2 ) 我们得到重复对策a ( 2 ，r ( w o ) ) 中局中人的最终支付为( 1 1 0 1 2 ，9 0 1 2 ，6 2 1 2 ，5 0 1 2 ) 。 此时因子对策r 1 的最优路径为y 1 ；( ( d ，d ，d ，d ) ) 。那么得到重复对策g ( 2 ，r ( ) ) 的 最优路径为( y 1 ，y2 ) 。 1 4 注释 示例中重复对策的a ( 2 ，r ( ) ) 的第1 步联盟剖分都为大联盟0 ，因此以下仅就 第2 步不同的联盟剖分带给局中人的收益进行比对。 对比当第2 步的联盟剖分分别为0 = 扎2 ，3 ，4 ) ) 和1 = m ， 2 ，3 ，4 ) ) 的情形， 对于局中人1 而言，在第2 步离开大联盟0 后的最终收益为7 9 1 2 ；显然比联盟剖 分为0 时的1 1 0 1 2 明显地要少，因此对于局中人1 来说第2 步的联盟剖分0 优于 1 ：同时对于局中人2 和4 而言，由于局中人1 的离开，他们的收益均有一定程度 的增加，而局中人3 的收益变化不大，因此对局中人2 、3 、4 来说联盟剖分1 优于 n o o 对比当第2 步的联盟剖分分别为o ； 仉2 ，3 ，4 】) 与2 = 扎2 】， 3 ，4 ) 】- 的情形， 对于局中人3 和4 而言，离开大联盟后他们的收益总和为1 2 8 1 2 ，显然比联盟剖分 为o 时的收益总和1 1 2 1 2 要多，因此对于局中人3 和4 来说联盟剖分2 优于“； 但是，对于局中人1 而言，由于局中人3 和4 的离开他的收益明显地减少，对于局 中人2 而言由于局中人3 和4 的离开他的收益有一定程度的减少，因此对于局中人 1 和2 来说联盟剖分0 优于2 。 1 4 第一章翼育变纯联嬲结构豹重复扩震型对策妻冬求解 对比当第2 步的联盟剖分分别为2 = l ，蛰， 3 ，4 与m = m ， 2 ，3 ，4 1 1 的情形， 对于局中人3 和4 丽言，联盟剖分为从时他们的收益总和为1 2 8 1 2 ，而联盟剖分为 m 时收益总和为n 6 王2 ，因此对于局中人3 和4 来说联盟剖分心优于m 。对于局 中人1 而言，联盟剖分为，时收益为8 5 1 2 ，联盟剖分为1 时收益为7 9 1 2 ，因此 对于局中人l 来说联盟剖分从优于m ；但是对于局中入2 丽言，联盟割分为m 时 收益比联盟剖分为1 时收益明显要少，因此对于局中人2 来说联盟剖分1 优于，。 上述完全合作与部分合作以及部分合作之闻的比对结果显示，局中人可能根据 情况的变化去寻求重复对策进程中的最优合作方式，在重复对策进程中以后的阶段 主动地选择“最优”联盟剖分以实现自己利益最大化。 1 5 青岛大学硕士学位论文 第二章具有完全信息及状态支付的连通图上的重复对策 本章通过在连通图的每个状态结点处引入状态支付向量，在图上研究考察动态 对策。运用c b e r g e 关于图上对策中策略的概念，证明了在具有状态支付向量的 连通图上重复对策中绝对均衡的存在性定理，给出其完整的算法以及在一个三维连 通网格图上的计算示例。 主要用于描述动态对策进程的对策树是一种结构简单的图，因此图上对策的研 究结果一般都可以直接推广到动态对策的范畴。图上对策最初的类型是有限树上的 对策( e z e m e l o ，1 9 6 1 ) ，图上对策一般形式的定义则是由c b e r g e 陋1 给出的。文 口1 讨论了目标结构由终端状态集合上的拟序关系给定的图上对策，作者推广了c b e r g e 的策略概念，即在图上每一个给定的状态处，下一个状态的选择取决于之前 所经历的状态，而不仅仅是之前所经过的最后一个状态。文阳9 3 的结果均是在平面 图上针对具有终端支付的对策给出。本文拟在有限连通图的每个状态结点处引入状 态支付向量，运用c b e r g e 的关于图上对策中策略的概念研究考察动态对策中的 ： 绝对均衡。 2 1 符号和定义 记具有顶点集合4 的连通图为 ，这里) ，a 2 ( 即) ，为图的弧集) ，状态 ( 顶点) 集合为彳= 和。，a 1 ) 。断面( 截面) ) ， 是图上状态口之后的所有状态 的集合，7 ， 是紧跟状态口的直接后续状态集合，4 是没有后续状态的状态集 合，上述三个集合均与下文将定义的策略相关。称 为咒一状态图，如果给定 集合4 4 的剖分为 4 ，4 1 ) 。引用对策术语，局中人的集合为n = 仉2 ，以 ，4 为局中人f 的状态集合，局中人的决策结点集合记为j = 似，4 ，4 ，而4 为 终端状态集合。图 上的轨迹( 或路径) 是状态口o ，a ，a ，的序列( 有限的或 1 6 一。第二耄其鸯完剿蠹息及状态支付的连通鼹上的重复蚶策 = = = = z = = = = ：= ：2 无限的) ，在序列中每一个七= 1 ，t 满足吼y 。称一个轨迹为局，如果 它或者无限的，或者包含了终端状态q ，称余下所有的轨迹为开局。满足条件 薯冬y 的经意映射鼍：4 一么称为焉中入珀每簿单策硌，局幸人珀皇所有篱单策略集合 记为戈。蠢一个状态8 么霹个篱单策略下的局势s 。是，。，霞) 乏x 将定义 一个局稼，是，气 = 8 ，s ( 露) ，5 2 ( 盘) ，。如果在图 中没有无限的路径，那么 与任意状态口彳都有一个映射c ：墨x s 。- - , a ，与之相关联，这个映射把每一个 简单策略下的局势( 蕞，& ) 相应地映为局 的终端状态。 定义2 。1 1 在图上每个状态据处赋予一个群维实