Approximate estimation

When \(n\) players make exact enumeration infeasible, nlp-shap approximates Shapley-style attributions by sampling coalitions. Three built-in estimators trade budget for accuracy:

  • MonteCarloEstimator — uniform random coalitions; attributions come from estimand plugins (Shapley or Banzhaf).

  • ComplementaryEstimator — symmetric pairs \((S, N\setminus S)\) with complementary-contribution (CC) aggregation.

  • NeymanEstimator — two-phase CC sampling with Neyman allocation over coalition sizes.

Budget model

All estimators read ExplainConfig.explanation.budget.fraction in \((0, 1]\). The fraction scales a method-specific maximum:

Estimator

Maximum coalitions

Monte Carlo

\(2^n - 1\) (grand coalition excluded)

Complementary / Neyman

\(2^n - 2\) (empty and grand masks excluded; pairs are even)

Monte Carlo and estimand delegation

Monte Carlo draws random coalitions and does not embed Shapley weights. Coalition payoffs \(v(S)\) are aggregated by the selected estimand plugin:

\[\text{MC} \rightarrow \{v(S_k)\}_{k=1}^{m} \xrightarrow{\text{EstimandAggregator}} (\phi_1, \ldots, \phi_n)\]

The same sampled masks yield different attributions under Shapley vs Banzhaf — a useful sanity check that estimand wiring is correct.

Complementary contributions

Complementary sampling evaluates symmetric pairs and accumulates CC statistics in \(M_{i,j}\) (how often player \(i\) appears in size-\(j\) coalitions) and \(C_{i,j}\) (summed complementary contributions). For pair \((S, N\setminus S)\) with payoffs \(v(S)\) and \(v(N\setminus S)\):

\[u = v(S) - v(N\setminus S)\]

Each \(u\) updates \(C\) for players present in \(S\) and \(N\setminus S\). Final attributions combine element-wise ratios \(C_{i,j}/M_{i,j}\) across coalition sizes.

Neyman allocation

Neyman-CC extends complementary sampling with two phases:

  1. Initial sampling — structured draws that fill every \(M_{i,j}\) cell at least \(m_{\text{init}}\) times (unless the total budget is exhausted).

  2. Neyman allocation — remaining budget is split across coalition sizes \(j \ge \lceil n/2 \rceil\) proportional to estimated standard deviations \(\hat\sigma_{i,j}\).

Variance estimates use the complementary sample variance:

\[\hat\sigma^2_{i,j} = \frac{1}{M_{i,j}-1} \left(\sum u^2 - \frac{(\sum u)^2}{M_{i,j}}\right)\]

Allocation follows the Neyman rule (symmetric halves summed):

\[\hat M_j \propto \sqrt{ \sum_{i} \frac{\hat\sigma^2_{i,j}}{j+1} + \sum_{i} \frac{\hat\sigma^2_{i,n-j-1}}{n-j} }\]

Approximation floor: when the total budget is small, phase one may consume the entire allowance before Neyman allocation begins. In that regime the estimator behaves like complementary sampling — a useful lower bound on accuracy per call.

Because allocation depends on phase-one payoffs, Neyman requires a two-step API: sample_masks() (phase one), begin_allocation(), then sample_allocation_masks().

Further reading