Estimation of the Shapley value by ergodic sampling

The idea of approximating the Shapley value of an n-person game by random sampling was introduced by Castro et al. (2009) and further improved by Maleki et al. (2013) and Castro et al. (2017) using stratification. In contrast to their independent sampling method, in this paper, we develop an algorithm that uses a pair of negatively correlated samples to reduce the variance of the estimation. We examine eight games with different characteristics to test the performance of our proposed algorithm. We show that in most cases (seven of eight) this method has at least as low variance as an independent sample, and in some instances (five of eight), it dramatically (almost 60% on average) improves the quality of the estimation. After analyzing the results, we conclude that the recommended method works best in case of games with high variability in the marginal contributions.