Research map / Multi-agent systems and games / Games and equilibria
Approximating the Shapley Value without Marginal Contributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SVARM and Stratified SVARM, parameter-free, unbiased Shapley value approximators that use a marginal-contribution-free representation and update many player estimates per coalition evaluation under a fixed evaluation budget.
Problem
Approximating Shapley values under a fixed budget of value-function evaluations, where existing methods are judged by marginal-contribution counts rather than actual accesses to the costly value function.
Approach
Rewrites the Shapley value as a difference of two weighted averages of coalition worths (positive and negative Shapley values), samples coalitions from tailored distributions so that each sampled coalition updates estimates for many players at once; the stratified variant groups coalitions by size and updates all players per sample.
Key results
- Stratified SVARM has variance bound O(log n / (T - n log n)) and unbiased estimates; SVARM variance bound 2H_n/T̄ (σ+² + σ-²).
- Stratified SVARM+ (without replacement) matches KernelSHAP on explainability games with n=14 and outperforms it on synthetic games.
- Stratified SVARM is significantly superior to ApproShapley and KernelSHAP on synthetic games across player numbers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Stratified SVARM instead of ApproShapley or KernelSHAP | Shapley value approximation · Shoe, Airport, and SOUG games | MSE | Helped |
| Use Stratified SVARM instead of SVARM | Shapley value approximation · Synthetic games | MSE | Helped |
| Use Stratified SVARM instead of Unbiased KernelSHAP | Shapley value approximation · Explainability games | MSE | Helped |
| Use Stratified SVARM+ instead of KernelSHAP | Shapley value approximation · Synthetic games | MSE | Helped |
| Use Stratified SVARM+ instead of KernelSHAP | Shapley value approximation · Explainability games | MSE | Mixed |
| Replace the proposed coalition-size distribution with uniform sampling over sizes 2 to n-2 (ablation) | Stratified SVARM · Synthetic and explainability games | MSE | No clear effect |
| Remove the warm-up phase (ablation) | Stratified SVARM · Synthetic and explainability games | MSE | Helped |
| Sample coalitions without replacement (ablation) | Stratified SVARM · Synthetic and explainability games | MSE | Helped |
Surprising findings
- Sample-mean-based Stratified SVARM+ rivals KernelSHAP, a quadratic-optimization method, on explainability games.
Limitations
- Quadratically growing number of strata in n may challenge higher player numbers.
- Exact MSE evaluation limited to n=14 in explainability games because true Shapley values must be computed exhaustively.
- Stratified SVARM+ samples without replacement and needs linear space in T, disabling on-the-fly approximation.
Experimental setup
Datasets: IMDB movie reviews ImageNet Adult income dataset Airport game Shoe game Sum of Unanimity Games (random)
Benchmarks: Airport game Shoe game SOUG game NLP sentiment analysis game (IMDB, DistilBERT) Image classifier game (ResNet18) Adult classification game
Metrics: mean squared error variance
Baselines: ApproShapley KernelSHAP Unbiased KernelSHAP Stratified Sampling SVARM
Builds on: ApproShapley KernelSHAP Stratified Sampling Maximum sample reuse (Banzhaf)
Closest papers by meaning
- Approximating Shapley Explanations in Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
- KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.87)
- Explaining Probabilistic Models with Distributional Values (ICML 2024 · similarity 0.87)
- Sequential Solution Concepts in Cooperative Games with Generalized Characteristic Functions (NeurIPS 2026 · similarity 0.86)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.86)
- Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.