（运筹学与控制论专业论文）边覆盖对策的均衡性及其算法.pdf

边覆盖对策的均衡性及其算法摘要组合合作对策，又称组合最优化对策，是建立在组合最优化模型上的合作对策合作对策理论研究的核心问题是如何将联盟的整体收益( 或费用) 公平合理地分配给每个局中人不同的分配合理性要求导出了合作对策中不同对策解的概念其中，核心是最重要的对策解的概念之一，它体现了分配的子联盟合理性若核心非空，则称对策是均衡的本文主要讨论建立在图的边覆盖问题基础上的几个合作对策模型及其均衡性，并从算法和计算复杂性角度对核心进行了研究主要研究内容有：( 1 ) 首先定义了由图的整数边覆盖问题导出的两类合作对策模型松弛和严格的 七】一边覆盖对策；利用边覆盖问题的整数规划模型和对偶理论，给出这两类边覆盖对策均衡性的刻画和它们之间的等价性，并讨论了相关的算法问题( 2 ) 定义了由图的分数边覆盖问题导出的两类合作对策模型松弛和严格的分数边覆盖对策；利用对偶理论证明了这两类边覆盖对策都是均衡的，并给出了它们核心之间的关系关键词：边覆盖对策：核心：均衡性：拉格朗日对偶：多项式时间算法b a l a n c e d n e s si s s u e sa n da l g o r i t h m sone d g ec o v e r i n gg a m e sa b s t r a c tc o m b i n a t o r i a lc o o p e r a t i v eg a m e ，a l s on a m e da sc o m b i n a t o r i a lo p t i m i z a t i o ng a m e ，i sp r o p o s e dt om o d e lt h ep r o f i to rc o s ta l l o c a t i o np r o b l e mw h i c ha r i s e sf r o ms o m ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s c o o p e r a t i v eg a m et h e o r yc o n s i d e r sh o wt od i s t r i b u t et h et o t a li n c o m e ( o rc o s t ) g e n e r a t e db yag r o u pt oi t sm e m b e r sf a i r l ya n dr a t i o n a l l y t h ec o r ei so n eo ft h em o s ti m p o r t a n ts o l u t i o nc o n c e p t s ，w h i c hi sd e f i n e do nt h eb a s i so fs u b g r o u pr a t i o n a l i t y t h eg a m ei sc a l l e db a l a n c e df fi t sc o r ei sn o n e m p t y i nt h i st h e s i s ，w ef o c u so i ls o m ec o o p e r a t i v eg a m em o d e l sa r i s i n gf r o me d g ec o v e r i n gp r o b l e m so ng r a p h s w ec o n s i d e rt h eb a l a n c e d n e s so ft h eg a m e s ，a n dd i s c u s st h ea l g o r i t h m i ci s s u e so nt h e i rc o r e s t h em a i nr e s u l t sa r ea sf o l l o w s ：( 1 ) t w or e l a t e dc o o p e r a t i v eg a m e sa r i s i n gf r o mi n t e g e re d g ec o v e t i n gp r o b -l e m so ng r a p h s ，r e l a x e da n dr i g i d 七) 一e d g ec o v e r i n gg a m e s ，a r ei n t r o d u c e d ；b a s e do nan e wp r o g r a mf o r m u l a t i o nf o ri n t e g e re d g ec o v e r i n gp r o b l e ma n dd u a l i t yt h e -o r y ，ac o m m o nn e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o rt h eb a l a n c e d n e s so fb o t hg a m e si so b t a i n e d ；m o r e o v e r ，a l g o r i t h m i ci s s u e so nc o r e sb , r ed i s c u s s e d ( 2 ) t w or e l a t e dc o o p e r a t i v eg a m e sa r i s i n gf r o mf r a c t i o n a le d g ec o v e t i n gp r o b l e m so ng r a p h s ，r e l a x e da n dr i g i df r a c t i o n a le d g ec o v e r i n gg a m e s ，a r ea l s oi n t r o d u c e d w i t hd u a l i t yt h e o r yo fl i n e a rp r o g r a m m i n g ，w ep r o v et h a tb o t hg a m e sa r eb a l a n c e d ，a n dg i v et h er e l a t i o n s h i pb e t w e e nt h e i rc o r e s k e y w o r d s ：e d g ec o v e r i n gg a m e s ；c o r e ；b a l a n c e d n e s s ；l a g r a n g ed u a l i t yt h e o r y ；p o l y n o m i a lt i m ea l g o r i t h m s独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含未获得或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名每腑字日期：2 年f 月矽日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)学位论文作者签名：妊表硷导师签字：签字日期：加焊，月矽日学位论文作者毕业后去向：工作单位：通讯地址：哥哥复，签字日期：加咕年f - 月) 7 日电话：邮编：1综述及基本概念1 1合作对策的研究背景对策论，也称博奕论，是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论，是研究竟争的逻辑和规律的数学分支简单地说，对策论是研究决策主体在给定的信息结构下如何决策以使自己的效用达到最大，以及两个或多个决策主体之间决策均衡的数学理论对策论思想古已有之，我国古代的孙子兵法就不仅是一部军事著作，而且算是最早的一部对策论专著对策论最初主要研究象棋、桥牌、赌博中的胜负问题，人们对对策局势的把握只停留在经验上，没有向理论化方向发展，正式发展成一门学科则是在2 0 世纪初1 9 2 1 年法国的包瑞尔首先对对策论进行研究，引入了“最优策略”的概念，同时猜出了一些对策的结果美籍数学家冯诺意曼在1 9 2 8 年证明了包瑞尔猜出的一些结果 1 】，得出了对策论的基本原理一最大最小定理，奠定了对策论的理论基础，从而宣告了对策论的正式诞生第二次世界大战期间，由于军事和生产的需要，提出了许多对策问题，这引起了一些科学家对对策行为进行研究：同时经济学与对策论的研究结合起来，为对策论的应用提供了广泛的背景，也加快了对策论体系的形成：1 9 4 4 年，冯诺意曼与摩根斯坦共著的划时代巨著对策论与经济行为 2 】引起了广泛关注，对策论也由最初对于桥牌、棋艺的研究转到经济、管理、军事等领域的广泛应用对策根据其所采用的假设不同可分为合作对策理论与非合作对策理论其中，合作对策允许局中人之间合作并联盟，它主要强调的是团体理性而非合作对策主要研究人们在利益相互影响的局势中如何选择策略使得自己的收益最大，即策略选择问题，强调的是个人理性2 0 0 5 年诺贝尔经济奖授予a u m a n n 和s c h e l l i n g ，以表彰他们在博弈论领域作出的贡献，在合作对策领域，a u m a n n 把可转移效用联盟对策( t ug a m e s ) 扩展到了效用不可转移联盟对策( n t ug a m e s ) ；a u m a n n 除了开创n t u 对策并公理化，在t u 对策方面也做出了不可或缺的贡献a u m a n n 和m a s c h l e r ( 1 9 6 4 ) 3 在t u 对策框架下提出了“提议”( p r o p o s a l ) 、“反对”( o b j e c t i o n ) 、“反反对”( c o u n t e r o b j e c t i 0 】等概念，并基于以上概念提出了“谈判集= ( b a r g a i n i n gs e t ) 概念由此而直接导边覆盖对策的均衡性及其算法致了陆续提出的“核”( k e r n e l ) 和“核子”( n u c l e o l u s ) 4 ，5 】等合作对策理论中极其重要的解的概念在合作对策模型f = ( n ，c ) 中，n = 1 ，2 ，n 为局中人集合，c ：2 _r 为特征函数，其中c ( 0 ) = 0 对于任意的子联盟s n ，c ( s ) 表示s 作为合作整体可以得到的最大收益或最小费用如果c ( s ) 可以通过求解s 所确定的某个最优化问题得到则称该对策为组合合作对策合作对策理论的核心问题是如何将联盟 r 的整体收益( 费用) 公平合理地分配给每个局中人经典合作对策理论中对于利益( 费用) 分配的各种合理性要求，都是在局中人个体、子联盟和整体联盟的关系基础上提出的，由此得到不同的对策解的概念。例如，一般的分配概念体现了个体合理性条件，即对于每个局中人的分配值不得少( 多) 于他个人单干所得的收入( 费用) ；核心 6 】概念体现了联盟合理性条件，即对于一切子联盟s ，核心分配给s 的利益( 费用) 不少( 多) 于s本身联合所得到的总收益( 总花费) c ( s ) 因此，对于一个给定的核心分配，任何子联盟c ( s ) 都不能从整体联盟中分离出来而得到更多的好处合作对策的一些基本概念和性质，在五十年代就由n a s h 、s h a p l e y 等人逐步引入但在九十年代以前，对策的研究主要还是解的概念和性质的讨论，很少涉及算法的问题随着对策模型规模的不断扩大，以及计算机技术的发展和广泛应用，计算复杂性被提出作为衡量解的合理性的又一标准这种合理性要求的出发点是考虑局中人在寻求合理的策略或判定一个给定的策略是否合理时，不愿意花费指数次长度的时间，即所谓的有界合理性对于组合合作对策，其特征函数可以通过求解某个组合最优化问题得到，因而组合合作对策的输入规模往往是局中人个数的多项式长度，这一特点为组合合作对策中算法和计算复杂性的研究提供了必要的前提近年来组合优化理论、算法及计算复杂性理论的快速发展，也为组合合作对策中算法的研究提供了基础m e g i d d o 于1 9 7 8 年首先提出合理的求解方法应当是多项式时间算法7 1 ，d e n g 和p a p a d i m i t r i o u 于1 9 9 4 年进一步提出将计算复杂性作为评价和衡量解的合理性的一种尺度 8 】以核心为例，从算法和计算复杂性的角度讨论对策核心的问题有：( 1 ) 核心非空性( 即对策的均衡性) 的判定问题：能否在多项式时间内判定给定的对策模型核心的非空性?( 2 ) 核心元素的构造问题：如果己知对策的核心非空，是否存在多项式时间2边覆盖对策的均衡性及其算法算法求出一个核心元素，如何构造这样的算法?( 3 ) 支付归属核心的判定问题：给定一个对策模型和一个分配方案，能否在多项式时间内判定该分配是否为核心元素? 在谈判和议价中，除了参与对策的局中人外，往往还有中间协调人由协调人提出分配方案，供局中人讨论确定接收或者拒绝这一方案而能否在多项式时间内判定一个分配方案是否为核心中的元素，对于局中人而言，具有很大的实际意义1 2合作对策的基本概念具有特征函数的合作对策模型r = ( n ，c ) 是由局中人集合n = 1 ，2 ，n )和特征函数c ：2 _ r 构成的，其中c ( 0 ) = 0 对于任意的子联盟s n ，c ( s ) 表示s 作为合作整体可以得到的最大收益或最小费用当特征函数c 表示收益( 费用) 时，我们称相应的对策为收益( 费用) 对策本文将主要讨论费用对策本节对策解的概念也均对费用对策提出，收益对策的有关概念可对称地得到按照不同的合理性要求来分配总费用c ( ) ，导出了不同的合作对策的解，核心是合作对策中最重要的解的概念之一对于对策r ，局中人的个人花费一般用向量z ：n - r 表示若z 满足：( 1 ) l 矗= c ( ) ；( 2 ) i ：鼢sc ( i ) ) ，则称z 为对策r 的一个分配( i m p u t a t i o n ) 对策r 的所有分配的全体记作x ( r ) 对v s ，本文将用记号z ( s ) 来表示讵s 对策r 的核心( c o r e ) 的概念是在子联盟合理性的基础上引入的其定义为：c o r e ( r ) = ( z r n ：x ( j v ) = c ( n ) 且x ( s ) c ( s ) ，坩) 即对核心中的一个分配来说，如果局中人的任何真子集合从整体联盟j v 中分离出来形成自己的联盟进行合作，都不会节省花费因此，核心的分配是保持局中人合作的一个合理分配根据核心的定义可知，对策r = ( n ，c ) 的核心非空当且仅当下述线性规划问题：m a xz ( )( c a p ：s 羔 七)则以p 中不同的顶点作为中心的任何星形子图都边不交下面对每个顶点“v ，我们用e ( u ) 来构造一个由星形子图构成的集簇( 1 ) 对每个t v 记9 ( e ) ( e e ( t ) ) 中的所有正数分别为9 1 = 9 ( e 1 ) ，夕2 =9 ( e 2 ) ，卯= g ( e t ) ，并将它们按非降的顺序排列，不妨设0 g l 夕2 9 l ( 此处记夕o = o ) 1 2边覆盖对策的均衡性及其算法情形1 当g t = 七时，如下定义f 类星形子图：一在丁夕中有9 1 个五( ) ；叫在丁g 中有9 2 一9 1 个t 2 ( u ) ；_ 在p 中有g t 一垒一1 个正( 牡) 情形2 当g t 七时，记a = k 9 1 则易证存在整数t ：0 t z 满足o 阳执s1 2 o 确+ 1 鱼则由星形子图构成的集簇可按如下方式得到：选择9 1 个噩( u ) = e 1 ) ，仍个死( 心) = e 2 ) ，g t 个互( “) = e t ) ，a e o g i g t 仇个正+ l ( u ) = e 件1 ) ：对于e 蚪l 边上夕剩余的值( = 0 蝉+ 1g i d )及e u ) 中的其它边( e j ：t + 1 一 一 一0 曲0州州躺忙如nnmi，i、，一戤戤酬=i i=、l，、孙孙抛边覆盖对策的均衡性及其算法若在导出子图g 司中不存在( 凫卜边覆盖函数，则c ( s ) = 十o 。( 或一个足够大的数m o ) 在松弛的边覆盖对策中，子集s y 在选择“边覆盖”时有更多的可能，因此有一( s ) c ( s ) 而对于所有局中人构成的集合y ，在两类对策中，均有相同的可能，即可y ) = c ( y ) 由此可得c o r e ( 1 ) c o r e ( f ) ( 2 2 1 )下一节中，我们将进一步证明c o r e ( r ) 同c o r e ( r ) 的非负部分相同2 3 尼 边覆盖对策的核心由单调对策的定义可验证，松弛 忌 边覆盖对策于：( v 动是单调的，而严格 七卜边覆盖对策r = ( vc ) 却不是单调的本节将对这两类【七卜边覆盖对策的核心进行刻画定理2 3 1令g = ( ve ；) 是一个边赋权图，r = ( v 刁是相应的松弛f 七) 一边覆盖对策则ze c o r e ( r 】当且仅当( 1 ) z 0 ，且z ( v ) = 硪y ) ；( 2 ) v e e ，z ( y ( e ) ) s 鼬( e ) 证明：假设z c o r e ( p ) 则由r 的单调性知z 0 给定边e e ，定义e 上的一个函数9 ：9 ( e ) = 七，g ( e 7 ) = 0 ( e ，e ) 显然，y ( e ) 被g 七) 一覆盖，由此得z ( y ( e ) ) 反y ( e ) ) 七u ( e ) 下面证明充分性令s y 夕是定义在e 上的函数，满足s 被g 。 七) 一覆盖且。e 9 ( e ) u ( e ) 达到最小，即。e 夕+ ( e ) u ( e ) = 议s ) 则有z ( s ) 。s 。e 扣) 9 。( e ) 】石( t ，) 。y e e ( 廿) 夕+ ( e ) z ( 口)= 。e9 ( e ) z ( y ( e ) ) 。f g 。( e ) u ( e ) = _ ( s ) ，其中，第一个“”是因为s 被夕+ 七) 一覆盖，第二个“”是因为z o 因此，ze c o r e ( 1 ) 证毕定理2 3 2 令g = ( ke ；u ) 是一个边赋权图，r = ( vc ) 是相应的严格 七) -边覆盖对策则ze c o r e ( r ) 当j t 仅当1 4边覆盖对策的均衡性及其算法( 1 ) z ( v ) = c ( y ) ；( 2 ) v v y 及0 s ( u ) ，有z ( su u ) e 。e 加，司七v ( e ) 证明：设2e c o r e ( i ) ，l u z ( v ) = c ( y ) 对任意的u v 及s j v ( o ) ，定义a su u ) 】上的函数g ，使得对任意的e e l y ，司，夕( e ) = 七；对于ege v ，司，夕( e ) = 0 显然，夕是导出子i s g su u j 的一个 奄) - 边覆盖函数，n z ( su u ) c ( su u ) 。e 加，s l 七u ( e ) 另一方面，若在导出子图g 【s 】中不存在 七) 边覆盖函数，则由严格 七卜边覆盖对策的定义，有z ( s ) l = 夕( e ) ；( 2 3 1 )vp s ：j f 丁：t t g 且口y ( 丁) ) i = k ( 2 3 2 )又由该定理的条件( 2 ) 知v t p ：z ( y ( 丁) ) 七。tu ( e ) ( 2 3 3 )因此有z ( s ) = 专e t e 即z ( y ( 丁) ) 丢t e 和七e e e tu ( e )= e t 丁。e e tu ( e ) = , e e s tg ( e ) u ( e ) = c ( s ) 其中，第一行中的“= ”由( 2 3 2 ) 式得到，第一行中的“由( 2 3 3 ) 式得到，第二行中第二个“= 由( 2 3 1 ) 式得到证毕由定理2 3 1 及定理2 3 2 ，可以得到这两类 七) 边覆盖对策的核心之间的关系推论2 。3 3 令r 和r 分别是定义在图g = ( ke ；u ) 上的松弛和严格 奄卜边覆盖对策，则c o r e ( i ) = c o r e ( i ) n 碎( n = l y l ) 证明：由( 2 2 1 ) 式可知c o r e ( r ) c o r e ( i ) 又易知松弛边覆盖对策r 是单调的，故z 0 因此c o r e ( i ) c o r e ( i ) n 碎另一方面，任给z c o r e ( r ) n r + ，由定理2 3 2 的条件( 2 ) , - - r 知，对每个e e ，都有z ( v ( e ) ) 鼬( e ) 因此，z 满足定理2 3 1 的两个条件，从而：c d r e ( 于) 1 5边覆盖对策的均衡性及其算法2 4 尼 边覆盖对策的均衡性本节将着重研究两类 七 边覆盖对策的均衡性我们将得到这两类对策均衡的等价性令g = ( v e ；u ) 是一个顶点集合为v = 砚，忱， ，边集合为e = e l ，e 2 ，】的边赋权图令a = ( 口玎) n m 是一个竹m 矩阵，其中行对应图g 的顶点，列对应图g 的边，且满足：当第i 个顶点与第j 条边关联时，m ，= 1 ；否则啦，= 0 则 七卜边覆盖问题可写成如下的整数规划形式：( i p l ) ：r a i n u z ：a x k ，z o ，1 ，七) m ) ( 2 4 1 )这里，u 是一个仇维行向量，它的每个分量对应e 中相应边的边权，k 是一个n 一维列向量，它的每个分量均为k 对于该整数规划，它的线性规划松弛及其对偶可写成：( l p l ) ：m i n u z ：a z k ，z o ) ；( 2 4 2 )( d l p l ) ：m a x y k ：y a u ，y o 、7注意到在( l p l ) ( 2 4 2 ) 中，我们使用约束z o 代替0 z 七这是因为在目标函数值最小的要求下，约束z 七是多余的以下把问题( p ) 的最优值简记为o p t ( p ) 在下面的定理中，我们将证明松弛 七卜边覆盖对策f = ( v , c - ) 是均衡的当且仅当线性规划松弛( l p l ) ( 2 4 2 ) 有整数最优解这里使用的方法类似于d e n g ，i b a r a k i 和n a g a m o c h i 2 5 1 中的方法定理2 4 1令g = ( ve ；u ) 是一个边赋权图，p = ( v 刁是相应的松弛 七一边覆盖对策则c o r e ( r ) d 当且仅当( l p l ) ( 2 4 2 ) 有整数最优解在此情况下，向量z = ( z 1 ，z 2 ，磊) 属于核心当且仅当壬是( d l p l ) ( 2 4 2 ) 的最优解证明：令z c o r e ( p ) 由定理2 3 1 知，壬是( d l p l ) ( 2 4 2 ) 的可行解，且z ( y ) 等于( i p l ) ( 2 4 1 ) 的最优值则由线性规划对偶定理知：z ( v ) = o p t ( i p l ) o p t ( l p l ) = o p t ( d l p t ) z ( y ) ，由此可得o p t ( i p l ) = o p t ( l p l ) 充分性得证另一方面，假设o p t ( i p l ) = o p t ( l p l ) ，且y = ( y l ，y 2 ，蜘) 是( d l p l )( 2 4 2 ) 的最优解对于向量z = k y ，有z ( v ) = k y ( v ) = o p t ( d l p l ) = o p t ( l p l ) = o p t ( i p l ) = 硪y ) 1 6边覆盖对策的均衡性及其算法又由是( d l p i ) ( 2 4 2 ) 的可行解知，z o 且z ( y ( e ) ) 七u ( e ) 由定理2 3 1 可得孑c o r e ( f ) 证毕为了研究严格f 七】，边覆盖对策的均衡性，我们对 凫) 边覆盖问题构造一个新的整数规划模型给定一个边赋权图g = ( v e ；u ) ，记v = ( t ，1 ，) ，e =( e 1 ，e m ) 引入两类整变量：i 弧_ 【o ，l ，七 ：边岛被选择玑次到( 七) 一边覆盖中；【o ，1 ，七) ：边白被选择次来覆盖吻则f 七卜边覆盖问题可描述为下面的整数规划：r a i n 翌1 玑2 卜鲥 掣铲矗嚣- - l , - 一，, m n 小卜，仃4 ix i j ，y i 【o ，七 i = l ，m ，j = l ，n在该整数规划中，约束e ( 。，) x i j = 七保证了顶点吻恰好选择了七次边来“覆盖”它因为在目标函数中没有z 玎项，所以这些约束等价于氏f ( 啦 k 而第二类约束y i 保证了顶点吻至多只能被边e t 覆盖y d ：k 用，y i 0 替换离散约束x j ，y 【o ，l ，七】，就得到了下面的线性规划松弛：( l p 2 ) ：“ 黧另一方面，我们考虑严格 七) - 边覆盖对策的核心，其对应的费用分配问题为：( c a p ) ：m 觚l ；= ( 2 4 5 )s t 。s 勿c ( s )s y、易知，c o r e ( f ) 口当且仅当( c a p ) ( 2 4 5 ) 的最优值等于c ( y ) ，且在此情况下，( c a p ) ( 2 4 5 ) 的最优解必是核心中的元素在下面的定理中，我们将给出( l p 2 ) ( 2 4 4 ) 和( c a p ) ( 2 4 5 ) 之间的密切联系定理2 4 2 对于定义在图g = ( ve ；u ) 上的严格f 七 一边覆盖对策r =( vc ) ，其费用分配问题( c a p ) ( 2 4 5 ) 等价于( l p 2 ) ( 2 4 4 ) 的对偶规划特别地，c o r e ( r ) 口当且仅当( l p 2 ) ( 2 4 4 ) 有整数最优解1 7、，j月t 42，flnn11=nmm，lll=| i边覆盖对策的均衡性及其算法证明：引入向量7 = ( z i ，磊) ，其中每个变量弓对应一个约束。e ( 叱) =七0 = 1 ，n ) ，我们把这些约束作为复杂条件约束，得到( l p 2 ) 的拉格朗日对 竺。咄玑+ 。弓c k - e 矗e ( 码) z 巧) s t 0 x i j 执i = 1 ，m ，歹= 1 ，n因为名1 氐层( = 譬l 吩矿( 矗) ，则上述规划具有如下等价形式：( l d ) ：乎 m 训a n 銎。( 咄犰一眯啪) 辆) + 七跺。弓( 2 4 6 )s t 0 z 巧瓠 = 1 ，m ，j = 1 ，n由强对偶定理【9 知，拉格朗日对偶( l d ) 等价于( l p 2 ) 的对偶规划，且与( l p 2 ) 有相同的最优值对于给定的向量，( l d ) 内部的最小化问题要么无界；要么有一个最优解= 玑= 0 ( = 1 ，m ，j = 1 ，n ) ，使其最优值为七凳l 弓而内部的最小化问题无界当且仅当存在顶点y 及子集s 人( 吻) ，使得咄一e ( su 吻) ) o 是一个充分大的常数) 如下：犰= z 巧= me 4 e 【吻，s 】，码s戤j = me p 是e h ，司中任意选定的一个边弘= z 臼= 0否贝u此时，该可行解的目标函数值为i 色e ，司咄一z ，( su _ ( 吻) ) jm 0 ，这表明内部的最小化问题无界另一方面，若对每个顶点v 及每个子集s ( ) ，都有岛e h s l 纰一z ( suf 吻) ) 0 ，则由约束0 y i ，易知z 巧= 鼽= 0( i = l ，m ，j = 1 ，n ) 必为( l d ) 内部最小化问题的最优解令z = k z ，由上述分析可知拉格朗日对偶规划( l d ) 可以写成下面的线性规划形式：m s a 六x 笳瓢暖倒s l 岫j _ 1 i ，幔sn ( v 1 ) ( 2 4 8 )s t z ( su 【) ) 七岛e i q ，岫= 1 ，n ，)、口vm 霸呼偶边覆盖对策的均衡性及其算法由引理2 3 2 ，z c o r e ( r ) _ 当 l 仅当对任意的吩y 及s n ( o j ) ，都有z ( su_ ) ) 矗研r j , 8 岫这表明线性规划( 2 4 8 ) ，即拉格朗日对偶( l d ) ，与费用分配问题( c a p ) 是等价的根据对偶定理，线性规划( c a p ) ，( l d ) ，( l p 2 ) 的最优值相等，故该定理的第二部分结论成立证毕考虑( l p 2 ) ( 2 4 4 ) 的对偶规划：m a x 七翟l 勿( d l p 2 ) ：“瞄兰( 2 4 9 )白e o ) 由单调对策的定义易验证i 松弛的分数边覆盖对策f = ( v 习是单调的，并根据与( 2 2 1 ) 式类似的分析可知：c o r e ( f ) c o r e ( f ) n4 ( 3 2 1 )可以进一步证明c o r e ( r ) 同c o r e ( r ) 的非负部分相同3 3松弛的分数边覆盖对策的均衡性本节我们对松弛的分数边覆盖对策的核心进行刻画令g = ( ve ；u ) 是一个顶点集合为v = u 1 ，也，u n 】，边集合为e =【e l ，e 2 ，e r a ) 的边赋权图令4 = ( ) n x 仇是一个n m 矩阵，其中行代表顶点，列代表边，满足：当第i 个顶点与第j 条边关联时，a , i j = l ；否则。玎= 0 对任2 2边覆盖对策的均衡性及其算法意的s v ，a s , m = ( ) n m 也是一个n 7 7 l 矩阵，其中行代表y 中的顶点，列代表e 中的边，满足：当第i 个顶点在s 中且与第歹条边关联时，= l ；否则n 巧= 0 则分数边覆盖问题可写成如下的线性规划形式：( l p i ) ：m j n ( u z ：a x 之1 ，z o ，( 3 3 1 )这里，u 是一个仇维行向量，它的每个分量对应e 中每条边的边权，1 是一个n 维列向量，它的每个分量均为1 我们使用约束z 0 代替0 z l ，这是因为在目标函数值最小的要求下，约束z 1 是多余的它的对偶线性规划可写成：( d l p l ) ：m a x y l ：y a u ，y o ) ( 3 3 2 )在下面的定理中，我们将证明松弛的分数边覆盖对策是均衡的定理3 3 1令g = ( ve ；u ) 是一个边赋权图，f = ( u 习是相应的松弛的分数边覆盖对策则r = ( k 刁是均衡的7 证明：令z = ( z l ! z 2 ，) 是( d l p l ) ( 3 3 2 ) 的最优解，则z ( y ) = t y 磊为对应的( d l p l ) 的最优值，即o p t ( d l p l ) = 州盈= 名( y ) 而可y ) 为( l p l ) ( 3 3 1 ) 的最优值，由对偶定理可知z ( y ) = 一( y ) 另一方面，对v s y ，设x i 为t 1 线性规划问题的最优解：可s ) = m i n u z ：a s , m x l s ，。o ) ( 3 3 3 )其中1 s p 为集合s 的指标向量，满足：当第i 个顶点在s 中时，l s ( i ) = l ：否则l s ( i ) = 0 则：( s ) z ( a s m z ) s ( z a ) x * s u z ；= 可s ) 因此，z6 c o r e ( r ) 证毕推论3 3 2 令g = ( ve ：u ) 是一个边赋权图，于= ( k 动是相应的松弛分数边覆盖对策则z6 c o r e ( i ) n j i 仅当( 1 ) z 0 ，且z ( y ) = 及y ) ：( 2 ) v e e ，z ( y ( e ) ) u ( e ) 边覆盖对策的均衡性及其算法证明：假设z c o r e ( r ) ，则由r 的单调性知z 0 给定边e e ，定义e 上的一个函数夕：g ( e ) = 1 ，g ( e 7 ) = 0 ( e 7 e ) 显然，y ( e ) 被夕分数覆盖，由此得z ( v 7 ( e ) ) 及y ( e ) ) u ( e ) 充分性由定理3 3 1 可得证毕推论3 3 3 给定图g = ( ve ，u ) ，令f = ( v 刁为松弛的分数边覆盖对策如果c o r e ( r ) 0 ，则1 ) 可以在多项式时间内求得对策r = ( kc - ) 的一个核心元素；2 ) 给定支付向量z ，可以在多项式时间内判定z 是否属于核。5 , c o r e ( r ) 3 4严格的分数边覆盖对策的均衡性本节将讨论严格分数边覆盖对策的均衡性先给出一个引理说明对于图g 的一个极小分数边覆盖函数g ，我们可以适当地选择一个由相应于9 的星形子图构成的集簇及相应的权重，使得g 中的每个顶点都恰好包含在该集簇中权重和为1 的星形子图中引理3 4 1 令夕是图g = ( v e ) 的一个极小分数边覆盖函数，则对任意的 v ，存在由g 产生的u 星形子图的集合，记作碍，和权重函数如：刀_ 4( 可能重复) ，使得( 1 )v e e ，。t 钾如( 力= 夕( e ) ；( 2 ) v u v ，集簇t g = 刀：影y ) 中包含u 的星形子图的权重和为l ，即掣y t r 刀乙( 丁) = 1 证明：因为9 是图g = ( ke ) 的一个极小分数边覆盖函数，所以对任意的顶点口v ，都有。e g ( e ) 1 又由g 的极小性，易知对任意的边( u ， ) e ，不等式。e ( u ) 夕( e ) l 和。f ( 。) 9 ( e ) 1 中至少有一个等号成立记v k 【t l v ：。e ) 9 ( e ) 1 ) 则以v 1 中不同的顶点作为中心的任何星形子图都边不交下面对每个顶点“n 我们用e ( t 1 ) 未构造一个由星形子图构成的集簇边覆盖对策的均衡性及其算法( 1 ) 对每个u v ，记9 ( e ) ( e e ( ) ) 中的所有正数分别为夕l = g ( e 1 ) ，9 2 =夕( e 2 ) ，g l = g ( e 1 ) ，并将它们按非降的顺序排列，不妨设o 9 1 9 2 g l ( 此处记g o = o ) 情形1 当g t = 1 时，如下定义f 类星形子图：e u ) ne ：g ( e )e u ) ne ：g ( e )e ( u ) nf e ：g ( e )g l z u ( 乃( u ) ) = g l ；9 2 “( 死( u ) ) = 9 2 9 1 ；卯)气( 正( u ) ) = 夕i 一9 l 一1 情形2 当卯 1 时，记口= 1 一仂则易证存在整数t - 0 t 2 满足o s t9 i 口 呸i s t + lg i 则由星形子图构成的集簇可按如下方式得到：i 丑( u ) = e 1 )u ( 丑( t 1 ) ) = g i ；l 乃u ) = 勿)如( 乃( u ) ) = 现ii 正( ) = 1 鼠)厶( 丑( “) ) = 夕t i 珥1 ( t ) = e ) 2 札( 研1 ( u ) ) = 口一0 i t g i 对于e t + 1 边上9 剩余的值( = 0 斑+ 1 俄一a ) 及e ( u ) 中的其它边 白：t + l j ? ) 上对应的g 值，我们用情形l 中的方法构造星形子图( 2 )对于两个端点u ，t ，gv 的边e = ( u ， ) ，我们选择f e 作为p 中的星形子图不妨设_ e 是以“为中心的，a 口t ( u ) = e 】，定义权重e u c t ( u ) =9 ( e ) ，匕( 丁( t ) = 0 对于如上构造的由星形子图构成的集簇及相应的权重，易知v e e ，。t 砰如( 丁) = 9 ( e ) ；并且v u v ，。矿r 刀e v ( t ) = 1 证毕利用t ，一星形子图，给出严格分数边覆盖对策核心的刻画定理3 4 2 令g = ( ve ；u ) 是一个边赋权图，r = ( vc ) 是相应的严格的分数边覆盖对策则：e c o r e ( r ) 当且仅当( 1 ) z ( v ) = c ( y ) ：( 2 ) v y 另n0 s ( u ) ，有z ( s u 【u ) ) 。e 加，s l u ( e ) 证明：设ze c o r e ( r ) ，口i g z ( v ) = c ( y ) 对w f 及s ( t ，) ，定义a su ) 上的函数g ，使得对v e e l y ，司，g ( e ) = 1 ：对于ege h 司，g ( e ) = 0 显、l，、，孙孙驰，、一，边覆盖对策的均衡性及其算法然，夕是导出子图c s u u 】- 】的一个分数边覆盖函数，口i u z ( s u u ) c ( s u ( 口) ) 。e h s lu ( e ) 另一方面，若在导出子图g 吲中不存在分数边覆盖函数，则由严格分数边覆盖对策的定义，有z ( s ) c ( s ) = + 下面考虑在g s 】中至少存在一个分数边覆盖函数的情况令s 冬y ，且g + 是导出子i 訇c s 1 的一个最小分数边覆盖函数，即。e 旧夕+ ( e ) u ( e ) = c ( s ) 由引理3 4 1 知，存在图c s l m - 个由星形子图构成的集簇p ，使得v e 科司：e e t e 露如( t ) = g ( e ) ；( 3 4 1 )vu s ：。s u e t e 砰厶( 丁) = 1 ；又由该定理的条件( 2 ) 知v t t g ：z ( y ( 丁) ) 。t u ( e ) 因此我们有( 3 4 2 )( 3 4 3 )z ( s ) = 。s t e 刀厶( 丁) ：( y ( t ) ) 。s t 刀厶( 丁) 。ta ) ( e )= v s 。? 丁碍厶( 丁) u ( e ) = 。e 【s 】9 ( e ) u ( e ) = c ( s ) 其中，第一行中的“= ”由( 3 4 2 ) 式得到，第一行中的“”由( 3 4 3 ) 式得到，第二行中第二个“= ”由( 3 4 1 ) 式得到证毕为了研究严格分数边覆盖对策的均衡性，我们用类似于第2 章中的方法，对分数边覆盖问题构造一个新的线性规划定义两类变量：f 玑 0 ，1 】：可看作边e i 被选择到分数边覆盖中的权重( 或可能性) ；【z 妇 o ，1 】可看作边e l 被选择来覆盖的权重( 或可能性) 则分数边覆盖问题可描述为下面的线性规划：n r nm i l l 乙i ：1 岫挑( l p 2 ) ：s 。 z 玎- , e 4 s e e 玑( v j ) z 玎21 ；三：，j j 三，歹：1 ，礼c 3 4 4 )【，玑0江1 ，m ，j = 1 ，n边覆盖对策的均衡性及其算法引理3 4 3 对于定义在图g = ( ve ；u ) 上的严格分数边覆盖对策f =( vc ) ，线性规划( l p 2 ) 的拉格朗日对偶等价于下面的线性规划：m a x 塾1 勿( l d ) ：s t z ( su 吩) ) 。e h 阎岫( 3 4 5 )歹= 1 ，n ，s n ( v j )该引理的证明与第二章中定理2 4 2 的证明类似，从略定理3 4 4 令f = ( vc ) 是对应于图g = ( ve ；u ) 的严格分数边覆盖对策则r = ( vc ) 是均衡的，且向量ze c o r e ( r ) 当且仅当z 是( l d + ) 的最优解证明：设：是( l d ) 的最优解，由对偶定理和引理( 3 4 3 ) 可知，z ( y ) =o p t ( l d + ) = o p t ( l p 2 ) = c ( y ) 又因为z 是( l d ) 的可行解，从而z ( su 吻 ) e e h 司岫j = 1 ，n ，s n ( v j ) ，由定理3 4 2 可知，ze c o r e ( f ) 另一方面，若。6 c o r e ( f ) ，则z ( y ) = c ( v ) = o p t ( l p 2 ) = o p t ( l d ) ，且z ( s u【吻) ) 。e hs l 咄歹= 1 ，n ，s ( 屿) ，从而z 是( l d ) 的最优解证毕推论3 4 5 给定图g = ( 1 i , e ，u ) ，令f = ( vc ) 为严格的分数边覆盖对策如果c o r e ( f ) d ，则1 ) 可以在多项式时间内求得对策f = ( vc ) 的一个核心元素；2 ) 给定支付向量z ，可以在多项式时间内判定z 是否属于核一& c o r e ( f ) 该推论的证明与第二章中定理2 4 6 的证明类似，从略由( 3 3 1 ) 式，推论3 3 2 及定理3 4 2 ，我们还可以得到两类分数边覆盖对策核心之间的关系：定理3 4 6 令r = ( vc ) 和f = ( v 石) 分别是相应于图g = ( ke ；u ) 的严格和松弛的分数边覆盖对策，则c o r e ( r ) = c o r e ( f ) n 群( 礼= l y l ) 参考文献【1 】j v o nn e u m a n n t h e o r yo fp a r l o rg a m e s m a t h e m a t i s c h ea n n a l e n ，1 9 2 8 ，l o o ( 1 ) ：2 9 5 3 2 0 【2 】j v b nn e u m a n n ，o m o r g e n s t e m t h et h e o r yo fg a m e sa n de c o n o m i c sb e h a v i o r p r i n c e t o n ，n e wj e r s e y ：p r i n c e t o nu n i v e r s i t yp r e s s ：1 9 4 4 【3 r j a u m a n n ，m m a s c h l e r t h eb a r g a i n i n gs e tf o rc o o p e r a t i v eg a m e s a n n a l so fm a t h e m a t i c ss t u d i e s