{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:13Z","timestamp":1779174793443,"version":"3.51.4"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>\n            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\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            such that\n            <jats:italic>A<\/jats:italic>\n            has a higher Shapley value than\n            <jats:italic>B<\/jats:italic>\n            , a counter-factual explanation is a smallest subset of data entries in\n            <jats:italic>A<\/jats:italic>\n            such that transferring the subset from\n            <jats:italic>A<\/jats:italic>\n            to\n            <jats:italic>B<\/jats:italic>\n            makes the Shapley value of\n            <jats:italic>A<\/jats:italic>\n            less than that of\n            <jats:italic>B.<\/jats:italic>\n            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\n            <jats:italic>A<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/3681954.3682004","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"3332-3345","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Counterfactual Explanation of Shapley Value in Data Coalitions"],"prefix":"10.14778","volume":"17","author":[{"given":"Michelle","family":"Si","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Pei","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1257\/jel.54.2.442"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329589"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29659-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-48533-1_18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44987-6_8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Arjun R Akula Shuai Wang and Song-Chun Zhu. 2020. CoCoX: Generating Conceptual and Counterfactual Explanations via Fault-Lines.. In AAAI. 2594--2601.","DOI":"10.1609\/aaai.v34i03.5643"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dib.2018.11.126"},{"key":"e_1_2_1_8_1","volume-title":"Wortman Vaughan (Eds.)","volume":"34","author":"Bajaj Mohit","year":"2021","unstructured":"Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. 2021. Robust Counterfactual Explanations on Graph Neural Networks. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 5644--5655. https:\/\/proceedings.neurips.cc\/paper\/2021\/file\/2c8c3a57383c63caef6724343eb62257-Paper.pdf"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402801"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-70992-5_8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300078"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461546"},{"key":"e_1_2_1_13_1","volume-title":"DataBright: Towards a Global Exchange for Decentralized Data Ownership and Trusted Computation. CoRR abs\/1802.04780","author":"Dao David","year":"2018","unstructured":"David Dao, Dan Alistarh, Claudiu Musat, and Ce Zhang. 2018. DataBright: Towards a Global Exchange for Decentralized Data Ownership and Trusted Computation. CoRR abs\/1802.04780 (2018). arXiv:1802.04780 http:\/\/arxiv.org\/abs\/1802.04780"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.2.257"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517912"},{"key":"e_1_2_1_16_1","volume-title":"Differential Privacy: A Survey of Results. In Theory and Applications of Models of Computation","author":"Dwork Cynthia","year":"2008","unstructured":"Cynthia Dwork. 2008. Differential Privacy: A Survey of Results. In Theory and Applications of Models of Computation, Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1--19."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407800"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2718178"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229054"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2017.371"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1749603.1749605"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602902"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365768"},{"key":"e_1_2_1_24_1","volume-title":"Deep learning","author":"Goodfellow Ian","unstructured":"Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep learning. MIT press."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-0696(78)90006-2"},{"key":"e_1_2_1_26_1","unstructured":"Miguel A Hern\u00e1n and James M Robins. 2010. Causal inference."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236266"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Masashi Sugiyama (Eds.)","volume":"89","author":"Jia Ruoxi","unstructured":"Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve G\u00fcrel, Bo Li, Ce Zhang, Dawn Song, and Costas J. Spanos. 2019. Towards Efficient Data Valuation Based on the Shapley Value. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Masashi Sugiyama (Eds.), Vol. 89. PMLR, 1167--1176. https:\/\/proceedings.mlr.press\/v89\/jia19a.html"},{"key":"e_1_2_1_29_1","volume-title":"Machine learning: Trends, perspectives, and prospects. Science 349, 6245","author":"Jordan Michael I","year":"2015","unstructured":"Michael I Jordan and Tom M Mitchell. 2015. Machine learning: Trends, perspectives, and prospects. Science 349, 6245 (2015), 255--260."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3572751.3572757"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Gustau Camps-Valls, Francisco J","author":"Kwon Yongchan","unstructured":"Yongchan Kwon and James Zou. 2022. Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.), Vol. 151. PMLR, 8780--8802. https:\/\/proceedings.mlr.press\/v151\/kwon22a.html"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 40th International Conference on Machine Learning","author":"Kwon Yongchan","year":"2023","unstructured":"Yongchan Kwon and James Zou. 2023. Data-OOB: Out-of-Bag Estimate as a Simple and Efficient Data Value. In Proceedings of the 40th International Conference on Machine Learning (Honolulu, Hawaii, USA) (ICML'23). JMLR.org, Article 749, 18 pages."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403066"},{"key":"e_1_2_1_35_1","volume-title":"Deep learning. nature 521, 7553","author":"LeCun Yann","year":"2015","unstructured":"Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015. Deep learning. nature 521, 7553 (2015), 436--444."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691191"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551829"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639311"},{"key":"e_1_2_1_39_1","unstructured":"Sasan Maleki Long Tran-Thanh Greg Hines Talal Rahwan and Alex Rogers. 2013. Bounding the Estimation Error of Sampling-based Shapley Value Approximation. arXiv:1306.4265 [cs.GT]"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29908-8_4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400051.3400058"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554835"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220013"},{"key":"e_1_2_1_44_1","volume-title":"2013 IEEE International Conference on Big Data. 38--42","author":"Pantelis K.","unstructured":"K. Pantelis and L. Aija. 2013. Understanding the value of (big) data. In 2013 IEEE International Conference on Big Data. 38--42."},{"key":"e_1_2_1_45_1","volume-title":"Causal inference in statistics: An overview. Statistics surveys 3","author":"Pearl Judea","year":"2009","unstructured":"Judea Pearl. 2009. Causal inference in statistics: An overview. Statistics surveys 3 (2009), 96--146."},{"key":"e_1_2_1_46_1","volume-title":"Causal inference. Causality: objectives and assessment","author":"Pearl Judea","year":"2010","unstructured":"Judea Pearl. 2010. Causal inference. Causality: objectives and assessment (2010), 39--58."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3045927"},{"key":"e_1_2_1_48_1","volume-title":"Data science and its relationship to big data and data-driven decision making. Big data 1, 1","author":"Provost Foster","year":"2013","unstructured":"Foster Provost and Tom Fawcett. 2013. Data science and its relationship to big data and data-driven decision making. Big data 1, 1 (2013), 51--59."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/245108.245121"},{"key":"e_1_2_1_50_1","volume-title":"Abbas Kazerouni, Ian Osband, and Zheng Wen.","author":"Russo Daniel","year":"2020","unstructured":"Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. 2020. A Tutorial on Thompson Sampling. arXiv:1707.02038 [cs.LG]"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481528.2481532"},{"key":"e_1_2_1_53_1","unstructured":"Kacper Sokol and Peter A Flach. 2019. Counterfactual explanations of machine learning predictions: opportunities and challenges for AI safety. In SafeAI@AAAI."},{"key":"e_1_2_1_54_1","volume-title":"The Stanford Encyclopedia of Philosophy (Winter 2022 ed.), Edward N","author":"Starr W.","unstructured":"W. Starr. 2022. Counterfactuals. In The Stanford Encyclopedia of Philosophy (Winter 2022 ed.), Edward N. Zalta and Uri Nodelman (Eds.). Metaphysics Research Lab, Stanford University."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/25.3--4.285"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371219"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241094.3241142"},{"key":"e_1_2_1_58_1","volume-title":"Interpretable counterfactual explanations guided by prototypes. arXiv preprint arXiv:1907.02584","author":"Looveren Arnaud Van","year":"2019","unstructured":"Arnaud Van Looveren and Janis Klaise. 2019. Interpretable counterfactual explanations guided by prototypes. arXiv preprint arXiv:1907.02584 (2019)."},{"key":"e_1_2_1_59_1","first-page":"841","article-title":"Counterfactual explanations without opening the black box: Automated decisions and the GDPR","volume":"31","author":"Wachter Sandra","year":"2017","unstructured":"Sandra Wachter, Brent Mittelstadt, and Chris Russell. 2017. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harv. JL & Tech. 31 (2017), 841.","journal-title":"Harv. JL & Tech."},{"key":"e_1_2_1_60_1","volume-title":"Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation. arXiv preprint arXiv:2308.15709","author":"Wang Jiachen T","year":"2023","unstructured":"Jiachen T Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. 2023. Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation. arXiv preprint arXiv:2308.15709 (2023)."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_14"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1540276.1540279"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","unstructured":"Matjaz Zwitter and Milan Soklic. 1988. Breast Cancer. UCI Machine Learning Repository. 10.24432\/C51P4M","DOI":"10.24432\/C51P4M"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3682004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:38:15Z","timestamp":1725475095000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3682004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":62,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3682004"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3682004","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}