Matrix Approach To Imputation Of Cooperative Games

Cooperative game is a game that all players participate in a cooperative way.In cooperative games,without damaging the payoff of others,at least one player's payoff will increase,thus the payoff of the whole society will increase.Cooperative game theory provides an analytical tool for investigating the behavior of players.How to distribute the payoff reasonably among the players is the central issue to be studied in cooperative games.The target problem in cooperative games is to find a reasonable imputation which makes each player gets their respective income.Shapley value and Banzhaf value in the imputation problem are important solution concepts in cooperative games.This paper mainly investigates the calculations of Shapley value and Banzhaf value for cooperative games based on the matrix approach,and establishes new formulas via carrier.This paper aims to simplify the calculations of Shapley value and Banzhaf value for cooperative games,and provides some new results about the relationship between carrier and imputations.Firstly,a necessary and sufficient condition is presented for the verification of carrier,based on which an algorithm is worked out to find the unique minimum carrier.Secondly,by virtue of the property of minimum carrier,it is proved that the imputation of players which do not belong to minimum carrier,called dummy players,is zero.And the imputation of players in minimum carrier is only determined by the minimum carrier.Then,a new formula of Shapley value is presented,which greatly reduces the computational complexity of the original formula,and shows that the Shapley value only depends on the minimum carrier.Based on the semi-tensor product of matrices,the obtained new formula is converted into an equivalent algebraic form,which makes the new formula convenient to use via MATLAB.By the minimum carrier and the semi-tensor product of matrices,a new calculation method of Banzhaf value is proposed,which reduces the computational complexity of Banzhaf value.The obtained results are applied to biological networks,and the Banzhaf value is used to determine the genes which are highly associated with genetic diseases.Finally,the application of several imputation problems about costallocation and voting in cooperative games is studied.