Computing Shapley Values in Preference Queries

This paper tackles the novel problem of computing Shapley values when multiple data owners collaborate to answer preference queries. Despite extensive existing research on preference queries and Shapley value computation separately, the evaluation of data owners' contributions to cooperatively answering such queries has not been systematically explored. To address this gap, we first establish that, for a linear preference utility function with one data point per owner, the Shapley value can be computed in polynomial time. This finding is applicable to attribute weight spaces that are subsets of a simplex and represent various linear preference utility functions. For scenarios involving multiple data points per owner, we observe that only the locally optimal points from each data owner can make non-zero marginal contributions. Thus, we partition the attribute weight space into a polynomial number of subsets, ensuring that in each subset, only one data point per owner needs to be considered. Experimental results on real Airbnb Listing data and synthetic data sets validate the effectiveness and efficiency of our algorithms, which significantly outperform baseline methods.