（应用数学专业论文）图上的动态对策中两类合作最优准则及其性质研究.pdf

a b s t r a c t l i l ll l ii l l li ii iul li ii y 17 3 4 0 0 2 i nt h i sp a p e r , w em a i n l yr e s e a r c hg a m e so nt r e ea n dg a m e so ng r a p hw i t hc o o p e r a t i v e a t t r i b u t e g i v e nt h el i n k b a s e dv a l u ea l l o c a t i o np r i n c i p l e ，w er e s e a r c ht h ev a l u eo fe a c ha r co n g r a p h ，a n dc o m p a r et h e a l l o c a t i o nv e c t o rb a s e do na r c sa n dt h es h a p l e yv e c t o r t h e nw es t u d yt h e c h o i c eo ft h ep l a y e r sb e t w e e nt h es t r a t e g i e sc o o p e r a t i o na n dc o u n t e r p l o ti ng a m e so ng r a p h i nt h ef i r s tc h a p t e r ，w eg i v et h em o d e l so fg a m e so nt r e ea n dg r a p hw i t hc o m p l e t e i n f o r m a t i o na n dc o o p e r a t i v ea t t r i b u t e 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 ep a r t 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 si nt h eg i v e n c o a l i t i o nk e e pc 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 s 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 i e st r yt og e tm a x i m a l p 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 es u mo ft h e i rp a y o f f sf i r s t l y , a n d t h e nt h ea l l o c a t i o no 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 ec o n s i d e r e d i nt h i sc h a p t e r ，w e i n t r u d u c et h ea l g o r i t h mo fc h a r a c t e rf u n c t i o n ，w h i c hi sa l s ot h eb a s i so fc a l c u l a t i n gt h ec h a r a c t e r f u n c t i o na n dl o o k i n gf o rt h eo p t i m a lp a t hi nc o m p l e t e d c o o p e r a t i o na n dp a r t i a l - c o o p e r a t i o n g a m e so ng r a p h i nt h es e c o n dc h a p t e r ，w ee s t a b l i s ha n dr e s e a r c ht h el i n k - b a s e dv a l u ea l l o c a t i o np r i n c i p l ei n d i s c r e t ed y n a m i cc o o p e r a t i v eg a m e ，f r o mt h es t a n d p o i n to ft h ef u n c t i o no ft h el i n k si ng a m e so n t r e ea n dg r a p h a c c o r d i n gt ot h ee f f e c to ft h ep r i n c i p l ea b o v e ，w ec a nj u d g et h es y s t e r m sw i t h s h a p eo ft r e eo rc o n n e c t e dg r a p ho rn e ti nt e r m so fs e c u r i t y f r o ma ne x a m p l e ，w ec a l c u l a t et h e k e ya r c s ，c h a r a c t e rf u n c t i o na n dt h es h a p l e yv e c t o r i nt h et h i r dc h a p t e r , ak i n do fn e wg a m ei ss t u d i d ，w h i c hi sd i f f e r e n tf r o mg e n e r a lg a m eo n t r e ew i t hc o m p l e t ei n f o r m a t i o n i t sm a i nc h a r a c t e ri st h a te a c hp l a y e rw o u l dd e c l a r ew e a t h e rh e c h o o s et oc o o p e r a t eo rt oa c ti n d e p e n d e n t l y , s ow h e a t h e rt oc o o p e r a t eo rn o tw i l lb ea ne l e m e n to f p l a y e r s s t r a t e g i e s t h i sc h a p t e rs h o wc o m p l e t e l yt h ec o n s t r u c t i o no fo p t i m a lp a t hi ng a m e o nt r e e w i t hs i m p l ec o a l i t i o ns t r u c t u r e ，a sw e l la st h ea l g o r i t h mo fp g nv e c t o rf o rt h i sg a m e k e yw o r d s ：c o a l i t i o n a lp a r t i t i o n ；g a m e so ng r a p h ；l b v a ；p g n - v e c t o r ；n a s he q u i l i b r i u m 弓r 言”l 第一章扩展型对策与图上对策3 1 1 扩展型对策3 1 1 1 扩展型完全合作对策3 1 1 2 扩展型合作对策中特征函数的算法4 1 2 联盟剖分型对策6 1 3 图上对策7 1 3 1 图上的完全合作对策8 1 3 2 图上的部分合作对策9 第二章图上动态合作对策中基于连接价值的最优准则1 2 2 1 符号、定义及模型1 2 2 2 基于连接价值的分配准则1 5 2 3 计算示例”1 7 第三章合作与对抗成为策略要素的扩展型动态对策及其p g n 向量3 0 3 1 符号和定义3 0 3 2 最优路径的构造与算法3 1 3 3 计算示例3 4 结论”3 8 参考文献3 9 攻读学位期间的研究成果“4 2 致谢4 3 学位论文独创性声明4 4 学位论文知识产权权属声明4 4 一一 引言 引言 图上对策一般形式的定义是由b e r g ec 给出的，而有限树上的对策( z e m e l o e 。1 9 6 1 ) 为一种结构简单的图，是图上对策最初的类型，主要用于描述动态对策进 程，因此图上对策的研究结果一般都可以直接推广到动态对策的范畴。 事实上，图上对策的研究结果在各类具有多个不同利益主体的网络中显现出了 重要的实际应用价值。当今世界，互联网、移动通讯网络已经几乎成为全部信息的 载体，如何协调网络中冲突各方的利益并且充分发挥其最大效率是管理科学必须解 决的问题。同时，将机制设计理论应用于图上对策分析，建立和完善复杂网络系统 内部的激励体系，从而设计并促进网络成员参与创新合作，对管理决策的科学化无 疑具有重要的现实意义。 在动念的冲突控制过程中选择最佳的合作类型以及具体合作类型之下的最优合 作方式也许永远都是对策参与者所期待的，但是在经典的对策模型中并没有给局中 人提供选择对局的可能。如果对过去所谓的完全信息的概念加以推广，使得局中人 可以预见到所有可能出现的对局( 对策) 以及每个对局之下自己的以及其他局中人 的支付结果，再通过设定对局与对局之间结果的优劣比较原则( 例如，可以参照经 典的静态合作对策中分配之间的优超关系) ，那么在某种意义之下，一些可以接受的 对局结果所对应的对局( 对策) 就是最优的事实上，我们似乎在考虑一种抽象对策， 即通过借鉴经典的静态对策中的合作及非合作最优准则( 如纳什均衡以及作为合作 对策中所有分配集合子集的核心、稳定集等) 的思维方式，类似地在所有对局的集 合中寻求它的某个子集，即特定意义下的最优对策。称上述过程为抽象的对策，因 为它不是通常意义下的对策，因为我们似乎看不到具体的局中人以及局中人为了实 现最优对策所采取的策略( 但这一点与经典的静态合作对策何其相似) 。如果限定每 个具体的对局是本文所考察的图上对策( 我们将称之抽象对策的元素) ，那么近年来 已经逐渐成为研究热点的网络对策的出现就成为十分自然的结果。 网络安全问题在当今世界的各个层面上已经得到越来越多的重视，网络中的连 接和结点是通常易受攻击的两大部分乜1 。在具体的网络中每条连接每个结点可能扮 演不同的角色，它们所发挥的作用以及产生的效率因而差异巨大口1 。同样的情形也 出现在动态决策支持系统中，决策通路的中断或者决策结点功能的丧失对于动态决 策的结果以及决策系统的工作效率将带来显而易见的影响。 在完全合作的动态对策的情形下( 即对策规则中约定局中人将为所属联盟的最 大和支付而采取简单策略) ，通过评估局中人的贡献并以此为依据在局中人之间分 配价值，例如，众所周知的s h a p l e y 值分配规则为在局中人之间分配对策的值提供 了一个很自然地方式。类似的，在扩展型动态对策( 树) 以及图上动态对策中，通 青岛人学硕十学位论文 过量化每条给定弧的贡献将帮助我们建立新的合作最优准则。 根据局中人参与合作或者独自行动等具体的行为方式，一直以来对策论被划分 为合作对策或者非合作对策，相应的结果则有合作对策的解( 如核心、沙甫利向量、 稳定集等) 以及非合作均衡( 如纳什均衡以及它的各种推广) 等。这样的划分使得 管理系统决策者常常觉得无所适从，首先因为管理系统不可能严格地以合作或者非 合作的形式出现，其次系统中参与者选择合作或是对抗、选择什么时候与其他参与 者合作或是对抗、( 多参与者系统中) 选择与哪些参与者合作或是对抗应该以决策者 的策略要素的形式出现。上述选择甚至包括上述选择的组合无法出现在决策者的策 略要素中是对策理论不能更有效地帮助决策者做出决策的主要原因之一。 针对上述问题本文考察一类新的对策模型，这个对策不同于具有完美信息的一 般有限扩展型对策( 但是此类对策通常依托于某个具体的一般有限扩展型对策) ，这 里每个局中人在进行决策之前通过宣称他将合作还是采取单独行动来告知其他局中 人，决定合作还是不合作将成为局中人策略的一个元素。在对策进程中，希望合作 的局中人从他宣称此意图那一时刻起开始合作并加入联盟内部。给定局中人集合为 的具有完美信息的有限扩展型对策的对策树为g ，如果在对策树g 的某一节点处 局中人，( f n ) 决定合作，则在此节点处联盟将由那些最初宣称合作的局中人和 在此节点处宣称合作的局中人组成。在这篇文章中我们将考虑局中人一旦加入联盟 后就不再离开直至对策结束的情形，因此联盟内局中人的数目是单调不减的。如果 局中人宣称在对策的某个阶段进行合作并且在此以前没有联盟形成，那么他将采取 单独行动直至出现其他的局中人宣称合作，在此之后进入联盟的局中人采取行动的 原则是维护该联盟的利益。 2 第一章扩展型对策与图上对策 第一章扩展型对策与图上对策 本章针对扩展型对策以及图上对策尝试在合作情形下以统一的观点来研究动态 对策过程，即不仅包含最大化自己支付的个体理性行为和完全合作行为，还要考虑 到各种程度的合作的可能，以及这种合作程度根据对策进程所产生的变化。此时则 有了对不同合作程度的效果、持久性和对于在冲突过程当前阶段的状态的依赖性进 行量化评估的可能。 1 1 扩展型对策 1 1 1 扩展型完全合作对策 考察有限树上具有完全信息的对策r 。假设局中人f 沿着某个具体路径 牙= ( 磊，乏，乏) ( 其中乏是终端结点) 完成对策之后将获得这个路径终点乏处预 先给定的支付忍( 亏) ( 终端支付) 。 以上述非合作对策r 为基础，如果再附加上所谓的合作假设，即对策规则中约 定局中人将为所属联盟的最大和支付而采取策略，而特征函数v ( s ) ，sc 7 n 可以按公 理化方式引入或者视为联盟s 与s 之间所进行的零和对策的值，它满足超可加性 条件，即对于s lcn ，s 2cn ，sn 是= a ，有 ，( su 曼) v ( s ) + v ( 是) ，f 4v ( f 乃) = 0 卜( 1 ) 则对策i 转化为扩展型完全合作对策，记为r 。 此时，在对策r ，中我们已经可以如同经典( 静态) 合作对策中那样定义分配集 厶 口 e = 忙( 甜窆专叫n i z l比圳 f ) = 1 ，棚)lj 核心c c e ， c = 仁c “善毒圳s ，, s c n c e l，e s 亦可以定义稳定集，s h a p l e y 向量以及其他经典合作对策中的最优准则。 需要指出的是，在扩展型完全合作对策的进程中处于某个联盟中的局中人在策 3 青岛人学硕十学位论文 略选择上需要兼顾其所在联盟的集体理性和局中人自身的个体理性，但是局中人在 上述两者之间将首选集体理性，然后按对策开始f j 某个预先约定的合作最优准则( 比 如s h a p l e y 向量) 通过对联盟收益的再分配实现其个体理性。 假设局中人协商选择能够最大化局中人支付总和的策略组合 万( ) = ( 瓦( ) ，瓦( ) ) ，并且由局势万( ) 所实现的路径( 轨迹) 是三= ( 磊，乏) ，则根据 万( ) 的定义，有 9 畸忽( z ，) = 曩( 乏) = v ( ) 卜( 2 ) ”1 ，- li = 1 我们称万为完全合作对策r ，的最优轨迹，局中人为了实现最优轨迹而采取的策略称 为最优合作策略。当然，对策中可能出现若干“最优轨迹 ，其中每个均给出相同的 最大和支付。局中人在采用最优合作策略完成对策进程之后，再依照对策开始之前 约定选择的最优准则对y ( ) 进行分配，从而获得自己最终的合作支付。 1 1 2扩展型合作对策中特征函数的算法 为了给出对策r 。中特征函数v ( s ) ，scn 程序化的算法，首先给出一些符号和定 义。 设r ( 五) 为一个具有完全信息的有限扩展型，z 人对策，n = 1 ，卅) 为全体局中人 集合，k ( 五) 表示以j c l 为初始结点的对策树。其结点集合的剖分为墨，只，+ ，局 中人i 的顺序集合记为只( f n ) ，终端结点集合记为+ 。用f ( 功表示在结点x 处决 策的局中人。局中人f 的支付由终端结点处的实值函数磅：匕。专r i , f n 给定。对策 r ( 而) 的长度，+ l 是指对策树k ( 而) 最长路径的长度，即最长路径所包含的结点个数。 称从对策树k ( x t ) 的初始结点出发通过，一t 步所能达到的结点处于对策r ( 五) 的第f 阶段，把这些结点的集合记为z ，= 0 ，1 ，。 定义1 1 1 设= l ，刀 为对策r ，( 葺) 中全体局中人集合，sc n 为局中人 联盟，所有联盟的集合记为p ( 忉。对策r ，( 五) 的特征函数是定义在p ( ) 上的实函 数1 ，其中v ( s ) 表示联盟s 通过协调其成员的策略所能保证得到的最大赢得，规定 v ( a ) = 0 。 考察对策r ，( 而) ，并假定其长度为l + 1 。现在针对某个给定的联盟s cn 给出 4 第一章扩展型对策与图上对策 扩展型完全合作对策的特征函数v ( s ) 的逆推算法。 起始阶段 设妒为t = 0 阶段的任意结点，即x o x 。c 只+ 。( 为简化符号使用起 醒( x 。) - - e h , ( x 。) 则o ( x o ) 表示联盟s 在结点妒处的支付总和。首先计算出对策树k ( _ ) 上在，- o 阶 段所有结点处的继( x 。) ，并记m ；= 聊；( 坼) ) “。扎。 第1 阶段从结点p 逆推至f 二1 阶段的结点x ，并记 剥：矗 “3 ， 这里，若f ( x 1 ) s ，则i ( x 1 ) 采取使联盟s 支付总和最大化的行为，即 x o a r g m a x m o ( x k ) ；若i ( 一) 诺s ，贝, l j i ( x 1 ) 采取使联盟s 支付总和最小化的行为，即 妒驾璺m i n 。碟( 磁) 。计算出该阶段所有结点处的所；( x 1 ) ，记作m ；= 研；( _ ) ) 以。丑。 埔( ) e 肘； “”一。 第f 阶段上述过程类似进行，并选取第f 阶段为代表。记 ，蝶( x ，) ： m t - 曩, 、( - 习一三三乏 一c 4 ， 若f ( x f ) s ， 则f ( ) 采取使联盟s 支付总和最大化的行为， 即 一1 a r gm a x l - 1 ( 讫) ；若f ( x 7 ) 仨s ，则f ( 一) 采取使联盟s 支付总和最小化的行为， ，略1 ( ) m f 、 7 即一- 1 a r g r a i n t - 1 ( 矗) 。计算出该阶段的所有结点处的m ；( ) ，记作 哄。1 ( 如) e m ；- 1 磁2 以( ) k 以。 需要指出的是，上述计算过程中可能遇到i a r g m a x m s ( x 。) l 1 ( 或 5 青岛火学硕+ 学位论文 l a r g m i n m ；( 屯) l 1 ) 的情况，此时在a 唱m a x 以( 坼) ( 或a r g m i n m s ( x k ) ) 中任取一结 点将不会对结果产生影响。最终，在对策树k ( 五) 的初始结点五处得到联盟s 的特征 函数值 v ( s ) = i n ：( x 7 ) 卜( 5 ) 这里结点一即为对策树k ( 五) 的初始结点而。 1 2联盟剖分型对策 联盟剖分型对策思想最初较为规范的表述源白a r n o l d 和w o o d e r s 的工作h 1 。局 中人在对策进程中联合并结成联盟，这些联盟构成全体局中人集合的剖分，本节把 这些联盟称作联盟一局中人。此时联盟一局中人如同个体理性的局中人采取行动，而 假定在给定联盟的内部局中人保持完全合作，称这样的对策为联盟剖分型对策。 联盟一局中人之间合作与对抗的可能性使得联盟之间以及联盟内部的局中人之 间的支付分配问题变得复杂，在对策进程中局中人的基本行为准则是根据最大化他 们所在联盟的支付而选择行动。 在沿用前面定义和符号的基础上，再给定以为初始结点的对策树k ( x o ) ，并 且用x 表示k ( x o ) 的某个结点，k ( z ) 表示k ( ) 上以x 为初始结点的子树，z ( 功表示 x 的直接后续结点集合，x 的直接后续结点y ( y z ( 功) 称为局中人f ( 功在x 处的 选择。在每一个终端结点we 只+ 。处给定”维实值向量办( w ) = ( ( 川，( w ) ) ， w e + 。，其中如( w ) ，i = l ，刀表示局中人f 在终端结点处的支付。用r ( x o ) 表示在 k ( x o ) d 的扩展型非合作对策。 定义1 2 1把每个决策结点x p 映到其唯一的直接脒- a d a y ez ( x ) 的映射 ( ) 称为局中人f 的策略，其策略集合用来表示。 根据以上定义，第i 个局中人的策略在其顺序集合p 中的任意结点x 处确定他对 于下一个结点的唯一选择。这样，每个局势甜= ( z f ，) ，v 唯一确定了对策树 k ( 而) 上从初始结点开始并到达某个终端结点的路径，称为局。每个局唯一确定 6 第一章扩展型对策与图上对策 了所抵达的终端结点w ，反之，终端结点w 也唯一确定了局。在终端结点w 处，每 个局中人f ，i = l ，刀得到支付曩( w ) 。 对策r ( x o ) 中局势”= ( ，) ，v 之下局中人i 的支付函数的值等于局势甜 所确定的局的终端结点w 处的支付忽( w ) 的值，即 k ( ，。) = 曩( w ) ，i = 1 ，r l 定义1 2 2 设a = s ，瓯) 为局中人集合的剖分，这里m n ， s , n s , 2 a ，且葛i 2 。称中每个元素墨为一个联盟一局中人，他的策略集合 为2 ，基。局势材唯一确定了对策树k ( ) 上以w 为终端结点的某个局，其中 甜= ( ，) ，u s , ，j = l ，m 在局势z ，之下联盟一局中人最的支付等于局势甜所确定的局的终端结点w 处联盟 最中局中人的支付总和，即 磷( ，& ) = 曩( w ) ，k = l ，棚 i t 假定在联盟瓯的内部局中人保持完全合作，所得到的对策模型称为具有固定联盟剖 分的扩展型对策，并记作f ( a ，x o ) 。对策i ( ，) 的进程依然是在原有的对策树k ( x o ) 之上并由r ( x o ) 的局中人顺次决策，所不同的是，这里局中人f 最将首先以最大化 其所在联盟s 的支付的原则而选择行动，最终形成联盟一局中人的均衡策略。 1 3 图上对策 图上对策一般形式的定义是由c b e r g e 给出的。在预先给定图上对策局中人策 略集合的前提下，图上的状态结点可能表现为有序的。我们通过在有限连通图上每 个状态结点处引入状态支付向量，并且运用c b e r g e 建立的图上对策中简单策略的 概念，研究图上动态对策。对策树是一种结构简单的图，主要用于描述动态对策进 程，因此图上对策的研究结果可以直接推广到动态对策的范畴。我们约定，图上的 任一状态结点均可作为初始状态，而一个可以用对策树表述的有限动态对策进程则 7 重璺| 人堂堡主堂堡笙奎 通常具有唯一的初始状态。 1 3 1图上的完全合作对策 给定具有状态支付向量的有向图 ，并假定任意局中人f 的策略类型为简 单策略，记局中人f 的策略集合为s ，且对策中局中人的策略集合一旦给定便不再发 生变化。记丁= ，这里4 是图t 的终端状态集合，正是图 上口处的状态支付向量。如果选定a o a 为初始状态，则得到具有状态支付 向量的图t 上的非合作简单对策1 1 ( 丁) 。在非合作对策的基础上再附加上所谓的合 作假设，即对策规则中约定局中人将为所属联盟的最大和支付而采取( 简单) 策略， 则对策r 唧( t ) 转化为图r 上以为初始状态的完全合作简单对策，记为g v ( t ，) 。 “简单 的含义是指局中人采用前面所说的简单策略，而，表示特征函数，即联盟 通过协调其成员的策略所能保证得到的最大支付，规定“o ) = 0 。此外，我们注意 到，选择不同的初始状态将导致不同的合作对策。 注意到，具有状态支付向量的有向状态图t = 给定了局 中人，( i n ) 的简单策略集合s j 当a o a 为初始状态时，简单策略下的局势 ( s i9 9 霸) s i 最将确定一个局 = 口0 ，s ( ) ，s 2 ( ) ， 这里s = 岛u u 。 以为初始状态的有向图丁按如下方式转换为以为根的对策树k ( a o ) 。每个 可能出现的局对应于对策树k ( a o ) 上的某个路径，具体地，有向图t 上r h 初始状态嘞 出发的局对应于对策树k ( a o ) 上从口。出发的路径，且路径，的结点与有向图t 上的 状态相对应并保持相同的顺序关系，路径，的终端结点处的支付向量 = ( 啊，) 为 对应的局支付向量。同样需要指出的是，不同的简单策略下的局势可能导致相同的 局，不过这并不影响合作对策特征函数值的计算。 因为在具有状态支付向量的图上对策中，局支付是通过状态支付的累加( 或加 r 第一章扩展型对策与图上对策 权) 的方式实现的，因此在有向图上的任一状态可以作为初始状态的前提下，选择 不同的初始状态所建立的合作简单对策中大联盟的特征函数值y ( ) 以及s h a p l e y 向 量均不同( 如果图上每个状态结点处的状态支付向量均非负，那么1 ，( ) 将具有递增 性) ，这个事实可能作为完全合作背景下选择“最优 初始状态的依据。 事实上，综和关于扩展型合作对策特征函数的算法以及针对图上对策所采用的 按状态结点的级递推的方法，可以得出图上的完全合作简单对策特征函数的算法， 并且算法不受图上的任意状态可作为初始状态这一最初假设的限制。 需要指出的是，该特征函数的算法使得在完全合作背景下的图上对策中有必要 做出“最优 初始状态的选择，因为即使选择同级状态作为初始状态的情况下局中 人的共同收益仍可能出现差别。 1 3 2 图上的部分合作对策 本节通过在有向图上的状态结点处定义合作函数，运用c b e r g e 的关于图上对 策中策略的概念，在有向图上考察部分合作动态对策。局中人在对策进程中将采取 部分合作而不是完全合作，部分合作的主要特点是每个局中人的行为是合作与单独 行动的组合。这里合作函数的设定允许局中人加入某个联盟之后由于某种原因再脱 离该联盟而选择单独行动，即联盟剖分是可以变化的。 定义1 3 1 称图 上终端状态w a ，处的实值向量 万( w ) = ( 瓦( w ) ，瓦( 们) 为终端支付向量，其中j ；( w ) 为局中人f ( f n ) 在w 处的终端 状态支付。 在以为初始状态的具有终端支付的有向图丁中引入合作函数f = ( 石，以) ， 在图上对策的进程中局中人可能选择合作也可能是单独行动，变换后的对策称为有 向图丁上具有终端支付的部分合作对策，记为r ，( 丁，嘞) 。需要指出的是，扩展型动 态对策中合作函数可以确定对策树上每个结点处特定简单联盟结构，与之不同的是， 图上对策中沿着不同的路径抵达同一状态处所形成的简单联盟结构可能是完全不同 的，这是有向图上的部分合作对策所特有的。 定义1 3 2给定以为初始状态的有向图丁上的合作函数厂，假设对策沿路 径d o ，a 进行到局中人f 的某个状态a ，联盟 砖( a o 90 9 口) = ，i 口，是路径 ，口 上到口最近的a j 中的点且乃( 口) = 1 9 青岛人学硕十学位论文 称为部分合作对策r ，( 丁，a o ) 中的动态联盟。 动态联盟影( 口。，d ) 由在口处正在采取合作行为与之前已经采取合作行为并且 对策沿着路径，口进行到状态口时尚未脱离所在联盟的局中人组成。定义1 3 2 说明，沿着路径，口在状态口处动态联盟量( 嘞，口) 形成之后，它所包含的局中 人仍然可以脱离该联盟，n s ( a o ，口) 中的局中人被认为沿着该路径在状态口处单 独行动，因此合作函数厂能确定沿着路径，口对策进行到状态口处的简单联盟结 构 s ( a o ，础，蜘，刮 ) 任取一状态口，设口4 ，记 ，垆 趴万以荔粥 在对策r _ 厂( 丁，a o ) 中，联盟q ( a o ，口) 被认为是在状态口处作决策的一个局中人， 由于( a o ，口) 与路径有关，所以，在状态日处作决策的局中人可能为数众多。然而 对策r ，( 丁，a o ) 中局中人集合最多可能由集合中的所有子集组成。f s ( 丁，a o ) 中某 个联盟( 或局中人) s 沿着 a o ，w 的支付定义为图t 的终端状态w 处联盟s 中局 中人的支付总和，即 k s ( a o ，) = 瓦( w ) ，w e4 j s 如果口是局中人，的一个状态( 即ae 4 ) ，则合作函数厂= ( 石，五) 确定了规则 啪，= 墨嬲曼 为求得有向图丁上部分合作对策r ( 丁，a o ) 的值，可以先将图t 转化为相应的对 策树，再针对所获得的扩展型部分合作对策进行求解。当选定某个状态口为初始状 l o 第一章扩展型对策与图上对策 态时，可以将有向图丁转换为以状态a 为根的对策树k ( 口) 。这里取消了部分合作对 策进程中联盟s ，( ) 单调递增的限制，允许局中人加入某个联盟后由于某种原因再脱 离该联盟而选择采取单独行动。采用将结点剖分并在对策树上进行逆推的方法可得 到有向图丁上的部分合作对策r ，( 丁，a o ) 的最优路径和对策的值。 本节所描述的联盟在形成过程中，局中人可以加入某个联盟或者根据需要选择 退出该联盟，这样的合作结构的变化可能是局中人主动采取的，也可能是受到来自 系统之外的干预，或者有时可能仅仅是随机发生的，也有可能是几种因素共同作用 的结果。之前发生的中国电信业的重组，就是由管理层决策实施并考虑到电信企业 本身发展的意愿，它的发生可以归纳为前两个原因共同作用的结果。而微软并购雅 虎计划案则可以看作是局中人主动寻求合作结构变化的典型例子。 对于图上对策，可以通过改变其合作函数厂而得到图丁上定义的所有可能的部 分合作对策r ，( 丁，) 组成的类r f ( 丁，) 。以此对策类作为研究对象，如果比较部分合作 对策r ，( 丁，) r f ( 丁，) 的值，可能得到“最优”的部分合作对策吗? 不过也许可以尝 试从另外一个完全不同的角度看待这个问题。 青岛人学硕+ 学位论文 第二章图上动态合作对策中基于连接价值的最优准则 本章将从扩展型动态对策( 树) 以及图上动态对策中连接( 通常称为弧) 功能 的角度出发，建立并研究离散动态合作对策中基于连接地位的最优准则，根据上述 最优准则发生作用的效果从安全可靠性方面评估树状决策系统、连通图型以及网格 状系统的优劣。 2 1 符号、定义及模型 定义局中人的集合为= 1 ，2 ，玎) ，记具有顶点集合彳和弧集7 ( 又称连接集合) 的连通图为g 。，这里y a 2 ，状态( 顶点) 集合为a = a o ，o l ， 。记4 为局中人f n 的状态集合，局中人的决策结点集合记为彳= 4 ，4 。7 是状态口的直接后 续的状态集合，彳，是没有后续状态的终端状态集合，若口，6 a ， a , b ) 表示一条由口 指向b 的有向弧。若状态结点a 4 ，而6 7 7 ，那么称弧 d ，b ) 为属于局中人f 的弧。针对序数口用归纳法按如下方式定义状态集合的子集巴冬a ：a ) c o = 4 ； b ) 设对于所有的 0 ，则称弧 口，b 是对策g ( g ) 的关键弧；如果p ( g ， 口，6 ) = 0 ， 1 3 ，r r jr- l rr r a 4 r、r ( a ) g o 图2 1 ，rr r1 r l r a 4 r1 r 6 l如 ( b ) 蜀 6 正 ，局 图g o 运用上面定义的符号，有蜀= g o 一 a 3 ，口4 。根据动态合作对策中大联盟的特 征函数值的算法n 1 ，可以得到p ( g o ) = v ( ig o ) = 5 8 ，而p ( g 。) = v ( l9 1 ) = 5 1 。弧 口3 ，0 4 ) 对于g ( 铂) 的边际贡献 a a ( g o ， 口3 ，吼) ) = p ( g o ) 一p ( 岛- a 3 ，口。 ) = 5 8 - 5 1 = 7 o 由定义4 ，弧 吩，0 4 ) 是对策g ( 岛) 的关键弧，边际贡献表示出由于状态图结构的变化 对于大联盟的收益的影响。 1 4 一- - - 第二二章图上动态合作对策中基于连接地位的最优准则 2 2 基于连接价值的分配准则 记具有状态支付的有限连通图g o 上的连接数目为l 岛i ，不妨设连接集合 y ( g o ) 2t q ，哆j ， a 3 ，a 4 ，。，t 口2 计l ，a 2 1 9 0 i j j 其中某些结点可能为相同结点。 定义2 2 1 称j 岛i 维向量x = ( _ 口i 口2 ，x l a 2 | w o f - , , 【j ) 为图g o 上的动态合作对策 g ( g 。) 的一个连接分配，如果t 勺以。 o ，并且t 乃舢， = ( g 。) 。 定义2 2 2 称函数妒：r ( g o ) - - - r 1 9 0 i 为对策g ( g 。) 中相对于的连接价值函数， 这里 撕( 刚) = 硒t ( g o ) 拈赢一k 6 ) ) 刊g ，) ) 学 其中l g o l 和l g 1 分别表示具有状态支付的图g o 和g 中连接的个数。 定理2 2 1 锻咖 ( g o ，t t ) = t ( g o ) 证明 给定具有状态支付的有限连通图g o 上连接集合的一种排序，例如定义 2 2 1 中那样。那么合作对策g ( g o ) 的另一种支付的分配方式可以是，将具有状态支 4 , - t 的图的总收益分配给连接，即对于第一个连接，记 2 矧( p ( 岛) 一p ( 岛一 帆 ) ) = 怒( “啦m a 妊x 舒础- - m 岍m a x ( g ，_ h 呸) ) ) = 锱( h 啦m a x m 叫a x 鲫( 咿一h 黩础啦m a x 例( v ( m ”) ) ) 锱m 刚i n i 帆m 幽a x ，一m 毗a x ，( v ( m ”) - - h 心m m a x c ( g m a x 删( v ( i g ”) ) ) 0 对于第二个连接，有 2 锱 应( 9 0 一m 帅( 岛一，吼) ) 霄岛人字坝十字倪论又 以此类推，对于最后一个连接有 k ，川 = 矧：蚓- - ，川帅( g 手) 容易验证 1 q 肌。) = ( 岛) ，并且不失一般性可以证明气q 羁+ ，) o ，所以x 为 g ( g 。) 的一个连接分配。 如果对于连接集合重新排序，例如将连接 哆l 孙卜。，呸i g o i ， q ，口z 依次重新标号 为 口l ，哆) ， g o l - i 哆1 9 0 i l ，则按照上述的方法将得到一个新的连接分配： ，= 锱 酬一p ( 岛一 , 0 1 - 1 9 0 1 ) “r 烈眺q ，口2 ) ) 一a ( g o e ) l , - l g o 工一，i 一p ( 岛) l ”“2 7 对于连接集合的其他编号次序，也可以按照这种方法得到相应的连接分配。由于l g o i 条弧的不同编号次序有k 。l ! 种，因此这样的分配也有陪。i ! 个。作为对每条连接“平 均 贡献的衡量，取l g 。i ! 个连接分配的平均值得到： 一 胁) 2 研1 矧( g 眇训一啦脚矗) 2 加) 其中 口f ，q + 1 ) 口：b i _ l ，口2 i g o i ， q ，呸) ) 。 显然。e 、纹q m l ( g o ，) = ( g o ) ，且缎q 靠。) (