The F-nucleolus Of Cooperative 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 and Shapley value. The nucleolus is an important solution which always exists and consists of a unique allocation. From the existence and uniqueness point of view, nucleolus is better than the core. Wallmeier(1983) introduced the definition of weighted nucleolus in some practical cases, which is also called f-nucleolus. Because of the complexity of the definition of the f-nucleolus, its computation is in general very difficult. This thesis focuses on the f-nucleolus of two combinatorial cooperative game models: the maximum weight cooperative game and the flow game. Based on duality theory of linear programming, polyhedron theory and graph theory, this thesis discusses the algorithmic issues on two specific classes of f-nucleolus: per-capita nucleolus and nucleon for maximum weight cooperative games and nucleon for simple flow games. The main results are as follows:The existence and uniqueness of f-nucleolus are proved when every proper subgroup S satisfies f_S>0 . Kopelowitz'sequential linear programs approach is also applied to the computation of the f-nucleolus, especially for per-capita nucleolus and nucleon. Furthermore, an example is given to illustrate the nucleon may not be a singleton, when the cost of some proper subgroups are zero.For the maximum weight cooperative games, formulations of computing the per-capita nucleolus and nucleon are given, which implies that these two kinds of weighted nucleolus can be computed in polynomial time.For the simple flow games, making use of the techniques of dual linear programming and the ellipsoid algorithm for computing the nucleolus, this thesis gives a set of"critical"coalitions to characterize the nucleon and proves that the nucleon is the same as the nucleolus. Thus, it is shown that the nucleon of a simple flow game can be computed in polynomial time.