JOINT SHAPLEY VALUES: A MEASURE OF JOINT FEA-
Year: 2022

Abstract:
The Shapley value is one of the most widely used measures of feature importance partly as it measures a feature’s average effect on a model’s prediction. We introduce joint Shapley values, which directly extend Shapley’s axioms and intuitions: joint Shapley values measure a set of features’ average contribution to a model’s prediction. We prove the uniqueness of joint Shapley values, for any order of explanation. Results for games show that joint Shapley values present different insights from existing interaction indices, which assess the effect of a feature within a set of features. The joint Shapley values provide intuitive results in ML attribution problems. With binary features, we present a presence-adjusted global value that is more consistent with local intuitions than the usual approach.

text: The Shapley value is one of the most widely used measures of feature importance partly as it measures a feature’s average effect on a model’s prediction. We introduce joint Shapley values, which directly extend Shapley’s axioms and intuitions: joint Shapley values measure a set of features’ average contribution to a model’s prediction. We prove the uniqueness of joint Shapley values, for any order of explanation. Results for games show that joint Shapley values present different insights from existing interaction indices, which assess the effect of a feature within a set of features. The joint Shapley values provide intuitive results in ML attribution problems. With binary features, we present a presence-adjusted global value that is more consistent with local intuitions than the usual approach.

heading: 1 INTRODUCTION
text: Game theory’s Shapley value partitions the value arising from joint efforts among individual agents (Shapley, 1953). Specifically, denote by N = {1, . . . , n} a set of agents, and by GN the set of games on N , where a game is a set function v from 2N to R with v(∅) = 0. Then v(S) is the worth created by coalition S ⊆ N . When there is no risk of confusion, we omit braces to indicate singletons (e.g. i rather than {i}) and denote a set’s cardinality by the corresponding lower case letter (e.g. s = |S|). For any agent i, Shapley’s value is then
ψi (v) ≡ ∑
S⊆N\{i}
s! (n− s− 1)! n! [v (S ∪ i)− v (S)] . (1)
This is the average worth that i adds to possible coalitions S, weighted as follows: if the set of agents, S, has already ‘arrived’, draw the next agent, i, to arrive uniformly over the remaining N\S agents. Shapley’s value is widely used in explainable AI’s attribution problem, partitioning model predictions among individual features (q.v. Štrumbelj & Kononenko (2014); Lundberg & Lee (2017)) after the model has been trained. Evaluating the prediction function at a specific feature value corresponds to an agent’s presence; evaluating it at a reference (or baseline) feature value corresponds to the agent’s absence. A feature’s Shapley value is its average marginal contribution to the model’s predictions.
When features are correlated, individual measures of importance may mislead (Bhatt et al., 2020; Patel et al., 2021), as measures of individual significance such as the t-test do. Thus, Shapley’s value has been extended to sets of features (Grabisch & Roubens, 1999a; Marichal et al., 2007; Alshebli et al., 2019; Dhamdhere et al., 2020). As these extensions introduce axioms not present in Shapley, they do not preserve the Shapley value’s intuition.
We extend Shapley’s axioms to sets of features, randomizing over sets rather than individual features. The resulting joint Shapley value thus directly extends Shapley’s value to a measure of sets of feature importance: the average marginal contribution of a set of features to a model’s predictions.
Our approach’s novelty is seen in our extension of the null axiom: in Shapley (1953), a null agent contributes nothing to any set of agents to which it may belong; here, a null set contributes nothing to any set to which it may belong. By contrast, interaction indices (Grabisch & Roubens, 1999a; Alshebli et al., 2019; Dhamdhere et al., 2020) recursively decompose sets into individual elements, retaining the original Shapley null axiom. Thus, these indices measure sets’ contributions relative to their constituent elements — so are complementary to the joint Shapley value.
The generalised Shapley value (Marichal et al., 2007) is closer to our work, but differs in a number of respects: our probabilities are independent of the size of the set of features under consideration1; our efficiency axiom is fully joint, while theirs are based on singletons and pairs; our symmetry axiom provides uniqueness without reliance on recursion or partnership axioms.
To illustrate, consider a null coalition, T , whose individual members contribute positively to coalitions that they join. Interaction indices assign a negative value to T , as the individual members act discordantly together. However, from a joint feature importance viewpoint, T should be assigned value 0. The joint Shapley value matches this intuition.
In the movie review application presented below, the joint Shapley values reveal contributions of collections of words, including grammatical features such as negation ({disappointed} versus {won’t, disappointed}), and adjectives ({effort} versus {terrific, effort}).
Like the Shapley-Taylor interaction index (Dhamdhere et al., 2020), our efficiency axiom depends on a positive integer k, the order of explanation, which limits the number of joint Shapley values to those for subsets up to cardinality k. As there are 2N − 1 non-empty subsets of N , the full set of joint Shapley values rapidly becomes unmanageable otherwise. In practice, k should be set to trade off insight (favouring higher k) against computational cost (favouring lower k).
For each k, the extended axioms yield a unique joint Shapley value. Unlike in Shapley (1953), the joint anonymity and symmetry axioms are not interchangeable: each imposes distinct restrictions.
Section 2 presents and extends the original Shapley axioms. Section 3 introduces joint Shapley values, deriving them as the unique solution to the extended axioms. Section 4 illustrates joint Shapley values in the game theoretical environment and applies them to the Boston housing (Harrison & Rubinfeld, 1978) and Rotten Tomatoes movie review (Pang & Lee, 2005) datasets, comparing them to interaction indices and presenting a sampling technique to facilitate calculation. Section 5 concludes. The Appendix collects proofs and other supplemental material.

heading: 2 EXTENDING SHAPLEY’S AXIOMS
text: For a game v ∈ GN , and a permutation σ on N , denote a permuted game by σv ∈ GN such that σv(σ(S)) = v(S),∀S ⊆ N , where σ(S) = {σ(i) : i ∈ S}. An index φ(v) of the game v ∈ GN is any real-valued function on 2N .
The original axioms uniquely satisfied by the (standard) Shapley value ψ, are:
LI linearity : ψ is a linear function on GN , i.e. ψ(v + w) = ψ(v) + ψ(w) and ψ(av) = aψ(v) for any v, w ∈ GN and a ∈ R.
NU null : An agent that adds no worth to any coalition has no value, i.e. if v(S ∪ {i}) = v(S) for all S ⊆ N \ {i}, then ψi(v) = 0. This axiom is sometimes called dummy.
EF efficiency : The sum of the values of all agents is equal to the worth of the entire set, i.e. for all v ∈ GN , ∑n i=1 ψi(v) = v(N).
AN anonymity : For any σ on N and any v ∈ GN , ψi(v) = ψσ(i)(σv), for all i ∈ N .
1Measures of joint significance (e.g. F -tests) and model selection (e.g. BIC or AIC) penalize larger feature sets to avoid overfitting. As joint Shapley values are calculated after model training, this problem does not arise.
SY symmetry : If two agents add equal worth to all coalitions that they can both join then they receive equal value: if v(S ∪ {i}) = v(S ∪ {j})∀S ⊆ N \ {i, j} then ψi(v) = ψj(v). This is strictly weaker than anonymity.
Now extend each of these axioms in natural ways to conditions on sets rather than singletons. Below, φS(v) denotes an index for coalition S on game v.
JLI joint linearity : φ is a linear function on GN , i.e. φ(v + w) = φ(v) + φ(w) and φ(av) = aφ(v) for any v, w ∈ GN and a ∈ R. (This axiom has not been modified.)
JNU joint null : A coalition that adds no worth to any coalition has no value, i.e. if v(S ∪T ) = v(S) for all S ⊆ N \ T , then φT (v) = 0.
JEF joint efficiency : The sum of the values of all coalitions up to cardinality k is equal to the worth of the entire set, i.e. for all v ∈ GN ,∑
∅6=T⊆N : |T |≤k
φT (v) = v(N).
JAN joint anonymity : For any σ on N and any v ∈ GN , φT (v) = φσ(T )(σv), for all T ⊆ N . JSY joint symmetry : If two coalitions perform equally when joining coalitions that they can both
join and for other coalitions they add no worth then they receive an equal value, i.e. if 1. v(S ∪ T ) = v(S ∪ T ′) for all S ⊆ N \ (T ∪ T ′), 2. v(S ∪ T ) = v(S) for all S ⊆ N \ T such that S ∩ T ′ 6= ∅, 3. v(S ∪ T ′) = v(S) for all S ⊆ N \ T ′ such that S ∩ T 6= ∅,
then φT (v) = φT ′(v).
Axiom JSY only equates the joint Shapley values for coalitions T and T ′ if they contribute identically to coalitions that they may both join, and contribute nothing to the other coalitions. Axioms JLI, JEF and JAN are all also used in Dhamdhere et al. (2020). Our joint null and joint symmetry notions appear to be new: they reflect our interest in a set of features’ contribution to a model’s predictions, so that the set’s cardinality should not play a role in determining its value.

heading: 3 JOINT SHAPLEY VALUES
text: Our main result is that there is a unique solution to axioms JLI, JNU, JEF, JAN and JSY, the joint Shapley value. The uniqueness is up to the kth order of explanation; we say nothing about |T | > k. Theorem 1. For each order of explanation k ∈ {1, . . . , n}, there is a unique (up to the kth order of explanation) index φJ which satisfies axioms JLI, JNU, JEF, JAN and JSY. It has the form
φJT (v) = ∑
S⊆N\T
q|S|[v(S ∪ T )− v(S)]
for each ∅ 6= T ⊆ N with |T | ≤ k, where (q0, . . . , qn−1) uniquely solves the recursive system
q0 = 1∑k
i=1 ( n i ) , qr = ∑r−1s=(r−k)∨0 (rs)qs∑k∧(n−r) s=1 ( n−r s
) ; (2) for all r ∈ 1, . . . , n− 1.
When k = 1, the joint Shapley values coincide with Shapley’s values.2 When k = n, we have
qr = r∑ j=0 ( r j ) (−2)r−j 2n−j − 1 , ∀ r ∈ {0, . . . , n− 1}.
For each k, the constants qr are non-negative and satisfy ∑n−1 s=n−k ( n s ) qs = 1. Further, as the joint Shapley value is similar in form to equation (1)’s standard Shapley value, the value of coalition T 2The Shapley-Taylor interaction index, φST , also has this property (Dhamdhere et al., 2020).
depends on its marginal contribution to other coalitions; unlike interaction indices, it does not depend on the worth of its constituent agents.
As with the Shapley value, the joint Shapley value can be seen as the worth brought by ‘arriving’ agents but, rather than arriving one at a time, they can now also arrive in coalitions. We develop this interpretation in Appendix A.
We show here the implication of each of the joint axioms introduced above and prove Theorem 1.
It is already known that joint linearity restricts measures to be linear combinations of worths: Lemma 1 (Grabisch & Roubens (1999a), Proposition 1). If φ satisfies JLI, then for every ∅ 6= T ⊆ N there exists a family of real constants {aST }S⊆N such that for every v ∈ GN ,
φT (v) = ∑ S⊆N aTSv(S).
Axiom JNU then constrains the values of the constants {aTS}: Lemma 2. Suppose φ satisfies JLI and JNU and let {aST }S⊆N,∅ 6=T⊆N be the constants from Lemma 1. Then for every ∅ 6= T ⊆ N and ∅ 6= S ⊆ N \ T , aTS = −aTS∪T . Further, for every ∅ 6= T ⊆ N , S ⊆ N \ T , and ∅ 6= H ( T , aTS∪H = 0.
SCombining these two lemmas yields: Proposition 1. Suppose φ satisfies JLI and JNU. Then there exist constants {pT (S)} that depend on T and S such that for every ∅ 6= T ⊆ N and v ∈ GN
φT (v) = ∑
S⊆N\T
pT (S)[v(S ∪ T )− v(S)]. (3)
Now establish a condition on the {pT (S)} values which must be satisfied under JEF: Proposition 2. For each order of explanation k, φ satisfies axioms JLI, JNU and JEF if and only if for every ∅ 6= T ⊆ N with |T | ≤ k and v ∈ GN , φT (v) = ∑ S⊆N\T p
T (S)[v(S ∪ T )− v(S)] with{ pT (S) } satisfying
δN (S) = ∑
∅ 6=T⊆S: |T |≤k
pT (S \ T )− ∑
∅6=T⊆N\S: |T |≤k
pT (S), (4)
for all ∅ 6= S ⊆ N , where δN (S) equals 1 if S = N and 0 otherwise.
Recall that symmetry axiom SY is strictly weaker than anonymity axiom AN (Malawski, 2020). This is not the case for their joint counterparts: each imposes a different constraint on the constants {pT (S)}, as we shall see here. First, consider the effect of imposing JAN. Proposition 3. For each order of explanation k, φ satisfies axioms JLI, JNU, JEF and JAN if and only if for every ∅ 6= T ⊆ N and v ∈ GN , φT (v) = ∑ S⊆N\T p T (S)[v(S ∪ T )− v(S)] with { pT (S)
} satisfying (4) and
pT (S) = pT ′ (S′)∀∅ 6= T, T ′ ⊆ N, S ⊆ N \ T, S′ ⊆ N \ T ′ s.t. s = s′, t = t′. (5)
The analogous result for JSY is: Proposition 4. For each order of explanation k, φ satisfies axioms JLI, JNU, JEF and JSY if and only if for every ∅ 6= T ⊆ N and v ∈ GN , φT (v) = ∑ S⊆N\T p T (S)[v(S ∪ T )− v(S)] with { pT (S) } satisfying (4) and
pT (S) = pT ′ (S)∀∅ 6= T, T ′ ⊆ N, S ⊆ N \ (T ∪ T ′). (6)
Combining Propositions 2–4 completes the proof of Theorem 1.
The computational complexity of deriving the (q0, . . . , qn−1) is O(nk2). Once these have been determined, the joint Shapley values can be calculated; the complexity of doing so isO(3n∧ (2nnk)).

heading: 4 EXPERIMENTS

heading: 4.1 GAME THEORETICAL
text: We present two game theoretical models from Dhamdhere et al. (2020) with known ‘ground truths’. For each, we compare the joint Shapley value, the Shapley interaction index (Grabisch & Roubens, 1999b), the generalised Shapley value (Marichal et al., 2007), the added-value index (Alshebli et al., 2019), and the Shapley-Taylor interaction index (Dhamdhere et al., 2020), respectively:
φSIT (v) ≡ ∑
S⊆N\T
1
n− t+ 1 ( n− t s )−1 ∑ L⊆T (−1)t−l v (S ∪ L) ,∀T ⊆ N ;
φGST (v) ≡ ∑
S⊆N\T
(n− s− t)!s! (n− t+ 1)! [v (S ∪ T )− v (S)] ;
φAVT (v) ≡ v (T )− ∑ i∈T 1 2n−1 ∑ S⊆N :i∈S ∑ C⊆S\i c! (s− c− 1)! s! [v (C ∪ i)− v (C)] ;
φSTT (v; k) ≡
{∑ L⊆T (−1) t−l v (L) if t < k
k n ∑ S⊆N\T ( n−1 s )−1∑ L⊆T (−1) t−l v (S ∪ L) if t = k.
In the n = 3 majority game, Table 1 shows that, while Shapley-Taylor assigns 0 to singletons, the joint Shapley value recognises that singletons contribute positively when joining existing coalitions. The Shapley-Taylor and Shapley Interaction indices assign negative values to N (for discordant interaction between members); the joint Shapley rewards N for adding worth in its own right.
In the linear model with crosses, joint Shapley values’ signs can again differ from those of interaction indices: let c = −2, which sets φJ1 = 0: if i = 1 joins the empty coalition or either singleton, it adds unit worth; however, when i = 1 joins {2, 3}, it subtracts unit worth. Averaging (according to the arrival order), gives a net contribution of 0: coalition 1 does not contribute any worth in expectation. By contrast, the Shapley-Taylor value always (for k > 1) assigns value to singletons equal to their worth, as it is not (by design) capturing information about expected contributions of features.

heading: 4.2 THE AI/ML ATTRIBUTION PROBLEM
text: Following Štrumbelj & Kononenko (2010), let f be a prediction function, and x = (x1, . . . , xn) ∈ A an instance from the feature space. For a set of features S ⊆ N , define the prediction difference vx(S) when only features in S are known, as
vx(S) ≡ 1 |A| ∑ z∈A [f(τ(x, z, S))− f(z)], (7)
where τ(x, z, S) ∈ A is defined as τ(x, z, S)i equal to xi for i ∈ S and zi otherwise. Thus vx(S) is the difference between the expected prediction when only the feature values of x in S are known,
and the expected prediction when no feature values are known. Then for each T ⊆ N , φJT (vx) is the contribution of features T to the prediction f(x). To estimate φJT (vx), let X be a random variable whose law coincides with the law of the number of agents already present when T arrives in the arrival interpretation (so that the law of X depends on t, the size of T ):
P(X = i) = ( n− t i ) qi n−t∑ j=0 ( n− t j ) qj −1
for each i ∈ {0, . . . , n} and S be a random variable uniform on the set of subsets of N \ T of size X . Once X is sampled, we can generate the set of agents already arrived, called S, by choosing it uniformly from all subsets of N\T of size precisely X . Then
φJT (vx) = n−t∑ j=0 ( n− t j ) qjE[vx(T ∪ S)− vx(S)].
Thus, by the law of large numbers, we can estimate this expectation by taking an average of vi(T ∪ Si) − vi(Si) where Si has the same distribution as S and vi(S) = f(τ(x, zi, S)) − f(zi), where zi is chosen uniformly from the feature space. Refer to φJT (vx) as the local joint Shapley value of features T at instance x. We can combine local values to obtain, for each feature, a global joint Shapley value. We do so in two ways. The first is the standard methodology (q.v. Lundberg & Lee (2017)), which averages the absolute values of locals. We introduce the second for models with exclusively binary variables by considering presence/absence of features T in x. This presence-adjusted global joint Shapley value is defined as
φ̃JT (f) = 1 |A| ∑ x∈A (2 · 1x(T )=1 − 1)φJT (vx), (8)
where 1x(T )=1 is one if all features T are present in x, and 0 otherwise. Covert et al. (2020) introduced SAGE (Shapley Additive Global Importance), a more sophisticated treatment of global influence measures that maintains efficiency at the global level.
All experiments are run on a single Intel(R) Core(TM) i7-6820HQ CPU. Training details and tuning parameters are provided in the accompanying code.

heading: 4.2.1 SIMULATED DATA
text: Consider three features, x1, x2 and x3, each uniformly drawn from (0, 1) and a dataset of 50 observations. We first consider independently drawn features; we then investigate correlation by fixing x2 = 1 − x1. We use simplified ‘ML models’, f (x), to obtain exact global joint Shapley values, averaging the absolute values of local joint Shapley values derived from equation (7). Table 2 displays the results.
Independent variables As only x1 influences f1, only coalitions including it receive value; the more diluted its role, the lower the value; x2 and x3 are symmetrically irrelevant. For f2, x1 and x2 play equal roles, and receive equal values (up to variance due to the sample size). For f2 and f3, {x1, x2} receives similar value, and more than in f1, where only x1 influenced model predictions. Comparing f2 and f3 shows that values only differ for coalitions containing both x1 and x2.
Correlated features f2 now exhibits what we term a cancellation effect between x1 and x2, assigning a value of zero to coalitions containing both. Similarly, f3 reveals an enhancement effect: values assigned to coalitions with both x1 and x2 are larger than in the independent case.
Enhancement and cancellation effects do not uniquely identify underlying phenomena. To illustrate, let x1, x2 and x3 be independent Bernoulli(0.5) random variables. Setting k = 3 and letting n→∞, we obtain the exact presence-adjusted global joint Shapleys in Table 3.
The joint Shapley values containing x1 and x2 are larger for models f2 and f4 than for model f1, a different sort of enhancement effect from that above. However, the joint Shapley value for x1 is smaller in f4 than it is in f1 or f2, again a different type of cancellation effect.
Finally, joint Shapley values can provide insight into the black-box model’s structure. If, for example, f can be decomposed as f (x) = g (x1) + h (x2, . . . , xn) with independent Bernoulli(0.5) random variables, then the presence-adjusted global joint Shapley value of x1 is 1/2 (g (1)− g (0)) ∑n−1 s=0 ( n−1 s ) qs = 5/21, as shown in the table. If the joint Shapley value deviates from this, we reject the decomposition, as in the case of f4.

heading: 4.2.2 BOSTON HOUSING DATA
text: For comparability, we follow Dhamdhere et al. (2020) by training a random forest on the Boston housing dataset (Harrison & Rubinfeld, 1978), computing global values using the first notion discussed above. Table 4 presents the largest and smallest global joint Shapley and Shapley-Taylor values.
For k = 1, the joint Shapley values are the classical Shapley values. The unimportance of CHAS seems to reflect its low variance (only 35 of 506 units back onto the Charles).
For k = 2, LSTAT and RM still have the largest joint Shapley values, with {LSTAT, RM} having third largest. The top pairs all involve LSTAT or RM, indicating that these variables also contribute to explaining house prices jointly with other variables. By contrast, {LSTAT, RM} is the 16th largest Shapley-Taylor interaction value. The k = 2 singleton joint Shapley values are fairly evenly distributed throughout the pairs; by contrast, the singleton k = 2 Shapley-Taylor values outrank all the pairs. This is consistent with our extension of axiom NU to not favour singletons. The largest joint Shapley value involving NOX is {NOX, LSTAT}, which is about five times as large as {NOX, DIS}
and {NOX, RAD}. This is consistent with Harrison and Rubinfeld’s observation that NOX offset RAD and DIS, but reinforced LSTAT: knowing the values of NOX and LSTAT adds a lot of predictive power; knowing the values of NOX and RAD or DIS tends to wash out additional predictive power.
For k = 3, singletons again dominate: the largest triple is {AGE, LSTAT, RM}, the three individually most important features. Continuing the above analysis, the joint Shapley value of {DIS, RAD} is about 0.015, while that of {DIS, NOX, RAD} is about 0.008, and that of {DIS, LSTAT, RAD} is about 0.022. We understand this to mean {DIS, NOX, RAD} contains the same sort of information as {DIS, RAD}, but with NOX offsetting the other variables, while LSTAT brings novel socio-economic information to the distance variables DIS and RAD, which it continues to partially offset. Similarly, the least important joint features include the individually unimportant CHAS and its variants —- echoing the role played by RM and LSTAT at the top of the list. While {DIS, LSTAT} has a ShapleyTaylor value of 1.33 (indicating a large interaction between the pair but not its overall importance), its joint Shapley is 0.06 (ranked 18th) — directly assigning a value of importance.
Table 4’s values are exact. Figure 1 demonstrates the estimation procedure above, showing convergence of the sampled values as the iterations increase. As with other sampling procedures (e.g. Štrumbelj & Kononenko (2014)), this cuts the complexity to order n to a linear power of k; as k → n, the complexity approaches 2n times a polynomial in n (compared to 3n for the exact φJ ).

heading: 4.2.3 MOVIE REVIEWS
text: We train a fully connected neural network (two hidden layers, 16 units per layer, ReLU activations) on the binary movie review classifications in Pang & Lee (2005). From the full set of reviews, we remove a test block of 100 (picked to include those in Table 1 of Dhamdhere et al. (2020)) for analysis. We encode reviews as the 1000 most common words in the corpus, augmented by key words in Table 1 of Dhamdhere et al. (2020) to aid comparison of measures, for a total of 1004. (The DSA features are drawn from positive reviews: {won’t}, {disappointed}, {both}, {inspiring}, {a}, {crisp}, {excellent}, {youthful}, {John}, {terrific}.) Binary accuracy is typically c. 76% after four epochs.
Table 5’s local joint Shapley values are tiny as each of the 21004 − 1 joint features has a tiny effect on the probability of a positive review. In the vein of Dhamdhere et al., we identify intuitive effects:
1. negation: the negative local joint Shapley values for {disappointed} and {be, disappointed} become positive when negated by adding {won’t} to the coalition.
2. enhancement: the positive local joint Shapley values for {both} and {and} are enhanced by the positive {and, both}.
3. context: the sign of local joint Shapley values involving {well} depend on the context; while {you, well} is positive, {left, well} is negative.
4. lost potential: the positive local joint Shapley values involving {fascinating} become negative when {been} is added.
5. adjectival: while {director} and {effort} are individually negative, they become positive when qualified with the adjectives {winning} and {terrific}, respectively.
As the 10 DSA features are a very small subset of all 1004, we cannot asses whether JEF holds. However, as a health check note: the average presence-adjusted local joint Shapleys over the positive reviews is about 20% larger than that over the negative reviews. They are both negative: as these features are drawn from positive reviews, but largely absent in any given review, their effect is negative. Further, Table 6 indicates that the ranking of single features is largely preserved as k increases from 1 to 2: the exception is {a, crisp}: in the corpus, {crisp} is typically preceded by {a}.
Figure 2 shows the estimated values’ convergence.

heading: 5 CONCLUSIONS
text: The joint Shapley value directly extends Shapley’s value to measure the effect of a set of features on a model’s predictions. Further work is needed to maintain properties like global efficiency (Covert et al., 2020) and to make sampling more efficient (Williamson & Feng, 2020; Mitchell et al., 2021). We believe that understanding complex models is labor intensive. Nevertheless, we envisage a common workflow that computes k = 1 Shapley values, followed by k = 2 to identify strong pairwise effects; analyses for k ≥ 3 then respond to the analyst’s evolving questions about the model’s functioning.

heading: 6 ETHICS STATEMENT
text: This paper contributes to the literature on explainable AI, an important component of the Fairness, Accountability and Transparency research agenda for ethical AI. It does not use human subjects; it only draws on publicly available datasets; the work has not been sponsored, and does not seek to promote any third organisations; none of the authors face any conflict of interest.

heading: 7 REPRODUCIBILITY STATEMENT
text: Our proofs and source code are available in the accompanying supplemental material; all data are taken from the public domain.

heading: A ARRIVAL ORDER INTERPRETATION
text: As discussed in the paper, the joint Shapley value can be viewed in terms of the worth brought by ‘arriving’ agents but, rather than arriving one at time, they can now also arrive in coalitions. To be precise, consider this procedure: at time 0, no agents have arrived; at each t ∈ {1, 2, . . .}, the next set of agents to arrive is chosen uniformly from the set of non-empty subsets of size at most k of the remaining (yet to arrive) agents. Then φJT is the expected worth brought by coalition T when it arrives (a coalition is assigned zero worth if it does not arrive at any time). To see this, denote by Ai the coalition to arrive at time i, by Bi the union of all coalitions that have arrived up to time i: Bi = ⋃ j≤iAj , and by pT the probability that at some time coalition T arrives, pT = P(∃ i : Bi = T ). We have the recursive relationship:
pT = n∑ i=1 ∑ S(T :
|S|≥|T |−k
P(Bi−1 = S)P(Ai = T \ S | Bi−1 = S)
= n∑ i=1 ∑ S(T :
|S|≥|T |−k
P(Bi−1 = S) (n−|S|)∧k∑ r=1 ( n− |S| r )−1 = |T |−1∑ s=(|T |−k)∨0 ( t s ) pS (n−s)∧k∑ r=1 ( n− s r )−1 , where in the last line S is any set of size s. Thus we see that pT only depends on T through its cardinality, and defining
p̂t := pT (n−t)∧k∑ r=1 ( n− t r )−1 for any T with |T | = t, the expected worth brought by coalition T under this procedure is
n∑ i=1 ∑ S⊆N\T P(Bi−1 = S, Ai = T )[v(S ∪ T )− v(S)] = ∑ S⊆N\T p̂|S|[v(S ∪ T )− v(S)].
Further, we have the relationship
p̂t =
∑t−1 s=(t−k)∨0 ( t s ) ps∑(n−t)∧k
r=1
( n−t r ) and since we know that p0 = 1 (we start with no agents having arrived) and pn = 1 (we finish with all agents having arrived) we also have the identities:
1 = n−1∑ s=n−k ( n s ) p̂s, 1 = p̂0 k∑ r=1 ( n s ) .
By comparing with the identities defining (q0, . . . , qn−1), we deduce that p̂t = qt for all t ∈ {0, . . . , n− 1}, which verifies this arrival interpretation.

heading: B PROOFS
text: Proof of Lemma 2. For the first statement, for each ∅ 6= S ⊆ N \ T consider the game
vS(R) = { 1 if R = S or R = S ∪ T, 0 otherwise.
Then for such S, by JNU, φT (vS) = 0. By this equality, Lemma 1, and the definition of vS , 0 = φT (vS) = ∑ R⊆N aTRvS(R) = a T S + a T S∪T .
For the second statement, for each ∅ 6= H ( T let αH be a constant and for S ⊆ N \ T , consider the game
xαS (R) = { αH if R = S ∪H for some ∅ 6= H ( T, 0 otherwise.
By JNU, φT (xαS ) = 0 for every S ⊆ N \ T . Thus by Lemma 1
0 = φT (x α S ) = ∑ R⊆N aTRx α S = ∑ ∅ 6=H(T aTS∪Hx α S (S ∪H) = ∑ ∅ 6=H(T aTS∪HαH .
Since this holds for every choice of constants αH , it follows that aTS∪H = 0 for all S ⊆ N \ T and ∅ 6= H ( T , as required.
Proof of Proposition 1. By Lemma 1 there exist constants {aTS}S⊆N,∅ 6=T⊆N such that for every v and ∅ 6= T ⊆ N ,
φT (v) = ∑ S⊆N aTSv(S) = ∑ S⊆N\T aTSv(S) + ∑ ∅ 6=H(T aTS∪Hv(S ∪H) + aTS∪T v(S ∪ T )  =
∑ S⊆N\T (aTSv(S) + a T S∪T v(S ∪ T )) = ∑ S⊆N\T aTS∪T [v(S ∪ T )− v(S)];
where the last two equalities owe to Lemma 2. The proof is complete by setting pT (S) = aTS∪T .
Proof of Proposition 2. Suppose φ satisfies axioms JLI, JNU and JEF. Then by Proposition 1 the constants {pT (S)} exist, such that for every v and ∅ 6= T ⊆ N ,
φT (v) = ∑
S⊆N\T
pT (S)[v(S ∪ T )− v(S)].
Now for each ∅ 6= R ⊆ N consider the identity game
wR(S) = { 1 if S = R, 0 otherwise.
Then for every ∅ 6= T ⊆ N with |T | ≤ k, φT (wR) = ∑
S⊆N\T
pT (S)[wR(S ∪ T )− wR(S)].
Note that the term wR(S ∪ T ) − wR(S) in the above sum is equal to 1 only when S ( R and T = R \ S, i.e. only when S = R \ T and ∅ 6= T ⊆ R. Further note that this term is equal to −1 only when S = R and T 6= ∅, i.e. when S = R and ∅ 6= T ⊆ N \R (as must have S ∩ T = ∅). In all other cases, this term is 0. Hence we deduce from JEF that
δN (R) = wR(N) = ∑
∅6=T⊆R: |T |≤k
pT (R \ T )− ∑
∅ 6=T⊆N\R: |T |≤k
pT (R).
Now we show the implication in the other direction. If φT (v) = ∑ S⊆N\T p
T (S)[v(S ∪ T )− v(S)] then it is immediate that JLI and JNU are satisfied. For JEF, we wish to show that for every v,∑
∅6=T⊆N : |T |≤k
∑ S⊆N\T pT (S)[v(S ∪ T )− v(S)] = v(N).
Note that for each ∅ 6= R ⊆ N , the coefficient of v(R) on the left-hand side in the above equation is∑ ∅ 6=T⊆R: |T |≤k pT (R \ T )− ∑ ∅6=T⊆N\R: |T |≤k pT (R).
But by equation (4), this is equal to δN (R).
Proof of Proposition 3. In light of Proposition 2 we just have to consider JAN.
Only if: Suppose φ satisfies JLI, JNU, JEF and JAN. First, we shall establish that
pT (S) = pT (S′) ∀∅ 6= T ⊆ N, S, S′ ⊆ N \ T s.t. s = s′. (9)
Fix such a T , S and S′. Consider again the identity game, wS and let σ be a self-inverse permutation such that S 7→ S′, S′ 7→ S, and σ ({i}) = {i} for all i 6∈ S ∪ S′. As T ⊆ N \ (S ∪ S′) and σ (T ) = T , we have by JAN
φT (wS) = φσ−1(T ) (wS) = φT (σwS)
where
σwS (R) = wS ( σ−1 (R) ) = { 1 if R = σ (S) = S′ 0 otherwise } = wS′ (R) .
Hence we obtain φT (wS) = φT (σwS) = φT (wS′). Next, from Proposition 1 we have φT (wS) = ∑
Q⊆N\T
pT (Q) [wS (Q ∪ T )− wS (Q)] = −pT (S) ,
and similarly φT (wS′) = −pT (S′). Hence we obtain pT (S) = pT (S′), showing (9). Using induction on s, we now establish that (5) holds. Fix T and T ′ of the same size. For the base case, suppose s = s′ = n − t. For S ⊆ N \ T and S′ ⊆ N \ T ′, this forces S = N \ T and S′ = N \ T ′. Now consider the game
xn (R) = { 1 if r = n 0 otherwise,
so that xn (R) = 1 if and only if R = N . Define a self-inverse permutation σ so that σ (T ) = T ′, σ (T ′) = T and σ ({i}) = {i} for all i 6∈ (T ∪ T ′). Then by JAN and as σxn = xn,
φT (xn) = φσ−1(T ′)(xn) = φT ′(σxn) = φT ′(xn).
Next, from Proposition 1, φT (xn) = ∑
Q⊆N\T
pT (Q) [xn (T ∪Q)− xn (Q)] = pT (N \ T ) ,
and similarly φT ′ (wn) = pT ′ (N \ T ′). Hence we obtain pT (N \ T ) = pT ′ (N \ T ′) which establishes the base case.
We now suppose that pT (S) = pT ′ (S′) for all s = s′ ≥ n− c where S ⊆ N \ T , S′ ⊆ N \ T ′ and c is a positive integer. We shall show that pT (S) = pT ′ (S′) for all s = s′ ≥ n− c− 1 where where S ⊆ N \ T and S′ ⊆ N \ T ′. To this end, consider the game
x (R) = { 1 if r ≥ n− c− 1 + t, 0 otherwise .
Thus, as before, we may write φT (x) = ∑
Q⊆N\T
pT (Q) [x (Q ∪ T )− x (Q)] = ∑
Q⊆N\T n−c−1≤q<n−c−1+t
pT (Q) .
Similarly, φT ′ (x) =
∑ Q′⊆N\T ′
n−c−1≤q′<n−c−1+t
pT (Q) .
Again, by JAN, we prove that φT (x) = φT ′ (x). Define a self-inverse permutation σ so that σ (T ) = T ′, σ (T ′) = T and σ ({i}) = {i} for all i 6∈ (T ∪ T ′). As worth in game x depends only on a coalition’s cardinality, we have σx = x. Thus, by JAN, φT (x) = φσ(T )(σx) = φσ(T )(x) = φT ′(x).
However, φT (x) = ∑
Q⊆N\T q=n−c−1
pT (Q)+ ∑
Q⊆N\T n−c−1<q<n−c−1+t
pT (Q) = ∑
Q⊆N\T q=n−c−1
pT (Q)+ ∑
Q′⊆N\T ′ n−c−1<q′<n−c−1+t
pT ′ (Q′) ;
and φT ′ (x) = ∑ Q′⊆N\T ′ q′=n−c−1 pT ′ (Q′) +
∑ Q′⊆N\T ′
n−c−1<q′<n−c−1+t
pT ′ (Q′)
which gives, by the inductive hypothesis and φT (x) = φT ′(x),∑ Q⊆N\T q=n−c−1 pT (Q) = ∑ Q′⊆N\T ′ q′=n−c−1 pT ′ (Q′) .
But by (9), pT (Q) = pT (Q′) if q = q′. Thus the above equation becomes( n− t
n− c− 1
) pT (Q) = ( n− t
n− c− 1
) pT ′ (Q′)
for any Q ⊆ N \T and Q′ ⊆ N \T ′ with q = q′ = n− c−1. Thus, pT (Q) = pT ′ (Q′), completing the inductive step, and the ‘only if’ statement.
If: Suppose (5) is satisfied. Fix a permutation σ on N and game v ∈ GN . Then for any ∅ 6= T ⊆ N , φT (σv) = ∑
S⊆N\T
pT (S) [σv (S ∪ T )− σv (S)] = ∑
S⊆N\T
pT (S) [ v ( σ−1 (S ∪ T ) ) − v ( σ−1 (S) )] =
∑ S⊆N\T pT (S) [ v ( σ−1 (S) ∪ σ−1 (T ) ) − v ( σ−1 (S) )] .
Defining the set S′ = σ−1 (S) allows us to rewrite the above as φT (σv) = · · · = ∑
S′⊆N\σ−1(T )
pT (σ (S′)) [ v ( S′ ∪ σ−1 (T ) ) − v (S′) ] =
∑ S′⊆N\σ−1(T ) pσ −1(T ) (S′) [ v ( S′ ∪ σ−1 (T ) ) − v (S′) ] = φσ−1(T )(v),
with the penultimate step due to condition (5).
Proof of Proposition 4. In light of Proposition 2 we just have to consider JSY.
Only if: Suppose φ satisfies JLI, JNU, JEF and JSY, fix ∅ 6= T, T ′ ⊆ N , and consider again the identity game wR. Then for any ∅ 6= R ⊆ N \ (T ∪ T ′),
• wR(S ∪ T ) = 0 = wR(S ∪ T ′) for all S ⊆ N \ (T ∪ T ′),
• wR(S ∪ T ) = 0 = wR(S) for all S ⊆ N \ T such that S ∩ T ′ 6= ∅,
• wR(S ∪ T ′) = 0 = wR(S) for all S ⊆ N \ T ′ such that S ∩ T 6= ∅.
Hence by JSY φT (wR) = φT ′(wR). But φT (wR) = pT (R) and φT ′(wR) = pT (R). This shows that pT (R) = pT ′ (R) for all ∅ 6= R ⊆ N \ (T ∪ T ′). To show that pT (∅) = pT ′(∅) we consider the game
w∗(S) = { 1 if S 6= ∅, 0 otherwise.
Then
• w∗(S ∪ T ) = 1 = w∗(S ∪ T ′) for all S ⊆ N \ (T ∪ T ′),
• w∗(S ∪ T ) = 1 = w∗(S) for all S ⊆ N \ T such that S ∩ T ′ 6= ∅ (since then S 6= ∅),
• w∗(S ∪ T ′) = 1 = w∗(S) for all S ⊆ N \ T ′ such that S ∩ T 6= ∅ (since then S 6= ∅).
It thus follows by JSY that φT (w∗) = φT ′(w∗). However, φT (w∗) = pT (∅) and φT ′(w∗) = pT ′ (∅), which gives the required identity and shows that (6) holds.
If: Now we show the implication in the other direction. Suppose (6) holds and v ∈ GN satisfies the three conditions in JSY. Then
φT (v) = ∑
S⊆N\T
pT (S)[v(S ∪ T )− v(S)] = ∑
S⊆N\(T∪T ′)
pT (S)[v(S ∪ T )− v(S)]
= ∑
S⊆N\(T∪T ′)
pT ′ (S)[v(S ∪ T ′)− v(S)] = ∑ S⊆N\T ′ pT ′ (S)[v(S ∪ T ′)− v(S)] = φT ′(v).
Hence JSY is satisfied.
Proof of Theorem 1. We have to show that there exists exactly one choice of constants {pT (S)} which satisfy equations (4)–(6). Notice that satisfying (5) and (6) is equivalent to satisfying
pT (S) = pT ′ (S)∀S ⊆ N \ T, S′ ⊆ N \ T ′ s.t. s = s′.
Thus pT (S) does not depend on T at all, and only depends on the cardinality of S. Let qs denote pT (S) for any S ⊆ N \ T . Then we can re-write equation (4) in terms of qs as
1 = n−1∑ i=n−k ( n i ) qi, (10)
qs =
∑s−1 i=(s−k)∨0 ( s i ) qi∑k∧(n−s)
i=1
( n−s i ) ∀ s ∈ {1, . . . , n− 1}. (11) Note that for any q0, equation (11) fully determines all other qi, for i ∈ {1, . . . , n − 1} and q0 is then determined by (10). Thus there is at most one solution. However, we have already identified (see the arrival-order discussion in Appendix A) that a solution to this recurrence is given by
(q0, . . . , qn−1) = (p̂0, . . . , p̂n−1), for which p̂0 = (∑k
i=1 ( n i ))−1 .

heading: C STRONG JOINT SYMMETRY
text: We examine the effect of removing conditions 2 and 3 from JSY. As it turns out, this leads to the non-existence of an index. To be precise, we consider replacing axioms JAN and JSY with:
SJS strong joint symmetry : fix ∅ 6= T, T ′ ⊆ N . Then
v (S ∪ T ) = v (S ∪ T ′)∀S ⊆ N\ (T ∪ T ′) ⇒ φT (v) = φT ′ (v) .
Proposition 5. There is no index φ satisfying axioms JLI, JNU, JEF, and SJS that is guaranteed to exist for all games.
Proof. Since φ satisfies JLI, JNU, and JEF, by Proposition 2, φT (v) = ∑
S⊆N\T
pT (S)[v(S ∪ T )− v(S)]
with {pT (S)} satisfying (4), for any game v ∈ GN . We consider two games v1, v2 ∈ G{1,2}. As N = {1, 2}, (4) gives p{1}(∅) = p{2}({1}), p{2}(∅) = p{1}({2}), and p{1,2}(∅) + p{1}(∅) + p{2}(∅) = 1.
Suppose v1({1}) = v1({1, 2}) = 1, v1({2}) = 0. SJS thus gives that φ{1}(v1) = φ{1,2}(v1), i.e. p{1,2}(∅) = p{1}(∅) + p{2}(∅) which implies p{1,2}(∅) = 1/2.
Suppose also that v2({1}) = v2({1, 2}) = v2({2}) = 1. SJS gives that φ{1}(v2) = φ{2}(v2) = φ{1,2}(v2), i.e. p{1,2}(∅) = p{1}(∅) = p{2}(∅) which implies p{1,2}(∅) = 1/3, giving a contradiction.
Thus, SJS is too strong a notion of symmetry, imposing linear restrictions on sets of unequal sizes.

Review summaries:
This work introduces "joint Shapley values", which directly extend Shapley’s axioms and intuitions: joint Shapley values measure a set of features’ average effect on a model’s prediction. This work naturally extends Shapley's axioms from a single feature, to sets of features. In a nutshell: joint Shapley values measure the average marginal contribution of a set of features to a model’s predictions. This work presents rigorous mathematical results for the joint Shapley values approach. This approach is then evaluated on several datasets, including: (i) simulated data, (ii) Boston Housing data, (iii) Movie Review data.

The paper proposes an extension of the Shapley values, namely, the joint Shapley values which measure a set of features' average effect of a models prediction. The uniqueness of the joint Shapley values is proved. Moreover, training details and tuning parameters are provided in the accompanying code.