Journal of Frontiers of Computer Science and Technology ›› 2018, Vol. 12 ›› Issue (5): 804-819.DOI: 10.3778/j.issn.1673-9418.1705025

Previous Articles     Next Articles

Algorithm of Finding Core of Graphical Coalitional Structure

SHANG Chuanqi, LIU Jinglei+   

  1. School of Computer and Control Engineering, Yantai University, Yantai, Shandong 264005, China
  • Online:2018-05-01 Published:2018-05-07

图联盟结构核的求解算法

尚传启刘惊雷+   

  1. 烟台大学 计算机与控制工程学院,山东 烟台 264005

Abstract: The research of coalitional structure core is an important part in the field of artificial intelligence. Especially, the research of generating the coalitional structure and its distribution that can meet the core requirement is the present primary mission. Traditional algorithms use different methods to create the coalitions, but they still have some shortcomings, for example, assuming that all coalitions can be generated and satisfy the super-additivity, ignoring the restriction of external environment on the formation of coalition. The constraint graph is used as the constraint condition of the coalition generation, the distribution according to work is taken as the initial allocation scheme, and the bargaining set and the stable cost are taken as the allocation adjustment scheme, this paper designs the SCP (stable core programming) algorithm to generate the core of coalitional structure. As an algorithm to solve the stable situation of coalitions and the core of coalitional game, it can meet the best interest expectations of all agents in coalitions and guarantees the stability of coalitional structure.

Key words: graphical coalitional game, core of graphical coalitional structure, distribution according to one??s work, bargaining set, stable cost

摘要: 联盟结构核是人工智能领域中的一个重要研究内容,特别是生成满足核要求的联盟结构及其分配, 是当前主要的研究任务。传统算法存在一些缺陷,比如假定所有联盟可生成且联盟利益满足超加性,忽视外部环境对生成联盟的限制作用。采用约束图作为联盟生成的约束条件,按劳分配作为初始分配方案,谈判集、稳定成本作为分配调整方案,设计SCP(stable core programming)算法生成联盟结构核,使得生成的联盟结构核可以满足所有处于联盟状态Agent的最大利益期望,保证联盟结构的稳定性。

关键词: 图联盟博弈, 联盟结构核, 按劳分配, 谈判集, 稳定成本