Some Algorithic Results On Solutions Of Flow Games

The central problem in cooperative game theory is how to distribute the total cost or profit generated by a group in cooperation to its members fairly and rationally. There are several solution concepts with respect to different rationalities, such as the core, the nucleolus, the stable set, the kernel and Shapley value, etc. The definitions of game solutions are usually very complexity, and their computations are in general difficult. Algorithm design is an interesting topic in combinatorial cooperative games. Flow game arises from the profit distribution problem related to the maximum network flow, it is a kind of classical cooperative game model. The study of the algorithmic issues on the solutions concepts is very important both in theory and applications.In this thesis, we mainly discuss the algorithmic issues on the core and relative N-nucleolus of flow games. The main results are as follows:(1) We discuss the core of simple flow games with public arcs. We first give a characterization of the core allocations, and then estabilish a new proof for the nonemptyness condition of the core making use of linear programming model and dual theory. Based on these results, we show that the questiongs related to the core (testing core non-emptyness, checking membership of the core, finding a core member) are all polynomial time solvable, and apply the results of flow games to some other game models.(2) We focus on the relative nucleolus of the simple flow game without public arcs, and estabilish an efficient characterization of relative Nucleolus. We first show that the relative Nucleolus coincides with the core. which is not a single element, when the value of the maximum flow in the network is 1. And on the other hand, we prove that when the value of maixmum flow is greater than 1, the relative nucleolus coincides with the original nucleolus. The main techniques in our proofs are Kopelowitz's sequential linear programming method and linear programming duality theorem. These results yield that the relative nucleolus of a simple flow game can be computed in polynomial time.