Core Stability Of Combinatorial Cooperative Games

Cooperative game theory considers how to distribute the total income (cost)generated by a group to its members fairly and rationally. There are severalsolution concepts with respect to different rationalities, such as the core, thestable set, etc. The characterization of a game with stable core is known as oneof the most notorious problems in cooperative game theory. This thesis focuseson a class of cooperative games arising from packing and covering optimizationproblems. The main feature of this class of combinatorial cooperative games isthat the characteristic function value is determined by the related combinatorialoptimization problem and there is strong connection between the structure ofthe optimization problem and game solutions. Based on duality theory of linearprogramming, polyhedron theory and graph theory, this thesis discusses the corestability and related algorithmic issues for matching games and vertex covergames. The main results are as follows:●Sufficient and necessary conditions and the corresponding polynomial al-gorithm for core stability of matching games and vertex cover games.●For matching games and vertex cover games defined on bipartite graphs,the core largeness, the extendability and the exactness of the games are equivalentconditions, which strictly imply the stability of the core.●Extended results on other packing and covering games, such as indepen-dent set games, set cover games and so on.