Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation

In this paper, we propose a refinement of the polynomial method based on sampling theory proposed by Castro et al. (2009) to estimate the Shapley value for cooperative games. In addition to analyzing the variance of the previously proposed estimation method, we employ stratified random sampling with optimum allocation in order to reduce the variance. We examine some desirable statistical features of the stratified approach and provide some computational results by analyzing the gains due to stratification, which are around 30% on average and more than 80% in the best case.