Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling
Abstract
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.
Cite
Text
Burgess and Chapman. "Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/11Markdown
[Burgess and Chapman. "Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/burgess2021ijcai-approximating/) doi:10.24963/IJCAI.2021/11BibTeX
@inproceedings{burgess2021ijcai-approximating,
title = {{Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling}},
author = {Burgess, Mark Alexander and Chapman, Archie C.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {73-81},
doi = {10.24963/IJCAI.2021/11},
url = {https://mlanthology.org/ijcai/2021/burgess2021ijcai-approximating/}
}