A stochastic approach to approximate values in cooperative games

Computing additive values in cooperative games, like the Shapley value, is a hard task because, in general, it involves the summation of an exponential number of terms. We propose a new method, based on the stochastic approximation of deterministic games and sampling theory, to calculate a statistic estimate of these values and, at the same time, keeping under control estimation errors. We applied this technique to several well-known games and we show that in many cases we were able to improve previous results. © 2019 Elsevier B.V. All rights reserved