Algorithmic Research On Two Combinatorial Cooperative Games

Cooperative games provide a framework for fair and stable profit allocation in multi-agent systems. Core, least-core and nucleolus are such solution concepts that characterize stability of cooperation. In this paper, we study the algorithmic issues on the solution concepts of threshold cardinality matching games (TCMG) and path cooperative games (PC-games).A TCMG is defined on a graph G=(V, E), where V is the set of vertices, E is the set of edges, and each player controls a vertex in V. Given a threshold T, the profit v(S) of a coalition S C V is 1 if the size of a maximum matching in G[S] meets or exceeds T, and 0 otherwise.In chapter 2, we first introduce the definition of matching games and threshold matching games, where we point out that the later one is a variation of the former one. When the threshold matching game is defined on a weighted graph, it is NP-hard to compute the least-core and the nucleolus. So we focus on the case that the game is defined on a simple graph——threshold cardinality matching games. When the core is nonempty, we can obtain the core and the nucleolus efficiently. However, when the core is empty, the problem becomes more complicated.In chapter 3, we first prove that the problems of computing least-core value, finding and verifying least-core payoff are all polynomial-time solvable due to the separation oracle technique. We also provide a general characterization of the least-core for a large class of TCMG, which will be crucial in the later analysis. Next, based on Gallai-Edmonds Decomposition in matching theory, we establish a concise formulation of the nucleolus for three typical cases of TCMG:edge coalition games, threshold cardinality matching games defined on a graph which contains a perfect matching and threshold assignment games.The path cooperative game is defined on a simple network D = (V, E;s, t), where V is the vertex set, E is the arc set, s and t are respectively the source and the sink of the network. The player can either control an edge or a vertex, which are called edge path cooperative games and vertex path cooperative games respectively. In these games, a coalition of edges or vertices is successful if it can enable an s-t path and lose otherwise.Chapter 4 is dedicated to introduce the path cooperative games (PC-games). Firstly, we show that when the core of PC-games is nonempty, the one imputation in the core and the nucleolus can be found easily. Moreover, the CS-core of PC-games is always nonempty since the superadditive cover of PC-games is flow games.In chapter 5, we focus on the computation of the least-core and the nucleolus of PC-games when its core in empty. Due to the dual theorem and the relationship between PC-games and flow games, we can show the both the least-core and the nucleolus of PC-games can be computed in polynomial time. Finally, we generalize the result of PC-games defined on the directed graphs to undirected cases.