Summary

Shapley Values provide a fair method to distribute payoffs in cooperative games by assessing each player's marginal contribution.

Abstract

Shapley Values, a concept in game theory introduced by Lloyd Shapley, offer a solution to fairly allocate total winnings among players in cooperative games based on their individual contributions. The method involves calculating the marginal impact of each player by considering their addition to every possible coalition. An example with four players—Alice, Bob, Cooper, and Diana—illustrates the calculation process, which includes determining the average marginal contribution of a player across different coalition sizes and then dividing by the number of players to find their Shapley Value. This value represents the fair share of the prize money each player should receive. The process is mathematically intensive, involving combinations to count possible coalitions and averaging marginal contributions for each coalition size. The Shapley Values for all players sum up to the total prize money, ensuring a equitable distribution. This concept has gained popularity in machine learning for interpreting complex models.

Opinions

The author believes that Shapley Values offer a fair approach to distributing payoffs, emphasizing the importance of recognizing each player's contribution to the overall cooperation.
The use of examples and step-by-step calculations suggests the author's view that Shapley Values can be understood through practical illustrations, making the concept more accessible.
The mention of Shapley Values' application in machine learning, particularly in interpreting black-box models, indicates the author's opinion on the versatility and increasing relevance of this concept beyond game theory.
The article implies that while the calculation of Shapley Values can be complex, especially with a large number of players, it is a valuable tool for ensuring fairness in cooperative scenarios.

Economics, Illustrated: Shapley Values

Shapley Values is a widely-used concept in game theory that provides a fair way to distribute the total payoff of a cooperative game among its players. Introduced by Lloyd Shapley in 1953, the concept is based on the idea that each player should be compensated for their marginal contribution to the game.

Essentially, Shapley Values help answer the question: how important is each player to the overall cooperation, and consequently what payoff can each player expect?

Let’s work through an example to understand the math behind them.

Math Behind Shapley Values

Suppose we have a cooperative game with four players: Alice, Bob, Cooper, and Diana.

They have decided to join forces and play the game together as a coalition. They win a total of $1000.

Now the players are faced with the task of dividing the $1000 prize money fairly among themselves. To determine each player’s share, we need to calculate their individual Shapley Values, which measures their contribution to the total prize money.

In order to determine each player’s share of the winnings, we need to calculate their individual Shapley Values — a measure of their contribution to the total prize money.

To compute the Shapley Values, we also need to know how much each player would have won if they had played individually (let’s assume we have this information). Here are the individual amounts that Alice, Bob, Cooper, and Diana would have won:

While it may appear that the individual points earned by each player are indicative of their marginal contributions to the total prize, this is not necessarily the case. This is because when the players form coalitions of 2 or 3, they may contribute differently and win different prize amounts. In order to account for this, we need to consider the amount each pair of players would have won if they teamed up and formed coalitions of 2.

Similarly, they could have also formed coalitions of 3 and won these amounts:

And obviously, if no one plays, then there will be no money won, i.e., a coalition of size 0 wins $0.

Now that we have the individual and team contributions, we can calculate the Shapley Value for each player to determine their fair share of the prize money. Let’s start by calculating Alice’s marginal contribution by following these steps:

Step 1: Find the coalitions formed without Alice in them

Step 2: Count the number of coalitions formed of each coalition size

In this case, since we only have four players, it’s relatively simple to count the number of coalitions of each size. However, for larger games with, say, 100 players, this task becomes considerably more challenging. Fortunately, there is a simple formula in probability theory, the combination formula to calculate these values.

For example, if we wish to find the number of coalitions of size 2 that exclude Alice, we know that we need to select 2 players from the remaining 3 (Bob, Cooper, and Diana).

which matches the number of coalitions that we saw above:

Similarly, the number of ways of choosing 3 players out of 3 to form coalitions of size 3 is…

…and the number of ways of choosing 1 player out of 3 to form coalitions of 1…

…and the number of ways to form coalitions of 0 is:

Step 3: Find the average marginal contribution of Alice to each coalition that doesn't include her, for each coalition size

Marginal contribution refers to the additional amount of prize money that Alice brings to the coalition compared to the coalition without Alice.

Let’s start by finding the average marginal contribution for coalitions of size 2.

Firstly, we must calculate the difference in prize money between the coalition without Alice and the prize money after Alice is added to the coalition.

Secondly, we add up all the differences and divide this sum by the total number of coalitions of size 2. This gives us the average marginal contribution for coalitions of size 2.

For instance, let’s consider the first coalition of size 2 which is Bob and Cooper.

We see that they would’ve won $400. Let’s add Alice to this coalition:

The money won increases to $700. The difference between the 2 is:

So we see that adding Alice to this coalition increases its value by $300 and that is considered Alice’s marginal contribution.

Similarly, for the other coalitions of size 2:

Now we divide the sum of these marginal contributions by the total number of coalitions of size 3 (using the formula in Step 2):

This can be interpreted as: on average Alice marginally contributes $233.33 when added to coalitions of size 2.

We do the same for coalitions of size 3. Since there is only one coalition of size 3, we find the difference in prize money when Alice joins the coalition:

And then divide this by the number of coalitions of size 3:

for coalitions of size 3, Alice, on average, marginally contributes $200

And for coalitions of size 1:

And coalitions of size 0:

Step 4: Calculate Alice’s Shapley Value

To calculate the Shapley Value, we add up all the average marginal contributions from the different coalition sizes and divide by the number of different coalition sizes excluding Alice.

Here we saw that there are 4 sizes (0, 1, 2, and 3) of coalitions formed without Alice. So:

NOTE: An easier way to get the number of different coalition sizes is that this value is the same as the number of players in the game.

So, Alice contributed $237.5 to the $1000 prize money.

Now for each of the remaining players, we repeat this process and find each of their Shapley Values:

And if we add them up, we see that 237.5 + 237.5 + 245.8333 + 279.1667 = $1000, which is equal to the prize money won. These Shapley Values are a fair allocation of the players’ marginal contributions and, in turn, the money each of them gets to take.

NOTE: The formal formula to calculate Shapley Values is:

And that’s Shapley Values wrapped up in a neat little bow. In recent years, they have become popular in machine learning to interpret models, especially black-box ones that are tough to interpret. If you’re curious to see how they’re applied in that world, stay tuned and read about it in my next article!