Estimation of the Shapley value by ergodic sampling

Abstract

The Monte Carlo approximation of the Shapley value in cooperative games was first proposed by Mann and Shapley (1960), who introduced several heuristic techniques to reduce estimation error. Since then, classical variance reduction methods from the statistical literature have been adapted to improve the efficiency of Shapley value estimators. In this paper, we demonstrate that the antithetic variates method can be successfully applied to the Monte Carlo estimation of the Shapley value. We propose an algorithm that generates pairs of negatively correlated samples, leading to a variance reduction by producing dependent observations that satisfy the Strong Law of Large Numbers, which motivates the term ergodic sampling. The main contribution of the paper is to establish the existence of practical, algorithmic ergodic sampling schemes for Shapley value estimation. In contrast to the heuristic approaches of Shapley and Mann, our method is data–driven: a relatively small pilot sample is used to learn an effective ergodic transformation tailored to the given game. Through numerical experiments on eight structurally diverse cooperative games, we show that the proposed approach achieves estimation accuracy comparable to other variance reduction techniques in the literature, and in several cases yields substantial variance reductions relative to independent Monte Carlo sampling.