EUVIMEDEUVIMED entdecken
Crossref

Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games

Xuan Luo, Jian Pei, Cheng Xu, Wenjie Zhang, Jianliang Xu

Proceedings of the ACM on Management of Data · 12.03.2024 · 2 (1) · 1-28

DOI: 10.1145/3639311 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 26.03.2024. Verfasst von Xuan Luo und 4 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 72 Literaturangaben. Gefördert von: ARC Future Fellowship, ARC Discovery Project, Beyond the Horizon grant by Duke University.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • ARC Future Fellowship
  • ARC Discovery Project
  • Beyond the Horizon grant by Duke University
  • Hong Kong RGC CRF Project
  • NSERC Discovery Grant

Zitieren

APA

Luo, X., Pei, J., Xu, C., Zhang, W., & Xu, J. (2024). Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games. Proceedings of the ACM on Management of Data, 2(1), 1-28. https://doi.org/10.1145/3639311

Vancouver

Luo X, Pei J, Xu C, Zhang W, Xu J. Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games. Proceedings of the ACM on Management of Data. 2024;2(1):1-28. doi:10.1145/3639311

BibTeX
@article{Luo2024,
  author = {Luo, Xuan and Pei, Jian and Xu, Cheng and Zhang, Wenjie and Xu, Jianliang},
  title = {Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2024},
  volume = {2},
  number = {1},
  pages = {1--28},
  doi = {10.1145/3639311}
}
Kostenlos starten →