Researches On Coalition Structure Generation In Trust Network

Coalition formation is an important research topic in Multi-Agent Systems.It is known that combining several agents together can achieve the goals or the better effects that can not achieve alone.The key challenge is coalition structure generation,which aims to find the optimal coalition structure to maximize individual effects and coalition benefits.It is difficult to find the optimal coalition structure.On the one hand,most coalition formation models assume that any agents can form coalition.This assumption is too broad.There are various constraints in the formation of coalitions in real life,even if constraints are added,the complexity of the problem is still high.A new and fast algorithm is needed to solve large-scale practical problems.On the other hand,agents are supposed to be formed any number of coalitions.However,the number of coalitions should be limited in many practical situations.For example,agents may need to cooperate to complete all tasks in the field of task assignment.For the limited resources or capabilities of a single agent,it is necessary to assign tasks to coalitions.The number of coalitions must be consistent with the number of tasks to avoid wasting resources or failing to complete tasks.In response to the above problems,two common assumptions in the formation of coalitions are constrained.Specific work as follows:1)In real life,the relationship between agents is represented by graph.Each node represents an agent,and an edge represents the relationship between agents.It is called Graph Consortium Structure Generation(GCSG)problem.Inspired by the Monte-Carlo tree search technology,a scalable anytime coalition formation method is proposed to solve largescale GCSG problems.If time is limited,the algorithm can immediately return current best solution,and if there is sufficient time,the algorithm can converge to the best solution.2)In the context of task assignment,the number of coalitions formed is constrained to k,and there is a trust utility constraint between agents that form the coalition.The Edge Contraction Coalition Formation(ECCF)algorithm with trust utility relationship is proposed,which simulates the formation process of the coalition between agents through continuous edge contraction.Finally,simulation experiments demonstrate the effectiveness of the two algorithms.