Questions Of Cooperative Game Based On Minimum Cost Spanning Tree

For its special research field and various research approaches, game theory has many relations with other mathematical branches. During the last ten years, the relations between game theory and combinatorial optimization theory have become close. They provide methods for each other and develop further together. This paper applies theory of minimum cost spanning game to solve some game problems, and makes relations between these two mathematical branches more close. The main contributions can be summarized as follows:1. The player number varying payment game. Before and after the player number changes, the corresponding case of the imputation, core, nucleolus, Shapley value of the cooperative game are given respectively.2. The player number decreasing minimum cost spanning tree game. The minimum cost spanning tree game algorithm of the vertexes decreased is given, and the minimum cost spanning tree game core is obtained when the coalition K is out. When the coalition K is retrievable, as the imputation can not get a minimums payment result, a more fairly, more reasonable imputation is given, which can stabilize the coalition and minimize the collectivity payment. In the condition of player number increasing, the various conditions of the minimum cost spanning tree game is discussed when the vertexes and their edges are increased, and the minimum cost spanning tree game core is obtained when the player set K? joins in.3. The minimum cost k-degree constrained spanning tree game. The concrate form and complexity estimation of the feasible exchange is given when the source degree more than k or less than k, then the Glover-Klingman algorithm is improved and the complexity estimation of the improved algorithm is presented. Two rules based on threat theory and side-payment theory are established, and the characteristic functions are given, at last, the imputation in the core is obtained based on that the two characteristic functions is strategic equivalence with the characteristic function of minimum cost spanning tree game. That the core is nonempty about the minimum cost k-degree constrained spanning tree game is proved under the two rules.4. The weighted shortest path arborescence game. The models of shortest path arborescence game and weighted shortest path arborescence game are established and the imputations of this cooperative game in many cases are obtained.The last three questions of cooperative games arise from the minimum cost spanning tree game of payment game.