賦權(quán)Myerson值與一致性

單而芳, 聶珊姍, 呂文蓉

(1.上海大學(xué) 管理學(xué)院,上海 200444; 2.上海大學(xué) 數(shù)學(xué)系,上海 200444)

0 引言

在效用可轉(zhuǎn)移合作對策中,任何參與者之間都能形成可行聯(lián)盟進行合作,并從中獲得合作收益。合理分配參與者間產(chǎn)生的合作收益是保持其穩(wěn)定合作的關(guān)鍵。SHAPLEY[1]根據(jù)參與者對不同聯(lián)盟的邊際貢獻提出了著名的Shapley值?？紤]到在現(xiàn)實中,一些參與者之間不能形成可行聯(lián)盟,MYERSON[2]引入圖以描述參與者間的合作通訊結(jié)構(gòu),將Shapley值推廣到具有圖結(jié)構(gòu)的合作對策(簡稱圖對策)上,提出了Myerson值并給出了公理化刻畫。關(guān)于Myerson值最近的其他研究進展可參看LI和SHAN[3-6]、SHAN等[7]。

不過,在實際中不同參與者的討價還價能力可能不同,為此可以根據(jù)每個參與者的實力,對其進行賦權(quán)以體現(xiàn)參與者的討價還價能力。HAERINGER[8]基于SHAPLEY[9]提出的賦權(quán)Shapley值,將Myerson值推廣到賦權(quán)圖對策中,提出了賦權(quán)Myerson值,并證明它可以由分支有效性和賦權(quán)公平性所唯一確定。SLIKKER和VAN DEN NOUWELAND[10]把具有不同權(quán)值的參與者看作不對稱參與者,利用分支有效性、類賦權(quán)公平性(class weighted fairness)、高階獨立性(independence of higher classes)和類一致性(class consistency)給出了賦權(quán)Myerson值的刻畫。最近,WANG和SHAN[11]進一步討論了賦權(quán)Myerson值的分解性質(zhì)。

一致性公理最早由HART和MAS-COLELL[12]在1989年提出,并被用來刻畫Shapley值。此后,該性質(zhì)被廣泛應(yīng)用于值的公理化刻畫中。WINTER[13]將一致性應(yīng)用于到具有聯(lián)盟結(jié)構(gòu)的對策中,用一致性和其他四個性質(zhì)刻畫了著名的Owen值。DRANGAN[14]受HART和MAS-COLELL[12]研究的啟發(fā),構(gòu)造了Banzhaf值的縮減對策,并據(jù)此提出了與該縮減對策相對應(yīng)的一致性公理,用一致性和標準性給出了Banzhaf值的刻畫。ALBIZURI和ZARZUELO[15]則將一致性推廣到超圖對策上,提出了對應(yīng)于圖對策的CS-一致性公理,并仿照Shapley值的潛能函數(shù)[12]定義了Myerson值的潛能函數(shù),然后借助潛能函數(shù),用CS-一致性和CS-標準性刻畫了超圖對策上的Myerson值。

本文的目的是用一致性公理來刻畫賦權(quán)Myerson值。一般地,利用一致性公理來刻畫對策的值時,需要借助潛能函數(shù)做工具才能完成值滿足一致性的證明。本文在提出賦權(quán)圖對策上的縮減對策和縮減圖后,避開潛能函數(shù)的概念,直接建立了在賦權(quán)Myerson值下每個聯(lián)盟在縮減圖限制對策和原圖限制對策下紅利之間的關(guān)系式,由此證明了賦權(quán)Myerson值滿足一致性,并最終利用權(quán)意義下的一致性和標準性給出了賦權(quán)Myerson值的刻畫。

下一節(jié)介紹本文所涉及的概念、記號和術(shù)語。第三節(jié)首先提出賦權(quán)圖對策中的縮減對策、縮減圖概念和一致性公理,其次建立聯(lián)盟在賦權(quán)縮減圖限制對策和原賦權(quán)圖限制對策下紅利之間的關(guān)系式,然后利用權(quán)意義下的一致性和標準性給出賦權(quán)Myerson的公理化刻畫。最后一節(jié)對本文進行了總結(jié)。

1 預(yù)備知識

1.1 TU-對策和Shapley值

效用可轉(zhuǎn)移合作對策,簡稱TU-對策,由二元組(N,v)構(gòu)成,其中N={1,2,…,n}表示參與者(player)的集合,通常稱為N大聯(lián)盟,v表示特征函數(shù)(characteristic function),它是定義在N的冪集2N上的一個實映射,并且規(guī)定v(φ)=0。N的任意子集S稱為聯(lián)盟,v(S)表示聯(lián)盟中的參與者進行合作所產(chǎn)生的效用(worth),用|S|或s表示聯(lián)盟的基數(shù)。將N上所有TU-對策的集合記作GN。以下提到的對策均指TU-對策。

對于S∈2N{φ},對應(yīng)于S的一致性對策(N,uS)[1]定義為:若S?T,則uS(T)=1,否則uS(T)=0。任意TU-對策(N,v)都可以用一致性對策唯一線性表示[16],即

(1)

其中ΔS(v)為聯(lián)盟S的Harsanyi紅利,其表達式為

(2)

在TU-對策(N,v)中,x=(x1,…,xn)∈Rn表示一個支付向量,其中xi表示第i個參與者所獲得的支付。分配規(guī)則φ是定義在GN上的一個函數(shù),也即φ:GN→Rn,φi(N,v)表示給參與者i∈N的支付。

在TU-對策中,最著名的分配規(guī)則是Shapley值[1],其紅利表達式為

參與者i的Shapley值等于包含它的每個聯(lián)盟紅利的均值之和。

(3)

在合作對策理論中,Shapley值已被廣泛應(yīng)用于許多領(lǐng)域,對社會、政治、經(jīng)濟和科學(xué)等領(lǐng)域的發(fā)展均產(chǎn)生了深刻影響。此外,根據(jù)不同的實際背景,它已被推廣到諸如優(yōu)先聯(lián)盟合作結(jié)構(gòu)、通訊圖合作結(jié)構(gòu)等不同的合作結(jié)構(gòu)環(huán)境中。

1.2 圖對策和賦權(quán)Myerson值

1977年,MYERSON把Shapley值推廣到具有通訊圖結(jié)構(gòu)的合作對策中,提出了著名的Myerson值[2]。下面介紹相關(guān)的概念。

一個圖由二元組(N,L)表示,其中N是頂點的集合,每個頂點代表一個參與者,L?LN={{i,j}|i,j∈N,i≠j}是邊的集合,代表參與者之間的通訊聯(lián)系。為方便起見,本文用ij代替{i,j}來表示邊。如果ij∈L,稱i和j在圖中是直接連通的。對于不直接相連的參與者i和j,也可能通過其他參與者作為“中介”實現(xiàn)連通。如果存在一條路(path),也就是參與者序列(i1,i2,…,it),i1=i,it=j,使得對于所有k∈{1,2,…,t-1}有{ik,ik+1}∈L,則稱i和j是連通的。這條路也稱為i-j路,路的長度定義為該條路上邊的個數(shù)。若圖中任意兩點均是直接連通或連通的,則稱這個圖是連通的。在圖(N,L)中,每個極大的連通子圖稱作一個分支,用N/L表示圖(N,L)所有分支的集合。對任意S?N,由聯(lián)盟S導(dǎo)出的子圖記作(S,LS),其中LS={ij|ij∈L,i,j∈S},用S/LS表示S所有分支的集合。如果(S,LS)是連通的,則聯(lián)盟S是連通的。

一個圖對策由三元組(N,v,L)所構(gòu)成,其中(N,v)是一個TU-對策,而(N,L)是一個圖,用CSN表示N上所有圖對策的集合。MYERSON假定每個連通聯(lián)盟才是可行聯(lián)盟,并在此假設(shè)下引入了圖限制對策(N,vL)[2],其中特征函數(shù)vL定義為

(4)

MYERSON把圖限制對策(N,vL)的Shapley值作為一個分配規(guī)則,這就是著名的Myerson值[2],其表達式為μi(N,v,L)=Shi(N,vL)。

(5)

像引言中提到的,HAERINGER證明了賦權(quán)Myerson值可以由分支有效性和權(quán)公平性所唯一確定。而SLIKKER和VAN DEN NOUWELAND利用分支有效性、類賦權(quán)公平性、高階獨立性和類一致性給出了賦權(quán)Myerson值的不同刻畫。

2 一致性與公理化刻畫

2.1 一致性

一致性公理在值的公理化刻畫中具有重要的作用,為完成賦權(quán)Myerson值的公理化刻畫,我們首先引入賦權(quán)縮減圖對策和縮減圖的定義。

(6)

這里的Tc=NT表示T的補集,也即不在聯(lián)盟T中的參與者,而w|S∪Tc表示權(quán)向量w在S∪Tc上的限制。賦權(quán)縮減圖對策的含義為:在賦權(quán)縮減圖對策下,聯(lián)盟S的效用等于聯(lián)盟S與所有離開的參與者在賦權(quán)圖限制對策下進行合作所產(chǎn)生的效用,減去所有離開的參與者按照原分配規(guī)則φw所分得的收益和。

(7)

這里N(P)表示路P上參與者的集合。賦權(quán)縮減圖的邊包含兩部分,一是由T導(dǎo)出的子圖的邊,也即LT。二是新增加的邊:若T中的兩個參與者能由T之外的參與者形成的路所連結(jié)(除T中的這兩個參與者外,路上的其他參與者均在Tc中),則在這兩個參與者之間增加一條邊。

在定義了賦權(quán)縮減圖對策和縮減圖的基礎(chǔ)上,現(xiàn)提出權(quán)意義下的一致性公理。

則φw稱具有w-一致性。

2.2 賦權(quán)Myerson值的公理化刻畫

為了證明賦權(quán)Myerson值滿足w-一致性,根據(jù)上一小節(jié)所定義的賦權(quán)縮減圖對策和縮減圖,本小節(jié)首先給出一個關(guān)鍵的引理。這個引理給出了在賦權(quán)Myerson下任意聯(lián)盟S?T在賦權(quán)縮減圖限制對策和原賦權(quán)圖限制對策中的紅利關(guān)系式。

引理1設(shè)(N,v,L,w)為任意的賦權(quán)圖對策,T?N,則對任意的S?T,S在賦權(quán)縮減圖限制對策的紅利值滿足

下面利用上述引理證明賦權(quán)Myerson值滿足w-一致性。

為最終給出賦權(quán)Myerson值的公理化刻畫,我們需要引入下面的w-標準性。

w-標準性的含義為:對于一個兩人賦權(quán)圖對策,若兩個參與者不連通,則每個參與者所獲得的收益為自身產(chǎn)生的效用。若兩個參與者連通,則每個參與者先獲得自身產(chǎn)生的效用,再將剩余效用按照自身權(quán)重與總權(quán)重的比例進行分配。容易證明賦權(quán)Myerson值滿足w-標準性。

在利用w-一致性和w-標準性給出賦權(quán)Myerson值的刻畫之前,我們首先證明,若分配規(guī)則滿足w-一致性和w-標準性,則其一定滿足分支有效性。

3 結(jié)論

本文研究了賦權(quán)圖對策中賦權(quán)Myerson值的公理化刻畫問題,用一致性公理給出了賦權(quán)Myerson值的新的刻畫。為達到此目的,提出了賦權(quán)縮減圖對策和縮減圖的定義及賦權(quán)意義下的一致性公理。通過建立每個聯(lián)盟在賦權(quán)縮減圖限制對策和原賦權(quán)圖限制對策中的紅利關(guān)系,證明了賦權(quán)Myerson值滿足一致性,從而避開以往文獻中需要借助潛能函數(shù)才能完成的滿足一致性證明。最后用w-一致性和w-標準性給出了賦權(quán)Myerson值的公理化刻畫。