Approximating the Shapley Value with Many Players: A Hybrid Exact/Monte Carlo Estimator
Fuente:
Zenodo
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Recurso digital |
| Publicado: |
Zenodo
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866901794032975872 |
|---|---|
| author | Araar, Abdelkrim |
| author_facet | Araar, Abdelkrim |
| contents | <p>Computing the Shapley value exactly requires evaluating the characteristic function v(·) over all 2^n possible coalitions, which becomes computationally intractable as the number of players n grows beyond 20-25. This paper addresses the question of how<br>to draw coalitions efficiently when exact computation is infeasible. We first establish a unified framework for Monte Carlo Shapley estimators based on a level-stratified representation of the Shapley formula, and show that fixing the coalition-size level<br>before sampling strictly dominates drawing it at random. We then propose a novel Hybrid Exact/Sampling estimator that exploits the binomial structure of coalition counts: levels with few coalitions are enumerated exactly at zero variance cost, while only the large middle levels are sampled. The hybrid estimator is provably unbiased with strictly lower variance than any purely stochastic method at equal cost. We characterise precisely when this advantage is largest: the hybrid dominates<br>when the characteristic function is pseudo-continuous and individual marginal contri- butions are moderate relative to the range of v - conditions met by the broad class of functions used in inequality analysis, production theory, and machine learning<br>interpretability. A Monte Carlo experiment with n = 20 players conrms a 36-89% RMSE reduction relative to the state-of-the-art permutation sampler. A Neyman optimal-allocation variant is also derived, which further reduces variance when within-level dispersion is heterogeneous and the budget is large.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19847586 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Approximating the Shapley Value with Many Players: A Hybrid Exact/Monte Carlo Estimator Araar, Abdelkrim Shapley value Large games <p>Computing the Shapley value exactly requires evaluating the characteristic function v(·) over all 2^n possible coalitions, which becomes computationally intractable as the number of players n grows beyond 20-25. This paper addresses the question of how<br>to draw coalitions efficiently when exact computation is infeasible. We first establish a unified framework for Monte Carlo Shapley estimators based on a level-stratified representation of the Shapley formula, and show that fixing the coalition-size level<br>before sampling strictly dominates drawing it at random. We then propose a novel Hybrid Exact/Sampling estimator that exploits the binomial structure of coalition counts: levels with few coalitions are enumerated exactly at zero variance cost, while only the large middle levels are sampled. The hybrid estimator is provably unbiased with strictly lower variance than any purely stochastic method at equal cost. We characterise precisely when this advantage is largest: the hybrid dominates<br>when the characteristic function is pseudo-continuous and individual marginal contri- butions are moderate relative to the range of v - conditions met by the broad class of functions used in inequality analysis, production theory, and machine learning<br>interpretability. A Monte Carlo experiment with n = 20 players conrms a 36-89% RMSE reduction relative to the state-of-the-art permutation sampler. A Neyman optimal-allocation variant is also derived, which further reduces variance when within-level dispersion is heterogeneous and the budget is large.</p> |
| title | Approximating the Shapley Value with Many Players: A Hybrid Exact/Monte Carlo Estimator |
| topic | Shapley value Large games |
| url | https://doi.org/10.5281/zenodo.19847586 |