| The coalition formation is one of the most important challenges in the research of Multi-Agent Systems.How to divide the Agent to maximize the social welfare is the main problem.Assume that each Agent has rationality and self-interest.In order to maximize its own utility,it chooses to associate with other Agents,so as to maximize the social welfare of the entire system.At present,the coalition structure generation problem has great computational challenges.Even if constraints are added,new algorithms need to solve this problem faster and more efficiently.The theoretical model of cooperative game is the basis of the study of coalition formation.The typical transferable utility game model based on the form of characteristic function.It does not consider the possibility of forming coalition between Agents,nor does it consider the ways in which agents work together.This problem will put some restrictions on the practicality of models and technologies.Meanwhile,most cooperative game models assume that any Agent can form a coalition,and a set of Agent can form any number of coalitions.This assumption is too broad and there are some specific constraints in real life.In view of the above problems,two common assumptions in the process of forming a coalition are restricted.One restriction is that the number of formed coalitions is restricted to k.Moreover,there are certain trust utility constraints between the Agents.It’s proposed that coalition of trust utility relationships are formed.That is,Agents with higher trust utility relationships are allowed to form coalitions.If agents do not have the trust utility relationship,the connection would be established through the transfer between members.Under the premise of ensuring the agent’s individual rationality and the absence of blocks in the coalition,referring to the image processing s-t-cut algorithm,two polynomial-time coalition structure generation algorithms MT-s-t-cut and MTU-s-t-cut are proposed to find the optimal coalition structure under the set case.Finally,simulation experiments verify that trust can affect the formation of the coalition structure.It also demonstrates social welfare increases with the number of agents,and the proposed algorithm is much more efficient than the DP and ODP-IP algorithms. |
