Counterfactual Explanation of Shapley Value in Data Coalitions

Michelle Si, Jian Pei · 2025

Read Counterfactual Explanation of Shapley Value in Data Coalitions by Michelle Si, Jian Pei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01267.txt.

Introduction

Michelle Si and Jian Pei tackle a puzzle in data markets: why one owner's data are worth more than another's. Their 2025 paper uses the Shapley value, a fair-division score from game theory. They seek a counterfactual account: the smallest set of entries whose move from one owner to another would flip their ranking.

They show such an account always exists, but finding the exact one is NP-hard. A direct sampling route is also too costly, since each trial needs fresh value estimates. Their algorithm, SV-Exp, speeds the work with three tricks: tracking value changes, scoring single entries, and shifting sets greedily. Tests on real data show the method is fast and that the accounts help explain value gaps.

Catalog record

CREATORMichelle Si, Jian Pei
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-01267

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counterfactual Explanation of Shapley Value in Data Coalitions Michelle Si, Jian Pei Abstract . 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 A A and B B such that A A has a higher Shapley value than B B , a counterfactual explanation is a smallest subset of data entries in A A such that transferring the subset from A A to B B makes the Shapley value of A A less than that of B B . We show that counterfactual explanations always exist, but finding an exact counterfactual explanation is NP-hard. Using Monte Carlo estimation to approximate counterfactual explanations directly according to the definition is still very costly, since we have to estimate the Shapley values of owners A A and B 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. † † authors: . PVLDB Reference Format: PVLDB, 17(11): 3332 - 3345, 2024. doi:10.14778/3681954.3682004 † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 17, No. 11 ISSN 2150-8097. doi:10.14778/3681954.3682004 PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/michelleeesi/shapley_counterfactual . 1. Introduction The power of big data largely comes from many secondary uses of data, such as enabling numerous machine learning and AI models ( Jordan and Mitchell 2015 ; LeCun et al. 2015 ; Goodfellow et al. 2016 ) , recommender systems ( Resnick and Varian 1997 ; Aggarwal 2016 ) , causal inference ( Hernán and Robins 2010 ; Pearl 2010 ; Pearl 2009 ) , and data-driven decision-making applications ( Provost and Fawcett 2013 ) . However, incentivizing and facilitating data sharing and collaboration at scale remains a great challenge. Data markets ( Schomm et al. 2013 ; Pantelis and Aija 2013 ; Chen et al. 2019 ; Kennedy et al. 2022 ; Fernandez et al. 2020 ) are emerging as a promising way to enable and facilitate data sharing among many potential owners and consumers. Essentially, a data market is an online platform where various parties with demands can acquire datasets or data services; at the same time, data owners can exchange data and data services for revenue or compensations in one way or another. There are already many active data markets, such as AWS Data Exchange, Windows Azure Marketplace, Dawex, Datarade, dmi.io, WorldQuant, Xignite, and BlueTalon ( Kennedy et al. 2022 ) . At the core of every data market, there is a data valuation module. In a data market, a group of data owners collaborate to produce a target dataset or complete a target task that a buyer would like to acquire, such as assembling a dataset for data analytics or machine learning. We call collaboration among data owners a data coalition , where multiple datasets owned by different parties are used to produce target datasets. In a nutshell, data valuation assigns a score to a data owner to reflect the data owner’s contribution towards a task achieved by a data coalition. Data valuation plays a central role in ensuring fairness, effectiveness, and efficiency of data markets. There are various requirements on data valuation in different data markets ( Pei 2022 ) , such as truthfulness ( Agarwal et al. 2019 ) , revenue maximization, fairness ( Shapley 1952 ; Agarwal et al. 2019 ) , arbitrage-freeness ( Li et al. 2015 ) , privacy-preservation ( Acquisti et al. 2016 ; Fleischer and Lyu 2012 ; Niu et al. 2018 ; Tramèr et al. 2016 ; Aiello et al. 2001 ; Hynes et al. 2018 ; Dao et al. 2018 ; Nissim et al. 2014 ; Ghosh et al. 2014 ; Fung et al. 2010 ; Aggarwal and Yu 2008 ; Bertino et al. 2008 ; Dwork 2008 ; Zhou et al. 2008 ; Ferrag et al. 2017 ; Wu et al. 2010 ) , and computational efficiency ( Balazinska et al. 2011 ; Agarwal et al. 2019 ; Goldberg et al. 2001 ) . The rich diversity in requirements poses many technical challenges for data valuation solutions. The Shapley value ( Shapley 1952 ) is often used as a measure in data valuation ( Kwon and Zou 2023 ; Kwon and Zou 2022 ; Wang et al. 2023 ) , which is the expectation of marginal utility gain that a data owner can bring into coalitions. We will review the mathematical details in Section 2 . The Shapley value is the only valuation measure that provably satisfies efficiency, symmetry, zero element, and additivity. While numerous studies have investigated the fast computation of Shapley values by either designing cost-saving sampling strategies ( Maleki et al. 2013 ; Jia et al. 2019 ) or tackling the Shapley computation in specific settings ( Deutch et al. 2022 ) , one important question remains unexplored: how can one understand and explain the Shapley value of a data owner in a data coalition? Let us consider a concrete example. Suppose two data owners, Alice and Brittany, participate in a data coalition \mathbb{O} and obtain their Shapley values \psi_{\mathbb{O}}(Alice) and \psi_{\mathbb{O}}(Brittany) , respectively. Without loss of generality, let us assume \psi_{\mathbb{O}}(Alice)>\psi_{\mathbb{O}}(Brittany) . Then, one may ask how we can explain Alice’s advantage over Brittany according to their Shapley values. To answer this question, one intuitive approach is to look for a counterfactual explanation, which is a minimal subset S of data owned by Alice such that transferring S from Alice to Brittany can flip the direction of the inequality, that is, making \psi_{\mathbb{O}}(Alice)<\psi_{\mathbb{O}}(Brittany) . Using counterfactuals as an explanation tactic is a well established approach in philosophy and has enjoyed numerous applications in many domains ( Starr 2022 ) . A counterfactual explanation S provides some interesting insights. For example, by checking the data entries in S , one may understand which data entries are the most crucial for Alice’s advantage—what really makes Alice be able to contribute more and thus be more valuable than Brittany in the coalition? The counterfactual explanation allows us to detail the root of differences in Shapley values between data owners in a way that the Shapley value itself does not illuminate. For example, if Alice owns much more data than Alice but the size of the counterfactual explanation is small, it means that Alice’s advantage is driven by a few powerful rows of data–the elements of the counterfactual. To use another analogy, using a counterfactual explanation

Read the complete text