具有超圖合作結構的賦權Position值

單而芳， 李 康， 劉 珍

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

0 引言

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

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

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

本文考慮超圖對策上的賦權Position值。通過推廣Haeringer[12]提出的賦權系統到超圖對策上，并在無圈超圖對策上給出了此類賦權Position值的公理化刻畫。這里的賦權系統在一定程度上反映參與者的交流能力或合作水平對他獲得支付或分攤成本的影響，也就是，參與者的權值越大，那么該參與者在分配中將獲得更多的支付；不過，如果是成本，則分攤更少的成本。這是與經典賦權系統的一個區別。為此，我們需要尋找一個合理的方式來度量所有參與者的交流能力或合作水平。在圖論和超圖理論中，點的度值是一個重要概念。每個點的度值等于包含這個點的超邊的數目,在某種意義上說,每個點的度值體現了該點代表的參與者的交流能力或合作水平。 因此,點的度值越大,則點代表的參與者的交流能力越強或合作水平越高。本文用點的度值來度量每條超邊中每個點的交流能力或合作水平,并結合Haeringer[12]提出的用于推廣Shapley值的賦權系統給出了一類新的賦權系統。該賦權系統特點是：當超邊的Shapley值為正值時,包含的參與者的度值越大，其獲得的支付越多；反之，當超邊的Shapley值為負值時，參與者的度值越大，則其分攤的成本越少。對無圈超圖對策，我們證明了賦權Position值可以由“分支有效性”、“冗余超邊性”、“超邊可分解性”、“擬可加性”、“弱積極性”和“弱能轉換”六個性質所唯一確定。

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

1 預備知識

1.1 TU-對策

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

(1)

1.2 超圖對策的賦權Position值

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

在超圖(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))稱為由聯盟S導出的子超圖，其中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是超圖對策的一個解。在圖對策Myerson的值[2,4](Myerson)和Position值(Meessen)的基礎上,van den Nouweland等[5]進一步給出了超圖對策(N,v,H)∈HN上Myerson值和Position值的定義。Myerson值μ可以表示為：

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

(2)

(3)

(4)

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

(5)

2 超圖對策的賦權值的刻畫

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

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

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

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

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

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

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

(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}})

弱能轉換簡單來說，當聯盟中所有參與者合作獲得的效用為正值時，若參與者k獲得的支付為Fk；那么當聯盟中參與者合作獲得的效用為負值時，該參與者k分攤的成為1/Fk。

本文分兩步證明了本文的主要結論，即超圖對策的賦權Position值是滿足上述六個公理的唯一解。第一步，當超圖對策為一致性對策時，超圖對策的賦權Position值是同時滿足分支有效性、擬可加性、冗余超邊性、超邊可分解性、弱積極性和弱能轉換六個性質的解。第二步，我們運用擬可加性證明賦權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)

對于特征函數ηv,我們有：

(8)

(9)

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

(10)

(11)

(12)

(13)

根據上式，我們有：

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

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

因為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)。

下面，我們用兩個定理對超圖對策的賦權Position值進行刻畫。

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

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

所以，我們有：

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

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

下面我們證明賦權Position值滿足唯一性。

(14)

(15)

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

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

(16)

=λS(ηv)uH(S)

3 超圖對策舉例分析

(17)

4 結論

本文我們研究了參與者的交流能力或合作水平與其在聯盟中利潤分配或成本分攤之間的關系，定義了超圖結構中利潤分配或成本分攤的一種方法，使得利潤分配或成本分攤更加合理。通過引入超圖結構中點的度值來度量每條超邊中每個參與者的交流能力或合作水平，并結合Haeringer提出用于推廣Shapley值的權重系統定義了一類新的權重系統。根據分支有效性、超邊可分解性、冗余超邊性、擬可加性、弱能轉換以及弱積極性六個性質公理刻畫了具有超圖合作結構的賦權Position值。我們發現參與者獲得的支付隨其度值的增加而增加，參與者分攤的成本則隨其度值的增加而降低。當然，除考慮用參與者的度來度量其交流能力或合作水平外，還可以用邊的度來度量用于交流的每條邊的交流容量或者能力，然后研究邊的度值對每條邊的利潤分配或成本分攤的影響，進而研究相應的Position值的公理化刻畫問題。