{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:37:01Z","timestamp":1791916621683,"version":"4.3.4"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARC Future Fellowship","award":["FT210100303"],"award-info":[{"award-number":["FT210100303"]}]},{"name":"ARC Discovery Project","award":["DP230101445"],"award-info":[{"award-number":["DP230101445"]}]},{"name":"Beyond the Horizon grant by Duke University"},{"name":"Hong Kong RGC CRF Project","award":["C2004-21GF"],"award-info":[{"award-number":["C2004-21GF"]}]},{"name":"NSERC Discovery Grant"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>In this paper, we tackle the challenging problem of Shapley value computation in data markets in a novel setting of data assemblage tasks with binary utility functions among data owners. By modeling these scenarios as cooperative simple games, we leverage pivotal probabilities to transform the computation into a problem of counting beneficiaries. Moreover, we make an insightful observation that the Shapley values can be computed using subsets of minimal syntheses within the inclusion-exclusion framework in combinatorics. Based on this insight, we develop a game decomposition approach and utilize techniques in Boolean function decomposition into disjunctive normal form. One interesting property of our method is that the time complexity depends only on the data owners participating in those minimal syntheses, rather than all the data owners. Extensive experiments with real data sets demonstrate a significant efficiency improvement for computing the Shapley values in data assemblage tasks modeled as simple games.<\/jats:p>","DOI":"10.1145\/3639311","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-28","source":"Crossref","is-referenced-by-count":14,"title":["Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0849-1396","authenticated-orcid":false,"given":"Xuan","family":"Luo","sequence":"first","affiliation":[{"name":"Simon Fraser University, Burnaby, BC, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4412-4609","authenticated-orcid":false,"given":"Jian","family":"Pei","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7256-082X","authenticated-orcid":false,"given":"Cheng","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Kowloon, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6572-2600","authenticated-orcid":false,"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-5848","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Kowloon, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"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":"publisher","DOI":"10.14778\/3402755.3402801"},{"key":"e_1_2_1_7_1","unstructured":"Jan C. Bioch. 2002. Modular Decomposition of Boolean Functions. https:\/\/ssrn.com\/abstract=370984."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.12.010"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2010.5452760"},{"key":"e_1_2_1_11_1","volume-title":"An investigation of the laws of thought: on which are founded the mathematical theories of logic and probabilities","author":"Boole George","unstructured":"George Boole. 1854. An investigation of the laws of thought: on which are founded the mathematical theories of logic and probabilities. Vol. 2. Walton and Maberly."},{"key":"e_1_2_1_12_1","volume-title":"Boolean reasoning - the logic of boolean equations","author":"Brown Frank M.","unstructured":"Frank M. Brown. 1990. Boolean reasoning - the logic of boolean equations. Kluwer."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107415997"},{"key":"e_1_2_1_14_1","volume-title":"Computational Aspects of Cooperative Game Theory (Synthesis Lectures on Artificial Inetlligence and Machine Learning)","author":"Chalkiadakis Georgios","unstructured":"Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. 2011. Computational Aspects of Cooperative Game Theory (Synthesis Lectures on Artificial Inetlligence and Machine Learning) (1st ed.). Morgan & Claypool Publishers.","edition":"1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300078"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases","author":"Cohen Sara","year":"2006","unstructured":"Sara Cohen, Itzhak Fadida, Yaron Kanza, Benny Kimelfeld, and Yehoshua Sagiv. 2006. Full Disjunctions: Polynomial-Delay Iterators in Action. In Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12--15, 2006, Umeshwar Dayal, Kyu-Young Whang, David B. Lomet, Gustavo Alonso, Guy M. Lohman, Martin L. Kersten, Sang Kyun Cha, and Young-Kuk Kim (Eds.). ACM, 739--750. http:\/\/dl.acm.org\/citation.cfm?id=1164191"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-022-01679--4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1980.10486199"},{"key":"e_1_2_1_19_1","volume-title":"Hammer","author":"Crama Yves","year":"2011","unstructured":"Yves Crama and Peter L. Hammer. 2011. Boolean Functions - Theory, Algorithms, and Applications. Encyclopedia of mathematics and its applications, Vol. 142. Cambridge University Press. http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item6222210\/'site_locale=en_GB"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004--3"},{"key":"e_1_2_1_21_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_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.2.257"},{"key":"e_1_2_1_23_1","volume-title":"Computing the Shapley Value of Facts in Query Answering. CoRR abs\/2112.08874","author":"Deutch Daniel","year":"2021","unstructured":"Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mika\u00ebl Monet. 2021. Computing the Shapley Value of Facts in Query Answering. CoRR abs\/2112.08874 (2021). arXiv:2112.08874 https:\/\/arxiv.org\/abs\/2112.08874"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00578ED1V01Y201404DTM040"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01258278"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00118651"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407800"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229054"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9--15","volume":"2251","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, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 2242--2251. http:\/\/proceedings.mlr.press\/v97\/ghorbani19c.html"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602902"},{"key":"e_1_2_1_31_1","volume-title":"Solutions to general non-zero-sum games. Contributions to the Theory of Games 4, 40","author":"Gillies Donald B","year":"1959","unstructured":"Donald B Gillies. 1959. Solutions to general non-zero-sum games. Contributions to the Theory of Games 4, 40 (1959), 47--85."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365768"},{"key":"e_1_2_1_33_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_34_1","unstructured":"Miguel A Hern\u00e1n and James M Robins. 2010. Causal inference."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236266"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342637"},{"key":"e_1_2_1_37_1","volume-title":"Towards Efficient Data Valuation Based on the Shapley Value. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16--18","volume":"1176","author":"Jia Ruoxi","year":"2019","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 The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16--18 April 2019, Naha, Okinawa, Japan (Proceedings of Machine Learning Research, Vol. 89), Kamalika Chaudhuri and Masashi Sugiyama (Eds.). PMLR, 1167--1176. http:\/\/proceedings.mlr.press\/v89\/jia19a.html"},{"key":"e_1_2_1_38_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_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3572751.3572757"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574274"},{"key":"e_1_2_1_41_1","volume-title":"Theoretical Aspects Of Rationality And Knowledge: Proceedings of the 8 th conference on Theoretical aspects of rationality and knowledge","volume":"8","author":"Kleinberg Jon","year":"2001","unstructured":"Jon Kleinberg, Christos H Papadimitriou, and Prabhakar Raghavan. 2001. On the value of private information. In Theoretical Aspects Of Rationality And Knowledge: Proceedings of the 8 th conference on Theoretical aspects of rationality and knowledge, Vol. 8. Citeseer, 249--257."},{"key":"e_1_2_1_42_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_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691191"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.20"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551829"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Xuan Luo Jian Pei Cheng Xu Wenjie Zhang and Jianliang Xu. 2024. Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games (Technical Report). https:\/\/github.com\/IDEAL-Lab\/shapley-value-simple-game\/blob\/main\/technical_report.pdf","DOI":"10.1145\/3639311"},{"key":"e_1_2_1_47_1","volume-title":"Bounding the Estimation Error of Sampling-based Shapley Value Approximation With\/Without Stratifying. CoRR abs\/1306.4265","author":"Maleki Sasan","year":"2013","unstructured":"Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers. 2013. Bounding the Estimation Error of Sampling-based Shapley Value Approximation With\/Without Stratifying. CoRR abs\/1306.4265 (2013). arXiv:1306.4265 http:\/\/arxiv.org\/abs\/1306.4265"},{"key":"e_1_2_1_48_1","volume-title":"Values of large games, IV: Evaluating the electoral college by Montecarlo techniques","author":"Mann Irwin","unstructured":"Irwin Mann and Lloyd S Shapley. 1960. Values of large games, IV: Evaluating the electoral college by Montecarlo techniques. Rand Corporation."},{"key":"e_1_2_1_49_1","volume-title":"The a priori voting strength of the electoral college. Game theory and related approaches to social behavior","author":"Mann Irwin","year":"1964","unstructured":"Irwin Mann and Lloyd S Shapley. 1964. The a priori voting strength of the electoral college. Game theory and related approaches to social behavior (1964), 151--164."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2663171.2663188"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733070"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3240491"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2015.04.008"},{"key":"e_1_2_1_55_1","volume-title":"International workshop on business intelligence for the real-time enterprise. Springer, 129--144","author":"Muschalle Alexander","year":"2012","unstructured":"Alexander Muschalle, Florian Stahl, Alexander L\u00f6ser, and Gottfried Vossen. 2012. Pricing approaches for data markets. In International workshop on business intelligence for the real-time enterprise. Springer, 129--144."},{"key":"e_1_2_1_56_1","volume-title":"Pareto distributions and Zipf's law. Contemporary physics 46, 5","author":"Newman Mark EJ","year":"2005","unstructured":"Mark EJ Newman. 2005. Power laws, Pareto distributions and Zipf's law. Contemporary physics 46, 5 (2005), 323--351."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554835"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220013"},{"key":"e_1_2_1_59_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_60_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_61_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_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3045927"},{"key":"e_1_2_1_63_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_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237717"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/245108.245121"},{"key":"e_1_2_1_66_1","volume-title":"Quantifying Causal Effects on Query Answering in Databases. In 8th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2016","author":"Salimi Babak","year":"2016","unstructured":"Babak Salimi, Leopoldo E. Bertossi, Dan Suciu, and Guy Van den Broeck. 2016. Quantifying Causal Effects on Query Answering in Databases. In 8th USENIX Workshop on the Theory and Practice of Provenance, TaPP 2016, Washington, D.C., USA, June 8--9, 2016, Sarah Cohen Boulakia (Ed.). USENIX Association. https:\/\/www.usenix.org\/conference\/tapp16\/workshop-program\/presentation\/salimi"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481528.2481532"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236253"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538--7305.1949.tb03624.x"},{"key":"e_1_2_1_70_1","volume-title":"New Methods of Thought and Procedure: Contributions to the Symposium on Methodologies","author":"Shapley LS","unstructured":"LS Shapley. 1967. On committees. In New Methods of Thought and Procedure: Contributions to the Symposium on Methodologies. Springer, 246--270."},{"key":"e_1_2_1_71_1","unstructured":"Lloyd S. Shapley. 1952. A Value for n-Person Games. Technical Report P-295. RAND Corporation Santa Monica CA."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241094.3241142"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639311","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:14:17Z","timestamp":1755789257000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":72,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639311"],"URL":"https:\/\/doi.org\/10.1145\/3639311","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}