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

publication date

  • June 2017

start page

  • 180

end page

  • 188

volume

  • 82

international standard serial number (ISSN)

  • 0305-0548

electronic international standard serial number (EISSN)

  • 1873-765X

abstract

  • 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. (C) 2017 Elsevier Ltd. All rights reserved.

keywords

  • computer science; game theory; operations research; shapley value; stratified sampling algorithm; microarray games; complexity; networks; power