Fast Approximation of Shapley Values through Fractional Factorial Designs

The Shapley value is a well-known concept in cooperative game theory that provides a fair way to distribute revenues or costs among players. It has found applications in many fields besides economics, such as marketing and biology. Recently, it has been widely applied in data science for data quality evaluation and model interpretation. 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 evaluating the values for 2(n) different coalitions, which makes it infeasible for large n. In this article, we reveal the connection between cooperative games and two-level factorial experiments. For any coalition, each player's participation status can be represented as a two-level factor, while the coalition value can be viewed as the expected response of an experimental trial under the corresponding factor level combination. Building on this connection, we derive a factorial-effect representation of the Shapley value and propose a fast approximation approach based on a newly proposed fractional factorial design. Under certain conditions, our approach can obtain true Shapley values by evaluating values of fewer than 4n(2)-4 different coalitions. Generally, highly accurate approximations of Shapley values can also be obtained by evaluating values of additional O(n(2)) coalitions. Multiple simulations and real case examples demonstrate that, with equivalent computational cost, our method provides significantly more accurate approximations than several popular methods. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.