  The idea of approximating the Shapley value of an n-person game by Monte
Carlo simulation was first suggested by Mann and Shapley (1960) and they also
introduced four different heuristical methods to reduce the estimation error.
Since 1960, several statistical methods have been developed to reduce the
standard deviation of the estimate. In this paper, we develop an algorithm that
uses a pair of negatively correlated samples to reduce the variance of the
estimate. Although the observations generated are not independent, the sample
is ergodic (obeys the strong law of large numbers), hence the name "ergodic
sampling". Unlike Shapley and Mann, we do not use heuristics, the algorithm
uses a small sample to learn the best ergodic transformation for a given game.
We illustrate the algorithm on eight games with different characteristics to
test the performance and understand how the proposed algorithm works. The
experiments show that this method has at least as low variance as an
independent sample, and in five test games, it significantly improves the
quality of the estimation, up to 75 percent.
