---
kind: concept
slug: shapley-value
title: Shapley value
summary: >-
  Splits a shared score among players by averaging each player's marginal contribution over every order in which they could join. Covers exact enumeration, permutation and regression sampling, and Monte-Carlo credit for steps in LLM-agent runs, with the cost, axiom and sign trade-offs. Sources are one survey with no experiments and one paper validated only on synthetic models.
tags: [cooperative-game-theory, attribution, sampling, explainability]
papers: ["2202.05594", "2606.08275"]
related: [credit-assignment, feature-attribution, data-valuation, federated-learning, multi-agent-reinforcement-learning, ensemble-learning, causal-inference, llm-agent, influence-functions, explainable-ai]
status: draft
updated_at: 2026-11-01
---

## Overview

The Shapley value gives each player in a cooperative game a share of the total
payoff. The share is the average, over all orderings of the players, of how
much the player adds when it joins the players that came before it
[arxiv:2202.05594 §2.1] [arxiv:2202.05594 eq. 1]. In machine learning the
players can be input features, training points, models in an ensemble, data
owners, agents, or steps of a recorded agent run. The payoff can be a fit
score, a validation-based score, or the probability of a bad outcome
[arxiv:2202.05594 §4] [arxiv:2606.08275 §4].

The exact value is defined by four properties: null player, efficiency,
symmetry and linearity. A single-valued solution has all four if and only if
it is the Shapley value [arxiv:2202.05594 §2.2]. Approximations often lose some
of these properties [arxiv:2202.05594 §5.1.3]. Exact computation grows
factorially with the number of players, so every practical variant trades
exactness for a sample budget or a restricted model [arxiv:2202.05594 §5.1.1].

## Variants

### Exact enumeration

Average the marginal contribution of each player over all orderings
[arxiv:2202.05594 §2.1]. This is exact, but the survey lists four exact
applications with factorial time and one with O(|N| log |N|) time
[arxiv:2202.05594 tab. 2]. It is practical only for small player counts. The
survey's three-player example gives values 32/6, 50/6 and 68/6, which sum to
the grand-coalition payoff 25 [arxiv:2202.05594 tab. 1]. Use it as a test
fixture for an implementation.

### Permutation sampling

Draw k random orderings and average the marginal contributions over them
[arxiv:2202.05594 §3.1] [arxiv:2202.05594 alg. 1]. Two variance-reduction
options are named in the survey:

- **Stratified sampling** groups orderings by the position of a player in the
  coalition, with stratified empirical Bernstein bounds to set the allocation
  [arxiv:2202.05594 §3.1.1].
- **Antithetic sampling** pairs an ordering with its reverse
  [arxiv:2202.05594 §3.1.2].

Asymptotic error bounds need the variance of the marginal contributions, and
finite-sample bounds need either the variance or the range
[arxiv:2202.05594 §3.1]. The survey uses this family for feature selection,
data valuation and federated learning [arxiv:2202.05594 §4.1] [arxiv:2202.05594
§4.2] [arxiv:2202.05594 §4.3].

### Multilinear extension

Rewrite the Shapley sum as an integral over an inclusion probability q in
[0, 1], then approximate the integral by sampling q, with the trapezoid rule or
with antithetic pairs [arxiv:2202.05594 §3.2]. The survey gives no comparison
numbers for this variant.

### Weighted least squares (KernelSHAP-style)

The values are the solution of a weighted least-squares problem over coalitions,
with constraints that fix the intercept and make the values sum to the full
payoff [arxiv:2202.05594 §3.3]. The problem needs the payoff on all coalitions,
so coalitions are subsampled. The survey reports that the estimator is
consistent but biased, and that sampling coalitions in complementary pairs
reduces its variance [arxiv:2202.05594 §3.3]. For feature explanations of a
single prediction, the survey's explainability section names SHAP as the main
example of the universal Shapley game [arxiv:2202.05594 §4.4.1].

### Monte-Carlo Shapley over agent steps (counterfactual payoff)

Causal Agent Replay treats the steps of a failed LLM-agent run as players
[arxiv:2606.08275 §4]. A coalition S is the set of steps kept at their factual
actions, while the other steps are redrawn from the same policy. The value is
v(S) = P(bad outcome | steps in S held), estimated over K rollouts. Shares come
from permutation sampling with antithetic reverse permutations, and each step
gets a mean and a normal-approximation interval [arxiv:2606.08275 §4]. The
estimator runs until its budget is exhausted [arxiv:2606.08275 §4]. The paper
does not state K or the number of permutations, so the user must set them
[arxiv:2606.08275 §4].

On synthetic models with a known answer, a two-step AND interaction gives
Shapley values of 0.44 and 0.45, against analytic values of 0.5 each, and a
sum of 0.909 against a total effect of 0.91 [arxiv:2606.08275 §5]. These are
the only numbers reported for this variant. No real agent traces are used
[arxiv:2606.08275 §5] [arxiv:2606.08275 §7].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Few players, and you need exact values to check an implementation | Exact enumeration [arxiv:2202.05594 §2.1] | Factorial cost rules it out for larger games [arxiv:2202.05594 §5.1.1] |
| Many players and a payoff that is cheap to evaluate | Permutation sampling, with antithetic pairs [arxiv:2202.05594 §3.1] [arxiv:2202.05594 §3.1.2] | Error bounds depend on variance, so the sample count needs a rule the survey does not give [arxiv:2202.05594 §3.1] |
| One prediction to explain, and missing features can be replaced by a reference value | Weighted least squares, SHAP-style [arxiv:2202.05594 §3.3] [arxiv:2202.05594 §4.4.1] | Subsampled coalitions; the estimator is consistent but biased [arxiv:2202.05594 §3.3] |
| Each payoff is a full model training, as in data valuation | Sampled orderings with a small budget [arxiv:2202.05594 §4.2] | Exact values need one training per coalition; the survey notes this makes exact computation impractical [arxiv:2202.05594 §3] |
| Credit for steps in an agent run where steps interact, and you need uncertainty per step | Monte-Carlo Shapley with counterfactual rollouts [arxiv:2606.08275 §4] | Gives intervals, but is validated only on synthetic models [arxiv:2606.08275 §5] |
| A known causal graph constrains which orders are allowed | Graph-restricted orderings [arxiv:2202.05594 §4.4.3] | The survey describes it without numerical results |
| Players form groups with a known structure | Coalition-structure values such as the Owen value [arxiv:2202.05594 §5.2.1] | The survey says these have not been studied much in machine learning |

Choose the variant from the constraints that bind. Cost usually decides between
exact and sampled. Access to replay or to a rule-based outcome decides whether
the counterfactual variant is possible [arxiv:2606.08275 §3] [arxiv:2606.08275
§7].

## Implementation sketch

The core is the same in every sampled variant: draw orderings, add up
marginal contributions, and divide by the number of orderings. Variants differ
in how v is defined and in how orderings are drawn.

```pseudocode
# Permutation sampling with antithetic pairs  [arxiv:2202.05594 alg. 1]
# Input:  players N, payoff v(coalition) -> float, budget k
# Output: estimate phi[i] for every player i in N
def shapley_estimate(N, v, k):
    # Each player's estimate starts at zero
    phi = {i: 0.0 for i in N}
    for _ in range(k // 2):
        # Draw one ordering and use its reverse as well  [arxiv:2202.05594 §3.1.2]
        order = random_permutation(N)
        for ordering in (order, order[::-1]):
            # Walk the ordering; each player sees its predecessors  [arxiv:2202.05594 §2.1]
            before = set()
            for i in ordering:
                # Marginal contribution of i, divided by the sample count  [arxiv:2202.05594 eq. 1]
                gain = v(before | {i}) - v(before)
                phi[i] += gain / k
                before.add(i)
    return phi
```

For the counterfactual variant, v(S) is the estimated probability of the bad
outcome when the steps in S are held at their factual actions and the rest are
redrawn, averaged over K rollouts [arxiv:2606.08275 §4]. Values must not be
cached across orderings: caching would make the marginals collapse to zero
variance and give false confidence in the interval [arxiv:2606.08275 §4].

## Contradictions

- **Axioms under approximation.** The survey says the desired properties often
  fail for the approximations used in practice, and calls this the largest open
  issue. It gives no proof or counterexample of its own [arxiv:2202.05594
  §5.1.3]. The counterfactual paper reports sampled values that sum to 0.909
  against a total of 0.91 on one synthetic model [arxiv:2606.08275 §5]. This
  single check does not settle the survey's claim, and the paper does not test
  the axioms on other games.
- **Sign of the payoff.** The survey's machine-learning payoffs are described as
  goodness of fit, but several rows of its applications table use validation
  loss, and the survey does not say which sign convention to use
  [arxiv:2202.05594 §4.1] [arxiv:2202.05594 tab. 2]. The counterfactual paper
  uses the probability of the bad outcome as its payoff, so a positive share
  means the step pushes toward failure [arxiv:2606.08275 §4]. The two
  conventions are opposite in sign; pick one and state it.

## Pitfalls

- **v(empty) is not defined by the ML games.** The axioms assume v(empty) = 0
  [arxiv:2202.05594 §2.1]. The feature-selection, data-valuation, federated and
  ensemble games define v(S) through a trained model but do not say what the
  empty coalition gives [arxiv:2202.05594 §4.1] [arxiv:2202.05594 §4.2]
  [arxiv:2202.05594 §4.3] [arxiv:2202.05594 §4.6]. The counterfactual paper also
  does not state v(empty) for its game [arxiv:2606.08275 §4]. A constant
  predictor or a fully resampled baseline are possible conventions; neither
  paper fixes one.
- **The sample count is not given.** The survey gives no rule for k, and the
  bounds need variance or range values that are rarely known in advance
  [arxiv:2202.05594 §3.1].
- **"Linear time" needs qualifying.** Permutation sampling is described as
  linear-time per sample [arxiv:2202.05594 §3.1]. The regression approach needs
  the payoff on all coalitions and is made tractable only by subsampling
  [arxiv:2202.05594 §3.3]. The total budget is not stated.
- **Reference values for missing features.** Explainability games replace
  missing features with a reference value, such as a mean, and the survey gives
  no fixed choice [arxiv:2202.05594 §4.4.1]. Attributions depend on this choice.
- **Hard to read as an action.** The value is an average over orderings, so a
  value of twice the size does not mean twice the usefulness
  [arxiv:2202.05594 §5.1.2].
- **Relational game definition.** The survey defines its players as vertices in
  one place and describes explanations over edges in another, and it reuses the
  player-set symbol for the edge set [arxiv:2202.05594 §4.4.4].
- **Shapley cost in agent attribution.** One permutation costs two walks over the
  coalitions, and the worst case is exponential in the number of steps. The
  Monte-Carlo variance depends on the budget [arxiv:2606.08275 §7].
- **Replay and live tools.** Hosted models vary even at temperature 0, so the
  paper measures replay by action-match rate [arxiv:2606.08275 §3]. Counterfactual
  suffixes call the environment fresh, and the paper's demonstrations use mocked
  tools, so real side effects are not modelled [arxiv:2606.08275 §7].

## Papers

- [The Shapley Value in Machine Learning](/papers/2202.05594): survey of the
  value, its axioms, sampling and regression approximations, and six
  application areas. No experiments.
- [Causal Agent Replay: Counterfactual Attribution for LLM-Agent Failures](/papers/2606.08275):
  Monte-Carlo Shapley over agent steps with counterfactual rollouts and
  confidence intervals. Validated on synthetic models only.