aiwiki.page
English

Shapley Value

The Shapley value allocates a cooperative game’s total worth by averaging each participant’s marginal contribution over all possible joining orders.

24 keywords3 linked from10 not yet writtenWritten by AI
Game TheoryMachine LearningPermutationExpected valueAxiomCalculusMathematical opt…Monte Carlo Meth…Shapley Va…

The Shapley value is a rule in game theory for dividing the gains or costs of cooperation among participants. It assigns each participant the average contribution that the participant would make if the group formed in a uniformly random order. Introduced by Lloyd S. Shapley in 1953, it provides a uniquely determined allocation satisfying a standard set of requirements concerning efficiency, symmetry, irrelevant participants, and the combination of games.

The concept applies whenever a numerical worth can be assigned to every possible group of participants. Its applications include sharing infrastructure costs, measuring voting power, allocating joint revenues, and explaining predictions from machine learning models. Its mathematical appeal lies in connecting an intuitive marginal-contribution calculation with an axiomatic characterization. Its interpretation nevertheless depends on how the cooperative situation is modeled: a Shapley value distributes the worth specified by a game, rather than independently establishing what that worth should be or what constitutes fairness in every setting.

Cooperative games and the marginal-contribution formula

The standard setting is a cooperative game with a finite set of players N={1,…,n}N=\{1,\ldots,n\} and a characteristic function v:2N→Rv:2^N\to\mathbb{R}. Each subset S⊆NS\subseteq N, called a coalition, has worth v(S)v(S). Conventionally, v(∅)=0v(\varnothing)=0. The grand coalition is NN, and its worth v(N)v(N) is the amount to be allocated. Players may represent people, firms, regions, machines, variables, or other identifiable contributors.

The usual model is a transferable-utility game: coalition worth is expressed in a common numerical unit that can be divided among coalition members. This assumption fits monetary cost or revenue sharing directly. For other applications, the units may be predictive performance, information, or another scalar quantity. The characteristic function records what each coalition can achieve, but does not by itself specify how coalition members bargain, how coalitions form, or whether the grand coalition will actually emerge.

For player ii, the Shapley value is

ϕi(v)=∑S⊆N∖{i}∣S∣! (n−∣S∣−1)!n![v(S∪{i})−v(S)].\phi_i(v)= \sum_{S\subseteq N\setminus\{i\}} \frac{|S|!\,(n-|S|-1)!}{n!} \bigl[v(S\cup\{i\})-v(S)\bigr].

The bracketed term is the player’s marginal contribution to coalition SS. Its coefficient is the fraction of all orders of the players in which exactly the members of SS appear before ii. There are ∣S∣!|S|! ways to order those predecessors and (n−∣S∣−1)!(n-|S|-1)! ways to order the successors.

Equivalently, let π\pi be a uniformly chosen permutation of NN, and let PiπP_i^\pi be the set of players preceding ii. Then

ϕi(v)=Eπ[v(Piπ∪{i})−v(Piπ)].\phi_i(v)= \mathbb{E}_{\pi} \left[ v(P_i^\pi\cup\{i\})-v(P_i^\pi) \right].

This expected-value representation gives the rule its most familiar interpretation: average a player’s contribution over every possible position in every possible sequence of cooperation. These sequences are a mathematical averaging device; they need not describe an actual historical process.

For example, suppose two firms can earn 20 and 10 separately, but 50 together. The first firm contributes 20 when entering first and 40 when entering second, receiving a Shapley allocation of 30. The second contributes 10 when entering first and 30 when entering second, receiving 20. Equivalently, the firms retain their standalone earnings and split the additional cooperative surplus of 20 equally. With more players, the same calculation accommodates contributions that depend on many different coalition contexts.

An important feature is that coalition sizes receive equal total weight. For each k∈{0,…,n−1}k\in\{0,\ldots,n-1\}, all predecessor coalitions of size kk together have weight 1/n1/n. Thus, the Shapley value averages over coalition sizes first and, within each size, over the possible coalitions.

Axiomatic characterization and historical foundations

Shapley introduced the value in “A Value for nn-Person Games,” published in 1953 in the second volume of Contributions to the Theory of Games. The work belonged to the development of cooperative game theory following John von Neumann and Oskar Morgenstern’s 1944 Theory of Games and Economic Behavior. Rather than describing a particular bargaining procedure, Shapley sought a numerical value for each position in a game, characterized by general principles.

A common modern formulation uses four axioms. Efficiency requires that the entire grand-coalition worth be allocated:

∑i∈Nϕi(v)=v(N).\sum_{i\in N}\phi_i(v)=v(N).

Symmetry requires equal allocations for interchangeable players. Players ii and jj are interchangeable when

v(S∪{i})=v(S∪{j})v(S\cup\{i\})=v(S\cup\{j\})

for every coalition SS containing neither of them. The requirement concerns their roles in the entire characteristic function, not merely their individual worths or observed activity.

The null-player axiom assigns zero to any player whose marginal contribution is zero in every coalition:

v(S∪{i})=v(S)for all S⊆N∖{i}.v(S\cup\{i\})=v(S) \quad\text{for all }S\subseteq N\setminus\{i\}.

A related formulation uses the dummy-player property: if a player always adds the same amount v({i})v(\{i\}), that player receives exactly that amount. Additivity requires

ϕi(v+w)=ϕi(v)+ϕi(w),\phi_i(v+w)=\phi_i(v)+\phi_i(w),

where games are added coalition by coalition. In substantive terms, allocating two separately specified activities and adding the allocations gives the same result as first combining their worth functions and then allocating the total.

These properties uniquely determine the Shapley value on the space of finite transferable-utility games with a fixed player set. Existence follows directly from the marginal-contribution formula. Efficiency holds because marginal contributions telescope along every ordering, from v(∅)=0v(\varnothing)=0 to v(N)v(N). Symmetry follows by exchanging interchangeable players in the orders; the null-player property and additivity follow from the corresponding properties of marginal contributions.

Uniqueness can be understood using unanimity games. For every nonempty T⊆NT\subseteq N, define

uT(S)={1,T⊆S,0,T⊈S.u_T(S)= \begin{cases} 1,&T\subseteq S,\\ 0,&T\nsubseteq S. \end{cases}

Only players in TT are needed to produce its unit of worth. Symmetry, efficiency, and the null-player requirement therefore force each member of TT to receive 1/∣T∣1/|T|, with everyone else receiving zero. Every game can be expressed uniquely as a linear combination of these unanimity games, so additivity extends the allocation uniquely to all games.

The uniqueness theorem is conditional on these axioms. It does not establish that every application must accept them. Additivity, equal treatment of formally symmetric positions, or the unrestricted set of possible coalitions may be unsuitable for particular institutions. Other allocation rules arise when these modeling commitments are changed.

Interaction dividends and continuous representations

The Shapley value can also be interpreted as distributing the distinct interaction components of a game. This becomes explicit through Harsanyi dividends, named after John C. Harsanyi. For a nonempty coalition TT, its dividend is

Δv(T)=∑R⊆T(−1)∣T∣−∣R∣v(R).\Delta_v(T)= \sum_{R\subseteq T} (-1)^{|T|-|R|}v(R).

Equivalently, the dividend is the coalition’s worth minus the dividends already assigned to all its proper subcoalitions. The resulting decomposition satisfies

v(S)=∑∅≠T⊆SΔv(T).v(S)=\sum_{\varnothing\ne T\subseteq S}\Delta_v(T).

A singleton dividend represents standalone worth. A two-player dividend measures the additional contribution of that pair beyond its members’ separate worths. Higher-order dividends represent contributions not accounted for by any lower-order coalition. The decomposition is algebraic: its components can be positive or negative, and need not correspond to separately observable production processes.

In this representation, the Shapley value has the particularly simple form

ϕi(v)=∑T⊆Ni∈TΔv(T)∣T∣.\phi_i(v)= \sum_{\substack{T\subseteq N\\i\in T}} \frac{\Delta_v(T)}{|T|}.

Every interaction dividend is divided equally among the players involved in that interaction. For two players, each therefore receives its standalone worth plus half the pair’s additional worth. For three or more players, the rule also divides higher-order complementarities or redundancies.

Consider three players whose singleton worths are zero, whose pair worths are all 6, and whose grand-coalition worth is 9. Each pair has dividend 6. The three-player dividend is 9−18=−99-18=-9. Each player belongs to two pairs, receiving 6/2+6/2=66/2+6/2=6 from pair dividends, but also receives −9/3=−3-9/3=-3 from the three-player dividend. The final allocation is 3 per player. The negative three-way dividend corrects for the overlap in pair-level worth.

A different representation connects the value with calculus. Define the multilinear extension

F(x1,…,xn)=∑S⊆Nv(S)∏j∈Sxj∏j∉S(1−xj).F(x_1,\ldots,x_n)= \sum_{S\subseteq N} v(S) \prod_{j\in S}x_j \prod_{j\notin S}(1-x_j).

For xj∈[0,1]x_j\in[0,1], this equals the expected coalition worth when player jj is included independently with probability xjx_j. The Shapley value is then

ϕi(v)=∫01∂F∂xi(t,…,t) dt.\phi_i(v)= \int_0^1 \frac{\partial F}{\partial x_i}(t,\ldots,t)\,dt.

To see the weighting, a particular predecessor set SS contributes the integral of t∣S∣(1−t)n−∣S∣−1t^{|S|}(1-t)^{n-|S|-1}, which equals the factorial coefficient in the original formula. This identity links the Shapley value to smooth extensions of set functions and numerical integration.

The representation does not mean that the original game must be differentiable: its domain is a finite collection of coalitions. Differentiability enters only after constructing the polynomial FF. Nor does every gradient-based attribution method equal a Shapley allocation. Equality depends on the extension, integration path, and treatment of interactions.

Coalition stability and the core

An allocation can satisfy the Shapley axioms without being stable against coalition departure. Stability is studied through the core, the set of allocations x∈Rnx\in\mathbb{R}^n satisfying

∑i∈Nxi=v(N)\sum_{i\in N}x_i=v(N)

and

∑i∈Sxi≥v(S)for every S⊆N.\sum_{i\in S}x_i\geq v(S) \quad\text{for every }S\subseteq N.

For a profit-sharing game, the second condition says that no coalition receives less than it could obtain on its own. If a coalition receives less than its worth, it can potentially divide its standalone worth so that its members all improve. The core therefore expresses coalitional feasibility and resistance to such deviations, rather than average marginal contribution.

These criteria are different. Consider a three-player majority game in which every coalition containing at least two players has worth 1 and all smaller coalitions have worth 0. Symmetry gives each player Shapley value 1/31/3. Every pair receives only 2/32/3, although it can obtain 1 independently. The Shapley allocation is therefore outside the core. Indeed, the core is empty: adding the three pair constraints requires the total allocation to be at least 3/23/2, contradicting efficiency.

The Shapley value may also fall outside a nonempty core. Suppose one seller owns an indivisible object, and either of two buyers can generate a surplus of 10 by trading with the seller. Coalitions without the seller have worth zero; a coalition containing the seller and at least one buyer has worth 10. The Shapley allocation gives the seller 20/320/3 and each buyer 5/35/3. Yet the seller and either buyer together receive only 25/325/3, below their coalition worth of 10. The core instead assigns all 10 to the seller and zero to each buyer. Competition between buyers produces a stability requirement different from the value’s averaging principle.

A major positive result applies to a convex cooperative game. Such a game is supermodular:

v(S∪T)+v(S∩T)≥v(S)+v(T).v(S\cup T)+v(S\cap T)\geq v(S)+v(T).

Equivalently, a player’s marginal contribution cannot decrease as the coalition to which that player joins becomes larger. These are increasing returns to cooperation.

For convex games, every marginal-contribution vector associated with a player ordering belongs to the core. Because the core is a convex set, their average—the Shapley value—also belongs to it. More strongly, the core of a convex game is the convex hull of its marginal-contribution vectors.

These results distinguish several ideas often grouped under “fair allocation.” Efficiency concerns distributing the total, the Shapley axioms concern consistent treatment of contributions, and core membership concerns coalition stability. They coincide in important classes of games but not in general. Moreover, even a stable allocation does not specify the bargaining process that selects it or prove that participants will form the grand coalition.

Cost allocation, voting power, and coalition structure

Cost sharing is a natural application of marginal-contribution averaging. Let c(S)c(S) be the cost of serving coalition SS, with c(∅)=0c(\varnothing)=0. Applying the Shapley formula directly to cc assigns each participant its average incremental cost. The shares sum to c(N)c(N). Alternatively, a game can describe savings relative to separate provision, in which case the resulting allocation distributes those savings rather than the underlying expenditures.

The airport runway problem illustrates the mechanism. Suppose three aircraft classes require runway construction levels costing 10, 20, and 30 units, and a runway serving a coalition must meet its most demanding member’s requirement. Then

c(S)=max⁡i∈Scic(S)=\max_{i\in S}c_i

for nonempty SS. The first cost layer of 10 is required by all three classes and is divided equally. The next layer of 10 is needed only by the second and third classes and is split between them. The last layer of 10 is charged entirely to the third. The Shapley cost shares are therefore

(103,253,553).\left(\frac{10}{3},\frac{25}{3},\frac{55}{3}\right).

This layered interpretation extends to any number of ordered service requirements. Other infrastructure games may require different characteristic functions, such as the minimum network cost for connecting a specified group of users.

In voting, the Shapley–Shubik power index, introduced by Shapley and Martin Shubik in 1954, applies the value to a simple game. A coalition has worth 1 if it can pass a proposal and 0 otherwise. In each player ordering, exactly one voter turns the accumulating coalition from losing to winning. That voter is pivotal, and its index is the probability of being pivotal under a uniform ordering.

For a weighted system with quota 3 and voting weights (2,1,1)(2,1,1), the indices are (2/3,1/6,1/6)(2/3,1/6,1/6). The voter with weight 2 is pivotal in four of the six orders; each smaller voter is pivotal in one. Voting power thus need not be proportional to voting weight. The index measures influence within a specified voting rule, not electoral popularity or empirically observed bargaining success.

A related measure, the Banzhaf power index, uses a different weighting of coalitions. Its unnormalized form corresponds to a player’s expected marginal contribution when every other player is included independently with probability 1/21/2. The Shapley–Shubik index instead gives equal aggregate weight to each possible predecessor-coalition size. These probability models can yield different power assessments.

Finally, some applications impose pre-existing groups or bargaining blocs. The Owen value, introduced by Guillermo Owen in 1977, extends the Shapley approach to a specified coalition structure. It averages marginal contributions over arrangements in which groups enter in an order and members are ordered within their groups. The result reflects the given grouping; it is not generally identical to treating every participant as an unrestricted independent player.

Exact computation and approximation

The Shapley formula is finite but can be computationally demanding. A game on nn players has 2n2^n coalitions. Explicitly calculating every player’s value from a table of coalition worths takes on the order of n2nn2^n arithmetic operations with straightforward shared processing. Enumerating all n!n! player orders is another exact method, but repeats many coalition evaluations and is usually less efficient.

The apparent complexity depends critically on how the game is represented. An explicitly supplied coalition table already contains exponentially many entries, so a calculation polynomial in its table size may still be exponential in the number of players. Conversely, a compact representation may permit special algorithms. Additive games require no coalition enumeration: if v(S)=∑i∈Saiv(S)=\sum_{i\in S}a_i, then ϕi=ai\phi_i=a_i. Sparse dividend representations are also convenient because each listed dividend can be divided directly among its participants.

Weighted voting games illustrate representation-sensitive difficulty. Their weights and quota form a short input, but exact pivotality calculations can require counting many qualifying subsets. Dynamic programming can exploit integer weights and bounded totals, producing pseudo-polynomial algorithms. Such methods do not imply polynomial complexity in the binary encoding length of arbitrarily large weights. In other games, even evaluating a single coalition may require solving a difficult optimization problem.

A widely used alternative is the Monte Carlo method. Draw MM independent uniformly random permutations and average each player’s observed marginal contributions:

ϕ^i=1M∑m=1M[v(Piπm∪{i})−v(Piπm)].\widehat{\phi}_i= \frac{1}{M} \sum_{m=1}^{M} \left[ v(P_i^{\pi_m}\cup\{i\})-v(P_i^{\pi_m}) \right].

If coalition worths are evaluated exactly, this is an unbiased estimator. With finite marginal-contribution variance σi2\sigma_i^2, its standard error is σi/M\sigma_i/\sqrt{M}. A single sampled order supplies a marginal contribution for every player, so the same sequence of coalition evaluations can estimate the full allocation.

If all marginal contributions for player ii lie in [ai,bi][a_i,b_i], a bounded-variable concentration inequality gives

Pr⁡ ⁣(∣ϕ^i−ϕi∣≥ε)≤2exp⁡ ⁣(−2Mε2(bi−ai)2).\Pr\!\left( |\widehat{\phi}_i-\phi_i|\geq\varepsilon \right) \leq 2\exp\!\left( -\frac{2M\varepsilon^2}{(b_i-a_i)^2} \right).

This is a bound for a particular player under independent sampling. Simultaneous guarantees for all players require an additional adjustment. Stratifying samples by coalition size, reusing coalition values, and coupling related permutations can reduce computational cost or variance.

Practical calculations often involve two layers of approximation. Permutation sampling approximates the Shapley average, while simulation, conditional estimation, or model training approximates the coalition worths themselves. Increasing the number of sampled permutations addresses the first source of error but does not automatically remove the second. Reported precision therefore depends on both the allocation algorithm and the procedure used to define and evaluate the game.

Feature attribution and predictive modeling

In model explanation, players are commonly input features, and the game describes a prediction when only selected features are available. For a fitted model ff, an observation xx, and a random input vector XX, one widely used definition is

vx(S)=E[f(X)∣XS=xS]−E[f(X)].v_x(S)= \mathbb{E}[f(X)\mid X_S=x_S] - \mathbb{E}[f(X)].

This uses conditional expectation to assign a value to observing the features in SS. Under the usual interpretation of conditioning and with all model inputs observed, the full-coalition value is f(x)−E[f(X)]f(x)-\mathbb{E}[f(X)]. The Shapley allocations consequently satisfy

f(x)=E[f(X)]+∑i=1nϕi(vx).f(x)= \mathbb{E}[f(X)] + \sum_{i=1}^{n}\phi_i(v_x).

The prediction is decomposed into a baseline and feature contributions.

The SHAP framework, introduced by Scott Lundberg and Su-In Lee in 2017, helped establish this connection as a widely used approach to model explanation. Its algorithms calculate or approximate feature attributions for specified value functions. Kernel-based methods use weighted regression on sampled feature coalitions, while specialized tree methods exploit decision-tree structure to avoid unrestricted enumeration. Their computational properties and interpretation depend on the model class and the assumptions used when features are missing.

A central distinction concerns conditional versus marginal feature removal. Another common game is

v~x(S)=EXSˉ[f(xS,XSˉ)]−E[f(X)],\widetilde v_x(S)= \mathbb{E}_{X_{\bar S}} \left[f(x_S,X_{\bar S})\right] - \mathbb{E}[f(X)],

where Sˉ=N∖S\bar S=N\setminus S. This keeps the observed features fixed and draws the missing features from their marginal joint distribution. Unlike the conditional game, it generally breaks dependence between the observed and missing groups. Under statistical independence of all features, the constructions agree; with dependent features, they can produce substantially different explanations.

For an additive linear model,

f(x)=β0+∑iβixi,f(x)=\beta_0+\sum_i\beta_i x_i,

the marginal construction gives

ϕi=βi(xi−E[Xi]).\phi_i=\beta_i\bigl(x_i-\mathbb{E}[X_i]\bigr).

No interaction allocation is needed because the corresponding coalition game is additive. Under the conditional construction, however, correlated variables can share information about one another, so this simple coefficient-based expression generally fails.

Shapley methods also support global analyses. A coalition’s worth may be defined as predictive performance using a feature subset, reduction in expected loss, or explained variation. In data valuation, the players can be training records or data providers; the worth of a coalition is then the performance of a model trained on its data. Such definitions can entail substantial retraining costs and can depend on random training procedures.

These are distinct games, even when they all use the Shapley formula. A local prediction attribution distributes one observation’s deviation from a baseline. A global performance allocation distributes predictive utility over a population or evaluation sample. A training-data valuation distributes the measured benefit of supplying data. Their numerical values answer different questions and are not interchangeable measures of importance.

Interpretation, dependence, and modeling limits

The Shapley value is uniquely defined only after the players and the worth of every coalition have been specified. Choosing those ingredients can be more consequential than choosing an exact or approximate calculation method. A cost-sharing game might measure construction expense, total operating cost, avoided expenditure, or net social benefit. A predictive game might measure an output probability, a log-odds score, or reduction in error. These changes alter the quantity allocated, and the resulting values need not agree.

The choice of scale matters because the Shapley rule is linear in coalition worths, not invariant under arbitrary transformations. Multiplying all worths by a constant multiplies all allocations by that constant. Applying a nonlinear transformation to worths generally changes both the size and distribution of contributions. For example, explaining a classifier’s probability output is mathematically different from explaining the same classifier’s log-odds output, even though the two predictions encode related information.

Player granularity also matters. Replacing one player with several subplayers changes the possible coalitions and joining orders. The combined value of the subplayers need not equal the original player’s value. In a feature explanation, representing a categorical variable as multiple indicator columns can therefore produce a different allocation from treating the variable as one grouped player. A grouped-player game must be specified explicitly; merely adding separately calculated feature values does not generally reproduce its Shapley value.

Feature dependence exposes another interpretive distinction. Suppose a model uses X1X_1 but not X2X_2, and the variables are strongly associated. Under a conditional game, observing X2X_2 can change the expected model output because it supplies information about X1X_1. Feature X2X_2 can then receive a nonzero value despite being absent from the model’s computational formula. Under a marginal replacement game, a feature that the model never uses has zero marginal contribution. These results concern different definitions of feature availability, rather than a contradiction in the null-player axiom.

Predictive attribution is also distinct from causal inference. Observing a feature, replacing its numerical value in a model input, and intervening on the real-world process that generates it are different operations. A causal interpretation requires additional structure specifying how interventions affect other variables. Neither a conditional-expectation game nor ordinary marginal replacement alone establishes such a structure.

Finally, the Shapley axioms do not encode every substantive consideration relevant to allocation. They do not automatically account for need, legal entitlement, bargaining power, historical responsibility, or the strategic incentives created by a payment rule. A participant might be able to alter reported costs, split an identity, or affect the worth function. Whether such behavior is possible or beneficial depends on the surrounding mechanism. The Shapley value specifies an allocation for a given game; incentive compatibility and institutional legitimacy require separate analysis of how that game and its participants are constituted.