Shapley value

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 2202.05594 §2.1 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 2202.05594 §4 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 2202.05594 §2.2. Approximations often lose some of these properties 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 2202.05594 §5.1.1.

Variants

Exact enumeration

Average the marginal contribution of each player over all orderings 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 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 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 2202.05594 §3.1 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 2202.05594 §3.1.1.
• Antithetic sampling pairs an ordering with its reverse 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 2202.05594 §3.1. The survey uses this family for feature selection, data valuation and federated learning 2202.05594 §4.1 [arxiv:2202.05594 §4.2] 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 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 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 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 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 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 2606.08275 §4. The estimator runs until its budget is exhausted 2606.08275 §4. The paper does not state K or the number of permutations, so the user must set them 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 2606.08275 §5. These are the only numbers reported for this variant. No real agent traces are used 2606.08275 §5 2606.08275 §7.

When to use which

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 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.

# 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 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 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 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 2202.05594 §4.1 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 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 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 2202.05594 §4.1 2202.05594 §4.2 2202.05594 §4.3 2202.05594 §4.6. The counterfactual paper also does not state v(empty) for its game 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 2202.05594 §3.1.
• "Linear time" needs qualifying. Permutation sampling is described as linear-time per sample 2202.05594 §3.1. The regression approach needs the payoff on all coalitions and is made tractable only by subsampling 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 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 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 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 2606.08275 §7.
• Replay and live tools. Hosted models vary even at temperature 0, so the paper measures replay by action-match rate 2606.08275 §3. Counterfactual suffixes call the environment fresh, and the paper's demonstrations use mocked tools, so real side effects are not modelled 2606.08275 §7.

Papers

• The Shapley Value in Machine Learning: 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: Monte-Carlo Shapley over agent steps with counterfactual rollouts and confidence intervals. Validated on synthetic models only.