Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling

Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling

Mark A. Burgess, Archie C. Chapman

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence

The Shapley value is a well recognised method for dividing the value of joint effort in cooperative games. However, computing the Shapley value is known to be computationally hard, so stratified sample-based estimation is sometimes used. For this task, we provide two contributions to the state of the art. First, we derive a novel concentration inequality that is tailored to stratified Shapley value estimation using sample variance information. Second, by sequentially choosing samples to minimize our inequality, we develop a new and more efficient method of sampling to estimate the Shapley value. We evaluate our sampling method on a suite of test cooperative games, and our results demonstrate that it outperforms or is competitive with existing stratified sample-based estimation approaches to computing the Shapley value.
Keywords:
Agent-based and Multi-agent Systems: Cooperative Games
Uncertainty in AI: Uncertainty Representations