# Quantification of the environment of cool stars using numerical simulations

J. J. Chebly ${}^{1},^{2}$ J. D. Alvarado-Gómez1 K. Poppenhaeger${}^{1},^{2}$
1Leibniz Institute for Astrophysics, An der Sternwarte 16, 14482, Potsdam,
Germany
2Institute of Physics and Astronomy, University of Potsdam, Potsdam-Golm,
14476, Germany

(2022)

###### Abstract

Stars interact with their planets through gravitation, radiation, and magnetic
fields. Although magnetic activity decreases with time, reducing associated
high-energy (e.g., coronal XUV emission, flares), stellar winds persist
throughout the entire evolution of the system. Their cumulative effect will be
dominant for both the star and for possible orbiting exoplanets, affecting in
this way the expected habitability conditions. However, observations of
stellar winds in low-mass main sequence stars are limited, which motivates the
usage of models as a pathway to explore how these winds look like and how they
behave. Here we present the results from a grid of 3D state-of-the-art stellar
wind models for cool stars (spectral types F to M). We explore the role played
by the different stellar properties (mass, radius, rotation, magnetic field)
on the characteristics of the resulting magnetized winds (mass and angular
momentum losses, terminal speeds, wind topology) and isolate the most
important dependencies between the parameters involved. These results will be
used to establish scaling laws that will complement the lack of stellar wind
observational constraints.

###### keywords:

Stars: low-mass, stars: magnetic fields, stars: mass loss, stars: winds,
outflows, methods: numerical, magnetic fields (magnetohydrodynamics:) MHD

††volume: 370††journal: Winds of Stars and Exoplanets††editors: A. A. Vidotto,
L. Fossati & J. Vink, eds.

##  1 Introduction

The winds from cool, low-mass main sequence stars are weak and cannot be
observed directly, except in the case of our own Sun. This means that the
nature and behavior of these winds are not well understood. More knowledge
about stellar winds is needed because they carry a significant amount of
angular momentum that affects the rotational evolution of the star (Johnstone
et al. 2015). These magnetized winds also affect the atmospheric evolution of
planetary atmospheres (Kislyakova et al. 2014). Several techniques have been
proposed to infer the presence of stellar winds in cool stars. Examples are
the free emission at radio wavelengths (Gaidos et al., 2000) and searches for
X-ray emission induced by charge exchange (Wargelin & Drake, 2002) between
ionised stellar winds and neutral interstellar hydrogen. Unfortunately, both
methods resulted in non-detections, but provided important upper limits on the
wind mass-loss rates of a handful of Sun-like stars. One of the indirect
techniques is the Ly-$\alpha$ absorption method, which uses high-resolution UV
spectra from the Hubble Space Telescope (HST). As winds propagate from the
star, they collide with the Inter Stellar Medium (ISM), forming ’astrospheres’
analogous to the ’heliosphere’ surrounding the Sun (Wood, 2004). Signs of
charge exchange occur when the ISM is neutral or at least partially neutral,
leading to astrospheric absorption signature in the Ly-$\alpha$ line. This
method is the most successful for measuring the mass loss rate ($\rm\dot{M}$)
of winds from solar-like stars, with nearly 20 measurements to date (Wood et
al., 2021). The new measurements showed, that the coronal activity and
spectral type are not enough to determine wind properties. However, this
method has not provided measurements for larger numbers of stars because it is
only applicable to stars within 10-15 pc. Beyond this distance, ISM becomes
fully ionized. Also, Ly-$\alpha$ lines observed from cool stars are always
heavily contaminated by interstellar absorption. The lack of observational
data and associated limitations motivate the use of numerical simulations as a
way to improve our understanding of stellar winds. Models based on the Alfvén
waves are more popular when simulating the stellar wind from stars other than
the Sun (Suzuki, 2006). These waves are considered to be a likely key
mechanism for solar wind heating and acceleration (Van der Holst et al.,
2014). In this study, we use one of the most realistic physics-based solar
models to quantify the environment of low-mass main-sequence stars with an
outer convective envelope, i.e., late-F to M type. Our goal is to provide a
method for estimating stellar wind quantities as other related parameters
become available. This will also help to further constrain the habitable zone
(HZs) of exoplanets around these types of stars.

##  2 Stellar Wind Model and Selected Sample

Figure 1: Illustration of a 3D numerical magnetohydrodynamics simulation using
the Alfvén wave-solar model (AWSoM). Plots A and B show a steady-state
solution of the stellar wind simulation of $\tau$ Boo (F7) and some stellar
wind properties such as the dynamic pressure and the Alfvén surface ($S_{\rm
A}$). In C, we show the magnetogram reconstructed from observed Zeeman Doppler
Imaging maps used as the inner boundary of Solar Corona domain. The Inner
Heliosphere (IH) is shown in plot A along with the limits of the habitable
zone around $\tau$ Boo.

We use the Alfvén Wave Solar Model (AWSoM) to calculate different steady-state
solutions for a grid of models. This model reproduces successfully the solar
wind in a realistic manner (Oran et al. 2013, Sachdeva et al. 2019). Assuming
that stellar winds from solar analogues are driven by the same process as the
solar wind, we extend the model to stars other than the sun. AWSoM is part of
the Space Weather Modelling Framework (SWMF), which integrates numerical
models from the solar corona to the upper atmosphere into a high-performance
coupled model (Tóth et al., 2012).

In our simulation, we couple between two modules: the solar corona (SC), a
spherical domain, and the inner heliosphere (IH), a Cartesian domain, as shown
in Fig. 1, in the case of F, G, and K stars. Using the IH module was necessary
for these stars in order to accommodate their large HZs. For M-dwarfs, the
coupling was not necessary since the HZs is closer in. The SC domain in our
simulations ranges from 1.05 $R_{\filledstar}$ up to 67 $R_{\filledstar}$ for
F, G, and K stars. For the M-dwarfs we require a sufficiently large SC domain
(250 $R_{\filledstar}$) so that the resulting $S_{\rm A}$ would be completely
contained within it. Once the wind solution in SC reaches a steady state
(converges), SC provides the plasma variables at the inner boundary of IH.
Domain-overlap (from 62 $R_{\filledstar}$ to 67 $R_{\filledstar}$) is used in
the coupling procedure between the two domains for F, G, and K type stars. The
Inner Heliosphere component uses an ideal MHD approach and covers the range
from 62 $R_{\filledstar}$ up to 600 R${}_{\filledstar}$.

For our stellar wind models, the inner boundary conditions of AWSoM within the
SC component (e.g. plasma density, temperature, Alfvén wave pointing flux, and
the Alfvén wave correlation length), are kept identical to the values used to
simulate the solar wind (Van der Holst et al., 2014). In contrast, the
magnetic field and stellar properties are modified for each star. The strength
and geometry of the magnetic field is taken from from observed, reconstructed
Zeeman Doppler Imaging (ZDI) maps. This is a tomographic imaging technique
(Donati & Brown 1997; Kochukhov & Piskunov 2002) that allows us to reconstruct
the large-scale magnetic field (intensity and orientation) at the surface of
the star from a series of circular polarization spectra (Donati et al., 2006).
Therefore, the simulations are more realistic compared to models that assume
simplified/idealized field geometries. We only retrieve the radial component
of the magnetic field strength from the ZDI maps since solar wind models
neglect the contribution from the other components. We have also restricted
the parameter space to stars with an outer convective envelope. The sample
considered in this study consists of 21 stars (3F, 4G, 6K, 5M) located within
10 pc (taken from See et al. 2019). Each star has its corresponding stellar
rotation period ($P_{\rm rot}$), mass ($m_{\filledstar}$), and radius
($r_{\filledstar}$). The fastest star in our data set corresponds to an M6
star with $P_{\rm rot}$ = 0.71 d, and the slowest is a K3 star with a $P_{\rm
rot}$ = 42.2 d. As for the magnetic field strength, it ranges from 5G to 2kG.

##  3 Numerical estimate of stellar wind properties

By definition, the Alfvén surface ($S_{\rm A}$) corresponds to the boundary
between magnetically coupled outflows (MA $<$ 1) that do not carry angular
momentum away from the star and the escaping stellar wind (MA $>$ 1). In
numerical models, the $S_{\rm A}$ is used to extract the mass loss rate
($\rm\dot{M}$), and the angular momentum loss rate ($\rm\dot{J}$) (e.g. Cohen
et al. 2010; Garraffo et al. 2015a, Alvarado-Gómez et al. 2016). The angular
momentum loss rate is obtained by integrating over the $S_{\rm A}$. Knowing
the wind speed and density, the $\rm\dot{M}$ of a star can be calculated by
integrating over a closed area enclosing the star beyond the $S_{\rm A}$. Note
that the Alfvén surface does not have a regular shape when visualized in 3D.
This is due to several stellar parameters, such as the magnetic field
distribution on the stellar surface, the wind velocity, and the density.

$\mathcal{(}\rm\dot{M})=\rm{\rho}(\rm\textbf{u}\cdot dA)$ (1)
$\mathcal{(}\rm\dot{J})=\Omega\rho R^{2}\sin^{2}\theta(\textbf{u}\cdot dA)$
(2)

Here $\rho$ represents the wind density, u is the wind speed vector and $dA$
is the vector surface element. $\rm\Omega$ is the angular frequency of the
star and $\rm\theta$ is the angle between the lever arm and the rotation axis.
$\Omega$ changes with the different stellar rotation $\Omega=2\pi/\rm P_{\rm
rot}$.

###  3.1 $\rm\dot{M}$ and $\rm\dot{J}$ as a function of $B_{\rm R}$

(a) * (b) * Figure 2: Numerical estimate of $\rm\dot{M}$ and $\rm\dot{J}$ in
function of the radial magnetic field ($B_{\rm R}$). The colors correspond to
the different spectral types in our sample. The results shows that the loss
rates are strongly dependent on the $B_{\rm R}$.

[.54] [.54]

In Fig. 2(a), we plot the the $\rm\dot{M}$ and $\rm\dot{J}$, as estimated
using the method described previously, against $B_{\rm Rmax}$ for our sample
of stars. As expected, a stronger $B_{\rm R}$ produces stronger winds. This
means either faster or denser winds. This interplay dictates $\rm\dot{M}$ and
$\rm\dot{J}$ (cf. 1, 2), which will increase with increasing $B$ strength. We
also note that we observe a strong dependence of $\rm\dot{M}$ and $\rm\dot{J}$
in stellar winds as a function of $B_{\rm Rmax}$, regardless of spectral type.
In addition, we see on the left plot in figure 2(a) the presence of an outlier
in M-dwarfs for the strongest field $B_{\rm Rmax}=1.5$ kG. One thing that
might be causing this, is the way the simulation is being performed. We
already pointed out that we had to push further out the SC boundary condition
for the M-dwarfs. By doing this we reached a low grid resolution near the
outer boundary which might have cause the $\rm\dot{M}$ to have a small value.
Further testing will be performed to identify the possible cause of this
outlier.

###  3.2 $\rm\dot{M}$ as function of Rossby number

The evolution of the magnetic field complexity was proved to be an important
asset for explaining the bimodal distribution seen in the spin-down of stars
that follows the Skumanich rotation evolution in young Open Clusters (OCs)
(Garraffo et al., 2018). This complexity is a function of the Rossby number
($R_{\rm o}$) which is the ratio between the $P_{\rm rot}$ and the convective
turnover time. The Rossby number is considered an important parameter for
studying the effects of rotation on the dynamo action in stars with convective
outer layers, being related to the dynamo number $D=R_{\rm o}^{-2}$
(Charbonnneau 2020).

Figure 3: 3D MHD $\rm\dot{M}$ estimation in function of the Rossby number
($R_{\rm o}$). The colors correspond to the different spectral types in our
sample and Solar value is represented by a star symbol. This plot highlights
the importance of the field geometry in the magnetic field activity on the
star surface.

We used the Rossby number as a magnetic field geometry parameter and explored
how it changes with the $\rm\dot{M}$ loss rate of each star in our sample. We
adapted empirical convective turnover times defined in Cranmer & Saar (2011),
which depends on the effective temperature (Eq. 3).

$\mathcal{\rm}\tau_{c}=314.24\exp{({\frac{-T_{\rm eff}}{1952.5K}-(\frac{T_{\rm
eff}}{6250K})^{18}})}+0.002$ (3)

Our $\rm\dot{M}$ versus $R_{\rm o}$ (Fig. 3) shows a good representation of
the trend for the normalized X-ray luminosity as a function of $R_{\rm o}$ in
Reiners (2012) and Wright et al. (2018). The magnetic activity increases with
decreasing $R_{\rm o}$ ($R_{\rm o}$ $\leq$ 0.1). At fast rotation ($R_{\rm o}$
= 0.1), the dynamo reaches a saturation level that cannot be exceeded even if
the star rotates much faster. Moreover, the simulated $\rm\dot{M}$ appears to
have a maximum for stars with $R_{\rm o}$ $<$ 0.1. This raises the question of
whether stellar winds also reach a saturated regime. We also point out that
stars with different $R_{\rm o}$ can still have similar $\rm\dot{M}$. This is
expected since the field complexity changes with rotation rate (Vidotto et al.
2014a; Garraffo et al. 2015b; Réville et al. 2015), which in turn influence
the amount of mass loss.

##  4 Discussion and Conclusion

Understanding the behaviour and structure of cool stars’ stellar winds and the
habitability of its orbiting exoplanets requires detailed information on the
strength and topology of the surface magnetic field. Analysis of high-
resolution optical and NIR stellar intensity and polarisation spectra is
currently the only approach that allows such information to be obtained in a
systematic and direct manner. The measurement of quantities on the stellar
surface is much simpler and does not suffer from problems with the ISM, which
will always be a problem for the astrospheric and for the charge-exchange
technique. Moreover, the number of cool stars with ZDI observations is growing
($\sim$ 200, Marsden et al. 2014), so in principle estimates/models are
possible for a larger number of stars that would allow to extract statistical
properties about their winds. Quantifying these winds is becoming more crucial
as the number of discovered exoplanets is increasing (currently 5178 confirmed
exoplanets) and we enter a new era of detailed atmospheric characterization
with JWST and E-ELTs. On the other hand, we are reaching the maximum number of
systems that can be probed with the astrospheric technique due to the
limitations mentioned earlier. Three-dimensional MHD models that use ZDI maps
as inner boundary conditions for the magnetic field strength and geometry,
will help us obtain a more realistic estimate of the stellar wind parameters
(e.g. dynamic pressure, terminal velocity, sub/super-Alfvénic conditions).
Hence, we will be filling the missing observations and making progress in
constraining the habitable conditions around low-mass main sequence stars.

## References

  * Alvarado-Gómez et al. (2016) Alvarado-Gómez, J. D., Hussain, G. A. J., Cohen, O., et al. 2016, A&A, 594, A95
  * Charbonneau (2020) Charbonneau, P. 2020, Living Reviews in Solar Physics, 17, 4
  * Cohen et al. (2010) Cohen, O., Drake, J. J., Kashyap, V. L., Sokolov, I. V., & Gombosi, T. I. 2010, ApJ Letters, 723, L64
  * Cranmer & Saar (2011) Cranmer, S. R., & Saar, S. H. 2011, ApJ, 741, 54
  * Donati & Brown (1997) Donati, J. F., & Brown, S. F. 1997, A&A, 326, 1135
  * Donati et al. (2006) Donati, J. F., Howarth, I. D., Jardine, M. M., et al. 2006, MNRAS, 370, 629
  * Gaidos et al. (2000) Gaidos, E. J., Güdel, M., & Blake, G. A. 2000, GeoRL, 27, 501
  * Garraffo et al. (2015a) Garraffo, C., Drake, J. J., & Cohen, O. 2015a, ApJ, 813, 40
  * Garraffo et al. (2015b) —. 2015b, ApJ Letters, 807, L6
  * Garraffo et al. (2018) Garraffo, C., Drake, J. J., Dotter, A., et al. 2018, ApJ, 862, 90
  * Johnstone et al. (2015) Johnstone, C. P., Güdel, M., Brott, I., & Lüftinger, T. 2015, A&A, 577, A28
  * Kislyakova et al. (2014) Kislyakova, K. G., Holmström, M., Lammer, H., Odert, P., & Khodachenko, M. L. 2014, Science, 346, 981
  * Kochukhov & Piskunov (2002) Kochukhov, O., & Piskunov, N. 2002, A&A, 388, 868
  * Marsden et al. (2014) Marsden, S., Petit, P., Jeffers, S., et al. 2014, in Magnetic Fields throughout Stellar Evolution, ed. P. Petit, M. Jardine, & H. C. Spruit, Vol. 302, 138–141
  * Oran et al. (2013) Oran, R., van der Holst, B., Landi, E., et al. 2013, ApJ, 778, 176
  * Reiners (2012) Reiners, A. 2012, Living Reviews in Solar Physics, 9, 1
  * Réville et al. (2015) Réville, V., Brun, A. S., Strugarek, A., et al. 2015, ApJ, 814, 99
  * Sachdeva et al. (2019) Sachdeva, N., van der Holst, B., Manchester, W. B., et al. 2019, ApJ, 887, 83
  * See et al. (2019) See, V., Matt, S. P., Folsom, C. P., et al. 2019, ApJ, 876, 118
  * Suzuki (2006) Suzuki, T. K. 2006, ApJ Letters, 640, L75
  * Tóth et al. (2012) Tóth, G., van der Holst, B., Sokolov, I. V., et al. 2012, Journal of Computational Physics, 231, 870
  * Van der Holst et al. (2014) Van der Holst, B., Sokolov, I. V., Meng, X., et al. 2014, ApJ, 782, 81
  * Vidotto et al. (2014) Vidotto, A. A., Gregory, S. G., Jardine, M., et al. 2014, MNRAS, 441, 2361
  * Wargelin & Drake (2002) Wargelin, B. J., & Drake, J. J. 2002, ApJ, 578, 503
  * Wood (2004) Wood, B. E. 2004, Living Reviews in Solar Physics, 1, 2
  * Wood et al. (2021) Wood, B. E., Müller, H.-R., Redfield, S., et al. 2021, ApJ, 915, 37
  * Wright et al. (2018) Wright, N. J., Newton, E. R., Williams, P. K. G., Drake, J. J., & Yadav, R. K. 2018, MNRAS, 479, 2351


# Joint Shapley values: a measure of joint feature importance

Chris Harris
Tokyo, Japan
Raptor Financial Technologies
<EMAIL_ADDRESS>
&Richard Pymar
Economics, Mathematics & Statistics
Birkbeck College University of London, UK
<EMAIL_ADDRESS>
&Colin Rowat
Economics
University of Birmingham, UK
<EMAIL_ADDRESS>

###### 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.

##  1 Introduction

_Game theory_ ’s Shapley value partitions the value arising from joint efforts
among individual agents (Shapley, 1953). Specifically, denote by
$N=\\{1,\ldots,n\\}$ a set of agents, and by $\mathcal{G}^{N}$ the set of
games on $N$, where a game is a set function $v$ from $2^{N}$ to $\mathbb{R}$
with $v(\varnothing)=0$. Then $v(S)$ is the worth created by coalition
$S\subseteq N$. When there is no risk of confusion, we omit braces to indicate
singletons (e.g. $i$ rather than $\left\\{i\right\\}$) and denote a set’s
cardinality by the corresponding lower case letter (e.g. $s=\left|S\right|$).

For any agent $i$, Shapley’s value is then

$\psi_{i}\left(v\right)\equiv\sum_{S\subseteq
N\backslash\left\\{i\right\\}}\frac{s!\left(n-s-1\right)!}{n!}\left[v\left(S\cup
i\right)-v\left(S\right)\right].$ (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\backslash 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 consideration111Measures 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.; 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 $2^{N}-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.

##  2 Extending Shapley’s axioms

For a game $v\in\mathcal{G}^{N}$, and a permutation $\sigma$ on $N$, denote a
_permuted game_ by $\sigma v\in\mathcal{G}^{N}$ such that $\sigma
v(\sigma(S))=v(S),\forall\,S\subseteq N$, where $\sigma(S)=\\{\sigma(i):\,i\in
S\\}$. An index $\phi(v)$ of the game $v\in\mathcal{G}^{N}$ is any real-valued
function on $2^{N}$.

The original axioms uniquely satisfied by the (standard) Shapley value $\psi$,
are:

LI

_linearity_ : $\psi$ is a linear function on $\mathcal{G}^{N}$, i.e.
$\psi(v+w)=\psi(v)+\psi(w)$ and $\psi(av)=a\psi(v)$ for any
$v,w\in\mathcal{G}^{N}$ and $a\in\mathbb{R}$.

NU

_null_ : An agent that adds no worth to any coalition has no value, i.e. if
$v(S\cup\\{i\\})=v(S)$ for all $S\subseteq N\setminus\\{i\\}$, then
$\psi_{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\in\mathcal{G}^{N}$,
$\sum_{i=1}^{n}\psi_{i}(v)=v(N)$.

AN

_anonymity_ : For any $\sigma$ on $N$ and any $v\in\mathcal{G}^{N}$,
$\psi_{i}(v)=\psi_{\sigma(i)}(\sigma v)$, for all $i\in N$.

SY

_symmetry_ : If two agents add equal worth to all coalitions that they can
both join then they receive equal value: if
$v(S\cup\\{i\\})=v(S\cup\\{j\\})\forall S\subseteq N\setminus\\{i,j\\}$ then
$\psi_{i}(v)=\psi_{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, $\phi_{S}(v)$ denotes an index for coalition $S$ on
game $v$.

JLI

_joint linearity_ : $\phi$ is a linear function on $\mathcal{G}^{N}$, i.e.
$\phi(v+w)=\phi(v)+\phi(w)$ and $\phi(av)=a\phi(v)$ for any
$v,w\in\mathcal{G}^{N}$ and $a\in\mathbb{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\cup T)=v(S)$ for all $S\subseteq N\setminus T$, then
$\phi_{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\in\mathcal{G}^{N}$,

$\sum_{\begin{subarray}{c}\varnothing\neq T\subseteq N:\\\ |T|\leq
k\end{subarray}}\phi_{T}(v)=v(N).$

JAN

_joint anonymity_ : For any $\sigma$ on $N$ and any $v\in\mathcal{G}^{N}$,
$\phi_{T}(v)=\phi_{\sigma(T)}(\sigma v)$, for all $T\subseteq 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. 1.

$v(S\cup T)=v(S\cup T^{\prime})$ for all $S\subseteq N\setminus(T\cup
T^{\prime})$,

  2. 2.

$v(S\cup T)=v(S)$ for all $S\subseteq N\setminus T$ such that $S\cap
T^{\prime}\neq\varnothing$,

  3. 3.

$v(S\cup T^{\prime})=v(S)$ for all $S\subseteq N\setminus T^{\prime}$ such
that $S\cap T\neq\varnothing$,

then $\phi_{T}(v)=\phi_{T^{\prime}}(v)$.

Axiom JSY only equates the joint Shapley values for coalitions $T$ and
$T^{\prime}$ 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.

##  3 Joint Shapley values

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
$k^{\textnormal{th}}$ order of explanation; we say nothing about $|T|>k$.

######  Theorem 1.

For each order of explanation $k\in\\{1,\ldots,n\\}$, there is a unique (up to
the $k^{\textnormal{th}}$ order of explanation) index $\phi^{J}$ which
satisfies axioms JLI, JNU, JEF, JAN and JSY. It has the form

$\phi^{J}_{T}(v)=\sum_{S\subseteq N\setminus T}q_{|S|}[v(S\cup T)-v(S)]$

for each $\varnothing\neq T\subseteq N$ with $|T|\leq k$, where
$(q_{0},\ldots,q_{n-1})$ uniquely solves the recursive system

$q_{0}=\frac{1}{\sum_{i=1}^{k}\binom{n}{i}},\quad
q_{r}=\frac{\sum_{s=(r-k)\vee
0}^{r-1}\binom{r}{s}q_{s}}{\sum_{s=1}^{k\wedge(n-r)}\binom{n-r}{s}};$ (2)

for all $r\in{1,\ldots,n-1}$.

When $k=1$, the joint Shapley values coincide with Shapley’s values.222The
Shapley-Taylor interaction index, $\phi^{ST}$, also has this property
(Dhamdhere et al., 2020). When $k=n$, we have

$\displaystyle
q_{r}=\sum_{j=0}^{r}\binom{r}{j}\frac{\left(-2\right)^{r-j}}{2^{n-j}-1},\quad\forall\,r\in\\{0,\ldots,n-1\\}.$

For each $k$, the constants $q_{r}$ are non-negative and satisfy
$\sum_{s=n-k}^{n-1}\binom{n}{s}q_{s}=1$. Further, as the joint Shapley value
is similar in form to equation (1)’s standard Shapley value, the value of
coalition $T$ 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 $\phi$ satisfies JLI, then for every $\varnothing\neq T\subseteq N$ there
exists a family of real constants $\\{a_{T}^{S}\\}_{S\subseteq N}$ such that
for every $v\in\mathcal{G}^{N}$,

$\phi_{T}(v)=\sum_{S\subseteq N}a_{S}^{T}v(S).$

Axiom JNU then constrains the values of the constants $\\{a_{S}^{T}\\}$:

######  Lemma 2.

Suppose $\phi$ satisfies JLI and JNU and let $\\{a_{T}^{S}\\}_{S\subseteq
N,\,\varnothing\neq T\subseteq N}$ be the constants from Lemma 1. Then for
every $\varnothing\neq T\subseteq N$ and $\varnothing\neq S\subseteq
N\setminus T$, $a_{S}^{T}=-a_{S\cup T}^{T}$. Further, for every
$\varnothing\neq T\subseteq N$, $S\subseteq N\setminus T$, and
$\varnothing\neq H\subsetneq T$, $a_{S\cup H}^{T}=0$.

SCombining these two lemmas yields:

######  Proposition 1.

Suppose $\phi$ satisfies JLI and JNU. Then there exist constants
$\\{p^{T}(S)\\}$ that depend on $T$ and $S$ such that for every
$\varnothing\neq T\subseteq N$ and $v\in\mathcal{G}^{N}$

$\phi_{T}(v)=\sum_{S\subseteq N\setminus T}p^{T}(S)[v(S\cup T)-v(S)].$ (3)

Now establish a condition on the $\\{p^{T}(S)\\}$ values which must be
satisfied under JEF:

######  Proposition 2.

For each order of explanation $k$, $\phi$ satisfies axioms JLI, JNU and JEF if
and only if for every $\varnothing\neq T\subseteq N$ with $|T|\leq k$ and
$v\in\mathcal{G}^{N}$, $\phi_{T}(v)=\sum_{S\subseteq N\setminus
T}p^{T}(S)[v(S\cup T)-v(S)]$ with $\left\\{p^{T}\left(S\right)\right\\}$
satisfying

$\displaystyle\delta_{N}(S)=\sum_{\begin{subarray}{c}\varnothing\neq
T\subseteq S:\\\ |T|\leq k\end{subarray}}p^{T}(S\setminus
T)-\sum_{\begin{subarray}{c}\varnothing\neq T\subseteq N\setminus S:\\\
|T|\leq k\end{subarray}}p^{T}(S),$ (4)

for all $\varnothing\neq S\subseteq N$, where $\delta_{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 $\\{p^{T}(S)\\}$, as we shall
see here. First, consider the effect of imposing JAN.

######  Proposition 3.

For each order of explanation $k$, $\phi$ satisfies axioms JLI, JNU, JEF and
JAN if and only if for every $\varnothing\neq T\subseteq N$ and
$v\in\mathcal{G}^{N}$, $\phi_{T}(v)=\sum_{S\subseteq N\setminus
T}p^{T}(S)[v(S\cup T)-v(S)]$ with $\left\\{p^{T}\left(S\right)\right\\}$
satisfying (4) and

$p^{T}\left(S\right)=p^{T^{\prime}}\left(S^{\prime}\right)\forall\,\varnothing\neq
T,T^{\prime}\subseteq N,\,S\subseteq N\setminus T,\,S^{\prime}\subseteq
N\setminus T^{\prime}\text{ s.t. }s=s^{\prime},t=t^{\prime}.$ (5)

The analogous result for JSY is:

######  Proposition 4.

For each order of explanation $k$, $\phi$ satisfies axioms JLI, JNU, JEF and
JSY if and only if for every $\varnothing\neq T\subseteq N$ and
$v\in\mathcal{G}^{N}$, $\phi_{T}(v)=\sum_{S\subseteq N\setminus
T}p^{T}(S)[v(S\cup T)-v(S)]$ with $\left\\{p^{T}\left(S\right)\right\\}$
satisfying (4) and

$p^{T}\left(S\right)=p^{T^{\prime}}\left(S\right)\forall\,\varnothing\neq
T,T^{\prime}\subseteq N,\,S\subseteq N\setminus(T\cup T^{\prime}).$ (6)

Combining Propositions 2–4 completes the proof of Theorem 1.

The computational complexity of deriving the $(q_{0},\ldots,q_{n-1})$ is
$\mathcal{O}(nk^{2})$. Once these have been determined, the joint Shapley
values can be calculated; the complexity of doing so is
$\mathcal{O}(3^{n}\wedge(2^{n}n^{k}))$.

##  4 Experiments

###  4.1 Game theoretical

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:

$\displaystyle\phi^{SI}_{T}\left(v\right)$
$\displaystyle\equiv\sum_{S\subseteq N\backslash
T}\frac{1}{n-t+1}\binom{n-t}{s}^{-1}\sum_{L\subseteq
T}\left(-1\right)^{t-l}v\left(S\cup L\right),\forall T\subseteq N;$
$\displaystyle\phi^{GS}_{T}\left(v\right)$
$\displaystyle\equiv\sum_{S\subseteq N\backslash
T}\frac{\left(n-s-t\right)!s!}{\left(n-t+1\right)!}\left[v\left(S\cup
T\right)-v\left(S\right)\right];$ $\displaystyle\phi^{AV}_{T}\left(v\right)$
$\displaystyle\equiv v\left(T\right)-\sum_{i\in
T}\frac{1}{2^{n-1}}\sum_{S\subseteq N:i\in S}\sum_{C\subseteq S\backslash
i}\frac{c!\left(s-c-1\right)!}{s!}\left[v\left(C\cup
i\right)-v\left(C\right)\right];$ $\displaystyle\phi^{ST}_{T}\left(v;k\right)$
$\displaystyle\equiv\begin{cases}\sum_{L\subseteq
T}\left(-1\right)^{t-l}v\left(L\right)&\mbox{if }t<k\\\
\frac{k}{n}\sum_{S\subseteq N\backslash T}\binom{n-1}{s}^{-1}\sum_{L\subseteq
T}\left(-1\right)^{t-l}v\left(S\cup L\right)&\mbox{if }t=k.\end{cases}$

Table 1: Joint and interaction measures in $n=3$ game theory examples

| $v$ | Shapley | $\phi^{SI}$ | $\phi^{GS}$ | $\phi^{AV}$ | $\phi^{ST}\left(v_{m};k\right)$ | $\phi^{J}\left(v_{m};k\right)$
---|---|---|---|---|---|---|---
$T$ |  | $\left(k=1\right)$ |  |  |  | $k=2$ | $k=3$ | $k=2$ | $k=3$
The majority game: $v_{m}\left(T\right)=1$ when $t\geq 2$, and is equal to $0$
otherwise
$i$ | $0$ | $\nicefrac{{1}}{{3}}$ | $\nicefrac{{1}}{{3}}$ | $\nicefrac{{1}}{{3}}$ | $-\nicefrac{{1}}{{3}}$ | $0$ | $0$ | $\nicefrac{{1}}{{9}}$ | $\nicefrac{{2}}{{21}}$
$i,j$ | $1$ |  | $0$ | $\nicefrac{{1}}{{2}}$ | $\nicefrac{{1}}{{3}}$ | $\nicefrac{{1}}{{3}}$ | $1$ | $\nicefrac{{2}}{{9}}$ | $\nicefrac{{4}}{{21}}$
$N$ | $1$ |  | $-2$ | $1$ | $0$ |  | $-2$ |  | $\nicefrac{{3}}{{21}}$
A linear model with crosses: $v_{c}\left(T\right)=\sum_{i\in
T}1+c\max\left\\{0,t-2\right\\}$ for $c\in\mathbb{R}$
$i$ | $1$ | $\nicefrac{{1}}{{3}}\left(3+c\right)$ | $\nicefrac{{1}}{{3}}\left(3+c\right)$ | $\nicefrac{{1}}{{3}}\left(3+c\right)$ | $-\nicefrac{{1}}{{12}}c$ | $1$ | $1$ | $\nicefrac{{5}}{{18}}\left(2+c\right)$ | $\nicefrac{{5}}{{21}}\left(2+c\right)$
$i,j$ | $2$ |  | $\nicefrac{{1}}{{3}}c$ | $\nicefrac{{1}}{{2}}\left(4+c\right)$ | $-\nicefrac{{1}}{{6}}c$ | $\nicefrac{{1}}{{3}}c$ | $0$ | $\nicefrac{{1}}{{18}}\left(8+c\right)$ | $\nicefrac{{1}}{{21}}\left(8+c\right)$
$N$ | $3+c$ |  | $c$ | $3+c$ | $\nicefrac{{3}}{{4}}c$ |  | $c$ |  | $\nicefrac{{3}}{{21}}\left(3+c\right)$

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 $\phi^{J}_{1}=0$: if
$i=1$ joins the empty coalition or either singleton, it adds unit worth;
however, when $i=1$ joins $\left\\{2,3\right\\}$, 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.

###  4.2 The AI/ML attribution problem

Following Štrumbelj & Kononenko (2010), let $f$ be a prediction function, and
$\bm{x}=(x_{1},\ldots,x_{n})\in\mathcal{A}$ an instance from the feature
space. For a set of features $S\subseteq N$, define the prediction difference
$v_{\bm{x}}(S)$ when only features in $S$ are known, as

$v_{\bm{x}}(S)\equiv\frac{1}{|\mathcal{A}|}\sum_{\bm{z}\in\mathcal{A}}[f(\tau(\bm{x},\bm{z},S))-f(\bm{z})],$
(7)

where $\tau(\bm{x},\bm{z},S)\in\mathcal{A}$ is defined as
$\tau(\bm{x},\bm{z},S)_{i}$ equal to $x_{i}$ for $i\in S$ and $z_{i}$
otherwise. Thus $v_{\bm{x}}(S)$ is the difference between the expected
prediction when only the feature values of $\bm{x}$ in $S$ are known, and the
expected prediction when no feature values are known. Then for each
$T\subseteq N$, $\phi^{J}_{T}(v_{\bm{x}})$ is the contribution of features $T$
to the prediction $f(\bm{x})$. To estimate $\phi^{J}_{T}(v_{\bm{x}})$, 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$):

$\mathbb{P}(X=i)=\binom{n-t}{i}q_{i}\left(\sum_{j=0}^{n-t}\binom{n-t}{j}q_{j}\right)^{-1}$

for each $i\in\\{0,\ldots,n\\}$ and $\mathcal{S}$ be a random variable uniform
on the set of subsets of $N\setminus 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\backslash T$ of size precisely $X$. Then

$\phi^{J}_{T}(v_{\bm{x}})=\sum_{j=0}^{n-t}\binom{n-t}{j}q_{j}\mathbb{E}[v_{\bm{x}}(T\cup\mathcal{S})-v_{\bm{x}}(\mathcal{S})].$

Thus, by the law of large numbers, we can estimate this expectation by taking
an average of $v_{i}(T\cup S_{i})-v_{i}(S_{i})$ where $S_{i}$ has the same
distribution as $\mathcal{S}$ and $v_{i}(S)=f(\tau(\bm{x},z_{i},S))-f(z_{i})$,
where $z_{i}$ is chosen uniformly from the feature space. Refer to
$\phi_{T}^{J}(v_{\bm{x}})$ as the _local_ joint Shapley value of features $T$
at instance $\bm{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 $\bm{x}$. This
_presence-adjusted_ global joint Shapley value is defined as

$\tilde{\phi}_{T}^{J}(f)=\frac{1}{|\mathcal{A}|}\sum_{\bm{x}\in\mathcal{A}}(2\cdot{\bf
1}_{\bm{x}(T)=1}-1)\phi_{T}^{J}(v_{x}),$ (8)

where ${\bf 1}_{\bm{x}(T)=1}$ is one if all features $T$ are present in
$\bm{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.

####  4.2.1 Simulated data

Consider three features, $x_{1},x_{2}$ and $x_{3}$, each uniformly drawn from
$\left(0,1\right)$ and a dataset of 50 observations. We first consider
independently drawn features; we then investigate correlation by fixing
$x_{2}=1-x_{1}$. We use simplified ‘ML models’, $f\left(\bm{x}\right)$, 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.

Table 2: Uniform random variables; $k=3$ | $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{1},x_{2}$ | $x_{1},x_{3}$ | $x_{2},x_{3}$ | $x_{1},x_{2},x_{3}$
---|---|---|---|---|---|---|---
independent features
$f_{1}\left(\bm{x}\right)=x_{1}$ | 0.122 | 0 | 0 | 0.049 | 0.049 | 0 | 0.037
$f_{2}\left(\bm{x}\right)=x_{1}+x_{2}$ | 0.122 | 0.114 | 0 | 0.061 | 0.049 | 0.045 | 0.046
$f_{3}\left(\bm{x}\right)=x_{1}-x_{2}$ | 0.122 | 0.114 | 0 | 0.062 | 0.049 | 0.045 | 0.047
correlated features: $x_{2}=1-x_{1}$
$f_{2}\left(\bm{x}\right)$ | 0.122 | 0.122 | 0 | 0 | 0.049 | 0.049 | 0
$f_{3}\left(\bm{x}\right)$ | 0.122 | 0.122 | 0 | 0.098 | 0.049 | 0.049 | 0.073

##### Independent variables

As only $x_{1}$ influences $f_{1}$, only coalitions including it receive
value; the more diluted its role, the lower the value; $x_{2}$ and $x_{3}$ are
symmetrically irrelevant. For $f_{2}$, $x_{1}$ and $x_{2}$ play equal roles,
and receive equal values (up to variance due to the sample size). For $f_{2}$
and $f_{3}$, $\left\\{x_{1},x_{2}\right\\}$ receives similar value, and more
than in $f_{1}$, where only $x_{1}$ influenced model predictions. Comparing
$f_{2}$ and $f_{3}$ shows that values only differ for coalitions containing
both $x_{1}$ and $x_{2}$.

##### Correlated features

$f_{2}$ now exhibits what we term a _cancellation effect_ between $x_{1}$ and
$x_{2}$, assigning a value of zero to coalitions containing both. Similarly,
$f_{3}$ reveals an _enhancement effect_ : values assigned to coalitions with
both $x_{1}$ and $x_{2}$ are larger than in the independent case.

Enhancement and cancellation effects do not uniquely identify underlying
phenomena. To illustrate, let $x_{1},x_{2}$ and $x_{3}$ be independent
Bernoulli(0.5) random variables. Setting $k=3$ and letting
$n\rightarrow\infty$, we obtain the exact presence-adjusted global joint
Shapleys in Table 3.

Table 3: Bernoulli(0.5) random variables; $k=3$ $f\left(\bm{x}\right)$ | $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{1},x_{2}$ | $x_{1},x_{3}$ | $x_{2},x_{3}$ | $x_{1},x_{2},x_{3}$
---|---|---|---|---|---|---|---
$f_{1}\left(\bm{x}\right)=x_{1}$ | $\nicefrac{{5}}{{21}}$ | $0$ | $0$ | $\nicefrac{{1}}{{21}}$ | $\nicefrac{{1}}{{21}}$ | $0$ | $\nicefrac{{1}}{{56}}$
$f_{2}\left(\bm{x}\right)=x_{1}+x_{2}$ | $\nicefrac{{5}}{{21}}$ | $\nicefrac{{5}}{{21}}$ | $0$ | $\nicefrac{{2}}{{21}}$ | $\nicefrac{{1}}{{21}}$ | $\nicefrac{{1}}{{21}}$ | $\nicefrac{{1}}{{28}}$
$f_{4}\left(\bm{x}\right)=x_{1}x_{2}$ | $\nicefrac{{5}}{{42}}$ | $\nicefrac{{5}}{{42}}$ | $0$ | $\nicefrac{{1}}{{14}}$ | $\nicefrac{{1}}{{42}}$ | $\nicefrac{{1}}{{42}}$ | $\nicefrac{{3}}{{112}}$

The joint Shapley values containing $x_{1}$ and $x_{2}$ are larger for models
$f_{2}$ and $f_{4}$ than for model $f_{1}$, a different sort of enhancement
effect from that above. However, the joint Shapley value for $x_{1}$ is
smaller in $f_{4}$ than it is in $f_{1}$ or $f_{2}$, 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\left(\bm{x}\right)=g\left(x_{1}\right)+h\left(x_{2},\ldots,x_{n}\right)$
with independent Bernoulli(0.5) random variables, then the presence-adjusted
global joint Shapley value of $x_{1}$ is
$\nicefrac{{1}}{{2}}\left(g\left(1\right)-g\left(0\right)\right)\sum_{s=0}^{n-1}\binom{n-1}{s}q_{s}=\nicefrac{{5}}{{21}}$,
as shown in the table. If the joint Shapley value deviates from this, we
reject the decomposition, as in the case of $f_{4}$.

####  4.2.2 Boston housing data

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.

Table 4: Joint Shapley values for the Boston dataset

Shapley | $\phi^{ST}\left(f;k\right)$ | $\phi^{J}\left(f;k\right)$
---|---|---
$\left(k=1\right)$ | $k=2$ | $k=3$ | $k=2$ | $k=3$
RM: $2.57$ | RM: $3.12$ | RM: $3.12$ | LSTAT: $0.63$ | LSTAT: $0.42$
LSTAT: $2.47$ | LSTAT: $2.04$ | LSTAT: $2.04$ | RM: $0.56$ | RM: $0.34$
AGE: $0.81$ | DIS: $1.55$ | DIS: $1.55$ | LSTAT, RM: $0.30$ | AGE: $0.11$
DIS: $0.63$ | CRIM: $1.37$ | CRIM: $1.37$ | AGE, LSTAT: $0.21$ | LSTAT, RM: $0.11$
CRIM: $0.46$ | B: $1.31$ | DIS, LSTAT: $1.33$ | AGE, RM: $0.20$ | NOX: $0.10$
NOX: $0.44$ | NOX: $1.15$ | B: $1.31$ | DIS, RM: $0.19$ | DIS: $0.08$
PTRATIO: $0.27$ | ⋮ | ⋮ | ⋮ | ⋮
B: $0.24$ | CHAS, RM: $0.15$ | AGE, CRIM, RM: $0.21$ | CHAS, TAX: $0.02$ | RAD, TAX, ZN: $0.00$
TAX: $0.22$ | LSTAT, TAX: $0.15$ | AGE, DIS, PTRATIO: $0.21$ | RAD, ZN: $0.01$ | CHAS: $0.00$
INDUS: $0.19$ | INDUS, RAD: $0.15$ | DIS, LSTAT, PTRATIO: $0.21$ | CHAS, RAD: $0.01$ | CHAS, RAD, TAX: $0.00$
RAD: $0.13$ | NOX, TAX: $0.14$ | AGE, LSTAT, PTRATIO: $0.20$ | ZN: $0.01$ | CHAS, RAD, ZN: $0.00$
ZN: $0.07$ | DIS, INDUS: $0.13$ | AGE, NOX, RM: $0.20$ | CHAS: $0.01$ | CHAS, TAX, ZN: $0.00$
CHAS: $0.07$ | DIS, PTRATIO: $0.12$ | B, CRIM, LSTAT: $0.19$ | CHAS, ZN: $0.01$ | CHAS, ZN: $0.00$

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 Shapley-Taylor 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 2 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\rightarrow
n$, the complexity approaches $2^{n}$ times a polynomial in $n$ (compared to
$3^{n}$ for the exact $\phi^{J}$).

50100150200250300Number of iterations1.41.51.61.71.81.9L2 Norm

Figure 1: Sampled $\phi^{J}$ converges to exact $\phi^{J}$ with $L^{2}$ norm
$\approx 1.45$ ; $k=2$ Boston

050100150200250300Number of iterations0.000000.000050.000100.000150.00020L2
Norm

Figure 2: Difference between consecutive $\phi^{J}$ samples averages converges
to zero; $k=2$ movie review #2

####  4.2.3 Movie reviews

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: Examples of local joint Shapley values in the Pang & Lee (2005) movie
reviews

Review | joint Shapleys
---|---
1: _negation_ : aficionados of the whodunit won’t be disappointed |  | {disappointed}: $-2\times 10^{-5}$
---
{won’t}: $6\times 10^{-5}$
{be, disappointed}: $-9\times 10^{-8}$
{won’t, disappointed}: $6\times 10^{-8}$
{won’t, be, disappointed}: $5\times 10^{-9}$
2: _enhancement_ : both inspiring and pure joy |  | {both}: $2\times 10^{-4}$
---
{and}: $6\times 10^{-5}$
{and, both}: $1\times 10^{-6}$
3: _context_ : you wish Jacquot had left well enough alone |  | {you, well}: $9\times 10^{-7}$
---
{left, well}: $-3\times 10^{-7}$
4: _lost potential_ : fascinating little thriller that would have been perfect |  | {would}: $-1\times 10^{-4}$
---
{fascinating}: $2\times 10^{-4}$
{would, fascinating}: $3\times 10^{-7}$
{would, been, fascinating}: $-1\times 10^{-8}$
5: _adjectival_ : director …award-winning …make a terrific effort |  | {effort}: $-1\times 10^{-5}$
---
{director}: $-9\times 10^{-6}$
{terrific, effort}: $8\times 10^{-7}$
{winning, director}: $5\times 10^{-7}$

Table 5’s local joint Shapley values are tiny as each of the $2^{1004}-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. 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. 2.

_enhancement_ : the positive local joint Shapley values for {both} and {and}
are enhanced by the positive {and, both}.

  3. 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. 4.

_lost potential_ : the positive local joint Shapley values involving
{fascinating} become negative when {been} is added.

  5. 5.

_adjectival_ : while {director} and {effort} are individually negative, they
become positive when qualified with the adjectives {winning} and {terrific},
respectively.

For global values, as the features are binary, we compute the presence-
adjusted global joint Shapleys, $\tilde{\phi}^{J}$. Comparing the DSA
features’ global $\tilde{\phi}^{J}$ across the test reviews for $k=1$ and
$k=2$ shows {terrific} to be the largest, followed by {both} then {excellent}.
This reflects prevalence in the training set, where {terrific} appears four
times as often in positive reviews. Similarly, on the negative
$\tilde{\phi}^{J}$ side, {John} is followed by {disappointed}: {John} appears
thrice as often in negative reviews.

The largest pairs are {both, inspiring} followed by {excellent, youthful}. All
of the pairs, except {John, terrific}, have a positive sign: these pairs
typically do not appear outside the positive reviews from which they were
drawn. As our encoding discards sequential information, the pairs are smaller
than the singletons: a coalition merely indicates co-occurrence in a review,
rather than a bigram.

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.

Table 6: Largest presence-adjusted global joint Shapley values on DSA features

$k=1$ | terrific | both | excellent | won’t | crisp | youthful | a | inspiring | disappointed | John
---|---|---|---|---|---|---|---|---|---|---
$k=2$ | terrific | both | excellent | won’t | a | youthful | inspiring | crisp | disappointed | John

##  5 Conclusions

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\geq 3$ then respond
to the analyst’s evolving questions about the model’s functioning.

##  6 Ethics statement

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.

##  7 Reproducibility statement

Our proofs and source code are available in the accompanying supplemental
material; all data are taken from the public domain.

## References

  * Alshebli et al. (2019) Bedoor K Alshebli, Tomasz P Michalak, Oskar Skibski, Michael Wooldridge, and Talal Rahwan.  A measure of added value in groups.  _ACM Transactions on Autonomous and Adaptive Systems (TAAS)_ , 13(4):1–46, 2019.
  * Bhatt et al. (2020) Umang Bhatt, Alice Xiang, Shubham Sharma, Adrian Weller, Ankur Taly, Yunhan Jia, Joydeep Ghosh, Ruchir Puri, José M. F. Moura, and Peter Eckersley.  Explainable machine learning in deployment.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , pp. 648–657, 2020.
  * Covert et al. (2020) Ian Covert, Scott Lundberg, and Su-In Lee.  Understanding global feature contributions with additive importance measures.  _arXiv preprint arXiv:2004.00668_ , 2020.
  * Dhamdhere et al. (2020) Kedar Dhamdhere, Ashish Agarwal, and Mukund Sundararajan.  The Shapley Taylor interaction index.  In _International Conference on Machine Learning_ , pp. 9259–9268. PMLR, 2020.
  * Grabisch & Roubens (1999a) Michel Grabisch and Marc Roubens.  An axiomatic approach to the concept of interaction among players in cooperative games.  _International Journal of Game Theory_ , 28(4):547–565, 1999a.
  * Grabisch & Roubens (1999b) Michel Grabisch and Marc Roubens.  Probabilistic interactions among players of a cooperative game.  In _Beliefs, Interactions and Preferences in Decision Making_ , pp. 205–216. Springer, 1999b.
  * Harrison & Rubinfeld (1978) David Harrison and Daniel L Rubinfeld.  Hedonic housing prices and the demand for clean air.  _Journal of Environmental Economics and Management_ , 5(1):81–102, 1978.
  * Lundberg & Lee (2017) Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In _Advances in Neural Information Processing Systems_ , pp. 4765–4774, 2017.
  * Malawski (2020) Marcin Malawski.  A note on equal treatment and symmetry of values.  In _Transactions on Computational Collective Intelligence XXXV_ , pp. 76–84. Springer, 2020.
  * Marichal et al. (2007) Jean-Luc Marichal, Ivan Kojadinovic, and Katsushige Fujimoto.  Axiomatic characterizations of generalized values.  _Discrete Applied Mathematics_ , 155(1):26–43, 2007.
  * 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.
  * Pang & Lee (2005) Bo Pang and Lillian Lee.  Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales.  In _Proceedings of the ACL_ , 2005.
  * Patel et al. (2021) Neel Patel, Martin Strobel, and Yair Zick.  High dimensional model explanations: an axiomatic approach.  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , pp. 401–411, 2021.
  * Shapley (1953) Lloyd S. Shapley.  A value for $n$-person games.  In Harold William Kuhn and Albert William Tucker (eds.), _Contributions to the theory of games_ , volume II of _Annals of Mathematical Studies_ , chapter 17, pp. 307–317. Princeton University Press, Princeton, 1953.
  * Štrumbelj & Kononenko (2010) Erik Štrumbelj and Igor Kononenko.  An efficient explanation of individual classifications using game theory.  _The Journal of Machine Learning Research_ , 11:1–18, 2010\.
  * Štrumbelj & Kononenko (2014) Erik Štrumbelj and Igor Kononenko.  Explaining prediction models and individual predictions with feature contributions.  _Knowledge and Information Systems_ , 41(3):647–665, 2014.
  * Williamson & Feng (2020) Brian Williamson and Jean Feng.  Efficient nonparametric statistical inference on population feature importance using Shapley values.  In _International Conference on Machine Learning_ , pp. 10282–10291. PMLR, 2020.

JSY, JAN, JEF, JNU, JLI

In this supplementary material we discuss the arrival order interpretation,
present the proofs of all results, and discuss a notion of joint symmetry
obtained by removing conditions 2 and 3 from JSY.

##  Appendix A Arrival order interpretation

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\in\\{1,2,\ldots\\}$,
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
$\phi^{J}_{T}$ 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 $A_{i}$ the coalition to arrive at time $i$, by $B_{i}$ the
union of all coalitions that have arrived up to time $i$:
$B_{i}=\bigcup_{j\leq i}A_{j}$, and by $p_{T}$ the probability that at some
time coalition $T$ arrives, $p_{T}=\mathbb{P}(\exists\,i:\,B_{i}=T)$. We have
the recursive relationship:

$\displaystyle p_{T}$
$\displaystyle=\sum_{i=1}^{n}\sum_{\begin{subarray}{c}S\subsetneq T:\\\
|S|\geq|T|-k\end{subarray}}\mathbb{P}(B_{i-1}=S)\mathbb{P}(A_{i}=T\setminus
S\mid B_{i-1}=S)$
$\displaystyle=\sum_{i=1}^{n}\sum_{\begin{subarray}{c}S\subsetneq T:\\\
|S|\geq|T|-k\end{subarray}}\mathbb{P}(B_{i-1}=S)\left(\sum_{r=1}^{(n-|S|)\wedge
k}\binom{n-|S|}{r}\right)^{-1}=\sum_{s=(|T|-k)\vee
0}^{|T|-1}\binom{t}{s}p_{S}\left(\sum_{r=1}^{(n-s)\wedge
k}\binom{n-s}{r}\right)^{-1},$

where in the last line $S$ is any set of size $s$. Thus we see that $p_{T}$
only depends on $T$ through its cardinality, and defining

$\hat{p}_{t}:=p_{T}\left(\sum_{r=1}^{(n-t)\wedge k}\binom{n-t}{r}\right)^{-1}$

for any $T$ with $|T|=t$, the expected worth brought by coalition $T$ under
this procedure is

$\sum_{i=1}^{n}\sum_{S\subseteq N\setminus
T}\mathbb{P}(B_{i-1}=S,\,A_{i}=T)[v(S\cup T)-v(S)]=\sum_{S\subseteq N\setminus
T}\hat{p}_{|S|}[v(S\cup T)-v(S)].$

Further, we have the relationship

$\hat{p}_{t}=\frac{\sum_{s=(t-k)\vee
0}^{t-1}\binom{t}{s}p_{s}}{\sum_{r=1}^{(n-t)\wedge k}\binom{n-t}{r}}$

and since we know that $p_{0}=1$ (we start with no agents having arrived) and
$p_{n}=1$ (we finish with all agents having arrived) we also have the
identities:

$\displaystyle 1=\sum_{s=n-k}^{n-1}\binom{n}{s}\hat{p}_{s},\quad
1=\hat{p}_{0}\sum_{r=1}^{k}\binom{n}{s}.$

By comparing with the identities defining $(q_{0},\ldots,q_{n-1})$, we deduce
that $\hat{p}_{t}=q_{t}$ for all $t\in\\{0,\ldots,n-1\\}$, which verifies this
arrival interpretation.

##  Appendix B Proofs

###### Proof of Lemma 2.

For the first statement, for each $\varnothing\neq S\subseteq N\setminus T$
consider the game

$v_{S}(R)=\begin{cases}1&\mbox{if }R=S\mbox{ or }R=S\cup T,\\\
0&\mbox{otherwise}.\end{cases}$

Then for such $S$, by JNU, $\phi_{T}(v_{S})=0$. By this equality, Lemma 1, and
the definition of $v_{S}$,

$0=\phi_{T}(v_{S})=\sum_{R\subseteq N}a^{T}_{R}v_{S}(R)=a_{S}^{T}+a_{S\cup
T}^{T}.$

For the second statement, for each $\varnothing\neq H\subsetneq T$ let
$\alpha_{H}$ be a constant and for $S\subseteq N\setminus T$, consider the
game

$x_{S}^{\bm{\alpha}}(R)=\begin{cases}\alpha_{H}&\mbox{if }R=S\cup H\mbox{ for
some }\varnothing\neq H\subsetneq T,\\\ 0&\mbox{otherwise}.\end{cases}$

By JNU, $\phi_{T}(x_{S}^{\bm{\alpha}})=0$ for every $S\subseteq N\setminus T$.
Thus by Lemma 1

$0=\phi_{T}(x_{S}^{\bm{\alpha}})=\sum_{R\subseteq
N}a_{R}^{T}x_{S}^{\bm{\alpha}}=\sum_{\varnothing\neq H\subsetneq T}a_{S\cup
H}^{T}x_{S}^{\bm{\alpha}}(S\cup H)=\sum_{\varnothing\neq H\subsetneq
T}a_{S\cup H}^{T}\alpha_{H}.$

Since this holds for every choice of constants $\alpha_{H}$, it follows that
$a_{S\cup H}^{T}=0$ for all $S\subseteq N\setminus T$ and $\varnothing\neq
H\subsetneq T$, as required. ∎

###### Proof of Proposition 1.

By Lemma 1 there exist constants $\\{a_{S}^{T}\\}_{S\subseteq
N,\,\varnothing\neq T\subseteq N}$ such that for every $v$ and
$\varnothing\neq T\subseteq N$,

$\displaystyle\phi_{T}(v)$ $\displaystyle=\sum_{S\subseteq
N}a_{S}^{T}v(S)=\sum_{S\subseteq N\setminus
T}\left(a_{S}^{T}v(S)+\sum_{\varnothing\neq H\subsetneq T}a_{S\cup
H}^{T}v(S\cup H)+a_{S\cup T}^{T}v(S\cup T)\right)$
$\displaystyle=\sum_{S\subseteq N\setminus T}(a_{S}^{T}v(S)+a_{S\cup
T}^{T}v(S\cup T))=\sum_{S\subseteq N\setminus T}a_{S\cup T}^{T}[v(S\cup
T)-v(S)];$

where the last two equalities owe to Lemma 2. The proof is complete by setting
$p^{T}(S)=a^{T}_{S\cup T}$. ∎

###### Proof of Proposition 2.

Suppose $\phi$ satisfies axioms JLI, JNU and JEF. Then by Proposition 1 the
constants $\\{p^{T}(S)\\}$ exist, such that for every $v$ and $\varnothing\neq
T\subseteq N$,

$\phi_{T}(v)=\sum_{S\subseteq N\setminus T}p^{T}(S)[v(S\cup T)-v(S)].$

Now for each $\varnothing\neq R\subseteq N$ consider the identity game

$w_{R}(S)=\begin{cases}1&\mbox{if }S=R,\\\ 0&\mbox{otherwise.}\end{cases}$

Then for every $\varnothing\neq T\subseteq N$ with $|T|\leq k$,

$\phi_{T}(w_{R})=\sum_{S\subseteq N\setminus T}p^{T}(S)[w_{R}(S\cup
T)-w_{R}(S)].$

Note that the term $w_{R}(S\cup T)-w_{R}(S)$ in the above sum is equal to 1
only when $S\subsetneq R$ and $T=R\setminus S$, i.e. only when $S=R\setminus
T$ and $\varnothing\neq T\subseteq R$. Further note that this term is equal to
$-1$ only when $S=R$ and $T\neq\varnothing$, i.e. when $S=R$ and
$\varnothing\neq T\subseteq N\setminus R$ (as must have $S\cap
T=\varnothing$). In all other cases, this term is 0. Hence we deduce from JEF
that

$\delta_{N}(R)=w_{R}(N)=\sum_{\begin{subarray}{c}\varnothing\neq T\subseteq
R:\\\ |T|\leq k\end{subarray}}p^{T}(R\setminus
T)-\sum_{\begin{subarray}{c}\varnothing\neq T\subseteq N\setminus R:\\\
|T|\leq k\end{subarray}}p^{T}(R).$

Now we show the implication in the other direction. If
$\phi_{T}(v)=\sum_{S\subseteq N\setminus T}p^{T}(S)[v(S\cup T)-v(S)]$ then it
is immediate that JLI and JNU are satisfied. For JEF, we wish to show that for
every $v$,

$\sum_{\begin{subarray}{c}\varnothing\neq T\subseteq N:\\\ |T|\leq
k\end{subarray}}\sum_{S\subseteq N\setminus T}p^{T}(S)[v(S\cup T)-v(S)]=v(N).$

Note that for each $\varnothing\neq R\subseteq N$, the coefficient of $v(R)$
on the left-hand side in the above equation is

$\sum_{\begin{subarray}{c}\varnothing\neq T\subseteq R:\\\ |T|\leq
k\end{subarray}}p^{T}(R\setminus T)-\sum_{\begin{subarray}{c}\varnothing\neq
T\subseteq N\setminus R:\\\ |T|\leq k\end{subarray}}p^{T}(R).$

But by equation (4), this is equal to $\delta_{N}(R)$. ∎

###### Proof of Proposition 3.

In light of Proposition 2 we just have to consider JAN.

Only if: Suppose $\phi$ satisfies JLI, JNU, JEF and JAN. First, we shall
establish that

$p^{T}\left(S\right)=p^{T}\left(S^{\prime}\right)\,\forall\,\varnothing\neq
T\subseteq N,\,S,S^{\prime}\subseteq N\setminus T\text{ s.t. }s=s^{\prime}.$
(9)

Fix such a $T$, $S$ and $S^{\prime}$. Consider again the identity game,
$w_{S}$ and let $\sigma$ be a self-inverse permutation such that $S\mapsto
S^{\prime}$, $S^{\prime}\mapsto S$, and
$\sigma\left(\left\\{i\right\\}\right)=\left\\{i\right\\}$ for all $i\not\in
S\cup S^{\prime}$. As $T\subseteq N\setminus\left(S\cup S^{\prime}\right)$ and
$\sigma\left(T\right)=T$, we have by JAN

$\phi_{T}\left(w_{S}\right)=\phi_{\sigma^{-1}\left(T\right)}\left(w_{S}\right)=\phi_{T}\left(\sigma
w_{S}\right)$

where

$\displaystyle\sigma
w_{S}\left(R\right)=w_{S}\left(\sigma^{-1}\left(R\right)\right)=\left\\{\begin{array}[]{ll}1&\mbox{if
}R=\sigma\left(S\right)=S^{\prime}\\\
0&\mbox{otherwise}\end{array}\right\\}=w_{S^{\prime}}\left(R\right).$

Hence we obtain $\phi_{T}(w_{S})=\phi_{T}\left(\sigma
w_{S}\right)=\phi_{T}\left(w_{S^{\prime}}\right)$. Next, from Proposition 1 we
have

$\phi_{T}\left(w_{S}\right)=\sum_{Q\subseteq N\setminus
T}p^{T}\left(Q\right)\left[w_{S}\left(Q\cup
T\right)-w_{S}\left(Q\right)\right]=-p^{T}\left(S\right),$

and similarly
$\phi_{T}\left(w_{S^{\prime}}\right)=-p^{T}\left(S^{\prime}\right)$. Hence we
obtain $p^{T}\left(S\right)=p^{T}\left(S^{\prime}\right)$, showing (9).

Using induction on $s$, we now establish that (5) holds. Fix $T$ and
$T^{\prime}$ of the same size. For the base case, suppose $s=s^{\prime}=n-t$.
For $S\subseteq N\setminus T$ and $S^{\prime}\subseteq N\setminus T^{\prime}$,
this forces $S=N\setminus T$ and $S^{\prime}=N\setminus T^{\prime}$. Now
consider the game

$x_{n}\left(R\right)=\begin{cases}1&\mbox{if }r=n\\\
0&\mbox{otherwise,}\end{cases}$

so that $x_{n}\left(R\right)=1$ if and only if $R=N$. Define a self-inverse
permutation $\sigma$ so that $\sigma\left(T\right)=T^{\prime}$,
$\sigma\left(T^{\prime}\right)=T$ and
$\sigma\left(\left\\{i\right\\}\right)=\left\\{i\right\\}$ for all
$i\not\in\left(T\cup T^{\prime}\right)$. Then by JAN and as $\sigma
x_{n}=x_{n}$,

$\phi_{T}(x_{n})=\phi_{\sigma^{-1}(T^{\prime})}(x_{n})=\phi_{T^{\prime}}(\sigma
x_{n})=\phi_{T^{\prime}}(x_{n}).$

Next, from Proposition 1,

$\phi_{T}\left(x_{n}\right)=\sum_{Q\subseteq N\setminus
T}p^{T}\left(Q\right)\left[x_{n}\left(T\cup
Q\right)-x_{n}\left(Q\right)\right]=p^{T}\left(N\setminus T\right),$

and similarly
$\phi_{T^{\prime}}\left(w_{n}\right)=p^{T^{\prime}}\left(N\setminus
T^{\prime}\right)$. Hence we obtain $p^{T}\left(N\setminus
T\right)=p^{T^{\prime}}\left(N\setminus T^{\prime}\right)$ which establishes
the base case.

We now suppose that
$p^{T}\left(S\right)=p^{T^{\prime}}\left(S^{\prime}\right)$ for all
$s=s^{\prime}\geq n-c$ where $S\subseteq N\setminus T$, $S^{\prime}\subseteq
N\setminus T^{\prime}$ and $c$ is a positive integer. We shall show that
$p^{T}\left(S\right)=p^{T^{\prime}}\left(S^{\prime}\right)$ for all
$s=s^{\prime}\geq n-c-1$ where where $S\subseteq N\setminus T$ and
$S^{\prime}\subseteq N\setminus T^{\prime}$. To this end, consider the game

$x\left(R\right)=\begin{cases}1&\mbox{if }r\geq n-c-1+t,\\\
0&\mbox{otherwise}\end{cases}.$

Thus, as before, we may write

$\phi_{T}\left(x\right)=\sum_{Q\subseteq N\setminus
T}p^{T}\left(Q\right)\left[x\left(Q\cup
T\right)-x\left(Q\right)\right]=\sum_{\begin{subarray}{c}Q\subseteq N\setminus
T\\\ n-c-1\leq q<n-c-1+t\end{subarray}}p^{T}\left(Q\right).$

Similarly,

$\phi_{T^{\prime}}\left(x\right)=\sum_{\begin{subarray}{c}Q^{\prime}\subseteq
N\setminus T^{\prime}\\\ n-c-1\leq
q^{\prime}<n-c-1+t\end{subarray}}p^{T}\left(Q\right).$

Again, by JAN, we prove that
$\phi_{T}\left(x\right)=\phi_{T^{\prime}}\left(x\right)$. Define a self-
inverse permutation $\sigma$ so that $\sigma\left(T\right)=T^{\prime}$,
$\sigma\left(T^{\prime}\right)=T$ and
$\sigma\left(\left\\{i\right\\}\right)=\left\\{i\right\\}$ for all
$i\not\in\left(T\cup T^{\prime}\right)$. As worth in game $x$ depends only on
a coalition’s cardinality, we have $\sigma x=x$. Thus, by JAN,
$\phi_{T}(x)=\phi_{\sigma(T)}(\sigma
x)=\phi_{\sigma(T)}(x)=\phi_{T^{\prime}}(x)$.

However,

$\phi_{T}\left(x\right)=\sum_{\begin{subarray}{c}Q\subseteq N\setminus T\\\
q=n-c-1\end{subarray}}p^{T}\left(Q\right)+\sum_{\begin{subarray}{c}Q\subseteq
N\setminus T\\\
n-c-1<q<n-c-1+t\end{subarray}}p^{T}\left(Q\right)=\sum_{\begin{subarray}{c}Q\subseteq
N\setminus T\\\
q=n-c-1\end{subarray}}p^{T}\left(Q\right)+\sum_{\begin{subarray}{c}Q^{\prime}\subseteq
N\setminus T^{\prime}\\\
n-c-1<q^{\prime}<n-c-1+t\end{subarray}}p^{T^{\prime}}\left(Q^{\prime}\right);$

and

$\phi_{T^{\prime}}\left(x\right)=\sum_{\begin{subarray}{c}Q^{\prime}\subseteq
N\setminus T^{\prime}\\\
q^{\prime}=n-c-1\end{subarray}}p^{T^{\prime}}\left(Q^{\prime}\right)+\sum_{\begin{subarray}{c}Q^{\prime}\subseteq
N\setminus T^{\prime}\\\
n-c-1<q^{\prime}<n-c-1+t\end{subarray}}p^{T^{\prime}}\left(Q^{\prime}\right)$

which gives, by the inductive hypothesis and
$\phi_{T}(x)=\phi_{T^{\prime}}(x)$,

$\sum_{\begin{subarray}{c}Q\subseteq N\setminus T\\\
q=n-c-1\end{subarray}}p^{T}\left(Q\right)=\sum_{\begin{subarray}{c}Q^{\prime}\subseteq
N\setminus T^{\prime}\\\
q^{\prime}=n-c-1\end{subarray}}p^{T^{\prime}}\left(Q^{\prime}\right).$

But by (9), $p^{T}\left(Q\right)=p^{T}\left(Q^{\prime}\right)$ if
$q=q^{\prime}$. Thus the above equation becomes

$\binom{n-t}{n-c-1}p^{T}\left(Q\right)=\binom{n-t}{n-c-1}p^{T^{\prime}}\left(Q^{\prime}\right)$

for any $Q\subseteq N\setminus T$ and $Q^{\prime}\subseteq N\setminus
T^{\prime}$ with $q=q^{\prime}=n-c-1$. Thus,
$p^{T}\left(Q\right)=p^{T^{\prime}}\left(Q^{\prime}\right)$, completing the
inductive step, and the ‘only if’ statement.

If: Suppose (5) is satisfied. Fix a permutation $\sigma$ on $N$ and game
$v\in\mathcal{G}^{N}$. Then for any $\varnothing\neq T\subseteq N$,

$\displaystyle\phi_{T}\left(\sigma v\right)$ $\displaystyle=\sum_{S\subseteq
N\backslash T}p^{T}\left(S\right)\left[\sigma v\left(S\cup T\right)-\sigma
v\left(S\right)\right]=\sum_{S\subseteq N\backslash
T}p^{T}\left(S\right)\left[v\left(\sigma^{-1}\left(S\cup
T\right)\right)-v\left(\sigma^{-1}\left(S\right)\right)\right]$
$\displaystyle=\sum_{S\subseteq N\backslash
T}p^{T}\left(S\right)\left[v\left(\sigma^{-1}\left(S\right)\cup\sigma^{-1}\left(T\right)\right)-v\left(\sigma^{-1}\left(S\right)\right)\right].$

Defining the set $S^{\prime}=\sigma^{-1}\left(S\right)$ allows us to rewrite
the above as

$\displaystyle\phi_{T}\left(\sigma v\right)$
$\displaystyle=\cdots=\sum_{S^{\prime}\subseteq
N\backslash\sigma^{-1}\left(T\right)}p^{T}\left(\sigma\left(S^{\prime}\right)\right)\left[v\left(S^{\prime}\cup\sigma^{-1}\left(T\right)\right)-v\left(S^{\prime}\right)\right]$
$\displaystyle=\sum_{S^{\prime}\subseteq
N\backslash\sigma^{-1}\left(T\right)}p^{\sigma^{-1}\left(T\right)}\left(S^{\prime}\right)\left[v\left(S^{\prime}\cup\sigma^{-1}\left(T\right)\right)-v\left(S^{\prime}\right)\right]=\phi_{\sigma^{-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 $\phi$ satisfies JLI, JNU, JEF and JSY, fix $\varnothing\neq
T,T^{\prime}\subseteq N$, and consider again the identity game $w_{R}$. Then
for any $\varnothing\neq R\subseteq N\setminus(T\cup T^{\prime})$,

  * •

$w_{R}(S\cup T)=0=w_{R}(S\cup T^{\prime})$ for all $S\subseteq
N\setminus(T\cup T^{\prime})$,

  * •

$w_{R}(S\cup T)=0=w_{R}(S)$ for all $S\subseteq N\setminus T$ such that $S\cap
T^{\prime}\neq\varnothing$,

  * •

$w_{R}(S\cup T^{\prime})=0=w_{R}(S)$ for all $S\subseteq N\setminus
T^{\prime}$ such that $S\cap T\neq\varnothing$.

Hence by JSY $\phi_{T}(w_{R})=\phi_{T^{\prime}}(w_{R})$. But
$\phi_{T}(w_{R})=p^{T}(R)$ and $\phi_{T^{\prime}}(w_{R})=p^{T}(R)$. This shows
that $p^{T}(R)=p^{T^{\prime}}(R)$ for all $\varnothing\neq R\subseteq
N\setminus(T\cup T^{\prime})$. To show that
$p^{T}(\varnothing)=p^{T^{\prime}}(\varnothing)$ we consider the game

$w^{*}(S)=\begin{cases}1&\mbox{if }S\neq\varnothing,\\\
0&\mbox{otherwise.}\end{cases}$

Then

  * •

$w^{*}(S\cup T)=1=w^{*}(S\cup T^{\prime})$ for all $S\subseteq
N\setminus(T\cup T^{\prime})$,

  * •

$w^{*}(S\cup T)=1=w^{*}(S)$ for all $S\subseteq N\setminus T$ such that $S\cap
T^{\prime}\neq\varnothing$ (since then $S\neq\varnothing$),

  * •

$w^{*}(S\cup T^{\prime})=1=w^{*}(S)$ for all $S\subseteq N\setminus
T^{\prime}$ such that $S\cap T\neq\varnothing$ (since then
$S\neq\varnothing$).

It thus follows by JSY that $\phi_{T}(w^{*})=\phi_{T^{\prime}}(w^{*})$.
However, $\phi_{T}(w^{*})=p^{T}(\varnothing)$ and
$\phi_{T^{\prime}}(w^{*})=p^{T^{\prime}}(\varnothing)$, 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\in\mathcal{G}^{N}$ satisfies the three conditions in JSY. Then

$\displaystyle\phi_{T}(v)$ $\displaystyle=\sum_{S\subseteq N\setminus
T}p^{T}(S)[v(S\cup T)-v(S)]=\sum_{S\subseteq N\setminus(T\cup
T^{\prime})}p^{T}(S)[v(S\cup T)-v(S)]$ $\displaystyle=\sum_{S\subseteq
N\setminus(T\cup T^{\prime})}p^{T^{\prime}}(S)[v(S\cup
T^{\prime})-v(S)]=\sum_{S\subseteq N\setminus
T^{\prime}}p^{T^{\prime}}(S)[v(S\cup T^{\prime})-v(S)]=\phi_{T^{\prime}}(v).$

Hence JSY is satisfied. ∎

###### Proof of Theorem 1.

We have to show that there exists exactly one choice of constants
$\\{p^{T}(S)\\}$ which satisfy equations (4)–(6). Notice that satisfying (5)
and (6) is equivalent to satisfying

$p^{T}(S)=p^{T^{\prime}}(S)\,\forall\,S\subseteq N\setminus
T,\,S^{\prime}\subseteq N\setminus T^{\prime}\,\text{ s.t. }\,s=s^{\prime}.$

Thus $p^{T}(S)$ does not depend on $T$ at all, and only depends on the
cardinality of $S$. Let $q_{s}$ denote $p^{T}(S)$ for any $S\subseteq
N\setminus T$. Then we can re-write equation (4) in terms of $q_{s}$ as

$\displaystyle 1$ $\displaystyle=\sum_{i=n-k}^{n-1}\binom{n}{i}q_{i},$ (10)
$\displaystyle q_{s}$ $\displaystyle=\frac{\sum_{i=(s-k)\vee
0}^{s-1}\binom{s}{i}q_{i}}{\sum_{i=1}^{k\wedge(n-s)}\binom{n-s}{i}}\quad\forall\,s\in\\{1,\ldots,n-1\\}.$
(11)

Note that for any $q_{0}$, equation (11) fully determines all other $q_{i}$,
for $i\in\\{1,\ldots,n-1\\}$ and $q_{0}$ 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 $(q_{0},\ldots,q_{n-1})=(\hat{p}_{0},\ldots,\hat{p}_{n-1})$, for
which $\hat{p}_{0}=\left(\sum_{i=1}^{k}\binom{n}{i}\right)^{-1}$. ∎

##  Appendix C Strong joint symmetry

JSY, JAN, JEF, JNU, JLIWe 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 $\varnothing\neq T,T^{\prime}\subseteq N$. Then

$\displaystyle v\left(S\cup T\right)=v\left(S\cup T^{\prime}\right)\forall
S\subseteq N\backslash\left(T\cup T^{\prime}\right)$
$\displaystyle\Rightarrow\phi_{T}\left(v\right)=\phi_{T^{\prime}}\left(v\right).$

######  Proposition 5.

There is no index $\phi$ satisfying axioms JLI, JNU, JEF, and SJS that is
guaranteed to exist for all games.

###### Proof.

Since $\phi$ satisfies JLI, JNU, and JEF, by Proposition 2,

$\phi_{T}(v)=\sum_{S\subseteq N\setminus T}p^{T}(S)[v(S\cup T)-v(S)]$

with $\\{p^{T}(S)\\}$ satisfying (4), for any game $v\in\mathcal{G}^{N}$. We
consider two games $v_{1},v_{2}\in\mathcal{G}^{\\{1,2\\}}$. As $N=\\{1,2\\}$,
(4) gives $p^{\\{1\\}}(\varnothing)=p^{\\{2\\}}(\\{1\\})$,
$p^{\\{2\\}}(\varnothing)=p^{\\{1\\}}(\\{2\\})$, and
$p^{\\{1,2\\}}(\varnothing)+p^{\\{1\\}}(\varnothing)+p^{\\{2\\}}(\varnothing)=1$.

Suppose $v_{1}(\\{1\\})=v_{1}(\\{1,2\\})=1$, $v_{1}(\\{2\\})=0$. SJS thus
gives that $\phi_{\\{1\\}}(v_{1})=\phi_{\\{1,2\\}}(v_{1})$, i.e.
$p^{\\{1,2\\}}(\varnothing)=p^{\\{1\\}}(\varnothing)+p^{\\{2\\}}(\varnothing)$
which implies $p^{\\{1,2\\}}(\varnothing)=1/2$.

Suppose also that $v_{2}(\\{1\\})=v_{2}(\\{1,2\\})=v_{2}(\\{2\\})=1$. SJS
gives that
$\phi_{\\{1\\}}(v_{2})=\phi_{\\{2\\}}(v_{2})=\phi_{\\{1,2\\}}(v_{2})$, i.e.
$p^{\\{1,2\\}}(\varnothing)=p^{\\{1\\}}(\varnothing)=p^{\\{2\\}}(\varnothing)$
which implies $p^{\\{1,2\\}}(\varnothing)=1/3$, giving a contradiction.∎

Thus, SJS is too strong a notion of symmetry, imposing linear restrictions on
sets of unequal sizes.