具有超圖合作結(jié)構(gòu)的賦權(quán)Position值

單而芳， 李 康， 劉 珍

(上海大學(xué) 管理學(xué)院，上海 200444)

0 引言

經(jīng)典的可轉(zhuǎn)移效用的合作對策(TU-對策)[1]通常假定任何參與者的集合都可以形成一個合作聯(lián)盟，并獲得相應(yīng)的收益。然而，在現(xiàn)實生活中，由于受到不同文化宗教背景的影響以及社會階層、技術(shù)或組織機構(gòu)等因素的制約，一些聯(lián)盟無法形成。為此，Myerson[2]提出并研究了以圖作為合作結(jié)構(gòu)的TU-對策，其中圖的節(jié)點表示參與者，邊表示它的兩個端點所代表的參與者之間存在某種雙邊關(guān)系，并假定只有相互連通的參與者集合可以形成聯(lián)盟。Myerson[2]通過定義“圖限制對策”，并把圖限制對策的Shapley值作為圖對策的一個解，這就是著名的Myerson值。Myerson[2]首先給出了Myerson值的一個公理化刻畫。之后，Born等[3]又給出了Myerson值的另一個公理化刻畫。Myerson[4]和等van den Nouweland等[5]也把Myerson值推廣到具有超圖合作結(jié)構(gòu)的情形。

1988年，Meessen[6]提出了圖對策中另一個重要的分配規(guī)則，即Position值。為了定義Position值，他首先引入了“邊對策”的概念，邊對策是將每個邊集作為參與者的集合，并假定當(dāng)某個邊集導(dǎo)出的子圖連通時，才能形成聯(lián)盟。在此基礎(chǔ)上，首先計算邊對策中每條邊的值Shapley[7]，然后把每條邊的Shapley值平均分配給它的兩個端點，給每個參與者的支付(payoff)等于分配給它的所有邊Shapley值一半的和，這就是Position值。1992年，van den Nouweland等[5]進(jìn)一步把Position值推廣到超圖對策上，并給出了無圈超圖對策上Position值的刻畫。該模型把圖中每條邊或者超圖中每條超邊的Shapley值平均分配給邊上或者超邊中的點，而不考慮每個點的交流能力或合作水平，也就是把所有參與者看成是對稱的。

然而，在實際中，聯(lián)盟中的參與者可能有不同的議價能力、交流能力或合作水平。Shapley[8]首先提出并研究了賦權(quán)Shapley值。聯(lián)盟中對每個參與者的支付按照該參與者所占的權(quán)重比例進(jìn)行分配。此后，Owen[9]、Kalai和Samet[10]、Chun[11]以及Haeringer[12]等作者對賦權(quán)Shapley值做了進(jìn)一步研究，按照不同的權(quán)比例給出了不同解的形式。這些研究的共同特點是每一個參與者賦予一個正的權(quán)重，在每個聯(lián)盟中按權(quán)重比例對紅利進(jìn)行分配。此時，參與者的權(quán)重越大，其獲得的支付或分?jǐn)偟某杀疽苍蕉?。Haeringer[13]把賦權(quán)系統(tǒng)推廣到圖對策上，并刻畫了賦權(quán)Myerson值。而Slikker和van den Nouweland[14]則把Kalai和Samet提出的賦權(quán)系統(tǒng)推廣到Myerson值，并給出了它的公理化刻畫。

本文考慮超圖對策上的賦權(quán)Position值。通過推廣Haeringer[12]提出的賦權(quán)系統(tǒng)到超圖對策上，并在無圈超圖對策上給出了此類賦權(quán)Position值的公理化刻畫。這里的賦權(quán)系統(tǒng)在一定程度上反映參與者的交流能力或合作水平對他獲得支付或分?jǐn)偝杀镜挠绊懀簿褪?，參與者的權(quán)值越大，那么該參與者在分配中將獲得更多的支付；不過，如果是成本，則分?jǐn)偢俚某杀?。這是與經(jīng)典賦權(quán)系統(tǒng)的一個區(qū)別。為此，我們需要尋找一個合理的方式來度量所有參與者的交流能力或合作水平。在圖論和超圖理論中，點的度值是一個重要概念。每個點的度值等于包含這個點的超邊的數(shù)目,在某種意義上說,每個點的度值體現(xiàn)了該點代表的參與者的交流能力或合作水平。 因此,點的度值越大,則點代表的參與者的交流能力越強或合作水平越高。本文用點的度值來度量每條超邊中每個點的交流能力或合作水平,并結(jié)合Haeringer[12]提出的用于推廣Shapley值的賦權(quán)系統(tǒng)給出了一類新的賦權(quán)系統(tǒng)。該賦權(quán)系統(tǒng)特點是：當(dāng)超邊的Shapley值為正值時,包含的參與者的度值越大，其獲得的支付越多；反之，當(dāng)超邊的Shapley值為負(fù)值時，參與者的度值越大，則其分?jǐn)偟某杀驹缴佟o圈超圖對策，我們證明了賦權(quán)Position值可以由“分支有效性”、“冗余超邊性”、“超邊可分解性”、“擬可加性”、“弱積極性”和“弱能轉(zhuǎn)換”六個性質(zhì)所唯一確定。

本文第二節(jié)將介紹-對策和超圖對策的一些基本定義和記號，并給出了超圖對策賦權(quán)Position值的表達(dá)式。第三節(jié)對無圈超圖對策上賦權(quán)Position值進(jìn)行公理化刻畫。第四節(jié)舉例說明了超圖對策中賦權(quán)Position值的六個性質(zhì)。第五節(jié)對研究的結(jié)論做了總結(jié)。

1 預(yù)備知識

1.1 TU-對策

具有特征函數(shù)形式的合作對策通常稱為可轉(zhuǎn)移效用的合作對策，簡記TU-對策[1]。TU-對策可以用一個二元組(N,v)來表示，其中N=(1,2,…,n)為參與者(player)的集合，v表示特征函數(shù)(characteristic function)，它是從集族{S:S?N}到實數(shù)R的一個映射，即v:2N→R，且v(?)=0。N的任意子集S表示由S中的參與者形成的聯(lián)盟(coalition)。v(S)表示聯(lián)盟S的效用(worth)，|S|表示集合S的基數(shù)。 如果對所有的i∈N，都有v({i})=0，我們稱TU-對策(N,v)是0-規(guī)范的(0-normalized)。以下討論中涉及的對策均指0-規(guī)范的TU-對策。

(1)

1.2 超圖對策的賦權(quán)Position值

超圖(hypergraph)[5]是一個二元組(N,H)，其中N是點集，H?{e?N:|e|≥2}表示超邊(hyperlink)集。如果超圖的每條超邊均是二元子集，則該超圖也稱為圖。Hi={e∈H|i∈e}為(N,H)中包含點i的超邊的集合。進(jìn)一步，定義參與者i的度(degree)為|Hi|，記為di。因此di表示包含點i的超邊的數(shù)目。超圖(N,H)中的每一條超邊e∈H可以表示一個conference結(jié)構(gòu)[5]，只有參加同一個conference結(jié)構(gòu)[5]的參與者才可以形成特定交流。在實際中，超邊可以代表某種社會組織，例如：行業(yè)協(xié)會和社團(tuán)等，每個參與者可以參加多種行業(yè)組織或社團(tuán)，并參與不同聯(lián)盟的合作。

在超圖(N,H)中，一條長度為k的路(path)是指一個點邊交錯序列(i1,e1,i2,e2,…,ik,ek,ik+1)。這里i1,i2,…,ik+1表示不同的參與者，e1,e2,…,ek表示不同的超邊，且對任意1≤1≤k,{il,il+1}∈el。特別地，如果這條路的始點i1和終點ik+1相同，則稱它為圈。在(N,H)中，如果兩個點i,j間存在一條路(i=i0,i1,…,ik=j)，那么稱點i和j點是連通的。如果(N,H)中任意兩個點都是連通的，則稱(N,H)是連通的。對于任意j∈N，本文令ej表示超圖對策(N,H)中任意一條超邊，且對于任意的點i,j,…,n∈N，超邊ej={i,j,…,n}。對于任意非空集合S?N，(S,H(S))稱為由聯(lián)盟S導(dǎo)出的子超圖，其中H(S)={e∈H|e?S}。對于任意H′?H，(N,H′)稱為(N,H)的一個部分超圖。在(N,H)中，C稱為(N,H)的一個分支，即C是一個極大的連通子超圖，我們記所有分支的集合為N/H。為了方便起見，對S?N，記S/H(S)為S/H。對于任意分支C∈N/H，我們用H(C)表示分支C中超邊的集合。

三元組(N,v,H)表示一個超圖對策(hypergraph game)，它是由一個TU-對策(N,v)和一個超圖(N,H)兩部分組成。記參與者為N的所有超圖對策(N,v,H)的集合為HN。如果對于任意的超圖對策(N,v,H)∈HN都有唯一的支付向量F(N,v,H)∈RN，我們稱F是超圖對策的一個解。在圖對策M(jìn)yerson的值[2,4](Myerson)和Position值(Meessen)的基礎(chǔ)上,van den Nouweland等[5]進(jìn)一步給出了超圖對策(N,v,H)∈HN上Myerson值和Position值的定義。Myerson值μ可以表示為：

μ(N,v,H)=Sh(N,vH)

(2)

(3)

(4)

在刻畫超圖對策上賦權(quán)Position值之前，我們先給出一個引理，它是由Borm[3]提出的，它闡述了邊對策的一致性系數(shù)和聯(lián)盟對策的一致性系數(shù)兩者之間的關(guān)系。

(5)

2 超圖對策的賦權(quán)值的刻畫

在本小節(jié)，我們給出任意超圖對策的賦權(quán)Position值的公理化刻畫。首先，我們給出六個基本性質(zhì)公理.。第一個性質(zhì)是經(jīng)典的分支有效性[4,5]。

分支有效性表示對(N,H)的每一個分支C，分配給該分支中所有參與者的支付之和恰好等于該分支的效用v(C)。

F(N,v,H)=F(N,v,H{e})

Borm[3]定義了冗余邊性質(zhì)：對于任意的邊集A?L，如果rv(A)=rv(A{i,j})，則稱邊{i,j}∈L是冗余邊。冗余超邊性質(zhì)是對Borm[3]定義的冗余邊性質(zhì)從圖到超圖的自然推廣。

超邊可分解性建立在van den Brink[15]提出的邊一致性對策基礎(chǔ)上。邊一致性對策可以看作一個否決情況；為了終止一個提議，邊L鄰接的兩個參與者必須完全同意，滿足該性質(zhì)的邊對策為邊一致性對策。邊L一致性對策的公式為：

我們將邊一致性對策推廣到超圖中，得到超邊一致性對策的公式：

在超邊一致性對策中，超邊可分解性確保超邊的效用只能在同一條超邊中的參與者之間轉(zhuǎn)移。

(6)

Fi(N,uej,{{ej}})×Fi(N,-uej,{{ej}})

=Fj(N,uej,{{ej}})×Fj(N,-uej,{{ej}})

=…=Fn(N,uej,{{ej}})×Fn(N,-uej,{{ej}})

弱能轉(zhuǎn)換簡單來說，當(dāng)聯(lián)盟中所有參與者合作獲得的效用為正值時，若參與者k獲得的支付為Fk；那么當(dāng)聯(lián)盟中參與者合作獲得的效用為負(fù)值時，該參與者k分?jǐn)偟某蔀?/Fk。

本文分兩步證明了本文的主要結(jié)論，即超圖對策的賦權(quán)Position值是滿足上述六個公理的唯一解。第一步，當(dāng)超圖對策為一致性對策時，超圖對策的賦權(quán)Position值是同時滿足分支有效性、擬可加性、冗余超邊性、超邊可分解性、弱積極性和弱能轉(zhuǎn)換六個性質(zhì)的解。第二步，我們運用擬可加性證明賦權(quán)Position值滿足唯一性。然而，如例1所示，存在某些情況不滿足擬可加性。

例1假如存在一個超圖對策(N,v,H)，N={1,2,3,4,5}，v=2u{1,4}-3u{1,2,3,4,5},H={{1,2,3},{3,4,5}}，那么，r2u{1,4}=∑A∈H0uA+2uH，r-3u{1,2,3,4,5}=∑A∈H0uA-3uH，因此得，λH(r2u{1,4})λH(r-3u{1,2,3,4,5})<0。由擬可加性可知，超圖對策(N,2u{1,4},H)和(N,-3u{1,2,3,4,5},H)不可比較。

(7)

對于特征函數(shù)ηv,我們有：

(8)

(9)

為了方便接下來的證明，本文又提出兩個引理，并給出初步結(jié)論。

(10)

(11)

(12)

(13)

根據(jù)上式，我們有：

因此，對于任意的邊集A?H，我們有rχ(A)=0。假設(shè)H=?，因為TU-對策[1](N,χ)是0-規(guī)范的；結(jié)合分支有效性，對于任意i∈N，我們有Fi(N,χ,H)=v({i})=0。假設(shè)H≠?，由于TU-對策[1](N,χ)是0-規(guī)范的；結(jié)合分支有效性，對于任意的參與者i∈NN(H)，F(xiàn)i(N,χ,H)=0，接下來，考慮對于任意的分支C∈N/H，令|C|>1，我們有：

因為對于任意的邊集A?H，rχ(A)=0；所以(N,χ,H)是超邊一致性對策。結(jié)合超邊可分解性和分支有效性，我們有：

因為H(C)≠?，因此c=0，但這與條件|C|>1矛盾。 因此，對于任意i∈N,Fi(N,χ,H)=0。那么，我們有：F(N,χ+ηv,H)=F(N,χ,H)+F(N,ηv,H)=F(N,ηv,H)。

下面，我們用兩個定理對超圖對策的賦權(quán)Position值進(jìn)行刻畫。

=rv(H(C))=v(c)

第三個等式相等，因為Shapley值滿足冗余超邊性質(zhì)。

所以，我們有：

同理，對于任意點i,j,…,n∈N和任意的超邊ej={i,j,…,n}，及任意的超圖對策(N,-uej,{{ej}})，我們有：

第五，本文可以明顯看出賦權(quán)Position值滿足弱積極性，因此不作證明。

下面我們證明賦權(quán)Position值滿足唯一性。

(14)

(15)

已知超邊對策為超邊一致性對策，根據(jù)引理2，我們有：

根據(jù)式(14)，對于任意的超邊ej∈Hi，我們有:

(16)

=λS(ηv)uH(S)

3 超圖對策舉例分析

(17)

4 結(jié)論

本文我們研究了參與者的交流能力或合作水平與其在聯(lián)盟中利潤分配或成本分?jǐn)傊g的關(guān)系，定義了超圖結(jié)構(gòu)中利潤分配或成本分?jǐn)偟囊环N方法，使得利潤分配或成本分?jǐn)偢雍侠怼Ｍㄟ^引入超圖結(jié)構(gòu)中點的度值來度量每條超邊中每個參與者的交流能力或合作水平，并結(jié)合Haeringer提出用于推廣Shapley值的權(quán)重系統(tǒng)定義了一類新的權(quán)重系統(tǒng)。根據(jù)分支有效性、超邊可分解性、冗余超邊性、擬可加性、弱能轉(zhuǎn)換以及弱積極性六個性質(zhì)公理刻畫了具有超圖合作結(jié)構(gòu)的賦權(quán)Position值。我們發(fā)現(xiàn)參與者獲得的支付隨其度值的增加而增加，參與者分?jǐn)偟某杀緞t隨其度值的增加而降低。當(dāng)然，除考慮用參與者的度來度量其交流能力或合作水平外，還可以用邊的度來度量用于交流的每條邊的交流容量或者能力，然后研究邊的度值對每條邊的利潤分配或成本分?jǐn)偟挠绊懀M(jìn)而研究相應(yīng)的Position值的公理化刻畫問題。