Stratified Sampling for Shapley Value Estimation: A Variance-Optimal Approach

The computation of the Shapley value is a central problem in cooperative game theory, but its factorial complexity makes exact evaluation infeasible for large-scale games. In this work, we reinterpret the Shapley value as a stratified expectation over coalition sizes, revealing an inherent two-stage sampling structure. Based on this formulation, we introduce a class of stratified Monte Carlo estimators that decouple the target distribution from the sampling design. This enables the use of variance reduction techniques from survey sampling, including optimal allocation strategies such as Neyman allocation. We derive unbiased estimators under general sampling distributions and provide a variance analysis that characterizes the optimal sampling scheme. Experimental results show that the proposed approach significantly improves convergence in structured games where marginal contributions depend on coalition size, while maintaining comparable performance in unstructured settings. The proposed framework is simple, flexible, and naturally parallelizable, making it well suited for large-scale applications.