# The Shapley Value in Machine Learning

Benedek Rozemberczki1 Lauren Watson2 Péter Bayer3 Hao-Tsung Yang2
Oliver Kiss4 Sebastian Nilsson1 &Rik Sarkar2 1Research Data & Analytics,
Research & Development IT, AstraZeneca
2The University of Edinburgh, School of Informatics
3 Toulouse School of Economics & Institute for Advanced Study in Toulouse
4Central European University, Department of Economics and Business
<EMAIL_ADDRESS>
###### Abstract

Over the last few years, the Shapley value, a solution concept from
cooperative game theory, has found numerous applications in machine learning.
In this paper, we first discuss fundamental concepts of cooperative game
theory and axiomatic properties of the Shapley value. Then we give an overview
of the most important applications of the Shapley value in machine learning:
feature selection, explainability, multi-agent reinforcement learning,
ensemble pruning, and data valuation. We examine the most crucial limitations
of the Shapley value and point out directions for future research.111The
survey is supported by a collection of related work under
https://github.com/AstraZeneca/awesome-shapley-value.

##  1 Introduction

Measuring importance and the attribution of various gains is a central problem
in many practical aspects of machine learning such as explainability Lundberg
et al. (2017), feature selection Cohen et al. (2007), data valuation Ghorbani
et al. (2019), ensemble pruning Rozemberczki et al. (2021) and federated
learning Wang et al. (2020); Fan et al. (2021). For example, one might ask:
What is the importance of a certain feature in the decisions of a machine
learning model? How much is an individual data point worth? Which models are
the most valuable in an ensemble? These questions have been addressed in
different domains using specific approaches. Interestingly, there is also a
general and unified approach to these questions as a solution to a
transferable utility (TU) cooperative game. In contrast with other approaches,
solution concepts of TU games are theoretically motivated with axiomatic
properties. The best known solution of this type is the Shapley value Shapley
(1953) characterized by several desiderata that include fairness, symmetry,
and efficiency Chalkiadakis et al. (2011).

In the TU setting, a cooperative game consists of: a player set and a scalar-
valued characteristic function that defines the value of coalitions (subsets
of players). In such a game, the Shapley value offers a rigorous and intuitive
way to distribute the collective value (e.g. the revenue, profit, or cost) of
the team across individuals. To apply this idea to machine learning, we need
to define two components: the player set and the characteristic function. In a
machine learning setting players may be represented by a set of input
features, reinforcement learning agents, data points, models in an ensemble,
or data silos. The characteristic function can then describe the goodness of
fit for a model, reward in reinforcement learning, financial gain on instance
level predictions, or out-of-sample model performance. We provide an example
about model valuation in an ensemble Rozemberczki et al. (2021) in Figure 1.

Figure 1: The Shapley value can be used to solve cooperative games. An
ensemble game is a machine learning application for it – models in an ensemble
are players (red, blue, and green robots) and the financial gain of the
predictions is the payoff (coins) for each possible coalition (rectangles).
The Shapley value can distribute the gain of the grand coalition (right bottom
corner) among models.

Present work. We introduce basic definitions of cooperative games and present
the Shapley value, a solution concept that can allocate gains in these games
to individual players. We discuss its properties and emphasize why these are
important in machine learning. We overview applications of the Shapley value
in machine learning: feature selection, data valuation, explainability,
reinforcement learning, and model valuation. Finally, we discuss the
limitations of the Shapley value and point out future directions.

##  2 Background

This section introduces cooperative games and the Shapley value followed by
its properties. We also provide an illustrative running example for our
definitions.

###  2.1 Cooperative games and the Shapley value

######  Definition 1.

Player set and coalitions. Let $\mathcal{N}=\\{1,\dots,n\\}$ be the finite set
of players. We call each non-empty subset $\mathcal{S}\subseteq\mathcal{N}$ a
coalition and $\mathcal{N}$ itself the grand coalition.

######  Definition 2.

Cooperative game. A TU game is defined by the pair $(\mathcal{N},v)$ where
$v:2^{\mathcal{N}}\rightarrow\mathbb{R}$ is a mapping called the
characteristic function or the coalition function of the game assigning a real
number to each coalition and satisfying $v(\emptyset)=0$.

######  Example 1.

Let us consider a 3-player cooperative game where
$\mathcal{N}=\left\\{1,2,3\right\\}$. The characteristic function defines the
payoff for each coalition. Let these payoffs be given as:

$\displaystyle v(\emptyset)$ $\displaystyle=0;$
$\displaystyle\,\,\,\,v(\left\\{1\right\\})$ $\displaystyle=7;$
$\displaystyle\,\,\,\,v(\left\\{2\right\\})$ $\displaystyle=11;$
$\displaystyle\,\,\,\,v(\left\\{3\right\\})$ $\displaystyle=14;$
$\displaystyle v(\left\\{1,2\right\\})$ $\displaystyle=18;$
$\displaystyle\,\,\,\,v(\left\\{1,3\right\\})$ $\displaystyle=21;$
$\displaystyle\,\,\,\,v(\left\\{2,3\right\\})$ $\displaystyle=23;$
$\displaystyle\,\,\,\,v(\left\\{1,2,3\right\\})$ $\displaystyle=25.$

######  Definition 3.

Set of feasible payoff vectors. Let us define
$\mathcal{Z}(\mathcal{N},v)=\\{\mathbf{z}\in\mathbb{R}^{\mathcal{N}}\mid\sum_{i\in\mathcal{N}}\textbf{z}_{i}\leq
v(\mathcal{N})\\}$ the set of feasible payoff vectors for the cooperative game
$(\mathcal{N},v)$.

######  Definition 4.

Solution concept and solution vector. Solution concept $\Phi$ is a mapping
associating a subset $\Phi(\mathcal{N},v)\subseteq\mathcal{Z}(\mathcal{N},v)$
to every TU game $(\mathcal{N},v)$. A solution vector
$\phi(\mathcal{N},v)\in\mathbb{R}^{\mathcal{N}}$ to the cooperative game
$(\mathcal{N},v)$ satisfies solution concept $\Phi$ if
$\phi(\mathcal{N},v)\in\Phi(\mathcal{N},v)$. Solution concept $\Phi$ is
single-valued if for every $(\mathcal{N},v)$ the set $\Phi(\mathcal{N},v)$ is
a singleton.

A solution concept defines an allocation principle through which rewards can
be given to the individual players. The sum of these rewards cannot exceed the
value of the grand coalition $v(\mathcal{N})$. Solution vectors are specific
allocations satisfying the principles of the solution concept.

######  Definition 5.

Permutations of the player set. Let $\Pi(\mathcal{N})$ be the set of all
permutations defined on $\mathcal{N}$, a specific permutation is written as
$\pi\in\Pi(\mathcal{N})$ and $\pi(i)$ is the position of player
$i\in\mathcal{N}$ in permutation $\pi$.

######  Definition 6.

Predecessor set. Let the set of predecessors of player $i\in\mathcal{N}$ in
permutation $\pi$ be the coalition:

$\mathcal{P}^{\pi}_{i}=\left\\{j\in\mathcal{N}\mid\pi(j)<\pi(i)\right\\}.$

Let us imagine that the permutation of the players in our illustrative game is
$\pi=(3,2,1)$. Under this permutation the predecessor set of the $1^{st}$
player is $\mathcal{P}^{\pi}_{1}=\left\\{3,2\right\\}$, that of the $2^{nd}$
player is $\mathcal{P}^{\pi}_{2}=\left\\{3\right\\}$ and
$\mathcal{P}^{\pi}_{3}=\emptyset$.

######  Definition 7.

Shapley value. The Shapley value Shapley (1953) is a single-valued solution
concept for cooperative games. The $i^{th}$ component of the single solution
vector satisfying this solution concept for any cooperative game
$(\mathcal{N},v)$ is given by Equation 1.

$\displaystyle\phi^{Sh}_{i}=\frac{1}{|\Pi(\mathcal{N})|}\sum\limits_{\pi\in\Pi(\mathcal{N})}\underbrace{[v(\mathcal{P}^{\pi}_{i}\cup\left\\{i\right\\})-v(\mathcal{P}^{\pi}_{i})]}_{\begin{subarray}{c}\textbf{Player
$i$'s marginal contribution }\\\ \textbf{in permutation $\pi$}\end{subarray}}$
(1)

The Shapley value of a player is the average marginal contribution of the
player to the value of the predecessor set over every possible permutation of
the player set. Table 1 contains manual calculations of the players’ marginal
contributions to each permutation and their Shapley values in Example 1.

Table 1: The permutations of the player set, marginal contributions of the players in each permutation and the Shapley values. | Marginal Contribution
---|---
Permutation | Player 1 | Player 2 | Player 3
(1, 2, 3) | 7 | 11 | 7
(1, 3, 2) | 7 | 4 | 14
(2, 1, 3) | 7 | 11 | 7
(2, 3, 1) | 2 | 11 | 12
(3, 1, 2) | 7 | 4 | 14
(3, 2, 1) | 2 | 9 | 14
Shapley value | $32/6$ | $50/6$ | $68/6$

###  2.2 Properties of the Shapley value

We define the solution concept properties that characterize the Shapley value
and emphasize their relevance and meaning in a feature selection game. In this
game input features are players, coalitions are subsets of features and the
payoff is a scalar valued goodness of fit for a machine learning model using
these input features.

######  Definition 8.

Null player. Player $i$ is called a null player if
$v(\mathcal{S}\cup\\{i\\})=v(\mathcal{S})\,\,\forall\mathcal{S}\subseteq\mathcal{N}\setminus\\{i\\}$.
A solution concept $\Phi$ satisfies the null player property if for every game
$(\mathcal{N},v)$, every $\phi(\mathcal{N},v)\in\Phi(\mathcal{N},v)$, and
every null player $i$ it holds that $\phi(\mathcal{N},v)_{i}=0$.

In the feature selection game a solution concept with the null player property
assigns zero value to those features that never increase the goodness of fit
when added to the feature set.

######  Definition 9.

Efficiency. A solution concept $\Phi$ is efficient or Pareto optimal if for
every game $(\mathcal{N},v)$ and every solution vector
$\phi(\mathcal{N},v)\in\Phi(\mathcal{N},v)$ it holds that
$\sum\limits_{i\in\mathcal{N}}\phi(\mathcal{N},v)_{i}=v(\mathcal{N})$.

Consider the goodness of fit of the model trained by using the whole set of
input features. The importance measures assigned to individual features by an
efficient solution concept sum to this goodness of fit. This allows for
quantifying the contribution of individual features to the whole performance
of the trained model.

######  Definition 10.

Symmetry. Two players $i$ and $j$ are symmetric if
$v(\mathcal{S}\cup\\{i\\})=v(\mathcal{S}\cup\\{j\\})\,\,\forall\mathcal{S}\subseteq\mathcal{N}\setminus\\{i,j\\}$.
A solution concept $\Phi$ satisfies symmetry if for all $(\mathcal{N},v)$ for
all $\phi(\mathcal{N},v)\in\Phi(\mathcal{N},v)$ and all symmetric players
$i,j\in\mathcal{N}$ it holds that
$\phi(\mathcal{N},v)_{i}=\phi(\mathcal{N},v)_{j}$.

The symmetry property implies that if two features have the same marginal
contribution to the goodness of fit when added to any possible coalition then
the importance of the two features is the same. This property is essentially a
fair treatment of the input features and results in identical features
receiving the same importance score.

######  Definition 11.

Linearity. A single-valued solution concept $\Phi$ satisfies linearity if for
any two games $(\mathcal{N},v)$ and $(\mathcal{N},w)$, and for the solution
vector of the TU game given by $(\mathcal{N},v+w)$ it holds that

$\phi(\mathcal{N},v+w)_{i}=\phi(\mathcal{N},v)_{i}+\phi(\mathcal{N},w)_{i},\,\,\,\,\forall
i\in\mathcal{N}.$

Let us imagine a binary classifier and two sets of data points – on both of
these datasets, we can define feature selection games with binary cross
entropy-based payoffs. The Shapley values of input features in the feature
selection game calculated on the pooled dataset would be the same as adding
together the Shapley values calculated from the two datasets separately.

These four properties together characterize the Shapley value.

######  Theorem 1 (Shapley, 1953).

A single-valued solution concept satisfies the null player, efficiency,
symmetry, and linearity properties if and only if it is the Shapley value.

##  3 Approximations of the Shapley Value

Shapley value computation requires an exponential number of characteristic
function evaluations, resulting in exponential time complexity. This is
prohibitive in a machine learning context when each evaluation can correspond
to training a machine learning model. For this reason, machine learning
applications use a variety of Shapley value approximation methods we discuss
in this section. In the following discussion $\widehat{\phi}^{Sh}_{i}$ denotes
an approximated Shapley value for player $i\in\mathcal{N}.$

###  3.1 Monte Carlo Permutation Sampling

Monte Carlo permutation sampling for the general class of cooperative games
was first proposed by Castro et al. (2009) to approximate the Shapley value in
linear time.

Data: $(\mathcal{N},v)$ \- Cooperative TU game.

$k$ \- Number of sampled permutations.

Result: $\widehat{\phi}^{Sh}_{i}$ \- Approximated Shapley value $\forall
i\in\mathcal{N}$.

1

2$\widehat{\phi}^{Sh}_{i}\leftarrow 0,\,\,\,\forall i\in\mathcal{N}$

3

4for  _$(1,\dots,k)$_ do

5 $\pi\leftarrow\text{Uniform Sample}(\Pi(\mathcal{N}))$

6

7 for  _$i\in\mathcal{N}$_ do

8

9
$\mathcal{P}^{\pi}_{i}\leftarrow\left\\{j\in\mathcal{N}\mid\pi(j)<\pi(i)\right\\}$

10
$\widehat{\phi}^{Sh}_{i}\leftarrow\widehat{\phi}^{Sh}_{i}+\frac{v(\mathcal{P}^{\pi}_{i}\cup\left\\{i\right\\})-v(\mathcal{P}^{\pi}_{i})}{k}$

11

12 end for

13

14 end for

Algorithm 1 Monte Carlo permutation sampling approximation of the Shapley
value.

As shown in Algorithm 1, the method performs a sampling-based approximation.
At each iteration, a random element from the permutations of the player set is
drawn. The marginal contributions of the players in the sampled permutation
are scaled down by the number of samples (which is equivalent to taking an
average) and added to the approximated Shapley values from the previous
iteration. Castro et al. (2009) provide asymptotic error bounds for this
approximation algorithm via the central limit theorem when the variance of the
marginal contributions is known. Maleki et al. (2013) extended the analysis of
this sampling approach by providing error bounds when either the variance or
the range of the marginal contributions is known via Chebyshev’s and
Hoeffding’s inequalities. Their bounds hold for a finite number of samples in
contrast to the previous asymptotic bounds.

####  3.1.1 Stratified Sampling for Variance Reduction

In addition to extending the analysis of Monte Carlo estimation, Maleki et al.
(2013) demonstrate how to improve the Shapley Value approximation when
sampling can be stratified by dividing the permutations of the player set into
homogeneous, non-overlapping sub-populations. In particular, they show that if
the set of permutations can be grouped into strata with similar marginal gains
for players, then the approximation will be more precise. Following this,
Castro et al. (2017) explored stratified sampling approaches using strata
defined by the set of all marginal contributions when the player is in a
specific position within the coalition. Burgess et al. (2021) propose
stratified sampling approaches designed to minimize the uncertainty of the
estimate via a stratified empirical Bernstein bound.

####  3.1.2 Other Variance Reduction Techniques

Following the stratified approaches of Maleki et al. (2013); Castro et al.
(2017); Burgess et al. (2021), Illés et al. (2019) propose an alternative
variance reduction technique for the sample mean. Instead of generating a
random sequence of samples, they instead generate a sequence of ergodic but
not independent samples, taking advantage of negative correlation to reduce
the sample variance. Mitchell et al. (2021) show that other Monte Carlo
variance reduction techniques can also be applied to this problem, such as
antithetic sampling Lomeli et al. (2019); Rubinstein et al. (2016). A simple
form of antithetic sampling uses both a randomly sampled permutation and its
reverse. Finally, Touati et al. (2021) introduce a Bayesian Monte Carlo
approach to Shapley value calculation, showing that Shapley value estimation
can be improved by using Bayesian methods to approximate the Shapley value.

###  3.2 Multilinear Extension

By inducing a probability distribution over the subsets $\mathcal{S}$ where
$\mathcal{E}_{i}$ is a random subset that does not include player $i$ and each
player is included in a subset with probability $q$, Owen (1972) demonstrated
that the sum over subsets in Definition 7 can also be represented as an
integral $\int_{0}^{1}e_{i}(q)dq$ where
$e_{i}(q)=\mathbb{E}[v(\mathcal{E}_{i}\cup i)-v(\mathcal{E}_{i})]$. Sampling
over $q$ therefore provides an approximation method – the multilinear
extension. For example, Mitchell et al. (2021) uses the trapezoid rule to
sample $q$ at fixed intervals while Okhrati et al. (2021) proposes
incorporating antithetic sampling as a variance reduction technique.

###  3.3 Linear Regression Approximation

In their seminal work Lundberg et al. (2017) apply Shapley values to feature
importance and explainability (SHAP values), demonstrating that Shapley values
for TU games can be approximated by solving a weighted least squares
optimization problem. Their main insight is the computation of Shapley values
by approximately solving the following optimization problem:

$\displaystyle w_{\mathcal{S}}$
$\displaystyle=\frac{|\mathcal{N}|-1}{{|\mathcal{N}|\choose|\mathcal{S}|}|\mathcal{S}|(|\mathcal{N}|-|\mathcal{S}|)}$
(2)
$\displaystyle\underset{\widehat{\phi}^{Sh}_{0},...,\widehat{\phi}^{Sh}_{n}}{min}\sum_{\mathcal{S}\subseteq\mathcal{N}}$
$\displaystyle
w_{\mathcal{S}}\left(\widehat{\phi}^{Sh}_{0}+\sum_{i\in\mathcal{S}}\widehat{\phi}^{Sh}_{i}-v(\mathcal{S})\right)$
(3) $\displaystyle s.t.\hskip 5.69054pt\widehat{\phi}^{Sh}_{0}=$
$\displaystyle v(\emptyset),\hskip
14.22636pt\widehat{\phi}^{Sh}_{0}+\sum_{i\in\mathcal{N}}\widehat{\phi}^{Sh}_{i}=v(\mathcal{N}).$
(4)

The definition of weights in Equation (2) and the objective function in
Equation (3) implies the evaluation of $v(\cdot)$ for $2^{n}$ coalitions. To
address this Lundberg et al. (2017) propose approximating this problem
subsampling the coalitions. Note that $w_{\mathcal{S}}$ is higher when
coalitions are large or small. Covert et al. (2021) extend the study of this
method, finding that while SHAP is a consistent estimator, it is not an
unbiased estimator. By proposing and analyzing a variation of this method that
is unbiased, they conclude that while there is a small bias incurred by SHAP
it has a significantly lower variance than the corresponding unbiased
estimator. Covert et al. (2021) then propose a variance reduction method for
SHAP, improving convergence speed by a magnitude through sampling coalitions
in pairs with each selected alongside its complement.

##  4 Machine Learning and the Shapley Value

Table 2: An application area, payoff definition, Shapley value approximation technique, and computation time (the player set is noted by $\mathcal{N}$) based comparison of research works. Specific applications of the Shapley value are grouped together and ordered chronologically. Application | Reference | Payoff | Approximation | Time
---|---|---|---|---
Feature Selection | Cohen et al. (2007) | Validation loss | Exact | $\mathcal{O}(|\mathcal{N}|!)$
Sun et al. (2012) | Mutual information | Exact | $O(|\mathcal{N}|!)$
Williamson et al. (2020) | Validation loss | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Tripathi et al. (2020) | Training loss | Monte Carlo sampling | $O(|\mathcal{N}|)$
Patel et al. (2021) | Validation loss | Monte Carlo sampling | $O(|\mathcal{N}|)$
Guha et al. (2021) | Validation loss | Exact | $O(|\mathcal{N}|!)$
Data Valuation | Jia et al. (2019) | Validation loss | Restricted Monte Carlo sampling | $\mathcal{O}(\sqrt{|\mathcal{N}|}\log|\mathcal{N}|^{2})$
Ghorbani et al. (2019) | Validation loss | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Shim et al. (2021) | Validation loss | Exact | $\mathcal{O}(|\mathcal{N}|\log|\mathcal{N}|)$
Deutch et al. (2021) | Validation loss | Restricted Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Kwon et al. (2021a) | Validation loss | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Kwon et al. (2021b) | Validation loss | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Federated Learning | Liu et al. (2021) | Validation loss | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Universal Explainability | Lundberg et al. (2017) | Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Sundararajan et al. (2020a) | Interaction attribution | Integrated gradients | $\mathcal{O}(|\mathcal{N}|^{2})$
Sundararajan et al. (2020b) | Interaction attribution | Integrated gradients | $\mathcal{O}(|\mathcal{N}|^{2})$
Frye et al. (2020a) | Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Frye et al. (2020b) | Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Yuan et al. (2021) | Attribution | Monte Carlo sampling | $O(|\mathcal{N}|)$
Covert et al. (2021) | Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Explainability of Deep Learning | Chen et al. (2018) | Attribution | Restricted Monte Carlo sampling |  $\mathcal{O}(2^{|\mathcal{N}|})$ or $\mathcal{O}(|\mathcal{N}|)$
Ancona et al. (2019) | Neuron attribution | Voting game | $\mathcal{O}(|\mathcal{N}|^{2})$
Ghorbani et al. (2020b) | Neuron attribution | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Zhang et al. (2021) | Interaction Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Explainability of Graphical Models | Liu et al. (2020) | Attribution | Exact | $\mathcal{O}(|\mathcal{N}|!)$
Heskes et al. (2020) | Causal Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Wang et al. (2021b) | Causal Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Singal et al. (2021) | Causal Attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Explainability in Graph Machine Learning | Yuan et al. (2021) | Edge level attribution | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Duval et al. (2021) | Edge level attribution | Linear regression | $\mathcal{O}(|\mathcal{N}|)$
Multi-agent Reinforcement Learning | Wang et al. (2021a) | Global reward | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Li et al. (2021) | Global reward | Monte Carlo sampling | $\mathcal{O}(|\mathcal{N}|)$
Model Valuation in Ensembles | Rozemberczki et al. (2021) | Predictive performance | Voting game | $\mathcal{O}(|\mathcal{N}|^{2})$

Our discussion about applications of the Shapley value in the machine learning
domain focuses on the formulation of the cooperative games, definition of the
player set and payoffs, Shapley value approximation technique used, and the
time complexity of the approximation. We summarized the most important
application areas with this information in Table 2 and grouped the relevant
works by the problem solved.

###  4.1 Feature Selection

The feature selection game treats input features of a machine learning model
as players and model performance as the payoff Guyon et al. (2003); Fryer et
al. (2021). The Shapley values of features quantify how much individual
features contribute to the model’s performance on a set of data points.

######  Definition 12.

Feature selection game. Let the player set be
$\mathcal{N}=\left\\{1,\dots,n\right\\}$, for
$\mathcal{S}\subseteq\mathcal{N}$ the train and test feature vector sets are
$\mathcal{X}_{\mathcal{S}}^{\text{Train}}=\left\\{\textbf{x}^{\text{Train}}_{i}|i\in\mathcal{S}\right\\}$
and
$\mathcal{X}_{\mathcal{S}}^{\text{Test}}=\left\\{\textbf{x}^{\text{Test}}_{i}|i\in\mathcal{S}\right\\}$.
Let $f_{\mathcal{S}}(\cdot)$ be a machine learning model trained using
$\mathcal{X}^{\text{Train}}_{\mathcal{S}}$ as input, then the payoff is
$v(\mathcal{S})=g(\textbf{y},\widehat{\textbf{y}}_{\mathcal{S}})$ where
$g(\cdot)$ is a goodness of fit function, y and
$\widehat{\textbf{y}}_{\mathcal{S}}=f_{\mathcal{S}}(\mathcal{X}_{\mathcal{S}}^{\text{Test}})$
are the ground truth and predicted targets.

Shapley values, and close relatives such as the Banzhaf index Banzhaf III
(1964), have been studied as a measure of feature importance in various
contexts Cohen et al. (2007); Sun et al. (2012); Williamson et al. (2020);
Tripathi et al. (2020). Using these importance estimates, features can be
ranked and selected or removed accordingly. This approach has been applied to
various tasks such as vocabulary selection in natural language processing
Patel et al. (2021) and feature selection in human action recognition Guha et
al. (2021).

###  4.2 Data valuation

In the data valuation game training set data points are players and the payoff
is defined by the goodness of fit achieved by a model on the test data.
Computing the Shapley value of players in a data valuation game measures how
much data points contribute to the performance of the model.

######  Definition 13.

Data valuation game. Let the player set be
$\mathcal{N}=\\{(\textbf{x}_{i},y_{i})\ |\ 1\leq i\leq n\\}$ where
$\textbf{x}_{i}$ is the input feature vector and $y_{i}$ is the target. Given
the coalition $\mathcal{S}\subseteq\mathcal{N}$ let $f_{\mathcal{S}}(\cdot)$
be a machine learning model trained on $\mathcal{S}$. Let us denote the test
set feature vectors and targets as $\mathcal{X}$ and $\mathcal{Y}$, given
$f_{\mathcal{S}}(\cdot)$ the set of predicted labels is defined as
$\widehat{\mathcal{Y}}=\left\\{f_{\mathcal{S}}(\textbf{x})|\textbf{x}\in\mathcal{X}\right\\}$.
Then the payoff of a model trained on the data points
$\mathcal{S}\subseteq\mathcal{N}$ is
$v(\mathcal{S})=g(\mathcal{Y},\widehat{\mathcal{Y}})$ where $g(\cdot)$ is a
goodness of fit metric.

The Shapley value is not the only method for data valuation – earlier works
used function utilization Koh et al. (2017); Sharchilev et al. (2018), leave-
one-out testing Cook (1977) and core sets Dasgupta et al. (2009). However,
these methods fall short when there are fairness requirements from the data
valuation technique Jia et al. (2019); Ghorbani et al. (2019); Kwon et al.
(2021b). Ghorbani proposed a framework of utilizing Shapley value in a data-
sharing system Ghorbani et al. (2019); Jia et al. (2019) advanced this work
with more efficient algorithms to approximate the Shapley value for data
valuation. The distributional Shapley value has been discussed by Ghorbani et
al. (2020a) who argued that keeping privacy is hard during Shapley value
computation. Their method calculates the Shapley value over a distribution
which solves problems such as lack of privacy. The computation time of this
can be reduced as Kwon et al. (2021a) point out with approximation methods
optimized for specific machine learning models.

###  4.3 Federated learning

A federated learning scenario can be seen as a cooperative game by modeling
the data owners as players who cooperate to train a high-quality machine
learning model Liu et al. (2021).

######  Definition 14.

Federated learning game. In this game players are a set of labeled dataset
owners $\mathcal{N}=\left\\{(\mathcal{X}_{i},\mathcal{Y}_{i})|1\leq i\leq
n\right\\}$ where $\mathcal{X}_{i}$ and $\mathcal{Y}_{i}$ are the feature and
label sets owned by the $i^{th}$ silo. Let $(\mathcal{X},\mathcal{Y})$ be a
labeled test set, $\mathcal{S}\subseteq\mathcal{N}$ a coalition of data silos,
$f_{\mathcal{S}}(\cdot)$ a machine learning model trained on $\mathcal{S}$,
and $\widehat{\mathcal{Y}}_{\mathcal{S}}$ the labels predicted by
$f_{\mathcal{S}}(\cdot)$ on $\mathcal{X}$. The payoff of
$\mathcal{S}\subseteq\mathcal{N}$ is
$v(\mathcal{S})=g(\mathcal{Y},\widehat{\mathcal{Y}}_{\mathcal{S}})$ where
$g(\cdot)$ is a goodness of fit metric.

The system described by Liu et al. (2021) uses Monte Carlo sampling to
approximate the Shapley value of data coming from the data silos in linear
time. Given the potentially overlapping nature of the datasets, the use of
configuration games could be an interesting future direction Albizuri et al.
(2006).

###  4.4 Explainable machine learning

In explainable machine learning the Shapley value is used to measure the
contributions of input features to the output of a machine learning model at
the instance level. Given a specific data point, the goal is to decompose the
model prediction and assign Shapley values to individual features of the
instance. There are universal solutions to this challenge that are model
agnostic and designs customized for deep learning Chen et al. (2018); Ancona
et al. (2019), classification trees Lundberg et al. (2017), and graphical
models Liu et al. (2020); Singal et al. (2021).

####  4.4.1 Universal explainability

A cooperative game for universal explainability is completely model agnostic;
the only requirement is that a scalar-valued output can be generated by the
model such as the probability of a class label being assigned to an instance.

######  Definition 15.

Universal explainability game. Let us denote the machine learning model of
interest with $f(\cdot)$ and let the player set be the feature values of a
single data instance: $\mathcal{N}=\left\\{x_{i}|1\leq i\leq n\right\\}$. The
payoff of a coalition $\mathcal{S}\subseteq\mathcal{N}$ in this game is the
scalar valued prediction
$v(\mathcal{S})=\widehat{y}_{\mathcal{S}}=f(\mathcal{S})$ calculated from the
subset of feature values.

Calculating the Shapley value in a game like this offers a complete
decomposition of the prediction because the efficiency axiom holds. The
Shapley values of feature values are explanatory attributions to the input
features and missing input feature values are imputed with a reference value
such as the mean computed from multiple instances Lundberg et al. (2017);
Covert et al. (2021). The pioneering Shapley value-based universal explanation
method SHAP Lundberg et al. (2017) proposes a linear time approximation of the
Shapley values which we discussed in Section 3. This approximation has
shortcomings and implicit assumptions about the features which are addressed
by newer Shapley value-based explanation techniques. For example, in Frye et
al. (2020a) the input features are not necessarily independent, Frye et al.
(2020b) restricts the permutations based on known causal relationships, and in
Covert et al. (2021) the proposed technique improves the convergence
guarantees of the approximation. Several methods generalize SHAP beyond
feature values to give attributions to first-order feature interactions
Sundararajan et al. (2020b, a). However, this requires that the player set is
redefined to include feature interaction values.

####  4.4.2 Deep learning

In neuron explainability games neurons are players and attributions to the
neurons are payoffs. The primary goal of Shapley value-based explanations in
deep learning is to solve these games and compute attributions to individual
neurons and filters Ghorbani et al. (2020b); Ancona et al. (2019).

######  Definition 16.

Neuron explainability game. Let us consider $f_{\textsc{IN}}(\cdot)$ the
encoder layer of a neural network and x the input feature vector to the
encoder. In the neuron explainability game the player set is
$\mathcal{N}=f_{\textsc{IN}}(\textbf{x})=\left\\{h_{1},\dots,h_{n}\right\\}$
\- each player corresponds to the output of a neuron in the final layer of the
encoder. The payoff of coalition $\mathcal{S}\subseteq\mathcal{N}$ is defined
as the predicted output
$v(\mathcal{S})=\widehat{y}_{\mathcal{S}}=f_{\textsc{OUT}}(\mathcal{S})$ where
$f_{\textsc{OUT}}(\cdot)$ is the head layer of the neural network.

In practical terms, the payoffs are the output of the neural network obtained
by masking out certain neurons. Using the Shapley values obtained in these
games the value of individual neurons can be quantified. At the same time,
some deep learning specific Shapley value-based explanation techniques have
designs and goals that are aligned with the games described in universal
explainability. These methods exploit the structure of the input data Chen et
al. (2018) or the nature of feature interactions Zhang et al. (2021) to
provide efficient computations of attributions.

####  4.4.3 Graphical models

Compared to universal explanations the graphical model-specific techniques
restrict the admissible set of player set permutations considered in the
attribution process. These restrictions are defined based on known causal
relations and permutations are generated by various search strategies on the
graph describing the probabilistic model Heskes et al. (2020); Liu et al.
(2020); Singal et al. (2021). Methods are differentiated from each other by
how restrictions are defined and how permutations are restricted.

####  4.4.4 Relational machine learning

In the relational machine learning domain the Shapley value is used to create
edge importance attributions of instance-level explanations Duval et al.
(2021); Yuan et al. (2021). Essentially the Shapley value in these games
measures the average marginal change in the outcome variable as one adds a
specific edge to the edge set in all of the possible edges set permutations.
It is worth noting that the edge explanation and attribution techniques
proposed could be generalized to provide node attributions.

######  Definition 17.

Relational explainability game. Let us define a graph
$\mathcal{G}=(\mathcal{V},\mathcal{N})$ where $\mathcal{V}$ and $\mathcal{N}$
are the vertex and edge sets. Given the relational machine learning model
$f(\cdot)$, node feature matrix X, node $u\in\mathcal{V}$, the payoff of
coalition $\mathcal{S}\subseteq\mathcal{V}$ in the graph machine learning
explanation game is defined as the node level prediction
$v(\mathcal{S})=\widehat{y}_{\mathcal{S},u}=f(\textbf{X},\mathcal{V},\mathcal{S},u)$.

###  4.5 Multi-agent reinforcement learning

Global reward multi-agent reinforcement learning problems can be modeled as TU
games Wang et al. (2021a); Li et al. (2021) by defining the player set as the
set of agents and the payoff of coalitions as a global reward. The Shapley
value allows an axiomatic decomposition of the global reward achieved by the
agents in these games and the fair attribution of credit assignments to each
of the participating agents.

###  4.6 Model valuation in ensembles

The Shapley value can be used to assess the contributions of machine learning
models to a composite model in ensemble games. In these games, players are
models in an ensemble and payoffs are decided by whether prediction mad by the
model are correct.

######  Definition 18.

Ensemble game. Let us consider a single target - feature instance denoted by
$(y,\textbf{x})$. The player set in ensemble games is defined by a set of
machine learning models $\mathcal{N}=\left\\{f_{i}(\cdot)|1\leq i\leq
n\right\\}$ that operate on the feature set. The predicted target output by
the ensemble $\mathcal{S}\subseteq\mathcal{N}$ is defined as
$\widehat{y}_{\mathcal{S}}=\tilde{f}(\mathcal{S},\textbf{x})$ where
$\tilde{f}(\cdot)$ is a prediction aggregation function. The payoff of
$\mathcal{S}$ is $v(\mathcal{S})=g(y,\widehat{y}_{\mathcal{S}})$ where
$g(\cdot)$ is a goodness of fit metric.

The ensemble games described by Rozemberczki et al. (2021) are formulated as a
special subclass of voting games. This allows the use of precise game-specific
approximation Fatima et al. (2008) techniques and because of this the Shapley
value estimates are obtained in quadratic time and have a tight approximation
error. The games themselves are model agnostic concerning the player set –
ensembles can be formed by heterogeneous types of machine learning models that
operate on the same inputs.

##  5 Discussion

The Shapley value has a wide-reaching impact in machine learning, but it has
limitations and certain extensions of the Shapley value could have important
applications in machine learning.

###  5.1 Limitations

####  5.1.1 Computation time

Computing the Shapley value for each player naively in a TU game takes
factorial time. In some machine learning application areas such as multi-agent
reinforcement learning and federated learning where the number of players is
small, this is not an issue. However, in large scale data valuation Kwon et
al. (2021a, b), explainability Lundberg et al. (2017), and feature selection
Patel et al. (2021) settings the exact calculation of the Shapley value is not
tractable. In Sections 3 and 4 we discussed approximation techniques proposed
to make Shapley value computation possible. In some cases, asymptotic
properties of these Shapley value approximation techniques are not well
understood – see for example Chen et al. (2018).

####  5.1.2 Interpretability

By definition, the Shapley values are the average marginal contributions of
players to the payoff of the grand coalition computed from all permutations
Shapley (1953). Theoretical interpretations like this one are not intuitive
and not useful for non-game theory experts. This means that translating the
meaning of Shapley values obtained in many application areas to actions is
troublesome Kumar et al. (2020). For example in a data valuation scenario: is
a data point with a twice as large Shapley value as another one twice as
valuable? Answering a question like this requires a definition of the
cooperative game that is interpretable.

####  5.1.3 Axioms do not hold under approximations

As we discussed most applications of the Shapley value in machine learning use
approximations. The fact that under these approximations the desired axiomatic
properties of the Shapley value do not hold is often overlooked Sundararajan
et al. (2020b). This is problematic because most works argue for the use of
Shapley value based on these axioms. In our view, this is the greatest
unresolved issue in the applications of the Shapley value.

###  5.2 Future Research Directions

####  5.2.1 Hierarchy of the coalition structure

The Shapley value has a constrained version called Owen value Owen (1977) in
which only permutations satisfying conditions defined by a coalition structure
\- a partition of the player set - are considered. The calculation of the Owen
value is identical to that of the Shapley value, with the exception that only
those permutations are taken into account where the players in any of the
subsets of the coalition structure follow each other. In several real-world
data and feature valuation scenarios even more complex hierarchies of the
coalition, the structure could be useful. Having a nested hierarchy imposes
restrictions on the admissible permutations of the players and changes player
valuation. Games with such nested hierarchies are called level structure games
in game theory. Winter (1989) presents the Winter value a solution concept to
level structure games - such games are yet to receive attention in the machine
learning literature.

####  5.2.2 Overlapping coalition structure

Traditionally, it is assumed that players in a coalition structure are
allocated in disjoint partitions of the grand coalition. Allowing players to
belong to overlapping coalitions in configuration games Albizuri et al. (2006)
could have several applications in machine learning. For example in a data-
sharing - feature selection scenario multiple data owners might have access to
the same features - a feature can belong to overlapping coalitions.

####  5.2.3 Solution concepts beyond the Shapley value

The Shapley value is a specific solution concept of cooperative game theory
with intuitive axiomatic properties (Section 2). At the same time it has
limitations with respect to computation constraints and interpretability
(Sections 3 and 5). Cooperative game theory offers other solution concepts
such as the core, nucleolus, stable set, and kernel with their own
axiomatizations. For example, the core has been used for model explainability
and feature selection Yan et al. (2021). Research into the potential
applications of these solution concepts is lacking.

##  6 Conclusion

In this survey we discussed the Shapley value, examined its axiomatic
characterizations and the most frequently used Shapley value approximation
approaches. We defined and reviewed its uses in machine learning, highlighted
issues with the Shapley value and potential new application and research areas
in machine learning.

## Acknowledgements

This research was supported by REPHRAIN: The National Research Centre on
Privacy, Harm Reduction and Adversarial Influence Online (UKRI grant:
EP/V011189/1). The authors would like to thank Anton Tsitsulin for feedback
throughout the preparation of this manuscript.

## References

  * Albizuri et al. [2006] Josune Albizuri, Jesús Aurrecoechea, and José Manuel Zarzuelo.  Configuration Values: Extensions of the Coalitional Owen Value.  Games and Economic Behavior, 57(1):1–17, 2006.
  * Ancona et al. [2019] Marco Ancona, Cengiz Oztireli, and Markus Gross.  Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation.  In International Conference on Machine Learning, pages 272–281, 2019.
  * Banzhaf III [1964] John F Banzhaf III.  Weighted Voting Doesn’t Work: A Mathematical Analysis.  Rutgers L. Rev., 19:317, 1964.
  * Burgess et al. [2021] Mark A Burgess and Archie C Chapman.  Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling.  International Joint Conferences on Artificial Intelligence Organization, 2021.
  * Castro et al. [2009] Javier Castro, Daniel Gómez, and Juan Tejada.  Polynomial Calculation of the Shapley Value Based on Sampling.  Computers & Operations Research, 36(5):1726–1730, 2009.
  * Castro et al. [2017] Javier Castro, Daniel Gómez, Elisenda Molina, and Juan Tejada.  Improving Polynomial Estimation of the Shapley Value by Stratified Random Sampling with Optimum Allocation.  Computers & Operations Research, 82:180–188, 2017.
  * Chalkiadakis et al. [2011] Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge.  Computational Aspects of Cooperative Game Theory.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 5(6):1–168, 2011.
  * Chen et al. [2018] Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan.  L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data.  In International Conference on Learning Representations, 2018\.
  * Cohen et al. [2007] Shay Cohen, Gideon Dror, and Eytan Ruppin.  Feature Selection via Coalitional Game Theory.  Neural Computation, 19(7):1939–1961, 2007.
  * Cook [1977] R Dennis Cook.  Detection of influential observation in linear regression.  Technometrics, 19(1):15–18, 1977.
  * Covert et al. [2021] Ian Covert and Su-In Lee.  Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression.  In International Conference on Artificial Intelligence and Statistics, pages 3457–3465, 2021.
  * Dasgupta et al. [2009] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney.  Sampling algorithms and coresets for $\backslash$ell_p regression.  SIAM Journal on Computing, 38(5):2060–2078, 2009.
  * Deutch et al. [2021] Daniel Deutch, Nave Frost, Amir Gilad, and Oren Sheffer.  Explanations for Data Repair Through Shapley Values, page 362–371.  2021\.
  * Duval et al. [2021] Alexandre Duval and Fragkiskos D. Malliaros.  Graphsvx: Shapley value explanations for graph neural networks.  In Machine Learning and Knowledge Discovery in Databases., pages 302–318, 2021.
  * Fan et al. [2021] Zhenan Fan, Huang Fang, Zirui Zhou, Jian Pei, et al.  Improving Fairness for Data Valuation in Federated Learning.  arXiv preprint arXiv:2109.09046, 2021.
  * Fatima et al. [2008] Shaheen S Fatima, Michael Wooldridge, and Nicholas R Jennings.  A Linear Approximation Method for the Shapley Value.  Artificial Intelligence, 172(14):1673–1699, 2008.
  * Frye et al. [2020a] Christopher Frye, Damien de Mijolla, Tom Begley, et al.  Shapley Explainability on the Data Manifold.  In International Conference on Learning Representations, 2020.
  * Frye et al. [2020b] Christopher Frye, Colin Rowat, and Ilya Feige.  Asymmetric Shapley Values: Incorporating Causal Knowledge Into Model-Agnostic Explainability.  Advances in Neural Information Processing Systems, 33, 2020.
  * Fryer et al. [2021] Daniel Fryer, Inga Strümke, and Hien Nguyen.  Shapley Values for Feature Selection: the Good, the Bad, and the Axioms.  arXiv preprint arXiv:2102.10936, 2021.
  * Ghorbani et al. [2019] Amirata Ghorbani and James Zou.  Data Shapley: Equitable Valuation of Data for Machine Learning.  In International Conference on Machine Learning, pages 2242–2251, 2019.
  * Ghorbani et al. [2020a] Amirata Ghorbani, Michael Kim, and James Zou.  A Distributional Framework for Data Valuation.  In International Conference on Machine Learning, pages 3535–3544, 2020.
  * Ghorbani et al. [2020b] Amirata Ghorbani and James Zou.  Neuron Shapley: Discovering the Responsible Neurons.  In Advances in Neural Information Processing Systems, pages 5922–5932, 2020.
  * Guha et al. [2021] Ritam Guha, Ali Hussain Khan, Pawan Kumar Singh, Ram Sarkar, and Debotosh Bhattacharjee.  Cga: A new feature selection model for visual human action recognition.  Neural Computing and Applications, 33(10):5267–5286, 2021.
  * Guyon et al. [2003] Isabelle Guyon and André Elisseeff.  An Introduction to Variable and Feature Selection.  Journal of machine learning research, 3(Mar):1157–1182, 2003.
  * Heskes et al. [2020] Tom Heskes, Evi Sijben, Ioan Gabriel Bucur, and Tom Claassen.  Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models.  Advances in Neural Information Processing Systems, 33, 2020.
  * Illés et al. [2019] Ferenc Illés and Péter Kerényi.  Estimation of the Shapley Value by Ergodic Sampling.  arXiv preprint arXiv:1906.05224, 2019.
  * Jia et al. [2019] Ruoxi Jia, David Dao, Boxin Wang, Hubis, et al.  Towards Efficient Data Valuation Based on the Shapley Value.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167–1176, 2019.
  * Koh et al. [2017] Pang Wei Koh and Percy Liang.  Understanding black-box predictions via influence functions.  In International Conference on Machine Learning, pages 1885–1894, 2017.
  * Kumar et al. [2020] Elizabeth Kumar, Suresh Venkatasubramanian, Carlos Scheidegger, and Sorelle Friedler.  Problems with Shapley-Value-Based Explanations as Feature Importance Measures.  In International Conference on Machine Learning, pages 5491–5500, 2020.
  * Kwon et al. [2021a] Yongchan Kwon, Manuel A Rivas, and James Zou.  Efficient Computation and Analysis of Distributional Shapley Values.  In International Conference on Artificial Intelligence and Statistics, pages 793–801, 2021.
  * Kwon et al. [2021b] Yongchan Kwon and James Zou.  Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning.  arXiv preprint arXiv:2110.14049, 2021.
  * Li et al. [2021] Jiahui Li, Kun Kuang, Baoxiang Wang, et al.  Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, page 934–942, 2021.
  * Liu et al. [2020] Yifei Liu, Chao Chen, Yazheng Liu, Xi Zhang, and Sihong Xie.  Shapley Values and Meta-Explanations for Probabilistic Graphical Model Inference.  In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 945–954, 2020.
  * Liu et al. [2021] Zelei Liu, Yuanyuan Chen, Han Yu, Yang Liu, and Lizhen Cui.  GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning.  arXiv preprint arXiv:2109.02053, 2021.
  * Lomeli et al. [2019] Maria Lomeli, Mark Rowland, Arthur Gretton, and Zoubin Ghahramani.  Antithetic and Monte Carlo Kernel Estimators for Partial Rankings.  Statistics and Computing, 29(5):1127–1147, 2019.
  * Lundberg et al. [2017] Scott M Lundberg and Su-In Lee.  A Unified Approach to Interpreting Model Predictions.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 4768–4777, 2017.
  * Maleki et al. [2013] Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers.  Bounding the Estimation Error of Sampling-based Shapley Value Approximation.  arXiv preprint arXiv:1306.4265, 2013.
  * Mitchell et al. [2021] Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes.  Sampling Permutations for Shapley Value Estimation.  arXiv preprint arXiv:2104.12199, 2021.
  * Okhrati et al. [2021] Ramin Okhrati and Aldo Lipani.  A Multilinear Sampling Algorithm to Estimate Shapley Values.  In 2020 25th International Conference on Pattern Recognition (ICPR), pages 7992–7999. IEEE, 2021.
  * Owen [1972] Guillermo Owen.  Multilinear Extensions of Games.  Management Science, 18(5-part-2):64–79, 1972.
  * Owen [1977] Guilliermo Owen.  Values of Games with a Priori Unions.  In Mathematical Economics and Game Theory, pages 76–88. 1977\.
  * Patel et al. [2021] Roma Patel, Marta Garnelo, Ian Gemp, Chris Dyer, and Yoram Bachrach.  Game-Theoretic Vocabulary Selection via the Shapley Value and Banzhaf Index.  In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics, pages 2789–2798, 2021\.
  * Rozemberczki et al. [2021] Benedek Rozemberczki and Rik Sarkar.  The Shapley Value of Classifiers in Ensemble Games.  In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, page 1558–1567, 2021.
  * Rubinstein et al. [2016] Reuven Y Rubinstein and Dirk P Kroese.  Simulation and the Monte Carlo Method, volume 10.  2016\.
  * Shapley [1953] Lloyd Shapley.  A Value for N-Person Games.  Contributions to the Theory of Games, pages 307–317, 1953.
  * Sharchilev et al. [2018] Boris Sharchilev, Yury Ustinovskiy, Pavel Serdyukov, and Maarten Rijke.  Finding influential training samples for gradient boosted decision trees.  In International Conference on Machine Learning, pages 4577–4585, 2018.
  * Shim et al. [2021] Dongsub Shim, Zheda Mai, Jihwan Jeong, Scott Sanner, et al.  Online Class-Incremental Continual Learning with Adversarial Shapley Value.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9630–9638, 2021.
  * Singal et al. [2021] Raghav Singal, George Michailidis, and Hoiyi Ng.  Flow-based Attribution in Graphical Models: A Recursive Shapley Approach.  In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 9733–9743, 2021.
  * Sun et al. [2012] Xin Sun, Yanheng Liu, Jin Li, Jianqi Zhu, et al.  Feature Evaluation and Selection with Cooperative Game Theory.  Pattern recognition, 45(8):2992–3002, 2012.
  * Sundararajan et al. [2020a] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal.  The Shapley Taylor Interaction Index.  In International Conference on Machine Learning, pages 9259–9268, 2020.
  * Sundararajan et al. [2020b] Mukund Sundararajan and Amir Najmi.  The Many Shapley Values for Model Explanation.  In International Conference on Machine Learning, pages 9269–9278, 2020.
  * Touati et al. [2021] Sofiane Touati, Mohammed Said Radjef, and SAIS Lakhdar.  A Bayesian Monte Carlo Method for Computing the Shapley Value: Application to Weighted Voting and Bin Packing Games.  Computers & Operations Research, 125:105094, 2021.
  * Tripathi et al. [2020] Sandhya Tripathi, N Hemachandra, and Prashant Trivedi.  Interpretable Feature Subset Selection: A Shapley Value Based Approach.  In IEEE International Conference on Big Data, pages 5463–5472, 2020\.
  * Wang et al. [2020] Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song.  A Principled Approach to Data Valuation for Federated Learning.  In Federated Learning, pages 153–167. 2020.
  * Wang et al. [2021a] Jianhong Wang, Jinxin Wang, Yuan Zhang, Yunjie Gu, and Tae-Kyun Kim.  SHAQ: Incorporating Shapley Value Theory into Q-Learning for Multi-Agent Reinforcement Learning.  arXiv preprint arXiv:2105.15013, 2021.
  * Wang et al. [2021b] Jiaxuan Wang, Jenna Wiens, and Scott Lundberg.  Shapley Flow: A Graph-Based Approach to Interpreting Model Predictions.  In International Conference on Artificial Intelligence and Statistics, pages 721–729, 2021.
  * Williamson et al. [2020] Brian Williamson and Jean Feng.  Efficient Nonparametric Statistical Inference on Population Feature Importance Using Shapley Values.  In International Conference on Machine Learning, pages 10282–10291, 2020.
  * Winter [1989] Eyal Winter.  A Value for Cooperative Games with Levels Structure of Cooperation.  International Journal of Game Theory, 18(2):227–40, 1989.
  * Yan et al. [2021] Tom Yan and Ariel D. Procaccia.  If You Like Shapley Then You Will Love the Core.  Proceedings of the AAAI Conference on Artificial Intelligence, 35(6):5751–5759, May 2021.
  * Yuan et al. [2021] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji.  On Explainability of Graph Neural Networks via Subgraph Explorations.  In Proceedings of the 38th International Conference on Machine Learning, pages 12241–12252, 2021.
  * Zhang et al. [2021] Hao Zhang, Yichen Xie, Longjie Zheng, Die Zhang, and Quanshi Zhang.  Interpreting Multivariate Shapley Interactions in DNNs.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10877–10886, 2021.