11institutetext: Institute of Information Systems, University of Lübeck,
Germany 11email<EMAIL_ADDRESS>Institute for
Humanities-Centered AI (CHAI), University of Hamburg, Germany 22email:
<EMAIL_ADDRESS>
# Mechanisms for Data Sharing in Collaborative Causal Inference (Extended
Version)

Björn Filter 11 0009-0008-8666-6239 Ralf Möller 22 0000-0002-1174-3323 Özgür
Lütfü Özçep 22 0000-0001-7140-2574

###### Abstract

Collaborative causal inference (CCI) is a federated learning method for
pooling data from multiple, often self-interested, parties, to achieve a
common learning goal over causal structures, e.g. estimation and optimization
of treatment variables in a medical setting. Since obtaining data can be
costly for the participants and sharing unique data poses the risk of losing
competitive advantages, motivating the participation of all parties through
equitable rewards and incentives is necessary. This paper devises an
evaluation scheme to measure the value of each party’s data contribution to
the common learning task, tailored to causal inference’s statistical demands,
by comparing completed partially directed acyclic graphs (CPDAGs) inferred
from observational data contributed by the participants. The Data Valuation
Scheme thus obtained can then be used to introduce mechanisms that incentivize
the agents to contribute data. It can be leveraged to reward agents fairly,
according to the quality of their data, or to maximize all agents’ data
contributions.

###### Keywords:

Collaborative Causal Inference Data Evaluation Fairness Mechanism Design Data
Sharing

##  1 Introduction

Causal inference estimates the causal effect of treatment variables within a
particular population, a method widely adopted across various fields. In
healthcare, for example, it assesses the effectiveness of pharmaceutical
interventions [1] and explores gene effects on phenotypes [2]. It also finds
application in policy decision-making [3], recommender systems [4], education
[5], advertisement [6], agriculture [7], and numerous other domains.

Various methodologies for causal inference have emerged to analyze
interventional data, obtained from controlled experimental trials, or
observational data. However, their effectiveness can be hindered by data
quality issues, including data sparsity and non-representativeness. For
example, patient preferences for hospitals can limit each institution’s
records, causing biases and data sparsity. Thus, causal inference efforts by
single hospitals risk inaccurate treatment effect estimates, potentially
impeding optimal medication prescriptions [8].

Collaborative causal inference (CCI) leverages collective data pooling from
diverse agents, such as companies, organizations, or individuals, to tackle
data sparsity and non-representativeness challenges. This approach enhances
the precision of causal model estimations. Methods such as simple aggregation
or multi-source causal inference [9] yield accurate and statistically
significant estimates by utilizing data from all participants. However,
success depends on the willingness of agents to share data, which is not
always guaranteed. Entities often prioritize self-interest, hesitating to
share data due to associated collection costs.

As a concrete example consider the case of genetic research for predicting and
treating illnesses which relies on substantial amounts of data. Despite
decreasing costs, acquiring such data remains expensive [10]. Pooling genome
and gene expression data from multiple sources is crucial for accurate models,
especially when dealing with biased subpopulations. To achieve this, assessing
data quality and incentivizing parties based on it are necessary.

In this paper, we propose a mechanism for CCI aimed at motivating agents to
provide maximal amounts of data to gain access to a high-quality model. We
introduce a quantitative measure to assess data quality and each party’s
contribution to the collective model. This valuation scheme is tailored to the
unique requirements of statistical causal inference, where, in contrast to the
framework proposed by Karimireddy and colleagues [11], no ground truth is
available. Unlike the data valuation scheme introduced by Qiao and colleagues
[12], our method considers differences in estimated causal graph models and
probability distributions for causal effects among contributors’ data. The
resulting data valuation function incentivizes agents to maximize their data
contribution. Furthermore, it can also be used for the allocation of fair
incentives based on data quality, ensuring better causal estimators for agents
with higher-quality data.

An implementation of our data valuation scheme can be found at
https://github.com/bjofilter/Data-Valuation-CCI. This paper is an extended
version of a paper to be published in the proceedings of the 47th German AI
conference (KI 2024).

##  2 Preliminaries

We collect the basic notions and methods for causal structure learning.
Directed acyclic graphs (DAGs) can model conditional independencies. For a DAG
$\mathcal{D}=(\mathbf{V,E})$ let the vertices $\mathbf{V}={V_{1},...,V_{p}}$
correspond to a $p$-variate random vector $\mathbf{X}\in\mathbb{R}^{p}$, while
the edges $\mathbf{E}$ denote relationships between the variables they
connect. A probability function $P$ over $\mathbf{X}$ is called Markov
relative to a DAG $\mathcal{D}$ if it factorizes as
$P(x_{1},...,x_{p})=\prod_{i=1}^{p}P(x_{i}\mid Pa_{X_{i}}(\mathcal{D}))$,
where $Pa_{X_{i}}(\mathcal{D})$ are the parents of node $X_{i}$.

In causal inference, a DAG $\mathcal{D}$ is not only used to represent
associational but also causal relationships. Here, intuitively, the parents
$Pa_{V_{i}}(\mathcal{D})$ of a node $V_{i}\in\mathbf{V}$ can be interpreted as
the direct causes of $V_{i}$, and the children as the direct effects of
$V_{i}$. Such a model gives information about how a variable would change, if
its direct causes are changed, for example by external manipulation. To denote
such a manipulation, Pearl’s do-operator can be used: Let
$\mathcal{D}=(\mathbf{V},\mathbf{E})$ be a DAG that is Markov to a probability
distribution $P$ over a set of random variables
$\mathbf{V}=\\{V_{1},...,V_{p}\\}$. Let $V_{i},V_{j}\in\mathbf{V}$ be two
distinct variables and $v_{i},v_{i}$ the values of those variables. The causal
effect of $V_{i}$ on $V_{j}$ is denoted as $P(v_{j}\mid do(V_{i}=v_{i}))$,
where $do(V_{i}=v_{i})$ or short $do(v_{i})$ is an intervention that sets
$V_{i}=v_{i}$ [13].

Let $\mathbf{v}=(v_{1},...,v_{p})$ be a sequence of values of the variables
$\mathbf{V}$. $\mathbf{v}$ is consistent with $v^{\prime}_{i}$ if
$v_{i}=v_{i}^{\prime}$. Given a DAG $\mathcal{D}$, the distribution after an
intervention, called intervention distribution, can be expressed as follows:
$P_{\mathcal{D}}(\mathbf{v}\mid do(V_{i}=v^{\prime}_{i}))=$
$\prod_{j:V_{j}\neq V_{i}}P(v_{j}\mid Pa_{V_{j}}(\mathcal{D}))$ if
$\mathbf{v}$ is consistent with $v^{\prime}_{i}$, else set $=0$.

The total causal effect of $V_{i}$ on $V_{j}$ is written as $P(V_{j}\mid
do(V_{i}))$ and is defined as the probability distribution of $V_{j}$ after
the intervention at $V_{i}$.

A linear structural equation model (SEM) $\mathcal{M}$ comprises endogenous
variables $\mathbf{V}=\\{V_{1},...,V_{p}\\}$, exogenous variables
$\mathbf{U}=\\{U_{1},...,U_{p}\\}$, and a joint distribution $P_{M}$ over
$\mathbf{U}$, with structural assignments $V_{j}=\sum_{i<j}c_{ij}V_{i}+U_{j}$
(for $j=1,...,p$) defining direct causal effects between variables. When
dealing with observational data that is assumed to have been created by an
underlying SEM, various algorithms exist to estimate the underlying DAG, like
for example the PC algorithm [14] or GES (greedy equivalence search) [15].
However, most algorithms for estimating a DAG from observational data cannot
distinguish between two DAGs that are Markov equivalent (two DAGs
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are said to be Markov equivalent if
they encode the same set of conditional independencies [16]). Instead, one can
only identify the Markov equivalence class (MEC) of DAGs. This is represented
by a _Completed Partially Directed Acyclic Graph (CPDAG)_ , which has a
directed edge between two nodes if such an edge is present in all the DAGs
belonging to the MEC and an undirected edge between two nodes if edges in both
directions are present among DAGs in the MEC. The set of consistent DAG
extensions of $\mathcal{C}$, $CE(\mathcal{C})$, consists of all DAGs
represented by $\mathcal{C}$. We define the intervention distribution of
causal effects given a CPDAG $\mathcal{C}$ as follows:

$\displaystyle P_{\mathcal{C}}(\mathbf{v}\mid
do(V_{i}=v^{\prime}_{i}))=\sum_{\mathcal{D}\in
CE(\mathcal{C})}\frac{1}{|CE(\mathcal{C})|}P_{\mathcal{D}}(\mathbf{v}\mid
do(V_{i}=v^{\prime}_{i}))$ (1)

When a CPDAG $\mathcal{C}$ has been estimated, the IDA algorithm
(Intervention-calculus when the DAG is Absent) [17] can be used to estimate
the causal effect of a variable $V_{i}\in\mathbf{V}$ on another variable
$V_{j}\in\mathbf{V}$. This algorithm estimates the multiset $\Theta^{ij}$ of
all possible causal effects of $V_{i}$ on $V_{j}$ given the MEC described by
$\mathcal{C}$, i.e. the effects described by all possible DAGs $\mathcal{D}\in
CE(\mathcal{C})$. The basic idea behind the IDA algorithm is to determine all
DAGs $\mathcal{D}\in CE(\mathcal{C})$ for a given CPDAG $\mathcal{C}$. In each
of these DAGs, the parents of $V_{i}$ can be used as a so-called adjustment
set [13] (see also appendix 0.A) to estimate the _average causal effect (ACE)_
$\tau^{ij}(\mathcal{D})$, which is defined as
$\tau^{ij}(\mathcal{D})=E(V_{j}\mid do(V_{i}=v_{i}+1))-E(V_{j}\mid
do(V_{i}=v_{i}))$, where $E(V_{j}\mid do(V_{i}=v_{i}))$ stands for the
expected value of $V_{j}$ after the intervention $do(v_{i})$. The ACE can be
estimated by performing the regression of $V_{j}$ on $V_{i}$ and
$Pa_{V_{i}}(\mathcal{D})$, denoted $\beta_{V_{i}|Pa_{V_{i}}(\mathcal{D})}$ as
follows:

$\displaystyle\beta_{V_{i}|Pa_{V_{i}}(\mathcal{D})}=\begin{cases}0&\text{if
$V_{j}\in Pa_{V_{i}}(\mathcal{D})$},\\\ \text{coefficient of $V_{i}$ in
$V_{j}\sim V_{i}+Pa_{V_{i}}(\mathcal{D})$}&\text{if $V_{j}\notin
Pa_{V_{i}}(\mathcal{D})$},\end{cases}$ (2)

where $V_{j}\sim V_{i}+Pa_{V_{i}}(\mathcal{D})$ stands for the linear
regression of $V_{j}$ on $V_{i}$ and $Pa_{V_{i}}(\mathcal{D})$ [17]. Thus
$\beta_{V_{i}|Pa_{V_{i}}(\mathcal{D})}$ describes a Gaussian distribution
$\hat{\theta}^{ij}_{Pa_{V_{i}}(\mathcal{D})}$ consisting of the estimated
effect $\hat{\tau}^{ij}_{Pa_{V_{i}}(\mathcal{D})}$ and the standard error
$\hat{\sigma}^{ij}_{Pa_{V_{i}}(\mathcal{D})}$. Since only the parents of
$V_{i}$ are used to estimate the effect, DAGs in which $V_{i}$ has the same
parents yield the same effect. However, in DAGs with different parents, the
estimated causal effect can be different. Thus, a regression has to be
performed for each of the possible parent sets of $V_{i}$ given $\mathcal{C}$.
Let
$\mathbf{Pa}_{V_{i}}(\mathcal{C})=\\{Pa_{V_{i}}(\mathcal{D})|\mathcal{D}\in
CE(\mathcal{C})\\}$. The estimated causal effect of $V_{i}$ on $V_{j}$ given
CPDAG $\mathcal{C}$ is given by the weighted sum over all possible sets of
parents for $V_{i}$:

$\displaystyle\hat{\theta}^{ij}=\sum_{\mathbf{Z}\in\mathbf{Pa}_{V_{i}}(\mathcal{C})}\frac{|\\{\mathcal{D}\in
CE(\mathcal{C})|Pa_{V_{i}}(\mathcal{D})=\mathbf{Z}\\}|}{|CE(\mathcal{C})|}\hat{\theta}^{ij}_{\mathbf{Z}},$
(3)

that is, the mixture model obtained by summing over all effects induced by a
parent-set in $\mathbf{Pa}_{V_{i}}(\mathcal{C})$, divided by the fraction of
DAGs in $CE(\mathcal{C})$ in which $V_{i}$ has that set of parents.

##  3 Collaborative Causal Inference

We assume, that $n$ self-interested agents $N:=\\{1,...,n\\}$ want to solve a
common causal inference problem by estimating a CPDAG and using observational
data of $p$ variables, $\mathbf{V}=\\{V_{1},...,V_{p}\\}$ to estimate causal
effects between variable-pairs $(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$.
Furthermore, agents are non-malicious and they may acquire data from different
and potentially biased populations, but these data collectively form the
common target population of interest. Each agent $i\in N$ can produce data
points $D_{i}$ for a fixed cost $c_{i}>0$ per data point. Both single agents
as well as coalitions of agents use their available data to infer a CPDAG
$\mathcal{C}=\left(\mathbf{V},\mathbf{E}_{\mathcal{C}}\right)$ and then infer
the causal effects using the IDA algorithm. We will make the rather strict
assumption, that all agents are equally interested in all effects between all
possible variable pairs $(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$.

Let $N$ denote the grand coalition containing all agents and let $C\subseteq
N$ denote some coalition of agents. $D_{C}$ denotes the data provided by
coalition $C$. Let
$\mathcal{E}(D_{C})=\mathcal{E}_{C}=\left(\mathcal{C}_{C},\hat{\Theta}_{C}\right)$
be the estimator computed from $D_{C}$ as described in Section 2. It consists
of an estimated CPDAG $\mathcal{C}_{C}$ and the estimated distributions of
causal effects
$\hat{\Theta}_{C}=\\{\hat{\theta}^{ij}_{C}\mid(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}\\}$.
To simplify notation, the subscript $C$ is replaced by index $i$ when
$C=\\{i\\}$. Thus, $D_{C}=\cup_{i\in C}D_{i}$.

In the following, it will be necessary for agents and coalitions, to know the
quality of their estimators, to calculate their improvement rate, and to
allocate fair incentives to agents. Therefore let
$v:\mathcal{E}_{\mathcal{C}}\times\mathcal{E}_{B}\rightarrow\mathbb{R}$ be the
valuation function for the estimator $\mathcal{E}_{\mathcal{C}}$, which will
be defined in the next chapter. It evaluates an estimator against the
benchmark estimator $\mathcal{E}_{B}$ (usually the estimator obtained from the
data available to the grand coalition). We can use this to define a reward
value for each agent $i\in N$, denoted as $r_{i}$. The goal is to reward each
agent’s data contribution with an estimator $\mathcal{E}_{i}$, such that the
quality of $\mathcal{E}_{i}$ corresponds to the valuation of $i$’s data
contribution $D_{i}$, which will be measured using the function $v$.

##  4 Data Valuation Scheme

We assume coalitions are interested in both the inferred CPDAG $\mathcal{C}$,
as well as the estimated distributions of causal effects $\hat{\theta}^{ij}$
for all pairs of variables $(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$. In
practice, the ground truth CPDAG and causal effects are unknown quantities and
must be inferred from the observed data. The best available estimate for these
are the CPDAG and estimated distributions computed using all data available to
the grand coalition $N$, due to the asymptotic consistency of the estimators
[14]. Thus, we will usually treat the grand coalition estimates of the CPDAG
$\mathcal{C}_{N}$ as the surrogate for the CPDAG of the true underlying DAG,
similarly, for all $V_{i},V_{j}\in\mathbf{V}\times\mathbf{V}$, we use
$\hat{\theta}^{ij}_{N}$ (the estimated distributions using the grand
coalitions’ data) as the surrogate for the ground truth population ACE
$\theta^{ij}$.

Different CPDAGs often yield vastly different effects. Suppose we have two
CPDAGs, $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, over the same set of
variables $\mathbf{V}$, and we are interested in the possible causal effects
of $V_{i}\in\mathbf{V}$ on $V_{j}\in\mathbf{V}\setminus\\{V_{i}\\}$. To infer
these, one has to determine the sets $\mathbf{Pa}_{V_{i}}(\mathcal{C}_{1})$
and $\mathbf{Pa}_{V_{i}}(\mathcal{C}_{2})$ and has to use these to calculate
the possible causal effects (see Section 2).

Therefore, to evaluate the data of a coalition $C\subseteq N$, we propose to
first take into account the difference between the CPDAG estimated by that
coalition, $\mathcal{C}_{C}=(V,E_{C})$ and the grand coalition estimates of
the CPDAG $\mathcal{C}_{N}=(V,E_{N})$. To do this, we introduce a measure
extending the measure of _structural intervention distance (SID)_ [18]. We
will call this the _distribution-SID (dSID)_. It is the number of node-pairs
$V_{i},V_{j}$, for which the distribution of causal effects of $V_{i}$ on
$V_{j}$ given $\mathcal{C}_{1}$ is different from the distribution given
$\mathcal{C}_{2}$. For a discussion of the SID and other possible distance
measures from the literature see Section 7 on related work. We show how the
dSID can be computed in appendix 0.A.

######  Definition 1 (Distribution Structural Intervention Distance (dSID))

Let $\mathbb{G}$ be the space of CPDAGs over $p$ variables. We then define

$\displaystyle dSID:\text{ }$ $\displaystyle\mathbb{G}\times\mathbb{G}$
$\displaystyle\rightarrow\mathbb{N}$
$\displaystyle(\mathcal{C}_{1},\mathcal{C}_{2})$
$\displaystyle\mapsto|\\{(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V},V_{i}\neq
V_{j}\mid\text{the distribution of causal}$ $\displaystyle\text{effects of
$V_{i}$ on $V_{j}$ is falsely identified in $\mathcal{C}_{1}$ with respect to
$\mathcal{C}_{2}$}\\}|$

This leads to the first part of our data valuation measure. Let $\mathcal{E}$
be an estimator, consisting of a CPDAG
$\mathcal{C}_{\mathcal{E}}=(\mathbf{V},\mathbf{E})$ and the estimated
distributions $\hat{\theta}^{ij}_{\mathcal{E}}$ for all pairs of variables
$V_{i},V_{j}\in\mathbf{V}\times\mathbf{V}$. Further, let $\mathcal{B}$ be a
benchmark estimator (usually the estimator obtained from dataset $D_{N}$ of
the grand coalition), also consisting of a CPDAG
$\mathcal{C}_{\mathcal{B}}=(\mathbf{V},\mathbf{E}^{\prime})$ and distributions
$\hat{\theta}^{ij}_{\mathcal{B}}$. Let

$\displaystyle
v_{dSID}(\mathcal{E},\mathcal{B}):=-\frac{dSID(\mathcal{C}_{\mathcal{E}},\mathcal{C}_{\mathcal{B}})}{|\mathbf{V}|\cdot|\mathbf{V}-1|}.$
(4)

The $v_{dSID}$ metric can therefore be seen as the percentage amount of
variable pairs, for which the intervention distribution of causal effects
differ between $\mathcal{C}_{\mathcal{E}}$ and $\mathcal{C}_{\mathcal{B}}$.
Its maximum value is 0, if all intervention distributions in the two CPDAGs
are identical, and its minimum is $-1$ if all are different.

We will refine the $v_{dSID}$, because even for pairs of variables for which
the distribution of causal effects is correctly identified in
$\mathcal{C}_{\mathcal{E}}$ with respect to (wrt) $\mathcal{C}_{\mathcal{B}}$,
the estimated effect distributions $\theta^{ij}_{\mathcal{E}}$ and
$\theta^{ij}_{\mathcal{B}}$ can differ since they are computed by regression
using different datasets. Thus, we adopt the method proposed by Qiao and
colleagues [12], using the negative reverse Kullback-Leibler (KL) divergence.
It quantifies, how much one probability distribution differs from another
probability distribution.

For each pair of variables $V_{i},V_{j}$ where $\mathcal{C}_{\mathcal{E}}$ and
$\mathcal{C}_{\mathcal{B}}$ identify the same causal effects, the IDA
algorithm will yield relatively similar estimated causal effects. In contrast
to the approach of Qiao and colleagues [12], however, for a given variable-
pair $(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$, we are not dealing with one
causal effect described by a Gaussian distribution, but a distribution over
several effects. The mixture model given by the sum of these distributions
then describes the effect distribution $\hat{\theta}^{ij}_{\mathcal{E}}$ (see
Equation 3). This can then be compared to the mixture model of possible causal
effects from the benchmark estimator $\mathcal{B}$,
$\hat{\theta}^{ij}_{\mathcal{B}}$. Define
$\mathbf{A}=\\{(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V},V_{i}\neq V_{j}|$
the distribution of causal effects from $V_{i}$ to $V_{j}$ is correctly
identified in $\mathcal{C}_{\mathcal{E}}$ wrt $\mathcal{C}_{\mathcal{B}}\\}$.
We can now define the second part of our data valuation method:

$\displaystyle
v_{-KL}(\mathcal{E},\mathcal{B})=\frac{\sum_{(V_{i},V_{j})\in\mathbf{A}}-KL\left(\hat{\theta}^{ij}_{\mathcal{E}}||\hat{\theta}^{ij}_{\mathcal{B}}\right)}{\big{|}\mathbf{A}\big{|}}.$
(5)

Lastly, we propose the combination of $v_{dSHD}$ and $v_{-KL}$ as the final
data valuation function:

$\displaystyle
v(\mathcal{E},\mathcal{B})=v_{dSHD}(\mathcal{E},\mathcal{B})+v_{-KL}(\mathcal{E},\mathcal{B}).$
(6)

When $\mathcal{C}_{\mathcal{E}}$ and $\mathcal{C}_{\mathcal{B}}$ identify the
same distribution of causal effects for a variable pair
$(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$, the underlying data sets must be
similar concerning the effects between these variables. Thus the negative KL-
divergence between $\hat{\theta}^{ij}_{\mathcal{E}}$ and
$\hat{\theta}^{ij}_{\mathcal{B}}$ is relatively small. Consequently,
$v_{-KL}$-values are typically much smaller than $v_{dSHD}$-values. Because
differences in CPDAGs can lead to vastly different causal effects, this is
more significant than an effect, that is identically identified by both
CPDAGs, but then slightly differently estimated from the regressions given
coalitions different data sets. Thus, $v_{dSHD}$ makes up a significantly
larger part of our date valuation measure than the relatively small $v_{-KL}$.
Intuitively, the $v$ measure can be seen as a measure of the difference of the
estimated CPDAGs, degraded by the difference of the estimated effects.

##  5 Modeling an Individual Agent

To understand how agents will behave in a multi-agent setting, we first
consider the case of a single agent $i\in N$. In this case, the agent only has
access to the data he produces himself and the estimator arising from this
data. We will assume that each agent $i$ has a marginal fixed cost $c_{i}>0$
for producing a data point. Thus his cost for producing data $D_{i}$ is
$cost_{i}(D_{i})=c_{i}|D_{i}|$.

Using data $D_{i}$, agent $i$ will be able to produce some estimator
$\mathcal{E}_{i}$. However, there is no benchmark to assess the quality of
$\mathcal{E}_{i}$ without access to more data. Thus, agent $i$ can only
evaluate the quality of his estimator based on estimators he has produced
before, using a subset of his current data. Let $T=\\{1,2,...\\}$ be a series
of timestep. For each $t\in T$, let $D_{i}^{t}$ be the data produced so far by
$i$ at timestep $t$ with $D_{i}^{t-1}\subseteq D_{i}^{t}$ for all $t>1$. Let
$\mathcal{E}\left(D_{i}^{t}\right)=\mathcal{E}_{i}^{t}$ be the estimator
obtained by agent $i$ at time $t$ (using data $D_{i}^{t}$).

For the rest of this paper, we will assume that an agent will compare his
current estimator to the estimators he produced before, using the current
estimator as the benchmark (the current estimator presents his best knowledge
of the real distribution underlying the data). The agent will act according to
how much his estimator improved from older versions. If the improvement rate
is judged as too small by the agent, he will decide that further improvements
are not worth the cost and thus stop producing further data. We will assume,
that for as long as an agent produces data, he will produce the same amount of
data at every timestep. Let $\Delta_{i}$ denote this amount of data, thus for
all $t>1$, $|D_{i}^{t}\setminus D_{i}^{t-1}|=\Delta_{i}$. So while producing
data, at every timestep $i$ occurs additional cost $c_{i}\Delta_{i}$.

$v(\mathcal{E}_{i}^{t^{\prime}},\mathcal{E}_{i}^{t})$ assesses the discrepancy
between estimators $\mathcal{E}_{i}^{t^{\prime}}$ and $\mathcal{E}_{i}^{t}$,
with 0 indicating identical CPDAGs and causal effect distributions, and -1
indicating completely different CPDAGs. Conversely,
$-v(\mathcal{E}_{i}^{t^{\prime}},\mathcal{E}_{i}^{t})$ measures the
improvement in estimator quality from $\mathcal{E}_{i}^{t^{\prime}}$ to
$\mathcal{E}_{i}^{t}$, with $0$ denoting no improvement and $1$ completely
different estimators.

While the PC algorithm’s asymptotic consistency guarantees eventual
convergence to the true underlying distribution with sufficient data [17],
noise in early-stage data may not consistently improve estimator quality over
time, Thus,
$v(\mathcal{E}_{i}^{t^{\prime}},\mathcal{E}_{i}^{t})>v(\mathcal{E}_{i}^{t^{\prime}-1},\mathcal{E}_{i}^{t})$
is not guaranteed for every $t,t^{\prime}\in T$ with $t>t^{\prime}>1$. For
this reason, it makes sense for an agent to not only take into account the
improvement from the last estimator to the current one,
$v(\mathcal{E}_{i}^{t-1},\mathcal{E}_{i}^{t})$ but also the average
improvement rate from older estimators towards the current one:
$\frac{-v(\mathcal{E}_{i}^{t^{\prime}},\mathcal{E}_{i}^{t})}{t-t^{\prime}}$.
With this, we can define the improvement rate as follows:

$im_{i}(t):=\frac{1}{t-1}\sum_{t^{\prime}\in\\{1,...,t-1\\}}\frac{-v(\mathcal{E}_{i}^{t^{\prime}},\mathcal{E}_{i}^{t})+v\left(\mathcal{E}_{i}^{t},\mathcal{E}_{i}^{t}\right)}{t-t^{\prime}},$
(7)

This can be seen as the average rate of improvement in model quality towards
$\mathcal{E}_{i}^{t}$ per timestep, with $im_{i}(t)\in[0,1]$ for all $t$. We
assume that $i$ will gain some utility $u_{i}$ from the estimator improvement.
We will assume that the utility increases linearly with increasing estimator
quality. From this utility, we subtract the cost of producing $\Delta_{i}$
data points and thus get agent $i$’s utility at time $t$ by:

$\displaystyle u_{i}(t):=im_{i}(t)-c_{i}\Delta_{i}$ (8)

Finally, we will assume that agent $i$ will continue to produce data as long
as his utility is not shrinking and stop producing once his utility is
decreasing. That is, at the first $t\in T$, for which
$im_{i}(t)-c_{i}\Delta_{i}<0$, $i$ with stop producing data. Then the behavior
of a single agent will be as follows:

######  Definition 2 (Optimal Data Production)

Let $T=\\{1,2,...\\}$ be an infinite series of timestamps and $i\in N$ an
agent. Let $t_{i}^{s-opt}\in T$ be the unique timestamp, such that for all
$t<t_{i}^{s-opt}$ $im_{i}(t)-c_{i}\Delta_{i}\geq 0$ and
$im_{i}(t_{i}^{s-opt})-c_{i}\Delta_{i}<0$. Then the optimal data production
for $i$ is $D_{i}^{t_{i}^{s-opt}}$. For producing this data, $i$ will incur
cost $c_{i}|D_{i}^{t_{i}^{s-opt}}|=c_{i}\Delta_{i}t_{opt}$.

Since $i$ stops producing further data after $t_{i}^{s-opt}$, we have
$D_{i}^{t^{\prime}_{i}}=D_{i}^{t_{i}^{s-opt}}$ for all
$t^{\prime}_{i}>t_{i}^{s-opt}$.

##  6 Modeling Multiple Agents

We will now study how agents behave in a collaborative setting as described in
Section 3, where multiple agents produce data and the resulting model can be
shared. In this framework, a server mediates the interaction between agents.
First, the server publishes the mechanism to the agents, then, at each
timestep $t$, each agent $i$ contributes some data $D_{i}^{t}$ to the server
and finally, the server in turn rewards the agents with an estimator
$\mathcal{E}_{i}^{t}$ of a certain quality. The server also provides agents
with the opportunity to check the quality of any estimator they possess, that
is, at time $t$ the server computes
$v(\mathcal{E}_{i}^{t^{\prime}},\mathcal{E}_{N}^{t})$ for any estimator
$\mathcal{E}_{i}^{t^{\prime}}$ which $i$ received at some time $t^{\prime}\leq
t$. This way, $i$ can always check the improvement rate of models he received
so far, compared to the best available estimator at the time.

For time steps $T=\\{1,2,...\\}$ let
$\mathbf{D}^{t}=\\{D_{1}^{t},...,D_{n}^{t}\\}$ be the data provided by agents
$1$ to $n$ at time t. A _mechanism_ is formalized as a function
$\mathcal{M}(\mathbf{D}):D_{1}\times...\times
D_{n}\rightarrow\mathcal{E}_{1}\times...\times\mathcal{E}_{n}$, which maps the
agents’ contributions to estimators they receive from the mechanism. At $t$,
so far each agent $i$ generated and transmitted data $D_{i}^{t}$ to the
server. For this, he is rewarded with an estimator $\mathcal{E}_{i}^{t}$ of
quality $v(\mathcal{E}_{i}^{t},\mathcal{E}_{N}^{t})$. From now on,
$\mathcal{E}_{i}^{t}$ will denote the estimator $i$ receives at $t$ from the
server, while $\tilde{\mathcal{E}}_{i}^{t}$ will denote the estimator obtained
only from $i$’s data $D_{i}^{t}$. The first requirement for such a mechanism
is, for it to be feasible: A mechanism which returns an estimator
$\mathcal{E}_{i}^{t}$ to agent $i$ is said to be feasible if for any $i\in N$
and any $D_{i}^{t}$, it satisfies
$v(\mathcal{E}_{i}^{t},\mathcal{E}_{N}^{t})\leq
v(\mathcal{E}_{N}^{t},\mathcal{E}_{N}^{t})$. Feasibility is necessary to make
sure that the mechanism does not return an estimator that is better than the
estimator obtained by pooling all available data, $\mathcal{E}_{i}^{t}$. But
since $\mathcal{E}_{i}^{t}$ is always our benchmark to which every other
estimator is compared, by definition for any estimator
$v(\mathcal{E}^{\prime},\mathcal{E}_{N}^{t})\leq 1$, while
$v(\mathcal{E}_{N}^{t},\mathcal{E}_{N}^{t})=1$, thus feasibility always holds.

The second requirement for our mechanism is individual rationality (IR), which
is defined as follows: Given data contributions $\mathbf{D}^{t}$ by the
agents, the mechanism provides an estimator $\mathcal{E}_{i}^{t}$ to agent
$i$. Such a mechanism $\mathcal{M}$ is said to satisfy IR if for any agent
$i\in N$ and any contribution $\mathbf{D}^{t}$, it holds that
$v(\mathcal{E}_{i}^{t},\mathcal{E}_{N}^{t})\geq
v(\tilde{\mathcal{E}}_{i}^{t},\mathcal{E}_{N}^{t})$. Thus individual
rationality guarantees that no agent will obtain a worse estimator than they
would have obtained if they were working independently. IR is necessary to
guarantee that all rational agents will participate in the mechanism.

###  6.1 Standard Collaborative Setting

We first examine the most basic setting for collaborative causal inference.
Here, each agent immediately has access to the model of the grand coalition,
obtained from all data available to the mechanism at time $t$,
$\mathcal{E}_{N}^{t}$. Thus at all $t\in T$ and for all $i\in N$:
$[\mathcal{M}(\mathbf{D}^{t})]_{i}=\mathcal{E}^{t}_{N}$. This mechanism is
feasible and also satisfies individual rationality since
$v(\mathcal{E}_{N}^{t},\mathcal{E}_{N}^{t})\geq
v(\tilde{\mathcal{E}}_{i}^{t},\mathcal{E}_{N}^{t})$. We will assume that
agents will behave as they would if they were to act on their own. That is, at
each time step an agent $i\in N$ will produce and contribute some data to the
mechanism and then evaluate, how much the estimator of the grand coalition has
improved through their data contribution. If this improvement makes up for the
cost $i$ incurred, he will continue to produce data, until the improvement
does not outweigh their cost anymore. When first entering the mechanism, $i$
will contribute initial data $D^{1}_{i}$, since he does not know yet, how much
this data will improve the grand coalition’s estimator. After that, at each
timestep $t>1$, $i$ will compute the improvement rate $im_{i}(t)$ according to
Equation 7, but now comparing estimators of the grand coalitions at times
$t^{\prime}<t$ to the current estimator $\mathcal{E}_{N}^{t}$.

Again, $i$’s utility is calculated as
$u_{i}(t):=\sum_{t^{\prime}\in\\{1,...,t\\}}\left(im_{i}(t)-c_{i}\Delta_{i}\right)$,
and agent $i$ will continue to produce data as long as this is not decreasing
and stop producing once it decreases. Thus the behavior of an agent $i$ in the
standard collaborative setting will be as described in definition 2. However,
we will denote the optimal time for agent $i$ to stop producing further data
in the collaborative setting by $t_{i}^{opt}$, as opposed to $t_{i}^{s-opt}$
in the single agent setting.

###  6.2 Data Maximizing Mechanism

We will now present a mechanism that maximizes the data provided by all agents
$i\in N$. A mechanism $\mathcal{M}$ is data-maximizing given costs
$\mathbf{c}=\\{c_{1},...,c_{n}\\}$ if it maximizes the data collected at
equilibrium. Since at each timestep $i$ produces a fixed amount of data
$\Delta_{i}$, the total amount of data provided by agent $i$ is
$t^{opt}_{i}\Delta_{i}$

######  Definition 3 (Data Maximization)

A mechanism $\hat{\mathcal{M}}$ is data-maximizing if
$\hat{\mathcal{M}}\in\operatorname*{arg\,max}_{\mathcal{M}}\sum_{i\in
N}\left[t^{opt}_{i}\Delta_{i}\right]$, i.e., if it maximizes the amount of
data collected, subject to $\hat{\mathcal{M}}$ being feasible and satisfying
IR.

To maximize contributions, we need to make sure agents produce data for as
long as possible. To achieve this, we will reward them at every time step with
an estimator which is just good enough for them not to achieve a decrease in
utility. We will do this for as long as we can provide such an estimator,
given access to all the data contributed by the grand coalition. Following the
design described by Karimireddy and colleagues [11], we propose the following
mechanism. Now

$\displaystyle
im_{i}(t)=\frac{1}{t-1}\sum_{t^{\prime}\in\\{1,...,t-1\\}}\frac{-v\left(\mathcal{E}_{i}^{t^{\prime}},\mathcal{E}_{N}^{t}\right)+v\left(\mathcal{E}_{i}^{t},\mathcal{E}_{N}^{t}\right)}{t-t^{\prime}},$
(9)

as in equation 7, $im_{i}(t)$ measures the improvement towards the quality of
the last model $i$ has received, $\mathcal{E}_{i}^{t}$, however, this does not
have to be the best possible model $\mathcal{E}_{N}^{t}$. Now we can formulate
our data-maximizing mechanism:

$\displaystyle[\mathcal{M}(\mathbf{D}^{t})]_{i}=\begin{cases}\tilde{\mathcal{E}^{t}_{i}}&\text{if
}t<t^{s-opt}_{i}\\\ \mathcal{E}^{t}_{i},\text{such that
}im_{i}(t)=c_{i}\Delta_{i}+\epsilon&\text{else, if such $\mathcal{E}^{t}_{i}$
exists}\\\ \mathcal{E}_{N}&\text{else}.\end{cases}$ (10)

Even without external incentivization, $i$ will continue to produce data until
$t^{s-opt}_{i}$. From here on, $i$ will receive a model $\mathcal{E}^{t}_{i}$
such that the improvement rate just makes up for his incurred cost, so that
his utility does not decrease. At some point, $i$ will receive the best
possible model $\mathcal{E}^{t}_{N}$ or something very close to this, so it is
no longer possible to keep the average improvement rate over
$c_{i}\Delta_{i}$. Now, $i$ will receive the best possible model and no
further incentivization is possible. This leads to the result expressed in the
following theorem.

######  Theorem 6.1 (Data maximization with known costs)

The mechanism $\mathcal{M}$ defined by equation 10 is data-maximizing for
$\epsilon\rightarrow 0^{+}$. A rational agent $i$ will contribute
$\Delta_{i}t_{i}^{opt}$ data points where
$\Delta_{i}t_{i}^{opt}\geq\Delta_{i}t_{i}^{s-opt}$, yielding a total of
$\sum_{j\in N}\Delta_{j}t_{j}^{opt}$ data points.

A proof for Theorem 6.1 is presented in Appendix 0.B.

###  6.3 Achieving Fairness

While the mechanism described above maximizes the amount of data extracted
from each agent, it does not satisfy fairness. In parallel to work done by
Qiao and colleagues [12], we can use our data valuation function
$v(\mathcal{E},\mathcal{B})$, to design a reward scheme $r_{i}^{t}$ for every
agent $i\in N$ at each time $t\in T$, which fulfills the following fairness
conditions defined in the work of Qiao and colleagues [12]. At each $t\in T$,
let $v^{t}_{\emptyset}:=min_{i\in
N}v(\mathcal{E}^{t}_{i},\mathcal{E}^{t}_{N})$ for the empty coalition
$C=\emptyset$. Then:

  * •

(F1) Uselessness: Agent $i$ should receive a valueless reward if his data does
not improve the estimator of any other coalitions.

  * •

(F2) Symmetry: If two agents yield the same improvement for all other
coalitions, then they should receive equally valuable estimates as rewards.

  * •

(F3) Strict Desirability: If data from agent $i$ strictly improves the
estimate for at least one coalition more than that of agent $j$, but the
reverse is not true, then agent $i$ should receive a more valuable reward than
agent $j$.

  * •

(F4) Monotonicity: For an agent $i$, if his dataset $D_{i}$ strictly improves
the estimate for at least one coalition more compared to that of another
dataset $D_{i^{\prime}}$, but the reverse is not true, then sharing $D_{i}$
should give agent $i$ more valuable reward than sharing $D_{i^{\prime}}$.

At each $t\in T$, let $v^{t}_{\emptyset}:=min_{i\in
N}v(\mathcal{E}^{t}_{i},\mathcal{E}^{t}_{N})$ for the empty coalition
$C=\emptyset$. The marginal contribution $m^{t}_{i}(T)$ of the data of agent
$i$ to a coalition $T\subseteq N$ at time $t$ is then defined as
$m^{t}_{i}(T):=v(\mathcal{E}^{t}_{T\cup\\{i\\}},\mathcal{E}^{t}_{N})-v(\mathcal{E}^{t}_{T},\mathcal{E}^{t}_{N})$,
with $\mathcal{E}^{t}_{N}$ being the estimator obtained from all data
available to the grand coalition $N$. As proposed by Qiao and colleagues, the
Shapley Value (SV) can then be calculated as
$\phi^{t}_{i}:=\frac{1}{|N|!}\sum_{T\subseteq
N\setminus\\{i\\}}|T|!\cdot\left(|N|-|T|-1\right)!\cdot m^{t}_{i}(T)$. Using
this, the modified $\rho$-Shapley fair reward value is defined by

$\displaystyle
r^{t}_{i}:=max\left\\{v\left(\mathcal{E}^{t}_{i},\mathcal{E}^{t}_{N}\right)-v^{t}_{\emptyset},-v^{t}_{\emptyset}\cdot\left(\frac{\phi^{t}_{i}}{\phi^{t*}}\right)^{\rho}\right\\},$
(11)

with scaling factor $\rho\in(0,1]$ and $\phi^{t*}:=max_{i\in N}\phi^{t}_{i}$.
Using this keeps rewards lower than when using the standard SV while still
ensuring the fairness conditions [12]. Thus, agents can be incentivized to
produce data over a longer period than by using the standard SV. For
$\rho\rightarrow 0$, $r^{t}_{i}\rightarrow 0$, thus all agents receive the
same reward. The larger $\rho$, the larger the differences between agent’s
rewards, and thus the more fairness is achieved. A detailed discussion on the
effect of the $\rho$ parameter has been done by Qiao and colleagues [12].

We can use this reward scheme, to ensure that agents with more valuable data
receive a better estimator than other agents. For this, when computing the
modified $\rho$-Shapley fair reward value $r^{t}_{i}$, we need to set
$\rho\leq\min_{i\in
N}log(1-v\left(\mathcal{E}^{t}_{i},\mathcal{E}^{t}_{N}\right)/v^{t}_{\emptyset})/log(\phi^{t}_{i}/\phi^{t*})$
[12]. Now we can define our fair mechanism as:

$\displaystyle[\mathcal{M}_{fair}(\mathbf{D}^{t})]_{i}=\begin{cases}\tilde{\mathcal{E}^{t}_{i}}&\text{if
}t<t^{s-opt}_{i}\\\ \mathcal{E}^{t}_{i},\text{such that
}im_{i}(t)=c_{i}\Delta_{i}+r^{t}_{i}&\text{else, if such $\mathcal{E}^{t}_{i}$
exists}\\\ \mathcal{E}_{N}&\text{else}.\end{cases}$ (12)

###### Proposition 1

$\mathcal{M}_{fair}$ ensures fairness since agents with more valuable data
receive a better estimator [12]. The agent with the least valuable data
receives an estimator which just ensures that his average improvement rate
balances his costs, agents with more valuable data receive estimators with
larger improvement rates. This, in turn, means that $\mathcal{M}_{fair}$ is
not data maximizing anymore, because agents with data of high value receive
better estimators faster than they would under $\mathcal{M}$.

This proposition follows directly from the construction of the reward scheme
and the fact that $\mathcal{M}$, as defined in equation 10, is data maximizing
with $\mathcal{M}\neq\mathcal{M}_{fair}$.

##  7 Related Work

The data valuation scheme presented in this paper is inspired by the scheme
presented by Qiao and colleagues [12], in particular w.r.t. the use of
negative reverse KL divergence. However, they only performed one regression to
estimate one effect, they did not estimate a CPDAG and did not estimate the
causal effects between all pairs of variables.

For this reason, a measure for distances between CPDAGs was needed. One
possible measure here would be the structural hamming distance (SHD). However,
as described by Peters and Bühlmann [18], the SHD does not necessarily
describe well, how different two graphs are regarding the causal effects they
decode. They therefore introduce the structural intervention distance (SID),
which, given two DAGs $\mathcal{H}$ and $\mathcal{G}$ over the same vertices
$\mathbf{V}$, describes how many intervention distributions between variable
pairs are falsely estimated by $\mathcal{H}$ wrt $\mathcal{G}$. The SID can be
applied to CPDAGs as well, here however it returns a range of the SIDs between
all possible DAG extensions of the CPDAGs, whereas here a definite measure was
needed.

A data maximizing mechanism for federated learning was first presented by
Karimireddy and colleagues [11]. They assumed, however, that each data point
provided by any agent had the same value and that the quality of a model could
be directly computed. In our setting of collaborative causal inference, these
assumptions do not hold anymore, therefore the data valuation scheme was
introduced, both to measure the value of an agent’s data as well as to measure
the quality of a given estimator.

##  8 Conclusion and Future Work

This paper presents novel mechanisms for CCI aimed at motivating the
engagement of self-interested agents through the provision of superior causal
effect estimators compared to those agents that could develop independently.
Our initial mechanism incentivizes all participating agents to maximize data
contribution, thereby facilitating the construction of a comprehensive model
based on extensive data and expected to yield high accuracy. Building upon
this, our second mechanism assigns better estimators to agents supplying
higher-quality data, ensuring a fair reward allocation given individual
contributions.

A limitation of our mechanism lies in the assumption of known data production
costs $c_{i}$ for agents, prompting a future research direction towards
maximizing data despite unknown $c_{i}$’s. Furthermore, the presumption of
honesty and non-malicious behavior among all agents may not hold in practical
scenarios, with some parties potentially exploiting the transparent framework
for personal gain or harm to others. Consequently, a more robust mechanism
resilient to such behavior would be preferable.

### Acknowledgements

Björn Filter acknowledges funding for project FPOplus by BMDV/TÜV Rheinland
Consulting GmbH.

## References

  * [1] Shi, J., Norgeot, B.: Learning causal effects from observational data in healthcare: a review and summary. Frontiers in Medicine 9, 864882 (2022)
  * [2] Hu, P., Jiao, R., Jin, L., Xiong, M.: Application of causal inference to genomic analysis: advances in methodology. Frontiers in Genetics 9, 238 (2018)
  * [3] Yao, L., Chu, Z., Li, S., Li, Y., Gao, J., Zhang, A.: A survey on causal inference. ACM Transactions on Knowledge Discovery from Data (TKDD) 15(5), 1–46 (2021)
  * [4] Liang, D., Charlin, L., Blei, D.M.: Causal inference for recommendation. In: Causation: Foundation to Application, Workshop at UAI. AUAI (2016)
  * [5] Cordero, J.M., Cristóbal, V., Santín, D.: Causal inference on education policies: A survey of empirical studies using pisa, timss and pirls. Journal of Economic Surveys 32(3), 878–915 (2018)
  * [6] Sun, W., Wang, P., Yin, D., Yang, J., Chang, Y.: Causal inference via sparse additive models with application to online advertising. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 29 (2015)
  * [7] Singer, R.S., Williams-Nguyen, J.: Human health impacts of antibiotic use in agriculture: A push for improved causal inference. Current Opinion in Microbiology 19, 1–8 (2014)
  * [8] Masic, I., Miokovic, M., Muhamedagic, B.: Evidence based medicine–new approaches and challenges. Acta Informatica Medica 16(4), 219 (2008)
  * [9] Bareinboim, E., Pearl, J.: Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences 113(27), 7345–7352 (2016)
  * [10] Pareek, C.S., Smoczynski, R., Tretyn, A.: Sequencing technologies and genome sequencing. Journal of applied genetics 52, 413–435 (2011)
  * [11] Karimireddy, S.P., Guo, W., Jordan, M.I.: Mechanisms that Incentivize Data Sharing in Federated Learning. Papers 2207.04557, arXiv.org (Jul 2022), https://ideas.repec.org/p/arx/papers/2207.04557.html
  * [12] Qiao, R., Xu, X., Low, B.K.H.: Collaborative causal inference with fair incentives. In: Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., Scarlett, J. (eds.) Proceedings of the 40th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 202, pp. 28300–28320. PMLR (23–29 Jul 2023), https://proceedings.mlr.press/v202/qiao23a.html
  * [13] Pearl, J.: Causality. Cambridge University Press, Cambridge, UK, 2 edn. (2009)
  * [14] Kalisch, M., Bühlman, P.: Estimating high-dimensional directed acyclic graphs with the pc-algorithm. Journal of Machine Learning Research 8(3) (2007)
  * [15] Chickering, D.M.: Optimal structure identification with greedy search. Journal of machine learning research 3(Nov), 507–554 (2002)
  * [16] Chickering, D.M.: Learning equivalence classes of bayesian networks structures. CoRR abs/1302.3566 (2013), http://arxiv.org/abs/1302.3566
  * [17] Maathuis, M.H., Kalisch, M., Bühlmann, P.: Estimating high-dimensional intervention effects from observational data. The Annals of Statistics 37(6A), 3133–3164 (2009)
  * [18] Peters, J., Bühlmann, P.: Structural intervention distance for evaluating causal graphs. Neural Comput. 27(3), 771–799 (Mar 2015)
  * [19] Meek, C.: Causal inference and causal explanation with background knowledge. In: Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. p. 403–410. UAI’95, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1995)
  * [20] Shpitser, I., VanderWeele, T., Robins, J.M.: On the validity of covariate adjustment for estimating causal effects. In: Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence. p. 527–536. UAI’10, AUAI Press, Arlington, Virginia, USA (2010)
  * [21] Guo, R., Perkovic, E.: Minimal enumeration of all possible total effects in a markov equivalence class. In: Banerjee, A., Fukumizu, K. (eds.) Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 130, pp. 2395–2403. PMLR (13–15 Apr 2021)
  * [22] Peters, J., Janzing, D., Schölkopf, B.: Elements of Causal Inference: Foundations and Learning Algorithms. Adaptive Computation and Machine Learning, MIT Press (2017)
  * [23] Shachter, R.D.: Bayes-ball: The rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams). arXiv preprint arXiv:1301.7412 (2013)
  * [24] Wienöbst, M., Luttermann, M., Bannach, M., Liśkiewicz, M.: Efficient enumeration of markov equivalent dags. In: Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence. AAAI’23/IAAI’23/EAAI’23, AAAI Press (2023)

##  Appendix 0.A Distribution Structural Intervention Distance

To see how the dSID can be computed, we will first need some further
preliminaries, consisting of some more graph-theoretical definitions and the
concept of covariate adjustment.

###  0.A.1 Further Preliminaries

A partially directed acyclic graph (PDAG) is a partially directed graph
without directed cycles. A PDAG $\mathcal{G}$ is a maximally oriented PDAG
(MPDAG) if and only if the edge orientations in $\mathcal{G}$ are complete
under the Meek orientation rules [19].

To identify the total causal effect of a variable $V_{i}\in\mathbf{V}$ on a
variable $V_{j}\in\mathbf{V}$, one has to find an expression for $P(y\mid
do(x))$. Using only the preintervention probabilities of the observed
variables $\mathbf{V}$, this can be done through covariate adjustment. Here, a
so-called adjustment set is used, to estimate the causal effect [13]. A graph-
theoretical criterion can be used to determine, whether a set
$\mathbf{Z}\subseteq\mathbf{V}\mathbin{\backslash}\\{V_{i},V_{j}\\}$ is an
adjustment set wrt two nodes $V_{i},V_{j}\in\mathbf{V}$. This is the so-called
adjustment criterion:

######  Definition 4 (Adjustment Criterion for DAGs [20])

Let $\mathcal{D}=\mathbf{(V,E)}$ be a DAG, $V_{i},V_{j}\in\mathbf{V}$ two
nodes and
$\mathbf{Z}\subseteq\mathbf{V}\mathbin{\backslash}\\{V_{i},V_{j}\\}$. The set
$\mathbf{Z}$ satisfies the adjustment criterion relative to $(V_{i},V_{j})$ in
$\mathcal{D}$ if

  1. (a)

no element in $\mathbf{Z}$ is a descendant in $\mathcal{D}$ of any
$W\in\mathbf{V}\mathbin{\backslash}V_{i}$ which lies on a causal path from
$V_{i}$ to $V_{j}$ and

  2. (b)

all non-causal paths in $\mathcal{D}$ from $V_{i}$ to $V_{j}$ are d-separated
by $\mathbf{Z}$.

The adjustment criterion can then be used to find adjustment sets:

######  Theorem 0.A.1 ([20])

Let $\mathcal{D}=\mathbf{(V,E)}$ be a DAG, $V_{i},V_{j}\in\mathbf{V}$ two
nodes and
$\mathbf{Z}\subseteq\mathbf{V}\mathbin{\backslash}\\{V_{i},V_{j}\\}$.
$\mathbf{Z}$ is an adjustment set wrt $(V_{i},V_{j})$ in $\mathcal{D}$, if and
only if $\mathbf{Z}$ satisfies the adjustment criterion (definition 4)
relative to $(V_{i},V_{j})$ in $\mathcal{D}$.

For a DAG $\mathcal{D}=(\mathbf{V,E})$ and two nodes
$V_{i},V_{j}\in\mathbf{V}$ let
$AS_{(V_{i},V_{j})}(\mathcal{D})=\\{\mathbf{Z}\mid\mathbf{Z}\subseteq\mathbf{V}\mathbin{\backslash}\\{V_{i},V_{j}\\}\textit{
and }\mathbf{Z}$ fulfills the adjustment criterion for $\mathcal{D}\textit{
wrt }(V_{i},V_{j})\\}$ be the set of all possible adjustment sets wrt
$(V_{i},V_{j})$ in $\mathcal{D}$. It is easy to see that
$Pa_{V_{i}}(\mathcal{D})\in AS_{(V_{i},V_{j})}(\mathcal{D})$, because
$Pa_{V_{i}}(\mathcal{D})$ always fulfills the adjustment criterion wrt
$(V_{i},V_{j})$.

###  0.A.2 An Algorithm for Computing the dSID

Recall, that the dSID is defined as follows: Let $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ be two CPDAGs over the same set of variables $\mathbf{V}$.

$\displaystyle dSID:\text{ }$ $\displaystyle\mathcal{G}\times\mathcal{G}$
$\displaystyle\rightarrow\mathbb{N}$
$\displaystyle(\mathcal{C}_{1},\mathcal{C}_{2})$
$\displaystyle\mapsto|\\{(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V},V_{i}\neq
V_{j}\mid\text{the distribution of causal}$ $\displaystyle\text{effects of
$V_{i}$ on $V_{j}$ is falsely identified in $\mathcal{C}_{1}$ with respect to
$\mathcal{C}_{2}$}\\}|$

with the distribution of causal effects of $V_{i}$ on $V_{j}$ given CPDAG
$\mathcal{C}$ defined as:

$\displaystyle P_{\mathcal{C}}(v_{j}\mid do(V_{i}=v_{i}))=\sum_{\mathcal{D}\in
CE(\mathcal{C})}\frac{1}{|CE(\mathcal{C})|}P_{\mathcal{D}}(v_{j}\mid
do(V_{i}=v_{i}))$ (13)

To compute the dSID, for all $(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$, we
first need to identify all possible effects of $V_{i}$ on $V_{j}$ in all DAG-
extensions of both $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$. We then need to
check, whether all effects found given $\mathcal{C}_{1}$ can be found given
$\mathcal{C}_{2}$ as well, and vice versa. The dSID Algorithm is depicted in
figure 1. It will be described in detail in the following.

As mentioned before, to identify the possible effects of $V_{i}$ on $V_{j}$
given a CPDAG $\mathcal{C}$, we can compute $\mathbf{Pa}_{V_{i}}(\mathcal{C})$
and use these as adjustment sets to compute the effects. However, suppose
$\mathcal{D},\mathcal{D^{\prime}}\in CE(\mathcal{C})$ with
$Pa_{V_{i}}(\mathcal{D})\neq Pa_{V_{i}}(\mathcal{D^{\prime}})$. It is still
possible, that $Pa_{V_{i}}(\mathcal{D^{\prime}})$ can be an adjustment set wrt
$(V_{i},V_{j})$ in $\mathcal{D}$ (this is the case, when
$Pa_{V_{i}}(\mathcal{D^{\prime}})$ fulfills the adjustment criterion wrt
$(V_{i},V_{j})$ in $\mathcal{D}$). Now, the effect of $V_{i}$ on $V_{j}$ would
be identical given both $\mathcal{D}$ and $\mathcal{D^{\prime}}$. We will
therefore start by identifying the subclasses of DAGs, such that the effect of
$V_{i}$ on $V_{j}$ in each subclass is identical. For this, the IDGraphs
Algorithm [21] can be used (line 3 in figure 1), which runs in
$O(2^{m(\mathcal{C})})poly(|\mathbf{V}|)$, where $m(\mathcal{C})$ is the
number of undirected edges incident to $V_{i}$ on a proper possibly causal
path from $V_{i}$ to $V_{j}$. While $m(\mathcal{C})$ could be potentially as
big as $p$, in practice it tends to be small. $poly(|\mathbf{V}|)$ describes
the time used to complete the orientation rules of Meek [19], which are also
used in the PC algorithm. In practice, IDGraphs takes about twice the time of
IDA. It returns the minimal set of MPDAGs $\mathbf{M}$, such that
$CE(\mathcal{C})=\cup_{\mathcal{M}\in\mathbf{M}}CE(\mathcal{M})$ and for all
$\mathcal{M}\in\mathbf{M}$, for all pairs
$(\mathcal{D},\mathcal{D^{\prime}})\in\mathcal{M}$, $Pa_{V_{i}}(\mathcal{D})$
is an adjustment set wrt $(V_{i},V_{j})$ in $\mathcal{D^{\prime}}$.

Input: CPDAGs $\mathcal{C}_{1}=(\mathbf{V,E_{1}})$,
$\mathcal{C}_{2}=(\mathbf{V,E_{2}})$

Output: Number of pairs $(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$, for
which the distribution of causal effects of $V_{i}$ on $V_{j}$ is falsely
identified in $\mathcal{C}_{1}$ with respect to $\mathcal{C}_{2}$

1 dSID $\leftarrow$ 0;

2 foreach  _$(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$_ do

3 $\mathbf{M}_{1}=$ IDGraphs($\mathcal{C}_{1},V_{i},V_{j}$), $\mathbf{M}_{2}=$
IDGraphs($\mathcal{C}_{2},V_{i},V_{j}$);

4 foreach  _$\mathcal{M}\in\mathbf{M}_{1}$_ do

5 found $\leftarrow$ false;

6 $\mathcal{D}\leftarrow$ any DAG $\mathcal{D}\in CE(\mathcal{M})$;

7 foreach  _$\mathcal{M}^{\prime}\in\mathbf{M}_{2}$_ do

8 $\mathcal{D}^{\prime}\leftarrow$ any DAG $\mathcal{D}^{\prime}\in
CE(\mathcal{M}^{\prime})$;

9 if  _$Pa_{V_{i}}(\mathcal{D})$ is an adjustment set wrt $(V_{i},V_{j})$ for
$\mathcal{D}^{\prime}$_ then

10 if
_$\frac{|CE(\mathcal{M})|}{|CE(\mathcal{C}_{1})|}=\frac{|CE(\mathcal{M}^{\prime})|}{|CE(\mathcal{C}_{2})|}$_
then

11 found $\leftarrow$ true;

12 break;

13

14

15

16 if  _$\neg$ found_ then

17 dSID $+=1$;

18 break;

19

20

21

return _dSID_

Algorithm 1 dSID Figure 1: The dSID algorithm

Let $\mathbf{M}_{i}$ be the results of running IDGraphs on $\mathcal{C}_{i}$
for $i\in\\{1,2\\}$. We can use these sets to compute the possible effects and
their probabilities: For each $\mathcal{M}\in\mathbf{M}_{1}$, sample any
$\mathcal{D}\in\mathcal{M}$ (line 6). $Pa_{V_{i}}(\mathcal{D})$ can be used to
compute the effect of $V_{i}$ on $V_{j}$. The effects probability is given by
$\frac{CE(\mathcal{M})}{CE(\mathcal{C}_{1})}$. Now we need to check whether
this effect occurs also given $\mathcal{C}_{2}$, and with the same
probability. To do this, we will need the following Theorem:

###### Theorem 0.A.2

Let $\mathcal{D}_{1},\mathcal{D}_{2}$ be two Markov equivalent DAGs with nodes
$\mathbf{V}$ and let $V_{i},V_{j}\in\mathbf{V}$ be two nodes. Then
$AS_{(V_{i},V_{j})}(\mathcal{D}_{1})\cap
AS_{(V_{i},V_{j})}(\mathcal{D}_{2})\neq\emptyset$, if and only if
$AS_{(V_{i},V_{j})}(\mathcal{D}_{1})=AS_{(V_{i},V_{j})}(\mathcal{D}_{2})$.

###### Proof

WLOG, suppose there are two sets
$\mathbf{Z},\mathbf{Z}^{\prime}\subseteq\mathbf{V}\mathbin{\backslash}\\{V_{i},V_{j}\\}$
with $\mathbf{Z}\in AS_{(V_{i},V_{j})}(\mathcal{D}_{1})\cap
AS_{(V_{i},V_{j})}(\mathcal{D}_{2})$ and $\mathbf{Z}^{\prime}\in
AS_{(V_{i},V_{j})}(\mathcal{D}_{1})$.We will show, that
$\mathbf{Z}^{\prime}\in AS_{(V_{i},V_{j})}(\mathcal{D}_{2})$. According to
[20],

$\displaystyle\mathbf{Z}^{\prime}\in AS_{(V_{i},V_{j})}(\mathcal{D}_{2})$
$\displaystyle\Leftrightarrow P_{M_{2}}(v_{j}\mid do(v_{i}))$ (14)
$\displaystyle=\sum_{\mathbf{Z}^{\prime}}P_{M_{2}}(v_{j}\mid
v_{i},z^{\prime})P_{M_{2}}(z^{\prime})$ (15)

in all distributions $P_{M_{2}}$ entailed by a Markovian SCM $M_{2}$ which
induces $\mathcal{D}_{2}$. Since $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ are
Markov equivalent, every distribution $P_{M_{2}}$ is also entailed by some
Markovian SCM $M_{1}$ inducing $\mathcal{D}_{1}$ and vice versa (see
Proposition 7.1 in [22]). This gives

$\displaystyle\centering P_{M_{2}}(v_{j}\mid do(v_{i}))\@add@centering$
$\displaystyle=\sum_{\mathbf{Z}}P_{M_{2}}(v_{j}\mid
v_{i},\mathbf{z})P_{M_{2}}(\mathbf{z})$ ($\mathbf{Z}\in
AS_{(V_{i},V_{j})}(\mathcal{D}_{2})$) (16)
$\displaystyle=\sum_{\mathbf{Z}}P_{M_{1}}(v_{j}\mid
v_{i},\mathbf{z})P_{M_{1}}(\mathbf{z})$ ($P_{M_{2}}$ entailed by $M_{1}$) (17)
$\displaystyle=P_{M_{1}}(v_{j}\mid do(v_{i}))$ ($\mathbf{Z}\in
AS_{(V_{i},V_{j})}(\mathcal{D}_{1})$) (18)
$\displaystyle=\sum_{\mathbf{Z}^{\prime}}P_{M_{1}}(v_{j}\mid
v_{i},\mathbf{z^{\prime}})P_{M_{1}}(\mathbf{z^{\prime}})$
($\mathbf{Z^{\prime}}\in AS_{(V_{i},V_{j})}(\mathcal{D}_{1})$) (19)
$\displaystyle=\sum_{\mathbf{Z}^{\prime}}P_{M_{2}}(v_{j}\mid
v_{i},\mathbf{z^{\prime}})P_{M_{2}}(^{\prime}\mathbf{z^{\prime}})$
($P_{M_{1}}$ entailed by $M_{2}$) (20)

and thus follows $\mathbf{Z}^{\prime}\in AS_{(V_{i},V_{j})}(\mathcal{D}_{2})$.

Using this, we can check, whether all effects found given $\mathcal{C}_{1}$
can also be found given $\mathcal{C}_{2}$ with the same probability. For each
$\mathcal{M}\in\mathbf{M}_{1}$, we can find the causal effect by sampling a
DAG $\mathcal{D}\in\mathcal{M}$ and using $Pa_{V_{i}}(\mathcal{D})$ as an
adjustment set. The IDGraphs algorithm ensured, that $Pa_{V_{i}}(\mathcal{D})$
is an adjustment set wrt $(V_{i},V_{j})$ for all
$\mathcal{D}_{j}\in\mathcal{M}$ and therefore, by theorem 0.A.2, for all
$\mathcal{D}_{1},\mathcal{D}_{2}\in\mathcal{M}$,
$AS_{(V_{i},V_{j})}(\mathcal{D}_{1})=AS_{(V_{i},V_{j})}(\mathcal{D}_{2})$.

Now, iterate over all $\mathcal{M}^{\prime}\in\mathbf{M}_{2}$ (line 7), sample
a DAG $\mathcal{D}^{\prime}\in\mathcal{M}^{\prime}$ (line 8) and check,
whether $Pa_{V_{i}}(\mathcal{D})$ fulfills the adjustment criterion wrt
$(V_{i},V_{j})$ in $\mathcal{D}^{\prime}$ (line 9). This can be efficiently
done by the Bayes-Ball algorithm [23]. If this is the case, by theorem 0.A.2,
we know that,
$AS_{(V_{i},V_{j})}(\mathcal{D})=AS_{(V_{i},V_{j})}(\mathcal{D}^{\prime})$. By
the properties of IDGraphs and theorem 0.A.2, for all
$\mathcal{D}_{1}^{\prime},\mathcal{D}_{2}^{\prime}\in\mathcal{M}^{\prime}$,
$AS_{(V_{i},V_{j})}(\mathcal{D}_{1}^{\prime})=AS_{(V_{i},V_{j})}(\mathcal{D}_{2}^{\prime})$.
Thus, finally, for all $\mathcal{D}\in\mathcal{M}$ and
${D}^{\prime}\in\mathcal{M}^{\prime}$,
$AS_{(V_{i},V_{j})}(\mathcal{D})=AS_{(V_{i},V_{j})}(\mathcal{D}^{\prime})$. In
other words, $P_{\mathcal{D}}(v_{j}\mid do(V_{i}=v_{i}))$ will be identical
given any DAG $\mathcal{D}\in\mathcal{M}\cup\mathcal{M}^{\prime}$. If so,
check whether
$\frac{|CE(\mathcal{M})|}{|CE(\mathcal{C}_{1})|}=\frac{|CE(\mathcal{M}^{\prime})|}{|CE(\mathcal{C}_{2})|}$
(line 10), that is not only the effects are identical but also their
probability given $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$. This can be done
using the Clique-Picking algorithm [24], which computes the number of DAG-
extensions of a given MPDAG in polynomial time. If for all
$\mathcal{M}\in\mathbf{M}_{1}$, a corresponding
$\mathcal{M}^{\prime}\in\mathbf{M}_{2}$ can be found,
$P_{\mathcal{C}_{1}}(v_{j}\mid do(V_{i}=v_{i}))=P_{\mathcal{C}_{2}}(v_{j}\mid
do(V_{i}=v_{i}))$ must hold.

Applying this procedure for all pairs
$(V_{i},V_{j})\in\mathbf{V}\times\mathbf{V}$ and counting the instances, in
which $P_{\mathcal{C}_{1}}(v_{j}\mid do(V_{i}=v_{i}))$ and
$P_{\mathcal{C}_{2}}(v_{j}\mid do(V_{i}=v_{i}))$ differ (line 14), results in
the dSID. In the worst case, the runtime can amount to
$p^{2}O(2^{m(C)})poly(|V|)2^{p}2^{p}O(V)ploy(|V|)=O(2^{2p})$. Here, $p^{2}$
results from going over all pairs of variables, $O(2^{m(C)})poly(|V|)$ is the
runtime of IDGraphs, then there can be up to $2^{p}$ elements in both
$\mathbf{M}_{1}$ and $\mathbf{M_{2}}$, the Bayes-Ball algorithm takes $O(|V|)$
time. Finally, the Clique-Picking algorithm runs in $ploy(|V|)$. However,
normally CPDAGs tend to be sparse and mostly directing, resulting in very
small sets $\mathbf{M}_{1}$ and $\mathbf{M_{2}}$. In these cases, IDGraphs and
Clique-Picking run fast as well and the algorithm is not significantly slower
than IDA.

##  Appendix 0.B Proof of Theorem 6.1

######  Theorem 6.1 (Data maximization with known costs)

The mechanism $\mathcal{M}$ defined by equation 10 is data-maximizing for
$\epsilon\rightarrow 0^{+}$. A rational agent $i$ will contribute
$\Delta_{i}t_{i}^{opt}$ data points where
$\Delta_{i}t_{i}^{opt}\geq\Delta_{i}t_{i}^{s-opt}$, yielding a total of
$\sum_{j\in N}\Delta_{j}t_{j}^{opt}$ data points.

###### Proof

We will define the best response of agent $i$ to a mechanism $\mathcal{M}$ and
data contributions of all other agents over time
$\mathbf{D}_{-i}=\\{\mathbf{D}_{-i}^{1},\mathbf{D}_{-i}^{2}...\\}$ as the
time, at which $i$ will stop to produce data:

$\displaystyle B^{\mathcal{M}}_{i}(\mathbf{D}_{-i}):=t_{i}^{opt},$ (21)

such that for all $t<t_{i}^{opt}$ $im_{i}(t)\geq c_{i}\Delta_{i}$ and
$im_{i}(t_{i}^{opt})<c_{i}\Delta_{i}$.

First, we will see that given fixed data contributions $\mathbf{D}_{-i}^{t}$
from other users for all $t\in T$, for each agent $i$, $i$’s best response to
our mechanism $\mathcal{M}$ consists of more data than to any other feasible
and IR mechanism $\hat{\mathcal{M}}$. Will will then continue to show, that
this implies that the equilibrium contribution of the agent is also data
maximizing.

###### Lemma 1

For given data contributions over time $D_{-i}$ and any feasible and IR
mechanism $\hat{\mathcal{M}}$, define best responses of agent $i$
$B^{\mathcal{M}}_{i}(\mathbf{D}_{-i})$ and
$B^{\hat{\mathcal{M}}}_{i}(\mathbf{D}_{-i})$ for our mechanism $\mathcal{M}$
as defined in equation 10 and the other mechanism $\hat{\mathcal{M}}$. Then,
for any $i\in N$ and any $D_{-i}^{t}$,

$\displaystyle B^{\mathcal{M}}_{i}(\mathbf{D}_{-i})\geq
B^{\hat{\mathcal{M}}}_{i}(\mathbf{D}_{-i})$ (22)

For now, we will assume the above lemma and continue with our proof. Since the
best responses are defined as the time, at which $i$ stops contributing more
data, we will write
$B^{\hat{\mathcal{M}}}_{i}(\mathbf{D}_{-i})=t_{i}^{\hat{\mathcal{M}}}$ and
$B^{\mathcal{M}}_{i}(\mathbf{D}_{-i})=t_{i}^{\mathcal{M}}$. By definition 3,
the total data collected by mechanism $\mathcal{M}$ is calculated as

$\displaystyle\sum_{i\in N}t_{i}^{\mathcal{M}}\Delta_{i}=\sum_{i\in
N}B^{\mathcal{M}}_{i}(\mathbf{D}_{-i})\Delta_{i}.$ (23)

Thus, from equation 22 directly follows:

$\displaystyle\sum_{i\in
N}B^{\mathcal{M}}_{i}(\mathbf{D}_{-i})\Delta_{i}=\sum_{i\in
N}t_{i}^{\mathcal{M}}\Delta_{i}\geq\sum_{i\in
N}B^{\hat{\mathcal{M}}}_{i}(\mathbf{D}_{-i})\Delta_{i}=\sum_{i\in
N}t_{i}^{\hat{\mathcal{M}}}\Delta_{i}$ (24)

for all mechanisms $\hat{\mathcal{M}}$ which are feasible and IR. Thus
$\mathcal{M}$ is data maximizing.

It is easy to see that $\mathbf{t}^{\mathcal{M}}=\\{t_{i}^{\mathcal{M}}|i\in
N\\}$ is the unique Nash equilibrium: Each agent $i\in N$, will continue to
produce data at least until $t_{i}^{s-opt}$, since here their behavior is
identical to as if they would act on their own. From $t_{i}^{s-opt}$ on, by
definition of $\mathcal{M}$, they do not receive a decrease in utility at
every $t<t_{i}^{\mathcal{M}}$, since $j_{i}(t)\geq c_{i}\Delta_{i}$ for all
$t<t_{i}^{\mathcal{M}}$. Thus $i$ will continue to produce data until
$t_{i}^{\mathcal{M}}$. Due to $j_{i}(t_{i}^{\mathcal{M}})<c_{i}\Delta_{i}$,
$i$ will stop producing data at this time. Therefore,
$\mathbf{t}^{\mathcal{M}}$ is the unique Nash equilibrium.

∎

######  Proof (of Lemma 1)

Suppose, Lemma 1 does not hold. Then there has to be some agent $i$, such that
$B^{\hat{\mathcal{M}}}_{i}(\mathbf{D}_{-i})>B^{\mathcal{M}}_{i}(\mathbf{D}_{-i})$.
Thus $t_{i}^{\hat{\mathcal{M}}}>t_{i}^{\mathcal{M}}$. Let
$\mathcal{E}_{i}^{\mathcal{M},t}$ denote the estimator returned to $i$ by
mechanism $\mathcal{M}$ at time $t$ and
$\mathcal{E}_{i}^{\hat{\mathcal{M}},t}$ denote the estimator returned by
$\hat{\mathcal{M}}$. Similarly define $im_{i}^{\mathcal{M}}(t)$ and
$im_{i}^{\hat{\mathcal{M}}}(t)$.

Since $\hat{\mathcal{M}}$ satisfies IR, for all $t<t_{i}^{s-opt}$,
$\hat{\mathcal{M}}$ has to return an estimator to $i$ which is at least as
good as $\tilde{\mathcal{E}}_{i}^{t}$ (which is returned by $\mathcal{M}$), so
for all $t<t_{i}^{s-opt}$:
$v\left(\mathcal{E}_{i}^{\hat{\mathcal{M}},t},\mathcal{E}_{N}^{t}\right)\leq
v\left(\mathcal{E}_{i}^{\mathcal{M},t},\mathcal{E}_{N}^{t}\right)$.

For $t\in[t_{i}^{s-opt},t_{i}^{\mathcal{M}}-1]$,
$\mathcal{E}_{i}^{\mathcal{M},t}$ is defined as the estimator which fulfills
$im_{i}(t)=c_{i}\Delta_{i}$, for as long as such an estimator exists. Thus,
$\mathcal{E}_{i}^{\mathcal{M},t}$ is defined as the worst possible estimator
which will still incentivize $i$ to continue providing data. Therefore, also
for all $t\in[t_{i}^{s-opt},t_{i}^{\mathcal{M}}-1]$ :
$v\left(\mathcal{E}_{i}^{\hat{\mathcal{M}},t},\mathcal{E}_{N}^{t}\right)\leq
v\left(\mathcal{E}_{i}^{\mathcal{M},t},\mathcal{E}_{N}^{t}\right)$. At
$t_{i}^{\mathcal{M}}$, $i$ stopped producing data under $\mathcal{M}$, since
$\mathcal{M}$ was not able to return a model which would satisfy
$im_{i}(t)\geq c_{i}\Delta_{i}$ and therefore returned
$\mathcal{E}_{N}^{t_{i}^{\mathcal{M}}}$. $\hat{\mathcal{M}}$ however was able
to provide an estimator $\mathcal{E}_{i}^{t_{i}^{\hat{\mathcal{M}}}}$ which
could satisfy $im_{i}(t)\geq c_{i}\Delta_{i}$, since under
$\hat{\mathcal{M}}$, $i$ continues to produce data for at least one more time.
But this would imply

$\displaystyle
1=v\left(\mathcal{E}_{N}^{t_{i}^{\mathcal{M}}},\mathcal{E}_{N}^{t_{i}^{\mathcal{M}}}\right)<v\left(\mathcal{E}_{i}^{\hat{\mathcal{M}},t_{i}^{\mathcal{M}}},\mathcal{E}_{N}^{t_{i}^{\mathcal{M}}}\right).$
(25)

Notice, that since $\Delta_{i}$ is fixed for all $i$ regardless of the
mechanism, until $t_{i}^{\mathcal{M}}$, all agents have provided the same data
to both mechanisms, thus, for $t\leq t_{i}^{\mathcal{M}}$ both mechanisms
evaluate estimators using the same benchmark $\mathcal{E}_{N}^{t}$. But then,
the inequality described by equation 25 is impossible, since by definition of
the function $v$,
$v\left(\mathcal{E}_{N}^{t_{i}^{\mathcal{M}}},\mathcal{E}_{N}^{t_{i}^{\mathcal{M}}}\right)=1$
and $v$ can never take on a value larger then $1$. Thus we have reached a
contradiction.

∎