單而芳， 李 康， 劉 珍

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

0 引言

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

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

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

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

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

1 預(yù)備知識(shí)

1.1 TU-對(duì)策

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

(1)

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

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

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

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

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

(2)

(3)

(4)

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

(5)

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

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

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

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

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

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

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

在超邊一致性對(duì)策中，超邊可分解性確保超邊的效用只能在同一條超邊中的參與者之間轉(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)換簡(jiǎn)單來(lái)說(shuō)，當(dāng)聯(lián)盟中所有參與者合作獲得的效用為正值時(shí)，若參與者k獲得的支付為Fk；那么當(dāng)聯(lián)盟中參與者合作獲得的效用為負(fù)值時(shí)，該參與者k分?jǐn)偟某蔀?/Fk。

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

例1假如存在一個(gè)超圖對(duì)策(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。由擬可加性可知，超圖對(duì)策(N,2u{1,4},H)和(N,-3u{1,2,3,4,5},H)不可比較。

(7)

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

(8)

(9)

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

(10)

(11)

(12)

(13)

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

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

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

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

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

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

第三個(gè)等式相等，因?yàn)镾hapley值滿足冗余超邊性質(zhì)。

所以，我們有：

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

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

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

(14)

(15)

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

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

(16)

=λS(ηv)uH(S)

3 超圖對(duì)策舉例分析

(17)

4 結(jié)論

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