Counterfactual Explanation of Shapley Value in Data Coalitions

The Shapley value is widely used for data valuation in data markets. However, explaining the Shapley value of an owner in a data coalition is an unexplored and challenging task. To tackle this, we formulate the problem of finding the counterfactual explanation of Shapley value in data coalitions. Essentially, given two data owners AandBsuch that A has a higher Shapley value than B, a counter factual explanation is a smallest subset of data entries in Asuch that transferring the subset from A to Bmakes the Shapley value of A less than that of B. We show that counterfactual explanations always exist, but finding an exact counterfactual explanation is NP-hard. Using Monte Carlo estimation to approximate counter factual explanations directly according to the definition is still very costly, since we have to estimate the Shapley values of owners Aand B after each possible subset shift. We develop a series of heuristic techniques to speed up computation by estimating differential Shapley values, computing the power of singular data entries, and shifting subsets greedily, culminating in the SV-Exp algorithm. Our experimental results on real datasets clearly demonstrate the efficiency of our method and the effectiveness of counterfactuals in interpreting the Shapley value of an owner.

Duke Scholars

Author Jian Pei Computer Science