Multi-Agent System For Game Coalition Formation And Distribution Research Questions

Multi-Agent System (MAS) has become one of two important research branches in the field of Distributed Artificial Intelligence (DAI). The MAS theory has broken a new path for solving some core problems of many application fields, such as Intelligent Robot System, Cloud Computing System, Search Engine, Intelligent Transportation System, Network Comminication, etc., and it further improves to develop some more complex systems of these fields. In the research field of MAS, the effective cooperation and utility allocation for many agents in MAS is one of the key issues. The method to research this key issue based on the theory of Cooperative Games has brought abundant achievements, and the Cooperative Games based method has been extensive agreed in MAS. However, due to the complexity of MAS and many obstacles from the theory to the applicaitons for Cooperative Games, there still exist many challenging problems for solving the effective cooperation and utility allocation of MAS based on Cooperative Games. Aiming to these challenging problems, this dissertation thoroughly researches the effective cooperation and utility allocation of MAS, which has certain theoretical significance. The detail works about this dissertation are as follows.(1) Based on the principle of fair allocation, using the fair characteristic of Shapley value in Cooperative Games, this dissertation researches the effective cooperation and utility allocation of MAS. Firstly, a fast algorithm about forming a static initial coalition is improved. Secondly, a fast algorithm about dynamically updating the currrent coalition state is proposed, with the dynamic changes of the agent members and the tasks in MAS. Thirdly, a fast algorithm about solving the approximate Shapley value of an agent member, aiming to the bad efficiency obtaining the Shapley value based on its definition. Finally, the experimental results show that three proposed algorithms achieve the expected coalition and allocation, and that they have lower computing complexities.(2) Based on the principle of stable allocation, using the stable characteristic of bargaining set in Cooperative Games, this dissertation researches the effective cooperation and utility allocation of MAS. Firstly, the concept of concise coalition set is proposed, which can be obtained by deleting some bargaining inessential coalitions. Secondly, an algorithm solving the stable allocation vector of a certain coalition structure based on generic algorithm with the concise coalition set. And the proving showes that the bargaining set based on the concise coalition set is same as the classical bargaining set. Thirdly, an algorithm finding the stablest coalition structure is further proposed based on the method of comparing lexicographically orderings. Finally, the experimental results show that three proposed algorithms achieve the expected success rates, and that they have lower computing complexities.(3) Aiming to the shortcomings of the stable allocation theory in Multi-choice Games, this dissertation extend some stable allocation solutions in classical Cooperative Games to those in Multi-choice Games, and these solutions include Bargaining Set, Kernal and Nucleolus. Then the correlative provings show the existence of Bargaining Set, the existence and uniqueness of Nucleolus, and the relationships among Bargaining Set, Kernal and Nucleolus. In virtue of these extended stable allocation solutions, this dissertation further proposed several methods about solving the stable allocation vector in multi-level agent composing complex MAS, and it also show an algorithm solving the stable allocation vector for each level of every agent in the complex MAS based on Generic Algorithm.