A1192
Title: Fast approximation of Shapley values through fractional factorial designs
Authors: Wei Zheng - University of Tennessee (United States) [presenting]
Zheng Zhou - Beijing University of Technology (China)
Robert Mee - University of Tennessee (United States)
Herbert Hamers - Tilburg University (Netherlands)
Abstract: Shapley value is a well-known concept in cooperative game theory that provides a fair way to distribute revenues or costs to each player. Recently, it has been widely applied in various fields, such as data science, marketing, and genetics. However, the computation of the Shapley value is an NP-hard problem. For a cooperative game with $n$ players, calculating Shapley values for all players requires calculating the value function for $2^n$ different coalitions, which makes it infeasible for a large $n$. A fast approximation approach is proposed for Shapley values based on fractional factorial designs. Under certain conditions, the approach can obtain true Shapley values by calculating values of fewer than $4n^2-4$ different coalitions. In general, highly accurate approximations of Shapley values can also be obtained by calculating values of additional $O(n^2)$ different coalitions. Multiple simulations and real case examples demonstrate that, with equivalent computational cost, the method provides significantly more accurate approximations compared with several popular methods.
