·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 卷