具有超图合作结构的Banzhaf值.pdf
《具有超图合作结构的Banzhaf值.pdf》由会员分享,可在线阅读,更多相关《具有超图合作结构的Banzhaf值.pdf(10页珍藏版)》请在咨信网上搜索。
1、DOI:10.15960issn.1007-6093.2023.03.013Operations Research TransactionsVo1.27No.3Sep.,2023第2 7 卷第3 期运筹学学报2023年9 月具有超图合作结构的Banzhaf值*吕文蓉1单而芳1,t摘要2 0 0 6 年,Alonso-Meijide和Fiestras-Janeiro考虑了以图作为合作结构的可转移效用对策模型(简称为图对策),提出了图对策Banzhaf值,它是经典Banzhaf值的一类推广。本文进一步将Banzhaf值推广到超图对策中,定义了超图对策Banzhaf值。其次,证明了超图对策Banzh
2、af值满足分支可分解性、分支总贡献性、公平性、平衡贡献性以及隔离性,并给出了该值的两种公理性刻画。最后,举例分析了超图对策Banzhaf 值所满足的性质。关键词TU-对策,图对策,超图,超图对策,Banzhaf值中图分类号F224.322010数学分类号9 0 B35The Banzhaf value for hypergraph communicationsituations*LYU WenronglSHAN Erfangl,tAbstractAlonso-Meijide and Fiestras-Janeiro(2006)introduced TU games withrestricted
3、 cooperative structure represented by an undirected graph,or simple graphgames,and present the Banzhaf value of the graph game,that extend the Banzhaf value.In this paper,we first generalize the Banzhaf value to the hypergraph game,define theBanzhaf value of the hypergraph game.Secondly,we prove tha
4、t the Banzhaf value of thehypergraph game satisfies the property of component decomposability,component totalcontribution,fairness,balanced contribution,and isolation,and propose two characteri-zations of this value.Finally,we give an example to illustrate the properties satisfied bythe Banzhaf valu
5、e of the hypergraph game.Keywords TU-game,graph game,hypergraph,hypergraph game,Banzhaf valueChinese Library Classification F224.322010 Mathematics Subject Classification 90B35可转移效用合作对策1,简称TU-对策,描述的是所有参与者通过联盟进行合作,并产生相应的联盟效用。在这一框架下,任何有限参与者间都可以形成合作联盟,即任何联盟均是可行的。但现实中,由于受到各种因素的制约使得一些联盟并不能形成。基于此事实,Myerso
6、n(1 9 7 7)2 考虑合作限制,提出了具有图结构的合作对策,简称图对策,参与者表示为图中的节点,而参与者间的直接通讯关系表示为图中的边,并假设可行联盟仅在有边直接相接或存在路连通的参与者间形成。同时,Myerson提出了图对策的一个著名分配收稿日期:2 0 1 9-1 0-0 8*基金项目:国家自然科学基金(No.11971298)1.上海大学管理学院,上海2 0 0 444;School of Management,Sh a n g h a i U n i v e r s i t y,Sh a n g h a i 2 0 0 444,China十通信作者E-mail:16027卷吕文蓉
7、,单而芳规则,称之为Myerson值,该值由图限制对策中的Shapley值3给出。其次,Myerson2用公平性和分支有效性给出了该值的公理性刻画。随后,Myerson(1 9 8 0)4用平衡贡献性代替公平性给出了该值的另一种刻画。此后,具有限制的合作对策受到了研究者们的广泛关注,Myerson值也逐步被推广到超图5、概率图6、边赋权图7 和有向图8 等不同图结构中。1986年,Owen9开始考虑TU-对策联盟分配值与具有限制的合作对策联盟分配值之间的关系。一方面,Owen研究了Shapley值与Myerson值之间的关系;另一方面,Owen将目光转移到Banzhaf 值1 0,初步研究了图
8、限制对策中的Banzhaf 值。2 0 0 6 年,Alonso-Meijide和Fiestras-Janeirol在Owen工作的基础上,利用Meryson值的思想,提出了图对策Banzhaf值,该值由图限制对策中的Banzhaf值给出,并给出了图对策Banzhaf值的公理性刻画。超图是图的一种自然推广,在现实中是普遍存在的,它由节点集和超边集组成。与图中每条边恰由两个节点组成不同,在超图中,每条超边是节点集的一个子集,不同超边可以含有不同个数的节点。因此图是超图的一类特例。在合作对策中,超图的节点可视为参与者,而其超边可视为各类社会组织、行业协会和政治团体等团体和组织,因此超图结构可以描述
9、更为复杂的合作对策。本文旨在把图对策Banzhaf值推广到超图对策中,并提出超图对策Banzhaf值的公理性刻画。第1 节给出本文需要的基本定义和记号。第2 节给出超图对策Banzhaf值的表示式,并进行公理性刻画。第3节给出算例进行了分析。最后,总结了本文所做的工作并给出注记。1预备知识1.1TU-对策可转移效用合作对策,简称TU-对策,由二元组(N,)组成,其中N=1,2,n)表示参与者集合,表示特征函数,且规定(0)=0,是定义在2 NR上的一个映射。对N中任意非空子集S,u(S)表示联盟S中成员进行合作所产生的效用,集合S的基数由ISI表示。TU-对策是0-规范的,如果对于任意的iE
10、N,都有(i)=0。记所有 TU-对策的集合为VN,所有O-规范的TU-对策的集合为VN。对任意的SCN,(S,U Is)是由点集S 限制所构成的 TU-对策,这里对任意 T C S,有 uis(T)=u(T)。对于给定的参与者集合N和一个非空联盟 TN,一致性对策(N,uT)3 可定义为:若T S,则有 uT(S)=1;否则,有 uT(S)=0。为方便起见,对任意SN,我们将SU简记为SUi,S-简记为Si,并用对应的小写字母s表示S。另外,将(i,j,)简记为(i,j,k)。对于对策(N,u),一个支付向量是a=(1,a2,,a n)E R ,其中分量a;表示分配给参与者i的收益。TU-对
11、策的一个单值解或者值是一个函数f,它是指分配给任意(N,u)的一个支付向量f(N,u)E IRn,该值就是通常讲的分配规则。对于 TU-对策和任意的参与者iE N,最著名的单值有效解是Shapley值Sh(N,u)3,其定义如下:Shi(N,u)=s!(n-s-11)0(S U i)-(S),(1)n!SCN/1613期具有超图合作结构的Banzhaf值其中S是N中任意有限集,S=S。另一个著名的单值解是Banzhaf值Ba(N,u)12,,定义为:Ba:(N,)=2m-11,e(s Ua)-0(S)。(2)SCNIi1.2图、超图和图对策Banzhaf值图可以由(N,L)来表示,其中N称为图
12、的点集,而L称为图的边集,由N的一些无序二元子集所构成,也即LiNN:i 。为方便起见,本文将边 i,简记为订。超图5是图的一种自然推广,由二元组(N,H)组成,其中N是节点集,H是至少包含两个节点的超边集,即HHN=eCN:l e l 2。特别地,当lel=2时,超图就是普通图。(N,He)表示由(N,H)去掉超边e后形成的超图。记H,=eEHi E e)为H中包含节点i的超边集合,而H-i=eEH|i生e为H中不含节点i的超边的集合。在(N,H)中,如果iEe,我们称节点i与超边e是关联的。如果节点ijEe,e E H,则称节点i是邻接的。如果节点i,j间存在互异点列i=io,i,,i=j
13、,且对于l=1,2,k,都有i-1与i邻接,则称i,i是连通的。如果(N,H)中任意两点间都是连通的,则称(N,H)是连通的。对任意非空集合SN,联盟S的导出子超图表示为(S,H(S),其中 H(S)=eE HIe S)。当子超图(S,H(S)连通时,我们称 S是一个连通子集。在(N,H)中,一个分支是指它的一个极大连通子超图。用N/H表示(N,H)中所有分支的集合,而用S/H(S)表示由S所导出子超图的所有分支的集合。为方便起见,有时也将S/H(S)简记为S/H。超图对策由三元组(N,u,H)构成,其中(N,)表示TU-对策,(N,H)表示超图。在超图对策中,只有每条超边的参与者都参与某个联
14、盟时,可行联盟才可能形成,即连通的子集才能形成可行联盟。记N上所有超图对策的集合为HN。相应地,将所有0-规范超图对策的集合记为H。特别地,当H是一个图时,对应的对策称为图对策。如果对任意的(N,u,H)EHN都有唯一的支付向量f(N,H)ER,则称f为超图对策的一个解或者值。超图对策上的Myerson值4 是(N,u,H)上的一个解,定义为:i(N,u,H)=Sh;(N,u),其中,对于任意的TSN,u(T)=R E T/H(R),(N,u )被称为超图限制对策。如果用Banzhaf值来代替Myerson值中的Shapley值,就可得到另外的分配规则。2 0 0 6年,Alonso-Meij
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 具有 超图 合作 结构 Banzhaf
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。