Abstract: Aiming at the problem that Overlapping Coalition Structure Generation (OCSG) in the Framework of cooperative games with Overlapping Coalitions (OCF games) is difficult to solve, an effective algorithm based on greedy method was proposed. First, the OCF games with number of coalition k constraints (kOCF games) was used to limit the scale of the OCSG problem. Then, a similarity measure was introduced to represent the similarity between any two coalition structures, and the property of monotonicity was defined based on the similarity measure, which means that the higher the similarity between a coalition structure and optimal coalition structure, the greater the monotonicity value of this coalition. Finally, for the kOCF games with monotonicity, the method of inserting player numbers one by one to approximate the optimal coalition structure was used to design the Coalition Constraints Greed (CCG) algorithm to solve the given OCSG problem, and the complexity of CCG algorithm was proved to be O(n2^k+1) theoretically. The influences of different parameters and coalition value distribution on the performance of the proposed algorithm were analyzed and verified through experiments, and this algorithm was compared with the algorithm proposed by Zick et al. (ZICK Y, CHALKIADAKIS G, ELKIND E, et al. Cooperative games with overlapping coalitions:charting the tractability frontier. Artificial Intelligence, 2019, 271:74-97) in the terms such as constraint condition. The results show that when the maximum number of coalitions k is constrained by a constant, the search times of the proposed algorithm increase linearly with the number of agents. It can be seen that CCG algorithm is tractable with the fixed-parameter k and has better applicability.

Key words: Overlapping Coalition Structure Generation (OCSG), optimal coalition structure, coalition quantity constraint, monotonicity, fixed-parameter tractable

摘要： 针对重叠联盟的合作博弈框架（OCF games）中重叠联盟结构生成（OCSG）求解困难的问题，提出了一种基于贪心方法的有效算法。首先使用了一种带有联盟数量k约束的OCF博弈（kOCF games）模型来限制OCSG问题的规模；然后引入了一种相似度量来表示任意两个联盟结构之间的相似程度，并基于相似度量定义了单调性的性质，这意味着某一联盟结构与最优联盟结构的相似度越高，该联盟的单调性的值就越大；最后对于具有单调性质的kOCF博弈，采用了逐一插入玩家编号以逼近最优联盟结构的方法设计了联盟约束贪心（CCG）算法来求解给定的OCSG问题，并在理论上证明了CCG算法的复杂度是O（n2^k+1）。通过实验分析和验证了不同参数和联盟值分布对所提算法性能的影响，并把该算法与Zick等提出的算法（ZICK Y，CHALKIADAKIS G，ELKIND E，et al. Cooperative games with overlapping coalitions： charting the tractability frontier. Artificial Intelligence，2019，271：74-97）在约束条件等方面进行了对比，得出了当联盟最大数量k被常数约束时所提算法的搜索次数随agent的个数基本呈线性增长的结果。可见CCG算法是固定参数k可解的，而且拥有更好的适用性。

关键词: 重叠联盟结构生成, 最优联盟结构, 联盟数量约束, 单调性, 固定参数可解