The Shapley Value

The Shapley Value is a solution concept from coalitional game theory that calculates a fair distribution of credit for the team output to each teammate.  Named after its originator Lloyd Shapley, it is one of the most important concepts in coalitional game theory because, as Shapley proved mathematically, it is the only distribution of credit that satisfies many different desirable fairness properties.  For example, it is the only concept for which a player that contributes more toward production than another player receives a higher share of credit, the entire team output is fully distributed among the players so no credit is left unassigned, and only contributions to team production matter rather than other individual characteristics.  The Shapley Value has been used in industry, law, and government, and Shapley received the Nobel Prize in Economics in part for this conceptual contribution.

Below is a brief introduction to how the Shapley Value is calculated. It gets a little technical, so feel free to move to another article if these details do not interest you.

Before calculating the Shapley Value, the team-production setting must first be represented mathematically as a coalitional game.  The first part is the set of teammates.  The second part is the value function, which is a numerical description of how much output is produced for every possible subset (i.e., coalition) of the teammates when only the teammates in that coalition are involved in production.

Consider the following example.  Suppose the set of teammates includes only individuals A, B, and C.  With three teammates, there are 2^3 = 8 possible coalitions (i.e., the power set of possible coalitions) as shown in Table 1.  The first column in the table below lists the coalition members for each of the eight possible coalitions.  The None coalition has no teammates, three coalitions have exactly one teammate, three have exactly two, and the full coalition has all three players.  The second column states the output — or value — of each coalition, which is the output that the particular coalition produces when only the members of the coalition participate in the production.  In this example, coalitions None, A, B, C, and AC each produce output 0, coalitions AB and BC each produce output 1, and the ABC coalition produces output 2.

Table 1:  Value Function

Coalition MembersValue of Coalition
None (the empty set)0

To calculate the Shapley Value for a particular teammate, we need to calculate the marginal increase in production over all of the possible orders in which the full coalition (ABC) can be constructed.  With three teammates, there are 3! = 6 six possible orders:  A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, and C-B-A.  The first order in this list is the team construction in which A is added first, B is added second, and C is added third. The last order in the list is a team constructed in opposite order, with C added first, then B, then A.

Table 2 lists, for each of the orders, the value before A is added to the order, the value after A is added, and the marginal value from adding A, which is the change in value that results from adding A (i.e., the difference between after and before).

Table 2:  Shapley Value Calculation for A

OrderValue before adding A:Value after adding AMarginal value of adding A
Shapley Value = 0.50

Consider the first order A-B-C.  Because A is added first in this order, the coalition before A is added is None (the empty set) that has value 0 as seen in the first table.  After A is added, the coalition has just A, which yields value 0.  The marginal value of adding A in this order is thus 0.

Now consider the third order B-A-C.  The coalition before A is added is just B, which has value 0.  After A is added, the AB coalition produces 1, so the marginal value of adding A is 1.  The rest of this table is completed in a similar manner.

The Shapley Value for teammate A is the average marginal increase in production when adding A across all of the orders.  Adding up all of the marginal increases yields 0 + 0 + 1 + 1 + 0 + 1 = 3.  Dividing the sum of marginal increases 3 by the number of orders 6 gives a Shapley Value for A of 3/6 = 0.5.

Tables 3 and 4 show the Shapley Value calculations for B and C using the same six orders.

Table 3:  Shapley Value Calculation for B

OrdersValue before adding B:Value after adding AMarginal value of adding A
Shapley Value = 1.00

Table 4:  Shapley Value Calculation for C

OrdersValue before adding B:Value after adding AMarginal value of adding A
Shapley Value = 0.50

These calculations reveal that the fair distribution of credit for the team’s total production of 2 is such that A deserves 0.5 credit, B deserves 1.0 credit, and C deserves 0.5 credit.

This distribution makes intuitive sense given the value function and standard notions of fairness.  No teammate alone can achieve the maximum output of 2, so none deserves full credit.  Moreover, the maximum output cannot be achieved unless all three are in the coalition, so everybody deserves some credit.  However, B deserves more credit than A and C because neither A nor C can produce non-zero output without B, i.e., B is more necessary to production than A and C.  The Shapley Value puts a concrete number to this intuition.

A final important fact about the Shapley Value is that it always assigns 0 credit to a Null teammate.  A Null teammate is a teammate for whom the marginal value of adding that teammate to any coalition is always 0, i.e., the third column in the Shapley Value calculation table would have only zeros.  Intuitively, a Null teammate never adds value to production, so the Null teammate’s fair share of credit is 0.  In fact, a Null teammate can be removed from the set of teammates altogether and the Shapley Value calculations for the other players will remain the same.