單而芳, 劉賀宇, 呂文蓉, 史紀(jì)磊

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

0 引言

可轉(zhuǎn)移效用合作對(duì)策(cooperative game with transferable utility)[1]，簡稱TU-對(duì)策，描述的是參與者間通過形成合作聯(lián)盟，產(chǎn)生一定的聯(lián)盟效用。該模型假設(shè)任何有限參與者間都可能形成合作聯(lián)盟(coalition for cooperation)，即任何聯(lián)盟都是可行的。針對(duì)TU-對(duì)策，Shapley[2]以每個(gè)參與者為分析對(duì)象, 對(duì)參與者合作產(chǎn)生的聯(lián)盟效用提出了一種分配規(guī)則，即Shapley值。TU-對(duì)策中另一個(gè)著名分配規(guī)則是由Owen[3]提出的Banzhaf值，該值起源于投票對(duì)策，后被逐步拓展到TU-對(duì)策中。Shapley值和Banzhaf值都是通過參與者的邊際貢獻(xiàn)來度量的，可以看作參與者對(duì)所有聯(lián)盟產(chǎn)生的邊際貢獻(xiàn)的期望值。不過，它們對(duì)于每個(gè)聯(lián)盟邊際貢獻(xiàn)的權(quán)重定義是不同的。具體地，在Shapley值中，規(guī)定每個(gè)參與者加入任何相同規(guī)模聯(lián)盟的可能性是相同的，而在Banzhaf值中，規(guī)定參與者加入任何聯(lián)盟的可能性都是相同的。對(duì)于總效用的分配，Banzhaf值的計(jì)算方式比Shapley值更為簡單。

實(shí)際中，并非所有參與者間均能進(jìn)行有效合作。為描述該合作約束，Myerson[4]引入圖(graph)的概念，將TU-對(duì)策和圖結(jié)構(gòu)結(jié)合，提出了具有圖結(jié)構(gòu)的TU-對(duì)策，簡稱圖對(duì)策(graph game)。圖中的節(jié)點(diǎn)(node)代表參與者，圖中的邊(link)代表參與者之間存在的某種合作關(guān)系，且假設(shè)只有在有邊或路(path)連通的情況下，參與者間才能形成合作聯(lián)盟。在此基礎(chǔ)上，定義圖限制對(duì)策(graph-restricted game)上的Shapley值作為圖對(duì)策中的一種分配規(guī)則，即著名的Myerson值。同樣使用圖結(jié)構(gòu)描述參與者間的合作約束。Owen[5]對(duì)Banzhaf值進(jìn)行了研究，提出了圖限制對(duì)策中的Banzhaf值，簡稱為Banzhaf圖值(Banzhaf graph value)。之后，Alonso-Meijide和Fiestras-Janeri[6]給出了Banzhaf圖值的四種公理性刻畫。第一種是使用獨(dú)立性(isolation)、二合并性(pairwise merging)和公平性(fairness)；第二種是利用分支總貢獻(xiàn)性(component total power)和公平性(fairness)；第三種和第四種由平衡貢獻(xiàn)性(balanced contributions)代替公平性得到。其他以圖結(jié)構(gòu)描述合作約束的研究可參見[7～11]。

不同于Myerson[4]用圖結(jié)構(gòu)描述參與者間的合作約束，Owen[12]使用聯(lián)盟結(jié)構(gòu)描述合作約束，分析優(yōu)先聯(lián)盟(priori union)對(duì)效用分配造成的影響，提出了具有聯(lián)盟結(jié)構(gòu)的TU-對(duì)策(TU-games with coalition structures)，并定義了具有聯(lián)盟結(jié)構(gòu)的Banzhaf值(簡稱Banzhaf-Owen值)作為該對(duì)策上的一種分配規(guī)則。考慮對(duì)稱性，Alonso-Meijide和Fiestras-Janerio[13]提出了具有聯(lián)盟結(jié)構(gòu)的Banzhaf值的另一種修正形式，即對(duì)稱聯(lián)盟Banzhaf值(symmetric coalitional Banzhaf value)。類似的，Kamijo[14]定義了聯(lián)盟結(jié)構(gòu)TU-對(duì)策上的分割限制對(duì)策，提出并刻畫了該結(jié)構(gòu)下的一種新的分配方案，即Ka值。Owen值和Ka值所定義的聯(lián)盟結(jié)構(gòu)的不同點(diǎn)在于前者的優(yōu)先聯(lián)盟中的部分參與者可以和其他完整的優(yōu)先聯(lián)盟進(jìn)行合作，而后者則假定只有完整的優(yōu)先聯(lián)盟間才能進(jìn)行完全合作。

合作的復(fù)雜性使得合作往往受兩種甚至多種形式的約束。Alonso-Meijide等[15]考慮了具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)雙重限制的TU-對(duì)策，將Banzhaf-Owen值和對(duì)稱聯(lián)盟Banzhaf值推廣到了該模型中。而van den Brink等[16]則將Ka值和Myerson值推廣到具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的TU-對(duì)策(TU-games with coalition and graph structure)上，提出了圖-分割值(graph-partition value)和分割-圖值(partition-graph value)，即具有圖結(jié)構(gòu)的Ka值和具有聯(lián)盟結(jié)構(gòu)的Myerson值，并進(jìn)行了公理性刻畫。這兩個(gè)值都是Shapley值的推廣，而Banzhaf值在該形式下的推廣尚未有學(xué)者進(jìn)行研究。

本文旨在將Banzhaf值推廣到具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的TU-對(duì)策上，提出并刻畫一種新的具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的Banzhaf值。本文結(jié)構(gòu)安排如下： 第二節(jié)給出本文需要的基本定義和符號(hào)。第三節(jié)給出具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的Banzhaf值的定義，并進(jìn)行公理性刻畫。第四節(jié)以天然氣管道案例進(jìn)行分析，將具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的Banzhaf值與其他值進(jìn)行比較分析。最后對(duì)本文所做工作進(jìn)行總結(jié)并給出注記。

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

1.1 TU-對(duì)策

可轉(zhuǎn)移效用合作對(duì)策，簡稱TU-對(duì)策，是由二元組(N,v)組成。其中N表示有限參與者(player)集，v表示特征函數(shù)(characteristic function)，它是定義在2N→R上的一個(gè)映射，并規(guī)定v(?)=0。對(duì)N中任意一個(gè)非空子集S，v(S)表示聯(lián)盟中成員進(jìn)行合作所產(chǎn)生的效用，用s表示聯(lián)盟S的基數(shù)。(S,v|S)是(N,v)的子對(duì)策，且對(duì)任意的T?S，有v|S(T)=v(T)。為了簡便，我們將v({i,j,…,k})簡記為v(i,j,…,k)，相應(yīng)的也將S∪{i}簡記為S∪i。

支付向量(payoff vector)x=(x1,x2,…,xn)∈Rn是指分配給每個(gè)參與者i的支付為xi。TU-對(duì)策的一個(gè)分配規(guī)則(allocation)或者值是一個(gè)函數(shù)f，指分配給任意(N,v)的一個(gè)支付向量f(N,v)∈Rn。對(duì)于TU-對(duì)策(N,v)和任意的i∈N，Shapley值Sh(N,v)[2]是TU-對(duì)策上最著名的一個(gè)分配規(guī)則，其定義為：

TU-對(duì)策中，另一個(gè)分配規(guī)則是Banzhaf值[3]，其定義如下:

(1)

1.2 圖和通訊情境

圖(graph)由有限點(diǎn)集N和無向邊集L?LN={{i,j}|i,j∈N,i≠j}組成，用二元組(N,L)表示，其中LN稱為N上的完全圖。在參與者集合N固定時(shí)，我們將(N,L)簡記為L。記所有的圖(N,L)的集合為LN。為簡便起見，文中將{i,j}簡記為ij。

如果對(duì)任意k=1,2,…,p-1，都有ikik+1∈L，則稱點(diǎn)集(i1,i2,…,ip)為L中的一條路。如果i和j間存在一條路或者i=j，則稱i和j在L中是連通的。如果圖L中任意兩點(diǎn)間均是連通的，則稱圖L是連通的。對(duì)于任意的S?N，圖(S,L(S))稱為L在S上的子圖，其中L(S)={{i,j}∈L|i,j∈S}。對(duì)于任意的S?N，如果S中任意兩點(diǎn)在L(S)上均是連通的，則稱S在L上是連通的。一個(gè)極大的連通子集S稱為L上的一個(gè)分支。將(S,L(S))和(N,L)中所有分支的集合分別記為S/L和N/L。用(N,L-ij)表示由(N,L)去掉邊ij后形成的圖，用Li={ij∈L|j∈N}表示L中所有與i相關(guān)的無向邊的集合，記L-i,LLi表示去掉所有與i相關(guān)的無向邊后形成的子圖。

1.3 具有聯(lián)盟結(jié)構(gòu)的TU-對(duì)策

2 具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的Banzhaf值及其公理化刻畫

2.1 具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的Banzhaf值

具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的TU-對(duì)策由四元組(N,v,L,P)組成，其中(N,v)代表TU-對(duì)策，(N,L)代表圖，而(N,P)代表聯(lián)盟結(jié)構(gòu)。記所有具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的TU-對(duì)策(N,v,L,P)的集合為PN。對(duì)任意的(N,v,L,P)∈PN，van den Brink等[16]將分割-圖限制對(duì)策(N,(v|P)L)的特征函數(shù)定義為：對(duì)任意的S?N

(2)

在上述理論基礎(chǔ)上，本文將Banzhaf值拓展到具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的TU-對(duì)策中，定義一種新的具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的Banzhaf值，簡稱為PL-Banzhaf值。

定義1(PL-Banzhaf值) 對(duì)于任意的(N,v,L,P)∈PN，PL-Banzhaf值Ψ(N,v,L,P)可定義如下：對(duì)任意的i∈N

Ψi(N,v,L,P)=ξi(N,v1P,L)=Bai(N,(v|P)L)

(3)

顯然，當(dāng)P為平凡聯(lián)盟，也即P={N}或P={{1},{2},…,{n}}時(shí)，PL-Banzhaf值就是Banzhaf圖值。進(jìn)一步，當(dāng)P為平凡聯(lián)盟并且圖是完全圖時(shí)，PL-Banzhaf值就是Banzhaf值。因此，PL-Banzhaf值是Banzhaf圖值和Banzhaf值的一類自然推廣。

2.2 PL-Banzhaf值的公理化刻畫

本節(jié)將給出PL-Banzhaf值的公理性刻畫。為方便刻畫，我們首先介紹一些性質(zhì)。

分割分支總貢獻(xiàn)性是指：分支的總效用等于該分支內(nèi)每個(gè)參與者限制在該分支子對(duì)策上的效應(yīng)之和。

公平性(Fairness，簡記為FA)。對(duì)任意(N,v,L,P)∈PN，及任意的ij∈L，i,j∈N,若分配規(guī)則f∈Rn滿足fi(N,v,L,P)-fi(N,v,L-ij,P)=fj(N,v,L,P)-fj(N,v,L-ij,P),則稱f具有公平性。

公平性是指：與一條無向邊關(guān)聯(lián)的兩個(gè)參與者，當(dāng)去掉這條無向邊時(shí)，對(duì)這兩個(gè)參與者支付造成的影響是相同的。

引理1對(duì)任意的(N,v,L,P)∈PN，PL-Banzhaf值Ψ(N,v,L,P)滿足FA。

證明由定義1及Banzhaf圖值滿足FA[6]易得:

Ψi(N,v,L,P)-Ψi(N,v,L-ij,P)

=ξi(N,v|P,L)-ξi(N,v|P,L-ij)

=ξj(N,v|P,L)-ξj(N,v|P,L-ij)

=Ψj(N,v,L,P)-Ψj(N,v,L-ij,P)

所以Ψ(N,v,L,P)滿足公平性，引理得證。

平衡貢獻(xiàn)性(Balanced contributions，簡記為BC)。對(duì)任意(N,v,L,P)∈PN及i,j∈N，若分配規(guī)則∈Rn滿足fi(N,v,L,P)-fi(N,v,L-j,P)=fj(N,v,L,P)-fj(N,v,L-i,P),則稱f具有平衡貢獻(xiàn)性。

平衡貢獻(xiàn)性是指：i和j為聯(lián)盟N中的兩個(gè)參與者，參與者i選擇孤立自己對(duì)參與者j支付的影響與參與者j選擇孤立自己對(duì)參與者i支付的影響是相等的。

引理2對(duì)任意的(N,v,L,P)∈PN，PL-Banzhaf值Ψ(N,v,L,P)滿足平衡貢獻(xiàn)性(BC)。

證明由定義1及Banzhaf圖值滿足BC[6]易得:

Ψi(N,v,L,P)-Ψi(N,v,L-j,P)

=ξi(N,v|P,L)-ξi(N,v|P,L-j)

=Ψj(N,v,L,P)-Ψj(N,v,L-i,P)

所以Ψ(N,v,L,P)滿足平衡貢獻(xiàn)性，引理得證。

定理3對(duì)任意的(N,v,L,P)∈PN，PL-Banzhaf值Ψ(N,v,L,P)可由公平性(FA)和分割分支總貢獻(xiàn)性(PCTP)所唯一確定。

證明存在性。對(duì)于任意(N,v,L,P)∈PN，根據(jù)引理2可知，PL-Banzhaf值Ψ(N,v,L,P)滿足公平性。而由Banzhaf圖值滿足分支總貢獻(xiàn)性易證PL-Banzhaf值滿足PCTP。

唯一性。假設(shè)存在另一個(gè)滿足FA和PCTP的分配規(guī)則f，我們需證明f=Ψ。當(dāng)|L|=0時(shí)，即L為空?qǐng)D。此時(shí)，每個(gè)節(jié)點(diǎn)i∈N都是一個(gè)分支，由PCTP可得:fi(N,v,?,P)=v(i)=Ψi(N,v,?,P)。

現(xiàn)假設(shè)對(duì)任意的(N,v,L,P)∈PN，i∈N，當(dāng)|L|

fi(N,v,L,P)-fj(N,v,L,P)

=fi(N,v,L-ij,P)-fj(N,v,L-ij,P)

=Ψi(N,v,L-ij,P)-Ψj(N,v,L-ij,P)

=Ψi(N,v,L,P)-Ψj(N,v,L,P)

即,fi(N,v,L,P)-Ψi(N,v,L,P)=fj(N,v,L,P)-Ψj(N,v,L,P)。

根據(jù)分支內(nèi)參與者間的傳遞性可知，存在一個(gè)實(shí)數(shù)d，使得對(duì)任意i∈S∈S/L，有fi(N,v,L,P)-Ψi(N,v,L,P)=d。進(jìn)一步結(jié)合PCTP可得:

因?yàn)閟≠0，所以d=0，即fi(N,v,L,P)=Ψi(N,v,L,P)。

綜上所述，對(duì)任意的i∈N，均有fi(N,v,L,P)=Ψi(N,v,L,P)，定理得證。

引理4對(duì)任意的(N,v,L,P)∈PN，PL-Banzhaf值Ψ(N,v,L,P)滿足平衡貢獻(xiàn)性(BC)必定滿足公平性(FA)。

證明對(duì)于對(duì)策(N,v,L,P)及任意的i,j∈N，由PL-Banzhaf圖值滿足BC可知:

Ψi(N,v,L,P)-Ψi(N,v,L-j,P)

=Ψj(N,v,L,P)-Ψj(N,v,L-i,P)

(4)

對(duì)任意的i,j∈N及對(duì)策(N,v,L-ij,P)，由PL-Banzhaf圖值滿足BC可知：

Ψi(N,v,L-ij,P)-Ψi(N,v,(L-ij)-j,P)

=Ψj(N,v,L-ji,P)-Ψi(N,v,(L-ij)-i,P)

(5)

容易驗(yàn)證(L-ij)-j=L-j及(L-ij)-i=L-i成立。進(jìn)一步，式(5)可化簡為

Ψi(N,v,L-ij,P)-Ψi(N,v,L-j,P)

=Ψj(N,v,L-ij,P)-Ψj(N,v,L-i,P)

(6)

將式(4)和式(5)相減可得

Ψi(N,v,L,P)-Ψi(N,v,L-ij,P)

=Ψj(N,v,L,P)-Ψj(N,v,L-ij,P)

所以Ψ(N,v,L,P)滿足BC必定滿足FA，引理得證。

結(jié)合引理2、引理4和定理3可得關(guān)于PL-Banzhaf值的新刻畫。

定理5對(duì)任意的(N,v,L,P)∈PN，PL-Banzhaf值Ψ(N,v,L,P)可由平衡貢獻(xiàn)性(BC)和分割分支總貢獻(xiàn)性(PCTP)所唯一確定。

3 應(yīng)用舉例—天然氣管道運(yùn)輸問題

跨國運(yùn)輸問題一般均可抽象為具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的TU-對(duì)策，其中每個(gè)國家代表一種聯(lián)盟結(jié)構(gòu)，天然氣運(yùn)輸管道代表圖結(jié)構(gòu)。本節(jié)將引入一個(gè)跨國天然氣管道運(yùn)輸案例，分析PL-Banzhaf值的合理性和優(yōu)勢(shì)。

圖1 跨國天然氣管道運(yùn)輸模型示意圖

考慮由五個(gè)地區(qū)構(gòu)成的天然氣跨國運(yùn)輸模型。N={1,2,3,4,5}是地區(qū)集合，其中地區(qū)1坐落在P1國，地區(qū)2坐落在P2國，地區(qū)3坐落在P3國，地區(qū)4和地區(qū)5屬于同一個(gè)國家，記為P4國。地區(qū)1是天然氣的主要出口區(qū)，通過現(xiàn)有的天然氣管道將天然氣運(yùn)送給其他各區(qū)。而地區(qū)3是天然氣自給自足區(qū)，產(chǎn)生的天然氣僅供給本區(qū)使用，且不需要進(jìn)口。將國家抽象為聯(lián)盟結(jié)構(gòu)，天然氣管道抽象為圖結(jié)構(gòu)，可將上述模型抽象為如圖1所示的結(jié)構(gòu)。其中邊集L={12,24,45}，聯(lián)盟分割為P={P1,P2,P3,P4}={{1},{2},{3},{4,5}}

根據(jù)上述假設(shè)可知，地區(qū)3自身即可產(chǎn)生收益，不需與其他地區(qū)合作。地區(qū)1自身可以產(chǎn)生收益，也可通過與其他地區(qū)合作獲得更大的收益。而其他地區(qū)均需包含天然氣的出口區(qū)1時(shí)才會(huì)產(chǎn)生收益。現(xiàn)只考慮每個(gè)地區(qū)在運(yùn)輸過程中產(chǎn)生的效用，據(jù)此，我們定義如下特征函數(shù):

根據(jù)式(1)、式(2)和定義1，計(jì)算可得各地區(qū)的PL-Banzhaf值Ψ如表1所示，表中同樣還列出了Banzhaf值Φ、Banzhaf圖值Π、Banzhaf-Owen圖值[12]ξ和λ[13]。

表1 跨國天然氣管道運(yùn)輸案例各值計(jì)算結(jié)果

分析表1可知，Banzhaf值沒有考慮到各地區(qū)間所屬的國別差異和天然氣管道的限制，給予了地區(qū)2最低的分配值。但實(shí)際上，地區(qū)1往地區(qū)4和地區(qū)5運(yùn)輸天然氣時(shí)必須經(jīng)過地區(qū)2，因此，Banzhaf值并未體現(xiàn)出地區(qū)2在天然氣運(yùn)輸過程中的作為必要樞紐的重要性。Banzhaf圖值雖然體現(xiàn)出了地區(qū)2作為必要樞紐的重要性，但未考慮到聯(lián)盟結(jié)構(gòu)。Banzhaf-Owen值和對(duì)稱聯(lián)盟Banzhaf值雖然同時(shí)考慮了圖結(jié)構(gòu)和聯(lián)盟結(jié)構(gòu)，但并未體現(xiàn)聯(lián)盟結(jié)構(gòu)內(nèi)合作共贏的理念。一般而言，選擇天然氣進(jìn)口區(qū)時(shí)會(huì)傾向于選擇能使國家內(nèi)所有需求區(qū)都能獲得最大效用的地區(qū)，因此需征求所有地區(qū)的意見，而Banzhaf-Owen值和對(duì)稱聯(lián)盟Banzhaf值使用的聯(lián)盟結(jié)構(gòu)定義并不滿足該條件。本文提出的PL-Banzhaf值，則能夠很好適應(yīng)該結(jié)構(gòu)。

注意到PL-Banzhaf值不滿足有效性，因此這個(gè)值不一定在核心中。

4 結(jié)論及注記

本文給出了一種新的具有聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)的Banzhaf值(PL-Banzhaf值)的定義及其滿足的性質(zhì)，它是對(duì)Banzhaf值的一類推廣。首先，通過公平性、平衡貢獻(xiàn)性和分割分支總貢獻(xiàn)性，給出了PL-Banzhaf值的兩種刻畫方式。其次，根據(jù)跨國天然氣管道運(yùn)輸案例分析，PL-Banzhaf值相比其他分配規(guī)則更能提出參與者在運(yùn)輸過程中以及聯(lián)盟協(xié)商中的地位。另外，van den Brink等[16]指出聯(lián)盟結(jié)構(gòu)和圖結(jié)構(gòu)考慮的先后順序不同時(shí)，會(huì)形成兩種不同的限制對(duì)策，本文只考慮了其中一種，而另外一種也是十分具有研究意義的。