图联盟结构核的求解算法*

尚传启，刘惊雷

烟台大学 计算机与控制工程学院，山东 烟台 264005

1 引言

联盟博弈是处理几个实体间竞争、合作的策略，它假定所有的Agent都是理性的，即每一个Agent都会为了寻求自身利益的最大化，选择与他人合作（联盟）。正因为Agent具有自由联盟的能力，吸引了AI和MAS（multi-agent system）更多的关注[1]。然而在实际生活中联盟博弈具有复杂性和多样性，例如联盟的生成往往受到各种条件的限制，联盟行为具有动态性，无法快速达到稳定状态等问题。这些问题使得联盟中的成员无法快速获得最大利益，长时间处于转换联盟的动荡中，设计带有限制的联盟生成机制和构造稳定联盟结构及其分配的算法已经成为一个重要的研究目标。

一直以来对于合作博弈的研究，大都假定任意联盟可行，对于联盟的生成问题，仅从联盟内部因素考虑，忽略了外部环境对于联盟生成的影响。然而在外部环境中往往会存在许多限制和阻碍，比如距离、时间等因素，甚至与用户的性格有关。寻找一种方法，模拟现实中的各种限制，直观、简单地表现出联盟的生成关系就显得十分必要。本文采用约束图作为约束条件，来约束联盟的生成。下面通过对一个热点问题的分析来展示约束图的表现效果。图1表现的是无线合作文件共享系统[2]。由图可以发现用户间的联盟生成关系：用户1、3由于距离的原因无法组成联盟{1,3}，但是可以通过用户2作为“桥梁”来组建联盟 {1,2,3}，用户3、4、5可以自由组建联盟，由于距离的限制，用户4、5无法与用户1、2进行通信，需要借助用户3作为“桥梁”。通过上述的分析，可以发现由于外部环境的影响，联盟的生成变得复杂，通过交互图可以模拟实际应用中联盟生成的障碍。

Fig.1 Wireless file sharing system图1 无线合作共享系统

Agent加入联盟的目的是为了获得更大的利益，然而在传统研究中默认联盟利益满足超加性（若两个联盟合并，那么合并后的联盟具有的利益至少是合并前两个联盟的利益之和），这就使得大联盟（包含所有Agent的联盟）一定具有最大的社会福利。事实上Agent间组成联盟需要花费一定的代价，有时代价甚至大于联盟的收益，因此联盟利益满足超加性具有理想化的特点，运用它来解决现实中出现的问题并不适合。将联盟花费的概念引入，研究非超加性联盟博弈更具现实意义。多数文章在研究合作博弈时，考虑如何令联盟的结果有利于社会的发展（即找到最大社会福利的联盟结构），很少研究联盟利益分配的问题。出于理性考虑，Agent组成联盟的动力就是获得更大的利益，仅找到具有最大社会福利的联盟结构，而不将利益公平地分配给联盟的参与者是不合理的。在一些存在分配的研究中，大都采用夏普利值[3]作为分配方案，虽然这种方案具有公平性，但是产生的分配却可能不满足理性条件（Agent可能在联盟中分得的利益小于自己单独工作的利益）。这违背了Agent联盟的初衷，Agent将离开联盟，造成联盟破裂，因此这种分配方案并不具有稳定性和实用性。采用按劳分配作为初始分配方案将联盟利益分配给联盟中的每一位参与者，然后调整初始分配，使得联盟中的Agent获得最大利益，这样得到的分配兼具理性和公平性。

在现实社会中联盟的生成问题是动态的、持续的。事实上，旧联盟的破裂与新联盟的生成时刻都在发生，但是新旧间的替换并不是无迹可寻的。Agent组成联盟的目的是追寻更大的利益，那么一定存在一个可以使大多数或全部Agent获得最大利益的稳定联盟。然而，在现实中由于联盟数目众多，信息不明确等问题，无法快速找到最优的联盟，只能一次次尝试不同的联盟。本文算法采用核、谈判集、稳定成本等概念，快速求解稳定联盟结构和利益分配，可以保证大多数Agent获得最大利益。相较于传统联盟博弈的研究，本文具有的特点和贡献在于：

（1）在传统生成联盟的基础上考虑了外部约束，采用图形拓扑结构约束联盟的生成，并且引入联盟花费的概念，使得生成的联盟利益不再具有超加性，符合现实联盟生成和利益的特点，更好地将合作博弈的理论应用到实际领域中。

（2）采用按劳分配作为联盟的初始利益，运用谈判集、稳定成本作为初始利益调整方案，使得调整后的分配满足核的定义，即使在合作博弈不满足超加性的情况下，仍然满足每个Agent的理性条件，保证联盟的稳定性。

（3）设计了有效的求解联盟核算法，去除了不符合实际的联盟的生成，降低了求解联盟结构核的时间，算法复杂度为O(3n)，相较于以往的时间复杂度为O(nn)的研究具有快速性[4]。

2 相关工作

本文将从联盟生成、联盟利益分配、联盟稳定性三方面，简要地描述图联盟收益分配的相关工作。

在传统联盟博弈理论中，假定大联盟一定是最优的，对于联盟利益分配的研究也仅限于大联盟之中。传统理论对于大联盟的利益分配问题提供了多种方案，比如核[5]、夏普利值[3]、核仁[6]。最近，AI和MAS的研究人员一直在研究大联盟形成的可能性，发现生成大联盟存在多种限制，而且大联盟可能不是最优的联盟结构，反而多个小的联盟组成的联盟结构具有更好的可实现性和最优性。这个问题也被称为联盟结构生成（coalition structure generation，CSG）问题，在AI和MAS上一直是一个活跃的研究课题[1]。关于带有约束图的联盟博弈，Myerson在1976年就已经提出[7]，但是只对它进行了理论分析，并没有利用它来解决实际问题。最近Myerson的这篇文章由于其在自然领域的适用性，受到了越来越多的关注。例如Skibski等人将它应用到了恐怖主义网络的研究当中[8-9]，Zhang等人分析了它在现实社会中的利益分配问题[10]。利用约束图作为联盟生成的约束条件，剔除不切实际的联盟，能够降低算法的时间复杂度。Yeh首次提出了动态规划（dynamic programming，DP）算法[11]，并用来解决集合划分问题。徐广斌等人基于DP算法求最优联盟的问题，提出了联盟约束动态规划（coalition constrain dynamic programming，CCDP）算法[12]。本文吸取Myerson的理论，采用简单的图形拓扑关系模拟现实中的约束，并吸取CCDP算法动态生成最优联盟的思想，改进CCDP算法生成最优联盟结构。

合作博弈最困难也最有挑战性之处在于建立一个统一解（分配）的概念，即从各种各样的具有不同良好性质的解中挑选出唯一的配置。近年来，利用夏普利值进行联盟利益分配成为很多文章的分配选择，这种方案最大的优点就在于它的公平性[13]。若博弈具有超加性，夏普利值可以作为一个分配，且满足理性约束条件φ(xi)≥v({i})，即Agent在联盟中个人所得利益一定大于单独工作的利益。但当博弈不具有超加性时，夏普利值并不满足理性约束条件。本文研究的图联盟博弈不具有超加性，因此夏普利值并不适用于本文的研究。本文将按劳分配[14]作为初始分配方案，将联盟中每个Agent单独工作时的获利当作它对联盟收益的贡献。根据每个Agent的贡献按比例将联盟利益分配给联盟成员，得到的分配兼具理性和公平性。

联盟博弈假定所有的Agent都是理性的，要使一个联盟结构具有稳定性，必然要令联盟结构中所有联盟都稳定，这要求联盟的成员在联盟中获取最大的利益。在现实中令联盟达到稳定十分困难，存在各种各样的问题。最近Sless等人对社会网络的复杂性进行了研究，发现如果寻找稳定状态，必须将所有联盟利益和分配进行对比，找出最优的联盟结构及其利益分配。Sandholm等人在Sless的后续工作中，通过研究发现CSG问题的复杂性在最坏情况下为O(nn)[15]。Rahwan等人为了降低问题的时间复杂度，基于动态规划编写顶级算法，时间复杂度为O(3n)[4]，节省了大量的运算时间。然而在他们提出的模型中，Agent可以任意地组成联盟，而且并未对联盟结构进行利益的分配。Chalkiadakis等人2016年发表在人工智能上的一篇文章中[2]，提出了以图作为约束条件约束联盟生成，并寻找稳定分配的问题，在这篇文章中发现，最稳定的分配必然存在于具有最大利益的联盟结构中，并对它进行证明，但是并没有给出寻找稳定分配的算法。核作为一个最早的稳定分配概念，经常被人们用在联盟博弈中，从Breton等人的文章中了解到[16]，根据Scarf的引理[17]，如果联盟博弈是超加性的，那么它的核一定不是空集，但是他们却没有提出一个有效的快速找核的算法。Demange在后续工作中不仅验证了超加性联盟博弈具有非空的核，也验证了非超加性联盟博弈也具有非空核，还提供了一个关于计算核的程序，但是Demange的算法并不能求得非超加性联盟博弈的核。本文提出的SCP（stable core programming）算法可以求得超加性和非超加性的联盟博弈的核，快速寻找具有最大社会福利的联盟结构。

3 图联盟博弈与分配方案的相关定义

3.1 图联盟博弈的相关定义

本节主要通过介绍一些背景和相关符号来形式化框架。一个Agent集合N={1,2,…,n}，集合N的基为n，即|N|=n，用G=(N,E)表示一个由n个Agent组成的约束图[18]。

定义1（约束图）约束图由一个二元组(N,E)组成，即G=(N,E)，N为图中Agent的集合，E为图中Agent间的通信关系，当且仅当E(x,y)=1时，Agentx和y可以组成联盟。

将复杂的通信网络图划分成简单的约束图，其目的是简化社会通信网络，降低图中联盟的数量，从而降低算法求解时间。而降低求解时间则是为了更快地刷新最优联盟结构，规避联盟博弈的动态性和不稳定性带来的问题。下面介绍几种特殊的图形拓扑结构。

零散图（scattered graph），如图2（a）所示，当图中包含的约束条件最多时，即图中没有任何两个Agent间存在连接，禁止任何联盟的生成，可行的联盟个数为0，称这种约束图为零散图。

完全图（complete graph），如图2（b）所示，当G中存在的约束条件最少时，即所有Agent间都存在连接，任意两个Agent都可以建立联盟。若|N|=n，可生成的联盟个数为2n-1，称这种约束图为完全图。

链状图（chain graph），如图2（c）所示，图中包含的所有Agent通过一条线串联起来形成一条通路，这种结构具有的约束条件为：只有两个临近的Agent可以组成联盟，但是两个距离较远的Agent，可以通过它们之间所有的Agent作为“桥梁”构建联盟，若链状图中一个Agent出现问题发生断裂，不但发生断裂的Agent无法与其相邻的Agent组成联盟，而且原来以它为“桥梁”的所有联盟都无法生成，链状图中可行的联盟个数为0.5(n2+n)。

星状图（star graph），如图2（d）所示，图中以一个Agent为中心，其他所有Agent能且只能与位于中心位置的Agent建立连接。处于中心位置的Agent是所有联盟生成的核心Agent，任何联盟的生成都需要核心Agent的加入，当除了核心点外的其他Agent失去与核心Agent连接时，将只能选择自己单独工作，无法加入任何联盟。同样，当核心Agent消失，约束图就变为零散图，星状图中可行的联盟个数为n+2n-1-1。

Fig.2 Graph topology图2 图形拓扑结构

混合型拓扑结构（hybrid topology），就是含有两种或两种以上的拓扑结构同时使用的约束图。

定义2（图约束联盟）若Agent集合N的非空子集C中的Agent在约束图G中所诱导的子图G[C]=1，称C为图约束联盟，数学形式定义为：

在一个满足约束图约束条件的联盟中，所有成员合作产生的回报（收益）为联盟收益，赋值函数v:P(N)→R，其中P(N)表示集合N的幂集。例如v({1,2,3})=66，表示成员1、2、3组成联盟 {1,2,3}所能产生的收益为66。

定义3（图联盟博弈）图联盟博弈是由N、v、G组成的三元组，即Γ={N,v,G}，其中N表示所有参与博弈的Agent形成的集合，v为每一个可行联盟的收益，G代表图联盟博弈的约束图。

定义4（联盟结构）在Γ={N,v,G}中，一个或数个互不相交的可行联盟组成集合，若集合中包含所有的Agent，那么将此集合称为联盟结构，并用符号Λ表示，其数学形式定义为：约束图G上所有可行的联盟结构在下文中均用Cs(G)表示，可行的联盟结构应满足3个要求[19]：

（1）Λ中包含参与联盟博弈的所有Agent，即满足式子C1⋃C2⋃…⋃Ck=N。

（2）Λ中的联盟为满足约束图G=(N,E)约束条件的可行联盟。

（3）Λ中的任意两个联盟的交集为∅ ，即一个Agent只能加入一个联盟。

定义5（社会福利）联盟结构Λ中所有联盟Ci的联盟收益之和称为社会福利，并用符号Sw(Λ)表示，其数学形式化定义为：

在图联盟博弈Γ={N,v,G}中，最大社会福利用符号Swm(Γ)表示，Cs(G)中具有最大社会福利的联盟结构用符号Cs*表示。

定义6（个人所得利益）联盟C中的Agenti可以从联盟利益v(C)中分得的利益称为个人所得利益，用符号xi表示，并且xi满足等式：

定义6保证了将v(C)无保留地分配给联盟中的成员，因为联盟C中单个Agent的个人所得利益之和等于v(C)且v(C)是一个定值，所以无法在不损害其他Agent的个人所得利益的情况下，单独增加一个Agent的个人所得利益，因此定义6的定义满足帕累托效率性（Pareto efficiency）。

为了更好地理解上述的定义，下面通过例1来进行说明。

例1给定图联盟博弈Γ={{1,2,3},v,G1}，假设参与博弈的用户集合N={1,2,3}，约束图为图3所示的链状图，联盟收益v满足下列等式：

Fig.3 Chain graphG1图3 链状图G1

根据联盟结构的定义4，可以寻得可行的联盟结构Cs(G)：

根据定义5，Sw(Λ)依次为18、14、20、18，Swm(Γ)=20，Cs*={1},{2,3}。

3.2 初始分配方案

本节主要介绍对于联盟利益所采用的初始分配方案和方案特点，以及它相较于夏普利值的优点。

本文选用按劳分配作为初始分配方案[14]，简单来说，按劳分配就是将每一个Agent单独工作所能获得的利益，看作他们在联盟中所能做出的贡献，然后根据每一个Agent的贡献值，公平地将联盟利益分配给联盟的参与者。对联盟利益进行初始分配是调整分配得到稳定分配的基础。

定义7（按劳分配）在图联盟博弈Γ={N,v,G}中，按照单个Agent所提供给联盟C的贡献量分配联盟利益v(C)，单个Agenti在联盟C中可获得的个人所得利益xi满足等式：

采用夏普利值作为分配方案，就是根据Agent的边际贡献（Agent每可以加入一个联盟，均产生收益）计算每个Agent应得的利益，分配结果满足匿名性、有效性、可加性和虚拟性的特点。本文研究的图联盟博弈Γ={N,v,G}不具有超可加性。若采用夏普利值作为分配方案将联盟利益分配给单个Agent，得到的分配结果可能并不是一个分配，即不满足理性约束条件φ(xi)≥v({i})。当处在联盟状态的Agenti个人所得利益xi小于自己单独工作所获得利益v({i})时，Agenti会选择脱离联盟，单独工作或加入其他联盟，破坏原有联盟结构的稳定性，形成新的联盟结构。因此夏普利值对于本文研究的图联盟博弈并不适用。

如下的例2，利用按劳分配将联盟利益分配给单个Agent，给出了按劳分配的分配特点。

例2给定图联盟博弈Γ={{1,2,3},v,G2}，假设参与博弈的用户集合N={1,2,3}，约束图为图4所示的链状图，联盟收益v满足下列等式：

Fig.4 Chain graphG2图4 链状图G2

根据联盟结构的定义4，可以寻得可行的联盟结构Cs(G)：

根据定义5，Sw(Λ)依次为 23、33、20、24,Swm(Γ)=33，Cs*={1,3},{2}。

根据按劳分配的定义7，对联盟结构Λ依次进行初始利益分配：

4 稳定分析和初始分配调整方案

以下分析了稳定的联盟结构及分配所具有的特点，并发现采用按劳分配方案产生的分配结果可能是不稳定的。为了使联盟稳定往往需要满足每一个Agent的理性要求，但很多时候，由于联盟利益的限制，该要求是无法实现的，这使得寻找稳定分配具有复杂性。本文将分析复杂性并提出相应的分配调整方案，使得最终分配结果具有稳定性。

4.1 稳定分析

在Chalkiadakis等人的研究中发现，稳定的分配必然存在于具有最大社会福利的联盟结构内[2]，因此寻找的稳定联盟结构就是具有最大社会福利的联盟结构Cs*。若Cs*中处于联盟状态的Agent，均可以在Cs*中同时获得自身的最大期望利益，那么分配具有稳定性，这样的分配满足核的定义，因此将核的概念引入，将核作为主要考虑的稳定因素，定义它为实现最大社会福利的联盟结构及其分配。

定义8（核）在图联盟博弈Γ={N,v,G}中，Λ∈Cs*，xi∈Λ，对于任意一个联盟结构Λ∈Cs(G)，都有x(C)≥v(C)，称(Λ,(xi))为联盟结构的核，其数学形式定义为：

需要说明的是核有可能是空的，当联盟结构中所有处于联盟状态的Agent可获得的最大期望利益之和大于最大社会福利时，核为空。

通过一个简单的例3来表述核的定义。

例3给定图联盟博弈Γ={{1,2,3},v,G1}，假设参与博弈的用户集合N={1,2,3}，约束图为图3所示的链状图，联盟收益v满足下列等式：

根据联盟结构的定义4，可以寻得可行的联盟结构Cs(G)：

根据定义5，Sw(Λ)依次为 24、22、34、20,Swm(Γ)=34，Cs*={1},{2,3}。

根据按劳分配的定义7，对联盟结构Λ依次进行初始利益分配：

联盟结构 {1},{2,3}为实现最大社会福利的联盟结构Cs*，并且在此联盟结构中，所有处于联盟状态的Agent均获得了最大期望利益，因此({1},{2,3},(4,12,18))满足定义8，是联盟博弈的核，Cs-core(Γ)=({1},{2,3},(4,12,18))。

然而在实际应用中往往不会和例3一样，Cs*的初始分配结果正好满足核的定义，会出现以下3种情况：

（1）具有多个最大社会福利的联盟结构Cs*，即具有多个互不相同的联盟结构Λ，它们的社会福利均为最大社会福利Swm(Γ)。

（2）利用按劳分配作为初始分配方案，得到分配结果可能不是最优的，即存在个别处于联盟状态的Agent获利小于其他形式的联盟，不满足核的定义。

（3）无法令所有处于联盟状态的Agent同时获得最大利益，即核为空的情况。

4.2 解决方案

本节根据4.1节中可能发生的3种情况，提出了对应的解决方案，并用实例验证了方案的可行性。

情况（1）具有最大社会福利的联盟结构有多个，提出次稳定联盟结构Λ*的定义，在多个具有最大社会福利的联盟结构Cs*中，寻找最优的联盟结构作为次稳定联盟结构Λ*。在现实博弈中，可以令多数Agent同时获得最大利益的联盟结构才更加具有稳定性，因此选取令多数Agent获得最大利益的Cs*作为Λ*。

定义9（次稳定联盟结构）假设图联盟博弈Γ={N,v,G}存在多个Cs*，选取多数Agent获得最大利益的联盟结构Λ作为Λ*，并用符号Λ*表示。

若次稳定结构Λ*及其分配满足定义8，那么称(Λ*,(xi))为次稳定核，用符号Cs-score(Γ)表示，Csscore(Γ)=(Λ*,(xi))。

例4给出了次稳定联盟结构的应用。

例4给定图联盟博弈Γ={{1,2,3},v,G1}，假设参与博弈的用户集合N={1,2,3}，约束图为图3所示的链状图，联盟收益v满足下列等式：

根据联盟结构的定义4，可以寻得可行的联盟结构Cs(G)：

根据定义5，Sw(Λ)依次为35、40、40、40，Swm(Γ)=34，发现具有最大社会福利的联盟结构的个数为3，且它们的利益分配结构依次为：

(9.3,10.7,20);(7,9.4,23.6);(8,9.1,22.9)

通过比较初始利益分配的结果，发现在联盟结构 {1},{2,3}中x2、x3同时取得自身利益最大值9.4和23.6，即用户2、3同时获得自身最大利益，获得最大利益的Agent个数最多。根据次稳定核的定义9，选多数Agent获得最大利益的联盟结构 {1},{2,3}作为Λ*，当用户1想要破坏联盟{2,3}的稳定性时，用户2、3出于理性考虑，不会放弃最大利益离开原联盟。因此联盟结构 {1},{2,3}具有稳定性，并且Λ*及其初始分配(7,9.4,23.6)满足核的定义，Cs-core(Γ)=({1,2},{3},(9.3,10.7,20))。

情况（2）使用按劳分配方案得到的初始分配结果不是最优的，引入谈判集的概念调整初始分配，得到一个令所有Agent都满意的分配，并且这个分配满足核的定义。

定义10（谈判集）若C∈Cs*，i∈C，Agenti在Cs*中获取的利益xi小于Agenti在其他联盟中的利益，它可以向联盟C发出异议，要求重新划分利益，增加自身利益至期望值，其他Agent考虑是否接受，商量出一个可行的分配结果。

谈判集（bargaining set）最早是由Aumann等人于1964年提出的[20]，它是根据局中人之间可能出现的互相谈判而提出的合作博弈的解的概念，联盟C中的参与人i向联盟中其他参与人j提出异议，要求偏离现有的配置x，如果符合条件y(C)=v(C),yk＞xk,∀k∈S，其中S∈Γij≡ {C∈2N|i∈C,j∉C},y=(yk)k∈S，那么这种威胁就是可行的。参与人i提出异议的目的并不是阻止达成合作，而是希望能够从参与人j处得到转移利益（transfer of money），即在可行集内部改变财富的分配。

设置谈判的上下限均为Agent的最大利益期望，即相比于其他联盟，发起异议的Agent只能提出增大自身利益至最大利益期望的要求，接受异议的Agent只有在转移自身利益后，剩余利益依然满足自身的最大利益期望时，才会接受划分自身利益，谈判才能成功，接受异议的Agent将自身利益作为转移利益分给提出异议的Agent完成谈判。

例5给出了谈判集的应用。

例5给定图联盟博弈Γ={{1,2,3},v,G1}，假设参与博弈的用户集合N={1,2,3}，约束图为图3所示的链状图，联盟收益v满足下列等式：

根据联盟结构的定义4，可以寻得可行的联盟结构Cs(G)：

根据定义5，Sw(Λ)依次为16、24、31、20，Swm(Γ)=31，Cs*={1},{2,3} 。

根据按劳分配的定义7，对联盟结构Λ依次进行初始利益分配：

由上式可以看出在联盟结构{1,{2,3}}中用户2的个人所得利益x2为5，而在Cs*中x2为1，这样的初始分配结果，用户2是无法接受的，破环Cs*的稳定性。根据谈判集的定义，用户2发现在联盟{2,3}中的利益小于在联盟{1,2}中的利益，向联盟{2,3}发出异议，联盟中的其他成员判断是否接受异议，并将自己的利益作为转移利益分与成员2，C即使分3个利益点给成员2，增加成员2的个人所得利益x2至最大值5，成员3依然在联盟{2,3}中取得自身的最大利益25，因此谈判成功。初始分配调整后为(1,5,25)，调整后的分配结果满足核的定义，Cs-core(Γ)=({1},{2,3},(1,5,25))。

情况（3）无法令所有处于联盟状态的Agent同时获得最大利益，即核为空，尽管Cs*具有最大社会福利Swm(Γ)，也可能发生所有处于联盟状态的Agent无法同时获得最大利益的情况。对于这种情况，次稳定结构Λ*，谈判集无法令一个核为空的博弈存在核，而稳定成本则可以解决这个问题。

定义11（稳定成本）若图联盟博弈Γ={N,v,G}的核为空，向Cs*中不稳定的联盟利益v(C)加一个最小的Δ，令联盟博弈的核不为空，那么称这个Δ为稳定成本，具有稳定成本的核用符号Cs-core(ΓΔ)表示，其数学形式化表示为：

稳定成本从联盟博弈外部条件考虑，向外部环境借用最少的利益Δ，使联盟内部的成员都可以获得最大利益，Δ能够保证图联盟结构具有非空核[21]。这里说的外部环境具有多样性，可以简单地将这个外部环境考虑为上层调控。

例6给出了稳定成本Δ的应用。

例6给定图联盟博弈Γ={{1,2,3,4},v,G3}，假设参与博弈的用户集合N={1,2,3,4}，约束图为图5所示的混合拓扑结构，联盟收益v满足下列等式：

Fig.5 Hybrid topologyG3图5 混合拓扑结构G3

通过计算可以求得Swm(Γ)=8.2，Cs*={1,2,3},{4}。对部分有特点的联盟结构Λ进行利益分配可得：

从上述特殊的分配中发现，Cs*中处于联盟状态的用户1、2、3可以获得的最大利益均为2.5。但是联盟利益v({1,2,3})=7.2，不能同时令所有用户都获得最大利益，图联盟博弈的核为空，根据稳定成本定义有：

5 构造图联盟结构核的算法

下面介绍构造图联盟博弈稳定核的SCP算法，该算法在构造图联盟博弈稳定核时，可以分为两部分：

第一部分的输入为图联盟博弈Γ={N,v,G}，输出为最大社会福利的联盟结构Cs*及其初始分配B[Cs*]和每个Agent可获得最大利益的数组S[N]。此部分在构造Cs*和B[Cs*]时，不但吸收CCDP算法的最优子结构和子问题重叠的性质[12]，并以此为基础加入利益分配，对可行的每个联盟进行初始分配，生成每个Agent可获得的最大利益数组S[N]。

第二部分的输入为第一部分的输出，输出为满足定义8的联盟结构核。这部分对第一部分得到的初始分配B[Cs*]和S[N]进行分析，并根据4.2节提供的解决方案，调整初始分配B[Cs*]，最终找到Cs*的稳定分配并形成核。这两部分分别在5.1节、5.2节中详细描述。综合以上两部分，SCP算法的输入是图联盟博弈Γ={N,v,G}，输出是联盟结构核，即具有最大社会福利的联盟结构Cs*及其稳定分配。该算法的形式化描述如算法1所示。

算法1构造图联盟结构核算法

输入：图联盟博弈Γ={N,v,G}。

输出：图联盟结构核。

//Step1调用算法2，构造最大社会福利的联盟结构Cs*，初始分配B[Cs*]，每个Agent可获得最大利益数组S[N]。

调用算法2；

//Step2调用算法3，采用定义11判断核是否为空，计算稳定成本，采用定义9寻找次稳定结构，采用定义10调整B[Cs*]。

调用算法3；

5.1 构造最优联盟结构Cs*及其初始分配B[Cs*]的算法

算法2首先根据图G生成N={1,2,…,n}，所有可行的子集组成集合Z，根据生成子集所包含的Agent个数m，将子集分为Lm层，求解每层每个联盟C的优结构M[C]、优值F[C]、分配B[C]。Ln层为包含所有Agent的大联盟，Ln层生成的优结构为Cs*，优值为Swm(Γ)，分配给Cs*的初始分配为B[Cs*]，最后从各个联盟的初始分配中，找到每一个Agent可获得的最大利益，组成最大利益数组S[N]。

算法2生成联盟结构及其初始分配算法

输入：图联盟博弈Γ={N,v,G}。

输出：具有最大社会福利联盟结构，初始分配，最大利益数组。

//Step1根据输入中给定的N、v、G,生成满足G约束的联盟C，根据|C|将生成的联盟分为Ln层，m≤n，并初始化联盟值v(C)，设置优值F[C]，优结构M[C]，初始利益分配B[C]。

//Step2求出每层每个联盟的优结构M[C]，调整优值F[C]，初始分配B[Cs*]。

下面对算法2进行详细描述，在图联盟博弈Γ={N,v,G}中，集合的基|N|=n，满足图G约束的所有可行子集组成的集合为Z，联盟C中含有的Agent个数为m，n≥m，联盟的优结构为M[C]，优值为F[C]，联盟的初始分配为B[C]，最大利益数组为S[N]。

步骤1对算法进行初始化，输入图联盟博弈Γ={N,v,G}，即输入参与联盟博弈的Agent组成的集合N，对联盟生成存在约束的约束图G，和满足图G约束的联盟利益v，生成满足图G约束的所有联盟C，以联盟C的基|C|=m为分层条件，将所有可行联盟分为Lm层，对每层每个联盟的参数初始赋值，优值F[C]初始赋值为v(C)，优结构M[C]初始赋值为联盟C，初始分配B[C]初始赋值为 ({v{1},v{2},…,v{n}},i∈C)，以上过程如算法2的Step1所示。

步骤2通过自上向下的方式搜索联盟结构，即从第一层向下层逐层求出每层每个联盟C的优结构M[C]，优值F[C]，并采用按劳分配对联盟C进行初始利益分配，得到联盟C的初始分配B[C]，将分配结果(x1,x2,…,xn,xi∈C)存入B[C]。从L2层到Ln层依次搜索计算：比较给出的联盟利益F[C]和划分成两个划分块的利益F[C-C′]+F[C′]，这里C′⊆C,C′∈Z,CC′∈Z,|C′|≤ 0.5m。如果F[C-C′]+F[C′]＞F[C]，即划分成两个划分块的联盟利益和大于联盟C的初始利益，那么优值F[C]=F[C-C′]+F[C′]，优结构M[C]={CC′,C′}，如果F[C]＞F[C-C′]+F[C′]，即联盟C初始利益大于划分成两个划分块的联盟值时，那么优值F[C]=F[C]，优结构M[C]=C；如果F[C-C′]+F[C′]=F[C]，即联盟初始值等于划分成两个划分块的联盟值，那么优值F[C]=F[C]，优结构M1[C]=C,M2[C]={C-C′,C′}，即通过公式F[C]=max{F[C],F[C-C′]+F[C′]}，寻找联盟C的最优结构M[C]、F[C]。根据式（5）将联盟优值F[C]分配给优结构M[C]中的Agent，并将初始分配(x1,x2,…,xn,i∈C)存入B[C]。以上过程如算法2的Step2所示。

步骤3自顶向下构造具有最大社会福利的联盟结构Cs*及其初始分配B[Cs*]，搜索包含Agenti的所有B[Cs*]，选取B[C]中Agenti可获得的最大个人利益xi存入集合S[N]。首先对Cs*初始赋值，将Ln层的优结构M[C]作为初始值赋予Cs*，若M[C]的个数P=1，则Cs*=M[C]，若C∈Cs*且联盟M[C]≠C，则Cs*={(Cs*-C)⋃M[C]}。搜索Cs*中包含的联盟C，将联盟C的初始分配方案B[C]存入B[Cs*]，生成所有B[Cs*]，若M[C]的个数P大于1，则生成多个Cs*，重复上述P=1的步骤，生成多个Cs*和B[Cs*]，然后搜索每层B[Cs*]，将每个Agent在所有初始分配B[C]中可获得的最大利益存入S[N]。以上过程如算法2的Step3所示。

5.2 生成稳定联盟结构的算法

本节对SCP算法第二部分——生成联盟核算法进行详细的描述。算法的输入为算法2的返回值Cs*、B[Cs*]、S[N]，输出为图联盟结构的核。算法根据输入，分析Cs*、B[Cs*]属于4.1节的何种问题，并通过4.2节的解决方案生成核。

算法3生成联盟结构核算法

输入：Cs*、B[Cs*]、S[N]。

输出：联盟结构核。

//Step1利用次稳定结构概念优化的Cs*个数，得到唯一的操作对象core*。

//Step2运用稳定成本和谈判集的概念寻找联盟博弈的稳定结构及其分配。

步骤1判断输入的Cs*的个数P是否为1，若为1，将Cs*及其初始分配B[Cs*]赋予core*，即core*=(Cs*,(B[Cs*]))，若P≠1，则采用次稳定结构的概念得到次稳定结构Λ*，并将次稳定结构及其分配赋予core*，core*=(Λ*,(B[Λ*]))。以上过程如算法3的Step1所示。

步骤2选取core*中的所有联盟C，判断联盟收益v(C)与联盟C中Agent的最大利益加和的大小。若v(C)小，说明核为空，采用稳定成本的概念，计算稳定成本Δ，并将稳定成本分配给core*中的xi，使联盟C中所有Agent获得最大个人所得利益，core*中的B[Cs*]经过调整后满足核的定义；若v(C)大，那么判断联盟C中的Agent是否全部获得了最大利益，若是，core*满足核的定义，若不是采用谈判集的概念，调整初始分配B[Cs*]，直到所有处于联盟状态的Agent在Cs*中获得最大利益，core*满足核的定义。最后判断输出核的类型：若Δ≠0且P≠1，返回Csscore(ΓΔ)←core*；若只有Δ≠ 0，则返回Cs-core(ΓΔ)←core*；若只有P≠ 1，则返回Cs-score(Γ)←core*；若Δ=0且P=1，返回Cs-score(Γ)←core*。以上过程如算法3的Step2所示。

5.3 算法求解过程实例

例7存在图联盟博弈Γ={{1,2,3,4},v,G4}，|N|=5，约束图为图6所示的星型图G4，联盟利益为v（表1中第3列下划线标记）。下面根据算法步骤生成图联盟结构核。

Fig.6 Star graphG4图6 星状图G4

生成最大社会福利的联盟结构及其初始分配算法。表1用表格的形式表现此算法的求解过程。

步骤1输入图联盟博弈Γ={N,v,G4}，输入的联盟和联盟利益在表1中由下横线标出，根据联盟的基，|N|=5将联盟分为L5层。初始化算法：分别设置每层每个联盟C的优值F[C]、最优结构M[C]、联盟初始分配B[C]。

步骤2由L1向L5层分别求出每一层每一个联盟C的M[C]、F[C]、B[C]，并根据式（5）求得每一个可行联盟的初始分配B[C]。表1给出了SCP算法这两步具体的求解过程。

步骤3构造Cs*、B[Cs*]、S[N]，表1中L5层得到了两个实现最大福利的联盟结构Cs*，分别为 {1},{2,3,4,5}和 {2},{1,3,4,5}，最大社会福利Swm(Γ)=125，具有最大社会福利的联盟结构的个数P=2，初始分配B[Cs*]分别为(20,16.6,33.2,44.2,11)和(22,15,33,44,11)。搜索每层每个联盟C的初始分配B[C]，将每个Agent在所有初始分配B[C]中可获得的最大利益存入S[N]，S[N]=[22,16.6,33.2,44.2,11]。最后输出求得的Cs*、B[Cs*]、S[N]。

生成稳定联盟核算法。表2用表格的形式表现此算法的求解过程。

步骤1输入算法 2 求得的Cs*、B[Cs*]、S[N]，因为实现最大福利的联盟结构Cs*的个数P为2，采用次稳定核的概念，在两个联盟结构 {1},{2,3,4,5}、{2},{1,3,4,5}中，选取令多数Agent获得最大利益的 {1},{2,3,4,5} 作为Λ*，并将 {1},{2,3,4,5}，(20,16.6,33.2,44.2,11)赋予core*。

步骤2选取core*中联盟C(联盟C中包含的Agent的数量大于1)，发现core*中的联盟C均满足公式，因此不需要稳定成本来调节，Δ=0。对比core*中处于联盟状态的Agent所获得的分配(16.6，33.2，44.2，11)与S[N]中Agent最大利益期望[16.3,33.2,44.2,11]，可知core*中Agent均已获得了自身的最大利益，满足核的定义，因为P=2，Δ=0，所以输出Cs-score(Γ)=({1},{2,3,4,5},(20,16.3,33.2,44.2,11))。

Cs-score(Γ)包含两个联盟，其中{1}为单个用户，因此用户1只能获得初始利益20，联盟{2,3,4,5}包含4个用户，利益分配为(16.6，33.2，44.2，11)，并且联盟中的所有Agent可以在联盟中获得自身的最大利益，因此结果是稳定的。

Table 1 Generation process ofCs*and initial allocation under constraints of star graph表1 星状图约束下的最优联盟结构Cs*及其初始分配生成过程

Table 2 Generation process of coalition structure core表2 生成稳定联盟结构核的算法求解过程

6 算法的性质分析

下面对生成联盟博弈核的SCP算法在时间复杂度、正确性方面进行分析。算法的时间复杂度是衡量算法效率的基本要素；算法的正确性则主要刻画若进程能够按照所设计的算法来执行，其得到的运行结果一定是正确的。

6.1 算法时间复杂度分析

定理1（二项式定理）令n为一个正整数，且所有的x、y满足：

定理2SCP算法在最坏情况下的时间复杂度为O(3n)。

证明最坏情况下，图联盟博弈约束图Γ={N,v,G}为完全图，不限制任意联盟的生成，因此可行联盟的个数为2n-1，将可行的联盟根据联盟的基分为Ln层。Agent形成联盟时，依次取m个Agent组成小联盟C，从n个Agent中取m个的方法有种，将m个Agent分成两组的划分方法有2m-1-1种，需要搜索的次数用二项式表示为：

根据以上分析，SCP算法在求解联盟核时算法时间复杂度在最坏的情况下为O(3n)。

6.2 算法的正确性分析

定理3将联盟利益全部分给博弈的参与者，并且Agent在联盟中的个人所得利益满足理性条件，只有同时满足上述条件的联盟才是稳定的[16]。

证明假设联盟C中满足式子，或存在Agent在其他联盟D获得比联盟C更大的利益，那么Agent会选择离开联盟单独工作，或加入联盟D来最大化自身利益，这样联盟C是不稳定的，进而造成联盟结构的不稳定，假设错误，定理成立。

定理4存在图联盟博弈Γ={N,v,G}，其稳定的分配一定存在于实现最大社会福利的联盟结构中。

证明存在联盟博弈Γ={N,v,G}，假设有联盟结构核 (Λ,xi)，Λ∈Cs*，xi∈Λ，对于任意一个可行的联盟结构Λ′∈Cs(G)和任何一个x′i∈Λ′，从每个Agent的理性考虑，当xi≥x′i时，才是稳定的分配。因为Λ中的联盟是互不相交的而且完全覆盖N，得到式子Sw(Λ)=，所以Sw(Λ)＞Sw(Λ′)。综上所述，其稳定的分配一定存在于实现最大社会福利的联盟结构中。

定理5正确性：SCP算法求解出的核一定具有稳定性。

证明SCP算法解出每层最优的联盟结构，并根据按劳分配方案得到初始分配，通过自顶向下的方式构造实现最大社会福利的联盟结构，并调整分配方案，最终解得的核同时满足定理3、定理4，因此SCP算法得到的核一定是正确的。

7 实验

7.1 实验环境与评估标准

本文实验是在计算机上进行的，计算机的系统环境是Windows7 64 bit，配有4 GB DDR 3内存，主频为3.2 GHz的i5-3470英特尔处理器。程序编写语言是C语言，运行环境是MicrosoftVisual Studio 2008。实验数据是随机生成的联盟及其联盟收益。

本文将算法的运行时间作为效率的评估标准,从两方面分析算法的效率：一方面研究参与联盟博弈的Agent的个数N对运行时间的影响；另一方面研究不同结构的约束图对运行时间的影响。

7.2 |N|对SCP算法求解时间的影响

本节研究|N|对SCP算法求核时间的影响。通过建立图联盟博弈Γ={N,v,G}，|N|=n，分别设定约束图为零散图、链状图、星状图、混合型拓扑结构，并改变不同约束图中含有的Agent个数，即改变|N|的数量，记录生成联盟核所需要的时间，实验结果如表3，折线图如图7。折线图以参与博弈的人数n为横坐标，求解时间为纵坐标，每一条折线代表具有相同约束图结构、不同参与人数参与联盟博弈时，SCP算法的求解时间变化。

通过对图7、表3的观察分析容易发现，若约束图为零散图，SCP算法求解时间不受|N|数量的影响。因为在零散图约束下，任意|N|值可以生成满足图约束的联盟个数为0。若约束图是除零散图以外的其他类型的约束图，随着|N|的数量的增加，算法运行时间逐渐增加。因为参与联盟人数增加，形成可行联盟的个数会增大。

Fig.7 Influence of the number ofnon running time图7 n的个数对求解时间的影响

Table 3 Running time of SCP algorithm with differentn表3 不同Agent个数n对应SCP算法的求解时间

7.3 约束图G在不同结构下对SCP算法求解时间的影响

本节研究约束图G具有不同结构时对SPC算法求解时间的影响。建立图联盟博弈Γ={N,v,G},设定参与博弈的人数|N|为10至50，改变不同|N|下约束图的结构（零散图、链状图、星状图、混合型拓扑结构），记录生成核所需要的时间，实验结果如表3所示，折线图如图8。折线图以图形结构的种类为横坐标，求解时间为纵坐标，每一条折线代表相同个数Agent在不同结构的约束图下，SCP算法的求解时间的变化。

通过对图8、表3的分析可以发现，当约束图约束结构不同时，算法的求解速度是不同的。当约束图为零散图时，即所有的联盟都不可以生成，只能形成一种联盟结构，且分配为每一个Agent的初始利益。因此求解时间非常快，求解时间不受N的影响，符合约束的联盟数量最大，求解时间最长。可以看出，SCP算法的运行时间随着零散图、链状图、混合型拓扑结构的顺序逐渐增大。因为这些约束图按顺序依次允许更多的联盟生成，所以SCP算法求核时间主要和满足图约束的联盟个数有关。

Fig.8 Influence of graph structure on running time图8 约束图结构对算法求解时间的影响

7.4 对比算法

本节对比SCP算法和CCDP算法在求解最优联盟时的优点。

CCDP算法是由徐广斌等人编写的求解带有联盟个数约束的最优结构算法，该算法基于DP思想引入了联盟划分块的概念，通过比较初始联盟值和分成两个划分块的联盟值之和，得到2n-1个联盟的划分数，求得最优的联盟结构。联盟个数的约束就是通过判断联盟划分数得到符合条件的联盟结构[12]。

CCDP算法需要将2n-1个联盟分解，算法假定所有的联盟都是可行的。而本文提出的SCP算法在开始就对联盟的生成进行了约束，减少了可行联盟个数，减少了算法在生成最优联盟时所需处理的数据，降低了算法的求解时间。

表4是CCDP算法生成最优联盟结构的时间，将表4与表3中SCP求解时间进行对比可以发现，SCP算法求解时间远远小于CCDP算法，并且参与联盟的Agent个数越多效果越明显。因为Agent个数越多，受约束图约束的联盟个数越多，两个算法所处理的可行联盟个数差异越大。

Table 4 Running time of CCDP with differentn表4 不同Agent个数n对应CCDP算法的求解时间

8 结论和未来工作

本文给出了图形联盟博弈的定义，分析了多种图形拓扑结构在图联盟博弈中的应用，刻画了联盟收益分配的稳定性的概念，分析了求解稳定结构和分配的复杂性，给出了相应的解决方案。基于CCDP算法设计了一种有效的求解联盟结构核的算法，该算法首先改进CCDP算法的约束条件，利用图形拓扑结构约束联盟的生成，利用CCDP算法分层生成最优子结构，避免了重复计算。然后将按劳分配作为初始分配方案，公平地将联盟收益分配给联盟成员，运用稳定成本、谈判集的概念，调整初始分配，得到满足核定义的联盟结构和稳定分配。最后通过实验，得出SCP算法在不同N和约束图结构下的运行时间，并总结出算法的求解时间与生成可行联盟的个数正相关，并且可生成的联盟个数受|N|和约束图结构控制。

未来工作包括:

（1）加入夏普利值分配方案，当联盟满足超加性时，采用夏普利值进行分配，得到满足核要求的分配。

（2）在分配方案上将单个Agent的贡献细分化，将脑力劳动、体力劳动、成本和边际贡献[22]加入到分配方案中，使分配方案更贴近现实博弈。

（3）细化约束条件，例如引入参与联盟的Agent的偏好，进一步约束联盟的生成，删去不符合逻辑的联盟，降低算法的时间复杂度。

[1]IwasakiA,Ueda S,Hashimoto N,et al.Finding core for coalition structure utilizing dual solution[J].Artificial Intelligence,2015,222(5):49-66.

[2]Chalkiadakis G,Greco G,Markakis E.Characteristic function games with restricted agent interactions:core-stability and coalition structures[J].Artificial Intelligence,2016,232(1):76-113.

[3]Tan Chunqiao.Shapley value fornpersons games with interval fuzzy coalition based on Choquet extension[J].Journal of Systems Engineering,2010,25(4):451-458.

[4]Rahwan T,Jennings N R.An improved dynamic programming algorithm for coalition structure generation[C]//Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems,Estoril,May 12-16,2008.New York:ACM,2008:1417-1420.

[5]Billera L J.Some theorems on the core of ann-person game without side-payments[J].SIAM Journal on Applied Mathematics,1970,18(3):567-579.

[6]Schmeidler D.The nucleolus of a characteristic function game[J].SIAM Journal on Applied Mathematics,1969,17(6):1163-1170.

[7]Myerson R B.Graphs and cooperation in games[J].Mathematics of Operations Research,1977,2(3):225-229.

[8]Skibski O,Michalak T P,Rahwan T,et al.Algorithms for the Shapley and Myerson values in graph-restricted games[C]//Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems,Paris,May 5-9,2014.New York:ACM,2014:197-204.

[9]Michalak T P,Rahwan T,Szczepanski P L,et al.Computational analysis of connectivity games with applications to the investigation of terrorist networks[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence,Beijing,Aug 3-9,2013.Menlo Park:AAAI,2014:293-301.

[10]de Weerdt M,Zhang Yingqian,Klos T.Multiagent task allocation in social networks[J].Autonomous Agents and Multi-Agent Systems,2012,25(1):46-86.

[11]Yeh D Y.A dynamic programming approach to the complete set partitioning problem[J].BIT Numerical Mathematic,1986,26(4):467-474.

[12]Xu Guangbin,Liu Jinglei.The optimal coalition structure generation with the constrained number of coalition[J].Journal of Nanjing University:Natural Sciences,2015,51(4):601-613.

[13]Yang Xiangfeng,Gao Jinwu.Uncertain core for coalitional game with uncertain payoffs[J].Journal of Uncertain Systems,2014,8(1):13-21.

[14]Guan Baichun.New interpretation of distribution according to one's performance—an explanation of innovation pursuit[J].Theory Journal,2005(3):35-39.

[15]Sandholm T,Larson K,Andersson M,et al.Coalition structure generation with worst case guarantees[J].Artificial Intelligence,1999,111(1/2):209-238.

[16]Breton M L,Owen G,Weber S.Strongly balanced cooperative games[J].International Journal of Game Theory,1992,20(4):419-427.

[17]Scarf H E.The core of anNperson game[J].Econometrica,1965,35(1):50-69.

[18]Voice T,Polukarov M,Jennings N R.Coalition structure generation over graphs[J].Journal of Artificial Intelligence Research,2012,45(1):165-195.

[19]Bachrach Y,Meir R,Jung K,et al.Coalitional structure generation in skill games[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence,Atlanta,Jul 11-15,2010.Menlo Park:AAAI,2011:703-708.

[20]Aumann R J,Maschler M.The bargaining set for cooperative games[J].Advances in Game Theory,1964,52(1):443-476.

[21]Bachrach Y,Elkind E,Meir R,et al.The cost of stability in coalitional games[C]//LNCS 5814:Proceedings of the 2nd International Symposium on Algorithmic Game Theory,Paphos,Oct 18-20,2009.Berlin,Heidelberg:Springer,2009:122-134.

[22]Aurangzeb M,Lewis F L.Internal structure of coalitions in competitive and altruistic graphical coalitional games[J].Automatica,2014,50(2):335-348.

附中文参考文献:

[3]谭春桥.基于Choquet延拓具有区间模糊联盟n人对策的Shapley值[J].系统工程学报,2010,25(4):451-458.

[12]徐广斌,刘惊雷.带有联盟个数约束的最优联盟结构生成[J].南京大学学报:自然科学,2015,51(4):601-613.

[14]关柏春.按劳分配新论——一种追求变革的解说[J].理论学刊,2005(3):35-39.