The Shapley Value: An Extremely Short Introduction

at hierophants of escapism, by versatis

[For those who find the LaTeX formatting hard to read: pdf version + LaTeX version]

If we view economics as a method of decomposing (or unwriting) our stories about the world into the numerical and functional structures that let them create meaning, the Shapley value is perhaps the extreme limit of this approach. In his 1953 paper, Shapley noted that if game theory deals with agents’ evaluations of choices, one such choice should be the game itself—and so we must construct “the value of a game [that] depends only on its abstract properties” (1953: 32). By embodying a player’s position in a game as a scalar number, we reach the degree zero of meaning, beyond which any sort of representation is severed entirely. And yet, this value recurs over and over throughout game theory, under widely disparate tools, settings, and axiomatizations. This paper will outline how the Shapley value’s axioms coalesce into an intuitive interpretation that operates between fact and norm, how the simplicity of its formalism is an asset rather than a liability, and its wealth of applications.

Overview

Cooperative game theory differs from non-cooperative game theory not only in its emphasis on coalitions, but also by concentrating on division of payoffs rather than how these payoffs are attained (Aumann, 2005: 719). It thus does not require the degree of specification needed for non-cooperative games, such as complete preference orderings by all the players. This makes cooperative game theory helpful for situations in which the rules of the game are less well-defined, such as elections, international relations, and markets in which it is unclear who is buying from and selling to whom (Aumann, 2005: 719). Cooperative games can, of course, be translated into non-cooperative games by providing these intermediate details—a minor industry known as the Nash programme (Serrano, 2008).

Shapley introduced his solution concept in 1953, two years after John F. Nash introduced Nash Equilibrium in his doctoral dissertation. One way of interpreting the Shapley value, then, is to view it as more in line with von Neumann and Morgenstern’s approach to game theory, specifically its reductionist programme. Shapley introduced his paper with the claim that if game theory deals with agents’ evaluations of choices, one such choice should be the game itself—and so we must construct “the value of a game [that] depends only on its abstract properties” (1953: 32). All the peculiarities of a game are thus reduced to a single vector: one value for each of the players. Another common solution concept for cooperative games, the Core, uses sets, with the corollary that the core can be empty; the Shapley value, by contrast, always exists, and is unique.

To develop his solution concept, Shapley began from a set of desirable properties taken as axioms:

  • Efficiency: \sum_{i\in{N}} \Phi_i(v) = v(N).
  • Symmetry: If v(S ∪{i}) = v(S ∪{j}) for every coalition S not containing i & j, then ϕi(v) = ϕj(v).
  • Dummy Axiom: If v(S) = v(S ∪{i} for every coalition S not containing i, then ϕi(v) = 0.
  • Additivity: If u and v are characteristic functions, then ϕ(u + v) = ϕ(u) + ϕ(v)

In normal English, any fair allocation ought to divide the whole of the resource without any waste (efficiency), two people who contribute the same to every coalition should have the same Shapley value (symmetry), and someone who contributes nothing should get nothing (dummy). The first three axioms are ‘within games’, chosen based on normative ideals; additivity, by contrast, is ‘between games’ (Winter, 2002: 2038). Additivity is not needed to define the Shapley value, but helps a great deal in mathematical proofs, notably of its uniqueness. Since the additivity axiom is used mainly for mathematical tractability rather than normative considerations, much work has been done in developing alternatives to the additivity axiom. The fact that the Shapley value can be replicated under vastly different axiomatizations helps illustrate why it comes up so often in applications.

The Shapley value formula takes the form:

\Phi_i(v) = \sum\limits_{\substack{S\in{N}\\i\in{S}}} \frac{(|S|-1)!(n-|S|)!}{n!}[v(S)-v(S\backslash\{i\})]

where |S| is the number of elements in the coalition S, i.e. its cardinality, and n is the total number of players. The initial part of the equation will make far more sense once we go through several examples; for now we will focus on the second part, in square brackets. All cooperative games use a value function, v(S), in which v(Ø) ≡ 0 for mathematical reasons, and v(N) represents the ‘grand coalition’ containing each member of the game. The equation [v(S) – v(S\{i})] represents the difference in the value functions for the coalition S containing player i and the coalition which is identical to S except not containing player i (read: “S less i”). The additivity axiom implies that this quantity is always non-negative. It is this tiny equation that lets us interpret the Shapley value in a way that is second-nature to economists, which is precisely one of its most remarkable properties. Historically, the use of calculus, which culminated in the supply-demand diagrams of Alfred Marshall, is what fundamentally defined economics as a genre of writing, as opposed to the political economy of Adam Smith and David Ricardo. The literal meaning of a derivative as infinitesimal movement along a curve was read in terms of ‘margins’: say, the change in utility brought about by a single-unit increase in good x. Thus, although these axioms specify nothing about marginal quantities, we can nonetheless interpret the Shapley value as the marginal contribution of a single member to each coalition in which he or she takes part. This marginalist interpretation was not built in by Shapley himself, but emerged over time as the Shapley value’s mathematical exposition was progressively simplified. It is this that allows us to illustrate by examples instead of derivations.

Examples 1 & 2: Shapley-Shubik Power Index (Shapley & Shubik, 1954)

Imagine a weighted majority vote: P1 has 10 shares, P2 has 30 shares, P3 has 30 shares, P4 has 40 shares.

For a coalition to be winning, it must have a higher number of votes than the quota, here q = \frac{110}{2} = 55

v(S) =\begin{cases} 1, & \text{if }q>55 \\ 0, & \text{otherwise}\end{cases}  Winning coalitions: {2,3}, {2,4}, {3,4} & all supersets containing these.

Since the values only take on 0s and 1s, we can work with a shorter version of the Shapley value formula:

\Phi_i(v) = \sum\limits_{\substack{S\text{ winning}\\S\backslash\{i\}\text{ losing}}} \frac{(|S|-1)!(n-|S|)!}{n!}

Here, [v(S) – v(S\{i})] takes on a value of 1 iff a player is pivotal, making a losing coalition into a winning one. Otherwise it is either [0 – 0] = 0 for a losing coalition or [1 – 1] = 0 for a winning coalition.

For P1: v(S) – v(S\{1}) = 0 for all S, so ϕ1(v) = 0 (by dummy player axiom)

For P2: v(S) – v(S\{2}) ≠ 0 for S = {2,3}, {2,4}, {1,2,3}, {1,2,4}, so that:

\Phi_2(v)=2\frac{1!2!}{4!}+2\frac{2!1!}{4!}=\frac{8}{24}=\frac{1}{3}

By the symmetry axiom, ϕ2(v) = ϕ3(v) = ⅓. By the efficiency axiom, 0 + ⅓ + ⅓ + ϕ4(v) = v(N) = 1 → ϕ4(v) = ⅓

It is worth noting that, within the structure of our voting game, P4’s extra ten votes have no effect on his power to influence the outcome, as shown by the fact that ϕ2 = ϕ3 = ϕ4. A paper by Shapley (1981) notes an actual situation for county governments in New York in which each municipality’s number of votes was based on its population; in one particular county, three of the six municipalities had Shapley values of zero, similar to our dummy player P1 above. Upon realizing this, the quota was raised so that our three dummy players were now able to be pivotal for certain coalitions, giving them nonzero Shapley values (Ferguson, 2014: 18-9).

For a more realistic example, consider the United Nations Security Council, composed of 15 nations, where 9 of the 15 votes are needed, but the ‘big five’ nations have veto power. This is equivalent to a weighted voting game in which each of the big five gets 7 votes, and each of the other 10 nations gets 1 vote. This is because if all nations except one of the big five vote in favor of a resolution, the vote count is (35 – 7) + 10 = 38.

Thus we have weights of w1 = w2 = w3 = w4 = w5 = 7, and w6 → w15 = 1.

Our value function is v(S) =\begin{cases} 1, & \text{if }q>39 \\ 0, & \text{otherwise}\end{cases}  Winning coalitions: {1,2,3,4,5, any 4+ of the 10}

For the 4 out of 10 ‘small’ nations needed for the vote to pass, the number of possible combinations is \frac{10!}{4!\,6!}.

Hence, in order to calculate the Shapley value for any member (say, P1) in the big five, we take into account that v(S) – v(S\{1}) ≠ 0 for all 210 coalitions, plus any coalitions with redundant members; this is just another way of expressing their veto power. In our previous example, we were able to count by hand the members in each pivotal coalition S and multiply that number by the Shapley value function for coalitions of that size. Here the number of pivotal coalitions for each size is so large that we must count them using combinatorics. Our next equation looks arcane, but it is only the number of pivotal coalitions multiplied by the Shapley function. First we have the minimal case where 4 of the 10 small members vote in favor of the resolution, then we have the case for 5 of the 10, and so on until we reach the case where all members unanimously vote together:

\Phi_1(v)=(\frac{10!}{4!6!})(\frac{8!6!}{15!})+(\frac{10!}{5!5!})(\frac{9!5!}{15!})+(\frac{10!}{6!4!})(\frac{10!4!}{15!})+(\frac{10!}{7!3!})(\frac{11!3!}{15!})+(\frac{10!}{8!2!})(\frac{12!2!}{15!})+(\frac{10!}{9!1!})(\frac{13!1!}{15!})+(\frac{14!}{15!})

=210\frac{1}{45045}+252\frac{1}{30030}+210\frac{1}{15015}+120\frac{1}{5460}+45\frac{1}{1365}+10\frac{1}{210}+1\frac{1}{15} = 0.19627

By the symmetry axiom, we know that all members of the big five have the same Shapley value of 0.19627. Also, as before, the efficiency axiom implies that the Shapley values for all the players sum to v(N) = 1. Since symmetry also implies that the Shapley values are the same for the 10 members without veto power, we need not engage in any tedious calculations for the remaining members, but can simply use the following formula:

\Phi_6=\cdots=\Phi_{10}=\frac{1-5(0.19627)}{10}=\frac{1-0.98135}{10}=0.001865

Part of the purpose of this example is to help the reader appreciate how quickly the complexity of such problems increases in the number of agents n. Weighted voting games are actually relatively simple to calculate because v(N) = 1, which is why we just sum together the Shapley formulas for each pivotal coalition’s size; in our next example we will relax this assumption. In so doing, the part of the Shapley formula v(S) – v(S\{i}) gains added importance as a ‘payoff’, whereas the Shapley formula used in our weighted voting game examples acts as a probability, so that the combined formula is reminiscent of von Neumann-Morgenstern utility. The Shapley formula can be construed as a probability in the following way (Roth, 1983: 6-7):

suppose the players enter a room in some order and that all n! orderings of the players in N are equally likely. Then ϕi(v) is the expected marginal contribution made by player i as she enters the room. To see this, consider any coalition S containing i and observe that the probability that player i enters the room to find precisely the players in S – i already there is (s – 1)!(n – s)!/n!. (Out of n! permutations of N there are (s – 1)! different orders in which the first s – 1 players can precede i, and (n – s)! different orders in which the remaining n – s players can follow, for a total of (s – i)!(n – s)! permutations in which precisely the players S – i precede i.

One drawback to this approach is its implicit assumption that each of the coalitions is equally likely (Serrano, 2013: 607). For cases such as the UN Security Council this is doubtful, and overlooks many very interesting questions. It also assumes that each player wants to join the grand coalition, whereas unanimous votes seldom occur in practice. The main advantage of the Shapley value in the above examples is that another common solution concept for cooperative games, the Core, tends to be empty in weighted voting games, giving it no explanatory power. The Shapley value can be extended to measure the power of shareholders in a company, and can even be used to predict expenditure among European Union member states (Soukenik, 2001). We will go through another relatively simple example, and then move on to several more challenging applications.

Example 3: Dragon’s Den (cf. Wang, 2007: 16, 19)

Dragon’s Den is a popular reality television show hosted by three venture capitalists; small business owners go on the show, describe their business, and try to convince the hosts to fund their business in exchange for a share of the company. The hosts ask questions and debate amongst themselves about the prospects of the company (e.g. its target market, scalability of its business model) and finally suggest what they perceive as an equitable share of the company they will receive in exchange for their funding. Both the amount of funding and the share of the company demanded in return may differ among the hosts, since they are proportional to the resources (e.g. marketing, supply chains) the host has to increase the company’s value. The question we ask in our model is: if all of the hosts want to fund a small business, and all contribute in different amounts to the growth of the company, how do we fairly allocate shares of the company among the business owner and the three hosts? (Note: we are assuming perfect information about how much each member can contribute.)

Suppose P1 has a company presently valued at $10K. P2, P3, and P4 are venture capitalists.

We first list all possible coalitions, which total 2n = 24 = 16, including the empty set (which we set to zero). The first line, in which all coalitions among the hosts are zero, simply reflects the fact that the hosts cannot create any value from the company if the small business owner does not allow them to.

v(Ø) = v({2}) = v({3}) = v({4}) = v({2,3}) = v({2,4}) = v({3,4}) = v({2,3,4}) = 0

v({1}) = 10         v({1,2}) = 20     v({1,3} = 30     v({1,4}) = 35

v({1,2,3}) = 45   v({1,2,4}) = 35  v({1,3,4} = 35   v({1,2,3,4}) ≡ v(N) = 50

We start with P1, listing each coalition of which he or she is a member, and his/her marginal contributions.

Recall: \Phi_i(v) = \sum\limits_{\substack{S\in{N}\\i\in{S}}} \frac{(|S|-1)!(n-|S|)!}{n!}[v(S)-v(S\backslash\{i\})].

To ease notation, let Pn(S) ≡ \frac{(|S|-1)!(n-|S|)!}{n!} and Δi(S) ≡ [v(S) – v(S\{i})]

The calculations for P2 and P3 are simpler because coalitions among the hosts are all zero-valued.

For P4’s Shapley value, we know by the efficiency axiom that \Phi_4(v)=\frac{160}{12}=13.33.

Because all the Shapley values sum to v(N), the efficiency axiom is satisfied. Since v(N) = 50, we need only multiply each Shapley value by 2 to find their fair share of the company. The symmetry and dummy axioms are not applicable here, but it is worth noting how the additivity axiom comes into play. Its main role is to guarantee the value function v(S) is monotonic (i.e. increasing, but not strictly). That is to say, it is not possible for any player to destroy value by joining a coalition, so that v(S) – v(S\{i}) would be negative.

Ex. 4: Bankruptcy Problem in the Talmud (Aumann, 2002; Guiasu, 2011)

In several passages of the Talmud, a holy book of Judaism that discusses civil law, the problem is posed of what to do in bankruptcy where the total debts owing are larger than the debtor’s estate. The Talmud provides numerical sums for each creditor to receive, depending on the size of the estate (Aumann, 2002: 1):

However, identifying a single unifying rule for these allocations had eluded commentators for millennia. We see in the first case (where the size of the estate is $100) that the estate is equally divided among the creditors, that in the third case (an estate of $300) it is proportionally divided so that each creditor receives half of the amount owed to them, whereas the second case eludes any sort of simple explanation. After coming across the passage, the Jewish game theorist Robert Aumann and his coauthor were able to solve the problem using game theory. The problem was originally solved using a solution concept called the nucleolus, but Guiasu (2011) shows that Shapley values can solve the problem just as well.

Guiasu’s (2011: 70-1) main innovation is to distinguish between cumulative games in which participants refuse to share and so the value function v(S) is calculated additively, and maximal games in which members of a coalition are willing to share parts of their claim. The case we are considering is a cumulative game, but other fair allocation problems in the Talmud are maximal problems, which gives the Shapley value method more generality than even Aumann’s original method (ibid., 77). In a cumulative game, we define v({i}) = min{di,E} and v({i,…,j}) = min[v({i}) + … + v({j}), E], where di is the claim of player i and E is the amount of the estate.

Case 1: E = 100, d1 = 100, d2 = 200, d3 = 300       v(Ø) = 0        v({1}) = 100 = E = v({2}) = v({3})

v({1,2}) = v({1,3}) = v({2,3}) = v(N) = E       Here, [v(S) – v(S\{i})] = [E – E] for all S except v({i}) ∀i

\Phi_i(v) = \sum\limits_{\substack{S\in{N}\\i\in{S}}} \frac{(|S|-1)!(n-|S|)!}{n!}[v(S)-v(S\backslash\{i\})]=\frac{0!2!}{3!}[v(\{i\})-v(\varnothing)]=\frac{2[E-0]}{6}=\frac{E}{3} = 33⅓

The latter is easy because all the claims are greater than or equal to the size of the estate. The general case can be written d1 < … < dm–1 < E ≤ dm < … < dn, and the value function defined as:

v(Ø) = 0        v({i}) = dii ∈ [1, m–1]          v({i}) = dm–1 + (E – dm–1)/(n – m – 1) ∀i ∈ [m, n])

So all players with claims smaller than the estate get at least the smallest claim, and the remainder is shared by the other debtors with claims larger than the estate. This allows us to solve for the latter two cases.

Case 2: E = 200, d1 = 100, d2 = 200, d3 = 300     d1 < E ≤ d2 < d3, so that n = 3 and m = 2

v(Ø) = 0         v({1}) = d1         v({2}) = v({3}) = d1 + (E – d1)/2   v({1,2}) = min{d1 + d2, E} = E

v({1,3}) = min{d1 + d3, E} = E   v({2,3}) = min{d2 + d3, E} = E      v(N) = min{d1 + d2 + d3, E} = E

For P1 we add up the Shapley formulas for the coalitions S = {1}, {1,2}, {1,3}, {1,2,3}. P2 and P3 are similar:

\Phi_1(v)=\frac{0!2!}{3!}[d_1-v(\varnothing)]+2\frac{1!1!}{3!}[E-(d_1+\frac{E-d_1}{2})]+\frac{2!0!}{3!}[E-E]=\frac{2}{6}100+2\frac{1}{6}\frac{200-100}{2}=\frac{100}{3}+\frac{200}{12}=50

\Phi_2=\Phi_3=\frac{0!2!}{3!}[(d_1+\frac{E-d_1}{2})-0]+\frac{1!1!}{3!}[E-d_1]+\frac{1!1!}{3!}[E-d_1-(d_1+\frac{E-d_1}{2})]+\frac{2!0!}{3!}[E-E]=\frac{5E-d_1}{12}=75

Case 3, where d1 < d2 < E ≤ d3 (n = 3, m = 3), is similar to Case 2, except we set v({2}) = d2 and v{1,2}) = E:

\Phi_1(v)=\frac{0!2!}{3!}[d_1-0]+\frac{1!1!}{3!}[E-d_1]+\frac{1!1!}{3!}[E-E]+\frac{2!0!}{3!}[E-E]=\frac{E+2d_1-d_2}{6}=50

\Phi_2(v)=\frac{0!2!}{3!}[d_2-0]+\frac{1!1!}{3!}[E-d_1]+\frac{1!1!}{3!}[E-E]+\frac{2!0!}{3!}[E-E]=\frac{E+2d_2-d_1}{6}=100

\Phi_3(v)=\frac{0!2!}{3!}[E-0]+\frac{1!1!}{3!}[E-d_1]+\frac{1!1!}{3!}[E-d_2]+\frac{2!0!}{3!}[E-E]=\frac{4E-d_1-d_2}{6}=150

The general idea behind this Talmudic law is therefore that “The division of the estate among the three creditors is such that any two of them divide the sum they together receive, according to the principle of equal division of the contested sum” (Aumann, 2002: 5). In Case 2 above, for instance, where E=200, P1 gets 50 and P2 gets 75, so that their claims add up to 125. Since P1’s claim is only for 100, he concedes 25 to P2, and the rest (‘contested sum’) is split equally between the two. While we can solve iteratively in this fashion, as the original rabbis likely did, the Shapley value provides a way to generalize this rule for any arbitrary estate size or number of creditors. And so, game theory has let us solve a thousand-year old mystery, in a shining example of its vast applicability.

Ex. 5: Shapley Decomposition for Portfolio Risk (Mussard & Terraza, 2008)

When analyzing a portfolio of financial assets it is very common to distinguish between idiosyncratic (within-security) risk  and systematic (between-security) risk , which correspond respectively to the left and right sides of the following formula for portfolio variance  (Mussard & Terraza, 2008: 713):

\sigma_p^2 = \sum\limits_{\substack{i=1}}^{n} \omega_i^2\sigma_i^2 + 2\sum\limits_{\substack{i=2}}^{n}\sum\limits_{\substack{j=1}}^{i-1} \omega_i\omega_j\text{cov}(r_i,r_j)

where ωi is the weight (amount invested) for asset i, σi2 is the variance of asset i, and cov(ri, rj) is the covariance between assets i and j. The problem with this formula is that while we can measure a given asset’s idiosyncratic risk (the left part), we cannot measure how much that asset contributes to the systematic risk, and thus cannot know its effect on the total portfolio variance. Happily, the Shapley value is ideally suited for this. Define F(ri, rj) ≡ ωiωjcov(ri, rj), so that F(ri) = ωi2cov(ri, ri) = ωi2σi2 and F(Ø) ≡ 0; this function acts like our value function v(S) used above. Let us use the Shapley value formula to get the risk contribution for the case of two-assets:

C_i=\sum\limits_{\substack{S\in{N}\\i\in{S}}} \frac{(|S|-1)!(n-|S|)!}{n!}[F(S)-F(S\backslash\{i\})]=\frac{1!0!}{2!}[F(r_i,r_j)-F(r_j)]+\frac{0!1!}{2!}[F(r_i)-F(\varnothing)]=\frac{1}{2}[F(r_i,r_j)-F(r_j)]+\frac{1}{2}F(r_i)

Once we do the same for Cj and sum, we get Ci + Cj = F(ri, rj) = ωiωjcov(ri, rj). Hence we can decompose the systematic risk—the right part of our above formula for portfolio variance—in terms of Ci + Cj:

\sigma_b^2 = 2\sum\limits_{\substack{i=2}}^{n}\sum\limits_{\substack{j=1}}^{i-1} \omega_i\omega_j\text{cov}(r_i,r_j) = 2\sum\limits_{\substack{i=2}}^{n}\sum\limits_{\substack{j=1}}^{i-1} (C_i+C_j)  →  \sigma_{bi}^2=2\sum\limits_{\substack{i=1}}^{n}C_i

The higher the amount of assets included in our portfolio, the more important the systematic risk becomes. An asset may not be very risky on its own, but the way it covaries with the other assets in our portfolio may make it a bad investment. Therefore the Shapley value can greatly help in making better investment decisions.

Insincerity, by versatis

Example 6: Fair Depreciation in Accounting (Ben-Shahar & Sulganik, 2009)

The Shapley value can also be used as a method of measuring depreciation in accounting. While this may seem odd at first, in determining depreciation across an asset’s useful life we want a method that “produces depreciation charges that directly depend on the asset’s generated earnings” for each period, and so “reflect the use of the asset in the revenue generating process” (Ben-Shahur & Sulganik, 2009: 9-10). In a creative twist, the ‘players’ in this cooperative game are actually the time periods of an asset’s useful life (ibid.). Thus we want to find a fair allocation of depreciation that matches the value created in a given time period.

Ben-Shahur & Sulganik propose an axiomatic system that any depreciation/amortization method must obey:

  • Axiom 1 – Positivity: di ≥ 0 ∀i ∈ [1, T] → Periodic depreciation must be non-negative
  • Axiom 2 – Upper Bound: \frac{y_i}{(1-r)^i}-d_i\geq0 ∀i ∈ [1,T] → di must be less than present value of earnings
  • Axiom 3 – Matching Principle: If \frac{y_i}{(1-r)^i}\leq\frac{y_j}{(1-r)^j} then \text{d}_i\leq\text{d}_j & \frac{y_i}{(1-r)^i}-d_i\leq\frac{y_j}{(1-r)^j}-d_ji,j ∈ [1,T] → Higher (equal) periodic present-value earnings must be associated with higher (equal) depreciation

where yi is earnings before interest and depreciation for t=i, r is cost of capital, and A is the asset’s depreciated cost. The Shapley formula is unchanged, but we specify that v(S) = \text{max}[\sum_{i\in{S}}\frac{y_i}{(1-r)^i} - A,\text{ 0}] ∀SØ, and v(Ø) = 0. Thus ϕi is period i’s “fair reward for its contribution to the total economic profit” (ibid., 5): d_i + \Phi_i = \frac{y_i}{(1-r)^i}.

We will show how the Shapley value satisfies the axioms for depreciation given above. To prove axioms 1 and 2, our definition of v(S) implies that the marginal contribution of period i can never exceed the present value of earnings in that period, so we know that \Phi_i\leq\frac{y_i}{(1-r)^i}. Since we’ve defined d_i + \Phi_i = \frac{y_i}{(1-r)^i}, this last inequality implies di ≥ 0 (Axiom 1). By our definition, v(S) is always non-negative, and so we know ϕi ≥ 0. Hence our definition of di implies that \frac{y_i}{(1-r)^i}-d_i\geq0 (Axiom 2). For axiom 3, we know by our definition of v(S) and the symmetry axiom that if \frac{y_i}{(1-r)^i}=\frac{y_j}{(1-r)^j} then ϕi = ϕj, and by our definition of di, we know di = dj. Similarly, if \frac{y_i}{(1-r)^i}<\frac{y_j}{(1-r)^j} then player i’s marginal contribution to each coalition can take one of three forms:

  • [v(S)-v(S\backslash\{i\})]=\sum\limits_{\substack{k=1}}^{i}\frac{y_k}{(1-r)^k}-A-[\sum\limits_{\substack{k=1}}^{i-1}\frac{y_k}{(1-r)^k}-A]=\frac{y_i}{(1-r)^i}
  • [v(S)-v(S\backslash\{i\})]=\sum\limits_{\substack{k=1}}^{i}\frac{y_k}{(1-r)^k}-A-0
  • [v(S)-v(S\backslash\{i\})]=0-0

(The others are ruled out since they make the marginal contribution negative, violating the additivity axiom.) Since \frac{y_i}{(1-r)^i}<\frac{y_j}{(1-r)^j}, then for any permutation where everything remains the same except i and j switch places, j’s marginal contribution is always larger than that of i, and consequently ϕi < ϕj. It follows that di < dj. The Shapley value therefore satisfies the depreciation axioms, and conforms to generally accepted accounting principles.

A special case (uncommon in practice) is where v(S) > 0 for all coalitions S, the Shapley value gives rise to the straight-line method for depreciation. Here it is helpful to recall Roth’s interpretation of the Shapley value as a probability. If i is first in the order for the grand coalition, its marginal contribution is \frac{y_i}{(1-r)^i}-A; otherwise its marginal contribution is \frac{y_i}{(1-r)^i}. Applying the Shapley formula for the case S = {i}, we get \frac{0!(T-1)!}{T!}=\frac{1}{T}. There are (T – 1) other places where i can be in the ordering, each having the same marginal contribution, giving:

\Phi_i=\frac{(\frac{y_i}{(1-r)^i}-A)+(T-1)\frac{y_i}{(1-r)^i}}{T}   →  \Phi_i = \frac{y_i}{(1-r)^i}-\frac{A}{T}

Our equation d_i + \Phi_i = \frac{y_i}{(1-r)^i}  →  \Phi_i = \frac{y_i}{(1-r)^i}-d_i thus implies that d_i = \frac{A}{T}, i.e. straight-line depreciation.

Ben-Shahur & Sulganik (2009: 7-14) provide a series of examples for different families of earnings flows, each of whose results (axiomatically) conform to generally accepted accounting principles. While the example itself may seem dull, it involves a highly creative interpretation of the Shapley value that underscores its versatility.

Example 7: Wine Ranking (Ginsburgh & Zang, 2012)

One of the quirkier applications of the Shapley value is as a superior method of ranking wines in contests. Different contests, even among the same wines, often have entirely different winners, and the results are quite sensitive to the specific method used in tallying the votes. These issues have led many aficionados to brand oenology as pseudoscience. However, Ginsburgh & Zang (2012) assert that such problems can be attributed not to the judges themselves, but to the ranking system. They point out, for instance, that very deep results in social choice theory such as Arrow’s impossibility theorem (see Tao, 1991) can be brought to bear on wine-ranking. The latter theorem proves that no realistic voting system can satisfy all of the following properties:

  • Consensus: If all voters prefer A to B, then the aggregate order ranks A above B.
  • Independence of Irrelevant Alternatives: The relative ranking of A and B in the aggregate order is independent of the voters’ preference for a new choice C.
  • No Dictator: No judge can impose his or her own ranking.

This is illustrated by Ginsburgh & Zang (2012: 170; slightly edited) for wine rankings as follows:

[C]onsider the following example of 3 wines A, B and C, and 60 judges. 23 rank A ≻ B ≻ C; 2 rank B ≻ A ≻ C; 17 rank B ≻ C ≻ A; 10 rank C ≻ A ≻ B; finally 8 rank C ≻ B ≻ A. Counting the ranks for each wine, adding them and then averaging, turns out to rank B first, A second & C third. Consider now pairs of candidate wines: A wins against B by 33 (=23+10) to 27 (=2+17+8); B wins against C by 42 to 18. Obviously, if A wins against B and B against C, it should be true that A is the winner. But C wins against A by 35 to 25, so C wins against A. This is an example of the Condorcet Paradox and non-transitive aggregate preferences…

The new ranking system the authors propose is this: each judge votes for a subgroup Sj of the n wines that they consider a viable candidate for first place, where |Sj| ≡ sj and 0 < sj ≤ n. Each judge gets the fraction 1/sj of one vote. The latter requirement helps to avoid the problem of some judges being more generous than others—that is, if one judge tends to vote between 6/10 and 9/10, in some voting systems they may have more influence over the outcome than a judge who votes between 4/10 and 7/10. Instead, here the judge’s total vote is diluted over the number of wines they elect for their subgroup. It turns out that after we sum up the 1/sj votes given by each judge, the (unique) result equals the Shapley value for that wine.

To see this, consider the choice made by judge j ∈ J as a subgame with sub-Shapley value ϕj(i) for wine i. Let W be a nonempty subset of wines in N, and Sj ⊆ N be the subset of wines chosen by judge j.

Our value function is v(W) =\begin{cases} 1, & \text{if }W\subseteq\text{S}_j \\ 0, & \text{otherwise}\end{cases}

By efficiency, \sum_{i\in{N}} \Phi_j(i) = v(N) = 1. We can split this into \sum_{i\in{N}} \Phi_j(i) = \sum_{i\in{S}} \Phi_j(i) + \sum_{i\notin{S}} \Phi_j(i) = 1.

By the dummy axiom, ϕj(i) = 0 if i ∉ S, so that \sum_{i\notin{S}} \Phi_j(i) = 0.

By the symmetry axiom, if both i and k are in Sj, then ϕj(i) = ϕj(k), which implies \sum_{i\in{S}} \Phi_j(i) = |S_j|\Phi_j(i).

So \sum_{i\in{N}} \Phi_j(i) = |S_j|\Phi_j(i) + 0 = 1  →  \Phi_j(i) = \frac{1}{|S_j|}. This is exactly the same as giving each judge \frac{1}{s_j} votes, since |Sj| ≡ sj.

Bringing in the other judges, we see that the full game is the sum of all the subgames (Ginsburgh & Zang, 2003: 324).

And by additivity, we know that the sub-values add to the full Shapley value: \Phi_i(v) = \sum_{j\in{J}} \Phi_j(i) = \sum_{j\in{J}}\frac{1}{|S_j|}.

Conclusion

Beginning from first principles, we have seen how the Shapley value applies to a wealth of applications, from accounting and politics to reality TV shows and thousand-year old Talmudic mysteries. We have seen how the relative simplicity of its mathematics lets us redefine notions such as ‘players’ and ‘fairness’ in unexpectedly creative ways. So while the Shapley value cannot tell us everything about a scenario, it helps us to reach a point between fact and norm, between structure and agency, that intuitive reasoning can seldom reach on its own.

.

References

  • Aumann, R. (2002). “Game Theory in the Talmud.” Jewish Law and Economics 4(2), pp. 1-11
  • Aumann, R. (2005). “An Interview with Robert Aumann.” Macroeconomic Dynamics 9, pp. 683-740
  • Ben-Shahur, D. & Sulganik, E. (2009). “Fair Depreciation: A Shapley Value Approach.” The B.E. Journal of Theoretical Economics 9(1), pp. 1-16
  • Ferguson, T. (2014). Game Theory, 2nd Ed. Unpublished textbook. Retrieved from http://www.math.ucla.edu/~tom/Game_Theory/Contents.html
  • Ginsburgh, V. & Zang, I. (2012). “The museum pass game and its value.” Games & Economic Behaviour 43, pp. 322-5
  • Ginsburgh, V. & Zang, I. (2012). “Shapley Ranking of Wines.” Journal of Wine Economics 7(2), pp. 169-80
  • Guiasu, S. (2011). “Three ancient problems solved by using the game theory logic based on the Shapley value.” Synthese 181, pp. 65-79
  • Mussard, S. & Terraza, V. (2008). “The Shapley Decomposition for Portfolio Risk.” Applied Economics Letters 15, pp. 713-5
  • Roth, A. (1988). “Introduction to the Shapley value,” in Roth, A. (Ed.). (1988). The Shapley Value: Essays in Honor of Lloyd S. Shapley. New York: Cambridge University Press, pp. 1-27
  • Serrano, R. (2008). “Nash Program,” in Durlauf, S. & Blume, L. (2008). The New Palgrave Dictionary of Economics, 2nd Ed. London: Palgrave-Macmillan.
  • Serrano, R. (2013). “Lloyd Shapley’s Matching and Game Theory.” Scandinavian Journal of Economics 115(3), pp. 599-618
  • Shapley, L. [1953]. “A value for n-person games,” in Roth, A. (Ed.). (1988). The Shapley Value: Essays in Honor of Lloyd S. Shapley. New York: Cambridge University Press, pp. 31-40
  • Shapley, L. (1981). “Measurement of power in political systems,” in Lucas, W. (Ed.). Game Theory & its Applications: Proceedings of Symposia in Applied Mathematics, vol. 24. Providence, RI: American Mathematical Society, pp. 69-81.
  • Shapley, L. & Shubik, M. (1954). “A method for evaluating the distributions of power in a committee system.” The American Political Science Review 48(3), pp. 787-92
  • Soukenik, K. (2001). “Shapley value predicts the distribution of EU expenditure among member states.” Journal of European Integration 23(2), pp. 165-98
  • Tao, T. (1991). “Arrow’s Theorem.” Working Paper. Retrieved from http://www.math.ucla.edu/~tao/arrow.pdf
  • Wang, S. (2007). “Operations Research Lecture Notes – Game Theory.” Unpublished Lecture Notes. Retrieved from staffhome.ecm.uwa.edu.au/~00028221/courses/2OR/gametheory.pdf
  • Winter. E. “The Shapley Value,” in Aumann, R. & Hart, S. (Eds.). (2002). Handbook of Game Theory, vol. 3. North Holland: Elsevier Science, pp. 2025-52

.

Advertisements

About Graham Joncas

We are a way for capital to know itself.

Posted on June 9, 2015, in Economics, Finance, Game Theory, Mathematics and tagged , , , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: