We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Assessing Antithetic Sampling for Approximating Shapley, Banzhaf, and Owen Values.
- Authors
Staudacher, Jochen; Pollmann, Tim
- Abstract
Computing Shapley values for large cooperative games is an NP-hard problem. For practical applications, stochastic approximation via permutation sampling is widely used. In the context of machine learning applications of the Shapley value, the concept of antithetic sampling has become popular. The idea is to employ the reverse permutation of a sample in order to reduce variance and accelerate convergence of the algorithm. We study this approach for the Shapley and Banzhaf values, as well as for the Owen value which is a solution concept for games with precoalitions. We combine antithetic samples with established stratified sampling algorithms. Finally, we evaluate the performance of these algorithms on four different types of cooperative games.
- Subjects
COOPERATIVE game theory; STATISTICAL sampling; PERMUTATIONS; ALGORITHMS; VARIANCES
- Publication
AppliedMath, 2023, Vol 3, Issue 4, p957
- ISSN
2673-9909
- Publication type
Article
- DOI
10.3390/appliedmath3040049