陳少白，張 嫚，胡朝娣

(1.武漢科技大學理學院，湖北 武漢，430065;2.武漢科技大學冶金工業(yè)過程系統(tǒng)科學湖北省重點實驗室，湖北 武漢，430065)

賦權(quán)合作博弈中的可行聯(lián)盟結(jié)構(gòu)與收益分配

陳少白1，2，張 嫚1，胡朝娣1

(1.武漢科技大學理學院，湖北 武漢，430065;2.武漢科技大學冶金工業(yè)過程系統(tǒng)科學湖北省重點實驗室，湖北 武漢，430065)

合作博弈的局中人由于投入或收益期望的不同，他們在聯(lián)盟結(jié)構(gòu)中往往具有不同的權(quán)重，因此本文提出賦權(quán)合作博弈問題。給出形成賦權(quán)合作博弈中可行聯(lián)盟結(jié)構(gòu)的規(guī)則：參與者為追求收益最大化而自發(fā)形成一個有加權(quán)平均最大收益的一級聯(lián)盟，余下被排除在外的參與者再自發(fā)形成下一個有加權(quán)平均最大收益的二級聯(lián)盟，以此類推，直至全部參與者均實現(xiàn)結(jié)盟。通過參與者在所有可行聯(lián)盟結(jié)構(gòu)中的收益確定其權(quán)益值，依此對最大聯(lián)盟結(jié)構(gòu)收益進行分配。最后通過一個算例驗證了所提出的可行聯(lián)盟結(jié)構(gòu)及其收益分配方法的合理性，即參與者權(quán)益來源于個體之間的競爭，總收益最大化反映參與者全體的合作性。

合作博弈；可行聯(lián)盟結(jié)構(gòu)；收益分配

合作博弈是博弈論中一項重要研究內(nèi)容，其應(yīng)用十分廣泛。對于多人合作博弈，Shapley值法和Banzhaf值法是經(jīng)典的收益分配方法，而Owen值則在聯(lián)盟結(jié)構(gòu)的收益分配方法中應(yīng)用較多[1-2]，對于這種方法，研究人員給出了不同程度的改進[3-4]。聯(lián)盟參與者由于投入或收益期望的不同，他們在聯(lián)盟結(jié)構(gòu)中往往具有不同的權(quán)重，故本文提出賦權(quán)合作博弈問題，對賦權(quán)合作博弈中可行聯(lián)盟結(jié)構(gòu)的形成規(guī)則進行研究，并給出不同于采用Owen值的收益分配方案。

1 研究思路

在聯(lián)盟形成過程中，如果參與者自由地追求收益最大化，則其會找加權(quán)平均收益最大的聯(lián)盟加入。對于聯(lián)盟而言，它會吸收能使聯(lián)盟加權(quán)平均收益增加的成員，而排斥或剔除使聯(lián)盟加權(quán)平均收益減少的成員，以形成賦權(quán)平均收益最大的聯(lián)盟，這里稱為一級聯(lián)盟；而被排斥在外的成員又會形成他們的加權(quán)平均收益最大的聯(lián)盟，稱為二級聯(lián)盟；如此進行下去，直到所有參與者都加入到其中的一個聯(lián)盟為止，這些聯(lián)盟組成了一個聯(lián)盟結(jié)構(gòu)。每一個參與者都希望加入上一級聯(lián)盟，只有當他達不到加入聯(lián)盟的要求時，才被迫轉(zhuǎn)而追求下一級聯(lián)盟，如此產(chǎn)生的聯(lián)盟結(jié)構(gòu)是可能出現(xiàn)的，本文稱之為可行聯(lián)盟結(jié)構(gòu)，而其它聯(lián)盟在個體逐利、信息透明的情況下不會產(chǎn)生。

如果某級聯(lián)盟出現(xiàn)多個，這樣會出現(xiàn)多種可行聯(lián)盟結(jié)構(gòu)，給成員的收益帶來不穩(wěn)定性，即一個成員可能進入一級聯(lián)盟獲得高額收入，也可能被排除在一級聯(lián)盟之外，從而產(chǎn)生較大的收益差距。為了確保收益的穩(wěn)定性，去掉隨機性，參與者之間必須作出妥協(xié)，這樣的話合作機制就發(fā)揮作用：一方面，按最大收益聯(lián)盟結(jié)構(gòu)確定聯(lián)盟結(jié)構(gòu)的總收益，另一方面，按參與者在各可行聯(lián)盟中的地位或權(quán)益進行分配。本文根據(jù)上述觀點給出基于可行聯(lián)盟結(jié)構(gòu)的權(quán)益值。

2 可行聯(lián)盟結(jié)構(gòu)

記πΔ=argmax{v(π):π∈ΠN}為最優(yōu)聯(lián)盟結(jié)構(gòu)，其中ΠN為N上所有聯(lián)盟結(jié)構(gòu)組成的集合，argmax表示括號內(nèi)函數(shù)取最大值的解。

定義1 設(shè)(N,v,ω)為集合N={1,2,…,n}上的一個賦權(quán)合作博弈，S?N，記

稱S*為S的可行聯(lián)盟，如果有多解，則S*表示S的所有可行聯(lián)盟組成的集合。

A0=N,A1∈N*,A2∈(A0-A1)*,…,Am∈(Am-2-Am-1)*,(Am-1-Am)*=?

稱π為N的可行聯(lián)盟結(jié)構(gòu)，N的可行聯(lián)盟結(jié)構(gòu)全體記為π*。

3 可行聯(lián)盟結(jié)構(gòu)的生成算法

取A1∈A1=N*，得二進制數(shù)A0-A1。

保留A0-A1中取1的項，重新進行二進制編碼，重復(fù)上述過程，可以形成若干二級可行聯(lián)盟A2=(A0-A1)*，取A2∈A2=(A0-A1)*，反復(fù)進行下去，直到余下為空集為止，最終可得到所有N的可行聯(lián)盟結(jié)構(gòu)。

4 可行聯(lián)盟結(jié)構(gòu)的收益分配

可行聯(lián)盟結(jié)構(gòu)是依照博弈局中人個體追求利益最大化的原則形成，可行聯(lián)盟結(jié)構(gòu)與最優(yōu)聯(lián)盟結(jié)構(gòu)可以不同，從整個博弈過程來看，后者較前者可以獲得更大的整體利益。在獲得整體最大利益后，需要根據(jù)局中人在可行聯(lián)盟中的地位來確定收益的分配。另外，由于可行聯(lián)盟結(jié)構(gòu)可能不止一個，局中人在不同的可行聯(lián)盟結(jié)構(gòu)中的地位可能有很大落差，于是局中人必須降低其期望值，確保他有穩(wěn)定收益。

(1)

(2)

在可行聯(lián)盟結(jié)構(gòu)下，局中人各自追求的是使其收益最大的最優(yōu)可行聯(lián)盟結(jié)構(gòu)，記各種可行聯(lián)盟的總收益為：

(3)

則局中人在博弈中的權(quán)益值為：

(4)

收益分配步驟如下:

(1)確定最大收益聯(lián)盟結(jié)構(gòu)，即實際實施的聯(lián)盟結(jié)構(gòu)，計算其總收益；

(2)求出各可行聯(lián)盟結(jié)構(gòu)，分別計算各可行聯(lián)盟的收益總和；

(3)計算出各局中人在這些可行聯(lián)盟結(jié)構(gòu)中所占的收益比例；

(4)對所有可行聯(lián)盟結(jié)構(gòu)取平均值，確定各局中人的權(quán)益值；

(5)局中人按其權(quán)益值對最大收益聯(lián)盟結(jié)構(gòu)的總收益進行分配。

5 算例

對于最優(yōu)聯(lián)盟結(jié)構(gòu)，4、5車間的組合僅僅使這兩個車間獲得平均兩個單位的收益，而聯(lián)盟結(jié)構(gòu){{1,2},{3,4,5}}的總收益雖然只有11，但由于4、5車間將3車間拉進聯(lián)盟，將使這3個車間獲得平均3個單位的收益。這表明，如果按最優(yōu)聯(lián)盟結(jié)構(gòu)的聯(lián)盟收益來分配，4、5車間將會因為照顧整體的最大收益而犧牲自己的部分權(quán)益。以下采用本文提出的可行聯(lián)盟結(jié)構(gòu)方法來確定各車間的權(quán)益值。

第一步 確定一級聯(lián)盟N*有兩個：

A1={1,2,3}，A2={3,4,5}

第二步 確定二級聯(lián)盟(A0-A1)*：

A12={4,5}，A21={1,2}

由于沒有三級聯(lián)盟，所以獲得兩個可行聯(lián)盟結(jié)構(gòu)：

π1={A1={1,2,3},A12={4,5}}

π2={A2={3,4,5},A21={1,2}}

由v(π1)=v(A1)+v(A12)=9+4=13，v(π2)=v(A2)+v(A21)=9+2=11，得:

由式(4)計算得5個車間的權(quán)益值：

5個車間的最優(yōu)聯(lián)盟結(jié)構(gòu)為πΔ={{1,2,3},{4,5}}，獲得最大收益為13，按上述權(quán)益值進行分配，得到5個車間的收益分別為2.167、2.167、3.250、2.708和2.708。

6 結(jié)語

合作博弈的局中人由于投入和收益期望的不同，或者由于其本身為大小不同的聯(lián)盟體，他們在聯(lián)盟結(jié)構(gòu)中往往具有不同的權(quán)重，因此本文研究了賦權(quán)合作博弈問題，給出形成可行聯(lián)盟結(jié)構(gòu)的規(guī)則，并證明可行聯(lián)盟結(jié)構(gòu)的子聯(lián)盟結(jié)構(gòu)一定是一個子集上的可行聯(lián)盟結(jié)構(gòu)。根據(jù)局中人在可行結(jié)盟結(jié)構(gòu)中的收益確定其相應(yīng)的權(quán)益值，得到不同于采用Owen值的收益分配方案。該方法的合理性體現(xiàn)為：參與者權(quán)益來源于個體之間的競爭，總收益最大化反映全體參與者的合作性。

[1] Owen G．Value of games with a priori unions[M]//Mathematical Economics and Game Theory. Berlin:Springer，1977：76-88.

[2] Khmelnitskaya A B，Yanovskaya E B．Owen coalitional value without additivity axiom[J]．Mathematical Methods of Operations Research，2007,66(2)：255-261．

[3] Herings P J J, van der Laan G, Talman D．The average tree solution for cycle-free graph games[J]．Games and Economic Behavior,2008，62：77-92．

[4] Albizuri M J，Aurrecoechea J，Zarzuelo J M．Configuration values：extensions of the coalitional Owen value[J]．Games and Economic Behavior，2006，57：1-17．

[責任編輯 尚 晶]

Feasible coalitional structure and profit distribution in aweighted cooperative game

ChenShaobai1，2,ZhangMan1,HuZhaodi1

(1.College of Science, Wuhan University of Science and Technology, Wuhan 430065, China; 2. Hubei Province Key Laboratory of Systems Science in Metallurgical Process，Wuhan University of Science and Technology, Wuhan 430065, China)

Participants in a cooperative game usually have different weights in the coalitional structure because of different investments and income expectations, so this paper proposes weighted cooperative game problem. The rules to form a feasible coalitional structure in a weighted cooperative game are discussed. In order to maximize gain, a subset of players spontaneously forms a primary coalition (also called the first-level coalition) with the weighted averaged maximum gain. The remaining players spontaneously form a secondary coalition with the weighted averaged maximum revenue and so on until all players have joined the coalition. By determining the players’ equity indexes via their profits in each feasible coalitional structure, revenue of the optimal coalitional structure is allocated.A study case demonstrates the rationality of the proposed feasible coalitional structure and profit distribution method.It shows that the rights and interests of players are from the competition among individuals and the overall maximum revenue reflects the cooperation of all players.

cooperative game; feasible coalitional structure; profit distribution

2014-09-10

湖北省自然科學基金資助項目(2013CFA131).

陳少白(1957-)，男，武漢科技大學教授. E-mail:chenshaobai71@163.com

O225

A

1674-3644(2015)01-0077-04