约束条件下联盟生成研究进展（烟台大学：任子仪、童向荣）

第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201804054 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180619.1422.002.html 约束条件下联盟生成研究进展 任子仪，童向荣 (姻台大学计算机与控制工程学院，山东烟台264005)】 摘要：联盟生成是在多Agent系统的研究中最为重要的挑战之一。如何对Agent进行划分使所得社会福利最 大化是当前面临的主要问题。假设每个Agt都具有理性和自利性的特性，为了追求自身的利益最大化而选 择和其他的Agεt进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即 使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下 的联盟生成的研究进行综述，主要包括4部分：最坏情况有限界联盟生成、动态规划联盟生成求精确最优解 联盟生成求近似最优解和约束条件下联盟生成求最优解。 关键词：联盟结构；社会福利；联盟生成；约束条件；特征函数；联盟结构图：联盟博弈；动态规划 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)03-0413-10 中文引用格式：任子仪，童向荣.约束条件下联盟生成研究进展机.智能系统学报，2019,14(3)：413-422 英文引用格式：REN Ziyi,TONG Xiangrong.Research progress of constrained coalition formation.CAAI transactions on intelli- gent systems,2019,14(3:413-422. Research progress of constrained coalition formation REN Ziyi,TONG Xiangrong (School of Computer and Control Engineering,Yantai University,Yantai 264005,China) Abstract:Coalition formation is one of the most important challenges in the research of multiagent systems.Currently, our main problem is how to divide Agent to maximize the social welfare.We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests.An Agent integrates with another Agent, which also maximizes the interest of the whole system.At present,the coalition formation problem presents notable computational challenges.If constraints are added during the coalition process,new algorithms are needed to solve the problem more rapidly and effectively.This paper mainly summarizes the study of coalition structure generation under constraint conditions.This paper comprises four parts:the coalition structure generation with the worst case guaranteed, the use of the dynamic programming to find the exact optimal solution,the near-optimal solution after formation of the coalition structure,and the optimal solution to the constrained coalition formation. Keywords:coalition structure;social welfare;coalition formation;constraint;characteristic function;coalition structure graph;coalition game;dynamic programming 联盟生成是多Agent系统(multi--agent system, 中的其他Agent合作，共同合作活动的目的是达 MAS)研究基本问题之一a,主要将Agent进行合 到最佳的标准。当Agent通过组建联盟共同工作 作或协商，使其效用增加。Agent联盟基本上被 时，联盟结构生成就会发生。目标就是求一种 认为在MAS的框架内的一组Agent,.愿意与这组 最优的联盟结构，使得所求的社会福利最大，并 返回其值4。 收稿日期：2018-04-26.网络出版日期：2018-06-20 Agent在联盟生成时达到最优方案不一定是 基金项目：国家自然科学基金项目(61572418)：山东省科技发 展计划项目(2016GGX109004) 全局最优解，但是应该是Nash最优解6-或者次优 通信作者：童向荣.E-mail:twr@ytu.edu.cn 解，因此联盟生成主要包括以下活动：

DOI: 10.11992/tis.201804054 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180619.1422.002.html 约束条件下联盟生成研究进展 任子仪，童向荣 （烟台大学 计算机与控制工程学院，山东 烟台 264005） 摘 要：联盟生成是在多 Agent 系统的研究中最为重要的挑战之一。如何对 Agent 进行划分使所得社会福利最 大化是当前面临的主要问题。假设每个 Agent 都具有理性和自利性的特性，为了追求自身的利益最大化而选 择和其他的 Agent 进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即 使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下 的联盟生成的研究进行综述，主要包括 4 部分：最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、 联盟生成求近似最优解和约束条件下联盟生成求最优解。 关键词：联盟结构；社会福利；联盟生成；约束条件；特征函数；联盟结构图；联盟博弈；动态规划 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)03−0413−10 中文引用格式：任子仪, 童向荣. 约束条件下联盟生成研究进展[J]. 智能系统学报, 2019, 14(3): 413–422. 英文引用格式：REN Ziyi, TONG Xiangrong. Research progress of constrained coalition formation[J]. CAAI transactions on intelli￾gent systems, 2019, 14(3): 413–422. Research progress of constrained coalition formation REN Ziyi，TONG Xiangrong (School of Computer and Control Engineering, Yantai University, Yantai 264005, China) Abstract: Coalition formation is one of the most important challenges in the research of multiagent systems. Currently, our main problem is how to divide Agent to maximize the social welfare. We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests. An Agent integrates with another Agent, which also maximizes the interest of the whole system. At present, the coalition formation problem presents notable computational challenges. If constraints are added during the coalition process, new algorithms are needed to solve the problem more rapidly and effectively. This paper mainly summarizes the study of coalition structure generation under constraint conditions. This paper comprises four parts: the coalition structure generation with the worst case guaranteed, the use of the dynamic programming to find the exact optimal solution, the near-optimal solution after formation of the coalition structure, and the optimal solution to the constrained coalition formation. Keywords: coalition structure; social welfare; coalition formation; constraint; characteristic function; coalition structure graph; coalition game; dynamic programming 联盟生成是多 Agent 系统 (multi-agent system， MAS) 研究基本问题之一[1-2] ，主要将 Agent 进行合 作或协商，使其效用增加。Agent 联盟基本上被 认为在 MAS 的框架内的一组 Agent，愿意与这组 中的其他 Agent 合作，共同合作活动的目的是达 到最佳的标准。当 Agent 通过组建联盟共同工作 时，联盟结构生成就会发生[3]。目标就是求一种 最优的联盟结构，使得所求的社会福利最大，并 返回其值[4-5]。 Agent 在联盟生成时达到最优方案不一定是 全局最优解，但是应该是 Nash 最优解[6-7]或者次优 解，因此联盟生成主要包括以下活动： 收稿日期：2018−04−26. 网络出版日期：2018−06−20. 基金项目：国家自然科学基金项目 (61572418)；山东省科技发 展计划项目 (2016GGX109004). 通信作者：童向荣. E-mail：txr@ytu.edu.cn. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019

·414· 智能系统学报 第14卷 l)联盟结构生成：Agent之间进行协商生成 共有7种情况，分别是{a}、{a2、{a3}、{a,a2}、 联盟，但不考虑各个联盟之间的协商。 {a1,a、{a2,a3}、{a1,2,a3l,联盟结构一共存在5种 2)解决每个联盟优化问题：将Agent的任务 情况，分别是{a,{a2,{a从、{a,{a2,a从{a2l,{a1,a从 和资源集中在一起，共同解决问题。Agent之间 {a3h,{a1,2}和{a1,a2,a3o 进行协商使联盟的社会福利尽可能最大化，即寻 定义2社会福利。社会福利即为联盟结构 找最优的方法使得联盟本身的效用最大化。 CS中所有的联盟C,ie1,2,,k的收益之和，将 3)划分值：在进行收益分配的时候，常用的 联盟的值记为v(C),并且要求(C)≥0，联盟结构 方法有两种，即公平（每个Agent所得到的收益是 的社会福利记为V(CS),将具有最大的社会福利 Agent在博弈中的贡献的体现)和稳定（存在没 联盟结构称为最优联盟结构，记为CS,其最优社 有和其他Agent协商而单独形成自己的自私利益 会福利记为V(CS),则 联盟)。 同样，存在很多方法寻找和创建一个最优的 'CS)=∑C 联盟一协商或搜索以及用于找出解决问题的几 定义3次加性。对于任意的不相交的联盟 种潜在的方法，例如：遗传算法、博弈论、粒子群 S,T∈N,都存在v(SUT)≤v(S)+v(T)。换言之， 算法等。但是，随着研究的不断深入，在现实世 a,{a2小，，{an}为最大社会福利的联盟结构。 界的应用中有一些联盟结构是不允许生成的⑧。 定义4特征函数。给定一个n个Agent的 目前，联盟研究的热点问题主要是约束条件下 博弈，C是一个联盟，v(C)是指C和N-C两个 联盟生成。在现有研究中，很多文献已经考虑 Agent博弈中C的最大效用，(C)称为联盟C特 将联盟进行广泛应用，例如：通过形成联盟，自主 征函数(characteristic function),规定v(O)=0。 传感器可以改善某些区域的监控情况；认识无 1.2博弈类型 线电网络可以增加它们的吞吐量；购买者可以 在常用的联盟博弈模型中，通常用货币来表 通过批量购买而获得较低的价格，自主连接车 示联盟的价值（或奖励）。在进行博弈的过程 辆进行护航工作2)；形成联盟促进社交网络关 中，假设存在一个在Agent之间可以自由流动的 系B1等。 交换媒介（如货币），每个Agent可以根据自己的 在Agent联盟研究发展中，Sandholm等u最 绩效得到相应的货币，这种博弈被称为“单边支 先提出最坏情况有限界联盟结构生成；Ych等6 付”博弈或可转移效用(transferable utility,TU)博 首次使用动态规划算法联盟生成并求得精确最优 弈。相反，联盟的绩效是用向量表示的，直接指 解；随着研究的不断深入，Agent数量的增加，先 定每个成员的绩效，Agent只能服从这种分配方 前的算法越来越不能满足当前的需求，Dang等叨 案，不能对分配方案进行修改，这种博弈被称为 首次提出建立次优联盟结构并求得次优解； 不可转移效用(non-transferable utility,NTU)博 Greco等u经过进一步研究，提出了一种新的联盟 弈。在多Agent系统中，可转移效用博弈受到了 结构生成的方式—约束联盟结构，即在生成联 很大的关注。 盟的过程对联盟添加约束。 1)特征函数博弈 1基本定义 特征函数博弈(characteristic function games,. CFGs)是联盟的价值完全取决于它所包含的 1.1主要定义 Agent的值。将特征函数博弈定义为(N,v),其中 假设所有的Agent都是理性的，并使用合作 N表示Agent数据集，v是一个函数，称为特征函 博弈建模进行Agent之间的合作和协商。在博弈 数，对于每个联盟C映射到函数中的值v(C)记为 中，令N是一个Agent集，其中n=W表示N中 v:2w→R。 Agent的个数，则N=(a1,a2,,an,联盟即N中非 2)分区博弈 空的子集。 在分区博弈(partition function games,.PFGs)中 定义1联盟结构。对于任意联盟C,在C上 联盟的价值不仅仅取决于所包含的Agent的值， 形成的联盟结构CS={C,C2,,Ck,其中UCS=C, 也会受非成员分区的影响。将分区博弈定义为 并且对于任意i,j∈L,2,…,,i≠j都需要满足 (N,w),其中N表示Agent数据集，w是一个分区 C:∩C,=0。 函数，每个嵌入式联盟(C,CS)映射到函数中的值 例1一个集合N={a,a2,a,N上的联盟一 是w(C,CS)或w(C,CS)

1) 联盟结构生成：Agent 之间进行协商生成 联盟，但不考虑各个联盟之间的协商。 2) 解决每个联盟优化问题：将 Agent 的任务 和资源集中在一起，共同解决问题。Agent 之间 进行协商使联盟的社会福利尽可能最大化，即寻 找最优的方法使得联盟本身的效用最大化。 3) 划分值：在进行收益分配的时候，常用的 方法有两种，即公平 (每个 Agent 所得到的收益是 Agent 在博弈中的贡献的体现) 和稳定 (存在没 有和其他 Agent 协商而单独形成自己的自私利益 联盟)。 同样，存在很多方法寻找和创建一个最优的 联盟——协商或搜索以及用于找出解决问题的几 种潜在的方法，例如：遗传算法、博弈论、粒子群 算法等。但是，随着研究的不断深入，在现实世 界的应用中有一些联盟结构是不允许生成的[8]。 目前，联盟研究的热点问题主要是约束条件下 联盟生成。在现有研究中，很多文献已经考虑 将联盟进行广泛应用，例如：通过形成联盟，自主 传感器可以改善某些区域的监控情况[9] ；认识无 线电网络可以增加它们的吞吐量[10] ；购买者可以 通过批量购买而获得较低的价格[11] ；自主连接车 辆进行护航工作[ 1 2 ] ；形成联盟促进社交网络关 系 [13-14]等。 在 Agent 联盟研究发展中，Sandholm 等 [15]最 先提出最坏情况有限界联盟结构生成；Yeh 等 [16] 首次使用动态规划算法联盟生成并求得精确最优 解；随着研究的不断深入，Agent 数量的增加，先 前的算法越来越不能满足当前的需求，Dang 等 [17] 首次提出建立次优联盟结构并求得次优解； Greco 等 [18]经过进一步研究，提出了一种新的联盟 结构生成的方式——约束联盟结构，即在生成联 盟的过程对联盟添加约束。 1 基本定义 1.1 主要定义 N n = |N| N N = (a1,a2,· · ·,an) N 假设所有的 Agent 都是理性的，并使用合作 博弈建模进行 Agent 之间的合作和协商。在博弈 中，令 是一个 Agent 集，其中 表示 中 Agent 的个数，则 ，联盟即 中非 空的子集。 C C CS = {C1,C2,· · ·,Ck} ∪CS = C i, j ∈ {1,2,· · ·, k},i , j Ci ∩Cj = Ø 定义 1 联盟结构。对于任意联盟 ，在 上 形成的联盟结构 ，其中 ， 并且对于任意 都需要满足 。 例 1 一个集合 N = {a1,a2,a3}，N 上的联盟一 {a1} {a2} {a3} {a1,a2} {a1,a3} {a2,a3} {a1,a2,a3} {{a1},{a2},{a3}} {{a1},{a2,a3}} {{a2},{a1,a3}} {{a3},{a1,a2}} {a1,a2,a3} 共 有 7 种情况，分别是 、 、 、 、 、 、 ，联盟结构一共存在 5 种 情况，分别是 、 、 、 和 。 Ci ,i ∈ {1,2,· · ·, k} v(Ci) v(Ci) ⩾ 0 V(CS) CS∗ V(CS∗ ) 定义 2 社会福利。社会福利即为联盟结构 CS 中所有的联盟 的收益之和，将 联盟的值记为 ，并且要求 ，联盟结构 的社会福利记为 ，将具有最大的社会福利 联盟结构称为最优联盟结构，记为 ，其最优社 会福利记为 ，则 V (CS) = ∑k i=1 ν(Ci) S,T ∈ N v(S ∪T) ⩽ v(S )+v(T) {{a1},{a2},· · ·,{an}} 定义 3 次加性。对于任意的不相交的联盟 ，都存在 。换言之， 为最大社会福利的联盟结构。 n C v(C) C N −C C v(C) C v(Ø) = 0 定义 4 特征函数。给定一个 个 Agent 的 博弈， 是一个联盟， 是指 和 两个 Agent 博弈中 的最大效用， 称为联盟 特 征函数 (characteristic function)，规定 。 1.2 博弈类型 在常用的联盟博弈模型中，通常用货币来表 示联盟的价值 (或奖励[19] )。在进行博弈的过程 中，假设存在一个在 Agent 之间可以自由流动的 交换媒介 (如货币)，每个 Agent 可以根据自己的 绩效得到相应的货币，这种博弈被称为“单边支 付”博弈或可转移效用 (transferable utility，TU) 博 弈。相反，联盟的绩效是用向量表示的，直接指 定每个成员的绩效，Agent 只能服从这种分配方 案，不能对分配方案进行修改，这种博弈被称为 不可转移效用 (non-transferable utility，NTU) 博 弈。在多 Agent 系统中，可转移效用博弈受到了 很大的关注。 1) 特征函数博弈 (N, v) N v v(C) v : 2N → R 特征函数博弈 (characteristic function games， CFGs) 是联盟的价值完全取决于它所包含的 Agent 的值。将特征函数博弈定义为 ，其中 表示 Agent 数据集， 是一个函数，称为特征函 数，对于每个联盟 C 映射到函数中的值 记为 。 2) 分区博弈 (N,w) N w (C,CS) w((C,CS)) w(C,CS) 在分区博弈 (partition function games，PFGs) 中 联盟的价值不仅仅取决于所包含的 Agent 的值， 也会受非成员分区的影响。将分区博弈定义为 ，其中 表示 Agent 数据集， 是一个分区 函数，每个嵌入式联盟 映射到函数中的值 是 或 。 ·414· 智 能 系 统 学 报 第 14 卷

第3期 任子仪，等：约束条件下联盟生成研究进展 ·415· CFGs是PFGs的子集，联盟C在CFGs中有 1)联盟结构图 一个精确值，但在PFGs中却存在很多值，这是因 Sandholm等提出的联盟结构图中，每个节点 为使用PFGs有不同的方法对N/C中的Agent进 代表一个联盟结构，并且将节点进行了划分，表示为 行分区。因此，在进行研究的过程中，使用 ,巧，…，，其中表示由i个联盟组成的所 C℉Gs更容易得到解决方案，提高算法的效率。 有的联盟结构的节点；边缘连接两个联盟结构， 1.3空间表示 当且仅当它们属于不同的划分，如和S:其中 在联盟结构生成问题中，通过联盟结构搜索 口中的联盟结构是由☑S,中的联盟分裂成两个联盟 得到最优联盟结构。 形成的。图1所示为具有4个Agent集联盟结构图。 {a},{a,{a,{a} a,aaa④a.a,atalalaata,ta.aaa.a,aa☑.ai.aa④ alaaa aalaa ☑a44④a4a4④aa44④a4,a4④@}a44④9 {a1,4,43a} 图14个Agent联盟结构 Fig.1 The coalition structure graph with 4 Agents 2)整数分区图 假设I∈P,定义巧∈是所有联盟结构组 在联盟结构图中，能直接看出具有ⅰ个联盟 成的子空间，其中联盟的大小受！部分的影响。例 所组成的联盟结构的情况。而Dean等2o提出的 如：份表示是由2个只有1个Agent联盟 整数分区图中，则是基于联盟结构中所包含的联 和1个有2个Agent组成的联盟形成的联盟结 盟的数量，将联盟结构中的空间划分成不相交的 构。对于这种表示一般用整数分区图来表示。整数 子空间，每个子空间是由n个整数分割表示的。 分区图也是一个无向图，其中每个节点代表一个 整数n的分区值可以通过递归的方法计算2四，用 子空间。两个节点I,∈P"是通过边连接的，当 Pm表示整数分区。例如：P=4,{1,3,{2,2,{1,1,2, 且仅当i,je1时，P=(八伍，)i+(三表示多重集 (1,1,1,1}。 的结合操作)。图2给出了有4个Agent整数分区图。 {1,1,1,1} u={{a1h,{a2,{a,{a}} {a},{az},{as,a},{az},{a},{a,a4} {1,12} {a1},{a3},aa}},{a2},a4},{a1,a3 {{a,{a,a2,a3}},{a3,{a4},{a1,a2}} , {a1,a2},{a1,a}》 a103a103 =2{2,2} {1,3} 3 {a1a4,{a1a2 4 Tr4={{a1,a2,a3,a4}} 图24个Agent整数分区图 Fig.2 The integer-partition graph representation of 4 Agents

N/C CFGs 是 PFGs 的子集，联盟 C 在 CFGs 中有 一个精确值，但在 PFGs 中却存在很多值，这是因 为使用 PFGs 有不同的方法对 中的 Agent 进 行分区。因此，在进行研究的过程中，使 用 CFGs 更容易得到解决方案，提高算法的效率。 1.3 空间表示 在联盟结构生成问题中，通过联盟结构搜索 得到最优联盟结构。 1) 联盟结构图 Π C 1 ,ΠC 2 ,· · ·,ΠC n Π C i Π C i Π C i−1 Π C i Π C i−1 Sandholm 等 [15]提出的联盟结构图中，每个节点 代表一个联盟结构，并且将节点进行了划分，表示为 ，其中 表示由 i 个联盟组成的所 有的联盟结构的节点；边缘连接两个联盟结构， 当且仅当它们属于不同的划分，如 和 ；其中 中的联盟结构是由 中的联盟分裂成两个联盟 形成的。图 1 所示为具有 4 个 Agent集联盟结构图。 2) 整数分区图 P n P 4 = {{4},{1,3},{2,2},{1,1,2}, {1,1,1,1}} 在联盟结构图中，能直接看出具有 i 个联盟 所组成的联盟结构的情况。而 Dean 等 [20]提出的 整数分区图中，则是基于联盟结构中所包含的联 盟的数量，将联盟结构中的空间划分成不相交的 子空间，每个子空间是由 n 个整数分割表示的。 整数 n 的分区值可以通过递归的方法计算[21] ，用 表示整数分区。例如： 。 I ∈ P Π C I ∈ Π C I Π {a1 ,a2 ,a3 ,a4 } {1,1,2} I,I ′ ∈ P n i, j ∈ I I ′ = (I\{i, j})Ξ{i+ j} Ξ 假设 ，定义 是所有联盟结构组 成的子空间，其中联盟的大小受 部分的影响。例 如： 表示是由 2 个只有 1 个 Agent 联盟 和 1 个有 2 个 Agent 组成的联盟形成的联盟结 构。对于这种表示一般用整数分区图来表示。整数 分区图也是一个无向图，其中每个节点代表一个 子空间。两个节点 是通过边连接的，当 且仅当 时， ( 表示多重集 的结合操作)。图 2 给出了有 4 个 Agent 整数分区图。 {a1},{a2 ,a3 ,a4} {a1 ,a2},{a3 ,a4} {a2},{a1 ,a3 ,a4} {a1 ,a3},{a2 ,a4} {a3},{a1 ,a2 ,a4} {a1 ,a4},{a2 ,a3} {a4},{a1 ,a2 ,a3} {a1},{a2},{a3 ,a4} {a1 ,a2},{a3},{a4} {a1},{a3},{a2 ,a4} {a2},{a4},{a1 ,a3} {a1},{a4},{a2 ,a3} {a2},{a3},{a1 ,a4} {a1},{a2},{a3},{a4} {a1 ,a2 ,a3 ,a4} Πc 4 Πc 3 Πc 2 Πc 1 图 1 4 个 Agent 联盟结构 Fig. 1 The coalition structure graph with 4 Agents {1,1,1,1} Πc {1,1,1,1}={{{a1},{a2},{a3},{a4}}} Πc {4}={{{a1 ,a2 ,a3 ,a4}}} {1,1,2} {2,2} {1,3} {4} { } {{a1},{a2},{a3 ,a4}},{{a2},{a3},{a1 ,a4}} {{a1},{a3},{a2 ,a4}},{{a2},{a4},{a1 ,a3}} {{a1},{a4},{a2 ,a3}},{{a3},{a4},{a1 ,a2}} =Πc {1,1,2} { } {{a1 ,a2},{a1 ,a4}}, {{a1 ,a3},{a1 ,a3}}, {{a1 ,a4},{a1 ,a2}} =Π{2,2} { } {{a1},{a2,a3 ,a4}} {{a2},{a1 ,a3 ,a4}} {{a3},{a1 ,a2 ,a4}} {{a4},{a1 ,a2 ,a3}} Πc {1,3}= 图 2 4 个 Agent 整数分区图 Fig. 2 The integer-partition graph representation of 4 Agents 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·415·

·416· 智能系统学报 第14卷 2联盟生成的复杂度 命题1表明，在联盟结构图上找到最优的联 盟结构是不可行的。所以，在进行联盟结构图的 2.1输入值的大小 搜索的时候设定一个限界。 对于具有n个Agent的数据集，会产生2n-1 对联盟结构的子集N进行搜索，目的在于寻 个非空的子集，生成2”-1个联盟，在进行运算时 找搜索中的最优联盟结构，即局部最优联盟结 需要输人2”-1个值。联盟结构生成算法的输入 构，记 值和Agent的个数之间呈指数关系。 理论上，在进行输入操作时即可排除一些不 CS=arg V(CS) 合理的联盟，或者在进行联盟结构生成的时候就 同时，为了保证设定的联盟结构在最佳范围 可以忽略一部分的输入。但是在接下来进行的操 内，即存在一个有限的但是尽可能小的值k,k被 作过程中无法保证存在单一的联盟与其他的联盟 称为搜索的解的界限，也是衡量局部最优解 进行合作之后的社会福利不是最佳社会福利，这 V(CSw)的标准。能够建立起界限的最小的k记为 V(CS) 是因为：被排除在外的联盟中可能存在比其他的 k=min),K≥vcS 联盟社会福利更大的联盟。 通常，如果没有对联盟结构进行完全搜索，设 2.2联盟结构的数量 定一个正确的界限是很难的。这是因为：在剪枝 随着联盟结构不断发展，Agent数量的增多， 的过程中虽然可以减少一些联盟结构的搜索，但 新问题也随之产生。联盟结构的个数表示为 是很难保证没有剪掉的比剪掉的具有更优性。在 立2 进行社会福利的定义的时候，令任意一个联盟C: 的值v(C)≥0，并且一个联盟结构的社会福利 其中：n代表数据集中的Agent个数；Zn,)表示具 V(CS)=∑v(C),这两点就保证了上述假设是不存 有i个联盟组成的联盟结构的个数；Zm,)满足第 2类Striling数的特征，即 在的，即在没有对联盟结构进行搜索的前提下设 Z(n,i)=iZ(n-1.)+Z(n-1,i-1) 置一个界限来缩小搜索联盟结构的数量。 式中：Zm,)=Zm,1)=1;Zn-1,)表示在现有存在 3.1建立界限 的联盟中增加一个新的Agent形成的联盟结构的 本节主要讨论如何尽可能地减少对图的搜索 个数；Zn-1,i-1)表示将一个新的Agent加入到 的前提下，建立一个界限k。 已有的联盟中，因为现在的联盟结构中只有 定理1对于界限k,可以只搜索联盟结构图 i-1个联盟被计算。有以下基本结果m2: 的最低的两级（图1中第7、5层）。在这个搜 命题1对于具有n个Agent的集合，具有 索中，界限=n,需要搜索的联盟结构节点的数量 2-1个联盟，O(n)和w2)个联盟结构（即联盟结 是2-1，这也是能够建立起界限的最小的搜索，即 构的个数的阶介于？n之间)。 nm=2-l。并且，没有其他的算法对于联盟结构 命题2寻找最优联盟结构是NP难问题。 的搜索的数量会比2-1少。 随着Agent数量的增加，联盟结构的数量也 最底层具有1个联盟结构，第二最底层中具 随之增加。经过实验的证明，当数据集中Agent 有2"-2个联盟(N中的所有子集，除掉全集和空 个数超过15时，使用穷举法列举出所有联盟结构 集)。在这一层中，每个联盟结构都有2个联盟， 是不可行的。 所以一共有2”-2)个联盟结构。只搜索最底下 3最坏情况有限界联盟结构生成 两层，一共搜索1+2-2)=2个联盟结果。 Dean和Boddy在时间依赖规划((time depend- 3.2算法描述 ent planning)的基础上提出了Anytime算法，其本 算法1最坏情况有保证联盟结构生成算法 质是一种反复求解使得结果更加精确的算法。在 1)搜索联盟结构图的最底二层； 算法的运行过程中，能够很快得到一个不精确的 2)从联盟结构图的顶层（第n层）开始，作宽 解，然后进行若干次的重复过程，经过重复后逐 度优先搜索，一直搜索到时间不允许为止或搜索 步提高解的质量，Anytime算法一个最显著的优 完整个联盟结构图； 点就是能够很好地权衡计算时间和解的质量。 3)返回迄今为止所得到的最优的联盟结构。 Sandholm等Is使用Anytime算法开创性地提出了 先前使用特征函数的方式2s2进行联盟结构 种最坏情况有限界联盟结构生成。 生成，算法1是一种任意时间算法，可以在任何时

2 联盟生成的复杂度 2.1 输入值的大小 2 n −1 2 n −1 2 n −1 对于具有 n 个 Agent 的数据集，会产生 个非空的子集，生成 个联盟，在进行运算时 需要输入 个值。联盟结构生成算法的输入 值和 Agent 的个数之间呈指数关系。 理论上，在进行输入操作时即可排除一些不 合理的联盟，或者在进行联盟结构生成的时候就 可以忽略一部分的输入。但是在接下来进行的操 作过程中无法保证存在单一的联盟与其他的联盟 进行合作之后的社会福利不是最佳社会福利，这 是因为：被排除在外的联盟中可能存在比其他的 联盟社会福利更大的联盟。 2.2 联盟结构的数量 随着联盟结构不断发展，Agent 数量的增多， 新问题也随之产生。联盟结构的个数表示为 ∑N i=1 Z(n,i) Z(n,i) Z(n,i) 其中：n 代表数据集中的 Agent 个数； 表示具 有 i 个联盟组成的联盟结构的个数； 满足第 2 类 Striling 数的特征，即 Z(n,i) = iZ(n−1,i)+Z(n−1,i−1) Z(n,i) = Z(n,1) = 1 iZ(n−1,i) Z(n−1,i−1) 式中： ； 表示在现有存在 的联盟中增加一个新的 Agent 形成的联盟结构的 个数； 表示将一个新的 Agent 加入到 已有的联盟中，因为现在的联盟结构中只 有 i－1 个联盟被计算。有以下基本结果[22-24] ： 2 n−1 O(n n ) ω(n n/2 ) n 2 命题 1 对于具有 n 个 Agent 的集合，具有 个联盟， 和 个联盟结构 (即联盟结 构的个数的阶介于 ~n 之间)。 命题 2 寻找最优联盟结构是 NP 难问题。 随着 Agent 数量的增加，联盟结构的数量也 随之增加。经过实验的证明，当数据集中 Agent 个数超过 15 时，使用穷举法列举出所有联盟结构 是不可行的。 3 最坏情况有限界联盟结构生成 Dean 和 Boddy 在时间依赖规划 (time depend￾ent planning) 的基础上提出了 Anytime 算法，其本 质是一种反复求解使得结果更加精确的算法。在 算法的运行过程中，能够很快得到一个不精确的 解，然后进行若干次的重复过程，经过重复后逐 步提高解的质量，Anytime 算法一个最显著的优 点就是能够很好地权衡计算时间和解的质量。 Sandholm 等 [15]使用 Anytime 算法开创性地提出了 一种最坏情况有限界联盟结构生成。 命题 1 表明，在联盟结构图上找到最优的联 盟结构是不可行的。所以，在进行联盟结构图的 搜索的时候设定一个限界。 对联盟结构的子集 N 进行搜索，目的在于寻 找搜索中的最优联盟结构，即局部最优联盟结 构，记： CS ∗ N = argmax CS ∈N V(CS ) V(CS ∗ N ) 同时，为了保证设定的联盟结构在最佳范围 内，即存在一个有限的但是尽可能小的值 k，k 被 称为搜索的解的界限，也是衡量局部最优解 的标准。能够建立起界限的最小的 k 记为 k = min{κ}, κ ⩾ V(CS ∗ ) V(CS ∗ N ) Ci v(Ci) ⩾ 0 V(CS ) = ∑k i=1 v(Ci) 通常，如果没有对联盟结构进行完全搜索，设 定一个正确的界限是很难的。这是因为：在剪枝 的过程中虽然可以减少一些联盟结构的搜索，但 是很难保证没有剪掉的比剪掉的具有更优性。在 进行社会福利的定义的时候，令任意一个联盟 的 值 ，并且一个联盟结构的社会福利 ，这两点就保证了上述假设是不存 在的，即在没有对联盟结构进行搜索的前提下设 置一个界限来缩小搜索联盟结构的数量。 3.1 建立界限 本节主要讨论如何尽可能地减少对图的搜索 的前提下，建立一个界限 k。 Π C 1 、Π C 2 2 n−1 nmin = 2 n−1 2 n−1 定理 1 对于界限 k，可以只搜索联盟结构图 的最低的两级 (图 1 中第 层)。在这个搜 索中，界限 k=n，需要搜索的联盟结构节点的数量 是 ，这也是能够建立起界限的最小的搜索，即 。并且，没有其他的算法对于联盟结构 的搜索的数量会比 少。 2 n −2 1 2 (2n −2) 1+ 1 2 (2n −2) = 2 n−1 最底层具有 1 个联盟结构，第二最底层中具 有 个联盟 (N 中的所有子集，除掉全集和空 集)。在这一层中，每个联盟结构都有 2 个联盟， 所以一共有 个联盟结构。只搜索最底下 两层，一共搜索 个联盟结果。 3.2 算法描述 算法 1 最坏情况有保证联盟结构生成算法 1) 搜索联盟结构图的最底二层； 2) 从联盟结构图的顶层 (第 n 层) 开始，作宽 度优先搜索，一直搜索到时间不允许为止或搜索 完整个联盟结构图； 3) 返回迄今为止所得到的最优的联盟结构。 先前使用特征函数的方式[25-26]进行联盟结构 生成，算法 1 是一种任意时间算法，可以在任何时 ·416· 智 能 系 统 学 报 第 14 卷

第3期 任子仪，等：约束条件下联盟生成研究进展 ·417· 间中断。如果将第1、2层搜索完成后，还存在剩 的答案。将动态规划算法应用于最优化的问题， 余时间，则可进一步地搜索缩小界限。 般分为4个步骤来完成： 定理2如果联盟结构图的第1、2层已经被 1)找出最优解的性质，并刻画其结构特征； 搜索完成并且第1层以及以上的层也被搜索完成 2)递归定义的最优值： 亿引当n=-nd且n三mad)时，k=[ 3)以自顶向下的方式计算出最优值； 是紧的，否则k=月是紧的，其中归= n-l 4)根据计算最优值所得到的信息，构造最优解。 +2 2 将动态规划算法应用于联盟中的想法是 在2-1个节点被搜索完之前，无法建立一个 Yeh在1986年首次提出的I;Rothkopf0及刘惊 界限。当搜索到2-1+1个节点时，可以建立界限 雷等B使用DP算法对求解最优联盟结构的算法 k=;搜索到2-l+1个节点的时候，界限变成 进行了改进，主要解决存在大量重复子问题计算 k=”。通过更多实验验证：当界限k变成” 的问题；Rahwan等2提出了IDP(improved dynam- 时，搜索的层数就会增加2层。当搜索的层数每 itic programming))算法；张新良等在2007年提出 增加2层，界限k前面的除数就会加1，若只多搜 了一种快速动态生成(search of coalition structure, 索一层时，没有明显效果。 SCS)算法，主要降低搜索次数。本文中，DP算法 总之，最坏情况有限界联盟结构生成算法中 主要基于定理3。 第2步具有很强的理性，即界限k能够迅速地下 定理3任意给定一个联盟C∈N,V(CS)是 降，同时该算法的收益递减，如图3所示。 最优联盟结构的社会福利，即V(CS)=maxV(CS), 则 (C),IC=1 V(CS*)= maxv(C),ma(vC)+v(C"),其他 ●， (1) 使用定理3进行动态规划，先计算只有一个 Agent的联盟，接着迭代具有2个Agent的联盟， 然后是具有3个Agent的联盟，一直迭代到具有 n个Agent的联盟。对于每个联盟C都需要使用 式(1)计算。从式(1)中易知：当1C≠1时，需要 ×104 2.5 50 7.5 10.0 搜索节点数 分别计算aC)+C和C)的值，然后将 两个值进行比较，得到具有较大社会福利的联 图3界限k作为10个Agent博奔中搜索的函数 盟。在此过程中，将所产生的暂存结果保存在变 Fig.3 Ratio bound k as a function of search in a 10-Agents 量t(C)中。 game 通过上述操作，计算出来的最大(C)就是我 界限k=n的建立与输入的Agct联盟的个 们最终要求的V(CS)。计算CS的迭代过程具体 数之间呈线性关系，这是因为输入2-1个数据，而 操作如例2所示。 当界限k=”时能够建立21个联盟结构，就是 例2令数据集N={a,a2,a3,aal,假设特征函 数为 所说的第1、2层和第n层上面的节点。 胡山立等22对算法1深入研究并进行改进， (a1)=30,v({a2)=40 v({a3)=25,v({a4)=45 给出了解决问题的一种任一时间联盟结构生成算 v{a1,a2})=50,v(《a1,a3)=60. 法和给定界限要求的联盟结构生成。Dang v{a1,aa)=80,v({a2,a3)=55 等提出不以层为单位最坏情况有限界的联盟结 v({a2,aa})=70,v({a3,aa})=80 构生成。 v({a1,a2,a3）=90,v({a1,a2,a4)=120 vla1,a3,a4l)=100,v({a2,a3,aul）=115 v({a1,a2,a3,a4)=140 4动态规划联盟生成求精确最优解 表1表示算法的具体运算过程。由表1知， 动态规划(dynamic programming,DP)算法和 tW=({a1,a2,{a3,au),能够将N分裂成{a1,2}和 分治法类似，其基本思想是将待求解的问题分解 {a,aa},而t({as,a4)={a3,a},这是因为{a1,a2}分 成若干个次级子问题，在求解的过程中，先求解 裂成{a{a2}后的社会福利比较大，{a,aa}不需 子问题，然后从子问题的解中得到要求解的问题 要进行分裂。所以CS={a,{a2,{a3,aa}o

间中断。如果将第 1、2 层搜索完成后，还存在剩 余时间，则可进一步地搜索缩小界限。 l > 3 n ≡ h−l( mod h) n ≡ l( mod h) k = ⌈ n h ⌉ k = ⌊ n h ⌋ h = ⌊ n−l 2 ⌋ +2 定理 2 如果联盟结构图的第 1、2 层已经被 搜索完成并且第 1 层以及以上的层也被搜索完成 ( )，当 且 时， 是紧的，否则 是紧的，其中 。 2 n−1 2 n−1 +1 2 n−1 +1 k = 1 2 n 1 3 n 在 个节点被搜索完之前，无法建立一个 界限。当搜索到 个节点时，可以建立界限 k=n；搜索到 个节点的时候，界限变成 。通过更多实验验证：当界限 k 变成 时，搜索的层数就会增加 2 层。当搜索的层数每 增加 2 层，界限 k 前面的除数就会加 1，若只多搜 索一层时，没有明显效果。 总之，最坏情况有限界联盟结构生成算法中 第 2 步具有很强的理性，即界限 k 能够迅速地下 降，同时该算法的收益递减，如图 3 所示。 k = 1 2 n 2 n−1 k = 1 2 n 2 n−1 界限 的建立与输入的 Agent 联盟的个 数之间呈线性关系，这是因为输入 个数据，而 当界限 时能够建立 个联盟结构，就是 所说的第 1、2 层和第 n 层上面的节点。 胡山立等[27-28]对算法 1 深入研究并进行改进， 给出了解决问题的一种任一时间联盟结构生成算 法和给定界限要求的联盟结构生成。 Dang 等 [29]提出不以层为单位最坏情况有限界的联盟结 构生成。 4 动态规划联盟生成求精确最优解 动态规划 (dynamic programming，DP) 算法和 分治法类似，其基本思想是将待求解的问题分解 成若干个次级子问题，在求解的过程中，先求解 子问题，然后从子问题的解中得到要求解的问题 的答案。将动态规划算法应用于最优化的问题， 一般分为 4 个步骤来完成： 1) 找出最优解的性质，并刻画其结构特征； 2) 递归定义的最优值； 3) 以自顶向下的方式计算出最优值； 4) 根据计算最优值所得到的信息，构造最优解。 将动态规划算法应用于联盟中的想法 是 Yeh 在 1986 年首次提出的[16] ；Rothkopf[30]及刘惊 雷等[31]使用 DP 算法对求解最优联盟结构的算法 进行了改进，主要解决存在大量重复子问题计算 的问题；Rahwan 等 [32]提出了 IDP(improved dynam￾itic programming) 算法；张新良等[33]在 2007 年提出 了一种快速动态生成 (search of coalition structure, SCS) 算法，主要降低搜索次数。本文中，DP 算法 主要基于定理 3。 C ∈ N V(CS∗ ) V(CS∗ ) = max CS ∈Πn V(CS) 定理 3 任意给定一个联盟 ， 是 最优联盟结构的社会福利，即 ， 则 V(CS∗ ) =    v(C), |C| = 1 max{v(C), max {C′ ,C′′}∈ΠN (v(C ′ )+v(C ′′)}, 其他 (1) |C| , 1 max {C′ ,C′′}∈ΠN v(C ′ )+v(C ′′) v(C) t(C) 使用定理 3 进行动态规划，先计算只有一个 Agent 的联盟，接着迭代具有 2 个 Agent 的联盟， 然后是具有 3 个 Agent 的联盟，一直迭代到具有 n 个 Agent 的联盟。对于每个联盟 C 都需要使用 式 (1) 计算。从式 (1) 中易知：当 时，需要 分别计算 和 的值，然后将 两个值进行比较，得到具有较大社会福利的联 盟。在此过程中，将所产生的暂存结果保存在变 量 中。 v(C) V(CS∗ ) CS∗ 通过上述操作，计算出来的最大 就是我 们最终要求的 。计算 的迭代过程具体 操作如例 2 所示。 例 2 令数据集 N = {a1,a2,a3,a4} ，假设特征函 数为 v({a1}) = 30, v({a2}) = 40, v({a3}) = 25, v({a4}) = 45, v({a1 ,a2}) = 50, v({a1 ,a3}) = 60, v({a1 ,a4}) = 80, v({a2 ,a3}) = 55, v({a2,a4}) = 70, v({a3,a4}) = 80, v({a1,a2,a3}) = 90, v({a1,a2,a4}) = 120 v({a1,a3,a4}) = 100, v({a2,a3,a4}) = 115, v({a1,a2,a3,a4}) = 140 t(N) = ({a1,a2},{a3,a4}) {a1,a2} {a3,a4} t({a3,a4}) = {{a3,a4}} {a1,a2} {a1}、{a2} {a3,a4} CS∗ = {{a1},{a2},{a3,a4}} 表 1 表示算法的具体运算过程。由表 1 知， ，能够将 N 分裂成 和 ，而 ，这是因为 分 裂成 后的社会福利比较大， 不需 要进行分裂。所以 。 5.0 10.0 ×10 1 4 3 5 7 9 k 搜索节点数 2.5 7.5 图 3 界限 k 作为 10 个 Agent 博弈中搜索的函数 Fig. 3 Ratio bound k as a function of search in a 10-Agents game 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·417·

·418· 智能系统学报 第14卷 表14个Agent动态规划算法 Table 1 The dynamic programming algorithm for 4 Agents c 特征函数值 (C) v(C) a1) vta1)=30 la) 30 (a2) v(Ia2》=40 (a2) 40 as) v(Ia3)=25 {a3} 25 (a4) v({a4)=45 las) 45 a,az v({a1,a2)=50,f{a1)+fa2D=70 a1,{a2} 70 {a1,a3} ({a1,a3》=60,fa1)+fla3)=55 {a1,a3 60 {a1,a4} ({a1,a4l)=80,fa1》+fa4l)=75 a1,a4} 80 (2.a3) v{a2,a3)=55,f({a2})+f({a3)=65 (a2).(a3) 65 az,a4) v({a2,a4》=70,f{a2)+fla4l)=85 {a2,{a4} 85 {a3,a4} {a3,a4)=80,f({a3)+f({a4)=70 {a3,a4 80 v({a1,a2,a3l)=90,fIa1)+f({a2,a3)=95 f(Ia2)+fa1,a3》=100,fa3》+f{a1,a2)=95 {a1,a2,3} {a2,{a1,a3} 100 v({a1,a2,a4)=120,f({a1)+f({a2,a4)=115 f({a2)+f{a1,a4)=120,f(la4)+f{a1,a2)=115 {a1,a2,a4} {a1,a2,a4} 120 {a1,a3,a4l)=100,fa1l)+f1a3,a4)=110 {a1,a3,a4} fa3)+f(ta,a4D=105,fa4)+f{a1,a3》=105 {a1,{a3,a4l 110 {a2,a3,a4)=115,f{a2D+f{a3,a4l)=120 {a2,a3,a4l f(a3》+f({a2,a4》=110,f{a4)+f{a2,a3》=110 {a2l,{a3,a4} 120 va,a2,a3,a4)=140,fa4》+f{a1,a2,a3D=145 la1,d2,a3,a4} fla1,a2l)+fa3,a4》=150,fa3)+f({a1,a2,a4)=145 f(la1,a3D+fa2,a4D=145,fa2)+f(la1,a3,a4)=150 {a1,a2,{a3,a4} 150 f(ta1,a4l)+fla2,a3)=145,fa1》+f{a2,a3,a4l)=150 定理4给定一组Agent集，使用动态规划算 集合（见表2）。设G,G2,,G∈S。是所有的存 法求得最优联盟结构的时间复杂度O3")。 在的唯一配置的结合（即不存在具有相同联盟大 DP算法在该算法的运行过程中实际做了如 小的两个元素)，令F:SCs→2s是一个函数，按照 下几方面： 提前设定好的配置返回所有的联盟结构。N表示 1)评估图上的运动： 一个列表，里面的每一个元素表示一组具有相同 2)在表1中存储最优结构； 配置的联盟结构。形式上，N定义为：N= 3)从底部节点开始向上运动。 {F(G),F(G2,,F(Gsa》,N,N2,…,Ne∈N表示N 5联盟生成求近似最优解 中的每个元素（见表3）。 表24个Agent联盟列表 Rahwan等B将联盟配置与Anytime算法进行 Table 2 The coalition list of 4 Agents 结合提出一种联盟结构相似最优解算法；为Ab CLs 联盟列表值 izui等基于整数分区对联盟结构进行推广从而 CLI {a1,{a2h,{a3l,{a4} 对联盟配置(coalition configuration)进行了定义。 CL2 {a1,a3l,{a1,a4},{a2,a3},{a2,a4h,{a3,a4 5.1基本定义 CL3 在进行求解的过程中，设CL∈2”，其中 {a1,a2,a3,{a1,2,a4},{a1,a3,a4h,{a2,a3,a4} se{1,2,,k是联盟列表，CL是联盟列表CL,的 CL4 {a1,a2,a3,a4}

O(3n ) 定理 4 给定一组 Agent 集，使用动态规划算 法求得最优联盟结构的时间复杂度 。 DP 算法在该算法的运行过程中实际做了如 下几方面： 1) 评估图上的运动； 2) 在表 t 中存储最优结构； 3) 从底部节点开始向上运动。 5 联盟生成求近似最优解 Rahwan 等 [34]将联盟配置与 Anytime 算法进行 结合提出一种联盟结构相似最优解算法；为 Alb￾izuri 等 [35]基于整数分区对联盟结构进行推广从而 对联盟配置 (coalition configuration) 进行了定义。 5.1 基本定义 CLs ∈ 2 n s ∈ {1,2,· · ·, k} CLi CLs 在进行求解的过程中，设 ，其中 是联盟列表， 是联盟列表 的 G1,G2,· · ·,Gςcs ∈ ςcs F : ςCS → 2 CS N N {F(G1),F(G2),· · ·,F(G|ςCS|)} N1,N2,· · ·,NςCS ∈ N N 集合 (见表 2)。设 是所有的存 在的唯一配置的结合 (即不存在具有相同联盟大 小的两个元素)，令 是一个函数，按照 提前设定好的配置返回所有的联盟结构。 表示 一个列表，里面的每一个元素表示一组具有相同 配置的联盟结构。形式上， 定义为： N = ， 表 示 中的每个元素 (见表 3)。 表 1 4 个 Agent 动态规划算法 Table 1 The dynamic programming algorithm for 4 Agents C 特征函数值 t(C) v(C) {a1} v({a1}) = 30 {a1} 30 {a2} v({a2}) = 40 {a2} 40 {a3} v({a3}) = 25 {a3} 25 {a4} v({a4}) = 45 {a4} 45 {a1,a2} v({a1,a2}) = 50, f({a1})+ f({a2}) = 70 {a1},{a2} 70 {a1,a3} v({a1,a3}) = 60, f({a1})+ f({a3}) = 55 {a1,a3} 60 {a1,a4} v({a1,a4}) = 80, f({a1})+ f({a4}) = 75 {a1,a4} 80 {a2,a3} v({a2,a3}) = 55, f({a2})+ f({a3}) = 65 {a2},{a3} 65 {a2,a4} v({a2,a4}) = 70, f({a2})+ f({a4}) = 85 {a2},{a4} 85 {a3,a4} v({a3,a4}) = 80, f({a3})+ f({a4}) = 70 {a3,a4} 80 {a1,a2,a3} v({a1,a2,a3}) = 90, f({a1})+ f({a2,a3}) = 95 f({a2})+ f({a1,a3}) = 100, f({a3})+ f({a1,a2}) = 95 {a2},{a1,a3} 100 {a1,a2,a4} v({a1,a2,a4}) = 120, f({a1})+ f({a2,a4}) = 115 f({a2})+ f({a1,a4}) = 120, f({a4})+ f({a1,a2}) = 115 {a1,a2,a4} 120 {a1,a3,a4} v({a1,a3,a4}) = 100, f({a1})+ f({a3,a4}) = 110 f({a3})+ f({a1,a4}) = 105, f({a4})+ f({a1,a3}) = 105 {a1},{a3,a4} 110 {a2,a3,a4} v({a2,a3,a4}) = 115, f({a2})+ f({a3,a4}) = 120 f({a3})+ f({a2,a4}) = 110, f({a4})+ f({a2,a3}) = 110 {a2},{a3,a4} 120 {a1,a2,a3,a4} v({a1,a2,a3,a4}) = 140, f({a4})+ f({a1,a2,a3}) = 145 f({a1,a2})+ f({a3,a4}) = 150, f({a3})+ f({a1,a2,a4}) = 145 f({a1,a3})+ f({a2,a4}) = 145, f({a2})+ f({a1,a3,a4}) = 150 f({a1,a4})+ f({a2,a3}) = 145, f({a1})+ f({a2,a3,a4}) = 150 {a1,a2},{a3,a4} 150 表 2 4 个 Agent 联盟列表 Table 2 The coalition list of 4 Agents CLs 联盟列表值 CL1 {a1},{a2},{a3},{a4} CL2 {a1,a3},{a1,a4},{a2,a3},{a2,a4},{a3,a4} CL3 {a1,a2,a3},{a1,a2,a4},{a1,a3,a4},{a2,a3,a4} CL4 {a1,a2,a3,a4} ·418· 智 能 系 统 学 报 第 14 卷

第3期 任子仪，等：约束条件下联盟生成研究进展 ·419· 表34个Agent配置表及具体联盟表示 Table 3 The configuration table and specific coalition representation of 4 Agents 联盟数量 配置表及具体联盟表示 1 G={4,F(G={a1,a2,a3,a4} {a1,a2h,{a3,a4H {Ha1,{a2,a3,a4} 2 G=2,21,F(G)= {a1,a3,{a2,a4} G={1,3,F(G)= {a2h,{a1,a3,a4}》 {a1,a4,{a2,a3} {a3,{a1,a2,a4》 {a4,{a1,a2,a3} {a3h,{a4,{a1,a2} {a2,{a4,{a1,a3} G=1,1,2,F(G= {a2,{a3,{a1,a4} {a1,{a4,{a2,a3} {a1,{a3,{a2,a4} {a1,{a2,{a3,a4} G={1,1,1,1,F(G={Ha1,{a2,{a3h,{a4} 5.2具体实现 中的联盟组成的不相交的联盟结构的值。 算法实现分为3个部分：1)预处理操作：2)构 ②泡含配置为1,2，…，的联盟：计算G={1,2,…,i 造和选择合适的配置：3)搜索元素。 配置的联盟结构的值。 1)预处理操作 经过上述两个操作搜索联盟结构，可以搜索 预处理的主要目的是计算CL,的最大值max, 空间的一部分（随着n的增加而减小）。表4表示 和平均值avg,并返回计算值，同时将当前搜索社 的是8个Agent搜索结果，其中配置G={8, 会福利最大的联盟结构返回记为CS。此过程 G={4,4},G=3,5,G=2,6,G={1,71,G={1,1,6, 中，主要进行2种操作，分别是评估互补大小和包 G=1,1,1,5},G=1,1,1,1,1,3},G={1,1,1,1,1,3}, 含配置为{1,2，…，计的联盟。 G=1,1,1,1,1,1,2,G=1,1,1,1,1,1,1,1)是在预处 ①评估互补大小：将CL,和CL,称为互补 理操作中需要将被搜索的配置。 的，如CL和CL1。在此过程中需要计算由互补 2)构造和选择合适的配置 表48个Agent配置表 Table 4 The configuration table of 8 Agents 层数 配置表 1=1 G={8) 1=2 G=4,4}G=3,5}G=2,61G={1,7} 1=3 G=2,3,3}G={2,2,4G=1,3,41G={1,2,5}G={1,1,6 1=4 G=2,2,2,2}G={1,2,2,3}G={1,1,3,3}G={1,1,2,4}G={1.1,1,5 1=5 G={1,1,2,2,2G={1,1,1,2,3}G={1,1,1,1,1,3引 1=6 G={1,1,1,1,2,2}G={1,1,1,1,1,3} 1=7 G={1,1,1,1,1,1,2} 1=8 G={1,1,1,1.1,1,1.1} 在搜索过程中，进行剪枝操作主要目的是减 1}和{1,1,1,1,1}。计算每个配置G对应于 少搜索空间。G为搜索完后找到可能存在最优联 F(G)的上界UBc和平均值Avgc。将V(CS)和 盟结构的配置。 UBcB进行比较，如果G中所有的配置都满足前 ①构造独一无二的配置：保证所有的配置的 者大于后者，那么该解即为最优解。否则，进行 集合等于所有Agent可能产生的整数分区。例 ②操作。 如，有5个Agent,.可能存在的整数分区的配置 ②选择合适的配置：搜索过程中满足AYC> 0BE≥K G为{5}，{4,1}，{3,2}，{3,1,1，{2,2,1}，{2,1,1， 则选择元素中最小的一个，否则继续进行剪枝工作

5.2 具体实现 算法实现分为 3 个部分：1) 预处理操作；2) 构 造和选择合适的配置；3) 搜索元素。 1) 预处理操作 CLs maxs avgs CS′ {1,2,· · ·,i} 预处理的主要目的是计算 的最大值 和平均值 并返回计算值，同时将当前搜索社 会福利最大的联盟结构返回记为 。此过程 中，主要进行 2 种操作，分别是评估互补大小和包 含配置为 的联盟。 CLs CLn−s CL3 CL1 ①评估互补大小：将 和 称为互补 的，如 和 。在此过程中需要计算由互补 中的联盟组成的不相交的联盟结构的值。 ②包含配置为 {1,2,··· ,i} 的联盟：计算 G = {1,2,··· ,i} 配置的联盟结构的值。 G = {8} G = {4,4} G = {3,5} G = {2,6} G = {1,7} G = {1,1,6} G = {1,1,1,5} G = {1,1,1,1,1,3} G = {1,1,1,1,1,3} G = {1,1,1,1,1,1,2} G = {1,1,1,1,1,1,1,1} 经过上述两个操作搜索联盟结构，可以搜索 空间的一部分 (随着 n 的增加而减小)。表 4 表示 的 是 8 个 Agen t 搜索结果，其中配置 ， ， ， ， ， ， ， ， ， ， 是在预处 理操作中需要将被搜索的配置。 2) 构造和选择合适的配置 G ′ 在搜索过程中，进行剪枝操作主要目的是减 少搜索空间。 为搜索完后找到可能存在最优联 盟结构的配置。 ①构造独一无二的配置：保证所有的配置的 集合等于所有 Agent 可能产生的整数分区。例 如 ，有 5 个 Agent，可能存在的整数分区的配置 G 为{5}，{4, 1}，{3, 2}，{3, 1, 1}，{2, 2, 1}，{2, 1, 1, UBG AvgG V(CS′ ) UBG′β G ′ 1}和{1, 1, 1, 1, 1}。计算每个配置 G 对应于 F(G) 的上界 和平均值 。将 和 进行比较，如果 中所有的配置都满足前 者大于后者，那么该解即为最优解。否则，进行 ②操作。 AVG UB∗ G ②选择合适的配置：搜索过程中满足 ⩾ k， 则选择元素中最小的一个，否则继续进行剪枝工作。 表 3 4 个 Agent 配置表及具体联盟表示 Table 3 The configuration table and specific coalition representation of 4 Agents 联盟数量 配置表及具体联盟表示 1 G = {4},F(G) = {{a1,a2,a3,a4}} 2 G = {2,2},F(G) =    {{a1,a2},{a3,a4}} {{a1,a3},{a2,a4}} {{a1,a4},{a2,a3}} G = {1,3},F(G) =    {{a1},{a2,a3,a4}} {{a2},{a1,a3,a4}} {{a3},{a1,a2,a4}} {{a4},{a1,a2,a3}} 3 G = {1,1,2},F(G) =    {{a3},{a4},{a1,a2}} {{a2},{a4},{a1,a3}} {{a2},{a3},{a1,a4}} {{a1},{a4},{a2,a3}} {{a1},{a3},{a2,a4}} {{a1},{a2},{a3,a4}} 4 G = {1,1,1,1},F(G) = {{a1},{a2},{a3},{a4}} 表 4 8 个 Agent 配置表 Table 4 The configuration table of 8 Agents 层数 配置表 l = 1 G = {8} l = 2 G = {4,4} G = {3,5} G = {2,6} G = {1,7} l = 3 G = {2,3,3} G = {2,2,4} G = {1,3,4} G = {1,2,5} G = {1,1,6} l = 4 G = {2,2,2,2} G = {1,2,2,3} G = {1,1,3,3} G = {1,1,2,4} G = {1,1,1,5} l = 5 G = {1,1,2,2,2} G = {1,1,1,2,3} G = {1,1,1,1,1,3} l = 6 G = {1,1,1,1,2,2} G = {1,1,1,1,1,3} l = 7 G = {1,1,1,1,1,1,2} l = 8 G = {1,1,1,1,1,1,1,1} 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·419·

·420· 智能系统学报 第14卷 ③更新上边界：进行搜索的CS·是可以计算 Agent集，称为枢纽Agent。规定任意一个可行联 本身的数值或者将其自身分裂后形成联盟的最大 盟结构中不允许存在两个及其以上的枢纽Agent。 值。例如，在搜索配置为G={1,1,1,1,2,3,4}的 a,B:SHR是两个评估函数，而x,y∈R是两个实 元素时，最大值可能的组合是{1,1,3}。当求配 数，则=是的评估结构。 置G={1,1,1,3,3,4;的上边界时，在配置G={1,1,3} 例4给定一个联盟博弈T=,其中N= 的上边界的基础上加上max,+max+max。以 {a1,a2,…,a}。评估结构为c=(D,{a1,a2,,B,x,y), 该方式对配置进行拆分处理，能更好地更新上 其中图D如图4所示。 边界。 3)搜索元素 搜索过程的关键在于构建联盟结构。在该算 0 法中，构建联盟结构的主要问题是，在执行时会 进行重复操作，从而形成冗余和无效的联盟结构。 ①避免重叠的联盟结构：重叠的联盟结构 是{a1,a2{a2,as》这样。使用快速索引技术进行 图47个Agent交互图 解决。 Fig.4 The interactive graph of 7 Agents ②避免冗余的联盟结构：冗余的联盟结构是 图4中C1={a1,al,C2={a4,a5,a6}是2个可行 {a1,l,{a3,a》和{Ha,aa,{a1,a2》这样。在进行组 联盟，而{a1,2}和{as,a}是2个不可行联盟，前者 合的过程中以升序排列，并且使用联盟中最小的 是因为联盟中2个Agent都是枢纽Agent,,后者则 元素C作为关键点，以确定已经存在的联盟。 是因为联盟不是图4的子图。 ③正确性证明：通过上述步骤可以生成唯一 如果C是可行联盟结构，将函数α、B和实数 的和有效的解决方案。 x、y通过式(2)定义成评估函数v的映射val,。 6约束条件下联盟生成求最优解 vale(v,C)= a(a)xv(C)+B(ai),(ai)=cns xxv(C)+y,cns=0 (2) Frankovi等B将关注点从所有Agent之间的 例5假设图4中，估值函数为”，C是一个 联系转移到只关注给定Agent之间建立最优的联 可行联盟，则v(C)被定义为由C所覆盖的边的权 盟。Greco等1经过进一步研究，提出了一种新的 值的总和，即 联盟结构生成方式一约束联盟结构，即在生成 C)=∑eeE,eeCw 联盟的过程对联盟添加约束。 C1={a,as1,C2={as,a6,a}的估值为 6.1约束联盟的基础 v(C1)=w(a1,a3)=1 在进行约束联盟结构形成的过程中，主要是 vC2)=w(a,a6,a)=w(as,a6)+w(a6,)=1+1=2 定义在一对上的，称为联盟博弈，其 假设函数、B分别为a:{a1,a2}→{1，B:{a1, 中N=(a,a2,,an)是Agent集，v是评估函数。 a2}→{0，而实数=0，=-12，则val(C)=1×v(C)+ 例3假设一个联盟博弈为,其中 0=1,val(C2)=0×vC2)-12=-12。 N=(a1,a2,a),评估函数为 63边际贡献网上联盟生成 ({a3》=0 边际贡献网在过去的几年里收到了相当大 v({a1)=v({a2l》=v({a1,a3l)=v(《a2,a3》=1 v({a1,a2l)=v({a1,a2,a3l》=3 的关注。边际贡献网(marginal contribution net- 易知，最优联盟结构是{a,a2,a}和{a,a2,{a3, work,MC-net)是包含一系列代表Agent的布尔变 这是因为v({a1,a2》+v({al》=({a1,a2,a3)=3。 量的规则，每个规则的形式为pattern)→value,其 假设在联盟博弈中，Agent集上定义 中pattern可以包含正面的连接或负面的连接， 一个无向图G,G称为交互图。联盟C是可行的， value是与此pattern相关的附加贡献。 当且仅当C在G的子图上是连通的。 例6给定一个联盟博弈T=,其中 6.2约束联盟结构生成 N={a1,a2,,as},v({a1,a2l)=v({a2,a3)=v({a1,a)=2; 令T=是联盟博弈，D=(W,E)是联盟 3ie(1,2,,5l,v({al)=0w({a1,a2,a3)=5:3Cc{a1,a2, 博弈上的一个交互图，其中图中的交点是N中的 a},vCU{a4》=vC{a)=v(C)=(CU{a,as);根 Agent,,边是节点集，设S∈W是一个可能为空的 据边际贡献网，给定规则为

CS ∗ max1 +max3+max4 ③更新上边界：进行搜索的 是可以计算 本身的数值或者将其自身分裂后形成联盟的最大 值。例如，在搜索配置为 G={1, 1, 1, 1, 2, 3, 4}的 元素时，最大值可能的组合是{1, 1, 3}。当求配 置 G={1, 1, 1, 3, 3, 4}的上边界时，在配置 G={1, 1, 3} 的上边界的基础上加上 。 以 该方式对配置进行拆分处理，能更好地更新上 边界。 3) 搜索元素 搜索过程的关键在于构建联盟结构。在该算 法中，构建联盟结构的主要问题是，在执行时会 进行重复操作，从而形成冗余和无效的联盟结构。 {{a1,a2}{a2,a3}} ①避免重叠的联盟结构：重叠的联盟结构 是 这样。使用快速索引技术[36]进行 解决。 {{a1,a2},{a3,a4}} {{a3,a4},{a1,a2}} C 1 k ②避免冗余的联盟结构：冗余的联盟结构是 和 这样。在进行组 合的过程中以升序排列，并且使用联盟中最小的 元素 作为关键点，以确定已经存在的联盟。 ③正确性证明：通过上述步骤可以生成唯一 的和有效的解决方案。 6 约束条件下联盟生成求最优解 Frankovi 等 [37]将关注点从所有 Agent 之间的 联系转移到只关注给定 Agent 之间建立最优的联 盟。Greco 等 [18]经过进一步研究，提出了一种新的 联盟结构生成方式——约束联盟结构，即在生成 联盟的过程对联盟添加约束。 6.1 约束联盟的基础 (a1,a2,· · ·,an) 在进行约束联盟结构形成的过程中，主要是 定义在一对 上的， 称为联盟博弈，其 中 N = 是 Agent 集，v 是评估函数。 N = (a1,a2,a3) 例 3 假设一个联盟博弈为 ，其中 ，评估函数为 v({a3}) = 0 v({a1}) = v({a2}) = v({a1,a3}) = v({a2,a3}) = 1 v({a1,a2}) = v({a1,a2,a3}) = 3 {a1,a2,a3} {{a1,a2},{a3}} v({a1,a2})+v({a3}) = v({a1,a2,a3}) = 3 易知，最优联盟结构是 和 ， 这是因为 。 假设在联盟博弈 中，Agent 集上定义 一个无向图 G，G 称为交互图。联盟 C 是可行的， 当且仅当 C 在 G 的子图上是连通的。 6.2 约束联盟结构生成 Γ= D = (N,E) S ∈ N 令 是联盟博弈， 是联盟 博弈上的一个交互图，其中图中的交点是 N 中的 Agent，边是节点集，设 是一个可能为空的 α, β : S 7→ R x, y ∈ R σ= Agent 集，称为枢纽 Agent。规定任意一个可行联 盟结构中不允许存在两个及其以上的枢纽 Agent。 是两个评估函数，而 是两个实 数，则 是 的评估结构。 Γ= {a1,a2,··· ,a7} σ = (D,{a1,a2},α, β, x, y) 例 4 给定一个联盟博弈 ，其中 N = 。评估结构为 ， 其中图 D 如图 4 所示。 C1 = {a1,a3} C2 ={a4,a5,a6} {a1,a2} {a5,a7} 图 4 中 ， 是 2 个可行 联盟，而 和 是 2 个不可行联盟，前者 是因为联盟中 2 个 Agent都是枢纽 Agent，后者则 是因为联盟不是图 4 的子图。 valσ 如果 C 是可行联盟结构，将函数 α、β 和实数 x、y 通过式 (2) 定义成评估函数 v 的映射 。 valσ(v,C) = { α(ai)×v(C)+β(ai), {ai} = C ∩S x×v(C)+y, C ∩S = Ø (2) v(C) 例 5 假设图 4 中，估值函数为 v，C 是一个 可行联盟，则 被定义为由 C 所覆盖的边的权 值的总和，即 v(C) = ∑ e ∈ E, e ∈ Cwe C1 = {a1,a3},C2 = {a5,a6,a7} 的估值为 v(C1) = w(a1,a3) = 1 v(C2) = w(a5,a6,a7) = w(a5,a6)+w(a6,a7) = 1+1 = 2 α、β α : {a1,a2} → {1} β : {a1, a2} → {0} valσ(C1) = 1×v(C1) 0 = 1,valσ(C2) = 0×v(C2)−12 = −12 假设函数 分别为 ， ，而实数 x=0，y=−12，则 + 。 6.3 边际贡献网上联盟生成 {pattern} → value 边际贡献网[38]在过去的几年里收到了相当大 的关注。边际贡献网 (marginal contribution net￾work, MC-net) 是包含一系列代表 Agent 的布尔变 量的规则，每个规则的形式为 ，其 中 pattern 可以包含正面的连接或负面的连接， value 是与此 pattern 相关的附加贡献。 Γ = N = {a1,a2,· · ·,a5} v({a1,a2})=v({a2,a3}) = v({a1,a3})=2 ∃i ∈ {1,2,· · ·,5}, v({ai}) = 0；v({a1,a2,a3}) = 5；∃C ⊆ {a1,a2 a3} v(C ∪ {a4}) = v(C ∪ {a5}) = v(C) = v(C ∪ {a4,a5}) 例 6 给定一个联盟博弈 ，其中 ， ； , ， ； 根 据边际贡献网，给定规则为 a1 a2 a3 a4 a6 a5 a7 1 2 1 2 2 1 1 1 图 4 7 个 Agent 交互图 Fig. 4 The interactive graph of 7 Agents ·420· 智 能 系 统 学 报 第 14 卷

第3期 任子仪，等：约束条件下联盟生成研究进展 ·421· {a1Aa2Aa3}→2 ory[M].Cambridge:MIT Press,1994 {a1Λa2Λa3}→2 [5]VON NEUMANN J,MORGENSTERN O.Theory of {a1Aa2Aa3}→2 games and economic behavior[M].Princeton:Princeton {a1Λa2∧a3}→5 University Press.1972 {a3Aas}→0 {a2Aa4}→0 [6]WOOLDRIDGE M.BUSSMANN S.KLOSTERBERG M. 根据给定的规则，v({a1,a1,a1)=2。 Production sequencing as negotiation[C]//Proceedings of the First International Conference on the Practical Applica- 定理5令h≥0是一个固定自然数，T= tion of Intelligent Agents and Multi-Agent Technology. 是一个博弈，其中v是独立于不相交成员的评估 London,UK,1996:709-726. 函数，交互图D所构成的树的高大于h。令 [7]SANDHOLM T,SIKKA S,NORDEN S.Algorithms for σ=,则(T,σ)的联盟结构生成的值 optimizing leveled commitment contracts[C]//Proceed- 可以在多项式时间内解决。 ings of the 16th International Joint Conference on Artifical 约束满足问题具有较强的灵活性，能够进行 Intelligence.Stockholm,Sweden,1999:535-540. 推广解决文献[32]中提到的约束问题。 [8]RAHWAN T,MICHALAK T P,WOOLDRIDGE M,et al. Coalition structure generation:a survey[J].Artificial intel- 7结束语 ligence,.2015,229:139-174. [9]ZHU Han,POOR H V.Coalition games with cooperative 联盟结构生成问题中如何能够更快更精确地 transmission:a cure for the curse of boundary nodes in 进行优化整体性能对于研究人员一直都是挑战。 selfish packet-forwarding wireless networks[Cl//Proceed- 本文针对这一问题进行了全面的综述：1)搜索空 ings of the 5th International Symposium on Modeling and 间的不同表示：2)动态规划算法的时候来解决这 Optimization in Mobile,Ad Hoc and Wireless Networks 个问题；3)使用近似最优来代替最优解；4)使用 and Workshops.Limasso,Cyprus,2009:1-8. 评估的方法，主要是添加了约束条件。所有的这 [10]KHAN Z,LEHTOMAKI J,LATVA-AHO M,et al.On selfish and altruistic coalition formation in cognitive ra- 些结构都是以一种独立的方式展示出来的。 dio networks[C]//Proceedings of the 2010 Fifth Interna- 但是，在现有联盟生成的研究中，大多数是 tional Conference on Cognitive Radio Oriented Wireless 以Agent之间具有相同的协商资源和态度为前提 Networks and Communications.Cannes,France,2010 的，只考虑了协商中的相同性，却忽略了协商中 1-5. 的异质性。在未来的工作中，可以考虑将协商的 [11]LI Cuihong,SYCARA K,SCHELLER-WOLF A.Com- 异质性与约束联盟中的评估结构相结合。 binatorial coalition formation for multi-item group-buy- 同时，在约束K-means聚类算法的启发下，可 ing with heterogeneous customers[J].Decision support systems,.2010,491):1-13. 以将一般形式的无法连接的约束进行合理操作后 [12]MANOOCHEHRI H E,WENKSTERN R Z.Dynamic 有理性地加入到评估结构中。另外，可以进行扩 coalition structure generation for autonomous connected 展，将允许联盟生成的概率使用先验知识进行检 vehicles[C]//Proceedings of 2017 IEEE International 验或者将Agent之间的动态相互信任添加到联盟 Conference on Agents.Beijing,China,2017:21-26. 生成的过程中。 [13]SLESS L,HAZON N,KRAUS S,et al.Forming k coali- tions and facilitating relationships in social networks[J] 参考文献： Artificial intelligence.2018.259:217-245. [14]SLESS L.HAZON N.KRAUS S.et al.Forming coali- [1]AZIZ H.Multiagent systems:algorithmic,game-theoretic, tions and facilitating relationships for completing tasks in and logical foundations by Y.Shoham and K.Leyton- social networks[Cl//Proceedings of the 2014 Internation- Brown Cambridge University Press,2008[J].ACM al Conference on Autonomous Agents and Multi-Agent SIGACT news,2010.41(1):34-37. Systems.Paris,France,2014:261-268. [2]WOOLDRIDGE M.Computational aspects of cooperative [15]SANDHOLM T,LARSON K,ANDERSSON M,et al. game theory[C]//Proceedings of the 5th KES International Coalition structure generation with worst case guarantees Conference on Agent and Multi-Agent Systems:Technolo- [J].Artificial intelligence,1999,111(1/2):209-238. gies and Applications.Manchester,UK,2011. [16]YEH D Y.A dynamic programming approach to the com- [3]ELKIND E,RAHWAN T,JENNINGS N R.Computation- plete set partitioning problem[J].BIT numerical mathem- al coalition formation[M].Cambridge:MIT Press,2013: atics,1986,26(4):467-474. 329-380. [17]DANG TT,FRANKOVIE B,BUDINNSKA I.Create [4]OSBORNE M J,RUBINSTEIN A.A course in game the- agent's coalition based on a dynamic programming ap-

{a1 ∧a2 ∧ ¬a3} → 2 {¬a1 ∧a2 ∧a3} → 2 {a1 ∧ ¬a2 ∧a3} → 2 {a1 ∧a2 ∧a3} → 5 {a3 ∧a5} → 0 {a2 ∧a4} → 0 根据给定的规则， v({a1,a1,a1}) = 2。 h ⩾ 0 Γ = v D σ= (Γ,σ) 定理5 令 是一个固定自然数， 是一个博弈，其中 是独立于不相交成员的评估 函数，交互图 所构成的树的高大 于 h。 令 ，则 的联盟结构生成的值 可以在多项式时间内解决。 约束满足问题具有较强的灵活性，能够进行 推广解决文献[32]中提到的约束问题。 7 结束语 联盟结构生成问题中如何能够更快更精确地 进行优化整体性能对于研究人员一直都是挑战。 本文针对这一问题进行了全面的综述：1) 搜索空 间的不同表示；2) 动态规划算法的时候来解决这 个问题；3) 使用近似最优来代替最优解；4) 使用 评估的方法，主要是添加了约束条件。所有的这 些结构都是以一种独立的方式展示出来的。 但是，在现有联盟生成的研究中，大多数是 以 Agent 之间具有相同的协商资源和态度为前提 的，只考虑了协商中的相同性，却忽略了协商中 的异质性。在未来的工作中，可以考虑将协商的 异质性与约束联盟中的评估结构相结合。 同时，在约束 K-means 聚类算法的启发下，可 以将一般形式的无法连接的约束进行合理操作后 有理性地加入到评估结构中。另外，可以进行扩 展，将允许联盟生成的概率使用先验知识进行检 验或者将 Agent 之间的动态相互信任添加到联盟 生成的过程中。 参考文献： AZIZ H. Multiagent systems: algorithmic, game-theoretic, and logical foundations by Y. Shoham and K. Leyton￾Brown Cambridge University Press, 2008[J]. ACM SIGACT news, 2010, 41(1): 34–37. [1] WOOLDRIDGE M. Computational aspects of cooperative game theory[C]//Proceedings of the 5th KES International Conference on Agent and Multi-Agent Systems: Technolo￾gies and Applications. Manchester, UK, 2011. [2] ELKIND E, RAHWAN T, JENNINGS N R. Computation￾al coalition formation[M]. Cambridge: MIT Press, 2013: 329–380. [3] [4] OSBORNE M J, RUBINSTEIN A. A course in game the￾ory[M]. Cambridge: MIT Press, 1994. VON NEUMANN J, MORGENSTERN O. Theory of games and economic behavior[M]. Princeton: Princeton University Press, 1972. [5] WOOLDRIDGE M, BUSSMANN S, KLOSTERBERG M. Production sequencing as negotiation[C]// Proceedings of the First International Conference on the Practical Applica￾tion of Intelligent Agents and Multi-Agent Technology. London, UK, 1996: 709–726. [6] SANDHOLM T, SIKKA S, NORDEN S. Algorithms for optimizing leveled commitment contracts[C]// Proceed￾ings of the 16th International Joint Conference on Artifical Intelligence. Stockholm, Sweden, 1999: 535–540. [7] RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition structure generation: a survey[J]. Artificial intel￾ligence, 2015, 229: 139–174. [8] ZHU Han, POOR H V. Coalition games with cooperative transmission: a cure for the curse of boundary nodes in selfish packet-forwarding wireless networks[C]// Proceed￾ings of the 5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops. Limasso, Cyprus, 2009: 1–8. [9] KHAN Z, LEHTOMÄKI J, LATVA-AHO M, et al. On selfish and altruistic coalition formation in cognitive ra￾dio networks[C]//Proceedings of the 2010 Fifth Interna￾tional Conference on Cognitive Radio Oriented Wireless Networks and Communications. Cannes, France, 2010: 1–5. [10] LI Cuihong, SYCARA K, SCHELLER-WOLF A. Com￾binatorial coalition formation for multi-item group-buy￾ing with heterogeneous customers[J]. Decision support systems, 2010, 49(1): 1–13. [11] MANOOCHEHRI H E, WENKSTERN R Z. Dynamic coalition structure generation for autonomous connected vehicles[C]// Proceedings of 2017 IEEE International Conference on Agents. Beijing, China, 2017: 21–26. [12] SLESS L, HAZON N, KRAUS S, et al. Forming k coali￾tions and facilitating relationships in social networks[J]. Artificial intelligence, 2018, 259: 217–245. [13] SLESS L, HAZON N, KRAUS S, et al. Forming coali￾tions and facilitating relationships for completing tasks in social networks[C]// Proceedings of the 2014 Internation￾al Conference on Autonomous Agents and Multi-Agent Systems. Paris, France, 2014: 261–268. [14] SANDHOLM T, LARSON K, ANDERSSON M, et al. Coalition structure generation with worst case guarantees [J]. Artificial intelligence, 1999, 111(1/2): 209–238. [15] YEH D Y. A dynamic programming approach to the com￾plete set partitioning problem[J]. BIT numerical mathem￾atics, 1986, 26(4): 467–474. [16] DANG T T, FRANKOVIE B, BUDINNSKA I. Create agent’s coalition based on a dynamic programming ap- [17] 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·421·

·422· 智能系统学报 第14卷 proach[Cl//Proceedings of the 15th European Conference tationally manageable combinational auctions[J].Man- on Artificial Intelligence,Workshop "Agent Technolo- agement science,1998,448):1131-1147. gies and Logistics".Lyon,France.2002:16-24. [31]刘惊雷，童向荣，张伟.一种快速构建最优联盟结构的 [18]GRECO G,GUZZO A.Constrained coalition formation 方法.计算机工程与应用，2006,42(4)：35-37,44. on valuation structures:formal framework,applications, LIU Jinglei,TONG Xiangrong,ZHANG Wei.A kind of and islands of tractability[J].Artificial intelligence,2017. method for quick constructing optimal coalition 249:19-46. structure[J].Computer engineering and applications, [19]童向荣，张伟.动态联盟收益值的再励学习.计算机 2006,42(4:35-37,44. 工程与应用，2006.42(6)：85-87. [32]RAHWAN T.MICHALAK T P.ELKIND E,et al.Con- TONG Xiangrong,ZHANG Wei.Reinforcement learn- strained coalition formation[C]//Proceedings of the ing for the value of dynamic coalition[.Computer en- Twenty-Fifth AAAI Conference on Artificial Intelligence. gineering and application,2006,42(6):85-87. San Francisco,USA,2011:719-725. [20]DEAN T,BODDY M.An analysis of time-dependent [33]张新良，石纯一.多Agent联盟结构动态生成算法]， planning[Cl//Proceedings of the 7th National Conference 软件学报，2007,18(3574-581. on Artificial Intelligence.St.Paul,Brazil,1988:49-54. ZHANG Xinliang,SHI Chunyi.A dynamic formation al- [21]BRUALDI R A.组合数学M).冯舜玺，译.5版.北京： gorithm of multi-agent coalition structure[J].Journal of 机械工业出版社，2012：180-186. software,2007,18(3):574-581. BRUALDI R A.Introductory combinatorics[M].FENG [34]RAHWAN T.RAMCHURN S D.DANG V D.et al. Shunxi,trans.5th ed.Beijing:China Machine Press, Near-optimal anytime coalition structure generation[C]// 2012:180-186. Proceedings of the 20th International Joint Conference on [22]KARP R M.Reducibility among combinatorial Artificial Intelligence.Hyderabad,India,2007: problems[C]//Complexity of Computer Computations. 2365-2371. New York,USA,1972:85-103. [35]ALBIZURI M J.AURRECOECHEA J.ZARZUELO J [23]HASTAD J.Clique is hard to approximate withinn[]. M.Configuration values:extensions of the coalitional Acta mathematica,1999,182(1):105-142. Owen value[J].Games and economic behavior,2006. [24]SANDHOLM T.An algorithm for optimal winner de- 57(1)1-17. termination in combinatorial auction[Cl//Proceedings of [36]RAHWAN T,JENNINGS N R.Distributing coalitional the Sixteenth International joint conference on artificial value calculations among cooperative agents[C]//Pro- intelligence.Stockholm,Sweden,1999:542-547 ceedings of the 20th National Conference on Artificial In- [25]LINIAL N.Game-theoretic aspects of computing[M]// telligence.Pittsburgh,Pennsylvania,2005:152-157. AUMANN R J,HART S.Handbook of Game Theory [37]FRANKOVI B,DANG T,BUDINSKA I.Agents'coali- with Economic Applications.Amsterdam,Netherlands: tions based on a dynamic programming approach[J].Acta Elsevier,1994:1339-1395. polytechnica hungarica,2008,5(2):5-21. [26]LARSON K S.SANDHOLM T W.Anytime coalition [38]IEONG S,SHOHAM Y.Marginal contribution nets:a structure generation:an average case study[J].Journal of compact representation scheme for coalitional games[Cl// experimental theoretical artificial intelligence,2000, Proceedings of the 6th ACM Conference on Electronic 12(1:23-42. Commerce.Vancouver,BC,Canada,2005:193-202. [27刀胡山立，石纯一.一种任一时间联盟结构生成算法) 软件学报.2001.12(5)：729-734. 作者简介： HU Shanli,SHI Chunyi.An anytime coalition structure 任子仪，女，1994年生，硕士研究 generation algorithm[J].Journal of software,2001,12(5): 生，主要研究方向为联盟结构生成和 729-734. 数据挖掘。 [28]胡山立，石纯一.给定限界要求的联盟结构生成刀.计 算机学报，2001,2411)少1185-1190. HU Shanli,SHI Chunyi.Coalition structure generation with given required bound[J].Chinese journal of com- puters,,2001,24(11):1185-1190. 童向荣，男，1975年生.教授，博 [29]DANG V D,JENNINGS N R.Generating coalition struc- 士，主要研究方向为多Agent系统、分 tures with finite bound from the optimal guarantees[C]// 布式人工智能、数据挖掘。主持国家自 Proceedings of 3rd International Joint Conference on 然科学基金面上项目2项，山东省自 Autonomous Agents and Multiagent Systems.New York. 然科学基金1项。发表学术论文50余篇。 USA,2004:564-571 [30]ROTHKOPF M H,PEKEC A,HARSTAD R M.Compu-

proach[C]//Proceedings of the 15th European Conference on Artificial Intelligence, Workshop “Agent Technolo￾gies and Logistics”. Lyon, France, 2002: 16–24. GRECO G, GUZZO A. Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability[J]. Artificial intelligence, 2017, 249: 19–46. [18] 童向荣, 张伟. 动态联盟收益值的再励学习[J]. 计算机 工程与应用, 2006, 42(6): 85–87. TONG Xiangrong, ZHANG Wei. Reinforcement learn￾ing for the value of dynamic coalition[J]. Computer en￾gineering and application, 2006, 42(6): 85–87. [19] DEAN T, BODDY M. An analysis of time-dependent planning[C]// Proceedings of the 7th National Conference on Artificial Intelligence. St. Paul, Brazil, 1988: 49–54. [20] BRUALDI R A. 组合数学[M]. 冯舜玺, 译. 5 版. 北京: 机械工业出版社, 2012: 180–186. BRUALDI R A. Introductory combinatorics[M]. FENG Shunxi, trans. 5th ed. Beijing: China Machine Press, 2012: 180–186. [21] KARP R M. Reducibility among combinatorial problems[C]// Complexity of Computer Computations. New York, USA, 1972: 85–103. [22] HASTAD J. Clique is hard to approximate within n 1-ε[J]. Acta mathematica, 1999, 182(1): 105–142. [23] SANDHOLM T. An algorithm for optimal winner de￾termination in combinatorial auction[C]// Proceedings of the Sixteenth International joint conference on artificial intelligence. Stockholm, Sweden, 1999: 542–547. [24] LINIAL N. Game-theoretic aspects of computing[M]// AUMANN R J, HART S. Handbook of Game Theory with Economic Applications. Amsterdam, Netherlands: Elsevier, 1994: 1339–1395. [25] LARSON K S, SANDHOLM T W. Anytime coalition structure generation: an average case study[J]. Journal of experimental & theoretical artificial intelligence, 2000, 12(1): 23–42. [26] 胡山立, 石纯一. 一种任一时间联盟结构生成算法[J]. 软件学报, 2001, 12(5): 729–734. HU Shanli, SHI Chunyi. An anytime coalition structure generation algorithm[J]. Journal of software, 2001, 12(5): 729–734. [27] 胡山立, 石纯一. 给定限界要求的联盟结构生成[J]. 计 算机学报, 2001, 24(11): 1185–1190. HU Shanli, SHI Chunyi. Coalition structure generation with given required bound[J]. Chinese journal of com￾puters, 2001, 24(11): 1185–1190. [28] DANG V D, JENNINGS N R. Generating coalition struc￾tures with finite bound from the optimal guarantees[C]// Proceedings of 3rd International Joint Conference on Autonomous Agents and Multiagent Systems. New York, USA, 2004: 564–571. [29] [30] ROTHKOPF M H, PEKEČ A, HARSTAD R M. Compu￾tationally manageable combinational auctions[J]. Man￾agement science, 1998, 44(8): 1131–1147. 刘惊雷, 童向荣, 张伟. 一种快速构建最优联盟结构的 方法[J]. 计算机工程与应用, 2006, 42(4): 35–37, 44. LIU Jinglei, TONG Xiangrong, ZHANG Wei. A kind of method for quick constructing optimal coalition structure[J]. Computer engineering and applications, 2006, 42(4): 35–37, 44. [31] RAHWAN T, MICHALAK T P, ELKIND E, et al. Con￾strained coalition formation[C]//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, USA, 2011: 719–725. [32] 张新良, 石纯一. 多 Agent 联盟结构动态生成算法[J]. 软件学报, 2007, 18(3): 574–581. ZHANG Xinliang, SHI Chunyi. A dynamic formation al￾gorithm of multi-agent coalition structure[J]. Journal of software, 2007, 18(3): 574–581. [33] RAHWAN T, RAMCHURN S D, DANG V D, et al. Near-optimal anytime coalition structure generation[C]// Proceedings of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India, 2007: 2365–2371. [34] ALBIZURI M J, AURRECOECHEA J, ZARZUELO J M. Configuration values: extensions of the coalitional Owen value[J]. Games and economic behavior, 2006, 57(1): 1–17. [35] RAHWAN T, JENNINGS N R. Distributing coalitional value calculations among cooperative agents[C]// Pro￾ceedings of the 20th National Conference on Artificial In￾telligence. Pittsburgh, Pennsylvania, 2005: 152–157. [36] FRANKOVI B, DANG T, BUDINSKÁ I. Agents’ coali￾tions based on a dynamic programming approach[J]. Acta polytechnica hungarica, 2008, 5(2): 5–21. [37] IEONG S, SHOHAM Y. Marginal contribution nets: a compact representation scheme for coalitional games[C]// Proceedings of the 6th ACM Conference on Electronic Commerce. Vancouver, BC, Canada, 2005: 193–202. [38] 作者简介： 任子仪，女，1994 年生，硕士研究 生，主要研究方向为联盟结构生成和 数据挖掘。 童向荣，男，1975 年生，教授，博 士，主要研究方向为多 Agent 系统、分 布式人工智能、数据挖掘。主持国家自 然科学基金面上项目 2 项，山东省自 然科学基金1项。发表学术论文50余篇。 ·422· 智 能 系 统 学 报 第 14 卷