Simplif ication of Shapley value for cooperative games via minimum carrier

Haitao Li · Shuling Wang · Aixin Liu · Meixia Xia

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 suffi cient condition is presented for the verif ication of carrier, based on which an algorithm is worked out to f ind the unique minimum carrier.Secondly, by virtue of the properties of minimum carrier, it is proved that the prof it allocated to dummy players (players which do not belong to the minimum carrier) is zero, and the prof it 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 signif icantly 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 coalition [ 7]. Through coalition, each player’s position can be strengthened in cooperative games.

In a cooperative game (N,v) with |N|=n, ann-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). Unfortunately, unlike Nash equilibrium,which is widely accepted as a solution to noncooperative games, there is still no universal “best imputation” in all situations. In the past few decades, the imputation of cooperative games has been well studied by many scientists,and many excellent results have been obtained [ 9- 11].Gillies [ 9] presented the def inition of core based on the concept of superiority. Core is a very reasonable solution to cooperative games because it consists of all imputations that make the total cooperation stable. However, the core of a cooperative game may be an empty set, which leads to the breakdown of the total cooperation. Nucleolus, which is included in the core, is another solution to cooperative games proposed by Schmeidler [ 10]. Nucleolus is made up of a unique imputation, and improves the defect that the core of a cooperative game may not exist. However,the calculation of nucleolus is too complicated to achieve when |N| is slightly large. Starting from three axioms,that is, effi ciency axiom, symmetry axiom and additivity axiom, the Shapley value was proposed by L. S. Shapley,the winner of 2012 Nobel prize in economics [ 11 ]. Since the Shapley value is the only imputation satisfying three axioms, it has been widely used and plays an important role in cooperative games.

The existing works on the Shapley value are mainly based on the original formula given in [ 11] (see ( 9) below).It should be pointed out that the original formula of Shapley value relies on all the subsets ofN, which implies that the computational complexity of the original formula for cooperative game (N,v) is O(2|N|) . Therefore, the computing load is heavy when dealing with a large-scale cooperative game.Recently, Cheng and Xu [ 12] have introduced the semitensor product (STP) method to the calculation of Shapley value. Using STP, the characteristic function of a cooperative game is converted into a pseudo-Boolean function and its algebraic form [ 13- 15]. Based on the algebraic form, the original formula of Shapley value is converted into a simple matrix form [ 12], which makes the Shapley value easy to calculate via MATLAB. However, the computational complexity of the matrix form is still O(2|N|) . Hence, it is necessary to establish a new formula for Shapley value, which has lower computational complexity than the original one. It is noted that the effi ciency axiom of the Shapley value shows that every player which is not in a carrier does not make any contribution to its coalition. This motivates us to simplify the original formula of the Shapley value by using the minimum carrier, which is the carrier with minimum cardinality.

In this paper, we aim to simplify the calculation of Shapley value for cooperative games, and present some new results on the relation between carrier and Shapley value.The main contributions of this paper are as follows:

1) The definition of minimum carrier of cooperative games is introduced in this paper. Based on the properties of minimum carrier, a new formula of the Shapley value is obtained. The new formula reveals that the prof it allocated to dummy players is zero, and the Shapley value is only determined by the players in the minimum carrier.

2) Based on STP, the obtained new formula of Shapley value is converted into an equivalent algebraic form, which makes it easier to calculate the new formula via MATLAB.The obtained algebraic form can greatly reduce the computational complexity of the original algebraic form obtained in [ 12] (see Remark 5 below).

The remainder of this paper is organized as follows. Section 2 recalls some necessary preliminaries on cooperative games and presents some important properties of carrier and minimum carrier. In Section 3, a new formula of the Shapley value is obtained based on the minimum carrier, and then the obtained new formula is converted into an equivalent algebraic form via STP. Section 4 presents an illustrative example to show the novelty of the new formula for Shapley value, which is followed by the conclusion in Section 5.

2 Carrier of cooperative games

In this section, we present some important properties of carrier for cooperative games, which is essential to establish the new formula of Shapley value.

2.1 Cooperative games

In this part, we recall some necessary preliminaries on cooperative games [ 5].

Def inition 1 A cooperative game, denoted by (N,v), consists of two factors:

1) a f inite set of playersN={1,2,…,n} ; 2) a characteristic functionv∶2N→? withv(?)=0 . More precisely, letH∈2Nbe a coalition, and thenv(H) represents the payoff ofHunder cooperative game (N,v).

A cooperative game (N,v) is said to satisfy super-additivity,if

holds for anyA,B∈2NwithA∩B=? . Super-additivity is a necessary condition for coalitionsAandBto form a new coalition.

Consider a cooperative game (N,v) withN={1,2, …,n} .Assume that (N,v) satisf ies super-additivity. Naturally, we have

A cooperative game (N,v) is called an essential cooperative game, if the characteristic function of (N,v) satisf ies

The following example illustrates cooperative game, superadditivity and essential cooperative game.Example 1Consider the trading horse problem (THP).Player 1 has a horse with value of 100 dollars. Player 2 is willing to spend up to 200 dollars to buy this horse, and player 3 is willing to spend up to 210 dollars to buy this horse. If player 1 sells the horse to player 2 at the price ofadollars ( 100＜a≤200 ), then the payoff s of players 1 and 2 receiving from this trade area-100 dollars and 200-adollars, respectively, that is, the payoff of coalition {1,2} isv({1,2})=100 . Similarly, one can obtain that the payoffof coalition {1,3} isv({1,3})=110 . For coalition {1,2,3} ,player 1 is willing to trade with player 3, which means thatv({1,2,3})=110 . In addition, it is easy to see that the payoff of coalition {1} is 100 dollars, and the payoff s of coalition{2} , {3} and {2,3} are 0 dollars. To sum up, we can obtain Table 1, which is the characteristic function of THP.

According to Table 1, it is easy to check that THP satisf ies super-additivity. In addition, one can see that THP is an essential cooperative game.

2.2 Carrier

This part presents the def inition and some properties of carrier. For details, please refer to [ 8]. The effi ciency axiom of the Shapley value shows that every player which is not in a carrier does not make any contribution to its coalition. Precisely, we have the following concept.

Definition 2 Consider cooperative game (N,v) and letT∈2N. Then,Tis said to be a carrier of (N,v), if

Remark 2IfTis a carrier of essential cooperative game(N,v), thenT≠? . In fact, ifT=? , then by Def inition 2, it is easy to obtain thatv≡0 , which contradicts with Remark 1.

The following results are immediately obtained from Def inition 2.

Proposition 1Consider cooperative game(N,v).

1)N is a carrier of(N,v).

2)If T is a carrier of(N,v),then v(T)=v(N).

Proof

1) For anyH∈2N, it is clear thatH∩N=H, which means thatv(H)=v(H∩N) . Then,Nis a carrier of (N,v).

2) Assume thatTis a carrier of (N,v). Then,v(N)=v(N∩T)=v(T) . This completes the proof.

?

The carrier of cooperative games has the following properties.

Proposition 2Consider cooperative game(N,v)and assume that T is a carrier of(N,v).

Table 1 Characteristic function of THP

1)If T ?W?N,then W is also a carrier of(N,v).

2)If i?T,then v(H∪{i})=v(H)holds for any H∈2N,where i is called a dummy player of(N,v).

Proof

1) For anyH∈2N, we havev(H∩W)=v[(H∩W)∩T]=v(H∩T)=v(H) , which means thatWis a carrier of(N,v).

2) Ifi?T, then for anyH∈2N, it is easy to see thatv(H∪{i})=v[(H∪{i})∩T]=v(H∩T)=v(H) .

?

Example 2Recall Example 1. It is easy to see from Proposition 1 that coalitionN={1,2,3} is a carrier of THP. In addition, inspired by Proposition 1, the payoff s of candidate carriers must be equal to that of coalitionN. Thus, we only need to check whether or not coalition {1,3} is a carrier of THP. A simple calculation shows thatv(H)=v(H∩{1,3})holds for anyH∈2N. Therefore, coalition {1,3} is also a carrier of THP. To sum up, THP has two carriers, that is,coalitionNand coalition {1,3} , and player 2 is a dummy player.

Next, we present an equivalent condition for the verif ication of the carrier. To this end, we convert the characteristic function into an equivalent algebraic form based on STP.

Lemma 1Let g∶Dn→?be a pseudo-Boolean function.Then, there exists a unique vector Mg∈?1×2n,called the structural matrix of g,such that

whereBlki(Mv(T))∈?1×2n-l,i=1,2,…,2l. Then, we have the following result on the verif ication of carrier.

Theorem 1Consider cooperative game(N,v).Given a nonempty coalition T={α1,…,αl}.T is a carrier of(N,v),if and only if for any i=1,2,…,2l,there exists βi∈?such that

Example 3Recall Example 1. First, we calculate the structural matrix ofv. To this end, we

Secondly, we f ind all the carriers of THP based on Theorem 1. By a simple calculation, one can obtain that

Therefore, by Theorem 1, THP has two carriers as coalitionNand coalition { 1,3} , which coincides with the conclusion drawn from Example 2.

2.3 Minimum carrier

In this part, we investigate the minimum carrier of cooperative games. To begin with, we give the def inition of minimum carrier.

Consider cooperative game (N,v). By Proposition 1,Nis a carrier of (N,v), that is, there exists at least one carrier for(N,v). In addition, by Remark 2, ? is not a carrier of (N,v).

The minimum carrier of cooperative games has the following property.

Proposition 3The minimum carrier of essential cooperative game(N,v)is unique.

that is,v≡0 , which is a contradiction to Remark 1.

Next, based on Proposition 1, Theorem 1 and Proposition 3, we present an algorithm to obtain the minimum carrier of an essential cooperative game. In the sequel, we denote the minimum carrier of an essential cooperative game byTmin.

Algorithm 1 The following steps are used to obtain the minimum carrierTminof essential cooperative game (N,v):

Step 1 Collect all candidate carriers as

Step 2 Construct an ordered set ofEas

whereζ=|E| satisfying 1≤ζ＜2n, and |＾Tk|≤|＾Tk+1| holds for anyk=1,…,ζ-1 . Seti=1.

Example 4Recall Example 1. We f ind the minimum carrierTminof THP based on Algorithm 1.

3 New formula of Shapley value

In this section, we f irstly present a new formula of Shapley value based on the minimum carrier of essential cooperative games, and then convert the new formula into an equivalent algebraic form based on STP, which can greatly simplify the calculation of Shapley value.

3.1 Shapley value and its new formula

In this part, we present a new formula of Shapley value. To this end, we recall some fundamental results on Shapley value.

Def inition 4 [ 11] Given a cooperative game (N,v), ann-dimensional vectorx=(x1,x2,…,xn) satisfying

is called an imputation of (N,v), wherexjdenotes the prof it allocated to playerj,j=1,2,…,n.E(v) is the set of all imputations of (N,v).

When studying cooperative games, one of the key issues is how to distribute the new surplus generated by cooperation, namely imputation. In essential cooperative games,new cooperation surplus is created by coalition, and thus coalition is meaningful. In addition, whether or not such a coalition can maintain depends on how the surplus of cooperation is distributed such that the prof it of each player increases. It is worth pointing out that Shapley value is the only imputation satisfying three axioms: effi ciency axiom,symmetry axiom and additivity axiom [ 11]. Hence, it has been widely used and plays an important role in cooperative games.

It should be pointed out that the computational complexity of formula ( 9) is O(2|N|) , which is extremely high when |N| is not small. Therefore, it is urgent to simplify the formula of Shapley value to reduce the computational complexity.

Note that for anyj?Tminand any coalitionH∈2Ncontainingj,

which means that playerjis a dummy player and does not make any contribution to coalitionH. In other words, for any coalitionH∈2N, only players inTminmake contributions.Based on the above analysis, a natural idea is to simplify the formula of Shapley value by usingTmin. Especially, when|Tmin|?|N| , the computational complexity of the new formula can be greatly reduced.

Given an essential cooperative game (N,v), assume thatTminis the minimum carrier of (N,v) and |Tmin|=l.

For anyj?TminandH?N{j} , one can easily obtain that

which together with ( 9) show thatφj(v)=0 , ?j?Tmin.

For anyj∈Tmin, partitioningN{j} into the following two disjoint sets:

it is easy to see that H=H1∪H2∪H3and Hi∩Hj=?holds for ?i,j∈{1,2,3} ,i≠j. Then, for anyj∈Tmin, ( 9)can be expressed as

ForH∈H1, the following two equations are obvious:

Similarly, for anyH∈H3, one can see from the def inition of carrier that

which can be combined with the second part of ( 10).

To sum up, we have the following new formula of Shapley value.

Proposition 4Consider cooperative game(N,v)with the minimum carrier Tmin.Assume|Tmin|=l.Then the new formula of Shapley value is φ(v)=(φ1(v),φ2(v),…,φn(v)),where

In the following, we simplify the coeffi cients ( 13) and( 14) in the new formula of Shapley value ( 12).

Proposition 5Coeffi cients(13)and(14)can be respectively simplif ied as follows:

ProofWe only need to prove ( 15). Similarly, one can prove( 16).Since

Therefore, we have

Based on Propositions 4 and 5, we finally obtain the following new formula of Shapley value.

Theorem 2Considering cooperative game(N,v)with the minimum carrier Tmin.Assuming|Tmin|=l,the Shapley value of(N,v)is φ(v)=(φ1(v),φ2(v),…,φn(v)),where

ProofBased on Propositions 4 and 5, it is easy to obtain that for anyj∈Tmin,

Remark 3The computational complexity of the new formula( 18) is O(2|Tmin|) , which is much lower than the computational complexity of ( 9), that is, O(2|N|) , when |Tmin|?|N|.

Remark 4For any dummy playerj?Tmin, it is easy to obtain thatv({j})=v({j}∩Tmin)=v(?)=0 . By Theorem 2, we can see that the prof it allocated to dummy playerjis also zero, and the Shapley value is only determined by the players in minimum carrier. Therefore, for any dummy playerj?Tmin,φj(v)=v({j})=0 , which verifies that dummy player does not make any contribution to the coalitions containing it.

3.2 Algebraic form of new formula ( 18)

Although the new formula ( 18) can greatly reduce the computational complexity of Shapley value, it is still inconvenient to calculate via MATLAB. Therefore, we convert ( 18) into an equivalent algebraic form via STP in this part.

Consider a cooperative game (N,v) with the minimum carrierTmin. AssumeTmin={α1,…,αl} andj=αrj,j∈Tmin.Then, for anyR?Tmin, we have Lemma 2[12]Construct a set of column vectors as follows:

Based on the above analysis, we can obtain that forj∈Tmin,

To sum up, we have the following result on the algebraic form of new formula ( 18).

Theorem 3Consider cooperative game(N,v)with the minimum carrier Tmin={α1,…,αl}.Then,

To make ( 9) easier to calculate, Cheng and Xu [ 12]also proposed an equivalent algebraic form of ( 9). Next,we recall the algebraic form of ( 9) presented in [ 12] and compare it with ( 22).

Remark 5Consider cooperative game (N,v) with |N|=n.Assume that the minimum carrier of (N,v) isTminand|Tmin|=l. According to Lemma 3, to calculate the Shapley value of (N,v), we need to calculateΞn∈?2n×n, which will be very large when (N,v) contains a great deal of players.However, by Theorem 2 and Theorem 3, to calculate the Shapley value of (N,v), we only need to calculate Sl∈?2l×l,which is much smaller thanΞnwhenl?n. Therefore,the new formulas proposed in Theorem 2 and Theorem 3 can greatly reduce the computational complexity when|Tmin|?|N|.Example 5Recall Example 4. We calculate the Shapley value of THP by two diff erent methods.

Therefore, we can obtain from Lemma 3 that the Shapley value of THP is

Next, we calculate the Shapley value of THP based on Theorems 2 and 3.

In Example 4,Tmin={1,3} ,l=|Tmin|=2. Since 2?Tmin,by Theorem 2, it is easy to obtain thatφ2(v)=0 . Then, to calculate the Shapley value of THP, we only need to calculate(φ1(v),φ3(v)).

4 An illustrative example

Consider cooperative game (N,v) withN={1,2,3,4,5} ,where the characteristic functionvis given by its structure matrix as

Thus, by ( 22), we have (φ2(v),φ5(v))=Mv|TminS2=[25 35].To sum up, the Shapley value of (N,v) is

Finally, we calculate the Shapley value of (N,v) according to Lemma 3.

Then, we can obtain the Shapley value from Lemma 3 as follows:

ComparingΞ5∈?32×5with S2∈?4×2, one can further see that the new formulas proposed in this paper greatly reduce the computational complexity of calculating the Shapley value for cooperative games.

5 Conclusions

In this paper, we have investigated the calculation of the Shapley value for cooperative games based on the carrier. We have presented a necessary and suffi cient condition for the verif ication of the carrier. Using the results on the carrier, we have established an algorithm to obtain the minimum carrier. Then, by virtue of the properties of the minimum carrier, we have proved that the prof it allocated to dummy players is zero, and the prof it allocated to players in minimum carrier is only determined by the minimum carrier, based on which a new formula of Shapley value has been presented. We have revealed that the calculation of the Shapley value for cooperative game can be conf ined to a sub-game def ined on the minimum carrier, which coincides with the effi ciency axiom. Based on STP, we have converted the new formula of the Shapley value into an equivalent algebraic form, which greatly reduces the computational complexity of the original Shapley value. An interesting topic is to apply the new formula of the Shaple value to the investigation of large-scale coalitional control systems [ 45].

AcknowledgementsThis work was supported by the National Natural Science Foundation of China (No. 62073202 and No. 61873150), the Young Experts of Taishan Scholar Project (No. tsqn201909076), and the Natural Science Fund for Distinguished Young Scholars of Shandong Province (No. JQ201613).