邊賦權(quán)圖對(duì)策M(jìn)yerson值的和分解

單而芳，劉 珍

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

0 引言

可轉(zhuǎn)移效用合作對(duì)策，也稱為TU-對(duì)策[1]，描述的是所有參與者通過聯(lián)盟進(jìn)行合作并獲得收益以及如何分配他們共同的收益[2]。通常假定所有參與者彼此之間都可以進(jìn)行合作，也就是所有可能的聯(lián)盟都是可行的。然而在實(shí)際中，由于受到各種因素的制約導(dǎo)致有些聯(lián)盟是無法形成的。為了描述這一事實(shí)，Myerson[3]提出了由圖作為限制結(jié)構(gòu)的合作對(duì)策，圖中的點(diǎn)(node)表示參與者，而邊(link)表示與該邊關(guān)聯(lián)的兩個(gè)點(diǎn)代表的參與者之間的直接通訊或交流關(guān)系，并且假定有邊直接相連或通過路(path)相連的參與者之間才能形成聯(lián)盟進(jìn)行合作。在這種假定下，Myerson定義了圖限制對(duì)策(graph-restricted game)[3]并把圖限制對(duì)策的Shapley值[4]作為分配規(guī)則，也即著名的Myerson值。Myerson值可以由分支有效性(component efficiency)和公平性(fairness)所唯一刻畫。隨后， Myerson[5]又用平衡貢獻(xiàn)性(balanced contributions)替代公平性, 給出了Myerson值的另一個(gè)刻畫。而后，Myerson值被廣泛研究，它被推廣到一些其他圖結(jié)構(gòu)上，例如，超圖[6]、概率圖[7]、有向圖[8]以及邊賦權(quán)圖[9]上。

2003年，Gómez[10]等在研究網(wǎng)絡(luò)中心性度量時(shí)，首次在對(duì)稱對(duì)策上提出了Myerson值的和分解問題。2017年，González[11]等把Myerson值的和分解問題推廣到一般圖對(duì)策上，考慮到每個(gè)參與者既可以在他所參與的聯(lián)盟中獲利，又可以作為其他參與者的中介獲利，定義了兩種分配規(guī)則，即組內(nèi)Myerson值和組間Myerson值，研究了兩類Myerson值的性質(zhì)并給出了刻畫。

邊賦權(quán)圖在實(shí)際中具有重要的應(yīng)用，它由點(diǎn)集和邊集所組成，其中每條邊賦予一個(gè)權(quán)重(非負(fù)實(shí)數(shù))，邊的權(quán)可以用不同的解釋：例如：它可以表示通信信道的容量或能力，流經(jīng)信道的流量，建立或維護(hù)通信鏈路的成本；社會(huì)網(wǎng)絡(luò)中的參與者的親密度，合作的強(qiáng)度或接觸的頻率；還可以表示兩個(gè)點(diǎn)之間的距離等。González-Arangüena等[9]研究了邊賦權(quán)圖的Myerson值問題。

本文繼續(xù)對(duì)Myerson值的和分解問題進(jìn)行討論。我們將Myerson值的和分解概念進(jìn)一步推廣到邊賦權(quán)圖對(duì)策上，給出了邊賦權(quán)圖上組內(nèi)Myerson值和組間Myerson值的定義，證明了這兩類值可以利用可加性、無效參與者性和關(guān)鍵參與者性所唯一刻畫。我們側(cè)重分析了這兩類值的穩(wěn)定性。在某種意義下，證明了邊賦權(quán)圖對(duì)策的組內(nèi)Myerson值和組間Myerson值滿足權(quán)穩(wěn)定性和廣義穩(wěn)定性。

本文第一節(jié)給出所需要的一些基本定義和記號(hào)。第二節(jié)提出賦權(quán)圖對(duì)策的Myerson值和分解概念，定義了賦權(quán)圖對(duì)策的組內(nèi)Myerson值和組間Myerson值并給出刻畫。第三節(jié)以邊權(quán)表示邊的通訊容量為例，討論了賦權(quán)圖對(duì)策組內(nèi)Myerson值和組間Myerson值的權(quán)穩(wěn)定性和廣義穩(wěn)定性。第四節(jié)對(duì)本文工作進(jìn)行了總結(jié)。

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

1.1 TU-對(duì)策

可轉(zhuǎn)移效用合作對(duì)策，又叫做TU-對(duì)策[1]，用二元組(N,v)來表示，其中N= {1,2,…n}，表示參與者(player)的集合，v表示特征函數(shù)(characteristic function)，是定義在2N上的實(shí)數(shù)映射，并且滿足v(?)=0。對(duì)于每個(gè)聯(lián)盟(coalition)S?N，v(S)表示S中的參與者同意合作所得的效用(utility)。記GN為參與者集合N上的所有對(duì)策的集。

對(duì)于每個(gè)非空聯(lián)盟S?N，一致性對(duì)策(N,uT)的特征函數(shù)可以表示為: 若T?S，則uT(S)=1，否則uT(S)=0。已經(jīng)知道GN中的任意對(duì)策的特征函數(shù)都可以用一致性對(duì)策的線性組合來唯一表示, 也即:

(1)

在TU-對(duì)策中，最重要有效分配方案是由Shapley在1953年提出的，即著名的Shapley值[4]，它可以表示為:

(2)

這里|S|=s,|N|=n。

1.2 圖、圖對(duì)策和Myerson值

一個(gè)圖可以用二元組(N,v)表示。其中N={1,2,…,n}表示點(diǎn)的集合，L表示邊的集合，即L?{{i,j}|i,j∈N,i≠j}。通常用i,j替代{i,j}表示L的一條邊,而以L來表示圖(N,L)，并記Li={ij∈L:j∈N}，也即L中與點(diǎn)i關(guān)聯(lián)的邊的集。

對(duì)于圖L，如果ij∈L，則說點(diǎn)i和j在圖中是直接連通的?；ギ慄c(diǎn)列i1,i2,…,ik稱為圖L的一條路，如果對(duì)于任意的h=1,…,k-1，都有ihih+1∈L。如果兩個(gè)點(diǎn)i,j之間存在一條路，則說i和j是連通的。若(N,L)中任意兩個(gè)點(diǎn)都是連通的，則稱(N,L)是連通的。對(duì)于非空點(diǎn)集S∈N，L(S)稱為由點(diǎn)集S導(dǎo)出的子圖，并且L(S)={ij∈L:i,j∈S}。如果子圖(S,L(S) )是連通的，則稱S是連通子集。圖L的極大連通子圖稱為分支。記L中所有連通分支的集為N/L。類似地，記S/L為L(zhǎng)(S)所有分支的集。對(duì)L(S)和i∈N，分別用L{l}和L-i表示去掉邊L和去掉與i相關(guān)聯(lián)的所有邊所形成的生成子圖。

1.3 邊賦權(quán)圖對(duì)策的Myerson值

一個(gè)邊賦權(quán)圖用二元組(N,Lw)表示。其中N是點(diǎn)集，而Lw={L,{wl}l∈L}，wl≥0。邊賦權(quán)圖中邊的權(quán)wl可以有多種不同的解釋，例如：wl可以表示邊l的通訊容量(capacity)，此時(shí)，wl∈(0,1]。wl可以表示l的兩個(gè)端點(diǎn)所代表的參與者之間的距離(distance)或是建立和維持合作關(guān)系所需的成本(cost)，此時(shí)，wl∈[0,∞)。更多含義的解釋可參見[9]。本文以邊權(quán)代表邊的通訊容量為例進(jìn)行討論，其他情況可做類似處理。

(3)

(4)

此時(shí), 邊賦權(quán)圖限制對(duì)策與圖限制對(duì)策是一致的。

González用分支有效性、公平性和平衡貢獻(xiàn)性對(duì)賦權(quán)圖對(duì)策M(jìn)yerson值進(jìn)行了刻畫。

2 邊賦權(quán)圖對(duì)策組內(nèi)Myerson值和組間Myerson值

2017年，González[11]把圖對(duì)策的Myerson值分解為組內(nèi)Myerson值和組間Myerson值的和，以此來區(qū)分每個(gè)參與者在參與聯(lián)盟中所獲收益和他作為其他參與者的中介所獲得的收益。本節(jié)將把圖對(duì)策M(jìn)yerson值的和分解概念推廣到邊賦權(quán)圖對(duì)策上，定義邊賦權(quán)圖對(duì)策組內(nèi)Myerson值和組間Myerson值并給出刻畫。

2.1 邊賦權(quán)圖對(duì)策組內(nèi)Myerson值及其刻畫

在本小節(jié)將給出邊賦權(quán)圖對(duì)策組內(nèi)Myerson值的定義及其刻畫。

定義2對(duì)任意的對(duì)策(N,v)∈GN，如果對(duì)于任意S?N{i},v(S∪{i})=v(S)成立，則參與者i在(N,v)中是一個(gè)無效參與者。如果對(duì)于任意S?N{i},v(S)=0，則參與者i在(N,v)中是一個(gè)關(guān)鍵參與者。

2.2 邊賦權(quán)圖對(duì)策組間Myerson值及其刻畫

本小節(jié)給出邊賦權(quán)圖對(duì)策組間Myerson值的定義及其刻畫。

由定義，容易驗(yàn)證μαW+μαB=μα。

下面給出邊賦權(quán)圖對(duì)策組間Myerson值的刻畫。

3 邊賦權(quán)圖對(duì)策組內(nèi)和組間Myerson值的穩(wěn)定性

在邊賦權(quán)圖對(duì)策中，當(dāng)在網(wǎng)絡(luò)中增加邊或者增大變得權(quán)值時(shí)，網(wǎng)絡(luò)中的參與者是否都是收益的？或者至少這些邊關(guān)聯(lián)的參與者是否收益？這就是邊或者權(quán)的單調(diào)性問題或者說穩(wěn)定性問題。對(duì)任意的邊賦權(quán)圖對(duì)策，在增加新邊或者增大邊的權(quán)值后，一般來說并不一定所有的參與者，甚至關(guān)聯(lián)的參與者收益。不過，對(duì)非負(fù)的邊賦權(quán)圖對(duì)策，也就是所有聯(lián)盟的紅利非負(fù)[14]，組內(nèi)和組間具有權(quán)穩(wěn)定性和廣義穩(wěn)定性。非負(fù)圖對(duì)策在實(shí)際中具有廣泛的應(yīng)用，如河流對(duì)策[15]、污染河流對(duì)策[16]和排隊(duì)對(duì)策[17]，這些對(duì)策都是非負(fù)的。

下列命題給出了μαW(v,Lw,α(Lw))的一個(gè)表達(dá)式。

(5)

定理3非負(fù)邊賦權(quán)圖對(duì)策組內(nèi)Myerson值滿足權(quán)穩(wěn)定性。

為了分析邊賦權(quán)圖對(duì)策組間Myerson值的權(quán)穩(wěn)定性，首先，我們有下列基本結(jié)論。

定理4非負(fù)邊賦權(quán)圖對(duì)策組間Myerson值滿足局部權(quán)穩(wěn)定性。

我們用一個(gè)例子來說明μαW和μαB滿足權(quán)穩(wěn)定性和局部權(quán)穩(wěn)定性。

圖1 圖Lw和Lw′

μα(v,Lw,α(Lw))=(0.183,0.333,0.283)

μαW(v,Lw,α(Lw))=(0.183,0.300,0.283)

μαW(v,Lw,α(Lw))=(0,0.033,0)

和μα(v,Lw′,α(Lw′))=(0.417,0.367,0.517)

μαW(v,Lw′,α(Lw′))=(0.417,0.367,0.450)

μαB(v,Lw′,α(Lw′))=(0,0,0.067)

通過計(jì)算結(jié)果可以看出，增加邊c的權(quán)重，則每個(gè)參與者的組內(nèi)Myerson值μαW組間Myerson值μαB都有所增加，并且與c關(guān)聯(lián)的參與者1和3的組間Myerson值μαB都至少不減。但是參與者2的組間Myerson值μαB減少了。因此μαW是穩(wěn)定的，而μαB是局部穩(wěn)定的。

接下來我們繼續(xù)在紅利非負(fù)的前提下，討論μαW和μαB的廣義穩(wěn)定性。

定理5對(duì)于非負(fù)邊賦權(quán)圖對(duì)策，若新增邊的權(quán)重不小于包含這條邊的所有圈上邊權(quán)的最小值，則μαW滿足廣義穩(wěn)定性。

在紅利非負(fù)的情況下，新增的邊l*的權(quán)重不小于包含l^*的所有圈上邊權(quán)的最小值的時(shí)候，μαW是滿足廣義穩(wěn)定性。但是對(duì)于μαB，如例中所示，μαB是不滿足廣義穩(wěn)定性的。

圖2 圖Lw和圖(L∪{l*})w′

顯然，該邊賦權(quán)圖對(duì)策為非負(fù)的。通過邊賦權(quán)圖對(duì)策M(jìn)yerson值、邊賦權(quán)圖對(duì)策組內(nèi)Myerson值和邊賦權(quán)圖對(duì)策組間Myerson值的定義，計(jì)算可得

μα(N,v,Lw,α(Lw))=(0.167,0.367,0.267)

μαW(N,v,Lw,α(Lw))=(0.167,0.300,0.267)

μαB(N,v,Lw,α(Lw))=(0,0.067,0)和

μα(v,(L∪{l*})w′,α((L∪{l*})w′))=(0.417,0.367,0.517)

μαW(v,(L∪{l*})w′,α((L∪{l*})w′))=(0.417,0.367,0.450)

μαB(v,(L∪{l*})w′,α((L∪{l*})w′))=(0,0,0.067)

但是對(duì)于紅利不均是非負(fù)的情況，如特征函數(shù)v=u{1,3}-3u{1,2}-u{2,3}，通過邊賦權(quán)圖對(duì)策M(jìn)yerson值、邊賦權(quán)圖對(duì)策組內(nèi)Myerson值和邊賦權(quán)圖對(duì)策組間Myerson值的定義，計(jì)算可得

μα(N,v,Lw,α(Lw))=(-0.233,-0.433,-0.133)

μαW(N,v,Lw,α(Lw))=(-0.233,-0.500,-0.133)

μαB(N,v,Lw,α(Lw))=(0,0.067,0)和

μα(v,(L∪{l*})w′,α((L∪{l*})w′))

=(-0.250,-0.700,-0.250)

μαW(v,(L∪{l*})w′,α((L∪{l*})w′))

=(-0.250,-0.700,-0.050)

μαB(v,(L∪{l*})w′,α((L∪{l*})w′))

=(0,0,-0.200)

注意到此時(shí)組內(nèi)Myerson值μαW和組間Myerson值μαB都不滿足廣義穩(wěn)定性。

4 結(jié)論

為了區(qū)別參與者在所參與聯(lián)盟的獲利和作為其他參與者中介獲利的情況，本文在邊賦權(quán)圖對(duì)策中定義了組內(nèi)Myerson值和組間Myerson值，組內(nèi)Myerson值用于衡量該參與者對(duì)所參加聯(lián)盟的貢獻(xiàn)程度；而組間Myerson值評(píng)估了該參與者作為其他參與者中介所獲得的收益。同時(shí)，證明了這兩個(gè)值能夠用可加性、無效參與者性和關(guān)鍵參與者性進(jìn)行唯一性刻畫。在邊權(quán)重表示邊的通訊容量前提下，證明了非負(fù)邊賦權(quán)圖對(duì)策組內(nèi)Myerson值和組間Myerson值分別滿足權(quán)穩(wěn)定性和局部權(quán)穩(wěn)定性。另外，證明了非負(fù)組內(nèi)Myerson值滿足廣義穩(wěn)定性，舉例說明了組間Myerson值不滿足廣義穩(wěn)定性。由于邊權(quán)可以表示多種實(shí)際含義，有時(shí)，在不同含義下邊賦權(quán)圖Myerson值的性質(zhì)有很大差別，那么在其他邊權(quán)意義下，組內(nèi)Myerson值和組間Myerson值具有穩(wěn)定性的條件是需要進(jìn)一步深入討論的問題。此外，我們還可以基于對(duì)策理論的視角，將邊賦權(quán)圖對(duì)策的組內(nèi)Myerson值和組間Myerson值這兩個(gè)值作為中心性度量，衡量參與者在邊賦權(quán)圖代表的社會(huì)網(wǎng)絡(luò)中發(fā)揮的作用或產(chǎn)生的經(jīng)濟(jì)效益，對(duì)合作收益的分配具有指導(dǎo)性的意義。