# On the Convergence of the Shapley Value in
Parametric Bayesian Learning Games

Lucas Agussurja  Xinyi Xu  Bryan Kian Hsiang Low

###### Abstract

Measuring contributions is a classical problem in cooperative game theory
where the Shapley value is the most well-known solution concept. In this
paper, we establish the convergence property of the Shapley value in
parametric Bayesian learning games where players perform a Bayesian inference
using their combined data, and the posterior-prior KL divergence is used as
the characteristic function. We show that for any two players, under some
regularity conditions, their difference in Shapley value converges in
probability to the difference in Shapley value of a limiting game whose
characteristic function is proportional to the log-determinant of the joint
Fisher information. As an application, we present an online collaborative
learning framework that is asymptotically Shapley-fair. Our result enables
this to be achieved without any costly computations of posterior-prior KL
divergences. Only a consistent estimator of the Fisher information is needed.
The effectiveness of our framework is demonstrated with experiments using
real-world data.

Bayesian learning, Shapley value, Finite sample convergence

##  1 Introduction

Recent significant increase in computing power has enabled the training of
high-capacity machine learning models (e.g., deep neural networks) which
results in an unprecedented level of performances in many domains. A key
ingredient of this success is the huge quantity of data that is used to train
these models. Going forward, as models and tasks grow in complexity, the
demand for more data will only rise in intensity and it will become necessary
to utilize data from multiple sources and across different organizations. A
benefit of data sharing is the ability to achieve a higher convergence rate.
It has been shown that when collaboration is possible, an exponential
improvement can be achieved in terms of sample complexity (Blum et al., 2017;
Chen et al., 2018; Nguyen & Zakynthinou, 2018).

When learning is done using datasets from multiple sources, a natural question
arises: _What are the relative contributions of individual datasets to the
resulting model?_ As examples, consider the following two scenarios: (a) In a
hospital, a new study is to be conducted on the general population and
datasets are collected from multiple clinics within the hospital. The datasets
contain bias due to the specializations of the clinics. Datasets from
pediatricians, for example, will contain data for patients under $12$ years
old, while datasets from rheumatologists will be gender-biased since women are
(biologically) more likely to develop rheumatoid-type conditions. It is
therefore important to know the influences that these datasets have on the
outcome. (b) A group of companies have decided to jointly develop a machine
learning application by pooling their data together. The application will then
be provided as a service to customers (e.g., on a pay-per-query basis). After
deployment, the group is then faced with the problem of distributing the
generated revenue from the application. Though resolving these problems
involves a number of non-technical (e.g., social and business) considerations,
a quantitative measure of the datasets’ contributions to the learning outcome
would be crucial.

The problem of attribution (cost/profit sharing) is a classical problem in
cooperative game theory and the two most well-known solution concepts are the
Shapley (Shapley, 1953) and Banzhaf (Banzhaf, 1965) values. Both concepts are
based on the marginal contribution, i.e., the increase in a coalition’s value
when a player joins it. These values of coalitions are given by the
characteristic (valuation) function which maps each given coalition to a real
number. Both the Shapley and Banzhaf values quantify a player’s contribution
with a weighted sum of its marginal contributions to all possible coalitions,
but they differ in the weights used. What makes the Shapley value appealing is
its uniqueness in satisfying the desirable properties of symmetry, null
player, linearity, and efficiency simultaneously. The first two properties are
often used as criteria for fairness. The Banzhaf value satisfies these
properties except efficiency.

The use of Shapley value has gained traction in the machine learning community
(Sim et al., 2020, 2022; Tay et al., 2022; Wu et al., 2022; Xu et al., 2021a,
b). Applications that are related to the present work include quantifying the
importance of features (Covert et al., 2020; Lundberg & Lee, 2017) and sets of
training data (Ghorbani & Zou, 2019). In these works, the characteristic
function is defined as the performance of the trained models on some test set.
However, the use of a test set can be infeasible. Consider the cases when the
players’ data, albeit can be explained by the same underlying hypothesis, may
not come from the same sample space or may be generative in nature. In these
cases, a Bayesian approach is a better fit. Instead of agreeing on a common
test set, the players agree on a common prior. Joint Bayesian inferences are
then performed and the value of a coalition is the information gain of their
joint posterior from the prior. To our knowledge, the use and analysis of the
Shapley value in this setting is still unexplored. So, the first contribution
of our work here is to bridge this gap.

Specifically, we study the asymptotic properties of the Shapley/Banzhaf value
in parametric Bayesian learning games. In these games, players come together
to perform Bayesian inference using their combined datasets. We assume that
there is a true hypothesis (parameter) and a player’s dataset is generated
from a distribution that is indexed by the true parameter. In this work, the
players’ distributions need not be the same. Given a commonly agreed prior,
the characteristic function is defined as the posterior-prior KL divergence.
In our main result, we show that as the size of datasets tends to infinity,
the difference in Shapley value converges in probability to the difference in
Shapley value of a limiting game whose characteristic function is proportional
to the log-determinant of the joint Fisher information. Fisher information is
classically interpreted as a measure of information that a dataset carries
about the underlying hypothesis. However, supposing one wants to use it as the
characteristic function, it is unclear what the suitable statistic is.
Providing this link is the second contribution of this work.

As the third contribution, we present a $2$-player online collaborative
learning framework that is asymptotically Shapley-fair. The key idea
underlying our framework is to vary the rates at which players’ data are
received such that the determinants of their Fisher information are the same
in the limit. Applying the main result, we show that the difference in Shapley
value converges in probability to zero. We empirically verify this on real-
world data for Bayesian linear regression and mean estimation in a learned
latent space. Moreover, we extend our framework to multiple players and
empirically show that the convergence can also be achieved approximately with
more than $2$ players.

##  2 Parametric Bayesian Learning Game

In this section, we will define a parametric Bayesian learning game and state
the assumptions A1 to A4 on the players’ data generation model. We will first
describe the players’ data generation model. In this work, we assume that
there is a true parameter (hypothesis) $\theta^{*}$ that all the players are
interested in finding. In the parametric setting, $\theta^{*}$ lies in the
parameter space $\Theta$ which is a subset of the $k$-dimensional Euclidean
space. Each player $i$ is associated with a family of distributions
$\\{F_{i,\theta}\\}_{\theta\in\Theta}$ and observes the random variables

$\textbf{X}_{i}^{m}:=(\textbf{X}_{i1},\dots,\textbf{X}_{im})\quad\text{where}\quad\textbf{X}_{i1},\dots,\textbf{X}_{im}\overset{\text{i.i.d.}}{\sim}F_{i,\theta^{*}}$

and $m$ denotes the number of data points. We will now state the first three
assumptions with regard to the players’ data generation model.

(A1) The density of $F_{i,\theta}$ is twice differentiable in $\theta$.

(A2) Besides the independence of a player’s data points, the random variables
$\textbf{Y}_{i,\theta}\sim F_{i,\theta}$ of player $i$ and
$\textbf{Y}_{j,\theta}\sim F_{j,\theta}$ of player $j$ are conditionally
independent given $\theta\in\Theta$.

The third assumption states that the data generated from the true parameter
can be distinguished from the ones generated from any other parameter. This is
a common assumption in statistical analysis to guarantee the existence of a
consistent estimator (e.g., maximum likelihood estimator). If the assumption
is violated, then there exists another parameter $\theta\in\Theta$ that is
observationally equivalent to $\theta^{*}$. Consequently, no algorithm will be
able to distinguish between the two, even with an infinite quantity of data.
Sometimes, the stronger assumption of identifiability is given, i.e.,
$F_{i,\theta}\neq F_{i,\theta^{\prime}}$ (w.r.t. a probability metric)
whenever $\theta\neq\theta^{\prime}$. Identifiability implies the following
weaker condition:

(A3) Let $\textbf{Y}_{i,\theta}^{m}$ denote a sample (of size $m$) drawn
independently from $F_{i,\theta}$. For each player $i$, there exists an
algorithm (or, in statistical term, a test) $D_{i,\theta^{*}}$ that accepts
$\textbf{Y}_{i,\theta}^{m}$ and $\varepsilon$ as inputs and outputs $0$ or $1$
s.t. for any $\varepsilon>0$,

$\mathbb{E}\left[D_{i,\theta^{*}}(\textbf{X}_{i}^{m},\varepsilon)\right]\longrightarrow
0\quad\quad\textnormal{and}$
$\begin{array}[]{c}\sup_{\theta:\|\theta-\theta^{*}\|\geq\varepsilon}\mathbb{E}\left[1-D_{i,\theta^{*}}(\textbf{Y}_{i,\theta}^{m},\varepsilon)\right]\longrightarrow
0\ .\end{array}$

An algorithm $D_{i,\theta^{*}}$ with the above property is called a uniformly
consistent distinguisher.

$\theta^{*}$$\bm{A}$$\bm{B}$$\bm{C}$$\sigma$$\bm{E}$$\bm{F}$$m$$m$$m$player
1player 2player 3

(a) An example of a data generation model

(b) Convergence of the differences in Shapley value

Figure 1: An illustrative example of a $3$-player parametric Bayesian learning
game.

As an example, consider the graphical model shown in Fig. 1(a) for three
players. In the model, each player observes a disjoint subset of the
observable random variables. Each subset depends on the hidden variable
$\theta^{*}$ which is the parameter of interest. The other hidden variable
$\sigma$ affects only player $3$. As an illustration, $\theta^{*}$ may
represent, say, the fraction of a population infected in an epidemic and the
three subsets represent different test results (e.g., CT scans, swabs with
varying accuracies) performed independently on random samples. In our example,
$\theta^{*}$ is a vector of four real numbers. Player $1$’s data is a linear
model (weighted by $\theta^{*}$) with known noise, player $2$’s data are noisy
observations of $\theta^{*}$, and player $3$’ data is a linear model with
unknown noise parameter $\sigma$. Note that a player’s data may depend on
unknowns other than $\theta^{*}$ although we are interested only in the
marginal posterior w.r.t. $\theta^{*}$.

Next, we will describe how to perform joint inference. A coalition $S$ is a
subset of players who may decide to cooperate to perform inference using their
combined data points. With a slight abuse of notations,
$\textbf{X}_{S}^{m}:=(\textbf{X}_{i}^{m})_{i\in S}$ and $\textbf{X}^{m}$
denote the combined data points of players in $S$ and that of all the players
in the grand coalition, respectively. Bayesian inference is then performed
using the joint likelihood $\mathcal{L}_{S}(\cdot;\textbf{X}_{S}^{m})$ and a
commonly agreed prior $\Pi$ whose density is denoted by $\pi$. Then, the joint
posterior $\bm{P}_{S}^{m}$ is of the density

$\begin{array}[]{rl}\bm{p}_{S}^{m}(\theta)=&\displaystyle\frac{\mathcal{L}_{S}(\theta;\textbf{X}_{S}^{m})\
\pi(\theta)}{\displaystyle{\int_{\theta^{\prime}\in\Theta}\mathcal{L}_{S}(\theta^{\prime};\textbf{X}_{S}^{m})\
\text{d}\Pi(\theta^{\prime})}}\ ,\vspace{1mm}\\\
\mathcal{L}_{S}(\theta;\textbf{X}_{S}^{m})=&\textstyle\prod_{i\in
S}\mathcal{L}_{i}(\theta;\textbf{X}_{i}^{m})\end{array}$

s.t. the second equality is due to assumption A2. Note that both the
likelihood and the posterior density are random functions whose values depend
on the realizations of $\textbf{X}_{S}^{m}$. This is also the case for the
characteristic function and the Shapley/Banzhaf value defined below. The prior
$\Pi$ is assumed to have the following properties:

(A4) The prior probability measure has a compact support, is absolutely
continuous around a neighborhood of $\theta^{*}$, and has a positive
continuous density at $\theta^{*}$.

We will now define the characteristic function $\bm{\mathcal{V}}^{m}$ of the
game. Since the function measures the value of a coalition, a natural
candidate therefore is to use the information gain on the true parameter via
the standard KL divergence of the joint posterior from the common prior:

$\bm{\mathcal{V}}^{m}(S):=\textnormal{KL}(\bm{P}_{S}^{m}\|\Pi):=\int_{\Theta}\log\left({\text{d}\bm{P}_{S}^{m}}/{\text{d}\Pi}\right)\text{d}\bm{P}_{S}^{m}$
(1)

which is the expectation (w.r.t. the posterior) of the log of the Radon-
Nikodym derivative of the posterior over the prior. In order for the
divergence to be well-defined, $\bm{P}_{S}^{m}$ has to be absolutely
continuous w.r.t. $\Pi$. This is always satisfied since in Bayesian inference,
any set with zero prior measure will also have zero posterior measure. By
definition, the value of the empty coalition is zero. Since a cooperative game
is completely defined by its characteristic function, we will use the two
terms interchangeably.

As mentioned previously, in cooperative game theory, the two most commonly
used measures of contributions are the Shapley and Banzhaf values. Both values
are defined as a weighted sum of a player’s marginal contributions to all
possible coalitions of other players, albeit with different weights. That is,
for each player $i$, both values have the form

$\textstyle\phi(i;\bm{\mathcal{V}}^{m}):=\sum_{S\subseteq
N\setminus\\{i\\}}w_{S}\left[\bm{\mathcal{V}}^{m}(S\cup\\{i\\})-\bm{\mathcal{V}}^{m}(S)\right]$

where $N$ is the grand coalition and the weights $w_{S}$ (associated with
coalition $S$) for the Shapley and Banzhaf values are, respectively,

$|S|!(|N|-|S|-1)!/|N|!\quad\text{and}\quad{1}/{2^{|N|-1}}\ .$

The linearity/additivity property holds for both values and is central to
deriving the main result of this paper: Let $V$ be a cooperative game. If $V$
can be decomposed additively (i.e., $V=V_{1}+\ldots+V_{n}$), then
$\phi(i;V)=\phi(i;V_{1})+\ldots+\phi(i,V_{n})$.

##  3 Convergence Results

The convergence results are divided into three parts: (a) w.r.t. the joint
posteriors, (b) the characteristic function, and (c) the Shapley/Banzhaf
value. For each result, we give its interpretation and the idea of its proof
in the main paper; their full proofs are in Appendix A. We start with a result
on the convergence of the joint posterior $\bm{P}_{S}^{m}$ for any nonempty
coalition $S$, which generalizes the Bernstein-von Mises theorem to that of
joint Bayesian inference. The proof therefore involves checking that the
required conditions still hold for the joint inference; see the works of Cam &
Yang (2000); van der Vaart (1998) for a complete proof of the Bernstein-von
Mises theorem.

######  Theorem 1 (Bernstein-von Mises).

If the regularity conditions A1 to A4 hold, then for any nonempty coalition
$S$,

$\left\lVert\bm{P}_{S}^{m}-\mathcal{N}\left(\bm{\hat{\theta}}^{m}_{S},{m}^{-1}\mathcal{I}^{-1}_{S}\right)\right\rVert_{\textnormal{TV}}\overset{\textnormal{p}}{\longrightarrow}0$

where $\bm{\hat{\theta}}_{S}^{m}$ is the maximum likelihood estimate w.r.t.
the joint likelihood $\mathcal{L}_{S}(\,\cdot\,;\textnormal{{X}}_{S}^{m})$,
$\mathcal{I}_{S}$ is the Fisher information w.r.t. the same likelihood, and
$\lVert\cdot\rVert_{\textnormal{TV}}$ is the total variation distance.

Recall that the Fisher information $\mathcal{I}_{S}$ is the expected value of
the squared gradient of the log-likelihood
$\log\mathcal{L}_{S}(\cdot;\textbf{X}_{S}^{m})$ and is thus a function of
$\theta$. In this work, the Fisher information is always taken to be at the
true parameter $\theta^{*}$:

$\mathcal{I}_{S}:=\mathbb{E}\\!\left[\\!\left(\frac{\partial}{\partial\theta}\log\mathcal{L}_{S}(\theta^{*};\textbf{X}_{S}^{1})\right)\\!\\!\left(\frac{\partial}{\partial\theta}\log\mathcal{L}_{S}(\theta^{*};\textbf{X}_{S}^{1})\right)^{\top}\right]$

which is not a random variable and does not depend on $m$ since the
expectation is w.r.t. a single data point from each player in $S$. However, it
depends on $S$ since different coalitions have different joint likelihoods.
Since the expectation of the gradient is zero at $\theta^{*}$, the Fisher
information is also the variance of the gradient of the log-likelihood at
$\theta^{*}$. If the Fisher information is large, then the log-likelihood is
steep around $\theta^{*}$ and hence makes it easy to identify $\theta^{*}$,
and vice versa. This is why Fisher information can be interpreted as a measure
of information that a random variable contains about the underlying true
parameter. Note also that it is a positive semidefinite matrix.

Theorem 1 states that the joint posterior $\bm{P}_{S}^{m}$ can be approximated
by the distribution

$\bm{\hat{P}}_{S}^{m}:=\mathcal{N}\left(\bm{\hat{\theta}}_{S}^{m},{m}^{-1}\mathcal{I}_{S}^{-1}\right)$
(2)

s.t. the accuracy improves with an increasing $m$. Furthermore, since
$\bm{\hat{\theta}}_{S}^{m}\overset{\textnormal{p}}{\longrightarrow}\theta^{*}$
under conditions A1 to A3, $\bm{\hat{P}}_{S}^{m}$ (and thus $\bm{P}_{S}^{m}$)
converges to the degenerate normal distribution that assigns an infinite
density to the true parameter. The KL divergence (i.e., characteristic
function (1)) therefore goes to infinity for any nonempty coalition. This, in
turn, causes the Shapley value of any player to go to infinity.

We will now describe the convergence result w.r.t. the characteristic
function. The idea is to approximate the value of $\bm{\mathcal{V}}^{m}(S)$ by
the KL divergence of the approximated joint posterior from the prior. In
general, however, the approximation (a normal distribution) is not absolutely
continuous w.r.t. the prior, so the divergence may not be well-defined. We
will instead use an extended version of the KL divergence defined as follows:
Let $P$ and $R$ be two probability measures defined on a measurable space
$(\mathcal{X},\Omega)$. Then, the _extended KL divergence_ of $P$ from $R$ is
defined as

$\textnormal{KL}^{+}(P\|R):=\int_{\mathcal{X}}\log\left({\text{d}P|_{R}}/{\text{d}R}\right)\text{d}P|_{R}$

where $P|_{R}$ is the absolutely continuous component of the Lebesgue’s
decomposition of $P$ w.r.t. $R$. Note that the measure $P|_{R}$ is not
necessarily probabilistic, i.e., $P|_{R}(\mathcal{X})$ need not be one.
Informally, instead of taking the integral over the whole support of $P$, only
the parts that intersect with the support of $R$ are used. Using the extended
KL divergence, we can now state the next result:

######  Lemma 1.

Let $\bm{\mathcal{V}}^{m}$ be a parametric Bayesian learning game. Under
regularity conditions A1 to A4, for any nonempty $S$,

$\Bigl{|}\,\bm{\mathcal{V}}^{m}(S)-\textnormal{KL}^{+}(\bm{\hat{P}}^{m}_{S}\|\Pi)\,\Bigr{|}\overset{\textnormal{p}}{\longrightarrow}0$

where $\bm{\hat{P}}^{m}_{S}$ is previously defined in (2).

Before proceeding, we will first show how this seemingly obvious result may
not be trivial to prove. Suppose that for now, in place of KL divergence, we
use the Hellinger distance $h$ instead. The reason for this choice is that it
satisfies the triangle inequality and is upper bounded by the total variation
distance. So, for every $m$,

$\begin{array}[]{lcl}\left|h(\bm{P}^{m}_{S},\Pi)-h(\bm{\hat{P}}^{m}_{S},\Pi)\right|&\leq&h(\bm{P}^{m}_{S},\bm{\hat{P}}^{m}_{S})\\\
&\leq&\left\lVert\bm{P}^{m}_{S}-\bm{\hat{P}}^{m}_{S}\right\rVert^{1/2}_{\textnormal{TV}}\
.\end{array}$

It follows that for any $\varepsilon>0$,

$\begin{array}[]{l}\Pr\left[\left|h(\bm{P}^{m}_{S},\Pi)-h(\bm{\hat{P}}^{m}_{S},\Pi)\right|>\varepsilon\right]\vspace{0.5mm}\\\
\leq\Pr\left[\left\lVert\bm{P}^{m}_{S}-\bm{\hat{P}}^{m}_{S}\right\rVert_{\textnormal{TV}}>\varepsilon^{2}\right],\end{array}$

which establishes the required convergence in terms of the convergence in
total variation distance. Since the latter is true given Theorem 1, so is the
former. On the other hand, the KL divergence neither satisfies the triangle
inequality nor is upper bounded by the total variation distance. Instead, we
use a triangle-like inequality which establishes its convergence in terms of
the convergence in total variation distance, the difference in entropy, and a
residual term. The latter two are then shown to converge in probability to
zero.

The above result allows us to obtain a closed-form approximation of
$\bm{\mathcal{V}}^{m}(S)$ for specific priors by analyzing the extended KL
divergence. If the latter converges in probability to some fixed function,
then so is the former. Next, we present such results for both uniform and
normal priors:

######  Corollary 1.

Let $\bm{\mathcal{V}}^{m}$ be a parametric Bayesian learning game s.t. the
regularity conditions A1 to A4 hold. If the commonly agreed prior is a uniform
distribution $U$ with support $\Theta_{U}\subseteq\Theta$, then for any
nonempty $S$,

$\left|\bm{\mathcal{V}}^{m}(S)-\left(\frac{k}{2}\log\left(\frac{m}{2\pi
e}\right)+\log\lambda(\Theta_{U})+\frac{1}{2}\log|\mathcal{I}_{S}|\right)\right|$

converges in probability to $0$ w.r.t. Lebesgue measure $\lambda$.

In condition A4, we assume that the support of the prior is compact, but this
is not the case for a normal distribution. However, in practice, the
difference between a truncated normal with a large support (centered at the
mean) and the standard version is negligible. For clarity of presentation, we
state the result informally using the standard normal instead of formally with
a truncated one: Let $\bm{\mathcal{V}}^{m}$ be a parametric Bayesian learning
game s.t. the regularity conditions A1 to A4 hold. If the commonly agreed
prior is a normal distribution $\mathcal{N}(\theta_{0},\Sigma_{0})$, then for
any nonempty $S$,

$\bm{\mathcal{V}}^{m}(S)\approx 0.5\ k\log m+\xi+0.5\log|\mathcal{I}_{S}|$

for a large $m$ where
$\xi:=0.5\left(\left\|\theta_{0}-\theta^{*}\right\|^{2}_{\Sigma_{0}^{-1}}\\!\\!-k+\log|\Sigma_{0}|\right)$
is a constant that depends on the choice of the prior’s parameters, the true
parameter, and its dimension $k$.

In both cases above, the characteristic function $\bm{\mathcal{V}}^{m}$ can be
approximately decomposed into a sum of three terms: The first term grows
logarithmically in $m$ while the rest are fixed. This tells us that while the
characteristic function diverges, it does so very slowly. The second term is a
constant that depends mainly on the parameters of the prior. The third term,
which is proportional to the log-determinant of the joint Fisher information,
is the only one that depends on $S$. If we apply $\phi$ which is additive,
then roughly,

$\phi(i,\bm{\mathcal{V}}^{m})\approx\phi(i,V_{1})+\phi(i,V_{2})+\phi(i,S\mapsto
0.5\log|\mathcal{I}_{S}|)$

for a large $m$ and some constant (w.r.t. $S$) functions $V_{1}$ and $V_{2}$.
So, if we take the difference between two players, then the first two terms
cancel out and we are left with the third. The preceding heuristic argument is
made precise by the following result and its proof:

######  Theorem 2.

Let $\bm{\mathcal{V}}^{m}$ be a parametric Bayesian learning game and $V$ be a
cooperative game s.t. $V(S):=0.5\log|\mathcal{I}_{S}|$ if $S$ is nonempty, and
$V(S):=0$ otherwise. If $\phi$ is an additive solution concept, then under
regularity conditions A1 to A4 and for a uniformly distributed prior and any
players $i,j\in N$,

$\phi(i;\bm{\mathcal{V}}^{m})-\phi(j;\bm{\mathcal{V}}^{m})\overset{\textnormal{p}}{\longrightarrow}\phi(i;V)-\phi(j;V)$

as $m\rightarrow\infty$. We call $V$ a limiting game of $\bm{\mathcal{V}}^{m}$
w.r.t. $\phi$.

We will now mention several remarks regarding the above result: (a) It does
not say that the game $\bm{\mathcal{V}}^{m}$ converges to $V$. In fact,
$\bm{\mathcal{V}}^{m}$ is divergent, as described previously. Rather, it says
that as far as the differences in Shapley value are concerned, the two games
are equivalent in the limit. (b) Though a uniform prior is assumed, the result
also holds for the normal prior, as argued previously and shown in our
experimental results. (c) The result applies not only to the Shapley/Banzhaf
value, but also to any additive solution concept or even, more generally, any
linear transformation of the characteristic function. (d) Notice that the
function $V$ does not depend on the choice of the prior’s parameters. In other
words, in the presence of a large quantity of data, the choice of the prior is
inconsequential; the relative contributions of the players depend only on
their Fisher information. Finally, (e) the result introduces the notion of
limiting games which is useful in describing asymptotically equivalent
sequences of games. Two games are equivalent (w.r.t. a solution concept) when
there exists a fixed game that is limiting for both.

Coming back to the example in Fig 1, in Fig. 1(b), we show the differences in
Shapley value as the number $m$ of data points shared increases. For each $m$,
we generate $10$ instances of the game by sampling $m$ data points from the
observable variables. Bayesian inferences are then performed using a normal
prior and the Shapley values are computed using posterior-prior KL
divergences. The differences are then plotted and represented by the circles
in Fig. 1(b). The dashed lines represent the differences computed based on the
game $S\mapsto 0.5\log|\mathcal{I}_{S}|$. Fig. 1(b) shows that as $m$
increases, the sampled differences get increasingly concentrated around the
dashed lines, hence aligning with Theorem 2.

##  4 Shapley-Fair Online Collaborative Learning Framework

In the previous section, we have shown that under some regularity conditions,
the difference in Shapley values converges to a value that is determined
solely by the Fisher information. In this section, we exploit this fact to
present a $2$-player iterative learning framework that is asymptotically
Shapley-fair. In this framework, players do not provide their data all at once
but rather at a rate that is determined by the framework. The main idea is to
vary the rates s.t. in the limit, the determinants of both players’ Fisher
information are the same. This is achieved by bundling several data points
together and treating them as a single unit. Consider a $2$-player game with
players $1$ and $2$. If we bundle $r$ of player $1$’s data points, then given
the i.i.d. condition of the data points, its new Fisher information is given
by

$\begin{array}[]{l}\displaystyle\text{Var}\left[\frac{\partial}{\partial\theta}\log\prod_{j=1}^{r}\mathcal{L}_{1}(\theta^{*};\textbf{X}_{1j})\right]\vspace{0.5mm}\\\
\displaystyle=\sum_{j=1}^{r}\text{Var}\left[\frac{\partial}{\partial\theta}\log\mathcal{L}_{1}(\theta^{*};\textbf{X}_{1j})\right]=r\mathcal{I}_{1}\
.\end{array}$

So, setting $r=(|\mathcal{I}_{2}\mathcal{I}_{1}^{-1}|)^{1/k}$ yields
$|r_{1}\mathcal{I}_{1}|=|\mathcal{I}_{2}|$. In other words, if player $1$
provides data points at the rate of $r$ w.r.t. player $2$, then the difference
in Shapley value converges in probability to zero, by Theorem 2.

The two main steps in the framework are (a) the estimation of the true
parameter which is the main objective of the collaboration, and (b) the
estimation of the Fisher information which is used to determine the rates at
which data are received. This is done using sample approximation. The
framework starts with some data points from both players and repeats the
following steps:

  1. 1.

Use current available data points to compute an estimate $\bar{\theta}$ of the
true parameter.

  2. 2.

Let $m_{i}$ denote the number of player $i$’s data points received so far. For
$i=1,2$, use sample approximation to estimate the Fisher information at
$\bar{\theta}$:

$\hat{\mathcal{I}}_{i}\\!=\\!\frac{1}{m_{i}}\\!\sum_{j=1}^{m_{i}}\\!\left(\\!\\!\frac{\partial}{\partial\theta}\log\mathcal{L}_{i}(\bar{\theta};x_{ij})\\!\\!\right)\\!\\!\left(\\!\\!\frac{\partial}{\partial\theta}\log\mathcal{L}_{i}(\bar{\theta};x_{ij})\\!\\!\right)^{\top}.$

  3. 3.

Collect $r_{1}$ and $r_{2}$ data points from the respective players $1$ and
$2$ s.t. the proportion $m_{1}+r_{1}:m_{2}+r_{2}$ of their cumulative data
points is equal to
$|\hat{\mathcal{I}}_{2}|^{1/k}:|\hat{\mathcal{I}}_{1}|^{1/k}$.

In practice, minimum and maximum constraints can be imposed on $r_{1}$ and
$r_{2}$ to limit the number of data points collected in each iteration. If the
estimator in step $1$ is consistent, then by the law of large numbers and
continuous mapping theorem, the sampled Fisher information converges in
probability to the true Fisher information. This, together with Theorem 2,
gives us the following result:

######  Corollary 2.

Suppose that $\bar{\theta}$ in step $1$ is a consistent estimator of the true
parameter. Then, as the number of iterations goes to infinity, the difference
in Shapley value between the two players converges in probability to zero.

Note that the framework does not require any Bayesian inference. The corollary
states that if in each iteration, Bayesian inferences were performed and the
KL divergences were computed, then the difference in Shapley value (based on
those divergences) would converge in probability to zero.

##  5 Experimental Results

In this section, our framework is empirically verified by showing that the
Shapley values converge over time in several $2$-player scenarios, followed by
multi-player scenarios. We will investigate parameter estimation, as in Fig.
1: parameter estimation for Bayesian linear regression (BLR) on real-world
datasets and mean estimation in a learned latent space of a variational auto-
encoder (VAE) (Kingma & Welling, 2014).

#### Data, experiments, and implementation details.

We will investigate parameter estimation for BLR on three real-world datasets:
California housing (CaliH) data (Pace & Barry, 1997), King County house sales
prediction (Harlfoxem, 2016), and age estimation from facial images (Zhang et
al., 2017); and mean estimation in a learned $2$-dimensional latent space of a
VAE on the digits $0$ and $1$ of MNIST. Our code is publicly available at
https://github.com/XinyiYS/Parametric-Bayesian-Learning-Games.

Experiment 1. For the CaliH data consisting of $20640$ data points of
$8$-dimensional real-valued features, BLR is directly performed on the $6$
real-valued features.111We drop the latitude and longitude features for CaliH
data. So, the parameter to be estimated is a $6$-dimensional real-valued
vector with a standard normal prior. For KingH (FaceA) consisting of data of
higher dimensions, we train a deep (i.e., convolutional) neural network as a
feature extractor to extract $10$ ($9$)-dimensional real-valued features to
perform BLR. So, the parameter to be estimated is a $10$ ($9$)-dimensional
real-valued vector. Additional details for KingH and FaceA are in Appendix B.

Experiment 2. This experiment is motivated from density estimation for high-
dimensional data being computationally expensive. So, it is often more
practical to estimate their density in the latent space and mean estimation is
a step in that direction. Specifically, supposing the data distribution
contains several modes/classes, we want to estimate the mean for each mode in
the latent space. In this experiment, we use digits $0$ and $1$ from the MNIST
dataset for a $2$-mode mean estimation and the mapping to a $2$-dimensional
latent space is given by a pre-trained VAE. So, the parameter to be estimated
is $4$-dimensional with a standard normal prior.

Implementation of framework in Section 4. Starting with $m_{i}$ initial data
points for P$i$ (i.e., player $i$), we perform Bayesian inference to obtain
the (joint) posterior mean $\bar{\theta}$ (as an estimate of the true
parameter) to be used for approximating the Fisher information
$\hat{\mathcal{I}}_{i}$ which is in turn used to determine the number $r_{i}$
of data points to collect for the next iteration as
$r_{i}=r_{i^{*}}|\mathcal{I}_{i^{*}}\mathcal{I}_{i}^{-1}|^{1/k}$ where
$i^{*}\coloneqq\arg\\!\max_{i\in N}|\mathcal{I}_{i}|$ and the number
$r_{i^{*}}$ of data points to collect for the player with the higher/highest
Fisher information follows a preset constant, and update $m_{i}\leftarrow
m_{i}+r_{i}$. As the Fisher information of player $i$’s data points is less
than that of player $i^{*}$, player $i$ needs to collect more data points than
player $i^{*}$ in the next iteration. For $2$ players, this specification of
$r_{i}$ ensures that the difference in their Shapley values converges in
probability to zero, by Theorem 2. To calculate the Shapley values
$\phi(i;\bm{\mathcal{V}}^{m_{i}})$ described in Section 2, we perform
additional inferences on the players’ individual data (up to the current
iteration) to compute the posterior-prior KL divergences
$\bm{\mathcal{V}}^{m_{i}}(S)=\textnormal{KL}(\bm{P}_{S}^{m_{i}}\|\Pi)$ (1).

2-player specification and results. In experiment $1$, P$1$ samples
P$1$_sample_size data points from a restricted subset (of size P$1$_data) of
the original data. This simulates that P$1$ can only observe data (e.g.,
housing prices) from a certain area or district for constructing its parameter
estimate. Two sampling methods are considered: standard uniform sampling
(denoted as iid) and a method based on the statistical leverage scores
(Drineas et al., 2012) (denoted as lvg_iid) due to its suitability in linear
regression. Intuitively, higher P$1$_data, P$1$_sample_size, and lvg_iid (vs.
iid) should result in more accurate parameter estimates (i.e., higher Fisher
information) from P$1$. P$2$ samples noisy observations from a distribution
whose mean is estimated based on a proportion (P$2$_ratio) of the original
data with a fraction (P$2$_nan) of missing values. In other words, P$2$’s
observation is more direct but defective due to noise and missing values.
Intuitively, a higher P$2$_ratio and a lower P$2$_nan should result in more
accurate parameter estimates (i.e., higher Fisher information) from P$2$.
Specific details are described in Appendix B.

In experiment $2$, P$1$ and P$2$ have a subset of the original data to sample
from and their sizes are, respectively, denoted by P$1$_data and P$2$_data.
But, their data (respectively, denoted by P$1$_ratio and P$2$_ratio) are
biased towards one digit or the other. For example, P$1$_ratio $=0.1$ means
that P$1$ has $0.1$ ($0.9$) probability of sampling the digit $0$ ($1$).

Figure 2: SV and cumulative count vs. iterations on CaliH (top) and FaceA
(bottom) for $2$-player scenarios. For CaliH, P$1$_data=$5000$,
P$1$_sample_size $=500$, P$1$’s sampling is lvg_iid, P$2$_ratio $=0.01$, and
P$2$_nan $=0.4$. For FaceA, P$1$_data $=1000$, P$1$_sample_size $=100$, P$1$’s
sampling is lvg_iid, P$2$_ratio $=0.1$, and P$2$_nan $=0.1$.

The Shapley values and the cumulative counts of shared data points over the
iterations are shown in Fig. 2. To additionally verify convergence, we will
analyze the following quantities: (a) statistics of the relative difference
$\delta\coloneqq|(\phi_{1}-\phi_{2})/(\phi_{1}+\phi_{2})|$, including the
lowest, average, and standard deviation, and (b) the number of iterations
(denoted by Iter) required for $\delta$ to be smaller than a threshold of
$0.1$ for $5$ consecutive iterations. These are computed after a burn-in
period of $5$ iterations, as shown in Table 1 for CaliH. Results for other
datasets are in Appendix B.

Fig. 2 (left column) shows that the Shapley values of P$1$ and P$2$ converge
over time and verifies our claim. More importantly, our framework adjusts the
cumulative counts based on the Fisher information of the players’ data points.
The plots on cumulative count in Fig. 2 (right column) shows that P$2$ (P$1$)
needs to consistently collect more data points for CaliH (FaceA). This is due
to the difference in the settings for P$1$ and P$2$’s data: For CaliH,
P$1$_data and P$1$_sample_size are higher and can hence lead to a higher
accuracy in P$1$’s parameter estimates. Also, P$2$_ratio is lower and P$2$_nan
is higher, which can lead to a lower accuracy in P$2$’s parameter estimates.
Consequently, for CaliH, P$2$ needs to collect more data points. This shows
that our framework identifies the correct relationship between the accuracy of
the players’ parameter estimates and correspondingly sets the cumulative
counts in order to ensure that their Shapley values converge.

Table 1 illustrates this effect in greater detail on CaliH via the statistics
on $\delta$ by varying P$1$’s settings. It shows $3$ cases of the difference
not diminishing (i.e., $3$ rows with *), which can be attributed to P$1$’s
sample size (of $10$) being too restrictive to construct accurate parameter
estimates to match P$2$’s. This suggests that if the data qualities of P$1$
and P$2$ differ significantly, it may be more difficult (e.g., more
iterations) for their Shapley values to converge. Additional results for other
datasets are in Appendix B.

Table 1: Statistics on $\delta$ for CaliH with varying P$1$’s contributions.
Iter denotes the smallest number of iterations for $\delta$ to be smaller than
$0.1$ for $5$ consecutive iterations and * denotes cases where it is not
satisfied. Also, P$2$_nan $=$ P$2$_ratio $=0.1$.

P$1$_data | P$1$_sample_size | sampling | Lowest | Average | StDev | Iter
---|---|---|---|---|---|---
1000 | 10 | iid | 0.239 | 0.267 | 0.021 | 50*
1000 | 10 | lvg_iid | 0.292 | 0.318 | 0.021 | 50*
1000 | 100 | iid | 0.090 | 0.104 | 0.011 | 30
1000 | 100 | lvg_iid | 0.092 | 0.105 | 0.011 | 37
1000 | 500 | iid | 0.044 | 0.053 | 0.007 | 5
1000 | 500 | lvg_iid | 0.050 | 0.060 | 0.008 | 5
5000 | 10 | iid | 0.353 | 0.376 | 0.019 | 50*
5000 | 500 | iid | 0.094 | 0.105 | 0.008 | 43
5000 | 500 | lvg_iid | 0.072 | 0.083 | 0.008 | 7

#### Multi-player extension and results.

We will first examine the $3$-player scenario in Fig. 1 (denoted as
synthetic): P$1$ (P$3$) samples some noisy linear transformations of the true
parameters (into a $1$-dimensional variable) perturbed with known (unknown)
zero-mean normal noise with standard deviation of $1$ ($1.1$), while P$2$
samples noisy observations of the true parameters where the noise is zero-mean
isotropic normal with variance $2.5$. Subsequently, we extend both experiments
$1$ and $2$. For experiment $1$, we add two players P$3$ and P$4$ where the
data sizes of P$3$ and P$1$ are equal but P$1$ (P$3$) adopts the lvg_iid (iid)
sampling, and P$4$ is defined in the same way as P$2$ (but its actual data are
different). For experiment $2$, we add two players P$3$ and P$4$ who have a
ratio of $0.5$ (i.e., balanced between digits $0$ and $1$) and data of the
same size as P$1$’s and P$2$’s data, respectively.

The Shapley values and the cumulative counts of shared data points over the
iterations for synthetic and KingH are shown in Fig. 3. We observe that the
Shapley values of the players converge over iterations, which empirically
demonstrates that our framework can be generalized to multiple players. For
synthetic, we observe that P$1$ and P$3$ need to collect consistently more
data points than P$2$ since P$2$ directly samples (noisy) observations of the
true parameter. P$1$ and P$3$ do not differ by much as P$3$ maintains and
updates a noise estimate dynamically; so, as its noise estimate becomes more
accurate, P$3$ becomes closer to P$1$. For KingH, we observe that both P$2$
and P$4$ need to collect consistently more data points than P$1$ and P$3$,
possibly because the ratio of missing values is high. The cumulative counts
for P$2$ and P$4$ overlap because P$2$ and P$4$ share an identical data
specification; similarly, for P$1$ and P$3$, they differ only in the sampling
method (lvg_iid vs. iid). Additional experimental results for other datasets
are in Appendix B.

Figure 3: SV and cumulative count vs. iterations on synthetic (top) and KingH
(bottom) for multi-player scenarios. For KingH, P$1$/P$3$_data $=1000$,
P$1$/P$3$_sampling_size $=100$, P$2$/P$4$_ratio $=0.1$, and P$2$/P$4$_nan
$=0.2$.

##  6 Conclusion and Future Work

In this paper, we study the asymptotic properties of linear solution concepts
(in particular, the Shapley value) in parametric Bayesian learning games. We
show that in the limit, under some regularity conditions, the differences in
Shapley value are determined solely by the players’ Fisher information. This
allows us to use a consistent Fisher information estimator in an online
collaborative framework to achieve asymptotically Shapley-fair data sharing
rates. Though the theoretical guarantee is established only for the $2$-player
setting, promising empirical results suggest a possibility for a more general
result. Extending it to an arbitrary number of players will be the primary
focus of our future work.

Though the assumptions used in this work are mild, their relaxations can be
considered in the future works. This includes using a general (possibly
improper) prior and dropping the independence assumption between players’
data. A particularly interesting direction is the relaxation of the
distinguishability property. There may be cases when even with an infinite
quantity of data, no single player is able to identify the true parameter.
This can occur, for example, when the players are restricted to observe only
certain parts of the same sample space. It is only by collaborating that the
true parameter can be identified with a greater accuracy. This will provide a
stronger motivation for collaborating beyond a faster convergence rate.
Finally, the use of different divergences and how that affects the resulting
Shapley value would also be considered.

## Acknowledgements

This research/project is supported by the National Research Foundation
Singapore and DSO National Laboratories under the AI Singapore Programme (AISG
Award No: AISG$2$-RP-$2020$-$018$). Xinyi Xu is supported by the Institute for
Infocomm Research of Agency for Science, Technology and Research (A*STAR).

## References

  * Banzhaf (1965) Banzhaf, J. F.  Weighted voting doesn’t work: A mathematical analysis.  _Rutgers Law Review_ , 19(2):317–343, 1965.
  * Blum et al. (2017) Blum, A., Haghtalab, N., Procaccia, A. D., and Qiao, M.  Collaborative PAC learning.  In _Proc. NeurIPS_ , 2017.
  * Cam & Yang (2000) Cam, L. L. and Yang, G. L.  _Asymptotics in Statistics: Some Basic Concepts_.  Springer Series in Statistics. Springer New York, NY, 2nd edition, 2000\.
  * Chen et al. (2018) Chen, J., Zhang, Q., and Zhou, Y.  Tight bounds for collaborative PAC learning via multiplicative weights.  In _Proc. NeurIPS_ , 2018.
  * Cover & Thomas (2006) Cover, T. M. and Thomas, J. A.  _Elements of Information Theory_.  John Wiley & Sons, Inc., 2nd edition, 2006.
  * Covert et al. (2020) Covert, I. C., Lundberg, S. M., and Lee, S.-I.  Understanding global feature contributions with additive importance measures.  In _Proc. NeurIPS_ , 2020.
  * Drineas et al. (2012) Drineas, P., Magdon-Ismail, M., Mahoney, M. W., and Woodruff, D. P.  Fast approximation of matrix coherence and statistical leverage.  _JMLR_ , 13(1), 2012.
  * Ghorbani & Zou (2019) Ghorbani, A. and Zou, J.  Data Shapley: Equitable valuation of data for machine learning.  In _Proc. ICML_ , 2019.
  * Ghourchian et al. (2017) Ghourchian, H., Gohari, A., and Amini, A.  Existence and continuity of differential entropy for a class of distributions.  _IEEE Communications Letters_ , 21(7):1469–1472, 2017.
  * Harlfoxem (2016) Harlfoxem.  House sales in King County, USA.  https://www.kaggle.com/harlfoxem/housesalesprediction, 2016.
  * Kingma & Welling (2014) Kingma, D. P. and Welling, M.  Auto-encoding variational Bayes.  In _Proc. ICLR_ , 2014.
  * Lundberg & Lee (2017) Lundberg, S. M. and Lee, S.-I.  A unified approach to interpreting model predictions.  In _Proc. NeurIPS_ , 2017.
  * Nguyen & Zakynthinou (2018) Nguyen, H. and Zakynthinou, L.  Improved algorithms for collaborative PAC learning.  In _Proc. NeurIPS_ , 2018.
  * Pace & Barry (1997) Pace, R. K. and Barry, R.  Sparse spatial autoregressions.  _Statistics & Probability Letters_, 33(3):291–297, 1997.
  * Shapley (1953) Shapley, L. S.  A value for $n$-person games.  In Kuhn, H. W. and Tucker, A. W. (eds.), _Contributions to the Theory of Games_ , volume 2, pp. 307–317. Princeton Univ. Press, 1953.
  * Sim et al. (2020) Sim, R. H. L., Zhang, Y., Chan, M. C., and Low, B. K. H.  Collaborative machine learning with incentive-aware model rewards.  In _Proc. ICML_ , pp. 8927–8936, 2020.
  * Sim et al. (2022) Sim, R. H. L., Xu, X., and Low, B. K. H.  Data valuation in machine learning: “ingredients”, strategies, and open challenges.  In _Proc. IJCAI_ , 2022.
  * Tay et al. (2022) Tay, S. S., Xu, X., Foo, C. S., and Low, B. K. H.  Incentivizing collaboration in machine learning via synthetic data rewards.  In _Proc. AAAI_ , 2022.
  * van der Vaart (1998) van der Vaart, A. W.  _Asymptotic Statistics_.  Cambridge Univ. Press, 1998.
  * Wu et al. (2022) Wu, Z., Shu, Y., and Low, B. K. H.  DaVinz: Data valuation using deep neural networks at initialization.  In _Proc. ICML_ , 2022.
  * Xu et al. (2021a) Xu, X., Lyu, L., Ma, X., Miao, C., Foo, C. S., and Low, B. K. H.  Gradient driven rewards to guarantee fairness in collaborative machine learning.  In _Proc. NeurIPS_ , 2021a.
  * Xu et al. (2021b) Xu, X., Wu, Z., Foo, C. S., and Low, B. K. H.  Validation free and replication robust volume-based data valuation.  In _Proc. NeurIPS_ , 2021b.
  * Zhang et al. (2017) Zhang, Z., Song, Y., and Qi, H.  Age progression/regression by conditional adversarial autoencoder.  In _Proc. CVPR_ , 2017.

##  Appendix A Proofs of Theoretical Results

Throughout, the measurable space is taken to be $\mathbb{R}^{k}$ equipped with
the standard Borel sigma algebra. Unless otherwise stated, absolute continuity
is w.r.t. the Lebesgue measure which is denoted with $\lambda$. We will start
with the following claim. The terms evaluated in this claim often appear as
residuals in later parts and here, they are shown to converge in probability
either to zero or one.

######  Claim 1.

The following are some properties of the approximate joint posterior
$\bm{\hat{P}}_{S}^{m}$ in relation to the support of the prior $\Theta_{\Pi}$
and its complement $\Theta_{\Pi}^{c}$:

  * i.

$\displaystyle{\int_{\Theta_{\Pi}^{c}}\text{\emph{d}}\bm{\hat{P}}_{S}^{m}\overset{\textnormal{p}}{\longrightarrow}0}\quad$
and
$\quad\displaystyle{\int_{\Theta_{\Pi}}\text{\emph{d}}\bm{\hat{P}}_{S}^{m}\overset{\textnormal{p}}{\longrightarrow}1}$,

  * ii.

$\displaystyle{\int_{\Theta_{\Pi}^{c}}}\log\left(\frac{\text{\emph{d}}\bm{\hat{P}}_{S}^{m}}{\text{\emph{d}}\lambda}\right)\text{\emph{d}}\bm{\hat{P}}_{S}^{m}\overset{\textnormal{p}}{\longrightarrow}0$.

###### Proof.

(i) The density of
$\displaystyle{\bm{\hat{P}}_{S}^{m}:=\mathcal{N}\left(\bm{\hat{\theta}}_{S}^{m},\frac{1}{m}\mathcal{I}_{S}^{-1}\right)}$,
denoted by $\bm{\hat{p}}_{S}^{m}(\theta)$, is given by

$\displaystyle\frac{\displaystyle\exp\left\\{-\frac{1}{2}(\theta-\bm{\hat{\theta}}_{S}^{m})^{\top}\left(\frac{1}{m}\mathcal{I}_{S}^{-1}\right)^{-1}(\theta-\bm{\hat{\theta}}_{S}^{m})\right\\}}{\displaystyle\sqrt{(2\pi)^{k}\left|\frac{1}{m}\mathcal{I}_{S}^{-1}\right|}}$
$\displaystyle=\frac{\displaystyle
m^{k/2}\exp\left\\{-\frac{m}{2}(\theta-\bm{\hat{\theta}}_{S}^{m})^{\top}\mathcal{I}_{S}(\theta-\bm{\hat{\theta}}_{S}^{m})\right\\}}{\displaystyle\sqrt{(2\pi)^{k}\left|\mathcal{I}_{S}^{-1}\right|}}$
$\displaystyle=C\sqrt{\frac{m^{k}}{\exp({m\cdot\bm{Z}})}}$

for some constant $C>0$ and nonnegative random variables
$\bm{Z}:=(\theta-\bm{\hat{\theta}}_{S}^{m})^{\top}\mathcal{I}_{S}(\theta-\bm{\hat{\theta}}_{S}^{m})$.
Since
$\bm{\hat{\theta}}_{S}^{m}\overset{\textnormal{p}}{\longrightarrow}\theta^{*}$,
$\bm{Z}\overset{\textnormal{p}}{\longrightarrow}0$ if $\theta=\theta^{*}$, and
$\bm{Z}\overset{\textnormal{p}}{\longrightarrow}a$ for some $a>0$ otherwise.
This means that for any measurable set $A$ s.t. $\theta^{*}\notin A$, the
function $\bm{\hat{p}}_{S}^{m}$ on $A$ converges pointwise to the zero
function, and thus

$\bm{\hat{P}}_{S}^{m}(A)=\int_{A}\bm{\hat{p}}_{S}^{m}\text{d}\lambda\overset{\textnormal{p}}{\longrightarrow}\int_{A}0\,\text{d}\lambda=0$

by the dominated convergence theorem. By Assumption A4,
$\theta^{*}\notin\Theta_{\Pi}^{c}$, and therefore

$\int_{\Theta_{\Pi}^{c}}\text{d}\bm{\hat{P}}_{S}^{m}\overset{\textnormal{p}}{\longrightarrow}0\quad\text{and}\quad\int_{\Theta_{\Pi}}\text{d}\bm{\hat{P}}_{S}^{m}=1-\int_{\Theta_{\Pi}^{c}}\text{d}\bm{\hat{P}}_{S}^{m}\overset{\textnormal{p}}{\longrightarrow}1\
.$

(ii) Note that ${\lim_{x\to 0^{+}}}x\log x=\lim_{x\to 0^{+}}(\log
x)/(1/x)\overset{\text{L'H}}{=}\lim_{x\to
0^{+}}({1/x})/({-1/x^{2}})=\lim_{x\to 0^{+}}-x=0$. From (i),
$\bm{\hat{p}}_{S}^{m}$ (on the set $\Theta_{\Pi}^{c}$) converges pointwise to
the zero function and therefore, so is
$\bm{\hat{p}}_{S}^{m}\log\bm{\hat{p}}_{S}^{m}$. Again, by the dominated
convergence theorem, we have the required result. ∎

### Theorem 1 (Bernstein-von Mises)

The conditions needed for Bernstein-von Mises to hold in a coalitional setting
are as follows: (i) Twice differentiability of $\mathcal{L}_{S}$ w.r.t.
$\theta$: This is fulfilled since by Assumption A2, the joint likelihood is
the product of individual likelihoods, the individual likelihoods are twice
differentiable (Assumption A1), and the products of differentiable functions
are differentiable. Note that sometimes a weaker condition is given, i.e., the
function is differentiable in the quadratic mean at $\theta^{*}$ (see, for
example, thw work of van der Vaart (1998)). For our purpose, however, the
slightly stronger yet simpler condition suffices. (ii) The combined data are
distinguishable from the ones generated using a parameter other than
$\theta^{*}$: This is satisfied as long as one player’s data is
distinguishable (Assumption A3) since its distinguisher can be used as the
distinguisher for the combined data. Finally, (iii) the prior satisfies the
conditions given in Assumption A4. In addition, note also that by the
independence assumption,

$\mathcal{I_{S}}=\textnormal{Var}\left[\frac{\partial}{\partial\theta}\log\mathcal{L}_{S}(\theta^{*};\textbf{X}_{S}^{1})\right]=\sum_{i\in
S}\textnormal{Var}\left[\frac{\partial}{\partial\theta}\log\mathcal{L}_{i}(\theta^{*};\textbf{X}_{i1})\right]=\sum_{i\in
S}\mathcal{I}_{i}\ .$

### Lemma 1

We start with a triangle-like inequality for the extended KL divergence:

######  Claim.

Let $F$, $G$, and $K$ be three probability measures on $\Theta$ s.t. $F\ll K$,
while $G$ may not be absolutely continuous w.r.t. $K$. Let $\Theta_{K}$ denote
the support of $K$ which is compact. Then, there exists a constant $c>0$ s.t.

$\Bigl{|}\,\textnormal{KL}(F\|K)-\textnormal{KL}^{+}(G\|K)\,\Bigr{|}\leq
c\cdot\bigl{\|}F-G\bigr{\|}_{\textnormal{TV}}+\Bigl{|}H(F)-H(G)\Bigr{|}+\left|\int_{\Theta_{K}^{c}}\log\left(\frac{\text{\emph{d}}G}{\text{\emph{d}}\lambda}\right)\text{\emph{d}}G\right|$

where $\Theta_{K}^{c}$ denotes the complement of $\Theta_{K}$.

###### Proof.

Let $f$, $g$, and $k$ be the densities of $F$, $G$, and $K$, respectively.
Then, by definition,

$\Bigl{|}\,\textnormal{KL}(F\|K)-\textnormal{KL}^{+}(G\|K)\,\Bigr{|}=\left|\int_{\theta\in\Theta_{K}}f(\theta)\log\left(\frac{f(\theta)}{k(\theta)}\right)\text{d}\theta-\int_{\theta\in\Theta_{K}}g(\theta)\log\left(\frac{g(\theta)}{k(\theta)}\right)\text{d}\theta\right|.$

After rearranging the terms,

$\left|\int_{\theta\in\Theta_{K}}[g(\theta)-f(\theta)]\cdot\log k(\theta)\
\text{d}\theta+\int_{\theta\in\Theta_{K}}f(\theta)\log f(\theta)\
\text{d}\theta-\int_{\theta\in\Theta_{K}}g(\theta)\log g(\theta)\
\text{d}\theta\right|$

which is upper bounded by

$\int_{\theta\in\Theta_{K}}\Bigl{|}g(\theta)-f(\theta)\Bigr{|}\cdot\Bigl{|}\log
k(\theta)\Bigr{|}\
\text{d}\theta+\left|-H(F)-\int_{\theta\in\Theta_{K}}g(\theta)\log g(\theta)\
\text{d}\theta\right|.$

For the first term, since $\Theta_{K}$ is compact, the logarithmic part is
bounded and

$\displaystyle\int_{\theta\in\Theta_{K}}\Bigl{|}g(\theta)-f(\theta)\Bigr{|}\cdot\Bigl{|}\log
k(\theta)\Bigr{|}\ \text{d}\theta$ $\displaystyle\leq$
$\displaystyle\int_{\theta\in\Theta_{K}}\Bigl{|}g(\theta)-f(\theta)\Bigr{|}\cdot\max_{\theta^{\prime}\in\Theta_{K}}\Bigl{|}\log
k(\theta^{\prime})\Bigr{|}\ \text{d}\theta$ $\displaystyle\leq$
$\displaystyle\max_{\theta^{\prime}\in\Theta_{K}}\Bigl{|}\log
k(\theta^{\prime})\Bigr{|}\cdot\int_{\theta\in\Theta}\Bigl{|}g(\theta)-f(\theta)\Bigr{|}\
\text{d}\theta$ $\displaystyle=$
$\displaystyle\max_{\theta^{\prime}\in\Theta_{K}}\Bigl{|}\log
k(\theta^{\prime})\Bigr{|}\cdot\left\|\,g-f\,\right\|_{L^{1}}$
$\displaystyle=$ $\displaystyle\max_{\theta^{\prime}\in\Theta_{K}}\Bigl{|}\log
k(\theta^{\prime})\Bigr{|}\cdot 2\,\bigl{\|}G-F\bigr{\|}_{\textnormal{TV}}\ .$

For the second term,

$\displaystyle\left|-H(F)-\int_{\theta\in\Theta_{K}}g(\theta)\log g(\theta)\
\text{d}\theta\,\right|$ $\displaystyle=$
$\displaystyle\left|-H(F)+H(G)+\int_{\theta\in\Theta_{K}^{c}}g(\theta)\log
g(\theta)\ \text{d}\theta\,\right|$ $\displaystyle\leq$
$\displaystyle\Bigl{|}H(F)-H(G)\Bigr{|}+\left|\int_{\theta\in\Theta_{K}^{c}}g(\theta)\log
g(\theta)\ \text{d}\theta\right|,$

as required. ∎

The claim above shows that the difference between $\textnormal{KL}(F\|K)$ and
$\textnormal{KL}^{+}(G\|K)$ can be bounded in terms of the total variation
distance between $F$ and $G$, their difference in entropy, and a residual
term. Note that when $G$ is also absolutely continuous w.r.t. $K$, the
extended KL divergence reduces to the standard definition and the residual
term disappears. By applying the claim, for any $m$ and $\varepsilon>0$, there
exists a constant $c>0$ s.t.

$\begin{array}[]{l}\displaystyle\Pr\left[\Bigl{|}\,\textnormal{KL}(\bm{P}^{m}_{S}\|\Pi)-\textnormal{KL}^{+}(\bm{\hat{P}}^{m}_{S}\|\Pi)\,\Bigr{|}>\varepsilon\right]\vspace{0.5mm}\\\
\displaystyle\leq\Pr\left[c\cdot\bigl{\|}\bm{P}^{m}_{S}-\bm{\hat{P}}^{m}_{S}\bigr{\|}_{\textnormal{TV}}+\left|H(\bm{P}^{m}_{S})-H(\bm{\hat{P}}^{m}_{S})\right|+\left|\int_{\Theta_{\Pi}^{c}}\log\left(\frac{\text{d}\bm{\hat{P}}^{m}_{S}}{\text{d}\lambda}\right)\text{d}\bm{\hat{P}}^{m}_{S}\right|>\varepsilon\right]\vspace{0.5mm}\\\
\displaystyle\leq\Pr\left[\bigl{\|}\bm{P}^{m}_{S}-\bm{\hat{P}}^{m}_{S}\bigr{\|}_{\textnormal{TV}}>\varepsilon/(3c)\right]+\Pr\left[\left|H(\bm{P}^{m}_{S})-H(\bm{\hat{P}}^{m}_{S})\right|>\varepsilon/3\right]+\Pr\left[\left|\int_{\Theta_{\Pi}^{c}}\log\left(\frac{\text{d}\bm{\hat{P}}^{m}_{S}}{\text{d}\lambda}\right)\text{d}\bm{\hat{P}}^{m}_{S}\right|>\varepsilon/3\right].\end{array}$

Therefore, if the three terms converge in probability to zero, then so is the
difference in extended KL divergence. The convergence of the first term (i.e.,
in total variation distance) is given by Theorem 1 and that of the residual
term is given by Claim 1(ii). The convergence in entropy is established next.

The convergence properties of (differential) entropy have been studied
extensively in the information-theoretic literature with different conditions
derived for the convergence to hold in terms of convergence in various
measures (e.g., $L^{1}$-distance, KL divergence, pointwise convergence). Here,
we adapted the approach found in (Ghourchian et al., 2017) that is well-suited
to our setting.

######  Claim.

Let $F$ and $G$ be two probability measures where the support $\Theta_{F}$ of
$F$ is compact while $G$ is absolutely continuous. Then,

$|H(F)-H(G)|\,\,\leq\,\,\delta\cdot\log\frac{\lambda(\Theta_{F})}{\delta}+\left|\int_{\Theta_{F}^{c}}\\!\\!\log\left(\frac{\text{\emph{d}}G}{\text{\emph{d}}\lambda}\right)\text{\emph{d}}G\right|$

for some $0\leq\delta\leq 2\bigl{\|}F-G\bigr{\|}_{\textnormal{TV}}\ .$

###### Proof.

Let $f$ and $g$ be the densities of $F$ and $G$, respectively. Furthermore,
let $M$ be defined as

$M:=\max\left\\{\sup_{\theta\in\Theta_{F}}f(\theta)\,,\,\sup_{\theta\in\mathbb{R}^{k}}g(\theta)\right\\}.$

We first apply a change of variables to $\bm{Y}_{F}\sim F$ and $\bm{Y}_{G}\sim
G$ by scaling them to obtain the random variables $2M\bm{Y}_{F}$ and
$2M\bm{Y}_{G}$, respectively. Let $\hat{F}$ and $\hat{G}$ be the new measures,
and $\hat{f}$ and $\hat{g}$ be their densities, respectively. Then,

$\begin{array}[]{ll}\displaystyle{\hat{f}(\theta)=\frac{1}{2M}\,f\\!\left(\frac{\theta}{2M}\right)}&\quad\text{with
support }\Theta_{\hat{F}}:=\\{2M\theta\\}_{\theta\in\Theta_{F}}\ ,\\\
\displaystyle{\hat{g}(\theta)=\frac{1}{2M}\,g\\!\left(\frac{\theta}{2M}\right)}&\quad\text{with
support }\mathbb{R}^{k}\ .\end{array}$

By scaling, we make the densities’ values lie in between $0$ and $1/2$ while
keeping both their $L^{1}$-distance and difference in entropy the same (since
we are scaling both by the same scalar). By letting
$u:=\theta/(2M)\Rightarrow\text{d}\theta=2M\,\text{d}u$,

$\int_{\theta\in\mathbb{R}^{k}}\\!|\hat{f}(\theta)-\hat{g}(\theta)|\
\text{d}\theta=\frac{1}{2M}\int_{\theta\in\mathbb{R}^{k}}\\!\left|f\left(\frac{\theta}{2M}\right)-g\left(\frac{\theta}{2M}\right)\right|\text{d}\theta=\int_{u\in\mathbb{R}^{k}}|f(u)-g(u)|\
\text{d}u$

and

$\left|H(\hat{F})-H(\hat{G})\right|=|H(F)+\log(2M)-H(G)-\log(2M)|=|H(F)-H(G)|\
.$

The purpose of scaling the densities to interval $[0,1/2]$ is so that we can
apply the following inequality later: If $x,y\in[0,1/2]$, then

$|x\log x-y\log y|\leq|x-y|\log\frac{1}{|x-y|}\ .$ (3)

The proof of the inequality can be found in Theorem $17.3.3$ (Equation
$17.27$) of Cover & Thomas (2006). Note that here we are indeed trying to
generalize Theorem $17.3.3$ to the continuous setting. We now construct
another probability measure $Z$ on $\Theta_{F}$ with the following density:

$z(\theta):=\left\\{\begin{array}[]{ll}\displaystyle{\frac{|\hat{f}(\theta)-\hat{g}(\theta)|}{\delta}}&\hskip
28.45274pt\text{if}\ \theta\in\Theta_{F}\ ,\\\ 0&\hskip
28.45274pt\text{otherwise}\ ;\end{array}\right.$

where
$\displaystyle{\delta:=\int_{\theta\in\Theta_{F}}\\!\\!|\hat{f}(\theta)-\hat{g}(\theta)|\
\text{d}\theta}$ is the normalizing factor. Note that

$\delta\leq\|\hat{f}-\hat{g}\|_{L^{1}}=\|f-g\|_{L^{1}}=2\bigl{\|}F-G\bigr{\|}_{\textnormal{TV}}\
.$

Putting all the above together,

$\displaystyle|H(F)-H(G)|$ $\displaystyle=\left|\int_{\Theta_{F}}f(\theta)\log
f(\theta)\ \text{d}\theta-\int_{\Theta_{F}}g(\theta)\log g(\theta)\
\text{d}\theta-\int_{\Theta_{F}^{c}}g(\theta)\log g(\theta)\
\text{d}\theta\right|$
$\displaystyle\leq\int_{\Theta_{F}}\Bigl{|}\hat{f}(\theta)\log\hat{f}(\theta)-\hat{g}(\theta)\log\hat{g}(\theta)\Bigr{|}\
\text{d}\theta+\left|\int_{\Theta_{F}^{c}}g(\theta)\log g(\theta)\
\text{d}\theta\right|=:R$
$\displaystyle\leq\int_{\Theta_{F}}|\hat{f}(\theta)-\hat{g}(\theta)|\cdot\log\frac{1}{|\hat{f}(\theta)-\hat{g}(\theta)|}\
\text{d}\theta+R\hskip 28.45274pt\text{(by
Inequality~{}\ref{useful_inequality})}$ $\displaystyle=\int_{\Theta_{F}}\delta
z(\theta)\cdot\log\frac{1}{\delta z(\theta)}\ \text{d}\theta+R\hskip
28.45274pt\text{(by Definition of $z$)}$
$\displaystyle=-\delta\log\delta\int_{\Theta_{F}}z(\theta)\
\text{d}\theta-\delta\int_{\Theta_{F}}z(\theta)\log z(\theta)\
\text{d}\theta+R$ $\displaystyle=-\delta\log\delta+\delta
H(Z)+R\phantom{\int}$
$\displaystyle\leq\delta\log\frac{\lambda(\Theta_{F})}{\delta}+R\ ,$

as required. ∎

By applying the claim to our setting,

$|H(\bm{P}_{S}^{m})-H(\bm{\hat{P}}_{S}^{m})|\leq\bm{\delta}^{m}\log\frac{\lambda(\Theta_{\Pi}))}{\bm{\delta}^{m}}+\left|\int_{\Theta_{\Pi}^{c}}\log\left(\frac{\text{d}\bm{\hat{P}}_{S}^{m}}{\text{d}\lambda}\right)\text{d}\bm{\hat{P}}_{S}^{m}\right|$

which converges in probability to zero since $\bm{\delta}^{m}\leq
2\bigl{\|}\bm{P}_{S}^{m}-\bm{\hat{P}}_{S}^{m}\bigr{\|}_{\textnormal{TV}}\overset{\textnormal{p}}{\longrightarrow}0$,
by Theorem 1, and the residual term as well, by Claim 1(ii). This completes
the proof.

### Corollary 1

By applying the definition of the extended KL divergence,

$\displaystyle\textnormal{KL}^{+}(\bm{\hat{P}}^{m}_{S}\|U(\Theta))$
$\displaystyle=$
$\displaystyle\int_{\Theta_{U}}\log\left(\frac{\bm{\hat{p}}^{m}_{S}}{1/\lambda(\Theta_{U})}\right)\text{d}\bm{\hat{P}}^{m}_{S}$
$\displaystyle=$ $\displaystyle\int_{\Theta_{U}}\log(\bm{\hat{p}}^{m}_{S})\
\text{d}\bm{\hat{P}}^{m}_{S}+\log\lambda(\Theta_{U})\int_{\Theta_{U}}\
\text{d}\bm{\hat{P}}^{m}_{S}$ $\displaystyle=$
$\displaystyle-H(\bm{\hat{P}}^{m}_{S})-\int_{\Theta_{U}^{c}}\log(\bm{\hat{p}}^{m}_{S})\
\text{d}\bm{\hat{P}}^{m}_{S}+\log\lambda(\Theta_{U})\int_{\Theta_{U}}\
\text{d}\bm{\hat{P}}^{m}_{S}$ $\displaystyle=$
$\displaystyle\frac{k}{2}\log\left(\frac{m}{2\pi
e}\right)+\frac{1}{2}\log|\mathcal{I}_{S}|-\int_{\Theta_{U}^{c}}\log(\bm{\hat{p}}^{m}_{S})\
\text{d}\bm{\hat{P}}^{m}_{S}+\log\lambda(\Theta_{U})\int_{\Theta_{U}}\
\text{d}\bm{\hat{P}}^{m}_{S}\ .$

From Claim 1,

$\int_{\Theta_{U}^{c}}\log(\bm{\hat{p}}^{m}_{S})\
\text{d}\bm{\hat{P}}^{m}_{S}\overset{\textnormal{p}}{\longrightarrow}0\quad\text{and}\quad\int_{\Theta_{U}}\
\text{d}\bm{\hat{P}}^{m}_{S}\overset{\textnormal{p}}{\longrightarrow}1$

which establish that

$\left|\textnormal{KL}^{+}(\bm{\hat{P}}^{m}_{S}\|U(\Theta))-\left(\frac{k}{2}\log\left(\frac{m}{2\pi
e}\right)+\log\lambda(\Theta_{U})+\frac{1}{2}\log|\mathcal{I}_{S}|\right)\right|\overset{\textnormal{p}}{\longrightarrow}0.$

Together with Lemma 1, this gives us the required result.

### Theorem 2

The characteristic function of a cooperative game is a mapping from $2^{N}$ to
$\mathbb{R}$. If we arrange the values of all coalitions in a vector, then we
get a $2^{|N|}$-dimensional real-valued vector. In other words, the set of all
possible characteristic functions is the $\mathbb{R}^{2^{|N|}-1}$ space; the
dimension is one less because the value of an empty coalition is always zero.
Note that in general, negative values are permitted. By definition, the
Shapley/Banzhaf value $\phi$ is a linear transformation from the
$\mathbb{R}^{2^{|N|}-1}$ space to the $\mathbb{R}^{|N|}$ space and is
therefore continuous. Now, define the function $\Delta_{ij}(v)$ for any
players $i\neq j$ as

$\displaystyle\Delta_{ij}$ $\displaystyle:\mathbb{R}^{2^{|N|}-1}\to\mathbb{R}\
,$ $\displaystyle v$ $\displaystyle\mapsto\phi(i,v)-\phi(j,v)\ .$

In other words, given a characteristic function $v$, $\Delta_{ij}(v)$ computes
the difference in Shapley value between players $i$ and $j$. Note that
$\Delta_{ij}$ is also a linear transform, by definition, and is thus
continuous. So, by the _continuous mapping theorem_ (CMT), if there is a
parametric Bayesian learning game $\bm{\mathcal{V}}^{m}$ s.t.
$\bm{\mathcal{V}}^{m}\overset{\textnormal{p}}{\longrightarrow}v$ for some game
$v$, then
$\Delta_{ij}(\bm{\mathcal{V}}^{m})\overset{\textnormal{p}}{\longrightarrow}\Delta_{ij}(v)$.
From Corollary 1, $\bm{\mathcal{V}}^{m}$ converges in probability to a game
that can be decomposed into three games $V_{1}+V_{2}+V$. $V_{1}$ and $V_{2}$
are vectors where all their entries are the same. By definition, if $v$ is a
vector with the same entries, then $\Delta_{ij}(v)=0$. Since $V$ is the game
$S\mapsto 0.5\log|\mathcal{I}_{S}|$,

$\displaystyle\Delta_{ij}(\bm{\mathcal{V}}^{m})$
$\displaystyle=\Delta_{ij}(\bm{\mathcal{V}}^{m})-\Delta_{ij}(V_{1})-\Delta_{ij}(V_{2})$
(by Definitions of $\Delta_{ij}(V_{1})$ and $\Delta_{ij}(V_{2})$)
$\displaystyle=\Delta_{ij}(\bm{\mathcal{V}}^{m}-(V_{1}+V_{2}))$ (by linearity
of $\Delta_{ij}$)
$\displaystyle\overset{\textnormal{p}}{\longrightarrow}\Delta_{ij}(V)$
$\displaystyle\text{(by Corollary \ref{cor:uniform_prior} \& CMT)}\ ,$

as required.

### Corollary 2

Note that since there are two players, the characteristic function can be
represented by a vector of three values. Consider a $2$-player cooperative
game where the characteristic function is given by
$V:=(0.5\log|\mathcal{I}_{1}|,0.5\log|\mathcal{I}_{2}|,0.5\log|\mathcal{I}_{12}|)$.
Suppose further that the determinant of both players’ Fisher information is
the same, i.e., $|\mathcal{I}_{1}|=|\mathcal{I}_{2}|$. By the symmetric
property, if the marginal contributions of the players to any other coalition
are the same, then their Shapley values are the same. The only other coalition
is the empty coalition and

$V(\\{1\\})-V(\\{\\})=\frac{1}{2}\log|\mathcal{I}_{1}|=\frac{1}{2}\log|\mathcal{I}_{2}|=V(\\{2\\})-V(\\{\\})\
.$

So, $\phi(1,V)-\phi(2,V)=0$. So, if $\bm{\mathcal{V}}^{m}$ is a parametric
Bayesian games for two players s.t. $|\mathcal{I}_{1}|=|\mathcal{I}_{2}|$,
then

$\displaystyle\phi(1,\bm{\mathcal{V}}^{m})-\phi(2,\bm{\mathcal{V}}^{m})$
$\displaystyle\overset{\textnormal{p}}{\longrightarrow}\phi(1,V)-\phi(2,V)$
(by Theorem 2) $\displaystyle=0\ .$

In general, in the case of $|\mathcal{I}_{1}|\neq|\mathcal{I}_{2}|$, if we
bundle $r_{1}$ of player $1$’s data points together and treat them as a single
point, we get a new Fisher information $r_{1}\mathcal{I}_{1}$ (similarly,
$r_{2}\mathcal{I}_{2}$ for player $2$). Therefore, if we set
$r_{1}:r_{2}={|\mathcal{I}_{2}|}^{1/k}:{|\mathcal{I}_{1}|}^{1/k}$, then

$|r_{1}\mathcal{I}_{1}|=r_{1}^{k}|\mathcal{I}_{1}|=\left(\sqrt[k]{\frac{|\mathcal{I}_{2}|}{|\mathcal{I}_{1}|}}\
r_{2}\right)^{k}\cdot|\mathcal{I}_{1}|=r_{2}^{k}|\mathcal{I}_{2}|=|r_{2}\mathcal{I}_{2}|\
.$

In other words, the new Fisher information are the same. This is equivalent to
having the total number of points shared by the players be proportional to
$r_{1}:r_{2}$, which implies that if in step $3$ of the framework, both
$\hat{\mathcal{I}}_{1}\overset{\textnormal{p}}{\longrightarrow}\mathcal{I}_{1}$
and
$\hat{\mathcal{I}}_{2}\overset{\textnormal{p}}{\longrightarrow}\mathcal{I}_{2}$,
then
$|r_{1}\mathcal{I}_{1}|-|r_{2}\mathcal{I}_{2}|\overset{\textnormal{p}}{\longrightarrow}0$
and the conclusion follows. In step $2$, as the number of iterations
increases, we have
$\hat{\mathcal{I}}_{1}\overset{\textnormal{p}}{\longrightarrow}\mathcal{I}_{1}(\bar{\theta})$
and
$\hat{\mathcal{I}}_{2}\overset{\textnormal{p}}{\longrightarrow}\mathcal{I}_{2}(\bar{\theta})$,
by the weak law of large numbers. Also, since we assume that $\bar{\theta}$ is
a consistent estimator, by the continuous mapping theorem,
$\hat{\mathcal{I}}_{1}\overset{\textnormal{p}}{\longrightarrow}\mathcal{I}_{1}$
and
$\hat{\mathcal{I}}_{2}\overset{\textnormal{p}}{\longrightarrow}\mathcal{I}_{2}$,
as required.

##  Appendix B Additional Experimental Details and Results

### Sharing Data Points in Learned Features with Neural Networks

King county housing sales prediction
(KingH)222https://www.kaggle.com/harlfoxem/housesalesprediction contains over
$21$K data of $21$ features. Age prediction from facial images (FaceA) (Zhang
et al., 2017) contains over $20$K face images of various sizes for people with
ages between $0$ and $116$. For KingH, we train a neural network with two
fully-connected layers of $64$ and $10$ hidden units with _rectified linear
units_ (ReLU) as the activation function. For FaceA, we train a convolutional
neural network with $3$ convolutional layers (with thefirst $2$ followed by
batch normalization and max pooling) and $3$ fully-connected layers
(respectively, with $1024$, $64$, $10$ hidden units). Then, we pass the
original data through the respective trained neural network models to
construct the features obtained after the last fully-connected layer of $10$
hidden units to construct features in the learned space of $10$ dimensions. We
find that there is a redundant extracted feature for the FaceA dataset
(containing all zeros), so it is dropped and the dimension for the extracted
features is $9$.

Details of experiment 1 on BLR. We will first describe how the real-world
datasets are used by players P$1$ and P$2$. P$1$ has a randomly selected
subset (of size P$1$_data) from the original dataset. P$2$ has a randomly
selected subset which is a fraction (P$2$_ratio) of the original dataset.
Furthermore, P$2$’s data has a proportion (P$2$_nan) of missing values which
are imputed with feature-wise average values.

Subsequently, a single data point $\mathbf{X}_{1j}$ of P$1$ is obtained as
follows: P$1$ samples P$1$_sample_size data points (e.g., housing records for
CaliH/KingH) with replacement from a restricted subset (of size P$1$_data) of
the original data, and uses these sampled P$1$_sample_size data points to
compute a least-squares solution as P$1$’s one data point $\mathbf{X}_{1j}$ in
the learning game. A single data point $\mathbf{X}_{2j}$ of P$2$ is obtained
from observing a noisy sample from
$\mathcal{N}(\hat{\theta}_{2},\mathbf{1}\times\sigma^{2})$ where
$\hat{\theta}_{2}$ is the least-squares solution from P$2$’s data (with
missing values imputed) and $\sigma$ is known.

Additional results for 2-player. Figs. 5 and 5 show the Shapley values and the
cumulative counts for KingH and MNIST_VAE, respectively. The statistics on
$\delta$ are tabulated in Tables 2, 3, 4, and 5 for the additional results on
CaliH, FaceA, KingH, and MNIST_VAE, respectively. Fig. 5 shows a similar trend
with previous results and verifies our result, while Fig. 5 displays more
fluctuations within the overall converging trend. Note from the setting for
Fig. 5 that though P$1$ has fewer data than P$2$, P$1$’s data are more
balanced between the two digits. The fluctuations in Fig. 5 suggest that
experiment $2$ is more difficult. This may be attributed to the fact that the
parameter estimates for linear regression (in experiment $1$) are more
analytically tractable than the mean estimates in a learned latent space
implicitly represented by a VAE.

From Table 3, we observe that for FaceA, the default setting seems to ‘favor’
P$2$: P$1$ needs more data to be able to contribute meaningfully (left table)
while increasing P$2$’s data further makes it hard for the Shapley values to
converge (right table). On the other hand, from Table 4, we observe that for
KingH, the default setting for both P$1$ and P$2$ ‘favors’ P$1$: Increasing
P$1$’s data further makes it harder for the Shapley values to converge (left
table) and P$2$ needs more data to be able to meaningfully contribute (right
table).

From Table 5 (left), we observe that as the bias in both players’ data is
comparable (first three rows), it takes fewer iterations for their Shapley
values to converge. However, as P$1$’s data becomes more balanced (last two
rows), it becomes more difficult for P$2$ to collect sufficient data points to
match, so it is more difficult for their Shapley values to converge. From
Table 5 (right), we observe that if the quantities of both players’ data
differ significantly, it is in general difficult for their Shapley values to
converge since all except one case (second row) were not able to converge
within $50$ iterations.

Figure 4: SV (cumulative count) vs. iterations on KingH where P$1$_data
$=1000$, P$1$_sample_size $=100$, P$1$’s sampling is iid, and P$2$_ratio $=$
P$2$_nan $=0.1$.

Figure 5: SV (cumulative count) vs. iterations on MNIST_VAE where P$1$_data
$=1000$, P$2$_data $=5000$, P$1$_ratio $=0.2$, and P$2$_ratio $=0.9$.

Table 2: Statistics on $\delta$ for CaliH with varying P$2$’s contributions.
Iter denotes the smallest number of iterations for $\delta$ to be smaller than
$0.1$ for $5$ consecutive iterations and * denotes cases where it is not
satisfied. Also, P$1$_data $=5000$, P$1$_sample_size $=500$, and P$1$’s
sampling is lvg_iid.

P$2$_nan | P$2$_ratio | Lowest | Average | StDev | Iter
---|---|---|---|---|---
0.05 | 0.01 | 0.000 | 0.041 | 0.009 | 5
0.10 | 0.01 | 0.001 | 0.018 | 0.009 | 5
0.40 | 0.01 | 0.000 | 0.008 | 0.006 | 5
0.05 | 0.10 | 0.013 | 0.025 | 0.005 | 5
0.10 | 0.10 | 0.016 | 0.032 | 0.006 | 5
0.40 | 0.10 | 0.000 | 0.007 | 0.006 | 5
0.05 | 0.50 | 0.063 | 0.074 | 0.009 | 8
0.10 | 0.50 | 0.093 | 0.109 | 0.009 | 50*
0.40 | 0.50 | 0.118 | 0.133 | 0.010 | 50*

Table 3: Statistics on $\delta$ for FaceA with varying P$1$’s (P$2$’s)
contributions on the left (right). Iter denotes the smallest number of
iterations for $\delta$ to be smaller than $0.1$ for $5$ consecutive
iterations and * denotes cases where it is not satisfied. For left table,
P$2$_ratio $=$ P$2$_nan $=0.1$. For right table, P$1$_data $=10000$,
P$1$_sample_size $=100$, and P$1$’s sampling is iid.

P$1$_data | P$1$_sample_size | sampling | Lowest | Average | StDev | Iter
---|---|---|---|---|---|---
1000 | 10 | iid | 0.392 | 0.427 | 0.031 | 50*
1000 | 10 | lvg_iid | 0.397 | 0.447 | 0.039 | 50*
1000 | 100 | iid | 0.006 | 0.025 | 0.006 | 5
1000 | 100 | lvg_iid | 0.000 | 0.005 | 0.004 | 5
1000 | 500 | iid | 0.055 | 0.067 | 0.007 | 5
1000 | 500 | lvg_iid | 0.017 | 0.036 | 0.008 | 5
5000 | 10 | iid | 0.377 | 0.429 | 0.033 | 50*
5000 | 500 | iid | 0.028 | 0.042 | 0.008 | 5
5000 | 500 | lvg_iid | 0.021 | 0.042 | 0.009 | 5

P$2$_nan | P$2$_ratio | Lowest | Average | StDev | Iter
---|---|---|---|---|---
0.05 | 0.01 | 0.065 | 0.080 | 0.011 | 13
0.10 | 0.01 | 0.065 | 0.084 | 0.011 | 16
0.40 | 0.01 | 0.065 | 0.088 | 0.013 | 24
0.05 | 0.10 | 0.008 | 0.021 | 0.007 | 5
0.10 | 0.10 | 0.016 | 0.030 | 0.006 | 5
0.40 | 0.10 | 0.029 | 0.044 | 0.007 | 5
0.05 | 0.50 | 0.097 | 0.115 | 0.014 | 50*
0.10 | 0.50 | 0.123 | 0.142 | 0.014 | 50*
0.40 | 0.50 | 0.167 | 0.187 | 0.016 | 50*

Table 4: Statistics on $\delta$ for KingH with varying P$1$’s (P$2$’s)
contributions on the left (right). Iter denotes the smallest number of
iterations for $\delta$ to be smaller than $0.1$ for $5$ consecutive
iterations and * denotes cases where it is not satisfied. For left table,
P$2$_ratio $=$ P$2$_nan $=0.1$. For right table, P$1$_data $=10000$,
P$1$_sample_size $=100$, and P$1$’s sampling is iid.

P$1$_data | P$1$_sample_size | sampling | Lowest | Average | StDev | Iter
---|---|---|---|---|---|---
1000 | 10 | iid | 0.000 | 0.015 | 0.011 | 5
1000 | 10 | lvg_iid | 0.000 | 0.015 | 0.014 | 5
1000 | 100 | iid | 0.000 | 0.005 | 0.004 | 5
1000 | 100 | lvg_iid | 0.000 | 0.005 | 0.005 | 5
1000 | 500 | iid | 0.033 | 0.173 | 0.024 | 50*
1000 | 500 | lvg_iid | 0.125 | 0.140 | 0.012 | 50*
5000 | 10 | iid | 0.000 | 0.015 | 0.013 | 5
5000 | 500 | iid | 0.133 | 0.159 | 0.011 | 50*
5000 | 500 | lvg_iid | 0.098 | 0.158 | 0.015 | 50*

P$2$_nan | P$2$_ratio | Lowest | Average | StDev | Iter
---|---|---|---|---|---
0.05 | 0.01 | 0.192 | 0.217 | 0.017 | 50*
0.10 | 0.01 | 0.189 | 0.207 | 0.014 | 50*
0.40 | 0.01 | 0.177 | 0.193 | 0.013 | 50*
0.05 | 0.10 | 0.000 | 0.005 | 0.004 | 5
0.10 | 0.10 | 0.000 | 0.006 | 0.006 | 5
0.40 | 0.10 | 0.000 | 0.005 | 0.005 | 5
0.05 | 0.50 | 0.000 | 0.006 | 0.004 | 5
0.10 | 0.50 | 0.000 | 0.009 | 0.006 | 5
0.40 | 0.50 | 0.000 | 0.010 | 0.006 | 5

Table 5: Statistics on $\delta$ for MNIST_VAE with varying P$1$’s (P$2$’s)
contributions on the left (right). Iter denotes the smallest number of
iterations for $\delta$ to be smaller than $0.1$ for $5$ consecutive
iterations and * denotes cases where it is not satisfied.

P$1$/P$2$_data | P$1$/P$2$_ratio | Lowest | Average | StDev | Iter
---|---|---|---|---|---
1000 / 1000 | 0.1 / 0.9 | 0.000 | 0.356 | 0.388 | 28
1000 / 1000 | 0.2 / 0.9 | 0.002 | 0.287 | 0.376 | 19
1000 / 1000 | 0.3 / 0.9 | 0.004 | 0.245 | 0.337 | 26
1000 / 1000 | 0.4 / 0.9 | 0.035 | 0.378 | 0.320 | 50*
1000 / 1000 | 0.5 / 0.9 | 0.004 | 0.418 | 0.447 | 50*

P$1$/P$2$_data | P$1$/P$2$_ratio | Lowest | Average | StDev | Iter
---|---|---|---|---|---
1000 / 5000 | 0.1 / 0.9 | 0.006 | 0.202 | 0.204 | 50*
1000 / 5000 | 0.2 / 0.9 | 0.007 | 0.226 | 0.332 | 38
1000 / 5000 | 0.3 / 0.9 | 0.000 | 0.345 | 0.366 | 50*
1000 / 5000 | 0.4 / 0.9 | 0.008 | 0.365 | 0.334 | 50*
1000 / 5000 | 0.5 / 0.9 | 0.006 | 0.329 | 0.334 | 50*

Additional results for multi-player. Figs. 8, 8, and 8 plot the Shapley values
and cumulative counts for CaliH, FaceA, and MNIST_VAE in multi-player
scenarios, respectively. It can be observed from Fig. 8 that the convergence
of the Shapley values is not very obvious, which corresponds to our previous
observations for the $2$-player scenario in Fig. 5 where there are more
fluctuations and suggests that this is a challenging setting.

Figure 6: SV (cumulative count) vs. iterations on CaliH for a multi-player
scenario where P$1$/P$3$_data $=1000$, P$1$/P$3$_sampling_size $=500$,
P$2$/P$4$_ratio $=0.05$, and P$2$/P$4$_nan $=0.3$.

Figure 7: SV (cumulative count) vs. iterations on FaceA for a multi-player
scenario where P$1$/P$3$_data $=5000$, P$1$/P$3$_sampling_size $=100$,
P$2$/P$4$_ratio $=0.1$, and P$2$/P$4$_nan $=0.2$.

Figure 8: SV (cumulative count) vs. iterations on MNIST_VAE for a multi-player
scenario where P$1$/P$3$_data $=1000$, P$1$_ratio $=0.1$, P$2$/P$4$_data
$=5000$, and P$2$_ratio $=0.1$.