單而芳, 聶珊姍, 呂文蓉

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

0 引言

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

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

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

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

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

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

1.1 TU-對(duì)策和Shapley值

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

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

(1)

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

(2)

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

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

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

(3)

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

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

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

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

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

(4)

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

(5)

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

2 一致性與公理化刻畫(huà)

2.1 一致性

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

(6)

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

(7)

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

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

則φw稱(chēng)具有w-一致性。

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

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

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

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

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

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

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

3 結(jié)論

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