Session IX (May 17, 8:30am-10:00am): Optimal Experimental Design, organized by Abhyuday Mandal

• Title: Approximating Shapley Values by Fractional Factorial Designs 

• Speaker: Wei Zheng, University of Tennesse

•  Abstract: 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 various fields such as data science, marketing, genetics. However, the computation of the Shapley value is an NP-hard problem. For a cooperative game with $n$ players,  calculating the Shapley value for one player requires calculating the value function for $2^n$ different coalitions, which makes it infeasible to calculate the Shapley value for a large $n$. \revA{In this paper, we propose a fast approximation approach for Shapley values based on fractional factorial designs. When the value function satisfies certain conditions, our approach can obtain true Shapley values by calculating contributions of  fewer than $4d^2-4$ different coalitions.  For general cases, highly accurate approximations of Shapley values can also be yielded by calculating contributions of additional $O(d^2)$ different coalitions.} Multiple simulations and real case examples demonstrate that, with equivalent computational cost, our method provides significantly more accurate approximations compared with several popular methods.