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 2n 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 4n2−4 different coalitions. Generally, highly accurate approximations of Shapley values can also be obtained by evaluating values of additional O(n2) coalitions. Multiple simulations and real case examples demonstrate that, with equivalent computational cost, our method provides significantly more accurate approximations than several popular methods.