Fast approximation of Shapley values through factorial designs

Music City Center 

Shapley value is a well-known concept in cooperative game theory which provides a fair way to distribute the revenues or costs to each player. Recently, it has been widely applied in data science for data quality evaluation and model interpretation. There are also other applications beyond economics such as marketing and biology. 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 values for $2^n$ different coalitions, which makes it infeasible for a large $n$. \revB{In this paper, we find that the value function of a cooperative game can be viewed as the expected response of a two-level factorial experiment. Based on this perspective, we derive a factorial effects representation of the Shapley value. Then, a fast approximation approach for Shapley values based on fractional factorial designs is proposed.} Under certain conditions, our approach can obtain true Shapley values by calculating values of fewer than $4n^2-4$ different coalitions. Generally, highly accurate approximations of Shapley values can also be obtained by calculating values of additional

interoperable artificial intelligence

design of experiments

computation

game theory 

International Chinese Statistical Association