约束条件下联盟生成研究进展

联盟生成是在多 Agent系统的研究中最为重要的挑战之一。如何对 Agent进行划分使所得社会福利最大化是当前面临的主要问题。假设每个 Agent都具有理性和自利性的特性,为了追求自身的利益最大化而选择和其他的 Agent进行联合,进而使整个系统实现利益的最大化。目前,联盟生成问题有很大的计算挑战,即使在进行联盟的时候添加了约束条件,也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下的联盟生成的研究进行综述,主要包括 4部分:最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、联盟生成求近似最优解和约束条件下联盟生成求最优解。

Research progress of constrained coalition formation

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.