Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling

Burgess, Mark A.; Chapman, Archie C.

doi:10.24963/ijcai.2021/11

Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling

Mark A. Burgess, Archie C. Chapman

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 73-81.

https://doi.org/10.24963/ijcai.2021/11

Keywords

Agent-based and Multi-agent Systems: Cooperative Games
Uncertainty in AI: Uncertainty Representations

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.

Mark A. Burgess, and Archie C. Chapman. 2021. Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 73–81. https://doi.org/10.24963/ijcai.2021/11

@inproceedings{ijcai2021p11,
  title     = {Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling},
  author    = {Burgess, Mark A. and Chapman, Archie C.},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {73--81},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/11},
  url       = {https://doi.org/10.24963/ijcai.2021/11},
}

TY  - CPAPER
TI  - Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling
AU  - Burgess, Mark A.
AU  - Chapman, Archie C.
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 73
EP  - 81
DO  - 10.24963/ijcai.2021/11
UR  - https://doi.org/10.24963/ijcai.2021/11
ER  -