What is the Shapley value ?
Do you know the SHAP method? The famous XAI local method. SHAP is based on the Shapley value. In this blog, you will open the box of how Shapley value works and demystify it.
In cooperative game theory, the Shapley value gives a way to do a fair distribution of payoffs to the players. It is named after Lloyd Shapley, who introduced the concept in 1953 and received the Nobel Prize in Economics in 2012 for his work.
Today, the Shapley value plays an increasingly important role in many fields, including in machine learning where it is used for example by SHAP to do local explainability of predictions.
In this blog, I will introduce you to some of the concepts behind the Shapley Value. I hope this will help you demystify the concept.
Cooperative games
In a cooperative game, “players” have the possibility to forge coalitions to achieve a common goal. One difficulty in the theory of cooperative games is the distribution of benefits among the players.
For example, a coalition of 3 factories produced goods worth 100 credits. How to redistribute these 100 credits fairly between the 3 participants of the coalition?
The Shapley value allows for a fair distribution of profits. But for a mathematician, “distribute fairly” means nothing… Before defining the Shapley value, it is therefore necessary to formally define what we mean by a fair distribution. Four axioms have been proposed to formally express the problem: Efficiency, Symmetry, Linearity and Dummy player.
In order to present these axioms mathematically, we must introduce some notations.
Some notations
- N is the set containing all the players. In our example, N contains the three factories.
- S is a subset of N (i.e. S ⊆ N). It is nothing more than a subset of participants of the grand coalition N.
- i is an element of N (i.e. i ∈ N)
- v is a value function that maps subsets of players S to a real number
Note that v(N) is the value function of the grand coalition. In our example, the value generated by our three factories is 100 credits: v(N)=100.
When a player i join a set of players S, the marginal contribution of player i to S is:
The marginal contribution measures the value that player i added when (s)he joined the group of players S. This contribution can be null, positive or even… negative.
And now … the Shapley value ϕ of player 𝑖 given the set 𝑁 and the value function 𝑣 is defined by:
The 4 axioms of fairness behind the Shapley value
It is now possible to use these notations to present more formally what are the axioms used by the Shapley value to define what is a fair distribution of benefits in a coalition.
Efficiency: All the revenues v(N) of the grand coalition N are redistributed among all the players (no more, no less).
The Shapley value ϕ measures the amount that players will receive. This axiom of Efficiency simply says that the sum of what each player will receive must be equal to what the grand coalition has produced.
Symmetry: Players i and j who contribute the same to all coalition subsets S receive the same share.
Roughly speaking, this axiom means that if you and me always contribute the same amount to all sub coalitions, then you and me should receive the same amount.
Linearity: Let (N, v₁) and (N, v₂) be two coalition games, the values from the games can be combined in an additive way.
This rule is used to define how to distribute the payoffs of a game that has been constructed by combining two games in a linear way. Suppose we have two games with the same players N but with different value functions v₁ and v₂. Suppose we define a new cooperative game for which the value function is nothing else than the sum of these two value functions v₁ + v₂. This axiom states that the Shapley value of our new game can be calculated by simply adding the Shapley value of each game.
Dummy player: Those who do not contribute receive nothing.
This last axiom is quite simple to understand in itself. Although it can raise legitimate ethical questions when it is used in areas such as economics (there has been a lot of work on how to modify this axiom), in areas such as machine learning, this last axiom does not pose such problems when we try for instance to measure the contribution of variables to the predictions of a model.
It can be shown that, for a coalition game (N, v), the Shapley value is the unique division of the payoff that divides the total payoff v(N) of the grand coalition N and that satisfies the axioms of Symmetry, Linearity and Dummy player.
The Shapley value equation
Given a set of players N and a value function v, the Shapley value of player i is given by:
Let’s take some time to untangle this equation… We can see that it can be divided into three main parts. The Shapley value of player i is a weighted average of the marginal contributions of i over all subsets S of N. The denominator |N|! before the sum is the number of permutations of the set N where |N| is the total number of players.
As we can see below: for a subset S, the weight is the product of the number of permutations of S and the number of permutations of the complement of S and i (i.e.; N\{S∪{i}}).
Another equivalent formulation of the Shapley value
Although the previous equation is a common definition of the Shapley value which is the solution to the 4 axioms of fairness, we often find another equivalent formulation which has the advantage of being easier to calculate.
To introduce the notation, let’s assume that we are in a game with four players: N={P1, P2, P3, P4}.
- Let σ be the set with all the permutations of N. For instance if |N|=4 then the set σ={(P1, P2, P3, P4), (P1, P2, P4, P3), (P1, P4, P2, P3), (P4, P1, P2, P3), (P4, P1, P3, P2), …, (P4, P3, P2, P1)} contains the 4!=24 permutations of N.
- Let Q(σⱼ , i) be the coalition of the predecessors of the player i in σⱼ where σⱼ is an element of σ. For instance if σⱼ=(P1, P4, P2, P3) and i=P2 then Q(σⱼ , i)={P1, P4}.
With this new natation, the Shapley Value for the player i is defined as the average of its marginal contribution over all permutations in σ:
Where in this equation, the σⱼ runs over all the |N|! permutations of the players in the set N and Q(σⱼ , i) is the set of predecessor players of i in σⱼ.
We will next give two examples that show how to use this method to calculate the value of Shapley.
Example 1
Suppose we have a three players in a cooperative game where the value of the different coalitions is given by:
As can be seen, the value of the grand coalition is v(N)=90… and, based on the values of all the sub-coalitions, the question is now how these 90 should be allocated.
The following table gives the details of the calculations to obtain the Shapley values for the three players.
We can see that, given Shapley’s value, Player P1, Player P2 and Player P3 should receive 39.16, 20.67 and 30.17respectively. Each column gives details of the calculations used to obtain the Shapley values. These calculations are made on the |N|!=3!=3×2×1=6 permutations of the 3 players.
Let’s see the steps to get the Shapley value 39.16 for player P1 and let’s take for example line number 3 with the permutation (P2, P1, P3). In this permutation σ₃, the predecessor of P1 is P2
and therefore, the marginal contribution of P1 on its predecessors in σ₃ is 24:
The table above gives the values of the marginal contribution of the 6 permutations. In red are indicated the predecessor of P1 in each permutation.
According to the above formula, to obtain the Shapley value, we simply have to average the 6 values to get the 39.16.
The same calculation can be used to obtain the other two Shapley values.
Example 2
A set of 3 companies producing gloves have formed a coalition. Each of them can produce either only left-handed gloves or only right-handed gloves. When selling the gloves, a right-handed glove must be matched with a left-handed glove. Unmatched gloves have zero value in the market.
If P1 and P2 produce left-handed gloves and P3 produces right-handed gloves then the value of the different coalitions is given by:
How can the revenue be redistributed fairly? If we apply the same technique as in the previous example, we obtain the following table:
Therefore, in order to comply with the four axioms defined above, player number 3 must receive 4/6 of the income generated by the grand coalition, while the other two must receive 1/6.
SHapley Additive exPlanations (SHAP) Value
SHAP is an explainable artificial intelligence (XAI) technique based on Shapley value and used in machine learning to determine how input variables contribute to output predictions.
The input variables are treated as players in a coalition game in which the model uses the contributions of each player to make a prediction. In this game, the payout of the grand coalition is the prediction, and the Shapley value is used to divide this payout equally among the players (i.e., the input variables).
As an illustration, in the example below, a machine learning model uses four input variables. Each variable makes a contribution to a cooperative game (i.e., the model) and the payoff of the game is the prediction.
I invite you to look at my blog on Agnostic explainable artificial intelligence (XAI) : An introduction with simple code examples if you want to know more about Shap value.
Conclusion
In this blog, we introduced the Shapley value which allows to redistribute fairly the gains generated during a cooperative game. After an intuitive introduction of the 4 axioms used by the Shapley value, the equation to calculate the Shapley value was presented. We ended with two examples and a brief introduction to the SHAP value that is used in machine learning.
Thanks for reading!
Please consider following me if you wish to stay up to date with my latest publications and increase the visibility of this blog.
And are you familiar with the Medium clap button 👏 ? Did you try it more than ones to see what happens 😎?
