Shapley values: an introductory example

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].

As the EA Forum page on Shapley values puts it,

In the context of EA, Shapley values are a method for assigning credit for the impact of an intervention to each of a set of actors collaborating to make it happen. The concept of a Shapley value comes from cooperative game theory, where it is a general solution to the problem of distributing gains from cooperation. In impact assessment, it is often compared to the calculation of the raw counterfactual impact of an intervention.

Loosely, each Shapley value (each associated with a specific actor) corresponds to the average of the counterfactual impact produced by the actor, considering each possible way in which the agents could have assembled themselves to cooperate.

The formula for Shapley values is quite confusing, and can be hard to internalize without a friendly example. This post aims to provide a such an 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:

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.

To understand the value of each player's individual contribution, we can check how much this value changes when we remove one player's contribution. The larger the drop in value, the larger that player's contribution.

The table below shows how much the value of the team's hand decreases when we remove each player’s cards.

Under this interpretation, C is contributing less than the other players, and B is contributing the same as A. 

However, the sum of the individual contributions is 500, 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].

 So player A’s Shapley value is

$⅓\cdot 200+⅙\cdot 150+⅙\cdot 100+⅓\cdot 50=\frac{750}{6}=125$

Player B’s Shapley value is 

$⅓\cdot 200+⅙\cdot 150+⅙\cdot 100+⅓\cdot 50=\frac{750}{6}=125$

Player C’s Shapley value is

$⅓\cdot 100+⅙\cdot 50+⅙\cdot 50+⅓\cdot 0=\frac{300}{6}=50$

This tracks with our intuition that player C - who only had a single Q  - made the smallest contribution. Even though players A and B had different cards, their contributions to point scores were the same, and so they have the same Shapley values.

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

1. ^{^}

   See the Wikipedia page for a list of desirable properties, or Shapley values: Better than counterfactuals

2. ^{^}

   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.