A0497
Title: Fast approximation of Shapley values via design methods
Authors: Zheng Zhou - Beijing University of Technology (China) [presenting]
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 remarkable connection is first identified between cooperative games and two-level factorial designs, which is a familiar concept from the field of design of experiments (DOE). This inspires the proposal of fast approximation approaches for Shapley values based on design methods. Multiple simulations and real case examples demonstrate that, with equivalent computational cost, the method provides significantly more accurate approximations compared with several popular methods.
