Polynomial calculation of the Shapley value based on sampling, Javier Castro, Daniel Gómez, Juan Tejada. Computers & Operations Research(2009)


In this paper we develop a polynomial method based on sampling theory that can be used to estimate the Shapley value (or any semivalue) for cooperative games. Besides analyzing the complexity problem, we examine some desirable statistical properties of the proposed approach and provide some computational results.