Epistemic status: I wrote this on the same day I learnt about Shapley values, and built the example for my own understanding.
When a group of players collaborate, with players making unequal contributions, it is not clear how much of the total gain to attribute to each player. Shapley values provide one way of doing this. There is no mathematically “correct” way of assigning credit, but Shapley values have a number of common-sense desirable properties^{[1]}.
This post aims to provide a quick introduction to Shapley values through a simple example.
A simple example
Imagine a game where teams join to build a collective hand of cards. The types of card are "Q" and "K".
The value of the hand is determined by the number of pairs, three-of-a-kind and four-of-a-kind tricks, as follows:
Trick | Example | Value |
Pair | K K | 50 |
Three-of-a-kind | Q Q Q | 100 |
Four-of-a-kind | K K K K | 200 |
Suppose players A, B, C each hold cards as follows:
A: Q Q K
B: Q K K
C: Q
What is the relative contribution of each player to the value of their collective hand? Or, in other words, what would be the fairest amount to pay each player for their contribution?
Together, they have Q Q Q Q K K K, for a total value of 200 + 100 = 300.
Player C only holds a single Q. They appear to be contributing less than A or B. We can enumerate this by looking at how much the total value drops when we remove each player’s cards from the team’s hand.
Coalition | Hand | Value of hand | Missing player | Contribution of missing player |
{A,B,C} | Q Q Q Q K K K | 300 | ||
{A,B} | Q Q Q K K K | 200 | C | 100 |
{A,C} | Q Q Q K | 150 | B | 150 |
{B,C} | Q Q K K | 100 | A | 200 |
Under this interpretation, C is contributing less than the other players, and B is contributing less than A.
However, the sum of the individual contributions is 450, which is more than the value of the hand that {A,B,C} hold. If players expected fair payment for taking part, we could not simply give each player their counterfactual contribution: there is not enough money to go around.
Shapley values are one way of determining the payment, or credit, due to each player. They take a weighted average of the contributions of each player under each possible combination (or “permutation”) of players. This includes all combinations with one, two or three players.
The full mathematical formula can be found on the Wikipedia page, but let’s see what it looks like in the example.
The table below calculates each player’s counterfactual contribution in each possible combination of players.
The Shapley value of a player is the weighted mean of these contributions.
In this example there are three possible players. One-third of the weight comes from coalitions of three players, one-third from coalitions of two players, and one-third from coalitions of one player^{[2]}.
Coalition |
Hand |
Value | Counterfactual contribution |
Weight | ||
A | B | C | ||||
{A,B,C} | Q Q Q Q K K K | 300 | 200 | 150 | 100 | ⅓ |
{A,B} | Q Q Q K K K | 200 | 150 | 150 | - | ⅙ |
{A,C} | Q Q Q K | 150 | 150 | - | 100 | ⅙ |
{B,C} | Q Q K K | 100 | - | 100 | 50 | ⅙ |
{A} | Q Q K | 50 | 50 | - | - | ⅓ |
{B} | Q K K | 50 | - | 50 | - | ⅓ |
{C} | Q | 0 | - | - | 0 | ⅓ |
So player A’s Shapley value is
Player B’s Shapley value is
Player C’s Shapley value is
This tracks with our intuition that player C’s contribution was smaller. Even though players A and B had similar cards, player A’s contribution was greater. This is because across all combinations, most value came from Q cards, and player A held more Q cards.
Also, notice that the Shapley values sum to 300, the total value of the team's hand. The values could be used to share out the group winnings.
This has been a simple example to illustrate how Shapley values are calculated in a three-player scenario. Shapley values could be a better way of thinking about counterfactual impact. Most importantly, since the values add up to the total value of the team effort, they help us avoid double-counting.
Photo: Peter Shapley
- ^{^}
See the Wikipedia page for a list of desirable properties, or Shapley values: Better than counterfactuals
- ^{^}
This generalizes so that in n-player situations, 1/n of the weight comes from coalitions of each size from 1 to n. See the Wikipedia page for a fuller mathematical formulation.