（应用数学专业论文）具有变化联盟部分的图上动态合作对策研究.pdf

摘要 论文考察研究具有变化联盟剖分的图上对策。本文针对对策树上具有固定以及 变化联盟剖分的扩展型对策、图上具有变化联盟剖分的对策展开研究，本文所考察 的对策类型均为完全信息的。 第一章考察具有完全信息和固定联盟剖分的动态对策，局中人在对策进程中联 合结成联盟，这些联盟构成全体局中人集合的剖分，假定联盟与联盟之间是非合作 的关系，而在给定联盟的内部局中人保持完全合作。本章给出了此类对策在上述行 为方式之下联盟一局中人的均衡局势求法并在此基础上建立了对策最优解的完整算 法。 第二章主要研究对策树上具有变化联盟剖分的扩展型对策。在非合作对策中局 中人选择使自己获得最大支付的策略，在完全合作或部分合作对策中局中人首先考 虑使他们所在联盟的所得收益最大，之后考虑在联盟内部的局中人之间收益分配的 问题。我们考察具有完全信息的扩展型对策，并且在对策树的一些固定结点处可能 随机改变联盟剖分，给出了最优子树( 或分枝) 以及最优解的算法，同时针对这样 的对策得到了一种新解( 类似于p m s 向量) 。 第三章考察具有变化联盟剖分的图上对策。具体地，在图上某些固定状态处可 能随机改变联盟剖分，需要特别注意到对策进程中联盟剖分的变化动态，即可能出 现对策进程到达某些状态处的联盟剖分不一致的情形，本章给出了此类对策最优解 的算法和示例。 关键词：联盟剖分；p m s 向量；图上对策；简单策略； a b s t r a c t i nt h i sp a p e r , w em a i n l yr e s e a r c hd y n a m i cg a m e sw i t hc h a n g i n gc o a l i t i o n a ls t r u c t u r e s o nf i n i t ec o n n e c t e dg r a p h ，i n c l u d i n gd y n a m i cg a m e sw i t hf i x e dc o a l i t i o n a ls r u c t u r c so n g a m et r e e s ，d y n a m i cg a m e sw i t hc h a n g i n gc o a l i t i o n a ls r u c t u r e so ng a m e t r e ea n df i n i t e c o n n e c t e dg r a p h g a m e sr e s e a r c h e di nt 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 i nt h ef i r s tc h a p t e r ，w er e s e a r c hd y n a m i cg a m e sw i t hc o m p l e t ei n f o r m a t i o na n d f i x e d c o a l i t i o n a ls t r u c 咖d u r i n gt h ep r o c e s so ft h eg a m e ，p l a y e r sf o r mc o a l i t i o n s ，w h i c hf o r mt h e p a n i t i o no ft h es e to fa l lt h ep l a y e r s w ea s s u m et h a tt h ep l a y e r s i nt h eg i v e nc o a l i t i o nk e e p c o m p l e t e dc o o p e r a t i o n ，a n dc o n s i d e rt h en o n - c o o p e r a t i v es i t u a t i o nb e t w e e nt h e c o a l i t i o n sa sw e l l 舔t h ep a y o f 黾，a l l o c a t i o nw i t h i nt h ec o a l i t i o n su n d e rt h i ss i t u a t i o n w ei n t r u d u c et h em e t h o do f c o n s t l l l c t i n ge q u i l i b r i u m ，o nt h eb a s i so fw h i c hw ee s t a b l i s ht h eo p t i m a lc o m p l e t e da l g o r i t h mo f g a m e s i nt h es e c o n dc h a p t e r , d y n a m i cg a m e sw i t hc h a n g i n g c o a l i t i o n a ls r u c t u r e so ng a m e 讹ea r er e s e a r c h e d i nn o n - c o o p e r a t i v eg a m e s ，t h ep l a y e r sc h o o s i n gt h e i rs t r a t e g m st r y t o g e tm a x i m a lp a y o f f s i nc o o p e r a t i v eg a m e st h ep l a y e r st r yt om a x i m i z et h e s u l no ft h e l r p a y o f f sf i r s t l y , a n dt h e nt h ea l l o c a t i o n o ft h i sm a x i m a lt o t a lp a y o f fb e t w e e nt h e ma r e c o n s i d e r e d w h e nt h ec o o p e r a t i o ni sn o tf u l l ，t h ep l a y e r sa l w a y sf o r mc o a l i t i o n sc h o o s i n g s t 赋g i e sw i t ht h ei n t e n t i o nt om a x i m i z e t h ep a y o f fo fc o a l t i o nt ow h i c ht h e yb e l o n g w e c o n s i e i e rg a m e sw i t hp e r f e c ti n f o r m a t i o n ，a n dr a n d o m l yc h a n g ec o a l i t i o n a lp a r t i t i o n sm s o m ef i x e dv e r t i c e so fg a m et r e e a na l g o r i t h mf o rc o n s t r u c t i n go p t i m a ls u b t r e e i s i n t r o d u c e d ，i nt h es a m et i m e ，t h en e wv e n i c e ( p m sv e r t i c e ) f o rs u c hg a m e s l sp r o p o s e d i nt h et h i r dc h a p t e r , g a m e sw i t hc h a n g i n g c o a l i t i o n a ls t r u c t u r e so nf i n i t ec o n n e c t e d g r a p ha r ec o n s i d e r e d b yc h a n g i n gc o a l i t i o n a ls t r u c t u r e sr a n d o m l y a ts o m ef i x e dp o m t s ， c o n s i d e r i n gd i f f e r e n tc a s e st h a tm o r et h a no n ec o a l i t i o n a ls t r u c t u r e sa to n ep o i n tw o u l d a p p e a r , w ee s t a b l i s ht h eo p t i m a la l g o r i t h m f o rs u c hg a m e s ，a n da ne x a m p l ea sw e l l k e y w o r d s ：c o a l i t i o n a ls t r u c t u r e s ；p m sv e r t i c e ；g a m e so ng r a p h ；s i m p l es t r a t e g i e 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：枸葱骰 日期：如卵年6 月，日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密回。 ( 请在以上方框内打“4 ) 论文作者签名：杨，蓬，欲 导师签名： ( 本声明的版权归青岛大学所有， 日期：y 9 年多月上日日期：y 7 年历月上日 日期：乙眇哆年彭月么日 未经许可，任何单位及个人不得擅自使用) 4 1 引言 引言 用动态对策理论的最新进展弥补非合作对策理论的局限性对于丰富管理科学理 论，深刻揭示经济管理系统的特性尤其是动态特性提供新的工具和手段，同时为各 类经济管理问题的研究提供博弈分析方法。 有限树上的对策( z e m e l oe ，1 9 6 1 ) 是图上对策最初的类型，图上对策一般形 式的定义是由b e r g ec n 1 给出的。主要用于描述动态对策进程的对策树是一种结构 简单的图，因此图上对策的研究结果一般都可以直接推广到动态对策的范畴。 图上的对策与对策树之间具有紧密的联系，但同时又具有对策树上完全不可能 出现的复杂情况。论文所研究的图本身可能并非有向图，但是在预先给定图上对策 局中人的策略集合的前提下，图上的状态结点就可能表现为有序的。此外，图上的 任一状态结点均可作为初始状态的假设所导致的图上对策的复杂性可能帮助揭示某 些重要的对策本质，这个复杂性又将直接导致研究手段和方法上的创新。 事实上，图上对策的研究结果在各类具有多个不同利益主体的网络中将显现其 重要的实际应用价值。互联网、移动通讯网络在当今世界已经几乎成为全部信息的 载体，但是由单一利益主体构建可以覆盖全球的通讯、运输及供应网络是不可完成 的工作，如何协调冲突各方的利益并且充分发挥上述网络的最大效率是管理科学必 须解决的问题。同时，将机制设计理论应用于图上的对策分析，建立和完善复杂网 络系统内部的激励体系设计并促进网络成员参与创新合作，将对管理决策科学化无 疑具有重要的现实意义。 处于社会经济网络、管理系统中的参与者或局中人，因系统条件的变化或偶然 性的因素可能导致合作方式发生变化，因此研究变化的联盟剖分的图上动态对策具 有重要的实际意义。 目前国际上数学对策论的文献把更多的注意力集中到研究局中人的行为方面， 已存在的最优准则一般只是针对联盟的行为在极端情况下的最优解，具体地说：个 体理性行为( 基本的最优准则是纳什均衡及其各种推广) 以及完全合作行为( 基本 的最优准则是核心、沙甫利向量、稳定集等等) 。2 0 0 4 年之前的一些工作表现出了 针对静态对策建立联盟剖分型对策最优行为准则( 如班卓夫指标) 的萌芽比州。 但是，上述工作中所提出的模型不能作为在图上的动态对策( 以及微分对策) 中描述最优行为的基础。欧文一沙甫利向量是上述所提及的工作中基本的最优行为准 则，从我们的观点看它的卓越性并不具备足够充分的理由，因为它的计算假定了构 成给定的联盟剖分的局中人一联盟之间完全合作的可能性。但是恰恰是这种情况与联 盟剖分型对策的情况相矛盾，因为剖分本身产生于完全合作的不可能! 在本论文中， 在非合作的前提假设下，我们将专注于寻找联盟剖分型对策的绝对均衡。仅从这个 青岛大学硕士学位论文 角度来看，论文研究成果的创新性将不容质疑。同时注意到，已有的工作只是涉及 到一次性对策( 静态的) ，在某种程度上也极大地限制了所获得的最优准则的适用范 围。 联盟剖分型对策思想最初的比较规范的表述源自a r n o l dt 和w o o d e r sm 的工 作呻1 。如果局中人在对策进程中联合结成联盟，这些联盟构成全体局中人集合的剖 分，此时联盟如同个体合理的局中人采取行动，而假定在给定联盟的内部局中人保 持完全合作，这样的对策称为联盟剖分型对策。p e t r o s y a nl 与m a m k i n as 在对策 树的一些固定结点处引入了联盟剖分随机变化分割的机制，并引入了此类对策新的 最优解p m s 向量阻1 。g r a u e rl v 则通过运用合作疗人囚徒困境对策核心中的分配构 造半合作对策，同时针对具有贴现支付的无限次重复对策证明了强纳什均衡的存在 性u 刚。我们还注意到了d o r o z h k i nk v 在2 0 0 2 - 2 0 0 5 年之间的一个有趣的但不太 引人注目的系列工作n 1 。1 劓，其本质上也是与联盟剖分型对策的思想一致。在他的工 作中通过建立因子对策和辅助对策对对策采取降阶的方法进行求解。在 1 1 中研究 了完全合作情形，即辅助对策内部的局中人之间完全合作而因子对策的局中人之间 也合作的情形。在 1 2 中研究了非合作情形， 1 3 中则是把这种方法应用于重复静 态对策，给出了在重复对策的不同阶段具有不同的联盟剖分情形的重复对策的求解 算法。因子对策方法可以视为对策的一种降阶方法，通过利用因子对策和辅助对策 可以加快求解的运算过程，但是需要注意的是，运用因子对策求解的结果既不是通 常意义上的非合作均衡( 非合作情形) 也可能不是完全合作的最优合作解( 合作情 形) ，因此这是一类新解，相近的研究工作还可以参见 1 4 。本文拟在连通图上的动 态对策研究工作中推广运用联盟剖分的思想。 2 第一章具有固定联盟剖分的扩展型对策 第一章具有固定联盟剖分的扩展型对策 联盟剖分型对策思想最初的比较规范的表述源自a r n o l dt 和w o o d e r sm 的工 作跚。局中人在对策进程中联合结成联盟，这些联盟构成全体局中人集合的剖分， 本文中把这些联盟称为联盟一局中人。此时联盟一局中人如同个体合理的局中人采取 行动，而假定在给定联盟的内部局中人保持完全合作，这样的对策称为联盟剖分型 对策。 联盟剖分型对策的计算假定构成给定的联盟剖分的联盟一局中人之间完全合作 的可能性。但是恰恰是这种情况与联盟剖分型对策的情况相矛盾，因为剖分本身产 生于完全合作的不可能! 联盟一局中人之间冲突与合作的可能性使得联盟之间以及联 盟内部的局中人之间的利益分配问题变得复杂，在对策进程中局中人的基本行为准 则是根据他们所在联盟的利益最大化而选择行动。针对联盟一局中人非合作的情形并 考虑到联盟内部的利益分配问题，本章给出构造解的算法。 1 1 符号、定义和模型 首先给出完全信息情形下具有固定联盟剖分的动态对策的基本模型。 定义1 1 - l 对策树是至少具有两个节点并且其中包含唯一初始节点( 根节点) 而的无圈有向连通图，记为k ( x o ) 。 本文所考察的对策树k ( x o ) 均是有限的。用z 表示对策树k ( x o ) 的某一个节点， k ( x ) 表示树k ( x o ) 上以x 为根的子树。z ( x ) 表示z 的直接后续节点集合。用f ( x ) 表 示在x 点处决策的局中人，x 的直接后续节点y ( y z ( x ) ) 称为局中人f ( 功在x 处 的选择。= l ，2 ，耐表示全体局中人集合。将对策树x 的节点集合剖分为 4 ，皿，见，见，这里d l ( f = 1 ，刀) 表示局中人i 的决策节点集合，见+ 。表示终端 节点集合。在每一个终端节点w 见+ 。处给定，l 维实值向量j 1 2 ( 叻= ( 扛( 叻，吃( 川) ， w e 见+ l 这里囊( w ) ，f = 1 ，oo 9 力表示局中人f 在终端节点处的支付。称对策树k ( x o ) 的最长路径上节点的个数为对策r ( x o ) 的长度，假设对策f ( x 0 ) 的长度为t + i 。用 r ( x o ) 表示在k ( x o ) - 1 2 的非合作对策。 青岛大学硕士学位论文 定义1 1 2 局中人f 的策略是指把每一个决策节点x 口映到唯一的直接后续 节点y z ( x ) 的映射( ) 。局中人，的策略集合用玑来表示。 根据上述定义，第f 个局中人的策略在其决策节点集合口中的任意节点x 处确 定他对于下一个节点的唯一选择。这样，每个局势”= ( 地，u 。) ，u t 唯一地确定 树形图k ( ) 上的从初始结点x o 开始并到达对策某个终端结点的路径，称之为局。 每个局唯一地确定了所抵达的终端结点w ，反之，终端结点w 唯一地确定了局。在 终端结点w 处，每个局中人f ，i = 1 ，力得到支付红( w ) 。 定义1 1 3 在对策r ( 而) 中局势“= ( ，”。) ，之下局中人珀勺支付函数的 值等于局势材所确定局的终端结点w 处的支付红( w ) 的值，即 k ( u l ，) = ( w ) ，i = 1 ，刀 卜( 1 ) 定义1 1 4 给定局中人集合的一个剖分a = 勰，瓯 ，这里所n ， s ，r 、墨= a ，而us ，= n 。称的每个元素最为一个联盟一局中人，他的策略集合 j f j ，一 为呔= 盟u 局势“唯一地确定图k ( 而) 上以w 为终端结点的某个局，这里 矿= ( 魄，) ，霜，j = l ，m 。在局势甜a 之下联盟一局中人的支付函数的值 等于局势甜所确定局的终端结点w 处联盟& 中局中人的支付总和，即 g 噜a ( “旷尥) = 红( w ) ，k = l ，m l 一( 2 ) ，趣 在给定联盟的内部局中人保持完全合作，称如上所得到的对策模型为具有固定 联盟剖分的动态对策。用r ( a ，x o ) 表示联盟一局中人之间在非合作情形下的具有固定 联盟剖分的动态对策。对策r ( ，x o ) 的进程依然是在原有的对策树k ( ) 之上并由 r ( x o ) 的局中人顺次进行决策，不同的是，这里局中人f 墨将首先根据最大化所在 联盟瓯的利益的原则而选择行动。 4 第一章墨查旦枣壁矍型坌塑茎垦型型簦 一一 一一_ 一一一 1 2 具有固定联盟剖分的非合作对策均衡及其最优解 1 2 1 联盟一局中人的均衡策略 将对策树k ( ) 上的所有节点剖分为x o ，五，耳：量= ) ，这里 五o ：o ，l ，r ) 表示由初始节点经过r 一，步恰可达到的节点集合，用薯表示五中的 节点。 首先考察k 中的每个节点，由于对策的长度等于丁+ 1 ，那么b + - ，局中 人的支付瑰( w ) ，w k ，i = 1 ，力在蜀上已经有定义。 第1 步：考察每个毛墨。如果五叠q + ，局中人f ( ) 选择行动。假设 f ( 而) s j ( s ，) ，规定局中人j ( 而) 代表联盟一局中人马以相同的概率选择每一个满 足如下条件的磊z ( x o ： 脚m a x 要驰) = 否纵动 令钳护a r g 删m a x 善獬也就是说孙护丢) = x e 2 ( x 。) i e s s 。似 相同的概率选择 意味着允许使用混合策略，以下同。 如果毛见+ l ，那么在五处局中人f 的支付忽( 西) ，i = 1 9 - 9 n 已经定义。 这样以五为初始节点的子树k ( _ ) 上局中人f ( _ ) 的最优策略集已经确定，记为 畈 ) ( 五) 。 假定在子树k ( 五) 之上局中人根据上述算法选择行动，在墨上按下式定义贝尔 曼函数1 ：墨专尺1 ，i = l ，刀 ，( 护1 司写磊槲如取哦1 ，f l红( 五) ， 如飘见+ 这里刁表示在节点而墨处局中人f 的期望支付。用，1 = ( 1 ，一) 表示向量 厂1 = ( 1 1 ，一) 的转置。 青岛大学硕士学位论文 第t 步：此时在五一l 之上，卜1 气r l t - ! ，t - 1 ) 已经定义，并且夏一2 z ( 薯一1 ) ( 薯一置一。) 已经选出。现在考察z 。如果叠见+ 。，局中人f ( t ) 选择行动。 假设f ( t ) 邑( s ) ，规定局中人f ( 薯) 代表联盟一局中人以相同的概率选择每个 满足如下条件的夏一。z ( t ) ： 脚m a x 矿l ( 力2 矿l ( 瓦) 令乏( 再) ( 薯) 2 鹕嬲荟卜1 ( x ) ，或者乏( 葺) ( 薯) = 少：荟一= x m e z a x ( x , ) t e s j 卜1 ( x ) 。 如果薯见，那么在x t 处局中人的支付红( _ ) ，i = 1 9 - - o9 n 已经定义。 对于i n ，若k ( ) n 皿a ，则以毛为初始节点的子树k ( x t ) 上局中人i 的最 优策略集已经确定，记为町( t ) 。 假定在子树k ( ) 之上局中人根据上述算法选择行动，在五上按下式定义贝尔 曼函数彳：置专r 1 ，i = 1 ，刀 以班去弘黾，蟾- 1 ) ，如飘哦，心 i - 囊( 一) ，如取见+ 。 这里彳表示在节点薯五处局中人i 的期望支付，并且同样记，= ( r , t ，巧) 。 逆推过程直到f = t 时终止。此时对任意的r = o ，1 t ，在墨之上厂f = ( r , t 巧) 已经定义，并且i 一。已经选出。 根据上述算法，我们有 定理1 2 1 对于i n ，记k ( ) 上局中人i 的最优策略集为u ( x o ) ，从而得到 具有固定联盟剖分的动态非合作对策c ( a ，x o ) 中联盟一局中人墨，k = 1 ，m 的均衡策 略集合= 墨叼( 而) ，而瓯在均衡局势下的支付为 磷( 唁，赡) = ，畦嚷，k = l ，棚 卜( 3 ) ，e & 第一章具有固定联盟剖分的扩展型对策 事实上，如果联盟一局中人& 偏离均衡策略而采取策略吐萑嚷，那么根据算法， 联盟一局中人的支付 磋( 唁，呔，哇) 磁( 唁，畦，赡) 卜( 4 ) 因而对联盟一局中人& 来说，2 墨研是对策r ( ，而) 中的纳什均衡策略集合。 1 2 2 联盟一局中人对均衡支付的分配 为了在联盟& ，k = 1 ，彤中确定局中人之间的分配联盟利益的方式，考察具有 特征函数的l 瓯1 人辅助合作对策g ( x o ，瓯) 。这里大联盟最的特征函数值为 飞( 瓯) = 矿( ) 。特征函数( r ) ，r 瓯看作辅助对策g ( 而，瓯) 中r 与瓯尺之 f e & 间进行的二人零和对策的值。没有进入辅助对策g ( x o ，瓯) 的局中人n s k 的策略固定 为上述算法中的某个最优纯策略。在对策g ( 而，& ) 中计算s h a p l e y 值观( 飞) ，f 瓯， 那么s h , ( v s ) = v s , ( s d 。用s h a p l e y 值作为合作i 1 人辅助对策g ( 而，& ) 局中人之 e 品 间的分配法则。按局中人在对策r ( x o ) 中原有的序号进行对位排列，这样所得到的刀 维向量记为对策r ( a ，) 的p m s 向量 p m s ( x o ) = ( p m s l ( x o ) ，p m s n ( x o ) ) 其中p m s , ( x o ) = s h 。( v s ) ) ，f & 。本文中将尸峪( 而) = ( 刷嗡( 而) ，懒( ) ) 作为 具有固定联盟剖分的动态对策非合作情形下的最优解。 1 3 计算示例 考察图1 1 所示对策树k ( ) 上进行的具有固定联盟剖分的动态对策r ( ，x o ) 。 这里局中人集合n = l ，2 ，3 ，4 ，5 ，局中人1 的个人决策节点集合q = ) ，局中人2 的个人决策节点集合0 2 = 瓴，屯，而) ，局中人3 的个人决策节点集合d 3 = ，x 7 ，而。) ， 局中人4 的个人决策节点集合功= x s ，五。，而，) ，局中人5 的个人决策节点集合 7 青岛大学硕士学位论文 d 5 = 五5 ，x 1 7 ，x 1 9 ，终端节点集合为d 6 = x 4 ，x 8 ，x l o ，毛2 ，x 1 4 ，x 1 6 ，x 1 3 ，x 2 0 ，恐2 ，x 2 4 ，x 2 6 ) 。 给定联盟剖分为= 1 ，3 ) ， 2 ， 4 ，5 ) ，并记s = 1 ，3 ，s 2 = 2 ) ，s 3 = 4 ，5 。 按决策进程将对策树k ( ) 上的所有节点剖分为： x o = 屯2 ，屯3 ，而4 ，而5 ，屯6 ，屯7 ，五= 6 ，x i 7 ，五3 ，x 1 9 ，x 2 0 ，x 2 1 ) ， 置= x l o ，x l l ，x 1 2 ，x i 3 ，x 1 4 ，x 1 5 ，x 3 = x 4 ，黾，x 7 ，x 8 ，x 9 ) ，五= 五，x 2 ，x 3 ) ，五= x o 首先考察x o = 而2 ，x 2 ，翰，x 2 5 ，x 2 ， 中的每个节点，由于对策的长度等于6 ， 那么x oc 见，局中人f 的支付吩( w ) ，w 五，f = 1 9o ，l 在x o 上已经有定义。 第一步：考察五= 而。，毛，x l 。，而，确，而。 中的每个节点。以j c l ，为例，由于 x l ，b ，局中人5 选择行动。因为5 s 3 ，局中人5 将力图使联盟一局中人马的利益 最大化，由于 m a x ( h , ( x 2 2 ) + 红( 而2 ) ，啊( 而3 ) + 魄( 吻3 ) ) = m a x ( 3 + 4 ，l + 2 ) = 7 因此在x 1 7 处局中人5 将选择而2 ，记，1 ( x 1 7 ) = ( 2 ，4 ，2 ，3 ，4 ) 。同理，局中人5 在x 1 9 处 选择砀，记，1 ( 而9 ) = ( 5 ，4 ，5 ，4 ，5 ) 。局中人3 在屯l 处将选择j c 2 7 ，记，1 ( 屯1 ) = ( 1 ，0 ，3 ，2 ，2 ) 。 而在葺6 ，x 1 8 ，而o 只处，贝尔曼函数，1 ( 毛6 ) = 办( _ 6 ) ，j ( 五8 ) = 办( 五8 ) ，1 ( 艺o ) = h ( x 2 0 ) 。 第二步：考察五= “o ，x l l ，毛：，x l ，x l 。，x l ，) 中的每个节点。以五。为例，由于 x l 。d 4 ，局中人4 选择行动。因为4 s 3 ，局中人4 将力图使联盟一局中人s 3 的利益 最大化，由于 m a x ( 才( 西6 ) + 砖( 葺6 ) ，才( 五7 ) + 一( 西7 ) ) = m a x ( 2 + 3 ，3 + 4 ) = 7 n 雌e x , l 处局中人4 选择而，记厂2 ( 而。) = ( 2 ，4 ，2 ，3 ，4 ) 。同理，局中人4 在而，处选 择五9 ，记，2 ( 而3 ) = ( 5 ，4 ，5 ，4 ，5 ) ；局中人5 在而5 处选择而l ，记，2 ( _ 5 ) = ( 1 ，0 ，3 ，2 ，2 ) 。 而，2 ( 而o ) = ( 1 ，0 ，l ，2 ，1 ) ，2 ( z 1 2 ) = ( 3 ，4 ，5 ，3 ，1 ) ，2 ( _ 4 ) = ( 0 ，l ，0 ，2 ，6 ) 。 第三步：考察置= 黾，x 5 ，x 7 ，x 8 ，x g 中的每个节点。以屯为例，由于b ， r 第一章具有固定联盟剖分的扩展型对策 局中人3 选择行动。因为3 s ，局中人3 将力图使联盟一局中人& 的利益最大化， 由于 m a x ( r , 2 ( 五o ) + 茸( 毛o ) ，i 2 ( 而1 ) + 孑( 毛1 ) ) - m a x ( 1 + 1 ，2 + 2 ) = 4 因此在毛处局中人3 选择五。，记，3 ( 黾) = ( 2 ，4 ，2 ，3 ，4 ) 。同理，局中人3 在而处选择而3 ， 记3 ( 而) = ( 5 ，4 ，5 ，4 ，5 ) ；局中人2 在而处选择札，记3 ( 而) = ( 0 ，1 ，0 ，2 ，6 ) 。而 3 ( _ ) = ( 1 0 ，3 ，8 ，1 ，2 ) ，3 ( ) = ( 4 ，1 ，2 ，2 ，2 ) ，3 ( 黾) = ( 2 ，1 ，3 ，0 ，1 ) 。 第四步：考察五= “，x 2 ，玛 中的每个节点。以而为例，由于五砬，局中人2 选择行动。因为2 岛，局中人2 将力图使联盟一局 a s 2 也就是自己的利益最大化， 由于 m a ) 【( 方( _ ) ，芎( 屯) ) = m a x ( 3 ，4 ) = 4 因此在而处局中人2 选择弓，记，4 ( 恐) = ( 2 ，4 ，2 ，3 ，4 ) 。同理，局中人2 在恐处选择西， 记，4 ( 而) = ( 5 ，4 ，5 ，4 ，5 ) ；局中人4 在毛处选择而，记，4 ( 恐) = ( 0 ，1 ，0 ，2 ，6 ) 。 第五步：考察五= 而) 。由于而q ，局中人l 选择行动。因为1 s ，局中人 1 将力图使联盟一局中人墨的利益最大化，由于 m a x ( r 1 4 ( 而) + g ( 五) ，彳( 而) + 譬( 而) ，r 1 4 ( 而) + 彳( 屯) ) = m a x ( 2 + 2 ，5 + 5 ，o + o ) = 1 0 因此在初始节点处局中人1 选择，记，5 ( 而) = ( 5 ，4 ，5 ，4 ，5 ) 7 。 上述算法给出了对策i ( ，x o ) 中联盟一局中人的均衡策略并可以由此确定均衡支 付，下面将解决1 2 2 中所说的联盟一局中人对均衡支付的内部分配问题。 为确定联盟一局中人s = l ，3 对于均衡支付鹾( 甜三，甜乏，砖) = 5 ( x o ) + r f ( x o ) - 1 0 的内部分配，需要考察具有特征函数v k 3 ( r ) ，r l ，3 ) ，的2 人辅助合作对策 g ( x o ， 1 ，3 ) ) ，这里v l 3 ( 1 ，3 ) ) = 5 ( 而) + 芎( 而) = 1 0 。特别需要指出的是，在计算特征 函数l ，3 ( r ) ，r l ，3 ) 的过程中，没有进入辅助对策g ( 而， l ，3 ) ) 的局中人2 ，4 ，5 的 9 青岛大学硕士学位论文 策略固定选择为上述算法中的得到的均衡策略。v 1 3 ( 尺) ，r 1 ，3 ) 的值为r 和 1 ，3 r 之间所进行二人零和对策的值，即尺 1 ，3 ) 作为最大化局中人将力图最大化 联盟r 的支付，而 1 ，3 r 努力使尺的所得最小。可以计算得到_ ，3 ( 1 ) = 3 ，v o , 3 ( 3 ) = 0 ( 可参见文献 3 ) 。利用s h a p l e y 值的计算公式得到趴( 1 ，3 ) ) = 1 3 2 ， 砚( 1 3 ) ) = 7 2 。同样可以计算得到，砚( 2 ) = 4 ，趴( 4 ，5 ) ) = 4 ，观( 4 ，5 ) ) = 5 。 最终我们得到该对策在非合作情形下的最优解 p m s ( x o ) = ( p m s l ( x o ) ，p m s 2 ( x o ) ，p m s 3 ( x o ) ，p m s 4 ( x o ) ，p m s s ( x o ) ) = ( 1 3 2 ，4 ，7 2 ，4 ，5 ) 而h砀屯6 砀 图1 1 1 0 第二章具有变化联盟剖分的扩展型对策 第二章具有变化联盟剖分的扩展型对策 现代对策论所研究的对策模型可分为两类：非合作对策和合作对策。在非合作 对策中局中人选择使自己获得最大支付的策略，在合作对策中局中人考虑使他们所 在联盟的所得收益最大。当不完全合作时，局中人往往选择使他们所在联盟得到最 大支付的策略来形成联盟盟6 16 1 7 3 。本章我们考察具有完全信息的扩展型对策，在对 策树的一些固定结点处可能随机改变联盟剖分，给出最优子树( 或分枝) 以及最优 解的算法，针对这样的对策同时得到了一种解( p m s 向量) 。 2 1 符号和定义 给定以而为初始结点的对策树k ( x o ) ，并且用x 表示k ( 而) 的某个结点，k ( 力表 示树k ( x o ) - l 以x 为初始结点的子树，z ( x ) 表示x 的直接后续结点集合，x 的直接后 续结点y ( y z ( x ) ) 称为局中人f ) 在x 处的选择。本节设赴= t ) 型为所有局中 人集合= l ，甩) 的剖分，t 芮足s , n s j = 。，f 歹，u 型s = ，并用表示的所 有剖分。 定义2 1 1 具有完全信息和变化的联盟剖分的扩展型对策r ( x 。) 及其以而为 初始结点的对策树k ( x o ) 具有以下特点： ( 1 ) 对策树k ( x o ) 的所有结点集合被剖分成刀+ 2 个子集d 1 ，d 2 ，o n ，o n + l o n + 2 ， 其中x 皿，f = 1 ，n 为局中人f 的决策结点，x o n “为边界点( 终端结点) ，x o n + 2 为联盟剖分发生变化的结点。 ( 2 ) 在每个结点x 处局中人集合的剖分a ( x ) a 满足条件 f ( x ) 兰( 力， 砂z ( x ) ，如黔go n + 2 ， 【3 y z ( x ) ：a ( x ) ( y ) ，如黔o n + 2 ( 3 ) 对每个y z ( x ) = 咒，只 ，z 球：，概率分布g ( 乃) ，g ( 只) ，q ( y ) - - 1 ， j ，e z ) ，= l z ( x ) i 给定。 ( 4 ) 在每个边界点给定实数向 青岛大学硕士学位论文 乃( w ) = ( 均( 叻，( w ) ) ，w e 见小j j i ( 叻0 ，i = 1 ，刀 其中红( w ) 是局中人f 在边界点w 处的支付。 2 2 具有变化联盟剖分的扩展型对策最优解的算法 具有完全信息和变化的联盟剖分的扩展型对策将按以下方法进行。 对策在而见+ 2 开始，此时联盟剖分a ( x 。) 给定。按定义2 1 1 中( 3 ) 所给 定的概率分布在结点处选择后续结点墨z ( x 。) ，并且联盟剖分( 墨) a 给定。 若夏d f ( 而) ，则在点墨处的局中人f ( 五) 按照使其所属联盟支付最大化的原则选 择结点夏= u 幅) ( i ) z ( 夏) ，并且在夏处的联盟剖分( 夏) 暑( 墨) 。 如果夏仨见+ 。u 或+ 2 ，则在五处局中人f ( 五) 根据使其所属联盟支付最大化的原 则选择写= u ( 而) ( 夏) z ( 五) 。如果夏见+ 2 ，则在夏处根据定义2 1 1 中( 3 ) 给定 的概率分布选择后续结点五。在随机选择的结点毛z ( 乏) 处，( 墨) a 与夏处的 剖分可能一致也可能不一致。如果在第k 步有夏叠见+ 。u 见+ 2 ，则在夏处的局中人 f ( 瓦) 根据使其所属联盟支付最大化的原则选择夏+ 。= ( 蕞) ( 墨) z ( 瓦) 。如果在第七 步有瓦见+ 2 ，则在结点夏根据定义2 1 1 中( 3 ) 给定的结点五处的概率分布选择 后续结点五卅，在瓦q z ( 瓦) 处联盟剖分( 瓦+ 。) 已给定，它与瓦处的剖分可能 一致也可能不一致。对策在到达边界点we 见+ 。之后结束。最后，根据定义2 1 1 中 的( 4 ) 在边界点w 处局中人的支付为( 啊( w ) ，吃( 们) 。 记对策r ( x 。) 中局中人f 的策略为珥( ) ，局中人f 所有策略的集合用u ，表示，局 中人的策略组合( 局势) 表示为“( ) = ( ( ) ，( ”。每个局势同时确定了终端结点 集合上的概率分布( 因为在z 见+ ：处决策权的转移) ，因此局中人f 的支付是一个随 机变量。局势甜( ) 唯一地与局中人支付的数学期望向量巨( ( ) ，( ”= 【曩( 叻】， 1 2 第二章具有变化联盟剖分的扩展型对策 f n 相对应。因而我们可以把对策写成规范形式 。但是对 策的规范型对我们研究此类对策并不十分有用，因为我们要考虑局中人属于不同的 联盟和联盟剖分的变化，下面提出一种新的构造解的方法，其中考虑到对策当前的 联盟剖分及其动态演变。 如前所述，假设局中人f 在结点y q 为使其所属联盟墨o s j ，s j a ( x ) ) 的支付最大化而采取行动。同时在联盟s ，内部使用s h a p l e y 值来分配支付，其计算 用到特别定义的特征函数r ，x ) ，rcs ，。采用这种方法，下面给出一种构造对策 r ( x o ) 解的算法。对策的求解要从终点位置向起点位置逆推，这个过程与在具有完全 信息的对策中构造子对策精炼纳什均衡n 蝴1 和在部分合作对策中确定最优路径的算 法相似嘲。 设对策f ( x o ) 的长度为丁+ 1 ，把对策树k ( x 。) 的全部结点集合剖分为丁+ 1 个集 合：五，五，墨；其中x r = 扛。 。集合置，f = 0 , 1 ，丁为从初始结点经丁一f 步可 达到的结点组成。用薯，t = 0 ，l ，r 表示置中的结点。 考察k 中的结点，由于对策的长度为t + i ，那么x ocq + 。，局中人的支付定 义h a w ) ，w ex o ，i = l ，| 。 第一阶段从x o 中的结点向x l x l 递推。如果而薯o n + 。u 或+ 2 ，则在x 。处局中 a i ( x ，) 进行选择。假设f ( 而) ：t ：i 姐s j ( x 。) ，s ( x 。) a ( x ，) ，这里 瓯( ) ) 是构成联 盟剖分a ( x ，) 的联盟的集合。每个局中入f ( 而) 以相同概率选择它的后续结点 诼z ( 而) ( 以相同的概率选择后续结点意味着允许使用混合行为策略) 斌m a “x k 蠢，姒力= 。蠢，纵回 2 d 记 孙栌a r g 赋k 羡，驰) 即 青岛大学硕士学位论文 孙柚2 忙蠢，h a y ) 则m a x ，。蠢，纵功 o if e 与( 而)4 _ ”f e 邑( 而)j 如果五q + ：( 即_ 是联盟剖分发生改变的结点) ，对策进行到石g ( x 。) 的概率 为p ( x ) ，根据对策规则，x 。处的支付的期望值为p ( x ) 鬼( 石) ，这里p ( x ) 是选择 后续结点的概率。如果五乜“，在x 。处的支付为忽( x 。) ，i = 1 ，n 。根据这种算法， 有时后续结点的选择是随机的，因而无法给出确定的路径，得到的是分支或子树。 类似的，针对集合五中的每个点五可以构造以t 五为初始结点的分支。因此 在每一个子树k ( x 。) ，x 。五( 当五见+ 。时这个子树只有一个结点) 上，在构建对策 分支的过程中终点夏或者z ( x 。) 上的概率分布得到确定( 如果由2 一( 1 ) 式得出的最大 点不唯一或而q + ：) 。根据子树k ( x ，) ，一k 中局中人的行为，我们引入定义在五 上的贝尔曼函数一：五专砖，i = 1 ，刀。其中1 是局中人f 在结点x i 处的期望支 付。在子树k ( x 。) 上局中人按照以下算法构造1 ( x 。) ，；1 ( 而) = 际i 砑霄。瓢恫，如飘哦- 呱z 囊( 五) ，如飘见“ 2 一( 2 ) g ( 们曩( 叻，如飘见+ ： ( h 表示集合彳中元素的个数) i n 。 第二阶段继续向根部递推。因为在x ：x ：处算法包含新的内容，因此我们详 细讨论。如果而叠见+ 。u 见+ 2 ，则局中人f ( x 2 ) s j ( x 2 ) 在x 2 需要做出选择。算法规 定局中人f ( t ) 以相同的概率选择每个满足如下条件的墨 其中一由2 一( 2 ) 式确定。记 脚m a x 拒副 ) - 搪蠹一(