Simplification of Shapley value for cooperative games via minimum carrier
- PDF / 2,036,647 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 97 Downloads / 166 Views
RESEARCH ARTICLE
Simplification of Shapley value for cooperative games via minimum carrier Haitao Li1 · Shuling Wang1 · Aixin Liu1 · Meixia Xia1 Received: 21 April 2020 / Revised: 27 June 2020 / Accepted: 14 August 2020 © South China University of Technology, Academy of Mathematics and Systems Science, CAS and Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Shapley value is one of the most fundamental concepts in cooperative games. This paper investigates the calculation of the Shapley value for cooperative games and establishes a new formula via carrier. 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 properties of minimum carrier, it is proved that the profit allocated to dummy players (players which do not belong to the minimum carrier) is zero, and the profit allocated to players in minimum carrier is only determined by the minimum carrier. Then, a new formula of the 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. Finally, based on the semi-tensor product (STP) of matrices, the obtained new formula is converted into an equivalent algebraic form, which makes the new formula convenient for calculation via MATLAB. Keywords Shapley value · Cooperative game · Carrier · Algebraic form · Semi-tensor product of matrices
1 Introduction Since von Neumann and Morgenstern’s pioneering work “Theory of Games and Economic Behavior” [1], the study of game theory has significantly promoted the development of many disciplines ranging from economics, engineering, and philosophy to political science, or even psychology [2, 3]. Roughly speaking, there are mainly two branches of game theory: noncooperative game [4] and cooperative game [5]. During the interactions among competing players, each player chooses its strategy independently to improve its own utility. Noncooperative game theory investigates the choice of strategies resulting from this process. In noncooperative game theory, Nash equilibrium, initiated by J. Nash [6], plays a central role in the choice of strategies. On the contrary, cooperative game theory provides analytical tools for the investigation of cooperative players’ behaviors. The main branch of cooperative games characterizes the construction of cooperating groups of players, called * Haitao Li [email protected] 1
School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, Shandong, China
coalition [7]. Through coalition, each player’s position can be strengthened in cooperative games. In a cooperative game (N, v) with |N| = n , an n-dimensional vector satisfying individual rationality and group rationality is called imputation [8], which is a fundamental concept in the study of cooperative games. The optimal imputation of (N, v) is commonly referred to as the solution to (N, v). Unfortuna
Data Loading...
