一類具有限制聯(lián)盟結(jié)構(gòu)的合作對策的兩階段Shapley值

王利明

(1.內(nèi)蒙古財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)與數(shù)學(xué)學(xué)院,內(nèi)蒙古 呼和浩特 010070; 2.內(nèi)蒙古經(jīng)濟(jì)數(shù)據(jù)分析與挖掘重點(diǎn)實(shí)驗(yàn)室,內(nèi)蒙古 呼和浩特 010070)

0 引言

在合作對策中，聯(lián)盟結(jié)構(gòu)是指局中人集合的一個(gè)劃分,劃分中的每個(gè)子集表示局中人結(jié)成的一個(gè)優(yōu)先聯(lián)盟。 優(yōu)先聯(lián)盟內(nèi)的局中人或者同時(shí)參與合作，或者同時(shí)不參與合作，即以整體的姿態(tài)參與大聯(lián)盟的合作。 很多學(xué)者對具有聯(lián)盟結(jié)構(gòu)的合作對策進(jìn)行研究，給出了解的概念，如Owen值[1]，Banzhaf-Owen值[2],對稱聯(lián)盟Banzhaf值[3]等。 2009年，Kamijo[4]從不同角度定義了具有聯(lián)盟結(jié)構(gòu)的合作對策的一個(gè)解，因在優(yōu)先聯(lián)盟之間和優(yōu)先聯(lián)盟內(nèi)部分別計(jì)算Shapley值，稱之為兩階段Shapley值(two-step Shapley value)。

在經(jīng)典的具有聯(lián)盟結(jié)構(gòu)的合作對策中，通常假設(shè)優(yōu)先聯(lián)盟作為一個(gè)整體互相之間可以任意結(jié)盟，優(yōu)先聯(lián)盟內(nèi)部的局中人也可以任意結(jié)盟。 然而在現(xiàn)實(shí)生活的合作實(shí)踐中，經(jīng)常會(huì)出現(xiàn)優(yōu)先聯(lián)盟之間或內(nèi)部結(jié)盟有限制的情形。 基于此，學(xué)者們討論了具有限制聯(lián)盟結(jié)構(gòu)的合作對策。 例如，Kongo[5]，van den Brink等[6]，Béal等[7]研究了優(yōu)先聯(lián)盟之間和內(nèi)部具有交流結(jié)構(gòu)限制的合作對策，Meng等[8,9]研究了凸幾何上的具有聯(lián)盟結(jié)構(gòu)的合作對策、擴(kuò)張系統(tǒng)上的具有聯(lián)盟結(jié)構(gòu)的合作對策，孫紅霞等[10]研究了優(yōu)先聯(lián)盟之間具有格結(jié)構(gòu)的合作對策。

在文獻(xiàn)中被廣泛研究的另外一類具有合作限制的合作對策是具有權(quán)限結(jié)構(gòu)的合作對策[11,12]。 在這類合作對策中，局中人需要其上級的許可才可以參與合作并發(fā)揮作用。 本文討論局中人結(jié)成優(yōu)先聯(lián)盟參與合作且優(yōu)先聯(lián)盟內(nèi)有權(quán)限結(jié)構(gòu)限制的合作對策。 利用兩階段Shapley值的分配思想給出這類合作對策的一個(gè)解，證明其滿足的公理體系，并通過例子驗(yàn)證了公理的獨(dú)立性。

1 預(yù)備知識

1.1 合作對策

用N={1,2,…,n}記局中人集合，v:2N→R滿足v(?)=0，則稱(N,v)為一個(gè)合作對策。?E?N，v(E)表示聯(lián)盟E內(nèi)局中人通過合作獲得的收益。 在不致引起混淆的情況下，合作對策(N,v)也用其特征函數(shù)v來表示。N上的所有合作對策記為GN。

設(shè)N′?N，稱(N′,v|N′)是(N,v)的一個(gè)子對策，其中v|N′是v限制在N′上得到的函數(shù)，即v|N′(E)=v(E)，?E?N′。 如果v∈GN滿足v(E)≤v(F)，?E?F?N，稱v是單調(diào)的。 如果i∈N滿足v(E∪{i})=v(E)，?E?N{i}，則稱i是v中的零元。 如果i∈N滿足v(E∪{i})=v(E)+v({i})，?E?N{i}，則稱i是v中的啞元。如果i∈N滿足v(E)=0，?E?N{i}，則稱i是v中的必要元。 如果i,j∈N滿足v(E∪{i})=v(E∪{j})，?E?N{i,j},則稱i和j在v中對稱。

映射ξ:GN→Rn稱為合作對策的一個(gè)單值解(簡稱解)，其中ξi(v)表示分給局中人i∈N的收益分配值。Shapley值[13]是被廣泛應(yīng)用的一個(gè)單值解，定義如下:

(v(E)-v(E){i}),?i∈N

1.2 具有聯(lián)盟結(jié)構(gòu)的合作對策

映射ξ:GN×CN→Rn稱為具有聯(lián)盟結(jié)構(gòu)的合作對策的一個(gè)解。 Kamijo[4]定義的具有聯(lián)盟結(jié)構(gòu)的合作對策的兩階段Shapley值如下：

1.3 具有權(quán)限結(jié)構(gòu)的合作對策

van den Brink等[12]對合取Shapley權(quán)限值進(jìn)行了公理刻畫。 下面給出解ξ:GN×SN→Rn需要滿足的一些性質(zhì)。

可加性 對任意v1，v2∈GN，S∈SN,有ξ(v1+v2,S)=ξ(v1,S)+ξ(v2,S)。

必要元性 設(shè)v∈GN是單調(diào)的，S∈SN，i是合作對策v中的必要元，則ξi(v,S)≥ξj(v,S)，?j∈N。

定理1[12]合取Shapley權(quán)限值φ是滿足有效性，可加性，非本質(zhì)元性，必要元性和結(jié)構(gòu)單調(diào)性的唯一解。

2 聯(lián)盟內(nèi)部限制兩階段Shapley值

注如果Sk(Ck)=?,?k∈M，則限制TS值KaS就是兩階段Shapley值[4];如果Γ={N}，則KaS就是合取Shapley權(quán)限值[11];如果Γ={{1},{2},…,{n}}，則KaS就是Shapley值[12]。

限制TS值KaS可以看作通過下面的兩階段分配得到的。

第一步，將大聯(lián)盟的收益根據(jù)商對策u的Shapley值分配給各個(gè)優(yōu)先聯(lián)盟，即每個(gè)優(yōu)先聯(lián)盟Ct獲得的分配為Sht(u)。

第二步，將每個(gè)優(yōu)先聯(lián)盟Ct在第一步獲得的收益Sht(u)分配給內(nèi)部各個(gè)局中人：v(Ct)部分根據(jù)具有權(quán)限結(jié)構(gòu)的對策(v|Ct,St)的合取Shapley權(quán)限值分配給Ct內(nèi)各局中人，優(yōu)先聯(lián)盟在第一步獲得的合作增益Sht(u)-v(Ct)以平均分配的方式分給Ct內(nèi)各局中人。

例設(shè)N={1,2,3,4,5}，N上的合作對策定義為:v({i})=0,?i∈N;

v({1,2})=3,v({3,4})=3,v({3,5})=4,v({4,5})=3，其余v({i,j})=0;

v(S)=2|S|，?S?N且|S|=3或4;

v({1,2,3,4,5})=15。

N上的限制聯(lián)盟結(jié)構(gòu)ΓS為:Γ={C1,C2}，其中C1={1,2},C2={3,4,5};S1(1)={2},S1(2)=?;S2(3) ={4,5},S2(4)=?,S2(5)=?。

下面給出限制TS值的公理刻畫結(jié)論，并通過一些解的例子說明這些公理是相互獨(dú)立的。

證明首先證明KaS滿足上述六條公理。

(1)有效性。由KaS的定義及Shapley值、合取Shapley權(quán)限值均滿足有效性，有

φi((αv1+βv2)|Ct,St)

若k?F′，則k是商對策uF′中的啞元，且?i∈Ck，i是ωF中的零元，從而是(N,ωF,ΓS)中的非本質(zhì)元。 由聯(lián)盟非本質(zhì)元性，對任意i∈Ck且k∈MF′,Ωi(ωF,ΓS) =0。

再由有效性得到

(1)

分兩種情形討論優(yōu)先聯(lián)盟Ck內(nèi)部的分配。

情形1f′=1。

由于每個(gè)i∈F都是ωF|Ck中的必要元，因此存在某個(gè)常數(shù)c，Ωi(ωF,ΓS)=c,?i∈F且Ωi(ωF,ΓS)≤c,?i∈αk(F)F。再由聯(lián)盟內(nèi)部結(jié)構(gòu)單調(diào)性得到Ωi(ωF,ΓS)≥c,?i∈αk(F)F。結(jié)合式(1)，得到

情形2f′≥2。

若k∈F′，則對任意E?Ck，ωF(E)=0。因此任意i∈Ck，均是子對策ωF|Ck的必要元。 由聯(lián)盟必要元性，Ωi(ωF,ΓS)=Ωj(ωF,ΓS),?i,j∈Ck。

下面通過給出幾個(gè)解的例子說明定理中公理化條件的獨(dú)立性。

φi(v|Ct,St),?i∈Ct∈Γ

則ξ4滿足有效性，聯(lián)盟非本質(zhì)元性，聯(lián)盟對稱性，聯(lián)盟必要元性，可加性，但不滿足聯(lián)盟內(nèi)部結(jié)構(gòu)單調(diào)性。

聯(lián)盟必要元性:定義f5:GN×SN→Rn為:

容易驗(yàn)證，ξ5滿足有效性，聯(lián)盟非本質(zhì)元性，聯(lián)盟對稱性，聯(lián)盟內(nèi)部結(jié)構(gòu)單調(diào)性，可加性，但不滿足聯(lián)盟必要元性。

可加性:定義f6:GN×SN→Rn為:

ξ6滿足有效性，聯(lián)盟非本質(zhì)元性，聯(lián)盟對稱性，聯(lián)盟內(nèi)部結(jié)構(gòu)單調(diào)性，聯(lián)盟必要元性，但不滿足可加性。

3 結(jié)束語

本文討論了局中人通過優(yōu)先聯(lián)盟整體參與合作，并且優(yōu)先聯(lián)盟內(nèi)部有合取權(quán)限結(jié)構(gòu)限制的合作對策，在優(yōu)先聯(lián)盟內(nèi)有些局中人需要獲得其他局中人的許可才能參與合作。 利用兩階段Shapley值和合取Shapley權(quán)限值定義了這類合作對策的解，并用一組公理唯一地刻畫該解，為現(xiàn)實(shí)社會(huì)中相應(yīng)情形下的合作收益分配問題提供了一種定量方法和理論支持。 在后續(xù)的研究工作中，可進(jìn)一步考慮其它的聯(lián)盟結(jié)構(gòu)限制方式，如二級權(quán)限結(jié)構(gòu)，即優(yōu)先聯(lián)盟之間和內(nèi)部均具有權(quán)限結(jié)構(gòu)限制的合作對策。 或者利用具有聯(lián)盟結(jié)構(gòu)的合作對策的其它解，如Banzhaf-Owen值，對稱聯(lián)盟Banzhaf值等，從不同角度給出更多的分配方式。