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

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