Research On Computational Complexity And Related Algorithms In Cooperative Games Of Multiagent System

Game theory is widely applied in the field of multi-agent system of which Coalition formation is an important branch. One of important problems in coalition formation is to divide the value into agents among coalitions. Fortunately, solution concepts in game theory is an efficient approach to solve this problem. Therefore, the computa-tional complexity of some solution concepts has been studied in this paper. On the other hand, the coalition structure generation is also an important issue in coalition formation. In the traditional setting, overlapping coalition is not allowed, so this paper also investigates the complexity and algorithms aspects of coalition structure genera-tion in the overlapping setting. In summary, the main contribution of this thesis can be summarized as follows:1) we thoroughly studied the issues of computational complexity about four solu-tion concepts, the undominated core, the farsighted core, the (vN-M) farsighted stable set and the largest consistent set. In the literature, there are two kinds of cores, the undominated core and the excess core. We showed that these two different cores are not equal in the general setting. Moreover, in the computer science literature, the computational complexity results are mainly about the ex-cess core. So, we fill in the blank of the undominated core. However, the empti-ness problem of undominated core for general games is unsolved. In the second, we focused on the latter three solution concepts into which farsightedness is in-corporated. Although farsighted core is most likely empty, its membership and emptiness problems are hard to decide. For the farsighted stable set, its member-ship problem is even beyond NP. Finally, we found that the membership problem of the largest consistent set may be undecidable. Table1presented the summary of results in this paper.2) we systematically prove some computational complexity results for Overlapping Coalition Formation(OCF) games and Threshold Task Games(TTGs). To our surprise, even the general coaltion structure generation problem for OCF-games is NP-hard, a specific case is indeed in P. And its optimization version also have a polynomial time algorithms which is based on linear programming(LP). In the next, we give a pseudopolynomial time algorithm for TTGs and prove the correctness and time complexity of our algorithms. For its extensions-bounded TTGs and unbounded TTGs, we introduce a binary coding method to transform these extensions into the ordinary case.