具有圖結構和聯盟結構的Banzhaf值及應用

單而芳, 劉賀宇, 呂文蓉, 史紀磊

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

0 引言

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

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

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

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

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

1 預備知識

1.1 TU-對策

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

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

TU-對策中，另一個分配規則是Banzhaf值[3]，其定義如下:

(1)

1.2 圖和通訊情境

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

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

1.3 具有聯盟結構的TU-對策

2 具有聯盟結構和圖結構的Banzhaf值及其公理化刻畫

2.1 具有聯盟結構和圖結構的Banzhaf值

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

(2)

在上述理論基礎上，本文將Banzhaf值拓展到具有聯盟結構和圖結構的TU-對策中，定義一種新的具有聯盟結構和圖結構的Banzhaf值，簡稱為PL-Banzhaf值。

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

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

(3)

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

2.2 PL-Banzhaf值的公理化刻畫

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

分割分支總貢獻性是指：分支的總效用等于該分支內每個參與者限制在該分支子對策上的效應之和。

公平性(Fairness，簡記為FA)。對任意(N,v,L,P)∈PN，及任意的ij∈L，i,j∈N,若分配規則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具有公平性。

公平性是指：與一條無向邊關聯的兩個參與者，當去掉這條無向邊時，對這兩個參與者支付造成的影響是相同的。

引理1對任意的(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)滿足公平性，引理得證。

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

平衡貢獻性是指：i和j為聯盟N中的兩個參與者，參與者i選擇孤立自己對參與者j支付的影響與參與者j選擇孤立自己對參與者i支付的影響是相等的。

引理2對任意的(N,v,L,P)∈PN，PL-Banzhaf值Ψ(N,v,L,P)滿足平衡貢獻性(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)滿足平衡貢獻性，引理得證。

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

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

唯一性。假設存在另一個滿足FA和PCTP的分配規則f，我們需證明f=Ψ。當|L|=0時，即L為空圖。此時，每個節點i∈N都是一個分支，由PCTP可得:fi(N,v,?,P)=v(i)=Ψi(N,v,?,P)。

現假設對任意的(N,v,L,P)∈PN，i∈N，當|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)。

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

因為s≠0，所以d=0，即fi(N,v,L,P)=Ψi(N,v,L,P)。

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

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

證明對于對策(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)

對任意的i,j∈N及對策(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)

容易驗證(L-ij)-j=L-j及(L-ij)-i=L-i成立。進一步，式(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，引理得證。

結合引理2、引理4和定理3可得關于PL-Banzhaf值的新刻畫。

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

3 應用舉例—天然氣管道運輸問題

跨國運輸問題一般均可抽象為具有聯盟結構和圖結構的TU-對策，其中每個國家代表一種聯盟結構，天然氣運輸管道代表圖結構。本節將引入一個跨國天然氣管道運輸案例，分析PL-Banzhaf值的合理性和優勢。

圖1 跨國天然氣管道運輸模型示意圖

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

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

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

表1 跨國天然氣管道運輸案例各值計算結果

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

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

4 結論及注記

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