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

單而芳, 謝娜娜, 王光明,2

(1.上海大學(xué) 管理學(xué)院,上海 200444; 2.濟(jì)南大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,山東 濟(jì)南 250022)

0 引言

經(jīng)典可轉(zhuǎn)移效用的合作博弈，簡(jiǎn)稱為TU-博弈[1]，描述了任何有限個(gè)參與者都可以形成合作聯(lián)盟并產(chǎn)生相應(yīng)的效用。然而，在實(shí)際中，由于受到不同文化、宗教背景、社會(huì)階層以及技術(shù)或者組織結(jié)構(gòu)等的限制使得一些聯(lián)盟并不能形成?；诖耸聦?shí)，Myerson[2]提出了具有圖結(jié)構(gòu)的合作博弈，簡(jiǎn)稱為圖博弈。在圖博弈中，圖的結(jié)點(diǎn)表示參與者，而圖的每條邊表示該條邊的兩個(gè)端點(diǎn)代表的參與者之間存在直接的雙邊協(xié)議或者通訊聯(lián)系，并假設(shè)只有通過路相互連通的參與者才能形成可行聯(lián)盟。Myerson把圖限制博弈的Shapley值[3]作為一個(gè)新的分配規(guī)則，也即Myerson值，并利用公平性和分支有效性給出了Myerson值的唯一性刻畫[2]。此后，圖博弈的研究得到廣泛關(guān)注。關(guān)于最近的Myerson值的研究進(jìn)展參看[4～8]。

1988年，Meessen[9]提出了圖博弈中另一個(gè)重要的分配規(guī)則，也就是Position值。它是首先將圖博弈中的所有邊看成“參與者”，計(jì)算出每條邊的Shapley值，然后把每條邊的Shapley值平均分配給它的兩個(gè)端點(diǎn)，給每個(gè)參與者的支付等于分配給它的所有邊Shapley值一半的和。Borm等[10]在無圈圖博弈上給出了該值的公理化刻畫。van den Nouweland等[11]和Algaba等[12]分別把Position值推廣到超圖博弈和并穩(wěn)定系統(tǒng)博弈中，并在無圈超圖博弈和一類并穩(wěn)定系統(tǒng)博弈上分別給出了該值的公理化刻畫。直到2005年，Slikker[13]才給出了任意圖博弈上Position值的公理化刻畫，他證明了Position值能夠被分支有效性和平衡邊貢獻(xiàn)性所唯一刻畫。迄今，任意超圖博弈上Position值的公理化刻畫問題仍未能解決。關(guān)于Position值的研究進(jìn)展參看[14～17]。

在實(shí)際中，參與者往往具有不同的個(gè)人特征，如討價(jià)還價(jià)能力，投入的努力程度等。此外，超圖中的超邊通常也具有不同的物理特征，如合作的能力，組織或團(tuán)體的規(guī)模，關(guān)系的親密程度或強(qiáng)度，建立或維持超邊的成本等?；趨⑴c者的不同特征，Shapley提出了賦權(quán)值Shapley值[18]。而后，Haeringer[19]，Slikker和van den Nouweland[20]將賦權(quán)Shapley值推廣到圖博弈和分層結(jié)構(gòu)中。最近，Gonzalez-Aranguena[21]根據(jù)賦權(quán)的不同解釋研究了賦權(quán)圖限制博弈和推廣的Myerson值。Ghintran[22]將Position值推廣到概率圖博弈，Ghintran[23]利用圖博弈中允許參與者獲得不同的邊Shapley值這種轉(zhuǎn)換機(jī)制推廣了Position值。

本文旨在給出超圖博弈上賦權(quán)Position值的公理化刻畫。為此，通過考慮賦權(quán)超圖博弈，引入了“賦權(quán)平衡超邊貢獻(xiàn)”公理，并結(jié)合經(jīng)典的“分支有效”性質(zhì)，給出了賦權(quán)超圖博弈上Position值的公理化刻畫。作為推論，我們得到了超圖博弈上Position值的公理化刻畫，同時(shí)頁推廣了Slikker的結(jié)論。最后，通過例子對(duì)刻畫公理進(jìn)行了說明，并與Myerson值進(jìn)行了比較。

本文第一節(jié)將介紹TU-博弈、圖博弈和超圖博弈的一些基本定義和記號(hào)，并給出了超圖博弈賦權(quán)Position值的表達(dá)式。第二節(jié)提出本文關(guān)鍵的公理——賦權(quán)平衡超邊貢獻(xiàn)，并給出超圖博弈上賦權(quán)Position值的公理化刻畫。第三節(jié)考慮了圖博弈上具有“度”賦權(quán)的Position值，并對(duì)Position值和Myerson值做了比較分析。

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

1.1 TU-博弈

可轉(zhuǎn)移效用的合作博弈，簡(jiǎn)稱為TU-博弈，可由二元組(N,v)來表示，其中N表示參與者的集合，v表示特征函數(shù)，它是{S:S?N}到實(shí)數(shù)集R的一個(gè)映射，即v:2N→R，且規(guī)定V(?)=0。N的任意子集S表示由S中的參與者形成的聯(lián)盟。v(S)表示聯(lián)盟S的效用，|S|表示集合S的基數(shù)。

對(duì)于任意一個(gè)博弈(N,v)和一個(gè)非空聯(lián)盟T?N，限制在參與者集合的子博弈(T,vT)定義為：對(duì)于所有的S?T,vT(S)=v(S)，如果對(duì)任意的i∈N，都有v({i})=0，則稱該TU-博弈(N,v)是0-規(guī)范的，每個(gè)TU-博弈都可以轉(zhuǎn)化為一個(gè)0-規(guī)范博弈[1]。以下討論中涉及的博弈均指0-規(guī)范的TU博弈。

稱為Harsanyi紅利[25]。對(duì)TU-博弈，最著名的有效單值解是Shapley值。對(duì)于任意一個(gè)博弈(N,v)和任意參與者i∈N，Shapley值可以表示為

(1)

考慮到參與者之間的非對(duì)稱性，Shapley將Shapley值推廣為賦權(quán)的情況。記θ=(θi)i∈N∈R+為參與者的賦權(quán)，博弈的賦權(quán)Shapley值:

(2)

顯然，當(dāng)對(duì)所有的i,j,θi=θj時(shí)，方程(1)和(2)是等價(jià)的，即當(dāng)所有參與者具有相同的賦權(quán)時(shí)，賦權(quán)Shapley值即為Shapley值。

1.2 超圖和圖博弈的Position值

超圖是一個(gè)二元組(N,H)，其中H?HN={e?N=|e|≥2}表示至少包含兩個(gè)參與者的超邊集合。Hi:={e∈H|i∈e}為(N,H)中包含參與者i的超邊的集合，參與者i的度記為|Hi|。(N,H)中的每條超邊e∈H都表示一個(gè)conference結(jié)構(gòu)。在實(shí)際中，超邊可以代表某種社會(huì)組織，如行業(yè)協(xié)會(huì)、企業(yè)集團(tuán)等。每個(gè)參與者可以參加多種行業(yè)組織或企業(yè)集團(tuán)，并參與不同聯(lián)盟的合作。若超圖中的每條超邊都包含個(gè)參與者，即對(duì)任意的e∈H,|e|=r則稱此超圖是r-一致的。對(duì)任意S?N,(S,H(S))稱為由聯(lián)盟S導(dǎo)出的子超圖，其中H(S)={e∈H|e?S}。

在(N,H)中，若i∈e，則稱參與者i與超邊是e∈H關(guān)聯(lián)的; 如果存在超邊e∈H，滿足i,j∈e，則稱參與者i和參與者j是鄰接的。如果存在一個(gè)點(diǎn)邊序列i=i1,e1,i2,e2,…,ik,ek,ik+1=j，使得對(duì)l=1,2,…,k都有il,il+1∈el，那么稱是點(diǎn)i和j是連通的。如果超圖中任意兩個(gè)點(diǎn)都是連通的，則稱超圖是連通的。對(duì)于任意非空集合S?N,(S,H(S))稱為由聯(lián)盟S導(dǎo)出的子超圖，其中H(S)={e∈H|e?S}。如果(S,H(S))是(N,H)中的連通子超圖，則稱聯(lián)盟S是聯(lián)通的。超圖的每個(gè)極大連通子集稱為一個(gè)分支。(N,H)中分支的集合記為N/H，包含i的分支記為(N/H)i。對(duì)H′?H,(N,H′)稱為(N,H)的一個(gè)部分超圖。S的所有分支的的集合記為S/H。對(duì)每一個(gè)分支C∈N/H，用H(C)表示包含在C中的超邊集。

超圖博弈是指一個(gè)三元組(N,v,H)，它是由TU-博弈(N,v)和描述通訊可能性的超圖(N,H)兩部分所組成。記參與者為N的所有超圖博弈(N,v,H)的集合為HN。

特別的，特別的，如果超圖的每條超邊e都有|e|=2，則超圖即為普通圖。此時(shí)對(duì)應(yīng)的超圖博弈稱為圖博弈。為了區(qū)別圖和超圖，用L表示圖的邊集，并記所有圖博弈(N,v,L)的集合為GN。

通過引入“平衡邊貢獻(xiàn)性”，并結(jié)合“分支有效性”，Slikker[13]給出了任意圖博弈上position值的公理性刻畫。

1.3 超圖博弈的賦權(quán)Position值

超圖博弈的一個(gè)分配規(guī)則或值f(N,v,H)是定義在HN上的映射，它是一個(gè)n維向量。在圖博弈中，Myerson值和Position值是兩個(gè)重要的分配規(guī)則。van den Nouweland等[11]將Myerson值和Position值推廣到超圖博弈。對(duì)參與者i∈N，超圖博弈的Myerson值μ定義為:

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

(3)

而超圖博弈上的Position值π定義為:

(4)

在Position值的定義中，超邊的Shapley值平均分配給本超邊的所有參與者。正像引言中指出的，在實(shí)際中參與者和超邊可能具有不同的特征，也即在參與者之間或超邊之間的平均處理不能反映實(shí)際中的非對(duì)稱性。

定義1對(duì)具有賦權(quán)結(jié)構(gòu)w=(θ,σ)的任意超圖博弈(N,v,H)∈HN以及任意的i∈N，定義超圖博弈賦權(quán)Position值為

(5)

Position值是在對(duì)稱的假設(shè)前提下，參與者平均分配其所在的超邊的Shapley值，而賦權(quán)Position值是在非對(duì)稱的假設(shè)前提下，參與者根據(jù)其賦權(quán)分配其所在超邊的Shapley值，且利用賦權(quán)Shapley值體現(xiàn)超邊的非對(duì)稱性。

2 賦權(quán)超圖博弈Position值的公理性刻畫

本節(jié)通過引入“賦權(quán)平衡超邊貢獻(xiàn)”這一關(guān)鍵公理，并結(jié)合經(jīng)典的“分支有效”公理，給出了賦權(quán)超圖博弈Position值的公理化刻畫。

首先，給出兩個(gè)基本性質(zhì)公理。記f是定義在超圖博弈HN上的一個(gè)分配規(guī)則。

在圖博弈中，Slikker[13]為了給出Position值的公理化刻畫，引入了平衡邊貢獻(xiàn)公理。而在超圖博弈中，每條超邊可能包含多個(gè)參與者，包含參與者i的超邊斷裂所造成的參與者j支付的差異，不僅與參與者i有關(guān)，還與包含它的超邊所包含的其它參與者有關(guān)。此外，每位參與者和每條超邊的非對(duì)稱性也應(yīng)當(dāng)被充分考慮?；诖?，我們提出了“賦權(quán)平衡超邊貢獻(xiàn)”這一新的公理。假定參與者i對(duì)參與者j支付的總貢獻(xiàn)為任意斷裂所有包含i的超邊造成的參與者j的支付差異的總和。賦權(quán)平衡超邊貢獻(xiàn)是指，對(duì)兩個(gè)任意參與者i和j，參與者i對(duì)參與者j支付的總貢獻(xiàn)等于參與者j對(duì)參與者i支付的總貢獻(xiàn)。具體地。

賦權(quán)平衡超邊貢獻(xiàn):對(duì)于任意(N,v,H)∈HN和賦權(quán)結(jié)構(gòu)w=(θ,σ)，對(duì)任意i,j∈N，有

這個(gè)公理在后面賦權(quán)Position值的刻畫中起著關(guān)鍵的作用。顯然，當(dāng)賦權(quán)超圖博弈限制為普通圖博弈時(shí)，賦權(quán)平衡超邊貢獻(xiàn)公理即為平衡邊貢獻(xiàn)公理。下面舉例說明賦權(quán)平衡超邊貢獻(xiàn):

例1設(shè)超圖博弈(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是常向量)，πθ和πσ分別是各自賦權(quán)超圖博弈Position值，通過計(jì)算，可得:

超邊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)

為了證明賦權(quán)超圖博弈Position值πw滿足分支有效和賦權(quán)平衡超邊貢獻(xiàn)這兩個(gè)公理，根據(jù)第一節(jié)給出的無異議博弈，我們給出下面的引理，它給出了超圖博弈的Position值的另一種表達(dá)形式。

根據(jù)引理3.1，可以證明πw滿足分支有效和賦權(quán)平衡超邊貢獻(xiàn)這兩個(gè)性質(zhì)：

引理3.2對(duì)于任意超圖博弈(N,v,H)∈HN及其賦權(quán)結(jié)構(gòu)w=(θ,σ)，Position值πw滿足分支有效和賦權(quán)平衡超邊貢獻(xiàn)性質(zhì)。

由引理3.2，可以給出賦權(quán)超圖博弈Position值的公理化刻畫：

定理3.3對(duì)于任意超圖博弈(N,v,H)∈HN及其賦權(quán)結(jié)構(gòu)w=(θ,σ)，其Position值πw是滿足分支有效和賦權(quán)平衡超邊貢獻(xiàn)公理的唯一解。

注1考慮非賦權(quán)或常向量賦權(quán)Position值，此時(shí)賦權(quán)平衡超邊貢獻(xiàn)退化為局部平衡超邊貢獻(xiàn)，即

局部平衡超邊貢獻(xiàn):對(duì)于任意超圖博弈(N,v,H)∈HN和i,j∈N，有

定理3.3說明超圖博弈的Position值可以被分支有效性和局部平衡超邊貢獻(xiàn)性所唯一刻畫。

例2設(shè)(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}。

根據(jù)Position值和Myerson值的定義，計(jì)算可得值π和μ值的分配結(jié)果如下。

超邊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 具有度賦權(quán)的Position值

本節(jié)討論一類特殊圖博弈賦權(quán)Position值。圖博弈(N,v,L)中，參與者關(guān)聯(lián)的邊數(shù)稱為此參與者的度。Shan[26]發(fā)現(xiàn)參與者的度明顯地反映了此參與者某種意義上的合作能力，即度越大的參與者應(yīng)該越依賴合作。這意味著度較大的參與者比度較小的參與者獲得更多支付，同時(shí)在邊斷開時(shí)受到的影響更大。

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

度賦權(quán)Position值是指將邊的Shapley值根據(jù)度的比例分配給此邊的兩個(gè)參與者。

下面的例子說明度越大的參與者應(yīng)該對(duì)合作的依賴程度越大。

例3設(shè)圖博弈(N,v,L)，其中N={1,2,…,5}，v是一致博弈u{1,2,3}，L={{1,4},{2,5},{3,5},{4,5}}。計(jì)算限制博弈得:

類似地，計(jì)算邊博弈可得:

易驗(yàn)證關(guān)于度的Position值滿足分支有效性和賦權(quán)平衡邊貢獻(xiàn)。表1中列出了幾個(gè)子圖的度賦權(quán)Position值。例如，參與人4對(duì)參與人1 的總貢獻(xiàn):

表1 關(guān)于度的Position值，Position值，Myerson值

參與人1對(duì)參與人4的總貢獻(xiàn):

由于(d1,d2,d3,d4,d5)=(1,1,1,2,3)，參與者5和參與者4關(guān)于度的Position值比Position值和Myerson值大。

4 結(jié)論

本文考慮了賦權(quán)超圖博弈并提出了賦權(quán)Position值的概念，通過引入賦權(quán)平衡超邊貢獻(xiàn)公理并結(jié)合經(jīng)典的分支有效公理給出了賦權(quán)超圖博弈Position值的公理化刻畫。作為推論，解決了超圖博弈Position值的刻畫問題。最后，以圖博弈上的度賦權(quán)Position值為例，說明了度越大的參與者對(duì)合作的依賴程度越大。