（应用数学专业论文）动态对策的最优联盟结构.pdf

摘要 摘要 本文所研究的对策类型均是具有完全信息的。首先是针对离散对策情况，分别 研究最优联盟结构和时间一致性问题。区别于传统的按照行动进行联盟剖分的方法， 本文根据选择合作对象给出了一种全新的联盟剖分形成方式。然后，运用降阶的方 法，在求解对策的过程中剖析出在非合作对策中隐性合作的可能性，之后将微分对 策中的时间一致性的概念推广到离散对策中，并举例阐述。最后，针对连续对策情 况，研究二人时间最优的追逃微分对策。 本文的第章中针对具有完全信息的对策，根据选择合作对象给出了一种全新 的联盟剖分形成方式，这是本文的一个重要创新。在此背景下假定联盟形成发生在 对策的最初阶段，按照此种构成方法能够形成所有可能形成的不同的联盟剖分，这 可以清晰地体现出对策进程中联盟剖分的具体的形成过程，在特定联盟形成之后其 中的每个局中人根据其所属联盟利益采取行动。 第二章运用降阶的方法求解对策，通过利用因子对策和辅助对策可以加快求解 的计算过程，但是自然地会出现因子对策的解既不是非合作均衡( 非合作情形) 也 可能不是完全合作的最优解( 合作情形) 。在上述求解过程中我们获得了本文第二个 重要的发现，计算示例显示在非合作背景之下可能出现我们称之为隐性合作的趋势， 这种隐性合作会带给局中人更好的收益；进步地，我们在文中指出当隐性合作转 化为公开的合作时，合作的收益可能变得更好。 第三章研究具有完全信息的有限扩展型部分合作对策的时间一致性问题。在离 散的情况下重新定义了时间一致性的概念，并在此基础上给出了判别一类特殊对策 类的时间一致性的判别定理。 有了前面三章离散对策的研究基础，我们自然而然地可以过渡到连续对策情 况。但是本章中我们的研究只局限于二人连续对称情形，事实上，针对多人情况目 前国际上没有完善的体系。在第四章中研究的是微分追逃对策及其中一种特殊形式 时间最优的微分追逃对策，我们给出了整个追逃空间的划分定理。 关键词：联盟结构；联盟剖分；因子对策：辅助对策；时间一致性；微 分追逃对策 a b s t r a e t a b s t r a c t t h eg a m e sd e a l tw i t hi nt h i st h e s i sa r ea l lg a m e sw i t hp e r f e c ti n f o r m a t i o n f i r s t ，t h i st h e s i sa i m s t os t u d yt h eo p t i m a lc o a l i t i o n a ls t r u c t u r ea n dt i m e - c o n s i s t e n c yp r o b l e m so ft h ed i s c r e t eg a m e s e p a r a t e l y an e wa p p r o a c ho ff o r m i n gc o a l i t i o n a lp a r t i t i o n sa c c o r d i n gt oc h o o s i n gc o o p e r a t i v e p a r t n e r s i sc o n s i d e r e d ，w h i c hi sd i f f e r e n tf r o mt h et r a d i t i o n a la p p r o a c ha c c o r d i n gt ot h ec o o p e r a t i o n b e h a v i o r s e c o n d ，t h i st h e s i sa n a l y z e st h ep o s s i b i l i t yo f e o v e ac o o p e r a t i o ni nt h ep r o c e s so f s o l v i n gt h e g a m eu s i n gt h em e t h o do fd e s c e n d i n go r d e r t h i r d ，t h ec o n c e p t i o no ft i m e - c o n s i s t e n c yo ft h e d i f f e r e n t i a lg a m ei se x t e n d e di n t ot h a to fd i s c r e t eg a m ea n de x a m p l e sa r es h o w e d a tl a s t ，t h i st h e s i s s t u d i e sd i f f e r e n t i a lt i m e o p t i m a lg a m e so f p u r s u i tw i t ht w op e r s o n so f c o n t i n u o u sg a m e s t h ef i r s tc h a p t e ri sc o n c e r n e dw i t han e wa p p r o a c ho ff o r m i n gc o a l i t i o n a lp a r t i t i o n sa e e o r d i n gt o c h o o s i n gc o o p e r a t i v ep a r t n e r so fg a m e sw i t hp e r f e c ti n f o r m a t i o n ，w h i c hi s a ni m p o r t a n ti n n o v a t i o n s u p p o s i n gp l a y e r sf o r mc o a l i t i o n a lp a r t i t i o no nt h ef i r s ts t a g eo ft h eg a m ea l lt h ep o s s i b l ec o a l i t i o n a l p a r t i t i o nc a nb ef o r m e d t h es p e c i f i cp r o c e s so ff o r m i n gt h ec o a l i t i o n a lp a r t i t i o nc a nb es h o w n t h e r e a f t e r , e a c hp l a y e ra c t si nt h ei n t e r e s to f c o a l i t i o nt ow h i c hh eb e l o n g s t h es e c o n dc h a p t e rs t u d i e sm e t h o do fd e s c e n d i n go r d e r t h ec o u r s eo fs o l v i n gp r o b l e m sc a nb e a c c e l e r a t e du s i n gt h ef a c t o rg a m ea n da u x i l i a r yg a m e ，b u ti ta p p e a r st h a tt h es o l u t i o no ft h ef a c t o r g a m ei s n e i t h e rt h en o n c o o p e r a t i v e e q u i l i b r i u m ( n o n c o o p e r a t i v es i t u a t i o n ) n o rt h ec o o p e r a t i v e o p t i m a ls o l u t i o n ( c o o p e r a t i v es i t u a t i o n ) t h es e c o n di m p o r t a n ti n n o v a t i o ni sf o u n d e dd u r i n gt h ec o u r s e o fs o l v i n gq u e s t i o n s ，w h i c hi st h ee x a m p l eo fc a l c u l a t i o ns h o w st h ep o s s i b l et e n d e n c yo fc o v e r t c o o p e r a t i o nw ec a l l e di nt h ec o o p e r a t i v es i t u a t i o n a n dt h ec o v e r tc o o p e r a t i o nm a yb r i n gp l a y e r sb e t t e r i n t e r e s t f u r t h e r m o r e ，c o o p e r a t i v ei n t e r e s tm a yt u m b e t t e rw h e nt h ec o v e r tc o o p e r a t i o nc h a n g e di n t o p u b l i cc o o p e r a t i o n t h et h i r dc h a p t e rs t u d i e st i m e c o n s i s t e n c yo f t h ep a r t i a lc o o p e r a t i v eg a m ei nf i n i t ee x t e n s i v ef o r m w i t hp e r f e c ti n f o r m a t i o n t h ec o n c e p t i o no ft i m e c o n s i s t e n c yi sr e - d e f i n e di nt h ed i s c r e t es i t u a t i o n ， a n dat h e o r e mo f d i s t i n g u i s h i n gt h et i m e - c o n s i s t e n c yo f as p e c i a lc l a s so f g a m e s o nt h eb a s eo fs t u d yt h ed i s c r e t eg a m et h ec o n t i n u o u sg a m ec a nb et r a n s i t e di n t on a t u r a l l y ，b u t t h i sc h a p t e ri sl i m i t e di nt h ec o n t i n u o u ss y m m e t r i c a ls i t u a t i o nw i t ht w op e r s o n s a c t u a l l yt h e r ei sn o p e r f e c ts y s t e md e a l i n gw i t h 一p e r s o n si n t e r n a t i o n a l l y t h el a s tc h a p t e rs t u d i e st h ed i f f e r e n t i a lg a m e o fp u r s u i ta n das p e c i a lt y p eo ft h e m d i f f e r e n t i a lt i m e o p t i m a lg a m e so fp u r s u i t ，a n dt h et h e o r e mo f d i v i d i n gt h ew h o l ep u r s u i ta p a c e k e y w o r d s ：e o a l i t i o n a ls t r u c t u r e ；c o a l i t i o n a ip a r t i t i o n ；t i m ec o n s i s t e n c y ；d i f f e r e n t i a l g a m e so fp u r s u i t 青岛大学硕十学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均己做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 王自 日期：如7 年岁月；，日 青岛大学硕士学位论文 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密d ( 请在以上方框内打“4 ”) 论文作者签名：王磕日期：h 1年岁月3 1 日 导师签名：孑刀泓鸟 日期：姊年月6 日 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 引言 引言 对策论是一门以严格的数学模型来研究和规范描述人与人之间利益相互制约下 策略选择时的理性行为及相应结局，并在统一框架下加以严整的数学分析的理论。 它是在2 0 世纪4 0 年代形成并发展起来的- - f - 年轻而极富生命力的学科。 在对于经典静态或者动态合作对策的研究中一般已经习惯于规定局中人自始至 终参与所属的联盟并为所在联盟获得最大收益采取相应的策略，并且规定某个局中 人的联盟一旦形成则在对策进程中不再发生变化，已有的合作对策理论即建立在这 样的假设的基础之上。 区别于对于合作对策局中人合作方式的严格限制，近年来开始对于局中人合作 和部分合作的方式、联盟结构在对策进程中发生变化时动态对策的最优解以及所获 得的最优解相对于时间的动态稳定性进行了相关研究。这个领域的主要研究结果基 本出现在近5 年的时间内。 对于联盟剖分型的对策的研究最初始于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 e o na 教授及其所领导的研究团队在具有变化 联盟结构的动态对策解的建立领域获得了系列最新研究结果( 见文献“卅) 。 同样在近5 年，由彼得罗相和他所领导学派成员进行了关于合作随机微分对策 的研究，进行了对于有外部随机作用情况下复杂的冲突控制系统内合作过程的数学 及信息计算机模拟。给出了具旁支付和不具旁支付情形的局中人的最优合作行为准 则。 我们在该领域的研究开始于2 0 0 4 年，在部分合作对策领域建立了对n a s h 均衡的 最优反应的概念，完成了p g n 向量的建立并给出算法。对于子对策中最优行为准则的 选择我们已经逐渐形成较为清晰的标准。我们的研究路线与圣彼得堡国立大学的同 行是基本一致的，至少在目前，国内尚未出现与我们的研究领域相近的研究工作。 文献旧定义的变化联盟结构的动态对策中，任一局中人可从一个给定的阶段开 始合作而不必在整个对策进程中合作。具体地说，每一个局中人在对策开始之前需 独立于其它局中人选定一个特定的阶段，并在该阶段开始同其他局中人的合作，加 入到准备在该阶段合作的局中人的联盟中去，该阶段之前此局中人一直保持个体理 性的独立行为而不与其他任何局中人合作。对策进程中局中人不允许改变既定的选 择，从而形成联盟剖分。 区别于文献“1 所定义的对策，文献“1 考虑在具有完美信息的多阶段对策中联盟 分割形成的两种方法。在第一种方法中局中人在对策树的每一个节点处可选择合作 青岛大学硕士学位论文 或不合作，采取合作行为的局中人形成一个单一联盟；在第二种方法中局中人在对 策的最初阶段形成联盟分割，其后联盟中的局中人根据其所属联盟的利益来采取行 动。在每种方法下构造最优路径和最优联盟分割的方法被提出。这里需要指出的是， 文献嗍对部分合作的定义仍然具有一定的局限性，即对策进程中局中人仍然不能改 变既定的选择，这具体表现在对策规则中对于局中人联盟单调递增性的要求上。 本文研究的是在具有完全信息的对策中考虑具有任意联盟结构的一种较按照行 动进行联盟剖分的全新的构成方法。在此背景下假定联盟形成发生在对策的最初阶 段，在联盟形成之后每个局中人根据其所属联盟利益采取行动。这种方法体现出对 策进程中任意联盟结构形成的不同方式，不再是事先假定联盟结构也不再是按照何 不合作进行联盟剖分，而是充分考虑到局中人的行动意愿选择合作对象，并且包含 各种选择情况，从而形成任意的联盟结构。同时，提出利用降阶的方法求解对策， 计算示例显示在非合作背景之下可能出现我们称之为隐性合作的趋势，这种隐性合 作会带给局中人更好的收益；进一步地，我们在文中指出当隐性合作转化为公开的 合作时，合作的收益可能变得更好。此外，在离散的情况下重新定义了时间一致性 的概念，并给分别出了一个时间一致的和时间不一致的具有完美信息的有限扩展型 部分合作对策的例子，将时间一致性这个概念形象化的体现出来。 2 第一章具有任意联盟结构的多阶段对策 第一章具有任意联盟结构的多阶段对策 现代对策论中原则上所考虑的理想对策模型可分为两类：策略对策和合作对策。 在策略对策中局中人选择使他自己获得最大支付的策略，在合作对策中局中人只考 虑使他们所在的联盟所得收益最大，而联盟中个人之间如何分配仍然有许多问题需 要解决。在对于经典静态或者动态合作对策的研究中一般已经习惯于规定局中人自 始至终参与所属的联盟并为所在联盟获得最大收益采取相应的策略，并且规定某个 局中人的联盟一旦形成则在对策进程中不再发生变化，已有的合作对策理论即建立 在这样的假设的基础之上。区别于对于合作对策局中人合作方式的严格限制，近年 来开始对于局中人合作和部分合作的方式、联盟结构在对策进程中发生变化时动态 对策的最优解以及所获得的最优解相对于时间的动态稳定性进行了相关研究。 经过近十年的努力，研究取得了一定的进展： 在1 9 9 6 年以前，对于对策中合作的和个体的行为方式组合的可能性进行了讨论， 真正认真研究过的还只是由完全合作向个体的行为转化( 或者相反) 的过程 ( g z a c c o u u r ，s j o r g e n s o n ，1 9 9 2 1 9 9 6 ) 。在c h i h r uh s i a o ，r a g h a v a n ( 1 9 9 3 ) ，a v a n d e nn o u w e l a n d ，s t i j s ，j z a r z u e l o ( 1 9 9 5 ) 的研究工作中也曾尝试定义部分合作的 静态对策，但没有超出对经典的合作对策的最优准则进行推广的范畴。特征函数的 定义也是形式上的引进，与静态理论中的一样。 在1 9 9 0 年一2 0 0 0 年期间，俄罗斯圣彼得堡大学的p e t r o s j a nl a 教授进行了动 态对策稳定性问题进行了充分研究，其研究成果的标志是2 0 0 0 年著作扩展型对策： 最优性与稳定性的出版。 在2 0 0 0 年一2 0 0 6 年期间，俄罗斯圣彼得堡大学p e t r o s j a nl a 教授开展了针对 具有完全信息的动态合作对策中部分合作情形的研究，其研究成果标志是2 0 0 0 年论 文部分合作动态对策的值的发表。在这篇文章中，p e t r o s j a nl a 教授研究了 扩展型部分合作对策( 其主要特点是每一个局中人的行为是他参与联盟与单独行动 的一个组合) ，在纳什均衡解以及合作对策解的基础上使用与纳什均衡解不同的概念 构造了一种最优路径的算法，这种算法主要考虑的问题是在个体行为被联盟代替的 节点处局中人支付的定义，从而得到了一种稳定的最优解。另外，p e t r o s j a nl a 教授也对具有变化的联盟结构的动态合作对策进行了研究，其研究成果标志是2 0 0 4 年论文具有变化联盟结构的动态对策的发表。在这篇文章中，考虑了具有完全 信息的扩展型对策，在对策树的一些固定节点处随机地改变联盟剖分，引入一个特 殊定义的特征函数，提出一种构造最优路径的算法，同时也得到了一种相对稳定的 青岛大学硕士学位论文 新值( p m s 一值) 。同时，p e t r o s j a nl a 教授在2 0 0 5 年发表的论文具有联盟结构 的多阶段对策考虑在具有完美信息的多阶段对策中联盟剖分形成的两种方法。在 第一种方法中局中人在对策树的每一个节点处可选择合作或不合作，采取合作行为 的局中人形成一个单一联盟；在第二种方法中局中人在对策的最初阶段形成联盟剖 分，其后联盟中的局中人根据其所属联盟的利益来采取行动。在每种方法下构造最 优路径和最优联盟剖分的方法被提出。 本章研究的是在具有完美信息的对策中考虑具有任意联盟结构的一种较按照行 动进行联盟剖分的全新的构成方法。在此背景下假定联盟形成发生在对策的最初阶 段，在联盟形成之后每个局中人根据其所属联盟利益采取行动。 1 1 符号和定义 若x 是一对策树的一个节点，如果此节点能在阶段内由对策树的根到达则称 节点x 有秩k ( k = o ，l ，2 ) 。我们用e 表示对策树中紧跟节点工的节点集合，用f ( 善) 表 示在节点x 处决策的局中人设= l 2 坍 为局中人的集合 定义1 1 1 定义局中人集合的联盟剖分，局中人集合的子集合系统= s 二。， 其满足岛n 墨= o ，歹七，且u 邑= 在节点x 处的联盟剖分用( z ) 表示。 假定在具有根d 的对策树g 上定义具有完美信息的珂人对策r ( 。 设0 为对策树g 的根，在对策树6 上的新的对策采用以下方式进行定义。 假定在对策树g 的根处局中人i 采取行动，则对策树g 的根0 是局中人珀q 个人 决策点。此时局中人的联盟剖分为a ( o ) = “1 7 - 9 栉 。在0 处局中人i 有行种选择： 即从剖分( d ) 的行个联盟中种选择一个联盟 _ ，) 作为合作伙伴，如果f 选择 f 本身， 即表示他不想与任何一个联盟合作，也就是说局中入i 预见到与其它局中人的结盟在 选定的最优准则之下并不会使得f 的收益增加。集合尼中对应每一种选择的每一个 节点相应地是联盟 1 ， 打，的决策点，被选择的局中人_ ，为了自身收益的最大化， 它有两种选择，第一种选择是同意合作，这时候局中入联盟剖分发生变化；第二种 4 第一章具有任意联盟结构的多阶段对策 选择是不同意合作，此时联盟剖分不变，与根节点相同。当 n 同意合作的时候，联 盟剖分变为 f ，力， 七 ， 行 ，这时候如果轮到_ | ，七f ，_ ，做决策，他会有一一1 种选 择来选择合作对象，目的是自身收益的最大化；如果轮到_ ，作决策。他决策的依据 将首先是使得联盟 f ， 的总收益最大化它，：f f n 一1 种选择。 假设对策树g 满足一个附加条件，即在秩数为0 和偶数的节点x 处的联盟剖分 为( x ) = 墨 二。，则在此个人决策点的选择有研种。 在对策树g 上秩数为0 和偶数的节点处局中人决定选择哪个联盟q 作为合作对象， 在秩数为奇数的节点被选择的联盟墨选择同意合作或者不同意合作。如果同意合 一 。 “ 作，则联盟结构发生变化，如果不同意合作，则联盟结构不变。于是，在对策树g 的 每一个节点处都定义了联盟剖分。 现在我们将给出对策树g 上具有完美信息的对策的正式定义。 定义1 1 2 一个具有完美信息的扩展型聍人对策是一个具有以下特征的对策树g ：， 对策树的长度为2 n + l + l ，前2 竹个阶段是联盟形成阶段，后1 4 阶段是联盟形成之 后对策进行阶段； 给定集合x 的剖分丑，昱，只，只。，这里只，f 是局中人f 的个人决策点集合， 满足对每个f ，数j j ( 办k ( o = o ，2 ，4 ，2 ( n 1 ) 存在且使秩数为| i ( f ) 的节点是局中人 i 的个人决策点。处于个人决策点的局中人i 是此时他所处联盟的发言人，所做的决 策是联盟的决策，依据是使得所在联盟总收益最大化。集合匕。是终点集合； 如果x 是秩数为0 或为偶数的节点且( 曲= t 二，则l f , l = m ，如果功选择自 己所在的联盟，则这一分支联盟剖分变化从这个阶段开始直到对策结束总是保持不 变。如果x 是秩数为奇数的节点则表示在此节点处被i 选择的联盟s 做出反应， 青岛大学硕士学位论文 c c 只，1 只l _ 2 。联盟巴做决策的依据是加入f ( 功所在的联盟之后的q 分配总和不 小于置不加入联盟所得的总收益。如果t 不同意合作，那么在之后的对策进程中s 也不会选择f 在每个节点x x 处唯一定义联盟剖分( x ) = = 马 三。 秩数为0 或为偶数的节点每一次只能选择一个联盟进行合作。局中人f 一旦加入某 个联盟则不能退出。 在终点w 只。处，支付只( w ) = 囊( w ) ，f n 被定义。对秩数为珂的节点毛和蠢 ( 矗) 对策r ( 毛) 与对策r ( ) 等价，o 是实现这种等价的的映射，于是 ( 计= ( o ( ，) ) ，这里w 和o ( w ) 是对策r ( 矗) 与r ( t ) 的相应终点。 定义i i 3 局中人f n 的策略玑( ) 是这样一个映射，对应每个节点工p ，节点 ) ，只或在只上的概率分布为矿( 矿= 矿劬j ，) | 只，p 。( ) ，) o ， 删矿( ) ，) = 1 ) 。 1 2 构造对策的解 对策的解通过使用逆推归纳法来构造。 假定对策的长度为2 n + ，+ 1 ，像前面所说的一样，在节点x 只( x 的秩数大于 或等于2 ) 处，局中入i 根据其所属联盟s ，总分配采取行动。要定义联盟中局中入 的支付我们也针对特别构造的特征函数采用s h a p l e y 值。这样选择的最优准则将导 致最终的支付成为p m s 向量 】。 步骤0 设而是秩数为2 摊+ z 的终点，则支付为矿( 而) ；曩( 确) ，i 步骤t ，t i 嬲上r 一1 】。 6 第一章具有任意联盟结构的多阶段对策 在这些节点处对策在固定的联盟剖分( ) 下进行，于是 翩= 静xi 三乏 这里焉一。= a r g 警( ( 墨的秩数2 ，节点磊的秩数为2 n + 1 ) 。这儿 l e s ( i ，s 以) ：s “) ，j “) 】意味着总和是针对包含在节点薯采取行动的局中人托i ) 的联 盟s ( 薯) 的。 节点写一。可能不是联盟s “) 中局中人获得支付总和最大值的唯一节点。这可能 导致解的不唯一。 情形2 t = t 。 在这种情形下对策在第一个节点而。处形成联盟剖分。要定义函数( 而。) 的值就 必须从联盟支付中取出局中人的支付，即对每个联盟s ( b ) ( 而。) 定义支付总和 ，也。) - - z 。如，4 ( ) 概念 。 在 恐。 处定义向量 p m s ( x 2 。) = ( p m s , ( x z 。) ，p m s ( x 2 。) ) ，这里p m s , ( x 2 。) 是在节点而。处通过针对定义 在联盟s ( 屯) ( ) 的子联盟上的特征函数吩( 引( ) 计算出s h a p i e y 值而得到的局 中人i 的支付。联盟s ( x 2 。) 中局中人的支付根据s h a p l e y 值进行计算，对应特征函数 1 ，( ) 定义如下： 1 ，( s ( 屯。) ) = 馄) ( 恐) ； 对每个非空联盟r c s ( ) ，v ( 足) 的值等于在联盟r ( 最大化局中人) 和、r 之 间的零和对策的值； v ( o ) = 0 。 7 青岛大学硕士学位论文 显然超可加性条件满足。 若砚( 纯，) ( x 2 。) ) 是局中人f s ( ) 的支付，则p m s 向量的分量有如下形式： 于是 钐皇t e 1 + l ，l + 2 n 】。 幽c 叫雾隅j ) ，麓：， y j ( x 2 。) = p m s , ( x 2 。) 若的秩为偶数，则的秩为奇数。假设( 玉) = 只 二，以一t ，且f ( ) s 。 1 局中人f 选择t ( 只一一) ，j # l 如果墨( 只。) 选择第一种选择z ：一：( 同意合作) ， 那么联盟结构发生变化，a ( z i t _ 2 ) = 墨u 邑，最，邑+ 墨。& ) ，z 1 。；如果 蜀咄) 选择第二种选择z 2 t _ 2 ( 不同意合作) ，那么联盟结构不发生变化， ( z 2 ，一：) 2 ( 薯) = 二。，z 2 乏- 2 - a r g 。嘴。2 ( ：川) ；：砑。锹霭。， 1 ”= 1 1 , 6 2 3 ( n j 碡6 ( ) 。一。) = 。2 ( - 一：) ， 节点乏一：可能不被唯一确定。这可能导致解的不唯一。 2 局中人f 选择s 一。) ，则代表联盟墨( 咒一。) 不准备于任何一个联盟合作。所以此时 的联盟结构不变，且这个分支结束。 - 1 ( m 一。) = - 2 0 2 。) 因为墨点处决策的局中人是f ，是此时他所属联盟s 的发言人，所做的决策是联盟 的决策，依据是使得联盟中的局中人分配总和最大化。 r 第一章具有任意联盟结构的多阶段对策 当f = 2 n + l 时，在对策的根。处可得到支付刀“( d ) 。对应最优路径的这种联盟 l 剖分我们称为最优联盟剖分，相应的向量函数“( d ) 称为对策的值，这样就与最优 联盟剖分的p m s 向量一致。 1 3 示例 这种方法考虑到了所有联盟剖分，并且包含每种割分所有可能的形成过程。 例1 在图1 1 所示的对策树g 上考虑具有完美信息的扩展型对策。= 1 ，2 3 ，4 局中人1 的个人决策点为0 ，局中人2 的个人决策点为w 2 ，局中人3 的个人决策点 为，局中人4 的个人决策点为比。在终点处定义局中人支付。 d 啦心 3 l 2 o 3 1 l 0 2 2 l o 图1 1 根据对策树g 构造对策树0 ，图2 仅仅给出了对策树0 的一部分，即局中人l 选择 2 并且2 同意合作的一部分对策树a 丑- - o ，最- - x 2 ，另= ，而，黾，而 ， 只= 而，而，屹，砀，b ，砀 ，以上这些节点是秩为零或者是偶数的节 9 一 啦 删鼽x燃概 趾 = ， 旧一 青岛大学硕士学位论文 点。( d ，五) 表示i 选择2 ，“，毛) 表示2 同意合作，这时候局中人联盟的剖分发生变 化，( 屯) = 1 ，2 ， 3 ， 4 ，在恐点处是局中人2 的决策点，此时2 属于联盟 l ，2 ， 他是联盟 1 ，2 的发言人，代表的整个联盟的决策，它的目的是使得联盟中的局中人 i 和2 的分配总和最大化。( 而，屯) 表示2 选择自己，即不予其他的局中人合作，那 么这个分支的联盟结构不再发生变化，( - 9 表示在玛之后的子对策树上与岣。点有相 同的结构( 其他的( 一) 也代表类似的子对策树) ( x 2 ，- ) 表示2 选择3 ，k ，黾) 表示 2 选择4 。对策依进行下去 如，而，五，而。 表示在他们的前任节点处的局中人选择联盟 4 ； 而，勘，) 表示在他们的前任节点处的局中人选择联盟 l ，2 ； 粕) 表示他 的前任节点处的局中入选择联盟 1 ，2 ，3 ； 而，) 表示他的前任节点处的局中人选择联 盟 l ，2 , 4 ； 而，而2 ，h ，砀，h ，b ，而， 表示在他们的前任节点处的局中人只 选择和自己合作。在边界点处联盟剖分被依次定义： ( 】啕) = ( j ) = ( 而，) = 1 ，2 ，3 ，4 ， ( 】柚) = ( 屯，) = ( ，畅) = 1 ，2 ， 3 ，4 ， ( _ 。) = ( _ ，) = ( ，) = ( 屯) = ( 而。) = 1 ，2 ，4 ， 3 ， ( 毛：) = ( 而。) = ( ，) = ( 为，) = ( 毛。) = ( 毛，) = ( 而：) = ( 而。) = ( 屯) = l ，2 ， 3 ， 4 ，( 粕) = ( 岛) = ( ) = ( 毛。) = 1 ，2 ，3 ) ， 4 1 0 第一章具有任意联盟结构的多阶段对策 除 b 除 2 ， 一 i 、 b o 3 1 ( 一)( 一)( ”)( ) ( i 一) ( )( ) ( 一) u 对2 粼甜 0 一影。心迅 砭 i b - 图1 2 我们采用逆推归纳法寻找这一分支上的最优路径。 青岛大学硕士学位论文 考虑在子树k ( 一) 上的子对策。在节点黾。处局中人4 采取行动( 4 l ，2 ，3 ，4 ) 。 h i ( x , s ) + 吃( 5 ) + 玛( 墨5 ) + 啊( 5 ) = 6 ( ) + 坞( 墨6 ) + 魄( 6 ) + 啊( ) = 9 ，于是在节 点妇处局中人4 将选择毛。，因此y 1 ( 黾。) = ( 2 ，3 ，1 ，3 ) 。继续向对策树的根移动。 考虑在子树k ( t z ) 上子对策。在节点墨：处局中人3 采取行动( 4e l ，2 ，3 ，4 ) 。由 y ? ( x 5 3 ) + 以( 毛3 ) + 一( 如3 ) + 以( 墨3 ) 托i 、一“，r ，2 il z “，1 - 乃il z “，+ 以1 ( x h ) 可知在屯2 处局中人3 将选择妇且，2 ( 墨2 ) = ( 2 313 ) 。 考虑在子树k ( ) 上的子对策。在节点处局中人2 采取行动。因为 斤( b ) + 疙瓴。) + 露如1 ) + 力( ) 砰( 勘) + 力( 2 ) + m 2 嘞j + 几2 ( 嘞) 所以在处局 中人2 选择嘞且，3 ) = ( 2 ，3 ，1 ，3 ) 。 考虑在子树k ( x 3 9 ) 上的子对策。在节点处局中人1 采取行动。因为 订( ) + 烈3 ，1 。，3 3 4 9 ，t m 3 帕卜，1 3 5 0 ，t ，2 3 l j ，t m 3 j 十乃3 ( ) 所以在x 3 9 处局 中人1 选择，且广( 毛，) = p m s ( x 3 0 。计算特征函数v ( ，) 有呷，2 ，3 ，4 ) = 9 ， v ( 1 ，2 ，3 ) = 6 ，v ( 1 ，2 ，4 ) = 6 ，v ( 1 ，3 ，4 ) = 6 ，v ( 2