賦權合作博弈中的可行聯盟結構與收益分配

陳少白，張 嫚，胡朝娣

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

賦權合作博弈中的可行聯盟結構與收益分配

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

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

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

合作博弈；可行聯盟結構；收益分配

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

1 研究思路

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

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

2 可行聯盟結構

記πΔ=argmax{v(π):π∈ΠN}為最優聯盟結構，其中ΠN為N上所有聯盟結構組成的集合，argmax表示括號內函數取最大值的解。

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

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

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

稱π為N的可行聯盟結構，N的可行聯盟結構全體記為π*。

3 可行聯盟結構的生成算法

取A1∈A1=N*，得二進制數A0-A1。

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

4 可行聯盟結構的收益分配

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

(1)

(2)

在可行聯盟結構下，局中人各自追求的是使其收益最大的最優可行聯盟結構，記各種可行聯盟的總收益為：

(3)

則局中人在博弈中的權益值為：

(4)

收益分配步驟如下:

(1)確定最大收益聯盟結構，即實際實施的聯盟結構，計算其總收益；

(2)求出各可行聯盟結構，分別計算各可行聯盟的收益總和；

(3)計算出各局中人在這些可行聯盟結構中所占的收益比例；

(4)對所有可行聯盟結構取平均值，確定各局中人的權益值；

(5)局中人按其權益值對最大收益聯盟結構的總收益進行分配。

5 算例

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

第一步 確定一級聯盟N*有兩個：

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

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

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

由于沒有三級聯盟，所以獲得兩個可行聯盟結構：

π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個車間的權益值：

5個車間的最優聯盟結構為πΔ={{1,2,3},{4,5}}，獲得最大收益為13，按上述權益值進行分配，得到5個車間的收益分別為2.167、2.167、3.250、2.708和2.708。

6 結語

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

[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