赋权合作博弈中的可行联盟结构与收益分配

陈少白，张 嫚，胡朝娣

(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