（基础数学专业论文）合作对策的解在新的最优准则下的构造及对策模型.pdf

摘要 摘要 本文分为三章。第一章针对于经典静态合作对策中效用不可转移的对策( n t u 对策) 建立了弱优超与弱稳定集的概念，对n t u 对策核心中的支付进行了精炼，并 讨论了所有不能被弱优超的支付的全体所组成的集合与核心、弱稳定集三者的关系。 第二章和第三章建立在具有完全信息的有限扩展型对策基础上。局中人以维护 自己所在的联盟利益为行为准则，即采取策略使得其所在联盟总收益最大。定义了 对非合作n a s h 均衡的最优反应，并以此为原则建立特征函数，在局中人对个体合理 性的要求无法保障的情况下采用核子( n u c l e o l u s ) 的方式在对策中建立动态最优解， 并给出最优解以及最优路径的算法。 第二章具体研究了具有完全信息和变化联盟结构的有限动态合作对策。针对于 在对策树给定的有限个节点上随机改变联盟剖分的动态对策，通过引入新的特征函 数和最优准则，建立了其动态最优解p g n 向量，并给出最优路径的算法。 第三章具体研究了具有完全信息的有限扩展型联合对策。针对于在对策开始的 阶段首先形成所有可能的联盟剖分过程的联合对策，构造出了最优联盟剖分。通过 引入新的特征函数和最优准则，建立动态最优解p g n 向量，同时给出最优路径的算 法。 硕士研究生乔晗( 基础数学) 指导教师田志远教授 关键词：n t u 对策弱优超联盟剖分联合对策p g n 向量 a b s t r a c t a b s t r a c t t h i st h e s i si sc o m p o s e do ft h r e ec h a p t e r s i nt h ef i r s tc h a p t e r , t h ec o n c e p t so fw e a k d o m i n a n c ea n dw e a ks t a b l es e ti nc l a s s i c a ls t a t i c c o o p e r a t i v eg a m ew i t h o u t s i d e p a y m e n t ( n t ug a m e ) a r ed e f i n e d ；t h ep a y o f f so f c o r e si nn t u g a m e sa r er e f i n e d a n d r e l a t i o n so f c o r e ，w e a ks t a b l es e ta n d p a y o f f sv e c t o rs e t st h a tc a n n o t b ew e a k l yd o m i n a t e d a l ed i s c u s s e d g a m e si ne x t e n s i v ef o r mw i t hp e r f e c ti n f o r m a t i o na r ec o n s i d e r e di nt h es e c o n da n d t h i r dc h a p t e rt h ep l a y e ra d o p t st h eb e h a v i o rr u l e sw h i c hm a i n t a i np r o f i t so fc o a l i t i o n s t h e yb e l o n gt o ，n a m e l y , t h ep l a y e rc h o o s e ss t r a t e g i e sw h i c h m a x i m i z et h es u mo f p a y o f f s o fc o a l i t i o n s n l ec o n c e p to ft h eb e s tr e s p o n s et on a s he q u i l i b r i u mo f n o n c o o p e r a t i v e g a m ea n d c h a r a c t e r i s t i cf u n c t i o n sb a s e do nt h i sa r ed e f i n e d b yi n t r o d u c i n gn u e l e o l u s ，t h e d y n a m i co p t i m a ls o l u t i o n ( p g nv e c t o r ) i sg i v e na n da l g o r i t h mf o rt h es o l u t i o na sw e l la s o p t i m a ls u b t r e e ( b u n c h ) i se s t a b l i s h e dw h e n i n d i v i d u a lr a t i o n a l i t yc a n n o tb em e t c o n c r e t e l y ，f i n i t ed y n a m i cc o o p e r a t i v eg a m e w i t hp e r f e c ti n f o r m a t i o na n dc 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 si sc o n s i d e r e di nt h es e c o n d c h a p t e r f o rd y n a m i cg a m et h a t r a n d o m l yc h a n g e sc o a l i t i o np a r t i t i o n s a tl i m i t e df i x e dn o d e so ft h e g a m et r e e t h e d y n a m i co p t i m a ls o l u t i o n ( p g nv e c t o r ) a n dt h ea l g o r i t h mf o rc o n s t r u c t i n gt h eo p t i m a l s u b t r e e ( b u n c h ) a l eg i v e nb yi n t r o d u c i n gn e wd e f i n e dc h a r a c t e rf u n c t i o n sa n do p t i m a l r u l e s i nt h et h i r d c h a p t e r ；t h e c o a l i f i o u a lg a m eo ff i n i t ee x t e n s i v et b r mw i t h p e r f e c t i n f o r m a t i o ni sc o n s i d e r e d f o rc o a l i t i o n a lg a m e st h a tf o r ma l lc o a l i t i o n a l p a r t i t i o n sa t b e g i n n i n gp h a s e o p t i m a l c o a l i t i o n a l p a r t i t i o n i sc o n s t r u c t e d t h ed y n a m i co p t i m a l s o l u t i o na n dt h ea l g o r i t h mf o rt h eo p t i m a ls u b t r e e ( b u n c h ) a r eg i v e nb yi n t r o d u c i n gn e w d e f i n e dc h a r a c t e rf u n c t i o n sa n d o p t i m a lr u l e s g r a d u a t e ：h a nq i a o ( m a t h e m a t i c s ) d i r e c t e db y p r o f z h i y u a n t i a n k e y w o r d s ：n t ug a m e ；w e a kd o m i n a n c e ；c o a l i t i o n a lp a r t i t i o n ；c o a l i t i o n a lg a m e ； p g n - v e c t o r 青岛人学硕十学位论文 序 对策论是运用严谨的数学模型研究冲突对抗条件下最优决策问题的理论，它足 在2 0 世纪4 0 年代形成并发展起来的一门年轻而极富生命力的学科。1 9 4 4 年j v o n n e u m a n n 和0 m o r g e n s t e r n 合著的t h e o r yo fg a m e sa n de c o n o m i cb e h a v io r 是对策论作为一门学科诞生的标志。 按对策中局中人的行为方式是否有先后之分可将对策划分为动态对策和静态对 策；而根据局中人行为的出发点是维护集体利益或个体利益又可将对策划分为合作 对策和非合作对策。 自对策论学科诞生以来，非合作对策( 包括静态和动态) 得到了广泛而深入的 研究。目前，非合作对策理论体系已趋于完善并在社会经济生活中得到极为成功的 应用。由于在非合作均衡方面所做出的杰出贡献，1 9 9 4 年度的诺贝尔经济学奖由著 名对策论学家j o h nf n a s hj r 、r s e l t e n 以及j h a r s a n y i 教授共同分享，这也 标志着非合作对策在发展过程中达到颠峰。 经典静态合作对策理论中假设局中人为了各自所属联盟的最大和收益而采取策 略，然后解决在联盟内部对最大和收益进行分配的问题。寻找合作对策中满足存在 性并具有唯一性性质的解是合作对策研究的核心问题。然而遗憾的是，目前已知的 各种合作对策的解在具备各自优点的同时都无一例外地具有存在性或唯一性不能保 障的某种缺陷。文献 1 - 5 3 中提出了多种经典静态合作对策解的概念，如：合作对策 的稳定集、核心( c o r e ) 、核( k e r n e l ) 、核子( n u c l e o l u s ) 、谈判集、s h a p l e y 值等。 1 9 9 6 年文献 6 中首次提出合作对策中弱优超和弱稳定集的概念，并提出以弱稳定 集作为一类新解的构想。关于效用不可转移的对策( n t u 对策) ，虽然已经建立了核 心及s h a p l e y 转移值等一些解的概念，然而n t u 对策理论还远未达到完善。 在对于经典静态或者动态合作对策的研究中一般已经习惯于规定局中人自始至 终参与所属的联盟并为所在联盟获得最大收益采取相应的策略，并且规定某个局中 人的联盟一旦形成则在对策进程中不再发生变化，已有的合作对策理论即建立在这 样的假设的基础之上。区别于对于合作对策局中人合作方式的严格限制，文献 8 、9 、 1 8 、2 0 等在对于局中人合作和部分合作的方式、联盟结构在对策进程中发生变化 的研究方面近5 年来取得了积极的进展。 对于对策中合作的和个体的行为方式组合的可能性的讨论，已经研究过的包括 完全合作向个体的行为转化( 或者相反) 的过程( 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 nd 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 ) 的工作中尝试定义部分合作的静态对策，但没有超出对经典的合 作对策的最优准则进行推广的范畴。3 ”。特征函数的定义也是形式上引进，与静态 1 序 理论中的一样。 事实上，动态合作对策模型更适合讨论现代经济系统中所出现的实际问题，建立 动态合作对策中新的构造最优准则的方式已经成为动态合作对策研究的中心问题。 以统一的观点来研究动态对策过程，即不仅包含完全合作和最大化自己支付的个体 倾向，还要考虑到各种程度的合作的可能，以及这种合作程度根据对策进程所产生 的变化。此时则有了对不同合作程度的效果、持久性和对于在矛盾冲突过程的状态 的依赖性进行量化评估的可能。圣彼得堡大学的p e t r o s j a nl 。a 教授领导的学术团 队2 0 0 0 2 0 0 4 年讨论了具有完全信息和在对策树的某些固定节点上随机改变联盟剖 分的对策，并构造了最优予树的算法和上述对策的解( p m s 值) ”。 文献 2 0 中所提出的p m s 向量是基于联盟内部以s h a p l e y 向量的方式进行分配 所定义的，但是在对策不满足超加性的情况下这样的定义无疑将受到限制。 以二人零和对策的值作为联盟内部合作对策特征函数的值等价于经典的合作对 策特征函数的定义，即联盟获得的可以保障的最大收益。这样的定义基于联盟对可 能获得收益的保守的估计，基于对联盟之外的局中人最极端对抗行为的判断。这样 的观点目前在以下三个方面遇到挑战。一方面是新的对局中人的合作方式的认识以 及联盟结构在对策进程中可能发生的变化要求改变局中人仅仅以极端对抗的思维判 断其他局中人的行为方式；二是动态对策进程本身所决定的，在具有完全信息的动 态合作对策中后行动的局中人可能根据自己所观测到的先行动的局中人的行为而改 变自己的决策方式；第三方面是在动态对策进程中合作与非合作的界线变得模糊， 非合作意义下的均衡概念( 如n a s h 均衡) 在动态合作对策进程中仍然具有相当的参 考价值。 上述原因促使我们思考在动态合作对策进程中以全新的方式构造特征函数。以 二人零和对策的值作为合作对策中特征函数的值的构造方式保证了子对策的特征函 数具有超加性，但是在特征函数的构造方式发生改变的情况下，比如把特征函数的 值视为对非合作n a s h 均衡的最优反应时，特征函数可能表现为不具有超加性，这使 得s h a p l e y 向量的运用没有意义( 因为此时它不是个体合理的) 。 本文以对非合作n a s h 均衡的最优反应为原则构建特征函数，在局中人对个体合 理性的要求无法保障的情况下采用核予( n u c l e o l u s ) 的方式在具有变化的联盟结构 的动态合作对策以及具有完全信息的联合对策中分别获得其动态最优解p g n 向量， 并给出最优路径的算法。 2 青岛人学硕士毕业论文 1 1 引言 第一章用弱优超的概念改造n t u 对策中的核心 众所周知，在效用不可转移的合作对策( n t u 对策) 背景之下由于支付的不可 转移造成特征函数只能阻集值映射这种极为复杂的形式来定义，并造成优解存在的 不确定性、结构难以用解析形式表述等一系列困难。对于n t u 对策虽然也建立了核 心及s h a p l e y 转移值等一些解的概念，然而其理论还远未达到完善。 1 9 9 6 年出现的弱优超的概念通过比较合作对策中联盟总体收益之间的差另0 的方 式确定分配的优劣，并在此基础上提出用弱稳定集作为对策的一种新的优解。弱优 超概念提供了在合作对策范围内建立弱稳定集的可能，已经证明凸对策中存在唯一 的稳定集和弱稳定集，两者一致并是该对策的核心( c o r e ) ；均衡对策的核心是该对 策唯一的弱稳定集( 1 9 9 6 - 1 9 9 9 ) 等一系列结论。 弱优超概念使得在n t u 对策范围内建立耨解成为可能。据此，本章将在n t u 对 策的子类中建立一种新的支付优劣比较准则，并按这种准则尝试对n t u 对策的核心、 s h a p l e y 转移值等优解做进一步的改进或提出新的最优解决方案；同时展开对于新 的优解存在的充分性条件、与现有体系的相容性、在特定条件下优解的唯一性等方 面的研究。具体地，本章建立了n t u 对策中弱优超和弱稳定集的概念及其相应理论。 l2 定义和标记 定义1 2 i 具有”个局中人的对策称为 人对策。h 人正规型对策包括如下三 个因素： ( 1 ) 局中人集合n = 12 ，聍 ； ( 2 ) 各局中人的策略集z 1 ，x 2 ，x ”： ( 3 ) 个实值函数只，马，只，即支付函数。其中e ( x 1 ，x 2 - - y ) 表示局中人1 采 用策略x 1 ，局中人2 采用策略x 2 ，局中人n 采用策略x “时局中人f 所得到的支 付。 这样一个疗人对策记为r = ( ，扛矗弛 ) 。 重策略组x = ( x 1 ，x 2 ，x ”) 称为对策r 的平衡点或平衡局势，如果对于每个 3 第一章用弱优超的概念改造n t i j 对策中的核心 f ，只o ) = m 。a 。x p , ( z l y 。) ；其中x l j ，= ( x i ，z 2 ，x 1 ，y 。，x 92 x ”) 表示在局势x 之下 局中人i 偏离了x 。而采用y 。，其他局中人策略都不变时所得的新局势。如果一个局 势是平衡局势，那么任何单个局中人在其他局中人都维持这一局势的情况下，无法 通过改变其自身的策略使自己获利更多。 对于h 个局中人的合作对策，局中人可以进行充分的合作：可以事先商定，把他 们的策略协调结合起来，在终局后重新分配若干个局中人所得支付的总和。 定义1 2 2 局中人集合n = 1 ，2 ，h 的任一子集s 称为联盟。所有联盟的全体 记为6 ( n 1 。 定义1 2 3胛人合作对策的特征函数是指定义在6 ( n ) 上的一个实函数 v ：8 ( n ) _ r ，其中v ( s ) 表示联盟s 通过协调其成员的策略所能保证得到的最大支 付( 赢得) 。 n 人对策r = ( ，红 豫 ) 的特征函数可表示为v ( s ) 2 絮盛穗丢只( t 力，其中 也表示s 中全部成员的联合混合策略的全体，x 。表示、s 中全部成员的联合混 合策略的全体。 特征函数v 满足：( 1 ) v ( e o ) = 0 ； ( 2 ) v ( s u t ) v ( s ) + v ( t ) ，s n t = 中( 超力口性) 。 由集合和特征函数v 确定的聍人合作对策可记为f = 【，v 】。合作对策的各局 中人从联盟的收入中分得的份额，称为支付向量，用xz ( _ ，x ：，x 。) r ”表示，其 中x ，表示第f 个局中人所得的份额。 定义1 2 4 满足以下两个条件的支付向量称为对策r = i n ，v 】的分配： ( 1 一v ( f ) ， i = 1 , 2 ，疗； ( 2 ) x ，= v ( ) 。 对策r 分配的全体用e ( v ) 表示。 哇 青岛人学硕士毕业论文 定义1 2 6 对于分配x 和y ，如果存在联盟s c n ，使得 石， y ， vz s 一v ( s ) f e s 则称x 关于s 优超y ，记为x y 。 s 1 3 合作对策的解 定义1 3 1 对于n 人合作对策r = 【，v l ，分配集e ( v ) 中不被任何分配优超的 分配，其全体称为对策的核心( c o r e ) 。记为c ( v 1 。 定理1 3 1 核心可表示为满足 x ( s ) v ( s ) ，v s f f z n x ( ) = v ( ) 的支付向量工的全体。其中x ( s ) = t 。 o e s 核心作为合作对策的解的缺陷是核心经常是空的。 定义1 3 2 设，是一个联盟，称，为对策的支柱，如果对于一切s 有， v ( s ) = v n ，) + v ( 机 i e s k l 定义1 3 3 合作玎人对策的s h a p l e y 值是满足下面三条公理的向量函数 s h ( v ) = ( s ( v ) ，s 巩( v ) ) 公理1 ( 对称性公理) ：若对的任一排列石和每一个s 互n 有v ( 您) = v ( s ) ，则 肋。( v ) = 勋，( v ) 。 公理2 ( 有效性公理) ：对于r 的每一个支柱，既( v ) = v ( ，) 。 f e ， 公理3 ( 可加性公理) ：对于定义在的全体子集类上的任意两个特征函数v 和 w ，有s h ( v + w ) = s h ( v ) + s h ( w ) 。 5 第一章用弱优超的概念改造n t u 对簧q ，的核一l 对于合作 人对策r = i n ，矿】，s h a p l e y 值总是存在并且唯一的。它可以由公式 s b , ( v ) = 萎尘掣【v ( s ) 一v ( 刚f ) 】，j = 1 ，- 一得出。其中蚓表示联盟s 中局 中人的个数。 s h a p l e y 值是按照各局中人的贡献大小来分配支付，体现了某种程度的“公平” 与“合理”，但这种分配方式未必能为各局中人接受，因为在一般情况下，s h a p l e y 值向量不一定是分配。但是如果对策r = 【，v 】满足超加性，则s h a p l e y 值必为分配。 定义1 3 4 对策r = ，v 】的稳定集是e ( y ) 中满足以下两个条件的子集： ( 1 ) 子集中任何两个支付都没有优超关系( 内部稳定性) ； ( 2 ) 子集外的任一支付都被该子集中的某支付优超( 外部稳定性) 。 1 9 9 6 年文献 6 中首次提出合作对策中弱优超和弱稳定集的定义，并提出以弱 稳定集作为合作对策的一类新解。 定义1 3 5 设r = i n ，v 】为”人合作对策，e ( v ) 为该对策中所有分配的集合， 对于x ，y e ( v ) ，称石通过s 弱优超于y ，如果有 x 。v ( s ) ( 1 3 1 ) 工。 y ，3 s n ( 1 3 2 ) 这个定义区别于传统优超定义之处在于用条件( 1 3 2 ) 代替了 x i y ， v i s( 1 3 3 ) 显然由( 1 3 3 ) 可得到( 1 3 2 ) ，但是反之未必。在弱优超条件下，如果联盟s 在 分配x 妙之间坚持选择石，那么该联盟有可能在v ( n ) 中属于s 的一部分重新分配， 其结果是使联盟s 中的每一个成员获得较y 多的收益。弱优超概念和优超的概念一 样不适用于单人联盟和全体局中人的结盟。 定义1 3 6 称分配的集合三ce ( v ) 为对策r = ，v 1 的弱稳定集，如果 ( 1 ) 三中任何两个分配之间都没有弱优超关系( 内部稳定性) ： 6 青岛火学硕十毕业论文 ( 2 ) e ( v ) 上中的任一支付都被该子集中的某支付优超( 外部稳定性) 。 引理1 3 2 弱优超于分配y e ( v ) 的分配x 存在的充分必要条件是对某个 联盟s c n ，有y ( s ) y 5 ，即x 只，v i s 。我们把x 优超于y 记为z 专j ，。 f o 定义1 4 3 核心是v ( n ) 中不可被优超的支付之全体，记为c ( n ，v ) ，有 c ( n ，y ) = w x y ( ) ，不存在s 及y 矿( s ) 使y 专x j = y ( ) 一s 昌u i n t v ( s ) 。 对于n t u 对策，设x = ( x ix 2 ，矗) 为某可行支付，s 为某局中人的联盟。由于 各局中人用以衡量其所得( 效用) 的尺度不一定相同，因此对于联盟s 内部的成员 所拥有的各个支付分量x i 不能进行求和。 s h a p l e y 曾经引入一个“效用尺度”向量丑= ( ，如，矗) ，用以将各局中人的 效用转化成具有相同度量单位的效用。3 。这样做的结果使得各支付向量之间可以进 行比较，但是没有对同属于某集合s 的局中人的效用总和进行比较。 设k 为全体n t u 对策的集合，c k 为各局中人具相同效用尺度的n t u 对策的 全体。对于z 中的对策，局中人之间虽不能进行效用的转移，但可以考察和比较效 用总和。下面我们将通过比较属于同一联盟的局中人的效用之和的方式建立n t u 对 策中弱优超的概念，并得出相应的结论。今后如无特殊说明，本节所提到的对策均 为中的元素。 定义1 4 4 给定( ，y ) ，x ，y v ( n ) ，称x 通过联盟s 弱优超于y ( 记为 。善”y ) ，如果存在s c n 使得x y ( s ) 且t y ，。 一 f e s，e s 这个定义区别于优超的定义之处在于，使用条件一 y ，代替工3 y 3 ，使得 j e si * s 条件有所减弱。由优超可以推出弱优超，反之则未必。弱优超概念同优超概念一样 8 青岛大学硕士毕业论文 不适用于单人联盟和全体局中人的联盟。 记c ( n ，v ) 为v ( n ) 中不可被弱优超的支付之全体，即 8 ( n , v ，= 砷x y c 忉，不存在s 及v y c s ，使得善” 善一) 。 定理1 4 1 给定( n ，v ) e ，弱优超于支付向量y v ( n ) 的支付存在的充要条 件是存在s c n ，使得y ( s ) y ( s ) ，即有x 善y 。再证必要性。由于存在 s c n 及x e y ( s ) 使得。专”y ，则y ， _ y 3 ，由此得x y ， 矛盾。所以，任给j ，弓( ，矿) ，必有y c ( n ，矿) ，即己( ，矿) c 7 c ( n ，矿) 。 定理1 4 2 表明，亡( ，矿) 可作为n t u 对策的一种解，事实上是通过运用弱优超 概念对n t u 对策核，6 c ( n ，v ) 的浓缩，因而在某种意义上优化了n t u 对策的解。 定理1 4 3 给定( ，矿) ，则 讪朋川”菡i 斗州) f 善_ 妇s ) ) 证明：记川卅。u i n t 卜删，陲氟回 o 先证砸c 。任取 x e c ( n ，矿) ，若x 仨a ，则存在s c n ，使得x l 一，这与x 不被弱优超相矛盾。 下证c c ( n ，v ) 。任取x ，若x c ( n ，v ) ，则由定理1 4 1 ，存在s 。c n ， 使得一 ；( r ) 。从而x y ( ) ，而且x i n t 。矿( ) 1 t ；( 品) ，由的定义， ，e 品 【 ，e 岛 j x 硅，矛盾。 下面运用弱优超的概念建立n t u 对策的弱稳定集，并考察其与核心c ( n ，v ) 的关 系。在n t u 对策中，稳定集是v ( n ) 中满足以下两个条件的子集： ( 1 ) 子集中任何两个支付都没有优超关系( 内部稳定性) ； ( 2 ) 子集外的任一支付都被该子集中的某支付优超( 外部稳定性) 。 定义1 4 5 给定( ，v ) ，弱稳定集是v ( n ) 中满足以下两条件的子集： ( 1 ) 子集中任何两个支付都没有弱优超关系( 内部稳定性) ： ( 2 ) 子集外的任一支付都被该子集中的某支付弱优超( 外部稳定性) 。 我们知道，如果核心是合作对策的稳定集，那么它是该对策的唯一的稳定集。 这个论述对合作对策中的弱稳定集成立，对n t u 对策中的弱稳定集也同样成立。 定理1 4 5 如果核心c ( n ，v ) 是对策( _ v ，v ) 的弱稳定集，则它是唯一的弱 稳定集。 证明： 设c ( n ，v ) 是弱稳定集，z 是另一弱稳定集。因为每个支付y v ( n ) z 应被z 中某一支付弱优超，而c ( n ，矿) 是不被弱优超的支付的集合，所以 c ( n ，v ) c z 。由此可得z = c ( n ，v ) 。因为若不然，可设j ，z c ( n ，v ) ，则存在 x c ( n ，v ) 及s c n 使得x 之”y 。又因为z c ( n ，矿) c z ，这与z 的内部稳定性矛 盾。 1 0 青岛大学硕士学位论文 2 1引言 第二章具有变化联盟结构的动态合作对策 本章考察具有完全信息的有限扩展型对策。在本章中，在对策树的某些固定节 点处可能改变联盟啬分，即假设在对策进程的某些时刻联盟的结构发生变化。 令n = l ，2 ， 为全体局中人集合。子集族。= 诲，y 型，使得s ，n s 。= q ，i j 且u s ，= n ，称为的剖分。的所有剖分的集合记为。 我们通过全体局中人的联盟的不同的剖分表现联盟结构所发生的变化，假设 这样的变化发生在对策的有限个给定节点之上。每个局中人的行为以维护其所在联 盟的利益为准则，即采取使得所在联盟总收益最大的策略参与对策。以对非合作n a s h 均衡的最优反应为原则构建特征函数，在局中人对个体合理性的要求无法保障的情 况下采用n 核的方式在对策中获得其动态最优解，并给出最优解以及最优路径的算 法。 2 2 具有变化联盟结构的有限动态合作对策 定义2 2 1 根节点为，并具有有限节点的树状图k 称为对策树。 下面介绍些将要用到的符号。记工为对策树上的某一位置。用k ( x ) 表示根节 点为工的子树。z ( x ) 表示紧接在x 之后的节点集。紧接在x 之后的节点y 称为j f 的后 续( 即y z ( x ) ) 。在x 点采取行动( 选择下一位置) 的局中人记为f ( x ) 。在位置x 局 中人f ( 功的选择记为譬z ( 曲。 定义2 2 。2 具有完全信息和改变联盟剖分的展开型对策r ( x 。) 是满足以下几 条性质的对策树k ： ( 1 ) 把对策树k 的所有的节点的集合分为”+ 2 个子集只，只，只，只。只+ ：。节 点x 只，b l ，t l 称为局中人i 的个人位置；节点x 只+ ，称为机会位置，节点 x 只+ ：称为终点位置。 第二章具有变化联盟结构的动态合作对策 ( 2 ) 对每一个x ，局中人集合的剖分( x ) a 给定，使得 f ( x ) 三( y ) ，v y z ( x ) ，女果x 诺只+ 。， 1 3 y z ( x ) ：a ( x ) ( y x 如果j 只+ 1 ( 3 ) 每一个_ y z ( x ) = 移，_ y 2 ，y ，) ，x 只。可能以概率p ( m ) ，p ( y ，) 被选择， p ( y ) = 1 ， y e z ( x ) r = l z ( x ) l 。 ( 4 ) 每一个终点位置都对应一个实向量h w ) = ( ( w ) ，h a w ) ) ，w 只+ 。 ，( w ) 0 ，i = 1 ， ，其中啊( w ) # b 肿a i 在终点位置的支付。 定义2 2 3局中人i 的策略就是把每一个位置x 尸映到一个后续节点 y z ( x ) 的单映射u 。( ) 。局中人f 的全部策略记为u ，。 在此我们假设局中人j 在他的个人位置y p 为了他所属的联盟s ，利益采 取使联盟收益达到最大的策略。假设全体局中人采取的策略为u ，u ( ) 。 对策按以下方式进行。对策在只+ ，开始，联盟剖分a ( x o ) a 给定。在按 照定义2 2 2 中( 3 ) 所定义的概率分布选择后续节点墨z ( x 。) ，其中联盟剖分 ( 夏) a 已经给定。假设墨( i ) ，则在位置章。局中人j ( _ 】) 按照使他所在联盟收益 达到最大( 在初始位置只+ ，做出选择之后实现的) 的策略采取行动选择后续节 点夏= u 蝻) ( 墨) z ( 墨) 。此处假定( 牙：) s ( i ) 。如果i 2 茌只。u 只+ ：，则在位置夏 局中人f ( 夏) 按照使得他所在联盟获得最大收益的策略采取行动选择后续节点 墨= 己，睢，) ( 膏2 ) z ( i 2 ) 。如果膏：只则在位最孟2 根据定义2 2 2 中( 3 ) 所定义的 概率分布选择后续节点墨。在位置墨z ( i ：) 处联盟剖分( 五) a 与节点i 2 处的剖 分可能一致也可能不一致。如果在第女阶段，墨芒只+ 。u 只+ ：，则在位露五局中人 f ( 瓦) 按照他所属联盟的最大利益采取行动选择后续夏。；u 陬) z 瓴) 。如果在第i 阶段对策处于机会位置，即五只+ 1 则在位置五根据定义2 2 2 中( 3 ) 所定义的概 1 青岛大学硕士学位论文 率分布选择位置瓦的后续节点瓦+ 、。在选定的位置t + ，z ( 瓦) ，其联盟剖分 ( 瓦+ 。) a 已经给定，与节点瓦处的联盟剖分可能一致也可能不一致。对策在达到 终点位置w 只+ ，时结束。由于对策树是有限的，因此这一选择会在有限步之内结束。 在位置w 按照定义2 2 2 中( 4 ) 的规定局中人获得支付( ( w ) ，h 。( w ) ) 。每一个策 略组合u ( ) = ( u ，( ) ，u 。( ) ) 对应着终点位置集上的概率分布，因而局中人f 的支付 囊( w ) 是一个随机变量。策略组u ( ) = ( u 。( ) ，( ) ) 唯一地与局中人支付的期望 巨( ( ) ，u 。( ) ) = 占阮( w ) 】，i 相对应。因而我们可以把这一对策化为标准形式 ( n ；u 1 ，一，u 。；五，e 。) 。但是，对策的标准形对我们研究此类对策并不十分有用， 因为它无法考虑局中人属于不同联盟的情况和联盟结构的变化。这使得利用经典解 的概念构造这一对策的最优策略无法实现。以下我们利用对策的联盟结构在对策进 程中所产生的变化建立一种新的解的构造方法。 2 3p g n 向量的构造与算法 假设局中人f 在位置y 为了他所在联盟s ，( f s ，s e n ( x ，) ) 的最大利 益采取策略，即他尽力使s ，中局中人支付总和最大。同时，用n 核( n u c l e o l u s ) 对应的分配方式定义联盟s ，内部局中人的支付，特征函数y ( r ，x ) ，r c s 将由2 4 节给定的方法计算得出。以此为基础，本节我们提出一种构造对策r ( x o ) 的解的方法， 同时也给出相应对策树上的最优路径。对策的解的构造使用逆推法从终点位置向起 点位置计算。 先介绍r ( x 。) 的长度的概念。对策r ( x 。) 的长度是指对策树k ( x o ) 的最大路径的 长度( 即最大路径的节点数) 。设对策r ( x 。) 的长度为r + 1 ，把对策树k ( x o ) 的所有 位置的集合分为丁+ 1 个集合：托，j 1 - ，：z ，= x o ) ；其中集合置是从初始位置 经r f 步可达到的位置构成。用x t ，r = o ，1 ，t 标记置中的某个位置。 考虑x 。中的位置的集合，由于对策的长度为丁+ 1 ，则x oc 只+ ：，并且局中人 1 3 第二章具有变化联盟结构的动态合作对策 的支付已给定，等于 ( w ) ，w 。，i = 1 ，月。 第1 步，从x 。中的位罱到五x 。，如果一隹只+ u 只+ ，则在位置x 处局中人 f ( x 。) 采取行动。假设j ( 工。) 属于联盟s ，( _ ) ：s j ( x 。) a ( x ) 。其中p m ) j 是构成联盟 剖分a ( x 。) 的联盟的集合。规定每一个局中人i ( x 。) 用相同概率选择每一个满足以下 条件的后续节点w z ( x 、) ： 。m a x k 狲加嚣( i ) q 3 d f、 记瓦_ ) _ a r g 。m a 。x ，。磊予 ) ，即互“肛t 卜i 。善j y 卜羔搿k 磊予。j 。 用相同的概率选择后续节点意味着允许使用混台行为策略。文献 1 5 证明了此 构造方法，在把对策相应的联盟剖分的元素( 联盟) 看成局中人时形成唯一定义的 子博弈完美“公平”n a s h 均衡。公式( 2 3 1 ) 唯一地定义了支付的相关的值。 如果_ 只+ 。( 石。是一个机会位置) ，根据定义的规则对策进行到x z ( x 。) 的概 率为p ( x ) ，而处的支付的期望为p ( x ) h i ( x ) 。如果而只+ ：，一的支付定义为 ，( 孔) ，i = 1 ，以。根据这种算法，在某些情况下后续节点是随机选择的，所提出的 算法不能给出唯的路径，而是“枝”或子树。 类似地，我们可以把x ，中每一个位置而看成根结点构造子树。因而对每一个子 树k ( x 。) ，z 。x 。( 当一只+ ：时，这个子树只有一个点) ，所构造的“枝”的终点位 置i 在对策中是固定的，或者在z ( x 。) 上的概率分布固定( 如果公式( 2 3 1 ) 得出的 最大的点不唯一或_ 只。) 。根据局中人在子树x ( x ，) ，一肖。上的行为，我们引入 定义在x l 上的贝尔曼函数：x lj r l + ，i = l ，h 。这里1 1 是局中人i 在位置 _ x 。的期望支付，假设在子树k ( x 。) 上局中人按照以下的算法采取行动( 其中1 a l 表示集合a 中元素的个数，i n ) ： 1 4 青岛大学硕+ 学位论文 南；。鄹9 鬼( x ) ， p ( w ) 啊( w ) ， 如果x tg 只+ 2 u 只+ 如果x 。只+ 2 ( 2 3 2 ) 女口果x l 只“ 第2 步，继续向根结点递推。因为在x ：x ：运算情况较复杂，故详细讨论。先 确定局中人在位置如x 2 的行为。若x 2 只+ 2u 己+ 1 则局中人，( 屯) s j ( x 2 ) 在x 2 需 做出选择。算法规定局中人f ( 石：) 用相等的概率选择每一个满足下列条件的位置i ： 。m a x ，。毙1 ( 加，。s s ( x 2 ) 1 ( i ) 3 3 其中1 1 由式( 2 3 2 确定。磁列g 。m a x k 琵。 用相同的概率选择后续意味着允许采用混合策略。文献 1 5 证明了在子对策中 当把相应的联盟剖分的元素( 联盟) 看成一个局中人时所构造的策略形成唯一定义 的子博弈完全“公平”n a s h 均衡。 如果x 2 只“( x 2 是一个机会位置) ，由于a ( x 2 ) 可能与a ( x 1 ) ，x l z ( x 2 ) 不一 致，在x ：位置我们得不到确定的局中人支付。为了定义函数2 ( x ：) 在位置x ：( 子树 k ( x ：) 中“枝”的根节点) 的值，我们应该从联盟支付中得出局中人的支付，即对 乜( 孔) 警“中的每一个联盟的联盟收益定义一个分配规则。这个分配规则可以借助 联盟剖分 ) x x 、中每一个元素对应的特征函数得到确定，此特征函数的构造将 在2 4 节给出。现在假设特征函数v ( 工，r ( s 。( x ) ) ，r s k ( x ) ，s 。( a ( x ) ， k = l ，| ( 工) 给定。选择任意一个联盟s k ( 一) a ( x 。) ，考虑合作慨( 一) f 人对策 g ( x 。，s 。( x 。) ) ，其特征函数为v ( x ，r ( 墨( 一) ) ) ，rc 7 s ( ) 。合作对策g ( x ，s 女( 一) ) 中 大联盟研( _ ) 的特征函数值等于： v ( 五，& ( 而) ) = 1 ( 而) ( 2 3 4 ) i e 黾( 而) 对母( 而) 等。“中的每一个联盟墨( _ ) 计算对策g ( x 。，s a x 。) ) 的n 核，其分量为 1 5 第二章具有变化联盟结构的动态合作对策 n u ，( 瓯( 一) ) ，i s k ( 一) ，并且n u ，( 瓯( x ，) ) = v ( x 。s ；( _ ) ) 。用n 核作为总联盟支付 ，e s k ( j 1 ) v ( x ，瓯( 一) ) 的一个分配方案，并用相同的方法找到 a ( x ) 、s 。( x ) 中其它联盟对应 的分配方案。定义向量 p g n ( x 1 ) = ( p g n i ( x 1 ) ，p g n ( x 1 ) ) ( 2 3 5 ) 其中p g n , ( x 。) = 肋，( ( 一) ) ，i s 。( 一) ，再用p g n ，( x ) 定义在x ：只+ 。位置局中人 1 ，n 的支付。 如果x 2 只+ 2 ，局中人在x 2 的支付等于曩( x 2 ) ，i = 1 ，h 。 在x 2 上定义函数2 ：x 2 斗垦+ ，i n ( 也) = 际1 习；。荔拶i - 髁彬鲰：呱， h t ( x 2 ) p ( x 。) p g n j ( x ，) 而e z ( 如1 如果x 2e 只+ 2 ( 2 3 6 ) 如果x 2 只“ 其中p ( x 。) 为选择后续节点z l 的概率，1 ( i ) 由( 2 3 2 ) 得出，p g n i ( x 。) ，i n 由 ( 2 3 5 ) 给出。至此得出每一个子树k ( x ：) 的“枝”。 以后的步骤与第1 步和第2 步相似。现在考虑第t 步，设x t x ，。标记函数 。1 ：置。j r ? ，i n ，它确定了局中人i n 在按照所提出的算法经历了位置 x f j ， 也( x 3 9