单而芳, 谢娜娜, 王光明,2

(1.上海大学 管理学院,上海 200444; 2.济南大学 数学科学学院,山东 济南 250022)

0 引言

经典可转移效用的合作博弈，简称为TU-博弈[1]，描述了任何有限个参与者都可以形成合作联盟并产生相应的效用。然而，在实际中，由于受到不同文化、宗教背景、社会阶层以及技术或者组织结构等的限制使得一些联盟并不能形成。基于此事实，Myerson[2]提出了具有图结构的合作博弈，简称为图博弈。在图博弈中，图的结点表示参与者，而图的每条边表示该条边的两个端点代表的参与者之间存在直接的双边协议或者通讯联系，并假设只有通过路相互连通的参与者才能形成可行联盟。Myerson把图限制博弈的Shapley值[3]作为一个新的分配规则，也即Myerson值，并利用公平性和分支有效性给出了Myerson值的唯一性刻画[2]。此后，图博弈的研究得到广泛关注。关于最近的Myerson值的研究进展参看[4～8]。

1988年，Meessen[9]提出了图博弈中另一个重要的分配规则，也就是Position值。它是首先将图博弈中的所有边看成“参与者”，计算出每条边的Shapley值，然后把每条边的Shapley值平均分配给它的两个端点，给每个参与者的支付等于分配给它的所有边Shapley值一半的和。Borm等[10]在无圈图博弈上给出了该值的公理化刻画。van den Nouweland等[11]和Algaba等[12]分别把Position值推广到超图博弈和并稳定系统博弈中，并在无圈超图博弈和一类并稳定系统博弈上分别给出了该值的公理化刻画。直到2005年，Slikker[13]才给出了任意图博弈上Position值的公理化刻画，他证明了Position值能够被分支有效性和平衡边贡献性所唯一刻画。迄今，任意超图博弈上Position值的公理化刻画问题仍未能解决。关于Position值的研究进展参看[14～17]。

在实际中，参与者往往具有不同的个人特征，如讨价还价能力，投入的努力程度等。此外，超图中的超边通常也具有不同的物理特征，如合作的能力，组织或团体的规模，关系的亲密程度或强度，建立或维持超边的成本等。基于参与者的不同特征，Shapley提出了赋权值Shapley值[18]。而后，Haeringer[19]，Slikker和van den Nouweland[20]将赋权Shapley值推广到图博弈和分层结构中。最近，Gonzalez-Aranguena[21]根据赋权的不同解释研究了赋权图限制博弈和推广的Myerson值。Ghintran[22]将Position值推广到概率图博弈，Ghintran[23]利用图博弈中允许参与者获得不同的边Shapley值这种转换机制推广了Position值。

本文旨在给出超图博弈上赋权Position值的公理化刻画。为此，通过考虑赋权超图博弈，引入了“赋权平衡超边贡献”公理，并结合经典的“分支有效”性质，给出了赋权超图博弈上Position值的公理化刻画。作为推论，我们得到了超图博弈上Position值的公理化刻画，同时页推广了Slikker的结论。最后，通过例子对刻画公理进行了说明，并与Myerson值进行了比较。

本文第一节将介绍TU-博弈、图博弈和超图博弈的一些基本定义和记号，并给出了超图博弈赋权Position值的表达式。第二节提出本文关键的公理——赋权平衡超边贡献，并给出超图博弈上赋权Position值的公理化刻画。第三节考虑了图博弈上具有“度”赋权的Position值，并对Position值和Myerson值做了比较分析。

1 预备知识

1.1 TU-博弈

可转移效用的合作博弈，简称为TU-博弈，可由二元组(N,v)来表示，其中N表示参与者的集合，v表示特征函数，它是{S:S⊆N}到实数集R的一个映射，即v:2N→R，且规定V(ø)=0。N的任意子集S表示由S中的参与者形成的联盟。v(S)表示联盟S的效用，|S|表示集合S的基数。

对于任意一个博弈(N,v)和一个非空联盟T⊆N，限制在参与者集合的子博弈(T,vT)定义为：对于所有的S⊆T,vT(S)=v(S)，如果对任意的i∈N，都有v({i})=0，则称该TU-博弈(N,v)是0-规范的，每个TU-博弈都可以转化为一个0-规范博弈[1]。以下讨论中涉及的博弈均指0-规范的TU博弈。

称为Harsanyi红利[25]。对TU-博弈，最著名的有效单值解是Shapley值。对于任意一个博弈(N,v)和任意参与者i∈N，Shapley值可以表示为

(1)

考虑到参与者之间的非对称性，Shapley将Shapley值推广为赋权的情况。记θ=(θi)i∈N∈R+为参与者的赋权，博弈的赋权Shapley值:

(2)

显然，当对所有的i,j,θi=θj时，方程(1)和(2)是等价的，即当所有参与者具有相同的赋权时，赋权Shapley值即为Shapley值。

1.2 超图和图博弈的Position值

超图是一个二元组(N,H)，其中H⊆HN={e⊆N=|e|≥2}表示至少包含两个参与者的超边集合。Hi:={e∈H|i∈e}为(N,H)中包含参与者i的超边的集合，参与者i的度记为|Hi|。(N,H)中的每条超边e∈H都表示一个conference结构。在实际中，超边可以代表某种社会组织，如行业协会、企业集团等。每个参与者可以参加多种行业组织或企业集团，并参与不同联盟的合作。若超图中的每条超边都包含个参与者，即对任意的e∈H,|e|=r则称此超图是r-一致的。对任意S⊆N,(S,H(S))称为由联盟S导出的子超图，其中H(S)={e∈H|e⊆S}。

在(N,H)中，若i∈e，则称参与者i与超边是e∈H关联的; 如果存在超边e∈H，满足i,j∈e，则称参与者i和参与者j是邻接的。如果存在一个点边序列i=i1,e1,i2,e2,…,ik,ek,ik+1=j，使得对l=1,2,…,k都有il,il+1∈el，那么称是点i和j是连通的。如果超图中任意两个点都是连通的，则称超图是连通的。对于任意非空集合S⊆N,(S,H(S))称为由联盟S导出的子超图，其中H(S)={e∈H|e⊆S}。如果(S,H(S))是(N,H)中的连通子超图，则称联盟S是联通的。超图的每个极大连通子集称为一个分支。(N,H)中分支的集合记为N/H，包含i的分支记为(N/H)i。对H′⊆H,(N,H′)称为(N,H)的一个部分超图。S的所有分支的的集合记为S/H。对每一个分支C∈N/H，用H(C)表示包含在C中的超边集。

超图博弈是指一个三元组(N,v,H)，它是由TU-博弈(N,v)和描述通讯可能性的超图(N,H)两部分所组成。记参与者为N的所有超图博弈(N,v,H)的集合为HN。

特别的，特别的，如果超图的每条超边e都有|e|=2，则超图即为普通图。此时对应的超图博弈称为图博弈。为了区别图和超图，用L表示图的边集，并记所有图博弈(N,v,L)的集合为GN。

通过引入“平衡边贡献性”，并结合“分支有效性”，Slikker[13]给出了任意图博弈上position值的公理性刻画。

1.3 超图博弈的赋权Position值

超图博弈的一个分配规则或值f(N,v,H)是定义在HN上的映射，它是一个n维向量。在图博弈中，Myerson值和Position值是两个重要的分配规则。van den Nouweland等[11]将Myerson值和Position值推广到超图博弈。对参与者i∈N，超图博弈的Myerson值μ定义为:

μi(N,v,H)=Shi(N,vH)

(3)

而超图博弈上的Position值π定义为:

(4)

在Position值的定义中，超边的Shapley值平均分配给本超边的所有参与者。正像引言中指出的，在实际中参与者和超边可能具有不同的特征，也即在参与者之间或超边之间的平均处理不能反映实际中的非对称性。

定义1对具有赋权结构w=(θ,σ)的任意超图博弈(N,v,H)∈HN以及任意的i∈N，定义超图博弈赋权Position值为

(5)

Position值是在对称的假设前提下，参与者平均分配其所在的超边的Shapley值，而赋权Position值是在非对称的假设前提下，参与者根据其赋权分配其所在超边的Shapley值，且利用赋权Shapley值体现超边的非对称性。

2 赋权超图博弈Position值的公理性刻画

本节通过引入“赋权平衡超边贡献”这一关键公理，并结合经典的“分支有效”公理，给出了赋权超图博弈Position值的公理化刻画。

首先，给出两个基本性质公理。记f是定义在超图博弈HN上的一个分配规则。

在图博弈中，Slikker[13]为了给出Position值的公理化刻画，引入了平衡边贡献公理。而在超图博弈中，每条超边可能包含多个参与者，包含参与者i的超边断裂所造成的参与者j支付的差异，不仅与参与者i有关，还与包含它的超边所包含的其它参与者有关。此外，每位参与者和每条超边的非对称性也应当被充分考虑。基于此，我们提出了“赋权平衡超边贡献”这一新的公理。假定参与者i对参与者j支付的总贡献为任意断裂所有包含i的超边造成的参与者j的支付差异的总和。赋权平衡超边贡献是指，对两个任意参与者i和j，参与者i对参与者j支付的总贡献等于参与者j对参与者i支付的总贡献。具体地。

赋权平衡超边贡献:对于任意(N,v,H)∈HN和赋权结构w=(θ,σ)，对任意i,j∈N，有

这个公理在后面赋权Position值的刻画中起着关键的作用。显然，当赋权超图博弈限制为普通图博弈时，赋权平衡超边贡献公理即为平衡边贡献公理。下面举例说明赋权平衡超边贡献:

例1设超图博弈(N,v,H)，其中N={1,2,…,5},v=u{1,4,5},H={{1,2,3},{2,4},{3,5}}。记e1={1,2,3},e2={2,4};e3={3,5},w(θ,σ)，其中θ=(1,2,2,1,1)，σ=(3,2,3)。则

令w=(θ,a)和w(b,σ)(其中a,b是常向量)，πθ和πσ分别是各自赋权超图博弈Position值，通过计算，可得:

超边Aπw(N,v,A)πθ(N,v,A)πσ(N,v,A)A=H(340,1960,25,112,18)(115,1645,1645,19,19)(18,14,516,18,310)A⊂H(0,0,0,0,0)(0,0,0,0,0)(0,0,0,0,0)

为了证明赋权超图博弈Position值πw满足分支有效和赋权平衡超边贡献这两个公理，根据第一节给出的无异议博弈，我们给出下面的引理，它给出了超图博弈的Position值的另一种表达形式。

根据引理3.1，可以证明πw满足分支有效和赋权平衡超边贡献这两个性质：

引理3.2对于任意超图博弈(N,v,H)∈HN及其赋权结构w=(θ,σ)，Position值πw满足分支有效和赋权平衡超边贡献性质。

由引理3.2，可以给出赋权超图博弈Position值的公理化刻画：

定理3.3对于任意超图博弈(N,v,H)∈HN及其赋权结构w=(θ,σ)，其Position值πw是满足分支有效和赋权平衡超边贡献公理的唯一解。

注1考虑非赋权或常向量赋权Position值，此时赋权平衡超边贡献退化为局部平衡超边贡献，即

局部平衡超边贡献:对于任意超图博弈(N,v,H)∈HN和i,j∈N，有

定理3.3说明超图博弈的Position值可以被分支有效性和局部平衡超边贡献性所唯一刻画。

例2设(N,v,H)∈HN，这里N={1,…,8},v=u{2,3,4},H={{1,4,7},{2,5},{3,6,8},{5,7,8}}。令e1={1,4,7},e2={2,5},e3={3,6,8},e4={5,7,8}。

根据Position值和Myerson值的定义，计算可得值π和μ值的分配结果如下。

超边Aπ(N,v,A)μ(N,v,A)A=H(112,18,112,112,524,112,16,16)(18,18,18,18,18,18,18,18)AH(0,0,0,0,0,0,0,0)(0,0,0,0,0,0,0,0)

3 具有度赋权的Position值

本节讨论一类特殊图博弈赋权Position值。图博弈(N,v,L)中，参与者关联的边数称为此参与者的度。Shan[26]发现参与者的度明显地反映了此参与者某种意义上的合作能力，即度越大的参与者应该越依赖合作。这意味着度较大的参与者比度较小的参与者获得更多支付，同时在边断开时受到的影响更大。

设θ=(d1,d2,…,dn)，其中di是参与者i在(N,L)中的度，n=|N|,(N,v,L),σ=a,a是常向量。我们用πd代替方程 (5) 中的πw:

度赋权Position值是指将边的Shapley值根据度的比例分配给此边的两个参与者。

下面的例子说明度越大的参与者应该对合作的依赖程度越大。

例3设图博弈(N,v,L)，其中N={1,2,…,5}，v是一致博弈u{1,2,3}，L={{1,4},{2,5},{3,5},{4,5}}。计算限制博弈得:

类似地，计算边博弈可得:

易验证关于度的Position值满足分支有效性和赋权平衡边贡献。表1中列出了几个子图的度赋权Position值。例如，参与人4对参与人1 的总贡献:

表1 关于度的Position值，Position值，Myerson值

参与人1对参与人4的总贡献:

由于(d1,d2,d3,d4,d5)=(1,1,1,2,3)，参与者5和参与者4关于度的Position值比Position值和Myerson值大。

4 结论

本文考虑了赋权超图博弈并提出了赋权Position值的概念，通过引入赋权平衡超边贡献公理并结合经典的分支有效公理给出了赋权超图博弈Position值的公理化刻画。作为推论，解决了超图博弈Position值的刻画问题。最后，以图博弈上的度赋权Position值为例，说明了度越大的参与者对合作的依赖程度越大。