（应用数学专业论文）具有不完全合作属性的复合型网络对策研究.pdf

a b s t r a c t i nt h i sp a p e r ，w es t u d yn e t w o r kf o r m a t i o ng a m e s f l o wa n dm i x e d f l o wn e t w o r kf o r m a t i o ng a m e b & g f u n c t i o no ft h ea g e n t s as y s t e m a t i cs t u d yo nt h ee x i s t e n c eo fn a s hn e t w o r k sa n dt h e c h a r a c t e r i s t i c so fn e t w o r k si sd o n ef o rv a r i e t i e so fn e t w o r kf o r m a t i o ng a m e s ，w i t ha s i t u a t i o no fn o n c o o p e r a t i o n ，i n c o m p l e t ec 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 t h eb a s i ck n o w l e d g ea n dc o n c e p to fo n e - w a yf l o wn e t w o r kf o r m a t i o ng a m ei s i n t r o d u c e di nc h a p t e r1 w ec o n s i d e ro n e - w a yf l o wn e t w o r kf o r m a t i o ng a m ew i t hf i x e d c o a l i t i o np a r t i t i o nb yd e f i n i n gc o a l i t i o n h o m o g e n e o u sc o s t s t h en e t w o r ki sf o r m e db y a g e n t sp l a y i n gl o c a lm o v e m e n t t h er u l eo ft h em o v e m e n ti sm a x i m i z i n gt h ep a y o f fo f t h ew h o l ec o a l i t i o nc o n t a i n i n gh i mf i r s t b & gf u n c t i o ni sc h o s e na st h ep a y o f ff u n c t i o no f t h ea g e n t s ，b yw h i c hb & gf u n c t i o no nc o a l i t i o n - a g e n ti sg e n e r a t e d u n d e rt h en e wr u l e ， w ew i l lp r o v i d et h ea r c h i t e c t u r ea n de x i s t e n c et h e o r e mo ft h el o c a ln a s hn e t w o r k i nc h a p t e r2 ，w es t u d yt h ea r c h i t e c t u r eo fs t r i c tn a s hn e t w o r k so fn o n - c o m p l e t e c o o p e r a t i v em i x e d f l o wn e t w o r kf o r m a t i o ng a m e sf o rt h ef i r s tt i m e i ns o m en e t w o r k s ， t h ew a yo fi n f o r m a t i o ne x c h a n g eb e t w e e na g e n t sw i t h i nt h es a m ec o a l i t i o ni so n e w a y f l o w ，o t h e r w i s e ，t h a ti st w o w a yf l o w i no t h e r s ，h ew a yo fi n f o r m a t i o ne x c h a n g eb e t w e e n a g e n t sw i t h i nt h es a m ec o a l i t i o ni st w o - w a yf l o w ，o t h e r w i s e ，t h a ti so n e - w a yf l o w t h e c o s t so ff o r m i n gl i n k sw i t h i nt h ec o a l i t i o na r el o w e r 舔c o m p a r e dt oc o s t so ff o r m i n gl i n k s a c r o s st h ec o a l i t i o n s a g e n t sw i t h i nt h es a m ec o a l i t i o nf i r s tf o r me f f i c i e n tn e t w o r k s ，o n t h i sb a s i s ，w es t u d yt h ea r c h i t e c t u r eo fs t r i c tn a s hn e t w o r k so fm i x e d - f l o wm o d e l sw i t h d e c a ya n dn od e c a yr e s p e c t i v e l y i nc h a p t e r3 ，w es t u d yc o m p l e xn e t w o r kf o r m a t i o ng a m e s i nt h e s en e t w o r k s ， a g e n t sc a nc h o o s eo n e w a yf l o wa n dt w o w a yf l o w u n d e rt h es t a t i o no fs o m ec o s t ，a s y s t e m a t i cs t u d yo nt h ec h a r a c t e r i s t i c so fs t a b l en e t w o r k si sd o n ef o rv a r i e t i e so fn e t w o r k f o r m a t i o ng a m e s ，w i t has i t u a t i o no fn o n - c o o p e r a t i o n ，i n c o m p l e t ec o o p e r a t i o na n d c o m p l e t ec o o p e r a t i o n k e yw o r d s ：n e t w o r kg a m e s ；m i x e d - f l o w ；n o n - c o m p l e t ec o o p e r a t i o n ；n a s hn e t w o r k s 引言 第一章单向及双向流 1 1单向流网络 1 2双向流网络5 1 3动态网络生成对策”8 第二章内单外双型和外单内双型网络生成对策1 4 2 1内单外双型网络生成对策1 4 2 1 1 无信息损耗的情形1 4 2 1 2 联盟内部无信息损耗而联盟之间有损耗的情形”1 5 2 1 3 计算示例1 6 2 2 外单内双型网络生成对策“1 8 2 2 1 无信息损耗的情形1 8 2 2 2 联盟内部无信息损耗而联盟之间有损耗的情形1 9 第三章复合型网络生成对策2 3 3 1四人混合流非合作网络对策2 3 3 2 四人混合流完全合作网络对策2 6 3 3 四人混合流部分合作网络对策一2 8 3 4 复合型非合作网络对策3 2 结论”3 6 参考文献3 7 攻读学位期间的研究成果“4 l 致谢”4 2 学位论文独创性声明4 3 学位论文知识产权权属声明4 3 引言 引言 对策论开始于1 9 4 4 年冯诺依曼和摩根斯坦恩合作的对策论和经济行为， 但是现代对策论与他们所论述的内容大相径庭。时至今日，对策论已经成为一门独 立的学科，其涵盖的范围极广，当中所涉及的学科包括：数学、运筹学、统计学、 经济学、金融学、市场学、管理学、生物学和政治科学等等，可以说得上是包罗万 象，应有尽有。譬如，从军事上的战机与导弹的最优控制到商业上的市场拓展与资 源开采的最优策略，或从国家宏观政策与外交到企业的投资与资本管理，都可以用 到对策论。 在现代对策论中，网络对策是其中一个非常有实用价值的的分支。网络对策是 一个前沿学科，仅有十几年的学术研究结果。社会与经济网络在现代社会中有着非 常重要的作用。在这些网络中，局中人通过一些特殊关系相连接，例如朋友关系或 贸易关系。网络中的每个结点代表一个局中人( 个体或一个组织) ，局中人通过连接 从中受益并且需要为自己建立的连接支付费用。网络对策可分为静态或动态、单向 流或双向流、费用同质或异质、收益同质或异质等情形。 论文将研究单向流网络对策和混合流网络对策，考察完全合作、部分合作或具 有固定联盟剖分的情况下纳什网的存在性以及网络结构特性。 例如本文研究的具有固定联盟剖分的单向流纳什网的动态形成过程，以b g 函 数作为支付函数，分别讨论对于联盟间的费用是同质的和异质的情况。由联盟问费 用与内部费用的巨大差距，联盟内部先形成联盟内部环网，再与其他联盟环网相连， 即形成纳什网。通过讨论尝试给出存在性定理或举出不存在的反例。当局中人在对 策进程中结成联盟，这些联盟构成全体局中人集合的剖分，联盟一局中人如同个体合 理的局中人采取行动，而假定在联盟的内部局中人实行完全合作，而且在整个对策 进程中直到对策结束联盟结构均不发生变化。局中人对联盟的成员之间所建立的连 接只需要支付相对较少的费用，且局中人以最大化其所在联盟的整体收益为行动原 则。最后用m y e r s o n 值分配他们的收益。改变连接的费用可能导致联盟剖分的动 态变化，因此可以扩展的研究内容还包括具有变化联盟结构的联盟同质费用单向流 纳什网的存在性等。 网络合作对策的研究不仅具有重要的理论意义，它丰富和发展了网络对策体系， 而且具有重要的现实意义。例如在国际社会中，国际政治或经济关系的主体首先是 国家，但众多国际组织，特别是政府间国际组织也充当着日益重要的角色。其中， 世界贸易组织、欧洲联盟、亚太经济合作组织、北大西洋公约组织、上海合作组织、 阿拉伯议会联盟等国际组织格外引人注目。以国家作为局中人，这些国际组织可以 视为局中人联盟，局中人通过一些特殊关系相连接( 如交易关系、协作关系) 维护 1 青岛大学硕+ 学位论文 本国以及地区的利益或者使自己的利益增加，最终他们形成社会政治或经济网络。 这些社会政治或经济网络在现代社会中扮演着重要的角色具有非常重要的作用。 非合作网络对策已经有了大量的论述，而针对合作情形的研究工作目前远未形 成完整的体系，特别是在目前国内尚未出现网络对策领域的研究工作，从这个意义 上来看，我们所做的工作具有重要的理论价值。 总而言之，网络对策的应用领域十分广泛，在经济、政治、军事战略以及 当代的计算机科学等领域都己成为重要的研究和分析工具。此外，它还与会计 学、统计学、数学基础、社会心理学以及诸如认识论与伦理学等哲学分支有重 要联系。 2 第一章单向及舣向流网络生成对策 第一章单向及双向流网络生成对策 本章主要研究具有固定联盟剖分的单向流纳什网的动态生成过程，这里局中人 之问的连接是有向的，表示为弧。弧的有向性对应于收益的流动性，即局中人f 和， 之间指向珀勺连接意味着f 通过与，连接从中获得收益。规定每个局中人只可以形成 指向自身的连接，所有的连接构成一个网络，在该网络中将定义每个局中人的支付 函数。称一个网络为纳什网，如果没有局中人可以通过偏离他所形成的连接集合而 获得更大( 严格大于) 的支付。 考察具有不完全合作属性的单向流网络生成对策。给定局中人集合的剖分，局 中人对联盟的成员之间所建立的连接只需要支付相对较少的费用，并且局中人将以 最大化其所在联盟的整体收益为首选的行动准则。 1 1 单向流网络 记为一个有限的局中人的集合。局中人，指向f 的连接记为( ，f ) ，称连接( ，f ) 是属于f 的。在局中人集合上的单向流网络为连接的集合，记为g n xn 。定义 局中人集合上的网络g 是连接的集合，这里不允许出现圈，即对任意的i n 有 ( f ，f ) 正g 。令g 是上所有可能的网络的集合。局中人f 到的一条有向路径是g 中 不同局中人，的一个序列，k 1 ，使得i = ，歹= ，对每个s = 1 ，k - 1 有 ( c ，0 。) g 。特别地，对于七= l ，i = 是一个f 到它自身的平儿有向路径。环网是由 连接所有局中人的环构成( 见图1 1 ) 。 图1 1 为方便起见，我们用+ 和一表示两个不同的网络之间的运算或者一个 网和一个连接之间的运算，运算的顺序是从左到右。例如， ( g g ) u ( ，讲用 g - 9 7 + ( ，f ) 来表示。记从g 中移除属于f 的连接之后得到的网络为g 。注意到从f 往 3 童鱼叁兰堡主堂篁笙茎一一 _ _ - - _ _ - _ _ 一一 外出的连接可能仍然存在于g 一，中。 定义1 1 1 记有限的局中人集合为= l ，n ) ，给定的剖分= 弓，只) ， 其中朋聍，而en 只：o ，l r ，s 力，s ，并且q 只= ，称中的每个元素圪为 联盟一局中人。 令m ( g ) ： n ：g 中存在到f 的有向路径) 是网络g 中局中人f 可观测到的局 中人的集合，令卅( g ) ： je ：( ，i ) eg 是g 中直接指向局中人f 的局中人集合。注 意到f m ( g ) ，但j 盛n ( g ) 。 对任意的局中人f ，设丌j ：g _ 酞是支付函数，这罩g 是上所有可能的单向流 网络的集合。我们选择以b & g 函数形式给出的支付函数： 一( g ) = 屹一勺 1 一( 1 ) 斥m ( g )j e n , 4 ( g ) 其中m ，是局中人，通过与歹连接而获得的收益，c ：f ，是形成连接( ，f ) 时局中人f 承 担的费用。在本文中假设收益和费用是非负的。设存在从，到f 的路径，局中人f 从 路径上的每一个局中人，处获得收益，同时需要为直接与自身的连接支付费用。如 果存在常数c ，使得对所有的f ，j e n ，f ，有勺= c ，则称连接费用是同质的。如果 对任意局中人f ，存在常数q ，使得对所有的都有勺= q ，则称连接费用是局 中人同质的n 1 。 定义1 1 2 设乃：g 天1 ，ien 是网络g 的给定的支付函数。联盟- 局中人 只，k = l ，m 的支付定义为 万r ( g ) = 乃( g ) j e 吒 定义1 1 3 如果存在常数q ，k = 1 ，m ，使得对所有的f ，je 最有勺= q ，并且 其它所有的q ，等于常数c ，则称连接费用是联盟同质的。 4 第一章单向及双向流网络生成对策 由定义1 1 2 ，联盟一局中人e 的支付为 ( g ) = ( ，：f ，一勺) ，e ，：m ( g )j e ? ( g ) = ( 屹一勺) 一勺 1 一( 2 ) i j e n i t 9 1j e n ? t g 、| e 巩j n ：t 酌 j e 雌j 仨斥 = ( 屹一q ) 一c l 斥j e n , ( g )j e 孵( g )，e 咯肛卵( g ) ，b庳咒 事实上，1 一( 2 ) 式可视为联盟最的1 3 & g 函数。 定义1 1 4 在网络g 中如果对任意的f ，j 均存在路径乇，f i ，t ，这里o = f ，= j ， 并且对s = 0 ，k 一1 有( ，+ 。) g ，则称g 为单向连通网。 1 2 双向流网络 双向流网络g 为无向网。连接( 歹，f ) 表示一条f 和之间的边，靠近f 的边上的叉 线表示该连接是由i 发起的( 即局中人i 为该连接支付费用) 。与单向流网络不同，在 双向流网络中局中人f 和j ( 即使局中人，并不需要为该连接支付费用) 将同时通过 连接( f ) 获得收益。 定义1 2 1 如果网络g 中有连接( f ，) g 或者( ，f ) g ，那么称局中人f 和j 之 间有双向连接砑( 或万巧) 。称无向网虿= c t ( g ) 为网络g 的闭包，其中的连接均 为双向连接。 如果存在双向连接砑，或者存在彼此不同的 ，j m 和i 以及_ ，使得 万币虿，丽虿，那么表示网络g 中局中人f 与之间存在一条双向路径，记 为f 5 j f 。记彤( g ) = 七f ) g ) ，而( g ) = i n ( g ) l 。用f ( 动= 后lf 付g 后) u 磅 表示由局中人f 在双向流网络g 中观察到的局中人的集合，那么鸬( 虿) = i ，( 虿) i 。 在连接费用是同质的情况下，针对双向流网络g ，支付函数则转化为 露( g ) = 鸬( 虿) 一( g ) c 1 一( 3 ) 即局中人f 的支付是他在双向流网络g 中观察到的局中人的数量减去主动形成连接 的总费用。与单向流网络不同的是，此时即使局中人不发起任何连接该局中人仍有 可能从( 除自己之外的) 其他人那里获得收益。 考察同质费用参数c 的三个范围。无论对于单向流还是双向流模型，如果 c ( 0 ，1 ) ，那么局中人，将愿意形成与任何局中人，的连接，因为形成一个连接所获 得的收益高于他为此需要付出的费用。当c ( 1 ， 一1 ) 时，如果局中人f 观测到j 形成 了与其他的局中人的连接，那么他将可能产生与，形成连接的愿望( 例如双向流情 形下，当c = 1 9 时，如果，已经与另一个局中人相连，因为3 一c l ，故f 将选择与 相连) 。最后，如果c ，7 1 ，那么任一局中人i 形成连接的支付将会小于不与任何局 中人相连的支付，因此局中人f 将不会形成与任何人的连接。 在双向流模型中，最优反应和严格纳什网的定义类似于单向流模型。 在双向流模型中，存在三种类型的“星 网，这依赖于网络中局中人所承担的 连接费用。对于一个即= 5 的局中人集合，图1 2 给出了这几种类型。 ( b ) 边缘赞助型 图1 2 定义1 2 2 在网络g 中，如果对联盟最，k = 1 ，m 存在常数瓦，使得对所有 f ，歹丑，f j ：有c o = 瓦，并且所有其余的c ：f = c o n s t ，那么称该网络为具有联盟同质 费用的。 记瓦= c i ，所有其余的= c o n s t 费用为常数乞。对每个f ，令乃：g 专r 是一个支 付函数。联盟乞作为联盟一局中人，定义其支付为 ( g ) = 互( g ) 卜( 4 ) f b 事实上，1 一( 4 ) 式可视为联盟只的“b & g 函数 。 6 ； 型 子r 一 5 子丁 王丁一 第一章单向及双向流网络生成对策 用参量万( o ，1 】来刻画损耗的标准。给定网络g ，如果局中人f 形成了与其他局 中人，的连接( ，f ) ，则局中人f 从歹获得的信息价值为万。一般地，如果网络中，到 i 的最短路径有q 1 个连接，则相对于i ，局中人的信息价值为扩。设i 丑，那么 单向流网络g 中局中人i 的支付可表示为 而双向流网络g 中局中人i 的支付则为 定义1 2 3 对任意的单向流网络g g ，记福利函数为w ：gjr ，即 形( g ) = 乃( g ) 网络g 称为是有效网，如果对于所有的g g 都有形( g ) w ( g ) 。 在双向流模型中，福利函数记为矿( g ) ，其定义类似。 l 一( 5 ) l 一( 6 ) 1 一( 7 ) 定义1 2 4 在双向流网络g 中称集合ccn 为双向部分，如果c 中任意两个局 中人之间都存在一条双向路径，并且不存在c 和c 间的双向路径。双向部分c 称 为是最小的，如果不存在包含三个及以上局中人的双向环，并且若存在连接( ，i ) ， 则不存在( f ，j ) 。网络g 称为最小双向连通网，如果它只有唯一的最小双向部分。 1 3 动态网络生成对策 给定局中人的集合和任意局中人f 的支付函数死，网络生成对策进行的阶段 为l ，2 ，令吕是f 阶段开始时的网络，并且这是所有局中人所共知的。初始网蜀是g 中的任意网。在f 阶段初根据随机机制选择某个局中人f ，并且假设所有局中人有正 的( 阶段独立的) 被选择的概率。在f 阶段局中人f 通过调整他的连接来改变网络吕， 7 c 馏 一 c 肌心 一 皓 白 万 + = g 万 乞 馏 一 q 础心 挥 一 儋 略 万 挥 + = g 一乃 青岛大学硕十学位论文 由此产生新网g 川，标志着t + l 阶段丌始。如果再也没有局中人需要调整自己的连接 集合则对策结束于g 。本章将局中人i 的行动限制在以下四种情形( 1 ) 通过；( 2 ) 增加一条指向f 的连接；( 3 ) 删去一条指向f 的连接；( 4 ) 替代，即( 2 ) 、( 3 ) 的联 合。上述四种行动类型称为局中人的局部行动。与之相对，如果允许局中人f 任意改 变指向他的连接的集合，则得到的行动称为全局行动。 定义1 3 1 局中人f 的行动是局中人的集合，记为s f ) 。若in ( g ) s 峰l 且i 墨砰( g ) 库l ，则称之为局中人f 的局部行动。若对墨没有限制则称为局中人，的 全局行动。 局中人i 的反应s 4 称为局中人f 的最优反应，如果对于所有反应s 冬 f ) ，都 有 7 r , ( g 一，+ ( ，f ) ：，s + ) ) 7 r , ( g 一，+ q 。 引理1 3 1 设j ( g ) g 最，即联盟最中的局中人没有与其他联盟中的局中人形 成任何连接，那么当联盟内部所有局中人形成一个环网时，联盟支付最大。 事实上，当联盟内部所有局中人形成一个环网时，每个局中人与联盟内所有局 中人相连，且连接费用最小，故支付最大【1 1 。此时，1 一( 4 ) 式变为 7 r p ( g ) 2 吲( 吲v - c k ) 定理1 3 2 对于联盟费用和收益同质的网络生成对策，当联盟同质费用和联 盟间费用满足 一p v + c o ，所以选择连接中的局中 青岛大学硕+ 学位论文 人，且根据引理1 1 1 ，将选择与钿相连。局中人f 2 将连接f l 。假设联盟p 中的局 中人丘( k i p i ) 以前的局中人已顺次连接，轮到屯行动时，如果他选择连接只中的 局中人，则将连接一。，那么联盟只的支付为7 只= ( 1 + 2 + + 七+ 旧1 ) v 一虹；如果他 选择与的i 一1 个联盟中的某个局中人相连，必选择与联盟成员数量最多的联盟环网 相连，则联盟只的支付为砟= ( 1 + 2 + + k - l + l p , l + l e , l 一( 七一1 ) q c ，由l 一( 8 ) 式得 磁，所以选择与一，相连。对于p 中局中人让i ，如果选择连接e 中的局 中人，则将与k i 一。相连，那么联盟p 的支付为= l e l 2 v i p i q ；如果选择与前f 一1 个 联盟中某个局中人相连，必选择与联盟成员数量最多的联盟环网相连，则联盟只的 支付为硝= ( 1 + 2 + + l e , l - l + l e , l + e , i i p , - ( i e , l - , ) c , 一c ，由1 一( 8 ) 式得 ， 所以钿选择连接让i - l 。这样联盟鼻形成内部环网。由于假设联盟暑，昱，e m 中的局中 人顺次行动，因此每个局中人行动一次之后所得到的网络为m 个孤立的联盟内部环 网( 它们相互之间没有连接) 。 局中人将按1 ，2 ，n 的某个排列继续之后的行动。假设所表示的最小值在某个 联盟只处达到，2 s m ，即= l f l ( l e l ) 。 i = i 最后证明当c l z i ，i 巧i 1 只i ，如果相连，p 增加的支付为 ip ，i l p l v c j 只i | 只1 v c o 则局中人i 必选择与巧相连。 情形2 当各联盟内部环网仍处于相互孤立的状态，由于 c o 故至少足满足上述条件。 针对各联盟内部环网之间的“非相互孤立”状态的情形，上述讨论说明联盟舅7 必 在其中。设只与某个曰7 相连后组成“广义联盟”互：( 上述情形1 等价于此时的，= 2 ) ， 则有新的“联盟剖分 昂，爿，只! ，p , - ，z ，记为日n ，耳n p 川m i ) 。令 1 ) = ：鳙r a ；i 。n 一。( i 最1 l 善1 只l | ) 那么当k 吲 1 吲+ 吲+ + l 最，口 缈l k - i 伊i = i 磁”i k i + l 曩”l + + l 最! ；口 = i 磁，| 旧；l + + 旧：“+ 旧：。l + + l 巧i ( 注：当七= ，时不出现旧：。i ) = 隰m 1 + 吲+ + 吲 所以p ( 1 p ，因而户( 1 ，p v c 。 类似于前面所进行的讨论，在新的“联盟剖分”下，会形成第二条联盟之间的 连接。以此类推，所有联盟内部环网之间将全部相连，最终形成单向连通网。定理 证毕。 事实上，不等式l 一( 8 ) 的左端主要为了限制并“迫使 各个联盟率先形成内 部环网；右端的限制则是针对于整个网络的连通性所设定。下面的推论考察了定理 的一些极端情形。 推论1 3 1 当选择充分小的占 0 并且c = 9 一g 时，联盟彤，c 可顺次连接成 环，且环的方向为互7 专巧斗专e 。若形成的环为图1 3 ( a ) 的形式，则局中 人还会通过局部行动将其调整为图1 3 ( b ) 。 由于纳什网的形成与局中人的行动顺序有关，最终还可能形成其他形式的连通 网，例如图1 3 ( c ) 。但此时会存在某些联盟局中人，他们的费用比形成环网的时 候大。 守口 1 2 ( b ) ( c ) 图1 3 1 3 口 青岛人学硕+ 学位论文 第二章内单外双型和内双外单型网络生成对策 本章运用联盟剖分的方式刻画部分局中人之间所具有的合作属性，即构成给定 联盟剖分的局中人将首先为最大化自己所在联盟的整体收益而采取行动。先研究具 有固定联盟剖分的内单外双混合型网络生成对策中严格纳什网的结构特性，所考察 网络的特殊性在于，联盟内部局中人之间的信息交换方式为单向流而除此之外的为 双向流，再考察了相反的情形。 针对一组通过网络共享一定收益的局中人定义网络生成对策，其中局中人可形 成附有收益的连接，每个局中人只可以形成指向自身的连接，所有的连接构成一个 网络。在此网络中定义每个局中人的支付函数，同时给定局中人集合的剖分，局中 人对联盟的成员之间所建立的连接只需要支付相对较少的费用。此外，本章对于网 络生成动态没有做出特别的限制，仅规定联盟内部首先形成有效网，然后不同联盟 的局中人之间可通过双向连接最终形成严格纳什网。 2 1 内单外双型网络生成对策 下面建立内单外双型混合流网络生成对策的模型。给定局中人集合n = 1 ，n ) 及其剖分= 墨，己) ，其中l 最i = ，而l i = 以= 聊。规定联盟一局中人最 ( 1 k m ) 内部的局中人只能建立单向流连接，而只的局中人和只( 1 s t m ) 的局中人之间可以形成双向流连接。形成单向流连接的费用为c l ，形成双向流连接 的费用为乞，不妨设q ，联盟内部有效子网为空网，严格纳什网为空网。( 2 ) 若q ，联盟内部 有效子网为环网，i ) 当0 c i ，所以增加任何一条连接都会使局中人所在联 盟支付总和减少，严格纳什网为空网。 在后一种情形下，每个联盟内部已形成环网，联盟一局中人采取行动，假设最终 形成严格纳什网g 。当0 ，联盟内部有效子网为空网，严格纳什网为空网。 1 s 重曼叁堂堡主堂生笙茎 ( 2 ) 若q ，联盟内部有效子网为环网，并且 i ) 当岛 r 2 8 时，严格纳什网为联盟孤立网； i i ) 当0 c ： ，2 ( 万一6 2 ) 时，严格纳什网为广义联盟完全网( 即任意两个联盟之间 存在一个双向流连接) ； i i i ) 当，2 ( 万一万2 ) q ，所以增加任何一个联 盟之间的双向流连接都会使局中人所在联盟的支付总和减少，故严格纳什网为空网。 在后一种情形下，当0 c ： ，2 ( 6 万2 ) 时，联盟直接相连比间接相连获得更大 的支付，所以严格纳什网为广义联盟完全网。当r 2 ( 万一万2 ) c ： ，2 万时，因为c ： 3 时， 联盟内部有效子网为空网，再由q 1 7 2 易知，严格纳什网为空网如图2 1 ( a ) 所示。 ( 2 ) 当q 3 时，联盟内部有效子网为环网。i ) 当0 3 ，则联盟内部有效子网为空网，再由c l 9 万时，严格纳什网为联盟孤立网， 1 6 第二章内单外双型和内双外单型网络生成对策 如图2 1 ( c ) 所示；i i ) 当0 c ： 9 ( 万一万2 ) 时，严格纳什网为广义联盟完全网，如图 2 1 ( d ) 所示；i i i ) 9 ( a 一万2 ) c ： 9 8 时，严格纳什网为联盟外部星网，包括图2 1 ( b 、e 、f ) 所示的情形。严格纳什网的分布如图2 2 所示。 10 2 005 o7 o $ o 9 04 莎题 。 ( c ) 图2 1 1 7 ( b ) ( d ) ( f ) 青岛人学硕十学位论文 2 2 外单内双型网络生成对策 图2 2 下面建立外单内双型混合流网络生成对策的模型。给定局中人集合n = 1 ，刀) 及其剖分= 日，已) ，其中i 最l = ，而i n i ；n = m r 。规定联盟一局中人e ( 1 后聊) 内部的局中人只能建立双向流连接，而只的局中人和c ( 1 s f n ) 的局中人之 间可以形成单向流连接。形成双向流连接的费用为q ，形成单向流连接的费用为巳， 不妨设q ，时，双向流联盟内部 有效子网为空网，当q ，时，联盟内部有效子网为最小双向连通网。 定理2 2 1 的结果显然，证明从略。 定理2 2 2 对于上述外单内双型混合流网络g ，有( 1 ) 当， q 乞时，严格 纳什网为空网( 所有局中人之间没有任何连接) ；( 2 ) 当c l ，时，i ) 如果c 2 厂2 ， 严格纳什网为联盟外部环网( 联盟与联盟之间通过单向流连接形成环网) ；i i ) 如果 ，2 c 2 ( 朋一1 ) r 2 ，那么严格纳什网为联盟孤立网。 事实上，( 1 ) 当， c i 2 8 + 万2 ，则联盟内部有效子网为空网，严格纳什网为空网( 如图2 3 ( a ) ) 。 ( 2 ) 若o q 8 + 4 8 2 + 4 8 3 时， 严格纳什网为联盟孤立网；i i ) 当岛 万+ 4 8 2 + 4 8 3 时，严格纳什网为连通网。 ( 3 ) 若2 ( 万一万2 ) q 万+ 4 8 2 + 4 8 3 时，最终形成的严格纳什网为联盟孤立网( 如图 2 3 ( b ) ) 。 i i ) 当8 + 8 2 2 8 3 c 2 8 + 4 8 2 + 4 8 3 时，最终形成的严格纳什网为联盟中心连 通网( 不同联盟之间仅有中心局中人相连) ( 如图2 3 ( c ) ) 。 i i i ) 当万一8 3 c 2 万+ 万2 2 万3 时，最终形成的严格纳什网为联盟中心边缘连通 网。( 一个联盟的中心局中人与其它联盟的所有局中人相连) ( 如图2 3 ( d ) ) 。 i v ) 当c 2 2 8 + 8 2 时，联盟内部增加任何一个连接都会使该联盟的支付 总和减少，故联盟内部有效子网为空网。由q c ：易知，严格纳什网为空网。 ( 2 ) 当0 c 。 8 + 4 8 2 + 4 8 3 时， 联盟一局中人之间形成任何一个连接将使发起连接的局中人所在联盟的支付总和减 少，此时严格纳什网为联盟孤立网。i i ) 当6 2 8 + 4 8 2 + 4 8 3 时，联盟一局中人之间形 成连接将使发起连接的局中人所在联盟的支付总和增加，故严格纳什网为连通网。 ( 3 ) 根据文献 1 关于双向流有效网的结构特性可知，当2 ( a 一艿2 ) q 8 + 4 8 2 + 4 8 3 时，因为联盟只中的局中人增加任何与联盟罡的连接都将使联盟毋的支付减少，此 2 0 第二章内单外双型和内双外单型网络生成对策 时形成的网络如图2 4 ( a ) 。当6 + 8 2 2 8 3 乞 8 + 4 8 2 + 4 8 3 时，联盟只的最优反应 是增加连接( 5 ，2 ) ，此时形成的网络如图2 4 ( b ) 。当万一万3 c 2 万+ 6 2 2 6 3 时，联 盟日的最优反应是增加连接( 5 ，2 ) 、( 4 ，2 ) 、( 6 ，2 ) 、( 5 ，1 ) 矛1 3 ( 5 ，3 ) ，此时形成图2 4 ( c ) 。 当c 2 c 2 ，且c 2 3 ，因为局中人以最大化自己的支付为行动准则，在得 到相同收益的前提下，局中人会选取费用较小的双向连接，由公式3 一( 1 ) 得 则混合流纳什网只能是双向流纳什网，包括双向流星网和双向流线网； ( 2 ) 若c l c ，且q 3 ，因为局中人以最大化自己的支付为行动准则，在得到相 同收益的前提下，局中人会选取费用较小的单向连接，则混合流纳什网只能是单向 流纳什网，包括单向环网和单向流花网。 ( 3 ) 其他条件下，因为局中人以最大化网络的总支付为行动准则，形成任意一条 连接都会使网络的总支付减少，则混合流纳什网为空网。 命题3 1 2 对于g = a 的情况 ( 1 ) 当0 q = c 2 1 时，除去单向流纳什网和双向流纳什网，混合流纳什网共4 8 0 个，大概分为4 类，如图3 1 ； ( a ) 混合流星网 第三章复合犁网络生成对策 3 ( a 1 ) 、= ：= 一一。，夕尹 。 ( a 2 ) ( a 4 ) ( b ) 混合流线网 l 簟：= = 二，崆_ k ：= = 二二：二叁4 ( b 1 ) k 二二，瞬：一二二二j 多争_ 畸 ( b 3 ) 1 卜 k e 一二：参争q ( b 5 ) l _ - 鲁_ 寺i = = ：囊q ( b 7 ) 卜予：二：二：? 多4 ( b 9 ) ( c ) 混合流花网 ( c 1 ) ( c 3 ) ( a 5 ) 商 户 ( a 3 ) _ 二7 k i c 二二二：= ：叁i c ：二：二：_ 4 ( b 2 ) l - _ 2 k 二二二：二叁争q ( b 4 ) l _ 写k 二二：+ ：砻卜1 4 ( b 6 ) 1 鲁卜号二二：二呵 ( b 8 ) 1 _ 1 号i 二= 二：j m ( b l o ) ( c 2 ) ( c 4 ) 青岛人学硕士学位论文 卜二i i 二：，：一 k ( c 7 ) ( c 9 ) ( d ) 混合流环网 芝 ( e 1 1 ) 卜一一一- t 上一。一一一一冉 ，二卜叫 ( c 6 ) ( c 8 ) ：二二：二二? m ( e 1 0 1 ( c 1 2 ) ( d 1 )( d 2 ) ( d 3 ) 图3 1 ( 2 ) 当l q = c 2 1 5 时，局中人以最大化自己的支付为行动准则，所以每个局中 人最多只愿意建立两个连接，则除去单向流纳什网和双向流纳什网，混合流纳什网 包括4 5 6 个，分别为图3 1 ( a ) 中( a 2 ) ( a 3 ) ( a 4 ) ( a s ) ，所有的( b ) ( c ) ( d ) ； 1 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 第三章复合犁网络生成对策 ( 3 ) 当1 5 q = c 2 3 时，局中人以最大化自己的支付为行动准则，所以都不愿意建立 连接，则混合流纳什网为空网。 单向流网络、双向流网络和混合流网络中各纳什网的分类及个数见下表4 1 环网线网花网星网双环网 单向流纳什网 61 22 441 2 双向流纳什网09 603 20 混合流纳什网 6 02 1 62 6 47 21 2 表4 1 在q = c 2 的情况下，在花费相同费用的前提下，选取双向连接对整个网络产生 更大的收益，因此有效的纳什网只能是双向流纳什网。凡是存在单向连接的网络就 不可能是严格纳什网，这是因为其中的单向连接可以被双向连接所取代。 3 2 四人混合流完全合作网络对策 设巧：g 专r 1 , f n 是网络g 的给定的支付函数。联盟一局中人最，k = 1 ，m 的支 付定义为 ( g ) = 乃( g ) f e 斥 在3 1 节的基础上，考虑完全合作的情况，这里局中人以网络的总支付最大化为目 标( 不考虑收益分配)