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 language | English |
---|---|
Article number | 56 |
Number of pages | 28 |
Journal | Proceedings of the ACM on Management of Data |
Volume | 2 |
Issue number | 1 |
DOIs | |
Publication status | Published - Feb 2024 |
User-Defined Keywords
- data assemblage
- data market
- shapley value
- simple game