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

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

Research output: Contribution to journalJournal articlepeer-review

Abstract

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.
Original languageEnglish
Article number56
Number of pages28
JournalProceedings of the ACM on Management of Data
Volume2
Issue number1
DOIs
Publication statusPublished - Feb 2024

User-Defined Keywords

  • data assemblage
  • data market
  • shapley value
  • simple game

Fingerprint

Dive into the research topics of 'Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple Games'. Together they form a unique fingerprint.

Cite this