具有超图合作结构的Banzhaf值.pdf

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值。其次，证明了超图对策Banzhaf值满足分支可分解性、分支总贡献性、公平性、平衡贡献性以及隔离性，并给出了该值的两种公理性刻画。最后，举例分析了超图对策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 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 that 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 value of the hypergraph game.Keywords TU-game,graph game,hypergraph,hypergraph game,Banzhaf valueChinese Library Classification F224.322010 Mathematics Subject Classification 90B35可转移效用合作对策1，简称TU-对策，描述的是所有参与者通过联盟进行合作，并产生相应的联盟效用。在这一框架下，任何有限参与者间都可以形成合作联盟，即任何联盟均是可行的。但现实中，由于受到各种因素的制约使得一些联盟并不能形成。基于此事实，Myerson（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卷吕文蓉，单而芳规则，称之为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，初步研究了图限制对策中的Banzhaf 值。2 0 0 6 年，Alonso-Meijide和Fiestras-Janeirol在Owen工作的基础上，利用Meryson值的思想，提出了图对策Banzhaf值，该值由图限制对策中的Banzhaf值给出，并给出了图对策Banzhaf值的公理性刻画。超图是图的一种自然推广，在现实中是普遍存在的，它由节点集和超边集组成。与图中每条边恰由两个节点组成不同，在超图中，每条超边是节点集的一个子集，不同超边可以含有不同个数的节点。因此图是超图的一类特例。在合作对策中，超图的节点可视为参与者，而其超边可视为各类社会组织、行业协会和政治团体等团体和组织，因此超图结构可以描述更为复杂的合作对策。本文旨在把图对策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 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-对策的一个单值解或者值是一个函数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称为图的点集，而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，且对于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）表示超图。在超图对策中，只有每条超边的参与者都参与某个联盟时，可行联盟才可能形成，即连通的子集才能形成可行联盟。记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-Meijide 和Fiestras-Janeirol11 给出了图对策 Banzhaf 值 Ba(N,u,L)的定义:Bai(N,u,L)=Bai(N,u),其中（N,uL）表示图限制对策。2超图对策Banzhaf 值及其公理性刻画2.1超图对策Banzhaf值从1.2 节图对策Banzhaf值的定义可知，图对策Banzhaf值是借助图限制对策Banzhaf16227卷吕文蓉，单而芳值定义的分配规则。事实上，这一概念可进一步推广到超图上，下面给出超图对策Banzhaf值的定义。定义1 对任意的超图对策（N,u,H)EHN,超图对策Banzhaf值Ba(N,u,H)E Rn定义为：Ba;(N,u,H)=Ba;(N,)。(3)2.2超图对策Banzhaf值公理性刻画本节将给出超图对策Banzhaf值的公理性刻画。首先，将图对策Banzhaf 值满足的一些性质推广到超图对策中，并给出关于超图对策Banzhaf值的一些相关引理。分支可分解性：对任意的超图对策（N,u,H)，任意的SEN/H和iES，若分配规则fERn满足fi(N,U,H)=fi(S,Uis,H(S),则称f具有分支可分解性。这个性质是指：任何参与者所获得的收益等于他所在分支子对策中获得的收益。引理1 对于任意超图对策（N,u,H)EHN,Ba(N,u,H）满足分支可分解性。证明设iEN,且有SEN/H使得iES。由(3)式可得：1Bai(N,u,H)=Bai(N,uH),u(TUi)-H(T)2n-1TCNi1(R)-2(R)2n-1TCNi RE(TUi)/HRET/H1e(Tn S)Ui)-uH(Tn S)2n-1TCNi2n-s2n-1u(TUi)-u(T)TCSi128-1TCSi=Ba;(S,U/s,H(S),其中，由第三个等式可知参与者i的收益仅与i所在的分支有关，而T中与i相关的分支仅在TnS中，且S外的结构对联盟收益无影响，故可得第四、五个等式。所以Ba(N,H)满足分支可分解性，引理得证。分支总贡献性：对任意的超图对策（N,H）E H N和任意的SEN/H，若分配规则fERn满足Zfi(N,u,H)=128-1ZuH(T)-uH(Ti),iESiESTCSiET则称具有分支总贡献性。1633期具有超图合作结构的Banzhaf值这个性质是指：任何极大连通子超图（即分支S）的总收益等于S中每个参与者i对S中包含的所有联盟边际贡献的平均值的总和。引理2 对任意超图对策（N,u,H)EHN,Ba(N,u,H)满足分支总贡献性。证明任意超图对策（N,U,H)EHN及SEN/H，由分支可分解性可得：Z Ba;(N,H)=Ba;(N,/s,H(S)=ZEBa;(N,usHS)iESiESiES125-1iESTCSiET1Zu(T)-uH(Ti)。2s-1iESTCSiET所以Ba(N,u,H)满足分支总贡献性，引理得证。公平性：对任意的超图对策（N,H)EHN，任意的eEH以及i,jEe,若分配规则fERn满足fi(N,u,H)-fi(N,H e)=f;(N,u,H)-fi(N,u,H e),则称于具有公平性。这个性质是指：去掉超边e，对e中所包含的每个参与者的影响是相同的。引理3对任意超图对策（N,H)EHN，Ba(N,H)满足公平性。证明任意超图对策（N,H)H,有H 且iie,考虑TN(i,j)。由(3)式得：Ba;(N,u,H)-Ba,(N,u,H)=Ba;(N,uH)-Ba,;(N,uH)11,0(S.)-(s)2n-1SiCNiS2CN1uH(TUiUi)+H(TUi)-H(TUj)-H(T)2n-1TCN(i,)1H(TUjUi)+uH(TUi)-H(TUi)-H(T)2n-1TCN(i,j)1uH(TUi)-uH(TUj),2n-2TCN(i,j)即：1Bai(N,H)-Baj(N,u,H)=2n-2uH(TUi)-H(TUj)。TCN(i,j)同理可得：Ba:(N,u,H e)-Ba;(N,u,H e)=2m-2,1eHe(TUi)-He(TUj)。TCN(i,j)16427卷吕文蓉，单而芳当TNi,时,有H(TUk)=He(TUk),这里=i,j。于是Bai(N,u,H)-Ba;(N,v,H)=Ba;(N,u,He)-Bai(N,u,H e)。所以Ba(N,u,H)满足公平性，引理得证。定理1 对任意的超图对策（N,u,H)EHN，超图对策Banzhaf值Ba(N,u,H）可由分支总贡献性和公平性唯一确定。证明对任意的（N,u,H）E H N，根据引理1 和2 可知：超图对策Banzhaf 值Ba(N,u,H)E Rn 满足分支总贡献性和公平性。现证Ba(N,H）是满足分支总贡献性和公平性的唯一值。假设存在分配规则满足分支总贡献性和公平性，对|H|用数学归纳法。若|H|=0，也就是空超图。此时，每个节点iEN都是一个分支，由分支总贡献性可得：pi(N,v,H)=v(i)=Bai(N,H)。现假设对任何超图H,当|H|i)。iENiENTSNiET因此，超图对策Banzhaf 值满足分支总贡献性。考虑公平性，不妨以参与者5,6 为例。注意到Bas(N,u,He3)=O;Bas(N,u,He3)=。容易验证:4Bas(N,u,H)-Bas(N,u,H e3)Ba6(N,u,H)-Ba6(N,u,H e3)。32因此，超图对策Banzhaf值满足公平性。最后，以参与者1,4为例验证平衡贡献性。通过计算可得：4Bai(N,u,H-4)=O;Ba4(N,u,H-1)322Bai(N,u,H)-Bai(N,u,H-4)=Ba4(N,u,H)-Ba4(N,u,H_1)。32即超图对策Banzhaf值满足平衡贡献性。16827卷吕文蓉，单而芳4结论及注记本文提出了超图对策Banzhaf值的定义，并通过公平性和分支总贡献性，给出了超图对策Banzhaf 值唯一性的刻画。同时，利用平衡贡献性代替公平性给出了超图对策Banzhaf值唯一性的另一种刻画。最后，讨论了超图对策Banzhaf值与图对策Banzhaf值所满足性质上的不同之处。注意到由于图对策是一种特殊的超图对策，此时每条边恰有两个元素。虽然在图对策中，Banzhaf值满足合并性（或者称为边收缩性)，但对超图而言，因超边结构的复杂性，收缩一条超边为一个点时可能会导致其结构发生质的改变，而破坏“超边收缩性”。另外，vandenNouweland等将Position值推广到了超图结构中5，对于任意的O-规范超图对策（N,u,H）E H，其Position值定义为1;(N,U,H)=She(H,uN),eEH;其中，对于任意的HCH,UN(H)=DREN/Hi(R)，（N,u N）被称为超边对策。事实上，也可以用Banzhaf值等来代替上述Position值中的Shapley值，从而得到新的分配规则。在文献1 3中图对策上对应Banzhaf 值的Position值已被提出，其定义为：Yi(N,u,L)=ZleLBa(N,uN)。不过，该值的刻画还有待解决。最近，超图对策中的广义Positon值1 4也被提出并刻画。参考文献1 Branzei R,Dimitrov D,Tijs S.Models in Cooperative Game Theory M.Berlin:Springer,2008.2 Myerson R B.Graphs and cooperation in games J.Mathematics of Operations Research,1977,2(3):225-229.3 Shapley L S.A value for n-person games M/Contributions to the Theory of Games.Prince-ton:Princeton University Press,1953:307-317.4 Myerson R B.Conference structures and fair allocation rules J.International Journal of GameTheory,1980,9(3):169-182.5 van den Nouweland A,Borm P,Tijs S.Allocation rules for hypergraph communication situa-tions J.International Journal of Game Theory,1992,20(3):255-268.6 Calvo E,Lasaga J,van den Nouweland A.Values of games with probabilistic graphs J.Math-ematical Social Sciences,1999,37(1):79-95.7 Gonzalez-Arangjena E,Manuel C M,Pozo M D.Values of games with weighted graphs J.European Journal of Operational Research,2015,243(1):248-257.8 Khmelnitskaya A,Selcuk O,Talman D.The Shapley value for directed graph games J.Oper-ations Research Letters,2016,44(1):143-147.9 Owen G.Values of graph-restricted games J.Society for Industrial and Applied Mathematics,1986,7(2):210-220.10 Owen G.Multilinear extensions and the Banzhaf value J.Naval Research Logistics Quarterly,1975,22(4):741-750.11 Alonso-Meijide J M,Fiestras-Janeiro M G.The Banzhaf value and communication situationsJ.Naval Research Logistics,2006,53(3):198-203.12 Lehrer E.An axiomatization of the Banzhaf value J.International Journal of Game Theory,1988,17(2):89-99.13 Gomez D,Gonzalez-Aranguena E,Manuel C,et al.Centrality and power in social networks:A game theoretic approach J.Mathematical Social Sciences,2003,46(1):27-54.14】李思文，赵加贵，单而芳.超网络博奔的位置值的公理化刻画J.运筹学学报，2 0 1 9,2 3(4)：1 6 5-1 7 4.