Fast Joint Shapley Values
Lists
Only you see this
Abstract
The Shapley value has recently drawn the attention of the data management community. Briefly, the Shapley value is a well-known numerical measure for the contribution of a player to a coalitional game. In the direct extension of Shapley axioms, the newly introduced joint Shapley value provides a measure for the average contribution of a set of players. However, due to its exponential nature, it is computationally intensive: for an explanation order of k, the original algorithm takes O(min(3^n, 2^n n^k)) time. In this work, we improve it to O(2^n nk).
BibTeX
@inproceedings{stoian2023fast,
author = {Mihail Stoian},
title = {{Fast Joint Shapley Values}},
booktitle = {SIGMOD Conference Companion},
year = {2023},
doi = {10.1145/3555041.3589393},
}Loading related content...