How do you estimate Shapley values when exact enumeration over 2^40 coalitions is impossible?

## Where the cost comes from The Shapley value of feature `i` is an average of `v(S + i) - v(S)` over all coalitions `S` that exclude `i`. With `n` features there are `2^n` distinct coalitions and `n!` orderings. For a 40-feature telecom pricing model, `2^40` is about 1.1 trillion coalition evaluations *per explained row*, and each evaluation is a forward pass through the model - possibly averaged over a background set on top of that. Exact enumeration is practical for roughly a dozen features and nothing beyond. Three escapes exist. The most general is sampling; the second is exploiting structure in the model family so the exact value can be computed in time polynomial in the model's size; the third is not computing Shapley values at all and using a cheaper local explanation. This section is about sampling. ## Permutation sampling The ordering formulation is what makes sampling easy. The Shapley value is the *expected* marginal contribution when features are revealed in a uniformly random order, so: ``` repeat m times: draw a uniformly random ordering of the n features S <- empty; prev <- v(empty) for each feature i in that ordering: S <- S + i cur <- v(S) contribution[i] += (cur - prev) prev <- cur phi_i = contribution[i] / m ``` Two properties matter. First, the estimator is **unbiased** - its expectation is the exact Shapley value, for every `m`. Whatever error you have is variance, not a systematic tilt. Second, one sampled ordering yields a contribution for every feature at once, from `n + 1` model evaluations, so the per-feature cost is amortised rather than multiplied. ## How the error behaves Because this is a plain Monte Carlo average of independent draws, the standard error of `phi_i` falls as `sigma_i / sqrt(m)`, where `sigma_i` is the spread of feature `i`'s marginal contribution across orderings. Two consequences: - **Diminishing returns.** Cutting the error in half costs four times the samples; one more decimal digit costs a hundred times. - **The error is per-feature.** A feature involved in strong interactions has a wide spread of marginal contributions across orderings and needs more draws than a feature with a near-constant effect. A uniform sample budget over-serves the easy features and under-serves the hard ones. Because the estimator is unbiased with computable per-feature variance, you can turn the running sample variance into a **standard error** and use it as a stopping rule instead of a fixed budget: keep drawing until each reported attribution's interval is narrow enough for the use it is put to. ## What "narrow enough" means depends on the decision This is the judgment part. If the explanation is displayed as a ranked list of the strongest drivers, what has to be stable is the *ranking of the top few*, not the third decimal of each value. Ranking is a much easier target: the top features usually separate from the rest early, and additional draws mostly refine values that are already clearly ordered. The right stopping test is therefore an operational one - draw until repeated runs of the estimator on the same row agree on the reported set, and until any pair of features whose order flips between runs are close enough that the flip does not change what a reader would do. If two features genuinely sit within noise of each other, more sampling will not resolve them into a stable order; that is a fact about the model, not a budget problem, and the honest report says they are comparable. ## Variance reduction and other levers - **Antithetic sampling**: evaluate an ordering and its exact reverse together. A feature that arrives early in one arrives late in the other, which cancels much of the ordering-induced variance. - **Stratification / adaptive allocation**: spend draws on the features whose running variance is largest rather than splitting the budget evenly. - **Truncation**: along an ordering, once the running coalition value has essentially converged to the full prediction, the remaining features' marginal contributions are near zero and the walk can be cut short. - **Background size**: the value function is itself an average over background rows, so cost is (orderings) x (features) x (background rows). Shrinking a background of thousands of rows to a well-chosen small sample is often the single largest saving, at the price of extra variance in `v` itself. - **Batching by row**: explanations for many rows share the same model and background, so evaluations can be batched. ## When sampling is the wrong answer If every scored row needs an explanation in real time, per-row Monte Carlo may simply not fit the latency budget, and the options are a model family whose structure admits an exact fast computation, precomputing explanations offline for the rows that will actually be read, or a cheaper explanation method. Recognising that the sampling budget is a product-level constraint - not just a tuning knob - is what separates a senior answer here.