The Shapley Value

The Shapley value answers a question that has no obvious answer: a group of n agents cooperating produces a surplus v(N); how much of it belongs to each agent? Its answer is each agent’s average marginal contribution, taken over all n! orders in which the grand coalition could have formed. What elevates that from one plausible formula among many is a uniqueness theorem: it is the only rule satisfying a short list of axioms. This note is written from the original — Lloyd Shapley’s A Value for n-Person Games, pages 307–317 of Contributions to the Theory of Games, Volume II (Annals of Mathematics Studies 28), eds. Kuhn & Tucker, Princeton 1953 — read here from a scanned copy on the Internet Archive, including page images where the OCR was unreliable. Reading the original corrects two things nearly every secondary account gets wrong: Shapley states three axioms, not four (the null-player property is a lemma, derived, not assumed), and the famous “random arrival order” story is not the definition — it appears in the paper’s final section as an afterthought, introduced with the admission that “the deductive approach of the earlier sections has failed to suggest a bargaining procedure which would produce the value of the game as the (expected) outcome.” Everything below is computed exactly with fractions.Fraction, cross-checked against Shapley’s own published numbers, and — for the sampling approximation — measured with error bars.

Mental Model: The Room That Fills Up One Person at a Time

Imagine the grand coalition assembling in an empty room. Members arrive one at a time in a uniformly random order. Each arrival is paid exactly the amount by which their arrival raises the room’s worth. Your Shapley value is your expected payment.

flowchart LR
    subgraph orders["All 3! = 6 arrival orders, each with probability 1/6"]
        O1["a, b, c"]
        O2["a, c, b"]
        O3["b, a, c"]
        O4["b, c, a"]
        O5["c, a, b"]
        O6["c, b, a"]
    end
    orders --> M["for each order, agent i is paid<br/><b>v(predecessors + i) - v(predecessors)</b>"]
    M --> AVG["average over the 6 orders"]
    AVG --> PHI["phi_a, phi_b, phi_c<br/><i>sums exactly to v(a,b,c)</i>"]
    style PHI fill:#dcfce7

What it shows: the arrival-order construction of the Shapley value for three agents. The insight: the payment is a telescoping sum along each order — down any single order the payments sum to v(N) exactly, because (v(S₁)−v(∅)) + (v(S₂)−v(S₁)) + … + (v(N)−v(S_{n−1})) collapses. Efficiency is therefore not an extra condition imposed on the average; it is inherited from every single ordering.

The reason a value is needed at all is that the more obvious solution concept fails. The core of a cooperative game is the set of payoff splits no coalition wants to defect from; as Nisan et al.’s Algorithmic Game Theory, §15.6 puts it, the core “rarely assigns a unique cost allocation to a game: … often either empty (making it useless in deciding how the cost of a service should be shared among the agents), or contains more than one point (making it necessary to have a second criterion).” The Shapley value is defined for every game, and always returns exactly one answer. It buys that at a price — sometimes it returns an answer nobody will accept — which is the subject of a later section.

The naive fix — pick one order, charge everyone their marginal cost — is called incremental cost sharing, and its flaw is that “the ordering of the agents makes a difference in the amount they will be charged,” i.e. it is not anonymous (AGT §15.6.1). The Shapley value is precisely the fix of averaging that arbitrariness away.

The Setup and the Formula, Symbol by Symbol

A transferable-utility (TU) cooperative game is a pair (N, v):

N = {1, …, n}, the players.
v : 2^N → ℝ, the characteristic function, with v(∅) = 0. v(S) is the worth that coalition S can secure on its own, in units of a freely transferable good (money). “Transferable utility” is the substantive assumption: the coalition’s proceeds can be split arbitrarily among its members without loss.

Shapley’s own definition is more general than the textbook one and worth seeing. He works over a possibly infinite universe of players U and defines a game as any superadditive set function v with v(∅) = 0 and v(S) ≥ v(S ∩ T) + v(S − T). He then introduces a carrier: a set N ⊆ U with v(S) = v(N ∩ S) for all S. The players outside a carrier “have no direct influence on the play since they contribute nothing to any coalition.” As he writes, “the use of carriers obviates the usual classification of games according to the number of players.” This is the device that lets his efficiency axiom quietly do the work of a null-player axiom, as shown below.

The value formula, as printed at equation (13) on page 312:

                    φ_i[v] = Σ_{S ⊆ N, S ∋ i}  γ_n(s) · [ v(S) − v(S − {i}) ]

with                γ_n(s) = (s − 1)! (n − s)! / n!

Symbol by symbol:

i is the player being valued; N is any finite carrier; n = |N|.
S ranges over coalitions that contain i. (The modern textbook form indexes over S ⊆ N \ {i} and writes the weight as s!(n−1−s)!/n! — the same thing after the substitution S ↦ S ∪ {i}.)
s = |S|.
v(S) − v(S − {i}) is i’s marginal contribution to S: what the coalition gains by admitting i last.
γ_n(s) = (s−1)!(n−s)!/n! is the probability that, in a uniformly random ordering of N, the set of players weakly preceding-and-including i is exactly S. There are (s−1)! ways to order the s−1 players ahead of i, (n−s)! ways to order those behind, and n! orderings in total.

The weights sum to 1 over each player, which is why the formula is an expectation rather than merely a weighted sum. A useful sanity identity, verified against the SHAP library’s source, is

# shap/utils/_general.py
def shapley_coefficients(n):
    out = np.zeros(n)
    for i in range(n):
        out[i] = 1 / (n * scipy.special.comb(n - 1, i))
    return out

1 / (n · C(n−1, s)) and s!(n−1−s)!/n! are algebraically identical, since C(n−1,s) = (n−1)!/(s!(n−1−s)!). A production ML library and a 1953 Annals of Mathematics Study are computing the same coefficient — worth checking once, because a great deal of confusion about SHAP evaporates once you see it is exactly this formula with a particular v.

flowchart TB
    subgraph two["Two equivalent readings of the same number"]
        A["<b>Combinatorial</b><br/>sum over 2^(n-1) subsets S not containing i,<br/>weight s!(n-1-s)!/n!<br/><i>cost: O(2^n) evaluations of v</i>"]
        B["<b>Probabilistic</b><br/>expected marginal contribution<br/>over a uniformly random arrival order<br/><i>cost: O(n!) if enumerated, O(n) per sample</i>"]
    end
    A <-->|"identical value;<br/>2^n is the cheaper route"| B
    A --> C["<b>Axiomatic</b><br/>the unique phi satisfying<br/>symmetry + efficiency + additivity<br/><i>Shapley 1953, Theorem</i>"]
    B --> C
    style C fill:#dbeafe

What it shows: three ways to arrive at the same vector of numbers. The insight: the probabilistic reading is the intuition, the combinatorial reading is the algorithm (2^n beats n! badly — see the timings below), and the axiomatic reading is the justification. Confusing the intuition for the justification is how people end up defending the Shapley value by saying “it averages over orderings,” which is a description, not an argument.

The Axioms and the Uniqueness Theorem

Here is the correction that reading the original buys. Nearly every treatment lists four axioms — efficiency, symmetry, null player, additivity. Shapley states three, verbatim from page 309:

AXIOM 1. For each π in Π(U), φ_{πi}[πv] = φ_i[v]. AXIOM 2. For each carrier N of v, Σ_N φ_i[v] = v(N). AXIOM 3. For any two games v and w, φ[v + w] = φ[v] + φ[w].

And his own gloss, also verbatim:

COMMENTS. The first axiom (“symmetry”) states that the value is essentially a property of the abstract game. The second axiom (“efficiency”) states that the value represents a distribution of the full yield of the game. This excludes, for example, the evaluation φ_i[v] = v({i}), in which each player pessimistically assumes that the rest will all cooperate against him. The third axiom (“law of aggregation”) states that when two independent games are combined, their values must be added player by player. […] It is remarkable that no further conditions are required to determine the value uniquely.

Read what each one actually says:

Symmetry (Axiom 1) is stated as invariance under relabelling: permute the players and the values permute with them. The textbook version (“two players with identical marginal contributions to every coalition get equal shares”) is a consequence, not the statement. Shapley’s point is philosophical — the value depends only on the abstract game, on the roles (“dealer,” “visiting team”) and not on who occupies them.
Efficiency (Axiom 2) is stated over carriers, not over N alone: for every carrier the values sum to v(N). This is stronger than budget balance and it is where the null-player property comes from.
Additivity (Axiom 3), which Shapley calls the “law of aggregation,” is the one people find least obviously desirable and it is the one doing the mathematical heavy lifting. His justification is forward-looking: it “is a prime requisite for any evaluation scheme designed to be applied eventually to systems of interdependent games” — you want to be able to value a portfolio of games by valuing each and adding.

The null-player property is Lemma 1, not an axiom. On the same page:

LEMMA 1. If N is a finite carrier of v, then, for i ∉ N, φ_i[v] = 0.

PROOF. Take i ∉ N. Both N and N ∪ {i} are carriers of v; and v(N) = v(N ∪ {i}). Hence φ_i[v] = 0 by Axiom 2.

Two lines. Apply Axiom 2 twice — once to N, once to N ∪ {i} — subtract, and the null player’s value is squeezed to zero. A footnote makes the intent explicit: “Three further properties of the value which might suggest themselves as suitable axioms will be proved as Lemma 1 and Corollaries 1 and 3 below.”

So: the standard “four axioms” presentation is a faithful reformulation, not the original. It replaces the carrier machinery with an explicit null-player axiom, which is easier to teach and makes the axiom set independent, at the cost of the elegance Shapley was after. If you compare treatments and one says three and another four, neither is wrong. Confusingly, the AGT textbook states a third variant — anonymity, dummy, additivity — with efficiency folded into its definition of a “value,” and calls the result Theorem 15.26. Three respectable sources, three axiom counts, one theorem.

flowchart TB
    subgraph shap53["Shapley 1953 — three axioms"]
        S1["<b>Axiom 1</b> symmetry<br/>invariance under relabelling"]
        S2["<b>Axiom 2</b> efficiency<br/>sums to v(N) for <i>every carrier</i>"]
        S3["<b>Axiom 3</b> additivity<br/>'law of aggregation'"]
    end
    subgraph derived["Derived, not assumed"]
        L1["<b>Lemma 1</b> null player<br/>i outside a carrier gets 0"]
        C1["<b>Corollary 1</b> individual rationality<br/>phi_i >= v({i}), equality iff dummy"]
        C3["<b>Corollary 3</b> strategic equivalence<br/>phi(cv + a) = c*phi(v) + a"]
    end
    S2 --> L1
    S2 --> C1
    S3 --> C3
    shap53 --> T["<b>THEOREM.</b> A unique value function<br/>satisfying Axioms 1-3 exists,<br/>and it is formula (13)."]
    style T fill:#dbeafe
    style derived fill:#fef9c3

What it shows: the actual logical structure of Shapley’s 1953 paper. The insight: the modern four-axiom list promotes Lemma 1 to axiomhood. The properties textbooks omit entirely — Corollaries 1 and 3 — are arguably more useful in practice: individual rationality (φ_i ≥ v({i}), so nobody does worse than going it alone) and strategic equivalence (rescaling the currency rescales the values).

Why the theorem is true, in one paragraph

The proof is a basis argument and it is short enough to carry in your head. For each non-empty R ⊆ U define the unanimity game v_R(S) = 1 if S ⊇ R, else 0 — “everyone in R must be present, and then the surplus is 1.” Shapley’s Lemma 2 pins these down immediately: by symmetry all members of R must receive the same amount; by efficiency those amounts must sum to 1; by Lemma 1 nobody outside R gets anything. Hence φ_i[c·v_R] = c/r for i ∈ R and 0 otherwise — forced, with no formula involved. Lemma 3 then states that any game with a finite carrier is a linear combination of unanimity games. Additivity extends φ uniquely from the basis to the whole space, and equation (13) is what you get when you expand. That is the entire uniqueness theorem: the unanimity games are a basis, the first two axioms fix φ on the basis, and additivity does the rest.

This is why additivity is indispensable and also why it is the axiom most often attacked. It is a linearity requirement on the map from games to payoffs. Drop it and uniqueness collapses instantly — the Banzhaf index, among many others, satisfies symmetry and null-player and is a perfectly coherent alternative that fails efficiency.

Computing It Exactly with `fractions.Fraction`

The Shapley value of a rational-valued game is a rational number. Computing it in floating point therefore throws away information for no reason and makes it impossible to distinguish a bug from rounding. Python’s stdlib fractions.Fraction gives exactness with no dependency — which matters on this machine, where numpy, pip, nashpy and gambit are all absent.

import itertools, math
from fractions import Fraction
 
def shapley_exact(n, v):
    """v: frozenset -> number.  Returns exact Fractions.
    Subset form: phi_i = sum over S subset N\\{i} of |S|!(n-1-|S|)!/n! * (v(S+i) - v(S))."""
    N = list(range(n))
    fact = [math.factorial(k) for k in range(n + 1)]
    phi = [Fraction(0) for _ in N]
    for i in N:
        others = [j for j in N if j != i]
        for k in range(n):                              # k = |S|
            w = Fraction(fact[k] * fact[n - 1 - k], fact[n])
            for S in itertools.combinations(others, k):
                fs = frozenset(S)
                phi[i] += w * (Fraction(v(fs | {i})) - Fraction(v(fs)))
    return phi
 
def shapley_by_orderings(n, v):
    """Definitional form: average marginal contribution over all n! orderings."""
    phi = [Fraction(0) for _ in range(n)]
    for perm in itertools.permutations(range(n)):
        S = frozenset()
        for i in perm:
            phi[i] += Fraction(v(S | {i})) - Fraction(v(S))
            S = S | {i}
    return [p / math.factorial(n) for p in phi]

Two implementations of the same quantity, from the two readings in the diagram above, is not redundancy — it is the test. shapley_by_orderings is the definition transcribed literally and is obviously correct; shapley_exact is the one you would actually ship. They must agree exactly, and with Fraction “exactly” means ==, not abs(a-b) < 1e-9. They do, on every game below.

Worked example 1: the glove game

Players 0 and 1 hold a left glove each; player 2 holds a right glove. A coalition is worth the number of complete pairs it can form.

    v({}) = 0     v({0}) = 0     v({1}) = 0     v({2}) = 0
    v({0,1}) = 0  v({0,2}) = 1   v({1,2}) = 1   v({0,1,2}) = 1

  exact Shapley (subset form == ordering form):
    phi_0 = 1/6   phi_1 = 1/6   phi_2 = 2/3      sum = 1

Hand-check φ_2: player 2 is pivotal — turns a worthless coalition into a worth-1 one — in every ordering except those where 2 arrives first (and then contributes 0 on arrival but makes whoever follows pivotal). Of the 6 orderings, 2 arrives first in 2 of them, contributing 0; in the other 4 it arrives second or third to a coalition already holding at least one left glove, contributing 1. So φ_2 = 4/6 = 2/3. The scarce side captures two thirds of a game whose total value is 1, which is the entire economics of scarcity derived from three axioms and no supply-and-demand story.

Worked example 2: the airport cost game

Littlechild and Owen’s classic. Aircraft of different sizes share a runway; a coalition’s cost is the cost of the longest runway anyone in it needs. With requirements [10, 20, 30]:

  v(S) = cost of the longest runway anyone in S needs
    phi_0 = 10/3  = 3.333333
    phi_1 = 25/3  = 8.333333
    phi_2 = 55/3  = 18.333333
    sum   = 30

The Shapley value here has a closed form so clean it doubles as a verification: split the cost of each successive runway segment equally among everyone who needs it or more. Segment 1 (0→10) is needed by all three: 10/3 each. Segment 2 (10→20) by the top two: 5 each. Segment 3 (20→30) by the largest alone: 10. That gives 10/3, 10/3 + 5 = 25/3, 10/3 + 5 + 10 = 55/3 — matching the computation exactly. This “serial cost sharing” reading is why the airport game is the canonical teaching example: it is the one case where the Shapley value is obviously the right answer before you compute it.

Worked example 3: reproducing Shapley’s own 1953 numbers

The strongest available validation is to recompute the numbers Shapley printed. On page 316 he gives two weighted-majority games under the convention v(S) = n − s if S outweighs its complement and v(S) = −s otherwise:

  phi = ((n-3)/(n-1)) * (-1, -1, ..., -1, n-1)   for the game [1, 1, ..., 1, n-2]
  phi = (2/5) * (1, 1, 1, -1, -1, -1)            for the game [2, 2, 2, 1, 1, 1]

Computed here with Fraction:

Game	Computed	Shapley 1953	Match
`[1,1,1,2]` (n=4)	`(−1/3, −1/3, −1/3, 1)`	`(1/3)·(−1,−1,−1,3)`	yes
`[1,1,1,1,3]` (n=5)	`(−1/2, −1/2, −1/2, −1/2, 2)`	`(2/4)·(−1,−1,−1,−1,4)`	yes
`[1,1,1,1,1,4]` (n=6)	`(−3/5, ×5, 3)`	`(3/5)·(−1,×5, 5)`	yes
`[1,1,1,1,1,1,5]` (n=7)	`(−2/3, ×6, 4)`	`(4/6)·(−1,×6, 6)`	yes
`[2,2,2,1,1,1]` (n=6)	`(2/5, 2/5, 2/5, −2/5, −2/5, −2/5)`	`(2/5)·(1,1,1,−1,−1,−1)`	yes

Five exact matches against numbers computed by hand in 1953.

A concrete extraction-vs-retrieval lesson

The Internet Archive’s OCR text for page 316 renders the two scalar coefficients as garbage: (|) = (-1, -1, -1, n-1) — the (n−3)/(n−1) is gone — and If = I (1, 1, 1, -1, -1, -1), where I is the mangled 2/5. Working from the OCR alone, my computed 2/5 would have looked like a disagreement with Shapley. Rendering the page image resolved it in one look and turned an apparent contradiction into a five-for-five confirmation. “Could not extract clean text” is not “could not read” — and OCR that silently drops a leading fraction is more dangerous than OCR that fails loudly, because it produces a plausible wrong equation.

Axiom checks on random games

Rather than trust the derivation, the axioms were verified numerically on 300 random games with n ∈ {3,4,5} and integer coalition worths drawn uniformly from [−20, 20], using exact arithmetic throughout:

  300 random games, all four axioms hold exactly:
  {'efficiency': 300, 'symmetry': 300, 'null': 300, 'additivity': 300}

The interesting one is additivity, tested by drawing two independent random games v₁, v₂, computing φ[v₁], φ[v₂] and φ[v₁+v₂] separately, and asserting φ_i[v₁] + φ_i[v₂] == φ_i[v₁+v₂] as an exact rational identity. Symmetry was tested by constructing games where players 0 and 1 are interchangeable (the worth depends only on how many of {0,1} are present, not which); null-player by constructing games where adding player n−1 never changes any coalition’s worth. Note that these games are not superadditive — they violate Shapley’s own standing assumption — and the value is well-defined and the axioms hold anyway. Shapley flags exactly this: “Only in this corollary have our results depended on the superadditive nature of the functions v,” referring to Corollary 1 (individual rationality). Superadditivity is needed for the value to be individually rational, not for it to exist or be unique.

Efficiency Is Not Stability: The Shapley Value Outside the Core

The most important negative result about the Shapley value is that it can prescribe a split that a subgroup will simply refuse.

The core of a cost game is the set of allocations x with Σ_N x_i = c(N) (budget balance) and Σ_S x_i ≤ c(S) for every S (no coalition is charged more than it would pay alone). Using the facility-location game of AGT Example 15.2 — three clients a, b, c, two facilities, with

c(a)=4  c(b)=3  c(c)=3  c(ab)=6  c(bc)=4  c(ac)=7  c(abc)=8

— my independent computation returns φ = (23/6, 11/6, 7/3), exactly reproducing the values printed in the book’s Example 15.24, and then:

  x_ab = 17/3 vs c(ab) = 6  -> ok
  x_bc = 25/6 vs c(bc) = 4  -> CORE VIOLATED
  x_ac = 37/6 vs c(ac) = 7  -> ok

b and c are jointly billed 25/6 ≈ 4.17 for a service the two of them could buy alone for 4. They will leave. And the book emphasizes the sting: “This is despite the fact that … the core of this game is nonempty” — (4, 2, 2) and (4, 1, 3) both lie in it. The Shapley value skipped a perfectly good stable allocation.

Perturbing the instance (adding a third facility, so c(ac) drops from 7 to 5) makes the core empty, which I confirmed with the Bondareva–Shapley balancedness check for n = 3: (c(ab) + c(bc) + c(ac))/2 = 15/2 < 8 = c(abc), so no budget-balanced allocation can satisfy all three pair constraints. There the Shapley value (7/2, 5/2, 2) violates two of the three — but so does everything else, and the Shapley value at least returns something.

flowchart TB
    G["a cooperative game (N, v)"] --> Q{"is the core<br/>non-empty?"}
    Q -->|"no"| E["<b>core empty</b><br/>no stable split exists<br/>Shapley value still returns<br/>a unique, efficient answer"]
    Q -->|"yes"| M{"is the game<br/>submodular/convex?"}
    M -->|"yes"| IN["<b>Shapley value IS in the core</b><br/>and is cross-monotone<br/>-> usable in Moulin mechanisms"]
    M -->|"no"| OUT["<b>Shapley value MAY be outside</b><br/>the core even though the<br/>core is non-empty<br/><i>AGT Example 15.24</i>"]
    style E fill:#fee2e2
    style OUT fill:#fef3c7
    style IN fill:#dcfce7

What it shows: when the Shapley value is and is not stable. The insight: the guarantee you want — Shapley value in the core — holds for submodular (concave) cost games, where AGT notes “any incremental cost-sharing, and therefore the Shapley value (which is a linear combination of incremental cost-sharing methods), is in the core,” and moreover is cross-monotone, which is what makes it usable inside Moulin’s group-strategyproof mechanisms. Outside submodularity you have no such promise. Check submodularity before you promise stability.

The deeper point is that fairness and stability are different axioms answering different questions. The Shapley value optimizes for “each agent gets what they contribute on average”; the core optimizes for “no subgroup can do better by leaving.” A game can force you to pick one. See Coalitional Games for the core in its own right.

The Cost: `O(n!)` Is a Distraction, `O(2ⁿ)` Is the Real Barrier

The Shapley value is routinely described as O(n!). That is true of the definition and false of any sensible implementation. The subset form evaluates v on 2^n coalitions, not n! orderings. Measured on this machine (CPython 3.14.7, glove games of increasing size, both implementations exact over Fraction):

`n`	`n!`	`2^n`	orderings form (s)	subset form (s)
3	6	8	0.0000	0.0001
5	120	32	0.0008	0.0002
7	5,040	128	0.0456	0.0008
8	40,320	256	0.4317	0.0019
9	362,880	512	4.4317	0.0046
10	3,628,800	1,024	skipped	0.0095
11	39,916,800	2,048	skipped	0.0216

At n = 9 the subset form is already 960× faster, and the gap widens by a factor of n per player. Both are exponential; only one is factorially exponential. AGT footnotes the same point: “since the Shapley value is defined in terms of a formula comprising of exponentially many points of the function c(·), evaluating it is computationally hard in general.”

Two escapes exist and they are different in kind:

Restrict the game’s representation. If v is given not as a table but in a structured form — minimum-cost spanning tree games, induced subgraph games, marginal contribution nets (Ieong & Shoham), algebraic decision diagrams (Aadithya et al.) — the value is computable in time polynomial in the representation, sometimes linear (Maleki et al., §3.1). This is exact and is always the right move when available.
Sample. Approximate the expectation by drawing random orderings. This is the general-purpose escape and the one everything downstream (including SHAP) relies on.

Sampling, with Measured Error Bars

The sampler is four lines and directly transcribes the probabilistic reading:

def shapley_sampled(n, v, m, rng):
    """m random orderings; accumulate each player's marginal contribution."""
    tot = [0.0] * n
    for _ in range(m):
        perm = list(range(n)); rng.shuffle(perm)
        S = frozenset(); prev = float(v(S))
        for i in perm:
            S = S | {i}
            cur = float(v(S))
            tot[i] += cur - prev            # one v-evaluation serves ALL players
            prev = cur
    return [t / m for t in tot]

Note the efficiency that makes this practical: one sweep through one permutation updates every player at once, costing n+1 evaluations of v for n estimates. Maleki et al. state this explicitly — “it is possible to re-use a sample (i.e., permutation) for all players; this will not affect the bound.”

The measurement

Benchmark game: gloves again, but 6 left and 4 right, n = 10. Exact values, computed via the 2^n form:

  exact left  players: 61/315  = 0.19365079
  exact right players: 149/210 = 0.70952381
  sum = 4  (= v(N), the number of complete pairs)

Marginal contributions here are always 0 or 1, so the range r = 1 — which lets the theoretical bounds be evaluated numerically. Running the sampler at each budget m with 200–400 independent repetitions and comparing against the exact rationals:

`m`	mean max abs error	p95 max abs error	RMSE	RMSE·√m
10	0.226448	0.309524	0.131860	0.417
100	0.074896	0.119524	0.041727	0.417
1,000	0.024027	0.037651	0.013476	0.426
10,000	0.007666	0.012051	0.004313	0.431
100,000	0.002425	0.003721	0.001365	0.432

The final column is the finding. RMSE·√m is essentially constant at ≈0.42 across four orders of magnitude of m, which is the 1/√m Monte Carlo rate observed rather than asserted. The practical reading: each additional decimal digit of accuracy costs 100× the samples. Going from three-decimal to four-decimal precision on this game means moving from ~10⁴ to ~10⁶ permutations.

Antithetic sampling, measured

SHAP’s PermutationExplainer does not sample naively. Its docstring states it iterates “through an entire permutation of the features in both forward and reverse directions (antithetic sampling),” and claims that a single such pair gives exact values “for models with up to second order interaction effects.” Implementing the same trick and re-running:

`m` (total sweeps)	plain RMSE	antithetic RMSE	ratio
100	0.041727	0.034595	0.829
1,000	0.013476	0.010683	0.793
10,000	0.004313	0.003464	0.803
100,000	0.001365	0.001198	0.878

A consistent ~17–21% RMSE reduction at equal sample budget on this game. Since error scales as 1/√m, a 0.80 error ratio is worth a factor of 1/0.80² ≈ 1.56 in samples — a free 1.5× speedup for four extra lines of code. It is not the order-of-magnitude win the docstring’s “exact for second-order interactions” might suggest, because the glove game has interaction structure well above second order.

Do the theoretical bounds hold up?

Maleki et al. give two finite-sample bounds, both of which need only a scalar summary of the game (§4.1–4.2):

Chebyshev, variance known: m ≥ ⌈σ² / (δ ε²)⌉
Hoeffding, range known: m ≥ ⌈ln(2/δ) · r² / (2 ε²)⌉

Their contribution is that these are non-asymptotic — unlike a CLT-based confidence interval, which “only holds when the number of samples increases to infinity” and introduces “an unquantifiable error” at finite m. Their objection is precise and worth repeating: obtaining a finite-sample CLT error requires the Berry–Esseen theorem, which “only holds under some strong assumptions,” and “in the general class of games, the marginal contributions of a player could follow any distribution.” A CLT error bar on a Shapley estimate is not a bound; it is a hope.

Evaluating the Hoeffding bound on the glove game (r = 1, δ = 0.05):

`ε`	required `m`
0.1	185
0.01	18,445
0.001	1,844,440

and then testing it empirically at ε = 0.01, m = 18,445, over 400 independent runs:

  any-player error exceeded 0.01 in 9 / 400 runs (0.0225)
  per-player budget is delta = 0.05; union bound over 10 players = 0.5

The bound holds with room to spare: the observed any-player failure rate of 2.25% sits below even the per-player budget of 5%, and far below the union-bound-over-ten-players figure of 50%. That is the expected outcome — Hoeffding is distribution-free and therefore loose — but it is worth having measured, because a bound you have never checked is a bound you do not know you are applying correctly.

xychart-beta
    title "Sampling error vs budget (glove game, n=10) — log-log"
    x-axis "log10(m)" [1, 2, 3, 4, 5]
    y-axis "-log10(RMSE)" 0.5 --> 3.5
    line [0.880, 1.380, 1.870, 2.365, 2.865]
    line [0.960, 1.461, 1.971, 2.460, 2.921]

What it shows: the measured RMSE of plain (lower line) and antithetic (upper line) permutation sampling, plotted as −log₁₀(RMSE) against log₁₀(m); higher is more accurate. The insight: both lines have slope ≈0.5, the signature of the 1/√m Monte Carlo rate, and antithetic sampling shifts the line up by a constant without changing its slope. Variance reduction buys you a constant factor; it does not buy you a better exponent.

What It Is Used For, Outside Economics

Cost allocation

The historical application, and the one Shapley’s axioms were shaped for. The airport game above is the textbook case; the pattern generalizes to any shared-infrastructure bill. In algorithmic game theory it appears inside multicast cost sharing, where AGT chooses “the Shapley Value (SH) mechanism” for budget balance and exploits its cross-monotonicity on submodular games to build group-strategyproof Moulin mechanisms (AGT §14.2.2, §15.6.1). Cross-monotone means an agent’s share never rises when the serviced set grows — the property that lets you run a “keep dropping agents who won’t pay” loop and have it terminate sensibly.

Voting power: the Shapley–Shubik index

Apply the Shapley value to a simple game — v(S) ∈ {0,1}, 1 if S can pass a motion — and you get the Shapley–Shubik power index (Shapley & Shubik, 1954). It measures the probability that a party is pivotal: the member whose arrival flips a losing coalition into a winning one, over uniformly random arrival orders. Computed exactly here:

Weights	Quota	Seat share	Shapley–Shubik power
`[50, 49, 1]`	51	`1/2, 49/100, 1/100`	`2/3, 1/6, 1/6`
`[4, 2, 1]`	4	`4/7, 2/7, 1/7`	`1, 0, 0`
`[1,1,1,1,7]`	8	`1/11 ×4, 7/11`	`1/20 ×4, 4/5`
`[3, 2, 1, 1]`	4	`3/7, 2/7, 1/7, 1/7`	`1/2, 1/6, 1/6, 1/6`

Every row teaches something and none of them is proportional to seats.

Row 1 is the classic. A party holding 1% of the seats has the same power (1/6) as a party holding 49%. Any winning coalition needs the 50-seat party plus one other, and the two others are interchangeable in that role regardless of size. The tiny party is not a rounding error; it is a kingmaker.
Row 2: with quota 4 and a 4-weight member, that member alone wins and no coalition wins without it — a dictator, power 1, and everyone else is a null player with power exactly 0 despite holding 3 of 7 seats.
Rows 3 and 4 show power both above and below seat share: 7/11 ≈ 0.64 of the seats yields 0.8 of the power; 3/7 ≈ 0.43 yields 0.5.

Shapley himself proved the monotonicity that makes this coherent: in a weighted majority game, φ_i < φ_j implies w_i ≤ w_j — “weight and value rank the players in the same order” (Example 5, page 315). Power is monotone in weight, but wildly non-linear in it.

Feature attribution in machine learning: SHAP

The largest modern user of the Shapley value by a wide margin is SHAP (SHapley Additive exPlanations), introduced by Lundberg & Lee, A Unified Approach to Interpreting Model Predictions, NeurIPS 2017. The translation is a dictionary substitution:

Cooperative game	SHAP
player `i`	feature `i`
coalition `S`	the set of features whose values are “known”
`v(S)`	expected model output given only the features in `S`
`v(N) − v(∅)`	`f(x) − E[f(X)]`, the prediction’s deviation from baseline
`φ_i`	feature `i`’s attribution for this one prediction

Efficiency becomes the local accuracy property that SHAP advertises: the attributions sum exactly to the gap between this prediction and the average prediction. That is a genuinely useful guarantee, and it is the same Axiom 2 read in a new domain.

The library’s machinery is worth reading rather than guessing at, since the algorithmic choices are where the semantics live. From the source:

KernelExplainer defaults to nsamples = 2 * M + 2**11 (i.e. 2M + 2048 coalitions), and caps at max_samples = 2**M − 2 when M ≤ 30 — at which point it is enumerating exhaustively and is exact.
It weights subsets by (M − 1) / (i · (M − i)), the Shapley kernel, which is what converts a weighted least-squares regression on coalition indicators into Shapley values. Sizes i and M − i are sampled in pairs (“paired subset sizes”).
ExactExplainer’s docstring recommends it “for models with less than ~15 features that vary from the background per sample,” and orders its masking sets by gray code so that consecutive coalitions differ in one bit, minimizing model re-evaluation.

Uncertain

Verify: SHAP’s runtime behaviour beyond what is written in its source. Reason: there is no SHAP installation on this machine (no pip, no numpy), so every claim in this section is read from the GitHub source and the papers — I have not run SHAP. The constants above (2*M + 2**11, 2**M - 2, the (M-1)/(i*(M-i)) kernel, the gray-code ordering) are quoted from master as fetched on 2026-08-28 and could change. To resolve: pin a release tag and re-read. uncertain

The honest caveats: additivity and correlated features are contested

SHAP’s marketing rests on the uniqueness theorem — these are the axiomatically correct attributions. The critical literature says the theorem is fine and the application is where the trouble is. Three distinct objections, each from a paper read for this note:

1. The value function is a modelling choice, and different choices give different answers. Sundararajan and Najmi (The Many Shapley Values for Model Explanation) is the definitive statement of this: several inequivalent ways of defining v(S) from a model all inherit the uniqueness theorem, so uniqueness given v does not confer uniqueness of the explanation. The main fork is interventional/marginal (replace absent features with independent draws from the marginal — “true to the model”) versus conditional/observational (condition on the observed features — “true to the data”), framed exactly that way by Chen, Janizek, Lundberg and Lee (True to the Model or True to the Data?).

Here is that fork made concrete and exact. A model f(x₁, x₂) = x₁ that completely ignores x₂; a population in which x₁ = x₂ always (perfect correlation), uniform on {(0,0), (1,1)}; explain the point x = (1,1) against the baseline E[f] = 1/2:

  interventional (SHAP default / marginal):   phi_x1 = 1/2   phi_x2 = 0
  conditional    (true-to-the-data):          phi_x1 = 1/4   phi_x2 = 1/4
  both sum to 1/2 = f(x) - E[f]

Same model, same data point, same axioms, two different attributions — and both are “the” Shapley value of a game. Under the conditional value function, x₂ receives half the credit for a prediction it has no causal role in, purely because it is informative about x₁. Under the interventional one, x₂ gets zero — correct about the model, but the counterfactual it computes (“what if x₁ = 1 and x₂ = 0?”) is a data point that cannot occur, so the model is being evaluated off-manifold. This is the trade-off Aas, Jullum and Løland attack directly in Explaining Individual Predictions When Features Are Dependent, whose entire premise is that SHAP’s independence assumption yields inaccurate values under dependence and needs replacing with genuine conditional estimation.

2. Additivity itself is questioned as an axiom for this task. Kumar, Venkatasubramanian, Scheidegger and Friedler (Problems with Shapley-Value-Based Explanations as Feature Importance Measures) argue the mismatch is conceptual rather than technical: the axioms were designed to divide a transferable payoff among agents who could actually form coalitions, and features are neither. There is no sense in which features “cooperate” or in which credit is “transferable” between them. An additive decomposition is a choice about the form of the explanation, imported wholesale from cooperative game theory along with its uniqueness theorem, and the theorem does nothing to justify the import.

3. The counting artefact. Shapley’s symmetry axiom means identical features split their credit, which makes attributions unstable under trivially redundant columns:

  informative feature duplicated 1 time(s): attributions ['1']
  informative feature duplicated 2 time(s): attributions ['1/2', '1/2']
  informative feature duplicated 3 time(s): attributions ['1/3', '1/3', '1/3']

A single real signal’s credit is divided by k when the column is copied k times. A feature-importance ranking can therefore be changed by duplicating a column — an operation that changes nothing about the model’s behaviour. This is not a bug in SHAP; it is symmetry working exactly as specified, in a setting where the specification does not match the question being asked.

None of this makes SHAP useless — it makes it a tool whose output means something precise that is not “how important is this feature.” State which value function you used, and never compare attributions computed under different ones.

Failure Modes and Gotchas

Assuming the Shapley value is stable. It is efficient, symmetric, null-respecting and additive — and it can still sit outside a non-empty core, as the facility-location example above demonstrates with b and c overcharged by 1/6. If your application needs “no subgroup will walk away,” you need a core allocation, and the Shapley value is not one unless the game is submodular. Symptom in production: a cost-sharing scheme that is provably fair and that a coalition of customers publicly refuses to pay.

Implementing the definition literally. Enumerating n! orderings is n× slower than enumerating 2^n subsets and buys nothing. Measured above: 4.43s vs 0.0046s at n = 9. Write shapley_by_orderings as a test oracle and ship the subset form.

Computing in floating point. The Shapley value of a rational game is rational. In float you cannot tell a bug from accumulated error, and the errors are real — the subset form sums 2^n terms with alternating signs. Use Fraction, get exact answers, and let == be your assertion. Every number in this note was produced that way.

Putting a CLT confidence interval on a sampled estimate. Maleki et al. show why this is unsound at finite m: the CLT is asymptotic, the finite-sample gap needs Berry–Esseen (whose hypotheses you cannot check), and “in the general class of games, the marginal contributions of a player could follow any distribution.” Use Hoeffding (needs the range r) or Chebyshev (needs the variance σ²). Both are loose — measured 2.25% failures against a 5% per-player budget — but they are actual bounds.

Forgetting the union bound. Every published bound is per player. Reporting all n values at confidence 1 − δ needs δ/n per player, i.e. an extra ln n factor of samples. In the measurement above, the per-player δ = 0.05 corresponds to a union bound of 0.5 over ten players — a “95% confident” claim that is really 50% confident jointly.

Reading a SHAP plot as causal. It is an attribution of a model’s output, and — under the conditional value function — features with no causal role receive credit merely for being correlated with features that do. Measured exactly above: x₂ gets 1/4 for a model that literally ignores it. The interventional alternative fixes the causal story and pays for it by evaluating the model off-manifold.

Comparing attributions computed with different maskers. Interventional and conditional SHAP values are values of different games. They are not two estimates of one quantity, and a difference between them is not error. Record which one you used.

Deduplicating features after computing attributions. Symmetry splits credit equally among identical features, so k copies of a signal each get 1/k of its importance. Aggregate or drop correlated columns before attribution, not after.

Assuming superadditivity is required. It is not, for existence or uniqueness — the axiom checks above passed on 300 games with values drawn uniformly from [−20, 20], most of which are not superadditive. Shapley says exactly where it is needed: “Only in this corollary have our results depended on the superadditive nature of the functions v” — Corollary 1, individual rationality. Drop superadditivity and you may get φ_i < v({i}), i.e. an agent better off alone.

Assuming everyone means the same axioms. Shapley 1953 states three (symmetry, efficiency-over-carriers, additivity); the standard modern presentation states four (efficiency, symmetry, null player, additivity); AGT §15.6.2 states three different ones (anonymity, dummy, additivity) with efficiency built into its definition of “value.” All three characterize the same function. When someone cites “the four axioms,” they are citing a reformulation, and the null-player axiom in it is Shapley’s Lemma 1.

Alternatives and When to Choose Them

Concept	Answers	Always exists?	Unique?	Efficient?	Choose when
Shapley value	“what did you contribute on average?”	yes	yes	yes	you need an answer for every game, and fairness beats stability
The core	“what will no subgroup reject?”	no (often empty)	no (often a polytope)	yes	stability is the requirement; you can tolerate “no answer”
Nucleolus	“which core-like point minimizes the worst complaint?”	yes	yes	yes	you want a unique point that is in the core whenever the core is non-empty
Banzhaf index	“how often are you pivotal?” (unnormalized)	yes	yes	no	measuring raw pivotality, not dividing a fixed pie
Nash bargaining solution	“what split maximizes the product of gains?”	yes	yes	yes (Pareto)	two-party bargaining with a disagreement point, no coalition structure
Egalitarian / leximin	“how high can the worst-off be pushed?”	yes	yes	yes	need is the criterion, contribution is not
Proportional (by weight)	“who is biggest?”	yes	yes	yes	contributions are genuinely additive — then Shapley reduces to this anyway

Three decision rules:

Shapley versus the core is fairness versus stability. The core asks a coalitional-deviation question; the Shapley value asks a contribution-accounting question. When the core is non-empty and you need stability, use the core (or the nucleolus, which picks a canonical point of it). When the core is empty — which balancedness makes easy to check — the Shapley value is one of the few concepts that still returns something.

Shapley versus Banzhaf is efficiency versus not. The Banzhaf index counts swings without weighting by coalition size and does not sum to v(N). That makes it wrong for dividing a fixed pie and arguably better for the pure question “how often does my vote decide the outcome,” since it does not impose a uniform-random-arrival-order model that no legislature actually follows.

If your game is additive, none of this matters. If v(S) = Σ_{i∈S} v({i}), the Shapley value is φ_i = v({i}) and every concept collapses to proportional shares. The machinery only earns its cost when there are genuine synergies — complementarities and substitutabilities between agents. The glove game is the minimal instance: two identical left gloves are substitutes for each other and complements to the right glove, and that single fact produces the 1/6, 1/6, 2/3 split.

Production Notes

The 2012 Nobel Prize. Lloyd Shapley shared the 2012 Sveriges Riksbank Prize in Economic Sciences with Alvin Roth. It is worth being precise about what for, because the Shapley value is frequently miscredited: the prize was awarded for “stable allocations and the practice of market design” — the official scientific background document is titled exactly that, and does not discuss the Shapley value at all. The cited work is Gale–Shapley deferred acceptance and Shapley–Scarf housing markets. See Stable Matching and The Gale-Shapley Algorithm. The Shapley value is Shapley’s most-used contribution and is not the one he was given a Nobel for.

RAND provenance. The 1953 paper carries the footnote “The preparation of this paper was sponsored (in part) by the RAND Corporation,” and Shapley’s affiliation line reads “Princeton University and The RAND Corporation.” Cooperative game theory’s founding results were Cold War defence-funded operations research, which is worth knowing when reading the framing about coalition formation.

Cost allocation in practice. The airport-runway formulation is the standard teaching case and the same serial pattern is used for shared infrastructure billing generally. Inside algorithmic mechanism design, the Shapley-value cost-sharing mechanism is chosen for multicast specifically because it is budget-balanced and, on submodular cost functions, cross-monotone — the property that makes Moulin’s group-strategyproof mechanism work (AGT §14.2.2). This is the closest thing to a “deployed” Shapley value in systems: not a fairness gesture, but a technical prerequisite for a strategyproofness proof.

SHAP is the volume leader. Whatever the conceptual objections, SHAP is where essentially all Shapley-value computation now happens by CPU-hours. Its engineering is a catalogue of how to make a 2^n quantity tractable: gray-code coalition ordering in ExactExplainer to reuse model evaluations; antithetic permutation pairs in PermutationExplainer (measured above at ~20% RMSE reduction); the weighted-least-squares Shapley kernel in KernelExplainer with paired subset sizes; and TreeExplainer, which exploits tree structure for a polynomial-time exact algorithm. The 2 * M + 2**11 default sample count is a fixed budget that does not scale with M beyond a linear term — meaning the accuracy of a default SHAP call silently degrades as you add features, since the coalition space grows as 2^M while the sample budget grows as 2M + 2048.

The reproducibility lesson from this note’s own research. The definitive source for this topic — Shapley 1953 — is a 73-year-old scanned book whose OCR silently dropped the scalar coefficients from two published results, in a way that would have made a correct implementation look like it contradicted the original. The resolution was to render the page image and read it. Two habits follow, and they generalize well past game theory: verify a computation against numbers the original author published, not against your own re-derivation, and treat OCR output as a lossy channel whose failures are sometimes silent rather than loud.

vault

Explorer

The Shapley Value

The Shapley Value

Mental Model: The Room That Fills Up One Person at a Time

The Setup and the Formula, Symbol by Symbol

The Axioms and the Uniqueness Theorem

Why the theorem is true, in one paragraph

Computing It Exactly with `fractions.Fraction`

Worked example 1: the glove game

Worked example 2: the airport cost game

Worked example 3: reproducing Shapley’s own 1953 numbers

Axiom checks on random games

Efficiency Is Not Stability: The Shapley Value Outside the Core

The Cost: `O(n!)` Is a Distraction, `O(2ⁿ)` Is the Real Barrier

Sampling, with Measured Error Bars

The measurement

Antithetic sampling, measured

Do the theoretical bounds hold up?

What It Is Used For, Outside Economics

Cost allocation

Voting power: the Shapley–Shubik index

Feature attribution in machine learning: SHAP

The honest caveats: additivity and correlated features are contested

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

The Shapley Value

The Shapley Value

Mental Model: The Room That Fills Up One Person at a Time

The Setup and the Formula, Symbol by Symbol

The Axioms and the Uniqueness Theorem

Why the theorem is true, in one paragraph

Computing It Exactly with fractions.Fraction

Worked example 1: the glove game

Worked example 2: the airport cost game

Worked example 3: reproducing Shapley’s own 1953 numbers

Axiom checks on random games

Efficiency Is Not Stability: The Shapley Value Outside the Core

The Cost: O(n!) Is a Distraction, O(2ⁿ) Is the Real Barrier

Sampling, with Measured Error Bars

The measurement

Antithetic sampling, measured

Do the theoretical bounds hold up?

What It Is Used For, Outside Economics

Cost allocation

Voting power: the Shapley–Shubik index

Feature attribution in machine learning: SHAP

The honest caveats: additivity and correlated features are contested

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks

Computing It Exactly with `fractions.Fraction`

The Cost: `O(n!)` Is a Distraction, `O(2ⁿ)` Is the Real Barrier