{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,28]],"date-time":"2026-10-28T08:32:36Z","timestamp":1793176356133,"version":"4.5.0"},"reference-count":47,"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":[[2023,7]]},"abstract":"<jats:p>The increasing demand for data-driven machine learning (ML) models has led to the emergence of model markets, where a broker collects personal data from data owners to produce high-usability ML models. To incentivize data owners to share their data, the broker needs to price data appropriately while protecting their privacy. For<jats:italic>equitable data valuation<\/jats:italic>, which is crucial in data pricing,<jats:italic>Shapley value<\/jats:italic>has become the most prevalent technique because it satisfies all four desirable properties in fairness: balance, symmetry, zero element, and additivity. For<jats:italic>the right to be forgotten<\/jats:italic>, which is stipulated by many data privacy protection laws to allow data owners to unlearn their data from trained models, the<jats:italic>sharded structure<\/jats:italic>in ML model training has become a de facto standard to reduce the cost of future unlearning by avoiding retraining the entire model from scratch. In this paper, we explore how the sharded structure for the right to be forgotten affects Shapley value for equitable data valuation in model markets. To adapt Shapley value for the sharded structure, we propose S-Shapley value, a sharded structure-based Shapley value, which satisfies four desirable properties for data valuation. Since we prove that computing S-Shapley value is #P-complete, two sampling-based methods are developed to approximate S-Shapley value. Furthermore, to efficiently update valuation results after data owners unlearn their data, we present two delta-based algorithms that estimate the change of data value instead of the data value itself. Experimental results demonstrate the efficiency and effectiveness of the proposed algorithms.<\/jats:p>","DOI":"10.14778\/3611479.3611531","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"3349-3362","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Equitable Data Valuation Meets the Right to Be Forgotten in Model Markets"],"prefix":"10.14778","volume":"16","author":[{"given":"Haocheng","family":"Xia","sequence":"first","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinfei","family":"Liu","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jian","family":"Lou","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhan","family":"Qin","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kui","family":"Ren","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"Hokkaido University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Xiong","sequence":"additional","affiliation":[{"name":"Emory University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. Technical Report. https:\/\/github.com\/ZJU-DIVER\/ValuationMeetsRTBF\/TR.pdf 2023. Technical Report. https:\/\/github.com\/ZJU-DIVER\/ValuationMeetsRTBF\/TR.pdf"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402801"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407854"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00019"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.35"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.01.019"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1365\/s43439-021-00038-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300078"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320231"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3559352"},{"key":"e_1_2_1_11_1","volume-title":"Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13--15","volume":"130","author":"Covert Ian","year":"2021","unstructured":"Ian Covert and Su-In Lee . 2021 . Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13--15 , 2021, Virtual Event (Proceedings of Machine Learning Research), Arindam Banerjee and Kenji Fukumizu (Eds.) , Vol. 130 . PMLR, 3457--3465. http:\/\/proceedings.mlr.press\/v130\/covert21a.html Ian Covert and Su-In Lee. 2021. Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13--15, 2021, Virtual Event (Proceedings of Machine Learning Research), Arindam Banerjee and Kenji Fukumizu (Eds.), Vol. 130. PMLR, 3457--3465. http:\/\/proceedings.mlr.press\/v130\/covert21a.html"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407800"},{"key":"e_1_2_1_13_1","unstructured":"GDPR.eu. 2018. Article 17: Right to be forgotten. (2018). https:\/\/gdpr.eu\/article-17-right-to-beforgotten GDPR.eu. 2018. Article 17: Right to be forgotten. (2018). https:\/\/gdpr.eu\/article-17-right-to-beforgotten"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18","volume":"119","author":"Ghorbani Amirata","year":"2020","unstructured":"Amirata Ghorbani , Michael P. Kim , and James Zou . 2020 . A Distributional Framework For Data Valuation . In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18 July 2020, Virtual Event (Proceedings of Machine Learning Research) , Vol. 119 . PMLR, 3535--3544. http:\/\/proceedings.mlr.press\/v119\/ghorbani20a.html Amirata Ghorbani, Michael P. Kim, and James Zou. 2020. A Distributional Framework For Data Valuation. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18 July 2020, Virtual Event (Proceedings of Machine Learning Research), Vol. 119. PMLR, 3535--3544. http:\/\/proceedings.mlr.press\/v119\/ghorbani20a.html"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15","volume":"97","author":"Ghorbani Amirata","year":"2019","unstructured":"Amirata Ghorbani and James Y. Zou . 2019. Data Shapley: Equitable Valuation of Data for Machine Learning . In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15 June 2019 , Long Beach, California, USA (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) , Vol. 97 . PMLR, 2242--2251. http:\/\/proceedings.mlr.press\/v97\/ghorbani19c.html Amirata Ghorbani and James Y. Zou. 2019. Data Shapley: Equitable Valuation of Data for Machine Learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 2242--2251. http:\/\/proceedings.mlr.press\/v97\/ghorbani19c.html"},{"key":"e_1_2_1_16_1","volume-title":"Making AI Forget You: Data Deletion in Machine Learning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Ginart Antonio","year":"2019","unstructured":"Antonio Ginart , Melody Y. Guan , Gregory Valiant , and James Zou . 2019 . Making AI Forget You: Data Deletion in Machine Learning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, December 8--14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 3513--3526. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/cb79f8fa58b91d3af6c9c991f63962d3-Abstract.html Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. 2019. Making AI Forget You: Data Deletion in Machine Learning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8--14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 3513--3526. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/cb79f8fa58b91d3af6c9c991f63962d3-Abstract.html"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056124"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i13.17371"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18","volume":"119","author":"Guo Chuan","year":"2020","unstructured":"Chuan Guo , Tom Goldstein , Awni Y. Hannun , and Laurens van der Maaten. 2020. Certified Data Removal from Machine Learning Models . In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18 July 2020 , Virtual Event (Proceedings of Machine Learning Research) , Vol. 119 . PMLR, 3832--3842. http:\/\/proceedings.mlr.press\/v119\/guo20c.html Chuan Guo, Tom Goldstein, Awni Y. Hannun, and Laurens van der Maaten. 2020. Certified Data Removal from Machine Learning Models. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18 July 2020, Virtual Event (Proceedings of Machine Learning Research), Vol. 119. PMLR, 3832--3842. http:\/\/proceedings.mlr.press\/v119\/guo20c.html"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"234","DOI":"10.69554\/TCFN5165","article-title":"Understanding the scope and impact of the California Consumer Privacy Act of 2018","volume":"2","author":"Harding Elizabeth Liz","year":"2019","unstructured":"Elizabeth Liz Harding , Jarno J Vanto , Reece Clark , L Hannah Ji , and Sara C Ainsworth . 2019 . Understanding the scope and impact of the California Consumer Privacy Act of 2018 . Journal of Data Protection & Privacy 2 , 3 (2019), 234 -- 253 . Elizabeth Liz Harding, Jarno J Vanto, Reece Clark, L Hannah Ji, and Sara C Ainsworth. 2019. Understanding the scope and impact of the California Consumer Privacy Act of 2018. Journal of Data Protection & Privacy 2, 3 (2019), 234--253.","journal-title":"Journal of Data Protection & Privacy"},{"key":"e_1_2_1_21_1","volume-title":"The collected works of Wassily Hoeffding","author":"Hoeffding Wassily","unstructured":"Wassily Hoeffding . 1994. Probability inequalities for sums of bounded random variables . In The collected works of Wassily Hoeffding . Springer , 409--426. Wassily Hoeffding. 1994. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding. Springer, 409--426."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342637"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994514"},{"key":"e_1_2_1_24_1","volume-title":"International Conference on Artificial Intelligence and Statistics, AISTATS 2022","volume":"151","author":"Kwon Yongchan","year":"2022","unstructured":"Yongchan Kwon and James Zou . 2022 . Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning . In International Conference on Artificial Intelligence and Statistics, AISTATS 2022 , 28--30 March 2022, Virtual Event (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 Yongchan Kwon and James Zou. 2022. Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28--30 March 2022, Virtual Event (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_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081891"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00297"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476380"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735505"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447700"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551829"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3045927"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457239"},{"key":"e_1_2_1_33_1","volume-title":"NIPS 2022","author":"Schoch Stephanie","year":"2022","unstructured":"Stephanie Schoch , Haifeng Xu , and Yangfeng Ji . 2022 . CS-Shapley: Class-wise Shapley Values for Data Valuation in Classification. In Advances in Neural Information Processing Systems 36 [Neural Information Processing Systems , NIPS 2022 , Nov 29 th - Dec 1st , 2022, New Orleans, USA]. https:\/\/neurips.cc\/Conferences\/2022\/ScheduleMultitrack?event=53147 Stephanie Schoch, Haifeng Xu, and Yangfeng Ji. 2022. CS-Shapley: Class-wise Shapley Values for Data Valuation in Classification. In Advances in Neural Information Processing Systems 36 [Neural Information Processing Systems, NIPS 2022, Nov 29th - Dec 1st, 2022, New Orleans, USA]. https:\/\/neurips.cc\/Conferences\/2022\/ScheduleMultitrack?event=53147"},{"key":"e_1_2_1_34_1","volume-title":"A value for n-person games. Contributions to the Theory of Games 2, 28","author":"Shapley Lloyd S","year":"1953","unstructured":"Lloyd S Shapley . 1953. A value for n-person games. Contributions to the Theory of Games 2, 28 ( 1953 ), 307--317. Lloyd S Shapley. 1953. A value for n-person games. Contributions to the Theory of Games 2, 28 (1953), 307--317."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/782"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2922638"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2641190.2641198"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512222"},{"key":"e_1_2_1_39_1","volume-title":"International Conference on Artificial Intelligence and Statistics, AISTATS 2023, 25--27 April 2023, Palau de Congressos, Valencia, Spain (Proceedings of Machine Learning Research). PMLR.","author":"Wang Tianhao","year":"2023","unstructured":"Tianhao Wang and Ruoxi Jia . 2023 . Data Banzhaf: A Robust Data Valuation Framework for Machine Learning (Oral) . In International Conference on Artificial Intelligence and Statistics, AISTATS 2023, 25--27 April 2023, Palau de Congressos, Valencia, Spain (Proceedings of Machine Learning Research). PMLR. Tianhao Wang and Ruoxi Jia. 2023. Data Banzhaf: A Robust Data Valuation Framework for Machine Learning (Oral). In International Conference on Artificial Intelligence and Statistics, AISTATS 2023, 25--27 April 2023, Palau de Congressos, Valencia, Spain (Proceedings of Machine Learning Research). PMLR."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-63076-8_11"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-63076-8_10"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476335"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588728"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00055"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2020.3043382"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587141"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2994641"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611531","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T21:02:43Z","timestamp":1729976563000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":47,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611531"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611531","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}