  Attribution scores reflect how important the feature values in an input
entity are for the output of a machine learning model. One of the most popular
attribution scores is the SHAP score, which is an instantiation of the general
Shapley value used in coalition game theory. The definition of this score
relies on a probability distribution on the entity population. Since the exact
distribution is generally unknown, it needs to be assigned subjectively or be
estimated from data, which may lead to misleading feature scores. In this
paper, we propose a principled framework for reasoning on SHAP scores under
unknown entity population distributions. In our framework, we consider an
uncertainty region that contains the potential distributions, and the SHAP
score of a feature becomes a function defined over this region. We study the
basic problems of finding maxima and minima of this function, which allows us
to determine tight ranges for the SHAP scores of all features. In particular,
we pinpoint the complexity of these problems, and other related ones, showing
them to be NP-complete. Finally, we present experiments on a real-world
dataset, showing that our framework may contribute to a more robust feature
scoring.
