Computing Shapley values for large cooperative games is an NP-hard problem. For practical applications, stochastic approximation via permutation sampling is widely used. In the context of machine learning applications of the Shapley value, the concept of antithetic sampling has become popular. The idea is to employ the reverse permutation of a sample in order to reduce variance and accelerate convergence of the algorithm. We study this approach for the Shapley and Banzhaf values, as well as for the Owen value which is a solution concept for games with precoalitions. We combine antithetic samples with established stratified sampling algorithms. Finally, we evaluate the performance of these algorithms on four different types of cooperative games.

Shapley values are the most widely used point-valued solution concept for cooperative games and have recently garnered attention for their applicability in explainable machine learning. Due to the complexity of Shapley value computation, users mostly resort to Monte Carlo approximations for large problems. We take a detailed look at an approximation method grounded in multilinear extensions proposed by Okhrati and Lipani (2021) under the name Owen sampling. We point out why Owen sampling is biased and propose unbiased alternatives based on combining multilinear extensions with stratified sampling and importance sampling. Finally, we discuss empirical results of the presented algorithms for various cooperative games including real-world explainability scenarios.

Shapley values are the most widely used point-valued solution concept for cooperative games and have recently garnered attention for their applicability in explainable machine learning. Due to the complexity of Shapley value computation, users mostly resort to Monte Carlo approximations for large problems. We take a detailed look at an approximation method grounded in multilinear extensions proposed in 2021 under the name “Owen sampling”. We point out why Owen sampling is biased and propose unbiased alternatives based on combining multilinear extensions with stratified sampling and importance sampling. Finally, we discuss empirical results of the presented algorithms for various cooperative games, including real-world explainability scenarios.

The Shapley value stands as the predominant point-valued solution concept in cooperative game theory and has recently become a foundational method in interpretable machine learning. In that domain, a prevailing strategy to circumvent the computational intractability of exact Shapley values is to approximate them by reframing their computation as a weighted least squares optimization problem. We investigate an algorithmic framework by Benati et al. (2019), discuss its feasibility for feature attribution and explore a set of methodological and theoretical refinements, including an approach for sample reuse across strata and a relation to Unbiased KernelSHAP. We conclude with an empirical evaluation of the presented algorithms, assessing their performance on several cooperative games including practical problems from interpretable machine learning.

The Shapley value is the predominant point-valued solution concept in cooperative game theory and has recently become a foundational method in interpretable machine learning. In this domain, a prevailing strategy for circumventing the computational intractability of exact Shapley values is to approximate them via a weighted least squares optimization framework. In this paper, we investigate an existing algorithmic framework for weighted least squares Shapley approximation, assessing its feasibility for feature attribution. Methodologically, we conduct a theoretical variance analysis within a Monte Carlo sampling framework, investigate an approach for sample reuse across strata, and establish a relation to Unbiased KernelSHAP. Our analysis reveals three main findings: (i) a structural equivalence between least squares sampling and Unbiased KernelSHAP; (ii) the non-zero covariance between sampled coalitions introduced by reusing samples across strata in one of the existing least squares-based approaches; and (iii) the absence of a universally optimal sampling strategy across tasks. We validate these results empirically on several cooperative games and practical machine learning problems.