
\section{Introduction}

There is a fundamental discrepancy between privacy attitudes and the  behaviors of users online: users claim to be concerned about their privacy but do little to protect privacy in their actions. More specifically, users express their concerns about privacy, including the ambiguous distribution of data and its use by third party \cite{Informationprivacyresearch, acquisti2017nudges, goldfarb2012shifts}; however, when choosing services, users mainly focus on the popularity, convenience, price, etc, despite the potential risk of data misuse \cite{Informationexamining,examination}. This phenomenon is known as the \emph{privacy paradox} \cite{privacyparadox} and understanding the reasons behind this paradox and its consequences for the design of online platforms is an important goal for both computer scientists and economists.  

The privacy paradox is at the root of the behavior of individuals in modern online data marketplaces.  Online platforms gather data on billions of individuals in order to personalize advertising and customize other aspects of their systems.  However, such usage tends to provide little direct benefits for the users, a fact that is used as indirect evidence to argue that users provide a small value on privacy \cite{athey2017digital}.  Such an argument ignores the impact that an individual's participation decision has on others.  In particular, when an individual shares her data, it is not just her privacy that is compromised; the privacy of other individuals whose data is correlated with hers is also compromised. Thus, these other individuals are more likely to share their own data given that some has already been leaked \cite{acemoglu_privacy}. This simple, but often overlooked issue is at the root of the privacy paradox.  Information leakage due to correlation has been shown to lead to oversharing since each individual overlooks their own privacy concerns as a result of the negative externalities created by others' revelation decisions.  Thus, information leakage leads to the potential for significant economic and social inefficiency in data marketplaces.

In this paper, \emph{we study the impact of privacy concerns and information leakage on the design of data markets.} Specifically, we study the task of designing mechanisms for obtaining verifiable data from a population for a statistical estimation task, such as estimating the expected value of some function of the underlying data.

The goal of designing mechanisms for optimal data acquisition is a core piece of the emerging literature on data marketplaces.  A common motivating example is a setting where a healthcare platform is doing statistical analysis on its population of users.  While some data is measured accurately from their smart devices, other desired data may be about characteristics users do not wish to provide or may vary over time. Thus the healthcare platform has to conduct a survey among the users to obtain such information accurately  (e.g. giving the individual a smart device or having the individual fill out a form); however when administering such a survey the responses are likely biased. For example, if weight is the target, then the respondents may be biased towards low-weight samples.  Thus, the task of designing mechanisms to limit the bias and reduce the variance of estimates obtained from such surveys is crucial.  However, such a task is challenging due to the fact that the analyst does not know the distribution of the data and has a limited budget.   

A growing line of work has focused on the design of such optimal data acquisition mechanisms, e.g., \cite{aaron_grant, dataacquisition, shuran_yiling, abernethy2015low}.  Initiated by \cite{abernethy2015low, aaron_grant}, this line of work has led to the design of mechanisms for unbiased estimation with minimal variance in a variety of settings. However, in this literature it is assumed that all individuals will participate, thus unbiased estimation is possible.  The trade-off between bias and variance has been ignored to this point with the exception of \citet{shuran_yiling}, which still assumes all individuals will participate and does not consider privacy concerns.  Further, this line of work has not considered the issues created  by information leakage due to correlation between the participants. Information leakage creates significant incentives for increased data sharing and thus mechanisms that do not consider it directly will suffer from undetected bias and increased variance in the obtained estimates.  Modeling the incentives created by leakage potentially provides the analyst the opportunity to obtain an estimator of the same quality using a smaller budget, due to the externalities created by data correlation.




\textbf{Contributions.} In this paper, we provide the first characterization of an optimal mechanism for data acquisition in the setting where agents are concerned about privacy and their data is correlated with each other. As a result, information leakage due to data correlation not only contributes to an agent's privacy cost, but also to the privacy costs of others with correlated data. Additionally, the mechanism allows, for the first time, a trade-off between the bias and variance of the estimator when privacy cost is considered. This offers the analyst freedom to tailor towards an emphasis on either bias or variance of the estimator depending on the contextual goals.

Specifically, we propose a novel model for data acquisition. The novelty of our model is a result of three important components. 
First, we introduce the privacy cost to model impacts of data correlation. Unlike modeling data correlation on an individual level in \cite{acemoglu_privacy},
we divide the agents into different groups and assume that agents within the same group share a same correlation strength. This gives us the power to work with any granularity of choice with regard to data correlation. For example, if every group has a relatively small size of agents, then our model of data correlation shifts towards a near individual level. In addition, an agent suffers a larger privacy cost if she joins the platform than that if she does not join. The choice of our privacy cost function enables us to model all these desired properties. Second, in reality, not every agent always decides to join the platform. Thus, we introduce the notion of participation rate as the ratio of the number of agents who join the platform to the number of total agents. This further allows us to study equilibrium with respect to participation rate, which is crucial since the mechanism impacts the participation rate, which in turn impacts the bias and variance. Third, given that not every agent always joins the platform, it is not always realistic to aim for an unbiased estimator. Instead, we minimize a linear combination of bias and variance of the estimator. Via a choice of constant weights for bias and variance, we are able to balance between these two metrics of the estimator as desired.

Our main theoretical results provide a closed form solution of payment and allocation rules under a choice of equilibrium participation rate in order to achieve a truthful mechanism (Theorem  \ref{pro_payment} $\&$  Theorem \ref{the_opt_pro}). More specifically, we aim to minimize a linear combination of bias and variance subject to budget and truthfulness constraints. By considering a linear combination, we are able to emphasize either bias or variance of the estimator as desired. Moreover, we provide conditions for the optimality of an unbiased estimator in the case when it is possible to achieve a full participation rate, i.e. every agent decides to join the platform.

Our results offer some interesting insights about mechanisms for data acquisition. First, an unbiased estimator is possible even if the budget is relatively small because we can meet the expected budget constraint using a small selection probability. However, an unbiased estimator is not always realistic in practice. As a result, it is important to optimize the bias-variance trade-off. Second, incorporation of privacy cost due to information leakage and sharing makes it possible for the analyst to underpay the agents to acquire the same data set. This can potentially lead to a relatively small payment for data, something that is frequently seen in practice. Last but not least, the privacy cost from leakage encourages more agents to join the platform, which coincides with the data oversharing phenomenon frequently observed in platforms today.



The design of mechanisms for data acquisition is known to be challenging even if we focus on an unbiased estimator and ignore privacy cost due to data correlation. However, obtaining our results requires overcoming additional challenges.  There are two technical innovations that enable our analysis. First, we need to introduce and characterize an equilibrium with respect to the participation rate, as the participation rate is an endogenous property of the mechanism design problem. This equilibrium adds considerable complexity to the analysis, but also provides insights about how the data acquisition mechanism depends on the popularity of the platform. Second, we introduce the notion of data correlation strength to characterize the privacy cost due to information leakage. This allows us to capture the impact of data correlation on the platform. Further, depending on a choice of group sizes, we are able to model information leakage at different granularity levels as desired.


\textbf{Related Literature.} The design of data markets has attracted a significant amount of interest in recent years. There is growing body of work studying a variety of aspects of data markets, including monetizing information via either dynamic sales or optimal mechanisms, e.g., \cite{babaioff2012optimal, horner2016selling}, exploiting personal information to improve allocation of resources in online markets, e.g., \cite{goldfarb2011online, bergemann2015selling, montes2019value}, optimal acquisition of information, e.g., \cite{aaron_grant, dataacquisition, shuran_yiling}. For a recent survey see \cite{bergemann_data_markets} and the references therein. Our work broadly falls into the last line of work, and focuses on the design of a mechanism for optimal data acquisition. The study of the optimal data acquisition has attracted a growing amount of attention across both economics and computer science. In this paper, we focus on designing a truthful mechanism in order to perform a statistical estimation task. This goal has received considerable attention. However, prior work does not consider the privacy cost of the participants.  Our work aims to fill the gap by considering privacy cost as an important factor for individuals' decision-making. 

In more detail, the prior work on optimal data acquisition can be divided into two categories depending on whether data is verifiable or not. In the first category, individuals' utilities often directly depend on the outcome of the statistical inference and they thus have an incentive to misreport their data, e.g., \cite{liu2016learning, liu2017sequential, liu2018surrogate, dekel2010incentive, meir2011strategyproof, meir2012algorithms, perote2003impossibility}. This is possible since there is no ground truth to verify the data. In the second category, individuals are assumed to report their data truthfully due to the ability of the analyst to verify the data, e.g., \cite{cummings2015accuracy,cai2015optimum,abernethy2015low, shuran_yiling, aaron_grant, dataacquisition}. In this paper, we consider the setting where data is verifiable and so focus our discussion on prior work in that category below.


The task in this context is to purchase data from individuals whose private costs are subject to an (expected) budget constraint. This model was introduced in \cite{abernethy2015low, aaron_grant}. The model assumes that data cannot be fabricated and that private costs of the participants are correlated with the data. Moreover, the participants do not derive utility or disutility from the estimation outcome. \citet{aaron_grant} minimizes a bound of the worst case variance while achieving an unbiased estimator while \citet{abernethy2015low} considers general supervised learning. Following these initial papers, a closed form result that directly minimizes the worst case variance is given in \cite{dataacquisition}. However, unbiased estimators are not always possible in realistic settings. When a biased estimator is considered, \citet{shuran_yiling} proposes a slightly different model, in which agents arrive in an online fashion and cost distribution is not known a priori. Under this model, \citet{shuran_yiling} studies a trade-off between bias and variance of the estimator rather than only focus on the unbiased estimators. This trade-off is also a core component of our work. 


The prior work discussed above mostly focuses on data acquisition without considering the privacy concerns of the participants. Even when the privacy concerns are considered in the prior work, privacy cost is often interpreted as a simple cost, which does not capture the information leakage due to data correlation.  In contrast, privacy cost due to information leakage as a result of data correlation is a crucial concern in the model we consider in this paper. There is a recent line of work that examines data acquisition through the lens of differential privacy \cite{ghosh_selling_privacy,cummings2015accuracy,fleischer2012approximately,buyingwithoutverification,nissim_redrawing}. As agents might not be willing to report their data due to their privacy concerns, monetary incentives are given to encourage individuals to participate in order to balance between privacy of individuals and accuracy of estimation. However, in this line of work, the  impact of information leakage is not considered and thus the practical impact of the privacy paradox is not considered.

The information leakage that results from correlation between individuals' is at the root of the privacy paradox and is a crucial factor for data markets, as has been recognized by recent work in economics, e.g.,\cite{liao2018social,acemoglu_privacy}.  More specifically, \citet{acemoglu_privacy} recently introduced the concept of information leakage to account for privacy cost due to other individuals' data sharing.
Inspired by this, we incorporate the privacy cost due to heterogeneous data correlation in our model and aim to design a truthful mechanism to balance between bias and variance subject to an expected budget constraint.  The privacy concern of individuals, specifically the privacy cost due to data correlation, is essential in the design of such a mechanism. This is a critical feature of our model that is not present in any prior work on data acquisition.  The setting and model we consider differ considerably from \cite{acemoglu_privacy}.  We consider the problem of optimal data acquisition and the incentives created by information leakage, which have not been considered in this context.


\section{System Model}

We consider an online platform consisting of an analyst and many agents.  At a high level, the analyst aims to design a pricing mechanism to purchase private data from agents in order to perform a statistical estimation task, e.g., estimate the mean of the agents' data. Ideally, the analyst would like to purchase all the private data to obtain an unbiased estimator. However, given a limited budget, the analyst has to design a pricing mechanism to wisely select the data in order to balance between the bias and variance of the estimator.


To this end, we consider a family of pricing mechanisms that presents a menu to the agents. The menu consists of pairs of payments and probabilities of having agents' data selected for use in the estimation task. Given the menu, the agents report their costs and decide individually if they would like to join the platform or not. Once the agents make the decisions, the analyst selects data from an agent on the platform to purchase with the given probability selected from the menu. The analyst's goal in designing the mechanism is to determine the menu of payments and selection probabilities in order to perform a statistical estimation subject to an expected budget constraint. The form of this mechanism is classical, and adopted from, e.g., \cite{aaron_grant,dataacquisition,abernethy2015low}.



Considering privacy cost is critical to the design of such a mechanism. For the agents on the platform, they obtain benefit from participation but reveal some personal information through their interactions with the platform, which leads to the privacy cost. Further, when an agent's data is used, it negatively impacts not only the privacy of the agent revealing the data, but also the privacy of other agents whose data is correlated. Thus, even though some agents do not join the platform and do not directly share their data, they may still suffer a privacy cost through their peers' interactions with the platform due to data correlation. This privacy cost via \emph{information leakage} is an important and novel feature of the model presented here. 

We describe the full details of the model and the family of mechanisms we consider in the remainder of this section.  Figure \ref{fig:model} provides an overview of the model.


\begin{figure}[t]
    \centering
    \includegraphics[width=0.95\textwidth]{model}
    \caption{An illustration of the model from the perspective of a participating agent in group $i$.}
    \label{fig:model}
\end{figure}



\subsection{Agent model} \label{sec:agent}


We consider $s$ agents that hold data of interest to the analyst.  The set of agents is denoted by $\mathcal{S}$. Every agent owns a data point. By reporting her data to the platform's survey, the agent incurs an overall cost $c$, which is known to her but not to the analyst. The overall cost consists of a combination of reporting cost and privacy cost, where the reporting cost results from the act of reporting the data while the privacy cost comes from both data sharing and data correlation. We discuss these costs further in Section \ref{sec:privacy}. 

We now present how the mechanism works. First, each agent is presented a price menu by the analyst that consists of a payment rule $P$ and selection probability $A$, both of which depend on the reported cost $\tilde{c}$ of the agent. We interchangeably use selection probability or allocation rule, as convenient. Second, given the menu, an agent decides if she would like to join the platform. An agent who decides to join the platform is asked to report her cost, which determines the payment and selection probability. The payment $P$ is given to the agent if she joins the platform \emph{and} her data is selected (used) by the analyst.   More specifically, her data is selected with probability $A$, and she receives the payment only if her data is selected.


Whether an agent decides to join the platform relies on weighing the benefit of participation $w(\cdot)$, plus a potential payment, against the privacy cost that occurs as a result of her own or her peers' interactions with the platform. More specifically, for an agent on the platform, her privacy cost incurred includes both the cost from the agent herself sharing her data and the privacy cost due to her friends' sharing of possibly correlated data. We use $\h$ to denote this combination.  In contrast, if an agent does not join the platform, she still suffers a  privacy cost $\g$  due to information leakage as a result of correlation between her data and the data of those agents who do join.
We use $\mathcal{N}$ to denote the set of agents who join the platform.
For agent $k$, her utility is as follows:
\begin{equation}\label{equ_uti_parameterized}
    \utility{\tilde{c}}{c}{i} = \begin{cases}
        -\g, &\text{if } k \not\in \mathcal{N}, \\
        -\h+w(\cdot), &\text{w/ prob. } 1-A, \text{ if } k \in \mathcal{N},\\ 
        P -c + w(\cdot), &\text{w/ prob. }  A, \text{ if } k \in \mathcal{N}.
    \end{cases}
\end{equation}


Up to this point, we have described the model in a general way, without giving details on the form of the benefit of participation ($w(\cdot)$) and privacy cost ($\g$ and $\h$).  In the remainder of this section, we introduce relevant models of these functions, which illustrate a variety of parameterized forms motivated by different potential settings. 



\subsubsection{Participation Benefit}

The participation benefit is the non-negative value received by agents who take advantage of the service provided by the platform. Intuitively, the more participants the platform attracts, the more valuable the platform's service becomes. Take Facebook as an example, the more friends of a user use Facebook, the more valuable Facebook as a social network is to this user. However, in light of the limited budget in practice, it is almost impossible to have every agent join the platform. As a result, we define the average participation rate of the population $\bar{\theta}$ to be the ratio of number of agents on the platform to the population of agents. The average participation rate $\bar{\theta}$ can be viewed as a measure of the popularity of the platform.\footnote{The participation rate is determined endogenously via the equilibrium, which we discuss in Section \ref{sec:mechanism}.} Moreover, let $\benefit{\bar{\theta}}$ denote the participation benefit as a continuous function of the average participation rate. The participation benefit is assumed to be non-decreasing in the average participation rate of the population $\bar{\theta}$. 

\subsubsection{Correlation Strength.}
Whether an agent decides to join the platform or not, an important source for her privacy cost comes from the information leakage due to data correlation. A stronger correlation naturally leads to more leakage and induces a larger privacy cost. Intuitively, if an agent's data is highly correlated with the rest of the agents, then she has a relatively large correlation strength.
Moreover, some agents might share a stronger correlation with each other within a group of agents than with others outside the group. For instance, on a healthcare related platform, users who carry a common disease might share a similar pattern and thus their data is possibly highly correlated with each other. In order to capture the inter-group versus intra-group difference, we divide $s$ agents into $I$ groups, and agents within the same group $i$ share a common correlation strength $\boldsymbol{\alpha}_i$. The correlation strength vector $\boldsymbol{\alpha}_i$ is further defined as $\boldsymbol{\alpha}_i \triangleq (\intraCor{i}, \interCor{i})$, where $\gIntraCor{i}$ and $\gInterCor{i}$ are used to respectively denote the correlation strength induced by agents inside group $i$ and those outside group $i$. Note that vectors are bold while scalars are not. 


\subsubsection{Privacy cost} \label{sec:privacy}

Privacy cost is critical to an agent's decision about whether to join the platform. For an agent who does not join the platform, her privacy cost $\g$ comes entirely from information leakage through her peers' data sharing on the platform due to data correlation. In contrast, for an agent who joins the platform but does not report her data, not only her peers' actions but also her own interactions with the platform result in her privacy cost, which is denoted by $\h$. Next, we introduce the parameterized form of privacy costs in detail.

\emph{Intra-group $\&$ Inter-group Privacy Loss.}
To differentiate the privacy cost due to correlation inside and outside the group, we further decompose privacy cost into a sum of intra-group cost and inter-group cost. Let the participation rate $\boldsymbol{\theta}_i$ denote a vector of participation rate within the group $\intraRatio{i}$ and that of the rest groups $\interRatio{i}$, i.e. $\boldsymbol{\theta}_i \triangleq  [\intraRatio{i},\interRatio{i}]$. For convenience, we later use $\bar{\theta}$ to denote the average participation rate of the overall population. For an agent in group $i$, her privacy cost is equal to a sum of intra-group cost and inter-group cost: $\gppl{c}{i} = \gintraloss{c}{i} + \ginterloss{c}{i}$ if the agent does not join the platform; otherwise her privacy cost of joining the platform is $\ppl{c}{i} = \intraloss{c}{i} + \interloss{c}{i}$.

Up to this point, we have introduced a parameterized form of privacy functions $\gppl{c}{i}$ and $\ppl{c}{i}$.
{To derive more clear engineering insights,} we make two assumptions regarding these privacy functions. These assumptions are intuitive and consistent with the applications we consider

\begin{assumption} \label{combine}
[Monotonicity $\&$ Boundedness] Both $\gppl{c}{i}$ and $\ppl{c}{i}$ are continuously  non-decreasing {in} cost $c$, participation rate $\intraRatio{i}$ and $\interRatio{i}$, and correlation strength $\intraCor{i}$ and $\interCor{i}$. Further, the difference $\ppl{c}{i}- \gppl{c}{i}$ is continuously increasing {in} cost $c$, {and  $\gppl{c}{i}$ is no greater than  $\ppl{c}{i}$. Both of them are bounded by $c$}:  $\gppl{c}{i} \le \ppl{c}{i} \leq c$.
\end{assumption}

To motivate the monotonicity assumption, first recall that cost is composed of reporting costs and privacy costs, as mentioned in Section \ref{sec:agent}. Thus, an agent with a high cost tends to value her privacy more, which is captured by the monotonicity with respect to costs. Second, intuitively, privacy costs increase as more agents join the platform. Indeed, the more agents join the platform and share their data, the more information that the analyst can infer about agents, including  those who do not join the platform. Third, the correlation strength characterizes how each agent's data is correlated with other agents' in the population. For an agent, a stronger correlation strength indicates that data sharing by other agents of the population could potentially cause more leakage, thus more privacy losses.

To understand the assumption $\gppl{c}{i}\leq\ppl{c}{i}\leq c$, we note that every agent suffers a privacy cost induced by her peers' activities on the platform due to data correlation even if she does not join the platform. In addition, for those who indeed join the platform, they tend to leak more information about themselves through their own activities on the platform. As a result, it is reasonable to assume that the privacy cost $\gppl{c}{i}$ of an agent, if she does not join the platform, is smaller than her privacy cost $\ppl{c}{i}$ if she joins but does not report her data. In other words,  sharing on the platform potentially leads to more privacy cost. The difference of these two parts models the privacy cost due to individual sharing. Naturally, for any agent, the privacy cost due to individual sharing tends to be higher if the agent has a larger overall cost. 
Since the overall cost consists of reporting cost and privacy cost, any privacy cost function is modeled as a fraction of the overall cost $c$, i.e. privacy cost is upper bounded by $c$.









\begin{assumption}
\label{Ass_linearincost}
The privacy cost  $\ppl{c}{i}$ is linear in cost $c$ with parameter $b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)$, i.e., 
\begin{equation}
     \ppl{c}{i} = c \cdot b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i).
 \end{equation}
\end{assumption}
	

We assume that the privacy cost function of participation $\ppl{c}{i}$ is linear in cost $c$.   This assumption is  a consequence of the work in~\citet{ghosh_selling_privacy}, which shows that cost functions of the form $c_i \varepsilon$ are appropriate for settings using differential privacy, where $\varepsilon$ quantifies the amount of privacy leaked. Note that the parameter $b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)$ inherits the monotonicity with respect to the participation rate and correlation strength from that of the privacy cost function $\ppl{c}{i}$. 

\subsubsection{Agent's Utility}
After introducing the key components of agent's utility, we summarize the utility function as follows:

\begin{enumerate}[label=(\roman*)]
    \item If the agent does not join the platform, she only experiences a privacy cost $\gppl{c}{i}$ induced by information leakage due to data correlation.
    \item If the agent joins the platform but is not selected to report her data, her utility is $\ppl{c}{i}+\benefit{\bar{\theta}}$, where $\benefit{\bar{\theta}}$ is the participation benefit.
    \item If the agent joins the platform and is selected to report her data, she incurs her overall cost $c$, which includes her privacy cost. Based on the agent's reported cost $\tilde{c}$, she receives a payment $\paymentP{\tilde{c}}{i}$ and thus her utility is $\paymentP{\tilde{c}}{i} -c + \benefit{\bar{\theta}}$.
\end{enumerate}



As the agent's privacy cost function is parameterized by the correlation strength parameter, so should the payment function $\paymentP{\tilde{c}}{i}$, selection probability $\selectionProbP{\tilde{c}}{i}$, utility $\utilityP{\tilde{c}}{c}{i}$. However, for simplicity, we later use $\payment{\tilde{c}}{i}$, $\selectionProb{\tilde{c}}{i}$, and $\utility{\tilde{c}}{c}{i}$, 
respectively to denote payment, selection probability and utility function. 
For agent $k$, her utility is as follows:
\begin{equation}\label{equ_uti}
    \utility{\tilde{c}}{c}{i} = \begin{cases}
        -\gppl{c}{i}, &\text{if } k \not\in \mathcal{N}, \\
        -\ppl{c}{i}+\benefit{\bar{\theta}}, &\text{w/ prob. } 1-\selectionProb{\tilde{c}}{i}, \text{ if } k \in \mathcal{N},\\ 
        \payment{\tilde{c}}{i} -c + \benefit{\bar{\theta}}, &\text{w/ prob. }  \selectionProb{\tilde{c}}{i}, \text{ if } k \in \mathcal{N}.
    \end{cases}
\end{equation}
 Let the expected utility for an agent (reporting $\tilde{c}$ while having a cost $c$) in group $i$ who joins the platform be denoted by $\expectedUtility{\tilde{c}}{c}{i}$. Consequently,
\begin{equation}\label{expected_utility}
\begin{aligned}
\expectedUtility{\tilde{c}}{c}{i} =& \selectionProb{\tilde{c}}{i} \left[ \payment{\tilde{c}}{i} -c + \benefit{\bar{\theta}} \right] + (1-\selectionProb{\tilde{c}}{i}) \left[ - \ppl{c}{i} + \benefit{\bar{\theta}} \right].\\
=&\selectionProb{\tilde{c}}{i}\left[\payment{\tilde{c}}{i} -c + \ppl{c}{i}\right]- \ppl{c}{i}+ \benefit{\bar{\theta}}.
\end{aligned}
\end{equation}



\section{Mechanism Design} 


\label{sec:mechanism}

The analyst aims to perform an estimation task by designing the menu for the mechanism, which is composed of payment function and allocation rule for agents. To study this problem, we first introduce two standard desirable properties of the mechanism: \emph{truthfulness} (Definition \ref{def_truthful}) and \emph{budget feasibility} (Definition \ref{def_budget}), and then define the overall objective (a trade-off between bias and variance of the estimator) (Definition \ref{def_obj}) subject to these two properties.  Following that setup, we introduce the equilibrium participation rate (Definition \ref{def_equilibrium}), which is  a situation where no agent wants to alter her participation decision given the current participation rate. We then derive  structural results on the payment function and allocation rule that induce participants' truthful reporting in the equilibrium in Section \ref{sec_payment} (Theorem \ref{pro_payment}). Finally, we present monotonicity properties of the mechanism in Section \ref{sec_properties}. 

\subsection{Problem Statement}

To define the analyst's mechanism design problem, we first describe two classical, desirable properties, truthfulness and an expected budget constraint. 
First, we require the mechanism to be truthful, which is common, e.g. \cite{dataacquisition, shuran_yiling}.

\begin{Def}[Truthfulness]\label{def_truthful}
A  mechanism is truthful if for every participant with cost $c$, she can maximize her expected utility if
she truthfully reports her cost, i.e.,
\begin{equation}\label{equ_truthfulness}
    \utility{c}{c}{i}\ge \utility{\tilde{c}}{c}{i}, \quad
    \forall \tilde{c} \neq c, \forall i.
\end{equation}
\end{Def}

Definition \ref{def_truthful} guarantees that rational agents on the platform will truthfully report their costs. Substituting the expected utility as in equation \eqref{expected_utility}, we get
\begin{equation}
\selectionProb{c}{i} \cdot \left[\payment{c}{i} -c + \ppl{c}{i}\right] \geq \selectionProb{\tilde{c}}{i} \cdot \left[\payment{\tilde{c}}{i} -c + \ppl{c}{i}\right], \quad
    \forall \tilde{c} \neq c, \forall i.
\end{equation}










 Second, we constrain the mechanism to use a limited budget $B$, which limits the payments of the analyst to the agents for their data. Before presenting the budget constraint in details, we introduce some notation. Every agent owns a data point $x$ and cost $c$.  These pairs $(x, c)$, owned by agents in group $i$ ($i\in [I]$), follow a joint distribution $\mathcal{D}_i$. Define  $\mathcal{D} \triangleq \{ \mathcal{D}_i \}_{i\in [I]}$. Let $f_i$ denote the marginal distribution of the cost. We assume that $f \triangleq \{ f_i \}_{i\in [I]}$ is known to the analyst while $\mathcal{D} \triangleq \{ \mathcal{D}_i \}_{i\in [I]}$ is unknown.\footnote{This prior $\{f_i\}$ could be constructed from previous interactions between agents and data buyers. Knowledge of the cost (or valuation) distribution is a standard assumption in Bayesian mechanism design (e.g.~\citet{myerson}), and is assumed in the works of \citet{aaron_grant} and \citet{dataacquisition}.}

\begin{Def}[Expected Budget Constraint]\label{def_budget}
A mechanism with payment function $P$ and selection probability $A$ satisfies the expected budget constraint $B$ if and only if
\begin{equation}
    \sum_{k: i = \group{k}} \E{c \sim f_{i}} [\payment{c}{i} \selectionProb{c}{i} \cdot \mathbbm{1} (\agent \in \groupParSet{i})] \le B.\\
\end{equation}
\end{Def}

We enforce the budget constraint on the expected payment in  Definition \ref{def_budget}, which is a common approach in the prior work, e.g. \cite{aaron_grant, dataacquisition, shuran_yiling}. Note that the expectation is taken with respect to the marginal distribution of agent's cost $f$, and the agents who join the platform as only they potentially receive a payment by the allocation rule. For convenience, we use $\group{k}$ to denote the group index of agent $k$.






We now formally define bias and variance of the  estimator of the analyst.  Recall the analyst seeks to optimize a tradeoff between bias and variance in our setting. Specifically, the analyst wishes to learn an underlying parameter $\mu$ of the whole population, and he obtains an estimator $\hat{m}$ based on participants' data.
The estimator $\hat{m}$ is viewed as a random variable, and the randomness of the estimator comes from the joint distribution $\mathcal{D}$ and the allocation rule $A$. We view the estimator as drawn from a distribution $\mathcal{T}(\jointD, A)$. 



\begin{Def}[Bias]\label{def_bias}
Given an allocation rule $A$ and an instance of the true distribution $\mathcal{D}$, the bias of an estimator $\hat{m}$ is defined as follows:
\begin{equation}
    \mathbb{B}(\estimator; \jointD, \allocation) = \left|\E{\hat{m} \sim \mathcal{T}(\jointD, A)} \left[ \hat{m} - \mu \right]\right|.
\end{equation}
\end{Def}



\begin{Def}[Variance]\label{def_variance}
Given an allocation rule $A$ and an instance of the true distribution $\mathcal{D}$, the variance of an estimator $\hat{m}$ is defined as follows:
\begin{equation}
    \mathbb{V}(\estimator; \jointD, \allocation) = \E{\hat{m} \sim \mathcal{T}(\jointD, A)} \left[ (\hat{m} - \mathbb{E} [\hat{m}])^2 \right].
\end{equation}
\end{Def}



Since the analyst does not know the joint distribution $\mathcal{D}$, he cannot directly optimize over bias and variance of the estimator. Instead, we consider the goal of minimizing the worst-case linear combination of bias (Definition \ref{def_bias}) and variance (Definition \ref{def_variance}) over all instantiations of $\mathcal{D}$ that are consistent with the marginal cost distribution $f$.

\begin{Def}[Worst-Case Bias-Variance Trade-off] \label{def_obj}
 \textcolor{black}{Given an allocation rule $A$, an instance of the true distribution $\mathcal{D}$, and a combination parameter $\lambda$, the worst-case bias-variance trade-off is the supremum of the linear combination of bias and variance:}  
 \begin{equation}
     \sup_{f \text{ consistent with } \mathcal{D}}\quad   \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation).
 \end{equation}
\end{Def}

Using the above, we formally define the mechanism design problem as follows.

\begin{Def}[Mechanism Design Task]\label{def_mech_design}
Given an estimator $\hat{m}$, cost distribution $f$, correlation strength parameters, and fixed parameter $\lambda$, the analyst aims to minimize a worst-case bias-variance trade-off by designing payment rule $P$ and allocation rule $A$ subject to truthfulness and budgetary constraints:
\begin{equation}\label{equ_mech_design}
\begin{aligned}
\inf_{A, P} \sup_{f \text{ consistent with } \mathcal{D}}\quad &   \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation)\\
\textrm{s.t.} \quad & \sum_{k: i = \group{k}} \E{c \sim f_{i}} [\payment{c}{i} \selectionProb{c}{i} \cdot \mathbbm{1} (\agent \in \groupParSet{i})] \le B\\
& \selectionProb{c}{i}\left[\payment{c}{i} -c + \ppl{c}{i}\right] \geq \selectionProb{\tilde{c}}{i}\left[\payment{\tilde{c}}{i} -c + \ppl{c}{i}\right], \quad
    \forall \tilde{c} \neq c, \forall i\\
\end{aligned}
\end{equation}
\end{Def}

Note that each agent suffers a privacy cost due to data correlation even if she does not join the platform. This negative utility offers the analyst freedom to compensate the agent a partial cost rather than the whole cost while motivating the agent to join the platform (individual rationality). As a result, we do not have to constrain the mechanism to satisfy a positive value of participation, which is a common requirement in the prior work in this area.  This is a novel, significant consequence of considering privacy leakage.









\subsection{Equilibrium Characterization}\label{sec_equilibrium}

To characterize the equilibrium that results under a given mechanism design, we consider the agents' decisions given a fixed participation rate. Recall that the participation rate is an aggregation of agents' decisions on whether to participate, and that an agent's utility depends on the participation rate. We emphasize that an agent's decision does not depend on other agents' individual decisions, rather only on the participation rate as an aggregate. This is natural for large platforms where a single agent's decision has little impact on others'. 

Before defining the equilibrium concept, we first introduce some notation. Recall that there are $I$ groups of agents parameterized by data correlation strength. We use $\groupProb{i}$ to represent the likelihood of a random agent coming from group $i$ in the population. For agents in group $i$, the cost follows a continuous distribution $f_i$  with  a support set $\mathcal{C} \triangleq [c_{\min},c_{\max}]$. We use $\bar{\theta}_i$ to denote the participation rate for group $i$. Let $\boldsymbol{\theta} \triangleq [\bar{\theta}_i]_{1\le i \le I}$, an array of average participation rate for all the groups, denote the participation rate profile. Naturally we have the average participation rate in the population satisfying $\bar{\theta} = \sum_{1\le i\le I} \groupProb{i}\cdot \bar{\theta}_i$.

For a given participation rate profile, an agent makes decisions by weighing her utility under different choices. For an agent with cost $c$ in group $i$, we use a binary variable $d_i(c | \boldsymbol{\theta})$ to denote her decision. If the agent joins the platform, $d_i(c | \boldsymbol{\theta}) = 1$; otherwise $d_i(c | \boldsymbol{\theta}) = 0$.  We consider a non-atomic model where a single agent's decision has no effect on the aggregate participation rate when the agent set is large enough \cite{marketdemand}. This is a realistic assumption for a large platform. Every agent is assumed to be rational, i.e., she decides to join the platform only if her utility of non-participation is not lower than that of participation. This translates to the following mathematical expression:
\begin{equation}\label{equ_brparticipaiton}
d_i(c|\boldsymbol{\theta}) = \begin{cases}
1, & \text{if}\ \ \max_{\tilde{c}}\expectedUtility{\tilde{c}}{c}{i}\ge -\gppl{c}{i},\\
0, &  \text{otherwise}.
\end{cases}
\end{equation}
Since both payment and selection probability depend on the reported cost, an agent tends to report the cost that maximizes her expected utility of participation $\expectedUtility{\tilde{c}}{c}{i}$.



For an agent in group $i, 1\le i\le I$, her decision on whether to participate is closely related to the participation rate  $\bar{\theta}_i$  of group $i$ and that of the rest groups $\bar{\theta}_{-i}$. Meanwhile, we notice that there are many possible participation rate profiles $\boldsymbol{\theta}$ that corresponds to one specific average participation rate $\bar{\theta} (= \sum_{1\le i\le I} \groupProb{i}\cdot \bar{\theta}_i)$. Thus, the average participation rate $\bar{\theta}$ alone is not enough to capture the agents' decisions. This motivates us to leverage the participation rate profile $\boldsymbol{\theta}$, instead of average participation rate $\bar{\theta}$ of all the groups, as the equilibrium concept.




We now define the equilibrium concept formally. This notion of equilibrium guarantees that agents' decisions are consistent with the participation rate profile. Note that we consider a strictly positive participation rate at equilibrium, i.e., $\bar{\theta}^*_i > 0, \forall i$, with an adequate budget; otherwise a zero participation rate for certain groups essentially leads to a biased estimator towards the rest of the groups with positive participation rates.

\begin{Def}[Equilibrium]\label{def_equilibrium}
A participation rate profile  $\boldsymbol{\theta}^*=[\bar{\theta}^*_i]_{1\le i\le I}$ is an equilibrium, if for each group $i, 1\le i\le I$, the fraction of participating agents is exactly $\bar{\theta}^*_i$, i.e., 
\begin{equation}\label{equ_equilibrium}
   \int_{c_{\min}}^{c_{\max}}\mathbbm{1}\left[d_i(c|\boldsymbol{\theta}^*)=1\right]\cdot f_i(c)dc = \bar{\theta}^*_i, \quad \forall i.
\end{equation}
\end{Def}




\subsection{Payment Function}\label{sec_payment}


We now analyze the structure of the payment function in the mechanism associated with the equilibrium $\boldsymbol{\theta}^*$. The analyst's mechanism design problem in Definition \ref{def_mech_design} involves a  truthfulness constraint and a budgetary constraint. We first present the payment function that satisfies the truthfulness constraint for a given non-increasing allocation rule. Later, in Section \ref{sec_opt_tradeoff}, we further optimize over allocation rule to solve for the general optimization problem. 


We present the payment function for group $i, 1\le i\le I$, and then characterize the requirements for a truthful mechanism. We begin with some definitions. For a fixed desired participation rate profile $\boldsymbol{\theta}$, we introduce  $\hat{c}{i}$  of group $i$, which satisfies the equality in \eqref{equ_ratio_threshold}. Later in this section, we explain in Corollary \ref{cor_threshold} that $\hat{c}{i}$ can be viewed as a cost threshold for agents in group $i$, and agents whose cost is no greater than this value would like to participate. 

\begin{equation}\label{equ_ratio_threshold}
	 \bar{\theta}_{i} = \int_{c_{\min}}^{\hat{c}{i}} f_i(c) dc, 1\le i\le I.
\end{equation}
Next, we give  the payment function of group $i$ as follows

\begin{equation}\label{equ_payment}
\begin{aligned}
\payment{\tilde{c}}{i} =\tilde{c}-\ppl{\tilde{c}}{i} 
+\frac{1}{\selectionProb{\tilde{c}}{i}}\left(\left(1-b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)\right)\int_{\tilde{c}}^{c_{\max}}\selectionProb{z}{i}dz + \constantpart{i}\right),
\end{aligned}
\end{equation}
where
\begin{equation}\label{equ_constantpart}
\constantpart{i} = \ppl{\hat{c}{i}}{i}-\gppl{\hat{c}{i}}{i}-\left(1-b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)\right)\int_{\hat{c}{i}}^{c_{\max}}\selectionProb{z}{i}dz - \benefit{\bar{\theta}}.
\end{equation}




The characterization of the payment function relies on allocation rule $A$ and the associated participation rate profile $\boldsymbol{\theta}$. According to Myerson's Lemma \cite{myerson}, the allocation rule should be non-increasing
{in} the reported cost $\tilde{c}$ in order to induce agents' truthfulness. Further, we present the requirements for a truthful mechanism in Theorem  \ref{pro_payment}. Such a mechanism can uniquely induce agents' truthful reporting of costs.  If the selection probability is strictly decreasing, the mechanism can induce agents' strict truthfulness.\footnote{By strict truthfulness, we are saying that the agent can maximize her utility of participation if and only if she truthfully reports her cost, i.e., $\utility{c}{c}{i}> \utility{\tilde{c}}{c}{i},$ for all $\tilde{c} \neq c$. That is, by removing the equality of (\ref{equ_truthfulness}) in Definition \ref{def_truthful}, we get the definition of strict truthfulness.} We highlight this result in Theorem \ref{pro_payment} and put its proof in Appendix \ref{appendixsec_payment}.
	\begin{The}\label{pro_payment}
	The mechanism is truthful (strictly truthful, respectively) and induces participation profile $\boldsymbol{\theta}^*$ at equilibrium if and only if for every group $i \in [I]$, both of the following statements hold:
	\begin{enumerate}	[label=(\roman*)]
	    \item allocation rule $\selectionProb{\tilde{c}}{i}$ is a non-increasing (decreasing, respectively) function of the reported cost $\tilde{c}$;
	    \item payment function is given as in Equation \eqref{equ_payment} (as a function of $A$), where $\boldsymbol{\theta} \triangleq \boldsymbol{\theta}^*$ is the desired participation rate profile.
	\end{enumerate}    
\end{The}


For a mechanism as described in Theorem  \ref{pro_payment}, the agent would like to truthfully report her overall cost, as truthful reporting can maximize her expected utility.  The monotonicity of the allocation rule indicates that an agent with a high reported cost in the same group is less likely to be selected and get a payment. 
Furthermore, we would like to emphasize that the strictly decreasing property of the allocation rule induces strict truthfulness of the mechanism. Suppose that the allocation rule is fixed in a certain range of reported cost (i.e., not decreasing).  By reporting any cost in this range, the agents in this range can get the highest utility, which does not satisfy strict truthfulness definition. Thus, a strictly decreasing allocation rule is necessary to induce strict truthfulness.


\begin{Cor}\label{cor_threshold}
Under the mechanism in Theorem \ref{pro_payment}, the participation decisions of agents in group $i$ satisfy $d_i(c | \boldsymbol{\theta}^*) = 1$ if $c\le \hat{c}{i}$ and $d_i(c | \boldsymbol{\theta}^*) = 0$ otherwise.
\end{Cor}
This result highlights that, under the mechanism in Theorem \ref{pro_payment}, the decisions of the agents in each group demonstrate a threshold structure with respect to overall cost $c$. Agents in group $i$ will participate and truthfully report her overall cost, if her overall cost is no greater than the threshold $\hat{c}{i}$; otherwise she will not participate.  



\subsection{Properties of the mechanism}\label{sec_properties}

We now study the connections among three key components of the mechanism design: data correlation, group participation rate, and payment (see Properties \ref{pr_pay_ratio}-\ref{pr_ratio_correlation} later in this section).  Existing discussions (e.g., \citet{acemoglu_privacy}) of the connections among data correlation, number of users, and payment, which demonstrated some interesting properties of data trading, motivate our study. For example, \citet{acemoglu_privacy} shows that the total payment to users is non-monotone in the number of users in some scenarios. It is interesting to explore such connections under the settings of this work. Moreover, studying the connections helps uncover the impacts these issues have on the mechanism design under our settings when we incorporate information leakage.

Many of the properties below highlight the complexity of data marketplaces with information leakage.  For example, our first property highlights that, even though a larger average participation rate means more participants,  the total payment for the entire group does not necessarily increase. This is because the individual payment for these agents will decrease as well.

\begin{Prop}\label{pr_pay_ratio}
Given a fixed selection probability $A$, the total expected payment for agents in group $i$ is non-monotonic
{in} the average participation rate of group $i$.
\end{Prop}


However, despite the non-monotonicity of the expected payment 
{in} the average participation rate, there are some intuitive monotonicity properties that do hold for the payment after imposing one additional natural assumption. 


\begin{Prop}\label{pr_payment_correlation}
Suppose the difference $\ppl{\hat{c}{i}}{i}-\gppl{\hat{c}{i}}{i}$ is non-increasing
{in} correlation strength. The payment to the agents in group $i$ who join the platform is decreasing 
{in} both intra-group correlation strength $\intraCor{i}$ and inter-group correlation strength  $\interCor{i}$. 
\end{Prop}

In the property above, we further require the difference function, i.e., $\ppl{\hat{c}{i}}{i}-\gppl{\hat{c}{i}}{i}$, to be non-increasing
{in} both intra-group correlation strength and inter-group correlation strength. Intuitively, this difference can be viewed as the extra privacy cost for the agent with cost equal to $\hat{c}{i}$ due to her own activities on the platform, and thus it might be even independent of data correlation strength. As a consequence, the payment for the agents who join the platform in group $i$ is decreasing in both intra-group and inter-group correlation strength, i.e., $\intraCor{i}$ and  $\interCor{i}$.

Some intuition for the above property comes from the observation that, when there is strong correlation among the agents' data, an individual will suffer a large privacy leakage even if they do not join the platform. As a result, they are incentivized to join the platform even when the individual payment is relatively low. Naturally, given a fixed participation rate profile and allocation rule, the total expected payment for the entire group decreases as a result.


However, in contrast to the above intuition, we do not have monotonicity of the participation rate in this setting, as we show in the property below.  Note that for most of this paper we treat the participation rate as something fixed (and optimized) by the analyst.  However, understanding its behavior is important for performing such an optimization. 


\begin{Prop}\label{pr_ratio_correlation}
In group $i$, the group participation rate is non-monotonic in both the intra-group correlation strength $\intraCor{i}$ and inter-group correlation strength  $\interCor{i}$.
\end{Prop}

To develop some intuition for the above, we note that the analyst's mechanism design is subject to a budget constraint. Although stronger data correlation indicates lower payment, the total expected payment is also affected by the selection probability. If the selection probability increases, the analyst needs to induce a lower group participation rate so that the total expected payment does not exceed the budget. Otherwise, the analyst could induce a higher participation rate. 


Our last property investigates what happens as the budget increases.  In this case the analyst can exploit the additional budget to improve either bias or variance. On the one hand, increasing the selection probability helps reduce the uncertainty of collected data, thus decreases the variance. On the other hand, inducing an equilibrium with a higher participation rate helps cover a wider range of participants' data, thus decreases the bias. 

\begin{Prop}\label{pr_pay_biasvariance}
As budget increases, the estimator achieves a better bias-variance trade-off, i.e., the optimal objective of the overall optimization problem as in Definition \ref{def_mech_design} reduces. 
\end{Prop}



\section{Optimization of the Worst-Case Bias-Variance Trade-off}\label{sec_opt_tradeoff}



We now discuss the design of a mechanism that optimizes the worst-case bias-variance trade-off.  First, we introduce the analyst's choice of estimator in Section \ref{sec_estimator}. Second, we  characterize the worst-case bias-variance trade-off of the estimator, given a selection rule and a participation rate profile at equilibrium, in Section \ref{sec_tradeoff}. Finally, we provide our full mechanism in Section \ref{sec_solution}. 

From a mathematical perspective, our bias-variance optimization problem optimizes over two types of variables: (i) the allocation rule, which is a collection of  probabilities that participants are selected to report their data and get the payments, and (ii) the participation rate profile in equilibrium, which controls the fraction of agents in each group that join the platform in the first place. However, in practice, a platform is unlikely to be willing to sacrifice a high participation rate to improve the performance of any single statistical task. Thus, optimizing over the participation rate is not attractice.  Thus, here, we treat the participation rate as given so that our work can  apply to any platform at any growth stage, e.g., either a start-up platform with a low participation rate or a popular platform with a high participation rate.


In what follows, we first show that the optimal allocation rule under a fixed equilibrium participation rate profile is monotone in the agents' virtual costs, as defined in Definition \ref{def_vcost} in Section \ref{sec_solution}, and provide a closed-form solution for this allocation rule. Given that optimizing over the participation rate is unrealistic, we instead present structural results and conditions for a full participation rate profile. This provides a connection to previous work on data acquisition since, when there is a full participation rate profile, the analyst sees a representative sample of the population and obtains an unbiased estimator. 

\subsection{Estimator}\label{sec_estimator}





The objective of the analyst's mechanism design problem in Definition \ref{def_mech_design} is to minimize the worst-case bias-variance trade-off of a given estimator. In this section, we describe the estimator of our choice. We then characterize its worst-case bias-trade-off variance in Section \ref{sec_tradeoff}. 


The analyst is interested in estimating a population statistic using the mechanism. In this paper, we focus on estimating a mean over the population in question. For example, the analyst wishes to understand the average income, average BMI, or average ratings for a new movie. 


We use the Horvitz-Thompson estimator \cite{HTestimator}, which is the unique unbiased linear estimator for the settings where an analyst must sample at different rates from different sub-populations; in our case, agents in different groups or with different costs may be selected with different probabilities $A(\cdot)$, and in turn define several distinct sub-populations. In such a setting, the standard sample mean estimator is biased towards the sub-populations from which the analyst samples most (relatively to the sub-population size). The Horvitz-Thompson estimator eliminates this bias by re-weighting each data point by the inverse of the selection probability associated with its sub-population. In our setting, the Horvitz-Thompson estimator reweights the data of each agent $k$ by $1/A^k$, where $A^k$ is the selection probability associated with agent $k$.

We define the Horvitz-Thompson estimator formally below in Definition \ref{Def_estimator}. Recall that $\mathcal{N}$ denotes the set of participants (i.e., agents who join the platform) and is of size $N$. Let $\mathcal{O}\subset \mathcal{N}$ denote the set of participants who are selected to report their data. Let $x_k$ be the data of agent $k$.
Suppose that the agents' data is independently and identically distributed. The Horvitz-Thompson estimator is then an unbiased estimator for the mean of data of the participants in set $\mathcal{N}$, i.e., the expectation of the estimator is equal to the expected value of the participants' data.

\begin{Def}[Horvitz-Thompson estimator] \label{Def_estimator}
The Horvitz-Thompson estimator is given by
\begin{equation}
\hat{m} = \frac{1}{N}\sum_{k\in \mathcal{N}} \frac{x_k \cdot \mathbbm{1}\{k\in \mathcal{O}\}}{A^k},
\end{equation}
where $A^k$ is the selection probability for agent $k$.
\end{Def}



Although the estimator is unbiased with respect to the set of participants $\mathcal{N}$, it may be biased with respect to the overall agent set $\mathcal{S}$, when the average participation rate is less than one. When some agents do not participate, their data are not fed to the estimator and the estimator fails to capture the information of the non-participants. On the other hand, if the average participation rate is equal to one, i.e., all the agents are willing to participate, the estimator is naturally unbiased.  In conclusion, the participation rate at equilibrium is an important factor in the issue of estimation bias. Since there is an intrinsic trade-off between bias and variance, the  analyst might prefer low variance instead of low or zero bias in some cases, e.g., when the linear weight associated with the variance in equation \eqref{equ_mech_design} is high and the budget is large enough to use a large selection probability. Later, in Section \ref{sec_solution}, we present conditions under which the analyst prefers to enforce a full participation rate to achieve an unbiased estimator. 


\subsection{Characterizing the worst-case bias-variance trade-off}\label{sec_tradeoff}
We characterize the worst-case bias-variance trade-off of the estimator in this section. We start by introducing some key notation. For simplicity,  we assume that the agent's data is binary from the set of $\{0,1\}$. In Remark \ref{rem_tradeoff}, we highlight that our analysis can be generalized to continuous data in $[0,1]$. The probability of an agent being in group $i$ is denoted by $\groupProb{i}$. Let $\mathbf{q}\triangleq [\groupProb{i}]_{1\le i\le I}$. Let $p_{i}(c) \triangleq Pr[x = 1|c, i]$ denote the probability of an agent $k$ with cost $c$ in group $i$ having data point $x_k = 1$. Recall that according to Corollary \ref{cor_threshold}, an agent in group $i$ will join in the platform if her cost $c$ is no greater than the participation threshold $\hat{c}{i}$. Let $A \triangleq \{\selectionProb{c}{i}\}_{1\le i\le I}$, consisting of the selection probabilities in all groups. Furthermore, we assume a positive correlation between data and cost, which is mathematically described as follows.
\begin{assumption}\label{a_positivecorrealtion}
For each group $i$, $p_{i}(c)$ is a non-decreasing function of cost $c$. 
\end{assumption}
The assumption is often reasonable in practice. If the agent's data is of a higher value, then her cost is more likely to be higher as well, and vice versa. For example, agents with a higher income or higher BMI might care more about their privacy, hence their reporting costs tend to be higher for them as well.


\begin{Lem}\label{lem_tradeoff}
Under Assumption \ref{a_positivecorrealtion}, fix allocation rule $A$ and participation rate profile $\boldsymbol{\theta}^*$. Conditional on $\mathcal{N}$, the \textcolor{black}{supremum}  of linear combination of bias and variance of the estimator $\hat{m}$ in Definition \ref{Def_estimator} is 
\begin{equation}\label{equ_tradeoff}
\begin{aligned}
T(A,\boldsymbol{\theta}^*) = &\sup_{f \text{ consistent with } \mathcal{D}}  \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation)\\& =\sup_{p_{i}(c)\in [0,1], c \le \hat{c}{i} } \frac{\lambda}{s\left(\bar{\theta}^*\right)^2}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\frac{p_i(c)}{\selectionProb{c}{i}}f_i(c)dc-\frac{1}{\bar{\theta}^*}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right)^2\right) \\ &+(1-\lambda)(1-\bar{\theta}^*) \cdot \left(1-\frac{1}{\bar{\theta}^*}\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right).
\end{aligned}
\end{equation}
\end{Lem}



\begin{remark}\label{rem_tradeoff}
While we focus on the binary data case, we note that if the agents' data points $x_k$ are taken from the interval $[0,1]$, our proof can immediately be adapted to show that
\begin{equation}
\begin{aligned}
T(A,\boldsymbol{\theta}^*) = &\sup_{f \text{ consistent with } \mathcal{D}}  \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation)\\ \le& \sup_{p_{i}(c)\in [0,1], c \le \hat{c}{i} } \frac{\lambda}{s\left(\bar{\theta}^*\right)^2}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\frac{p_i(c)}{\selectionProb{c}{i}}f_i(c)dc-\frac{1}{\bar{\theta}^*}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right)^2\right) \\ &+(1-\lambda)(1-\bar{\theta}^*) \cdot \left(1-\frac{1}{\bar{\theta}^*}\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right).
\end{aligned}
\end{equation}

\noindent That is, the expression that we optimize over is an over-estimate of the worst-case bias-variance trade-off; in turn, our approach still provides an upper bound and does not underestimate the bias-variance trade-off when the data is non-binary. 
\end{remark}

The proof of Lemma \ref{lem_tradeoff} and Remark \ref{rem_tradeoff} are in Appendix \ref{apendixsec_tradeoff}. The basic idea is to derive the variance and the worst-case bias separately, and they both are fully characterized by the distribution of participants' data (i.e., $p_i(c)$ for $c\le \hat{c}{i}$). Thus, optimizing a linear combination of bias and variance gives the worst-case linear combination of bias and variance.


Lemma \ref{lem_tradeoff} presents  an  analytical formulation of the objective function with an auxiliary variable $p_i(c)$. This  facilitates our later analysis of the optimization problem, which is the minimization of \eqref{equ_tradeoff} subject to truthfulness constraint and budget constraint.

To conclude the subsection, we provide some interpretation about how the allocation rule $A$ and participation rate profile $\boldsymbol{\theta}^*$ affect the trade-off between bias and variance.   If the value of allocation  rule $A_i(c)$ is higher, the variance $\mathbb{V}(\estimator; \jointD, \allocation)$ is lower. However, due to the budget constraint, a higher value of allocation  rule indicates a lower participation rate, which means a possibly higher bias. Thus, due to the budget constraint,  the analyst needs to carefully trade off bias and variance. 

The analyst's objective is to minimize the above  worst-case bias-variance trade-off by choosing the allocation rule $A$ and the participation rate profile $\boldsymbol{\theta}^*$ in the equilibrium.  Next, we discuss the optimal allocation rule and participation rate profile in details.

\subsection{Optimal Allocation Rule and Conditions of Full Participation Rate}\label{sec_solution}

We now derive solutions to the worst-case bias-variance trade-off optimization problem under the budget and truthfulness constraints. First, we present the optimal allocation rule given the participation rate profile at equilibrium. Second, we identify sufficient conditions under which the optimal participation rate is one and the analyst obtains an unbiased estimator. 

\subsubsection{Optimal Allocation Rule}
We first study the design of the allocation rule, given a desired participation rate profile $\boldsymbol{\theta}^*$ at equilibrium. Recall that we focus on $\boldsymbol{\theta}^*$ in which $\bar{\theta}^*_i\ge \bar{\theta}_{\min}, \forall i$ for some positive value $\bar{\theta}_{\min}>0$ to avoid the trivial case of complete non-participation of a group. 

In this section, we first introduce the notion of virtual cost in Definition \ref{def_vcost}, which is analogous to the classical notion of virtual value in~\cite{myerson}. The virtual costs help characterize the payment function that, given a fixed allocation rule, induces agents to report their privacy costs truthfully. The characterization of payment function is in Theorem \ref{pro_payment}.  We note that the virtual cost of an agent in group $i$ depends on her privacy cost ($ \pplequ{c}{i}$) and the cost distribution ($F_i$ and $f_i$) in group $i$. 

\begin{Def}[Virtual Cost]\label{def_vcost}
 In group $i$, given participation rate profile $\boldsymbol{\theta}^*$, the virtual cost of an  agent with cost $c$ is 
 \begin{equation}\label{equ_vcost}
 \phi_i(c;\boldsymbol{\theta}^*) = c-\pplequ{c}{i} + (1-b(\boldsymbol{\theta}^*_i;\boldsymbol{\alpha}_i))\frac{F_i(c)}{f_i(c)}.
 \end{equation}
 Here, $F_i$ and $f_i$ are cdf and pdf of cost in group $i$, respectively. 
 \end{Def}

Recall that the vector $\boldsymbol{\theta}^*_i$  consists of $\bar{\theta}^*_i$ and  $\bar{\theta}^*_{-i}$. The virtual cost $\phi_i(c;\boldsymbol{\theta}^*)$  in group $i$ is decreasing in the within-group participation rate $\bar{\theta}^*_i$ and the outside-group rate $\bar{\theta}^*_{-i}$, as $h(\cdot)$ and $b(\cdot)$ are increasing in both  $\bar{\theta}^*_i$ and  $\bar{\theta}^*_{-i}$. Recall that a higher participation rate means more privacy cost. Furthermore, we assume that the virtual cost within a group is non-decreasing in cost $c$ as in \cite{dataacquisition,myerson} (Assumption \ref{a_regularity}). Note that a uniform distribution is one example satisfying the assumption.    

\begin{assumption}\label{a_regularity}[Regularity]
The virtual cost $\phi_i(c;\boldsymbol{\theta}^*)$  in group $i$ is non-decreasing. Furthermore, $f_i(c)$ is twice differentiable, in which case $F_i(c)f'_i(c)\le2(f_i(c))^2$.
\end{assumption}


 



Now we are ready to present the optimal allocation rule of each group.
\begin{The}\label{the_opt_pro}
	Under Assumptions \ref{combine}-\ref{a_regularity}, given
	a desired participation rate  profile $\boldsymbol{\theta}^*$, the optimal allocation rule of group $i$ is


	\begin{align}\label{equ_general_opt_pro}
	    A_i(c) = \begin{cases}\chi, \ \ &\text{if} \ \  \phi_{i}(c;\boldsymbol{\theta}^*) \le \hat{\phi}, \\
	\frac{\eta}{\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}}, \ \ &\text{if} \  \ \hat{\phi}<\phi_{i}(c;\boldsymbol{\theta}^*)\le \phi_{i}(\hat{c}{i};\boldsymbol{\theta}^*).
	\end{cases}
	\end{align}
The characterizations of the constants $\eta$, $\chi$, and $\hat{\phi}$ depends on the system parameters including the budget $B$, number of agents $s$, distribution of virtual cost. See \eqref{equ_continuousA} in Appendix \ref{appendixsec_proof_the_opt}.
\end{The}




 



















\begin{wrapfigure}{r}{0.5\textwidth}
    \centering
    \includegraphics[width=.38\textwidth]{allocationrule.jpg}
    \caption{Illustration of two possible structures.}
    \label{fig_allocationrule}
\end{wrapfigure}
Theorem \ref{the_opt_pro} shows the optimal allocation rule of a group can have two possible structures: \emph{Fixed then Decreasing} (FtD) or  \emph{Strictly Decreasing} (SD), depending on system parameters such as budget $B$. Figure \ref{fig_allocationrule} provides an illustration. The FtD structure (the blue and red curves in Figure \ref{fig_allocationrule}) has an allocation rule  for the group that is firstly fixed in low-cost region (i.e., the region in which  $\phi_{i}(c;\boldsymbol{\theta}^*) \le \hat{\phi}$ holds) and then strictly decreasing in the high-cost region (inversely proportional to the square root of the virtual cost). Since the allocation rule is not strictly decreasing, the mechanism can only induce agents' weak (non-strict) truthfulness, according to Theorem \ref{pro_payment}. The other structure, SD (the orange curve in Figure \ref{fig_allocationrule}),  has an  allocation rule that is strictly decreasing (inversely proportional to the square root of the virtual cost) in the whole region. The strictly monotonic structure induces strict truthfulness.
{Note that the form of the optimal allocation rule parallels that of previous work~\cite{dataacquisition}, showing that a similar form is still optimal in a more general setting. As we have discussed, the generalization beyond~\cite{dataacquisition} to include the analyst's bias-variance trade-off, the agents' privacy costs, and data correlation add technical complexity and practicality. A priori, it is not clear that the optimal form would remain similar in the more general setting.}






Note that the optimal allocation rule presented in Theorem \ref{the_opt_pro} is defined for the  participating agents, whose cost are lower than threshold $\hat{c}{i}$ for group $i$. As in the case of non-participants, we only need to ensure monotonicity to induce truthfulness. A simple example is $A_i(c)=\epsilon$ for $c\ge \hat{c}{i}$, where $\epsilon$ is a small enough non-negative value. Note that this example does not make the total expected payment exceed the budget, as the non-participants do not get the payments.   In summary, the allocation rule of the cost lower than the threshold presented in Theorem \ref{the_opt_pro} and the allocation rule of the cost higher than the threshold make up a complete menu shown to the agents, which induces agents' truthfulness and optimizes the bias-variance trade-off.


We find that, when the budget $B$ is relatively small, the optimal allocation rule has a Strictly Decreasing structure. To state the result, first define 

\begin{equation}
 l(\boldsymbol{\theta}^*)\triangleq \sum_{i} q_i \bar{\theta}^*_i(\pplequ{\hat{c}{i}}{i}-\gpplequ{\hat{c}{i}}{i}-w(\bar{\theta}^*)).
\end{equation}
    \begin{Cor}\label{cor_opt_pro}
    Under Assumptions \ref{combine}-\ref{a_regularity}, the optimal allocation rule is 
    \begin{equation}
    A_i(c) = \frac{1}{\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}} \cdot\frac{B/s-l(\boldsymbol{\theta}^*)}{\sum_{i}\groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}f_i(c)dc},
    \end{equation}
    when the participation rate profile $\boldsymbol{\theta}^*$ satisfies the following inequality:
    \begin{equation}\label{equ_a}
        (B/s-l(\boldsymbol{\theta}^*))(2\lambda+\bar{\theta}^*(1-\bar{\theta}^*)(1-\lambda)s)<\lambda\sqrt{\phi_{\min}(\boldsymbol{\theta}^*)} \cdot\sum_{i}\groupProb{i} \int_{c_{\min}}^{\hat{c}{i}}\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}f_i(c)dc.
    \end{equation}
    Furthermore, the mechanism is strictly truthful.
    \end{Cor}
    

Corollary \ref{cor_opt_pro} is a special case of Theorem \ref{the_opt_pro}.  The inequality in (\ref{equ_a}) indicates that the budget is relatively low. Suppose the budget is large enough.  The analyst can keep the allocation rule in the low-cost region fixed, instead of strictly decreasing. In this case, the agents' reporting is weak truthful. However, if the budget is low as in (\ref{equ_a}), the optimal allocation rule is strictly decreasing, which induces agents' strict truthfulness. Strict truthfulness is a more desirable property than weak truthfulness.






\subsubsection{Sufficient Conditions for Unbiased Estimation}  

Next, we present simple, easy to verify, sufficient conditions for unbiased estimation. We focus on the low-budget regime, which induces agents' strict truthfulness, according to Corollary \ref{cor_opt_pro}. By substituting the allocation rule in Corollary \ref{cor_opt_pro} to the objective function (\ref{equ_tradeoff}), we arrive at an optimization problem  over $\boldsymbol{\theta}^*$ as follows:
\begin{equation}\label{equ_obj_ratio}
\max_{\boldsymbol{\theta}^*}  \ \  T^*(\boldsymbol{\theta}^*) = \frac{\lambda}{s}\left(U(\boldsymbol{\theta}^*)-\frac{1}{\bar{\theta}^*}\right),
    \end{equation}
where 

\begin{equation}\label{equ_L}
        U(\boldsymbol{\theta}^*) \triangleq  \frac{1}{\left(\bar{\theta}^*\right)^2}\cdot \frac{\left(\sum_{i}\groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}f_i(c)dc\right)^2}{B/s-l(\boldsymbol{\theta}^*)}.
    \end{equation}
The objective function in (\ref{equ_obj_ratio}) is complicated due to the complexity of $l(\boldsymbol{\theta}^*)$ in (\ref{equ_L}).  Furthermore, the complicated characterization of its derivative with respect to group $i$'s participation rate $\bar{\theta}^*_i$ adds to the complexity. Thus, we focus on identifying sufficient conditions under which the optimal participation rate is one, meaning that the analyst would like to have unbiased estimator. 

To begin, we introduce some notation and assumptions. We denote the full participation rate profile by $\boldsymbol{\theta}_f\triangleq [1]^I\in \mathbb{R}^I $, each component of which is one. We define $\Delta_i \triangleq \ppl{\hat{c}{i}}{i}- \gppl{\hat{c}{i}}{i}$. It captures the additional privacy cost of an participant (compared with non-participation) whose cost is the cost threshold in group $i$. 

We now present sufficient conditions for achieving full participation and an unbiased estimator.


\begin{Pro}\label{Pro_fullpart_benefit}
Suppose that, for all $\boldsymbol{\theta}^*$ in which $\bar{\theta}^*_i\ge \bar{\theta}_{\min}>0, \forall i$,  (i) the inequality in (\ref{equ_a}) holds, and (ii) $w'(\bar{\theta}^*)\ge  D_i(\boldsymbol{\theta}^*,B,\lambda,s,\mathbf{q})$ holds for the function $D_i(\boldsymbol{\theta}^*,B,\lambda,s,\mathbf{q})$ defined in \eqref{equ_D} of Appendix \ref{appendixsec_fullpart_benefit},  where $w'$ is the derivative of function $w(\cdot)$.  Then, the optimal participation rate profile is $\boldsymbol{\theta}_f$ and the analyst obtains an unbiased estimator.
   
   
   
   
   
   
       
   
   
   
   
   
   
        
    \end{Pro}
    




\begin{Pro}\label{pro_fullpart_loss}
Suppose that, for all $\boldsymbol{\theta}^*$ in which $\bar{\theta}^*_i\ge \bar{\theta}_{\min}>0, \forall i$, (i) the inequality in (\ref{equ_a})  holds, and (ii) $\frac{\partial \Delta_i}{\partial \bar{\theta}^*_i}\le  \delta_i(\boldsymbol{\theta}^*, B,\lambda,s,\mathbf{q})$ holds for the function $\delta_i(\boldsymbol{\theta}^*, B,\lambda,s,\mathbf{q})$ defined in \eqref{equ_delta} of Appendix \ref{appendixsec_fullpart_loss}. Then, the optimal participation rate profile is $\boldsymbol{\theta}_f$ and the analyst obtains an unbiased estimator.
   
   
   
   
   
    
   
   
   
   
   
   
   

    \end{Pro}
    
    The proofs of Proposition \ref{Pro_fullpart_benefit}
and Proposition \ref{pro_fullpart_loss} are in Appendix \ref{appendixsec_fullpart_benefit} and Appendix \ref{appendixsec_fullpart_loss}, respectively.    To understand the conditions in these two propositions, note that Condition (i) in both propositions indicates that the budget is ``small'', i.e., lower than a certain threshold, which is related to the expectation of virtual cost in the population. It ensures that the allocation rule is strictly decreasing, according to Corollary \ref{cor_opt_pro}. Further, it holds if the budget itself is relatively low, or if the expectation of the virtual cost is relatively high. Recall that in the definition of virtual cost (Definition \ref{def_vcost}), the virtual cost is determined by both the cost and data correlation strength. In summary, Condition (i) indicates that the overall cost is relatively high, or the data correlation strength is relatively weak, or the budget is relatively low. 
    
Next we discuss Conditions (ii) in the above two propositions. Recall that the participation benefit  $\benefit{\bar{\theta}}$ is increasing in the participation rate. Condition (ii) in Proposition \ref{Pro_fullpart_benefit} implies that the increment of this benefit is high as average participation rate increases, which indicates that the participation benefit is large. Meanwhile, recall that  $\Delta_i= \ppl{\hat{c}{i}}{i}- \gppl{\hat{c}{i}}{i}$ captures the addition part of the privacy cost that  does not concern data correlation. Condition (ii) in Proposition \ref{pro_fullpart_loss} implies that the increment of this part of the privacy cost is small as the group participation rate increases, which indicates that the privacy cost of participation is closed to that of non-participation. Intuitively, if Conditions (ii) in the above two propositions holds,  the analyst does not need to pay a lot to each agent to incentivize her participation. This is because the benefit of participation is significant (Condition (ii) in Proposition \ref{Pro_fullpart_benefit}) or the negative impact of participation is small (Condition (ii) in Proposition \ref{pro_fullpart_loss}). As a result, the expected payment of each agent is relatively low. This enables the analyst to increase the participation rate and  incentivize more fraction of the population. This finally leads to  a full participation rate to induce zero bias. 
  
  
\section{Concluding Remarks}

In this paper we study the design of an optimal mechanism for data acquisition in a setting where there is correlation among the data of participants that leads to information leakage.  Information leakage is a crucial and under-explored feature of data markets and our results represent the first to characterize an optimal mechanism for data acquisition in such a setting.  Additionally, our results provide the analyst the ability to optimally trade off bias and variance of the resulting estimator.  

Further, our results provide important perspectives about the consequences of correlation and information leakage for data marketplaces.  In particular, intuitively one might expect that these factors, which underlie the privacy paradox, would lead to inefficiencies where data marketplaces  exploit participants and obtain data for lower prices than otherwise.  The analysis in this paper shows that this is indeed the case.  Combined with the results of \cite{acemoglu_privacy}, there is a compelling argument that information leakage is a significant factor in market inefficiencies that lead to oversharing and reduced payments in data marketplaces.  

Thus, one may ask if it is possible to regulate data marketplaces to avoid such inefficiencies.  Unfortunately, our results highlight that typical suggestions, such as avoiding monopolistic platforms, may not be effective.  Since our results hold for any fixed participation rate, a platform can exploit information leakage regardless of its market size.  Further, differential privacy cannot eliminate the underlying issues in this case, which comes from inter-group and intra-group correlation.  Thus, an important open problem motivated by our work is: what approaches can be brought to bear to mitigate the impact of information leakage and the privacy paradox in data marketplaces?   


\bibliographystyle{unsrtnat}


\section{Introduction}

There is a fundamental discrepancy between privacy attitudes and the  behaviors of users online: users claim to be concerned about their privacy but do little to protect privacy in their actions. More specifically, users express their concerns about privacy, including the ambiguous distribution of data and its use by third party \cite{Informationprivacyresearch, acquisti2017nudges, goldfarb2012shifts}; however, when choosing services, users mainly focus on the popularity, convenience, price, etc, despite the potential risk of data misuse \cite{Informationexamining,examination}. This phenomenon is known as the \emph{privacy paradox} \cite{privacyparadox} and understanding the reasons behind this paradox and its consequences for the design of online platforms is an important goal for both computer scientists and economists.  

The privacy paradox is at the root of the behavior of individuals in modern online data marketplaces.  Online platforms gather data on billions of individuals in order to personalize advertising and customize other aspects of their systems.  However, such usage tends to provide little direct benefits for the users, a fact that is used as indirect evidence to argue that users provide a small value on privacy \cite{athey2017digital}.  Such an argument ignores the impact that an individual's participation decision has on others.  In particular, when an individual shares her data, it is not just her privacy that is compromised; the privacy of other individuals whose data is correlated with hers is also compromised. Thus, these other individuals are more likely to share their own data given that some has already been leaked \cite{acemoglu_privacy}. This simple, but often overlooked issue is at the root of the privacy paradox.  Information leakage due to correlation has been shown to lead to oversharing since each individual overlooks their own privacy concerns as a result of the negative externalities created by others' revelation decisions.  Thus, information leakage leads to the potential for significant economic and social inefficiency in data marketplaces.

In this paper, \emph{we study the impact of privacy concerns and information leakage on the design of data markets.} Specifically, we study the task of designing mechanisms for obtaining verifiable data from a population for a statistical estimation task, such as estimating the expected value of some function of the underlying data.

The goal of designing mechanisms for optimal data acquisition is a core piece of the emerging literature on data marketplaces.  A common motivating example is a setting where a healthcare platform is doing statistical analysis on its population of users.  While some data is measured accurately from their smart devices, other desired data may be about characteristics users do not wish to provide or may vary over time. Thus the healthcare platform has to conduct a survey among the users to obtain such information accurately  (e.g. giving the individual a smart device or having the individual fill out a form); however when administering such a survey the responses are likely biased. For example, if weight is the target, then the respondents may be biased towards low-weight samples.  Thus, the task of designing mechanisms to limit the bias and reduce the variance of estimates obtained from such surveys is crucial.  However, such a task is challenging due to the fact that the analyst does not know the distribution of the data and has a limited budget.   

A growing line of work has focused on the design of such optimal data acquisition mechanisms, e.g., \cite{aaron_grant, dataacquisition, shuran_yiling, abernethy2015low}.  Initiated by \cite{abernethy2015low, aaron_grant}, this line of work has led to the design of mechanisms for unbiased estimation with minimal variance in a variety of settings. However, in this literature it is assumed that all individuals will participate, thus unbiased estimation is possible.  The trade-off between bias and variance has been ignored to this point with the exception of \citet{shuran_yiling}, which still assumes all individuals will participate and does not consider privacy concerns.  Further, this line of work has not considered the issues created  by information leakage due to correlation between the participants. Information leakage creates significant incentives for increased data sharing and thus mechanisms that do not consider it directly will suffer from undetected bias and increased variance in the obtained estimates.  Modeling the incentives created by leakage potentially provides the analyst the opportunity to obtain an estimator of the same quality using a smaller budget, due to the externalities created by data correlation.




\textbf{Contributions.} In this paper, we provide the first characterization of an optimal mechanism for data acquisition in the setting where agents are concerned about privacy and their data is correlated with each other. As a result, information leakage due to data correlation not only contributes to an agent's privacy cost, but also to the privacy costs of others with correlated data. Additionally, the mechanism allows, for the first time, a trade-off between the bias and variance of the estimator when privacy cost is considered. This offers the analyst freedom to tailor towards an emphasis on either bias or variance of the estimator depending on the contextual goals.

Specifically, we propose a novel model for data acquisition. The novelty of our model is a result of three important components. 
First, we introduce the privacy cost to model impacts of data correlation. Unlike modeling data correlation on an individual level in \cite{acemoglu_privacy},
we divide the agents into different groups and assume that agents within the same group share a same correlation strength. This gives us the power to work with any granularity of choice with regard to data correlation. For example, if every group has a relatively small size of agents, then our model of data correlation shifts towards a near individual level. In addition, an agent suffers a larger privacy cost if she joins the platform than that if she does not join. The choice of our privacy cost function enables us to model all these desired properties. Second, in reality, not every agent always decides to join the platform. Thus, we introduce the notion of participation rate as the ratio of the number of agents who join the platform to the number of total agents. This further allows us to study equilibrium with respect to participation rate, which is crucial since the mechanism impacts the participation rate, which in turn impacts the bias and variance. Third, given that not every agent always joins the platform, it is not always realistic to aim for an unbiased estimator. Instead, we minimize a linear combination of bias and variance of the estimator. Via a choice of constant weights for bias and variance, we are able to balance between these two metrics of the estimator as desired.

Our main theoretical results provide a closed form solution of payment and allocation rules under a choice of equilibrium participation rate in order to achieve a truthful mechanism (Theorem  \ref{pro_payment} $\&$  Theorem \ref{the_opt_pro}). More specifically, we aim to minimize a linear combination of bias and variance subject to budget and truthfulness constraints. By considering a linear combination, we are able to emphasize either bias or variance of the estimator as desired. Moreover, we provide conditions for the optimality of an unbiased estimator in the case when it is possible to achieve a full participation rate, i.e. every agent decides to join the platform.

Our results offer some interesting insights about mechanisms for data acquisition. First, an unbiased estimator is possible even if the budget is relatively small because we can meet the expected budget constraint using a small selection probability. However, an unbiased estimator is not always realistic in practice. As a result, it is important to optimize the bias-variance trade-off. Second, incorporation of privacy cost due to information leakage and sharing makes it possible for the analyst to underpay the agents to acquire the same data set. This can potentially lead to a relatively small payment for data, something that is frequently seen in practice. Last but not least, the privacy cost from leakage encourages more agents to join the platform, which coincides with the data oversharing phenomenon frequently observed in platforms today.



The design of mechanisms for data acquisition is known to be challenging even if we focus on an unbiased estimator and ignore privacy cost due to data correlation. However, obtaining our results requires overcoming additional challenges.  There are two technical innovations that enable our analysis. First, we need to introduce and characterize an equilibrium with respect to the participation rate, as the participation rate is an endogenous property of the mechanism design problem. This equilibrium adds considerable complexity to the analysis, but also provides insights about how the data acquisition mechanism depends on the popularity of the platform. Second, we introduce the notion of data correlation strength to characterize the privacy cost due to information leakage. This allows us to capture the impact of data correlation on the platform. Further, depending on a choice of group sizes, we are able to model information leakage at different granularity levels as desired.


\textbf{Related Literature.} The design of data markets has attracted a significant amount of interest in recent years. There is growing body of work studying a variety of aspects of data markets, including monetizing information via either dynamic sales or optimal mechanisms, e.g., \cite{babaioff2012optimal, horner2016selling}, exploiting personal information to improve allocation of resources in online markets, e.g., \cite{goldfarb2011online, bergemann2015selling, montes2019value}, optimal acquisition of information, e.g., \cite{aaron_grant, dataacquisition, shuran_yiling}. For a recent survey see \cite{bergemann_data_markets} and the references therein. Our work broadly falls into the last line of work, and focuses on the design of a mechanism for optimal data acquisition. The study of the optimal data acquisition has attracted a growing amount of attention across both economics and computer science. In this paper, we focus on designing a truthful mechanism in order to perform a statistical estimation task. This goal has received considerable attention. However, prior work does not consider the privacy cost of the participants.  Our work aims to fill the gap by considering privacy cost as an important factor for individuals' decision-making. 

In more detail, the prior work on optimal data acquisition can be divided into two categories depending on whether data is verifiable or not. In the first category, individuals' utilities often directly depend on the outcome of the statistical inference and they thus have an incentive to misreport their data, e.g., \cite{liu2016learning, liu2017sequential, liu2018surrogate, dekel2010incentive, meir2011strategyproof, meir2012algorithms, perote2003impossibility}. This is possible since there is no ground truth to verify the data. In the second category, individuals are assumed to report their data truthfully due to the ability of the analyst to verify the data, e.g., \cite{cummings2015accuracy,cai2015optimum,abernethy2015low, shuran_yiling, aaron_grant, dataacquisition}. In this paper, we consider the setting where data is verifiable and so focus our discussion on prior work in that category below.


The task in this context is to purchase data from individuals whose private costs are subject to an (expected) budget constraint. This model was introduced in \cite{abernethy2015low, aaron_grant}. The model assumes that data cannot be fabricated and that private costs of the participants are correlated with the data. Moreover, the participants do not derive utility or disutility from the estimation outcome. \citet{aaron_grant} minimizes a bound of the worst case variance while achieving an unbiased estimator while \citet{abernethy2015low} considers general supervised learning. Following these initial papers, a closed form result that directly minimizes the worst case variance is given in \cite{dataacquisition}. However, unbiased estimators are not always possible in realistic settings. When a biased estimator is considered, \citet{shuran_yiling} proposes a slightly different model, in which agents arrive in an online fashion and cost distribution is not known a priori. Under this model, \citet{shuran_yiling} studies a trade-off between bias and variance of the estimator rather than only focus on the unbiased estimators. This trade-off is also a core component of our work. 


The prior work discussed above mostly focuses on data acquisition without considering the privacy concerns of the participants. Even when the privacy concerns are considered in the prior work, privacy cost is often interpreted as a simple cost, which does not capture the information leakage due to data correlation.  In contrast, privacy cost due to information leakage as a result of data correlation is a crucial concern in the model we consider in this paper. There is a recent line of work that examines data acquisition through the lens of differential privacy \cite{ghosh_selling_privacy,cummings2015accuracy,fleischer2012approximately,buyingwithoutverification,nissim_redrawing}. As agents might not be willing to report their data due to their privacy concerns, monetary incentives are given to encourage individuals to participate in order to balance between privacy of individuals and accuracy of estimation. However, in this line of work, the  impact of information leakage is not considered and thus the practical impact of the privacy paradox is not considered.

The information leakage that results from correlation between individuals' is at the root of the privacy paradox and is a crucial factor for data markets, as has been recognized by recent work in economics, e.g.,\cite{liao2018social,acemoglu_privacy}.  More specifically, \citet{acemoglu_privacy} recently introduced the concept of information leakage to account for privacy cost due to other individuals' data sharing.
Inspired by this, we incorporate the privacy cost due to heterogeneous data correlation in our model and aim to design a truthful mechanism to balance between bias and variance subject to an expected budget constraint.  The privacy concern of individuals, specifically the privacy cost due to data correlation, is essential in the design of such a mechanism. This is a critical feature of our model that is not present in any prior work on data acquisition.  The setting and model we consider differ considerably from \cite{acemoglu_privacy}.  We consider the problem of optimal data acquisition and the incentives created by information leakage, which have not been considered in this context.


\section{System Model}

We consider an online platform consisting of an analyst and many agents.  At a high level, the analyst aims to design a pricing mechanism to purchase private data from agents in order to perform a statistical estimation task, e.g., estimate the mean of the agents' data. Ideally, the analyst would like to purchase all the private data to obtain an unbiased estimator. However, given a limited budget, the analyst has to design a pricing mechanism to wisely select the data in order to balance between the bias and variance of the estimator.


To this end, we consider a family of pricing mechanisms that presents a menu to the agents. The menu consists of pairs of payments and probabilities of having agents' data selected for use in the estimation task. Given the menu, the agents report their costs and decide individually if they would like to join the platform or not. Once the agents make the decisions, the analyst selects data from an agent on the platform to purchase with the given probability selected from the menu. The analyst's goal in designing the mechanism is to determine the menu of payments and selection probabilities in order to perform a statistical estimation subject to an expected budget constraint. The form of this mechanism is classical, and adopted from, e.g., \cite{aaron_grant,dataacquisition,abernethy2015low}.



Considering privacy cost is critical to the design of such a mechanism. For the agents on the platform, they obtain benefit from participation but reveal some personal information through their interactions with the platform, which leads to the privacy cost. Further, when an agent's data is used, it negatively impacts not only the privacy of the agent revealing the data, but also the privacy of other agents whose data is correlated. Thus, even though some agents do not join the platform and do not directly share their data, they may still suffer a privacy cost through their peers' interactions with the platform due to data correlation. This privacy cost via \emph{information leakage} is an important and novel feature of the model presented here. 

We describe the full details of the model and the family of mechanisms we consider in the remainder of this section.  Figure \ref{fig:model} provides an overview of the model.


\begin{figure}[t]
    \centering
    \includegraphics[width=0.95\textwidth]{model}
    \caption{An illustration of the model from the perspective of a participating agent in group $i$.}
    \label{fig:model}
\end{figure}



\subsection{Agent model} \label{sec:agent}


We consider $s$ agents that hold data of interest to the analyst.  The set of agents is denoted by $\mathcal{S}$. Every agent owns a data point. By reporting her data to the platform's survey, the agent incurs an overall cost $c$, which is known to her but not to the analyst. The overall cost consists of a combination of reporting cost and privacy cost, where the reporting cost results from the act of reporting the data while the privacy cost comes from both data sharing and data correlation. We discuss these costs further in Section \ref{sec:privacy}. 

We now present how the mechanism works. First, each agent is presented a price menu by the analyst that consists of a payment rule $P$ and selection probability $A$, both of which depend on the reported cost $\tilde{c}$ of the agent. We interchangeably use selection probability or allocation rule, as convenient. Second, given the menu, an agent decides if she would like to join the platform. An agent who decides to join the platform is asked to report her cost, which determines the payment and selection probability. The payment $P$ is given to the agent if she joins the platform \emph{and} her data is selected (used) by the analyst.   More specifically, her data is selected with probability $A$, and she receives the payment only if her data is selected.


Whether an agent decides to join the platform relies on weighing the benefit of participation $w(\cdot)$, plus a potential payment, against the privacy cost that occurs as a result of her own or her peers' interactions with the platform. More specifically, for an agent on the platform, her privacy cost incurred includes both the cost from the agent herself sharing her data and the privacy cost due to her friends' sharing of possibly correlated data. We use $\h$ to denote this combination.  In contrast, if an agent does not join the platform, she still suffers a  privacy cost $\g$  due to information leakage as a result of correlation between her data and the data of those agents who do join.
We use $\mathcal{N}$ to denote the set of agents who join the platform.
For agent $k$, her utility is as follows:
\begin{equation}\label{equ_uti_parameterized}
    \utility{\tilde{c}}{c}{i} = \begin{cases}
        -\g, &\text{if } k \not\in \mathcal{N}, \\
        -\h+w(\cdot), &\text{w/ prob. } 1-A, \text{ if } k \in \mathcal{N},\\ 
        P -c + w(\cdot), &\text{w/ prob. }  A, \text{ if } k \in \mathcal{N}.
    \end{cases}
\end{equation}


Up to this point, we have described the model in a general way, without giving details on the form of the benefit of participation ($w(\cdot)$) and privacy cost ($\g$ and $\h$).  In the remainder of this section, we introduce relevant models of these functions, which illustrate a variety of parameterized forms motivated by different potential settings. 



\subsubsection{Participation Benefit}

The participation benefit is the non-negative value received by agents who take advantage of the service provided by the platform. Intuitively, the more participants the platform attracts, the more valuable the platform's service becomes. Take Facebook as an example, the more friends of a user use Facebook, the more valuable Facebook as a social network is to this user. However, in light of the limited budget in practice, it is almost impossible to have every agent join the platform. As a result, we define the average participation rate of the population $\bar{\theta}$ to be the ratio of number of agents on the platform to the population of agents. The average participation rate $\bar{\theta}$ can be viewed as a measure of the popularity of the platform.\footnote{The participation rate is determined endogenously via the equilibrium, which we discuss in Section \ref{sec:mechanism}.} Moreover, let $\benefit{\bar{\theta}}$ denote the participation benefit as a continuous function of the average participation rate. The participation benefit is assumed to be non-decreasing in the average participation rate of the population $\bar{\theta}$. 

\subsubsection{Correlation Strength.}
Whether an agent decides to join the platform or not, an important source for her privacy cost comes from the information leakage due to data correlation. A stronger correlation naturally leads to more leakage and induces a larger privacy cost. Intuitively, if an agent's data is highly correlated with the rest of the agents, then she has a relatively large correlation strength.
Moreover, some agents might share a stronger correlation with each other within a group of agents than with others outside the group. For instance, on a healthcare related platform, users who carry a common disease might share a similar pattern and thus their data is possibly highly correlated with each other. In order to capture the inter-group versus intra-group difference, we divide $s$ agents into $I$ groups, and agents within the same group $i$ share a common correlation strength $\boldsymbol{\alpha}_i$. The correlation strength vector $\boldsymbol{\alpha}_i$ is further defined as $\boldsymbol{\alpha}_i \triangleq (\intraCor{i}, \interCor{i})$, where $\gIntraCor{i}$ and $\gInterCor{i}$ are used to respectively denote the correlation strength induced by agents inside group $i$ and those outside group $i$. Note that vectors are bold while scalars are not. 


\subsubsection{Privacy cost} \label{sec:privacy}

Privacy cost is critical to an agent's decision about whether to join the platform. For an agent who does not join the platform, her privacy cost $\g$ comes entirely from information leakage through her peers' data sharing on the platform due to data correlation. In contrast, for an agent who joins the platform but does not report her data, not only her peers' actions but also her own interactions with the platform result in her privacy cost, which is denoted by $\h$. Next, we introduce the parameterized form of privacy costs in detail.

\emph{Intra-group $\&$ Inter-group Privacy Loss.}
To differentiate the privacy cost due to correlation inside and outside the group, we further decompose privacy cost into a sum of intra-group cost and inter-group cost. Let the participation rate $\boldsymbol{\theta}_i$ denote a vector of participation rate within the group $\intraRatio{i}$ and that of the rest groups $\interRatio{i}$, i.e. $\boldsymbol{\theta}_i \triangleq  [\intraRatio{i},\interRatio{i}]$. For convenience, we later use $\bar{\theta}$ to denote the average participation rate of the overall population. For an agent in group $i$, her privacy cost is equal to a sum of intra-group cost and inter-group cost: $\gppl{c}{i} = \gintraloss{c}{i} + \ginterloss{c}{i}$ if the agent does not join the platform; otherwise her privacy cost of joining the platform is $\ppl{c}{i} = \intraloss{c}{i} + \interloss{c}{i}$.

Up to this point, we have introduced a parameterized form of privacy functions $\gppl{c}{i}$ and $\ppl{c}{i}$.
{To derive more clear engineering insights,} we make two assumptions regarding these privacy functions. These assumptions are intuitive and consistent with the applications we consider

\begin{assumption} \label{combine}
[Monotonicity $\&$ Boundedness] Both $\gppl{c}{i}$ and $\ppl{c}{i}$ are continuously  non-decreasing {in} cost $c$, participation rate $\intraRatio{i}$ and $\interRatio{i}$, and correlation strength $\intraCor{i}$ and $\interCor{i}$. Further, the difference $\ppl{c}{i}- \gppl{c}{i}$ is continuously increasing {in} cost $c$, {and  $\gppl{c}{i}$ is no greater than  $\ppl{c}{i}$. Both of them are bounded by $c$}:  $\gppl{c}{i} \le \ppl{c}{i} \leq c$.
\end{assumption}

To motivate the monotonicity assumption, first recall that cost is composed of reporting costs and privacy costs, as mentioned in Section \ref{sec:agent}. Thus, an agent with a high cost tends to value her privacy more, which is captured by the monotonicity with respect to costs. Second, intuitively, privacy costs increase as more agents join the platform. Indeed, the more agents join the platform and share their data, the more information that the analyst can infer about agents, including  those who do not join the platform. Third, the correlation strength characterizes how each agent's data is correlated with other agents' in the population. For an agent, a stronger correlation strength indicates that data sharing by other agents of the population could potentially cause more leakage, thus more privacy losses.

To understand the assumption $\gppl{c}{i}\leq\ppl{c}{i}\leq c$, we note that every agent suffers a privacy cost induced by her peers' activities on the platform due to data correlation even if she does not join the platform. In addition, for those who indeed join the platform, they tend to leak more information about themselves through their own activities on the platform. As a result, it is reasonable to assume that the privacy cost $\gppl{c}{i}$ of an agent, if she does not join the platform, is smaller than her privacy cost $\ppl{c}{i}$ if she joins but does not report her data. In other words,  sharing on the platform potentially leads to more privacy cost. The difference of these two parts models the privacy cost due to individual sharing. Naturally, for any agent, the privacy cost due to individual sharing tends to be higher if the agent has a larger overall cost. 
Since the overall cost consists of reporting cost and privacy cost, any privacy cost function is modeled as a fraction of the overall cost $c$, i.e. privacy cost is upper bounded by $c$.









\begin{assumption}
\label{Ass_linearincost}
The privacy cost  $\ppl{c}{i}$ is linear in cost $c$ with parameter $b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)$, i.e., 
\begin{equation}
     \ppl{c}{i} = c \cdot b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i).
 \end{equation}
\end{assumption}
	

We assume that the privacy cost function of participation $\ppl{c}{i}$ is linear in cost $c$.   This assumption is  a consequence of the work in~\citet{ghosh_selling_privacy}, which shows that cost functions of the form $c_i \varepsilon$ are appropriate for settings using differential privacy, where $\varepsilon$ quantifies the amount of privacy leaked. Note that the parameter $b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)$ inherits the monotonicity with respect to the participation rate and correlation strength from that of the privacy cost function $\ppl{c}{i}$. 

\subsubsection{Agent's Utility}
After introducing the key components of agent's utility, we summarize the utility function as follows:

\begin{enumerate}[label=(\roman*)]
    \item If the agent does not join the platform, she only experiences a privacy cost $\gppl{c}{i}$ induced by information leakage due to data correlation.
    \item If the agent joins the platform but is not selected to report her data, her utility is $\ppl{c}{i}+\benefit{\bar{\theta}}$, where $\benefit{\bar{\theta}}$ is the participation benefit.
    \item If the agent joins the platform and is selected to report her data, she incurs her overall cost $c$, which includes her privacy cost. Based on the agent's reported cost $\tilde{c}$, she receives a payment $\paymentP{\tilde{c}}{i}$ and thus her utility is $\paymentP{\tilde{c}}{i} -c + \benefit{\bar{\theta}}$.
\end{enumerate}



As the agent's privacy cost function is parameterized by the correlation strength parameter, so should the payment function $\paymentP{\tilde{c}}{i}$, selection probability $\selectionProbP{\tilde{c}}{i}$, utility $\utilityP{\tilde{c}}{c}{i}$. However, for simplicity, we later use $\payment{\tilde{c}}{i}$, $\selectionProb{\tilde{c}}{i}$, and $\utility{\tilde{c}}{c}{i}$, 
respectively to denote payment, selection probability and utility function. 
For agent $k$, her utility is as follows:
\begin{equation}\label{equ_uti}
    \utility{\tilde{c}}{c}{i} = \begin{cases}
        -\gppl{c}{i}, &\text{if } k \not\in \mathcal{N}, \\
        -\ppl{c}{i}+\benefit{\bar{\theta}}, &\text{w/ prob. } 1-\selectionProb{\tilde{c}}{i}, \text{ if } k \in \mathcal{N},\\ 
        \payment{\tilde{c}}{i} -c + \benefit{\bar{\theta}}, &\text{w/ prob. }  \selectionProb{\tilde{c}}{i}, \text{ if } k \in \mathcal{N}.
    \end{cases}
\end{equation}
 Let the expected utility for an agent (reporting $\tilde{c}$ while having a cost $c$) in group $i$ who joins the platform be denoted by $\expectedUtility{\tilde{c}}{c}{i}$. Consequently,
\begin{equation}\label{expected_utility}
\begin{aligned}
\expectedUtility{\tilde{c}}{c}{i} =& \selectionProb{\tilde{c}}{i} \left[ \payment{\tilde{c}}{i} -c + \benefit{\bar{\theta}} \right] + (1-\selectionProb{\tilde{c}}{i}) \left[ - \ppl{c}{i} + \benefit{\bar{\theta}} \right].\\
=&\selectionProb{\tilde{c}}{i}\left[\payment{\tilde{c}}{i} -c + \ppl{c}{i}\right]- \ppl{c}{i}+ \benefit{\bar{\theta}}.
\end{aligned}
\end{equation}



\section{Mechanism Design} 


\label{sec:mechanism}

The analyst aims to perform an estimation task by designing the menu for the mechanism, which is composed of payment function and allocation rule for agents. To study this problem, we first introduce two standard desirable properties of the mechanism: \emph{truthfulness} (Definition \ref{def_truthful}) and \emph{budget feasibility} (Definition \ref{def_budget}), and then define the overall objective (a trade-off between bias and variance of the estimator) (Definition \ref{def_obj}) subject to these two properties.  Following that setup, we introduce the equilibrium participation rate (Definition \ref{def_equilibrium}), which is  a situation where no agent wants to alter her participation decision given the current participation rate. We then derive  structural results on the payment function and allocation rule that induce participants' truthful reporting in the equilibrium in Section \ref{sec_payment} (Theorem \ref{pro_payment}). Finally, we present monotonicity properties of the mechanism in Section \ref{sec_properties}. 

\subsection{Problem Statement}

To define the analyst's mechanism design problem, we first describe two classical, desirable properties, truthfulness and an expected budget constraint. 
First, we require the mechanism to be truthful, which is common, e.g. \cite{dataacquisition, shuran_yiling}.

\begin{Def}[Truthfulness]\label{def_truthful}
A  mechanism is truthful if for every participant with cost $c$, she can maximize her expected utility if
she truthfully reports her cost, i.e.,
\begin{equation}\label{equ_truthfulness}
    \utility{c}{c}{i}\ge \utility{\tilde{c}}{c}{i}, \quad
    \forall \tilde{c} \neq c, \forall i.
\end{equation}
\end{Def}

Definition \ref{def_truthful} guarantees that rational agents on the platform will truthfully report their costs. Substituting the expected utility as in equation \eqref{expected_utility}, we get
\begin{equation}
\selectionProb{c}{i} \cdot \left[\payment{c}{i} -c + \ppl{c}{i}\right] \geq \selectionProb{\tilde{c}}{i} \cdot \left[\payment{\tilde{c}}{i} -c + \ppl{c}{i}\right], \quad
    \forall \tilde{c} \neq c, \forall i.
\end{equation}










 Second, we constrain the mechanism to use a limited budget $B$, which limits the payments of the analyst to the agents for their data. Before presenting the budget constraint in details, we introduce some notation. Every agent owns a data point $x$ and cost $c$.  These pairs $(x, c)$, owned by agents in group $i$ ($i\in [I]$), follow a joint distribution $\mathcal{D}_i$. Define  $\mathcal{D} \triangleq \{ \mathcal{D}_i \}_{i\in [I]}$. Let $f_i$ denote the marginal distribution of the cost. We assume that $f \triangleq \{ f_i \}_{i\in [I]}$ is known to the analyst while $\mathcal{D} \triangleq \{ \mathcal{D}_i \}_{i\in [I]}$ is unknown.\footnote{This prior $\{f_i\}$ could be constructed from previous interactions between agents and data buyers. Knowledge of the cost (or valuation) distribution is a standard assumption in Bayesian mechanism design (e.g.~\citet{myerson}), and is assumed in the works of \citet{aaron_grant} and \citet{dataacquisition}.}

\begin{Def}[Expected Budget Constraint]\label{def_budget}
A mechanism with payment function $P$ and selection probability $A$ satisfies the expected budget constraint $B$ if and only if
\begin{equation}
    \sum_{k: i = \group{k}} \E{c \sim f_{i}} [\payment{c}{i} \selectionProb{c}{i} \cdot \mathbbm{1} (\agent \in \groupParSet{i})] \le B.\\
\end{equation}
\end{Def}

We enforce the budget constraint on the expected payment in  Definition \ref{def_budget}, which is a common approach in the prior work, e.g. \cite{aaron_grant, dataacquisition, shuran_yiling}. Note that the expectation is taken with respect to the marginal distribution of agent's cost $f$, and the agents who join the platform as only they potentially receive a payment by the allocation rule. For convenience, we use $\group{k}$ to denote the group index of agent $k$.






We now formally define bias and variance of the  estimator of the analyst.  Recall the analyst seeks to optimize a tradeoff between bias and variance in our setting. Specifically, the analyst wishes to learn an underlying parameter $\mu$ of the whole population, and he obtains an estimator $\hat{m}$ based on participants' data.
The estimator $\hat{m}$ is viewed as a random variable, and the randomness of the estimator comes from the joint distribution $\mathcal{D}$ and the allocation rule $A$. We view the estimator as drawn from a distribution $\mathcal{T}(\jointD, A)$. 



\begin{Def}[Bias]\label{def_bias}
Given an allocation rule $A$ and an instance of the true distribution $\mathcal{D}$, the bias of an estimator $\hat{m}$ is defined as follows:
\begin{equation}
    \mathbb{B}(\estimator; \jointD, \allocation) = \left|\E{\hat{m} \sim \mathcal{T}(\jointD, A)} \left[ \hat{m} - \mu \right]\right|.
\end{equation}
\end{Def}



\begin{Def}[Variance]\label{def_variance}
Given an allocation rule $A$ and an instance of the true distribution $\mathcal{D}$, the variance of an estimator $\hat{m}$ is defined as follows:
\begin{equation}
    \mathbb{V}(\estimator; \jointD, \allocation) = \E{\hat{m} \sim \mathcal{T}(\jointD, A)} \left[ (\hat{m} - \mathbb{E} [\hat{m}])^2 \right].
\end{equation}
\end{Def}



Since the analyst does not know the joint distribution $\mathcal{D}$, he cannot directly optimize over bias and variance of the estimator. Instead, we consider the goal of minimizing the worst-case linear combination of bias (Definition \ref{def_bias}) and variance (Definition \ref{def_variance}) over all instantiations of $\mathcal{D}$ that are consistent with the marginal cost distribution $f$.

\begin{Def}[Worst-Case Bias-Variance Trade-off] \label{def_obj}
 \textcolor{black}{Given an allocation rule $A$, an instance of the true distribution $\mathcal{D}$, and a combination parameter $\lambda$, the worst-case bias-variance trade-off is the supremum of the linear combination of bias and variance:}  
 \begin{equation}
     \sup_{f \text{ consistent with } \mathcal{D}}\quad   \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation).
 \end{equation}
\end{Def}

Using the above, we formally define the mechanism design problem as follows.

\begin{Def}[Mechanism Design Task]\label{def_mech_design}
Given an estimator $\hat{m}$, cost distribution $f$, correlation strength parameters, and fixed parameter $\lambda$, the analyst aims to minimize a worst-case bias-variance trade-off by designing payment rule $P$ and allocation rule $A$ subject to truthfulness and budgetary constraints:
\begin{equation}\label{equ_mech_design}
\begin{aligned}
\inf_{A, P} \sup_{f \text{ consistent with } \mathcal{D}}\quad &   \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation)\\
\textrm{s.t.} \quad & \sum_{k: i = \group{k}} \E{c \sim f_{i}} [\payment{c}{i} \selectionProb{c}{i} \cdot \mathbbm{1} (\agent \in \groupParSet{i})] \le B\\
& \selectionProb{c}{i}\left[\payment{c}{i} -c + \ppl{c}{i}\right] \geq \selectionProb{\tilde{c}}{i}\left[\payment{\tilde{c}}{i} -c + \ppl{c}{i}\right], \quad
    \forall \tilde{c} \neq c, \forall i\\
\end{aligned}
\end{equation}
\end{Def}

Note that each agent suffers a privacy cost due to data correlation even if she does not join the platform. This negative utility offers the analyst freedom to compensate the agent a partial cost rather than the whole cost while motivating the agent to join the platform (individual rationality). As a result, we do not have to constrain the mechanism to satisfy a positive value of participation, which is a common requirement in the prior work in this area.  This is a novel, significant consequence of considering privacy leakage.









\subsection{Equilibrium Characterization}\label{sec_equilibrium}

To characterize the equilibrium that results under a given mechanism design, we consider the agents' decisions given a fixed participation rate. Recall that the participation rate is an aggregation of agents' decisions on whether to participate, and that an agent's utility depends on the participation rate. We emphasize that an agent's decision does not depend on other agents' individual decisions, rather only on the participation rate as an aggregate. This is natural for large platforms where a single agent's decision has little impact on others'. 

Before defining the equilibrium concept, we first introduce some notation. Recall that there are $I$ groups of agents parameterized by data correlation strength. We use $\groupProb{i}$ to represent the likelihood of a random agent coming from group $i$ in the population. For agents in group $i$, the cost follows a continuous distribution $f_i$  with  a support set $\mathcal{C} \triangleq [c_{\min},c_{\max}]$. We use $\bar{\theta}_i$ to denote the participation rate for group $i$. Let $\boldsymbol{\theta} \triangleq [\bar{\theta}_i]_{1\le i \le I}$, an array of average participation rate for all the groups, denote the participation rate profile. Naturally we have the average participation rate in the population satisfying $\bar{\theta} = \sum_{1\le i\le I} \groupProb{i}\cdot \bar{\theta}_i$.

For a given participation rate profile, an agent makes decisions by weighing her utility under different choices. For an agent with cost $c$ in group $i$, we use a binary variable $d_i(c | \boldsymbol{\theta})$ to denote her decision. If the agent joins the platform, $d_i(c | \boldsymbol{\theta}) = 1$; otherwise $d_i(c | \boldsymbol{\theta}) = 0$.  We consider a non-atomic model where a single agent's decision has no effect on the aggregate participation rate when the agent set is large enough \cite{marketdemand}. This is a realistic assumption for a large platform. Every agent is assumed to be rational, i.e., she decides to join the platform only if her utility of non-participation is not lower than that of participation. This translates to the following mathematical expression:
\begin{equation}\label{equ_brparticipaiton}
d_i(c|\boldsymbol{\theta}) = \begin{cases}
1, & \text{if}\ \ \max_{\tilde{c}}\expectedUtility{\tilde{c}}{c}{i}\ge -\gppl{c}{i},\\
0, &  \text{otherwise}.
\end{cases}
\end{equation}
Since both payment and selection probability depend on the reported cost, an agent tends to report the cost that maximizes her expected utility of participation $\expectedUtility{\tilde{c}}{c}{i}$.



For an agent in group $i, 1\le i\le I$, her decision on whether to participate is closely related to the participation rate  $\bar{\theta}_i$  of group $i$ and that of the rest groups $\bar{\theta}_{-i}$. Meanwhile, we notice that there are many possible participation rate profiles $\boldsymbol{\theta}$ that corresponds to one specific average participation rate $\bar{\theta} (= \sum_{1\le i\le I} \groupProb{i}\cdot \bar{\theta}_i)$. Thus, the average participation rate $\bar{\theta}$ alone is not enough to capture the agents' decisions. This motivates us to leverage the participation rate profile $\boldsymbol{\theta}$, instead of average participation rate $\bar{\theta}$ of all the groups, as the equilibrium concept.




We now define the equilibrium concept formally. This notion of equilibrium guarantees that agents' decisions are consistent with the participation rate profile. Note that we consider a strictly positive participation rate at equilibrium, i.e., $\bar{\theta}^*_i > 0, \forall i$, with an adequate budget; otherwise a zero participation rate for certain groups essentially leads to a biased estimator towards the rest of the groups with positive participation rates.

\begin{Def}[Equilibrium]\label{def_equilibrium}
A participation rate profile  $\boldsymbol{\theta}^*=[\bar{\theta}^*_i]_{1\le i\le I}$ is an equilibrium, if for each group $i, 1\le i\le I$, the fraction of participating agents is exactly $\bar{\theta}^*_i$, i.e., 
\begin{equation}\label{equ_equilibrium}
   \int_{c_{\min}}^{c_{\max}}\mathbbm{1}\left[d_i(c|\boldsymbol{\theta}^*)=1\right]\cdot f_i(c)dc = \bar{\theta}^*_i, \quad \forall i.
\end{equation}
\end{Def}




\subsection{Payment Function}\label{sec_payment}


We now analyze the structure of the payment function in the mechanism associated with the equilibrium $\boldsymbol{\theta}^*$. The analyst's mechanism design problem in Definition \ref{def_mech_design} involves a  truthfulness constraint and a budgetary constraint. We first present the payment function that satisfies the truthfulness constraint for a given non-increasing allocation rule. Later, in Section \ref{sec_opt_tradeoff}, we further optimize over allocation rule to solve for the general optimization problem. 


We present the payment function for group $i, 1\le i\le I$, and then characterize the requirements for a truthful mechanism. We begin with some definitions. For a fixed desired participation rate profile $\boldsymbol{\theta}$, we introduce  $\hat{c}{i}$  of group $i$, which satisfies the equality in \eqref{equ_ratio_threshold}. Later in this section, we explain in Corollary \ref{cor_threshold} that $\hat{c}{i}$ can be viewed as a cost threshold for agents in group $i$, and agents whose cost is no greater than this value would like to participate. 

\begin{equation}\label{equ_ratio_threshold}
	 \bar{\theta}_{i} = \int_{c_{\min}}^{\hat{c}{i}} f_i(c) dc, 1\le i\le I.
\end{equation}
Next, we give  the payment function of group $i$ as follows

\begin{equation}\label{equ_payment}
\begin{aligned}
\payment{\tilde{c}}{i} =\tilde{c}-\ppl{\tilde{c}}{i} 
+\frac{1}{\selectionProb{\tilde{c}}{i}}\left(\left(1-b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)\right)\int_{\tilde{c}}^{c_{\max}}\selectionProb{z}{i}dz + \constantpart{i}\right),
\end{aligned}
\end{equation}
where
\begin{equation}\label{equ_constantpart}
\constantpart{i} = \ppl{\hat{c}{i}}{i}-\gppl{\hat{c}{i}}{i}-\left(1-b(\boldsymbol{\theta}_i;\boldsymbol{\alpha}_i)\right)\int_{\hat{c}{i}}^{c_{\max}}\selectionProb{z}{i}dz - \benefit{\bar{\theta}}.
\end{equation}




The characterization of the payment function relies on allocation rule $A$ and the associated participation rate profile $\boldsymbol{\theta}$. According to Myerson's Lemma \cite{myerson}, the allocation rule should be non-increasing
{in} the reported cost $\tilde{c}$ in order to induce agents' truthfulness. Further, we present the requirements for a truthful mechanism in Theorem  \ref{pro_payment}. Such a mechanism can uniquely induce agents' truthful reporting of costs.  If the selection probability is strictly decreasing, the mechanism can induce agents' strict truthfulness.\footnote{By strict truthfulness, we are saying that the agent can maximize her utility of participation if and only if she truthfully reports her cost, i.e., $\utility{c}{c}{i}> \utility{\tilde{c}}{c}{i},$ for all $\tilde{c} \neq c$. That is, by removing the equality of (\ref{equ_truthfulness}) in Definition \ref{def_truthful}, we get the definition of strict truthfulness.} We highlight this result in Theorem \ref{pro_payment} and put its proof in Appendix \ref{appendixsec_payment}.
	\begin{The}\label{pro_payment}
	The mechanism is truthful (strictly truthful, respectively) and induces participation profile $\boldsymbol{\theta}^*$ at equilibrium if and only if for every group $i \in [I]$, both of the following statements hold:
	\begin{enumerate}	[label=(\roman*)]
	    \item allocation rule $\selectionProb{\tilde{c}}{i}$ is a non-increasing (decreasing, respectively) function of the reported cost $\tilde{c}$;
	    \item payment function is given as in Equation \eqref{equ_payment} (as a function of $A$), where $\boldsymbol{\theta} \triangleq \boldsymbol{\theta}^*$ is the desired participation rate profile.
	\end{enumerate}    
\end{The}


For a mechanism as described in Theorem  \ref{pro_payment}, the agent would like to truthfully report her overall cost, as truthful reporting can maximize her expected utility.  The monotonicity of the allocation rule indicates that an agent with a high reported cost in the same group is less likely to be selected and get a payment. 
Furthermore, we would like to emphasize that the strictly decreasing property of the allocation rule induces strict truthfulness of the mechanism. Suppose that the allocation rule is fixed in a certain range of reported cost (i.e., not decreasing).  By reporting any cost in this range, the agents in this range can get the highest utility, which does not satisfy strict truthfulness definition. Thus, a strictly decreasing allocation rule is necessary to induce strict truthfulness.


\begin{Cor}\label{cor_threshold}
Under the mechanism in Theorem \ref{pro_payment}, the participation decisions of agents in group $i$ satisfy $d_i(c | \boldsymbol{\theta}^*) = 1$ if $c\le \hat{c}{i}$ and $d_i(c | \boldsymbol{\theta}^*) = 0$ otherwise.
\end{Cor}
This result highlights that, under the mechanism in Theorem \ref{pro_payment}, the decisions of the agents in each group demonstrate a threshold structure with respect to overall cost $c$. Agents in group $i$ will participate and truthfully report her overall cost, if her overall cost is no greater than the threshold $\hat{c}{i}$; otherwise she will not participate.  



\subsection{Properties of the mechanism}\label{sec_properties}

We now study the connections among three key components of the mechanism design: data correlation, group participation rate, and payment (see Properties \ref{pr_pay_ratio}-\ref{pr_ratio_correlation} later in this section).  Existing discussions (e.g., \citet{acemoglu_privacy}) of the connections among data correlation, number of users, and payment, which demonstrated some interesting properties of data trading, motivate our study. For example, \citet{acemoglu_privacy} shows that the total payment to users is non-monotone in the number of users in some scenarios. It is interesting to explore such connections under the settings of this work. Moreover, studying the connections helps uncover the impacts these issues have on the mechanism design under our settings when we incorporate information leakage.

Many of the properties below highlight the complexity of data marketplaces with information leakage.  For example, our first property highlights that, even though a larger average participation rate means more participants,  the total payment for the entire group does not necessarily increase. This is because the individual payment for these agents will decrease as well.

\begin{Prop}\label{pr_pay_ratio}
Given a fixed selection probability $A$, the total expected payment for agents in group $i$ is non-monotonic
{in} the average participation rate of group $i$.
\end{Prop}


However, despite the non-monotonicity of the expected payment 
{in} the average participation rate, there are some intuitive monotonicity properties that do hold for the payment after imposing one additional natural assumption. 


\begin{Prop}\label{pr_payment_correlation}
Suppose the difference $\ppl{\hat{c}{i}}{i}-\gppl{\hat{c}{i}}{i}$ is non-increasing
{in} correlation strength. The payment to the agents in group $i$ who join the platform is decreasing 
{in} both intra-group correlation strength $\intraCor{i}$ and inter-group correlation strength  $\interCor{i}$. 
\end{Prop}

In the property above, we further require the difference function, i.e., $\ppl{\hat{c}{i}}{i}-\gppl{\hat{c}{i}}{i}$, to be non-increasing
{in} both intra-group correlation strength and inter-group correlation strength. Intuitively, this difference can be viewed as the extra privacy cost for the agent with cost equal to $\hat{c}{i}$ due to her own activities on the platform, and thus it might be even independent of data correlation strength. As a consequence, the payment for the agents who join the platform in group $i$ is decreasing in both intra-group and inter-group correlation strength, i.e., $\intraCor{i}$ and  $\interCor{i}$.

Some intuition for the above property comes from the observation that, when there is strong correlation among the agents' data, an individual will suffer a large privacy leakage even if they do not join the platform. As a result, they are incentivized to join the platform even when the individual payment is relatively low. Naturally, given a fixed participation rate profile and allocation rule, the total expected payment for the entire group decreases as a result.


However, in contrast to the above intuition, we do not have monotonicity of the participation rate in this setting, as we show in the property below.  Note that for most of this paper we treat the participation rate as something fixed (and optimized) by the analyst.  However, understanding its behavior is important for performing such an optimization. 


\begin{Prop}\label{pr_ratio_correlation}
In group $i$, the group participation rate is non-monotonic in both the intra-group correlation strength $\intraCor{i}$ and inter-group correlation strength  $\interCor{i}$.
\end{Prop}

To develop some intuition for the above, we note that the analyst's mechanism design is subject to a budget constraint. Although stronger data correlation indicates lower payment, the total expected payment is also affected by the selection probability. If the selection probability increases, the analyst needs to induce a lower group participation rate so that the total expected payment does not exceed the budget. Otherwise, the analyst could induce a higher participation rate. 


Our last property investigates what happens as the budget increases.  In this case the analyst can exploit the additional budget to improve either bias or variance. On the one hand, increasing the selection probability helps reduce the uncertainty of collected data, thus decreases the variance. On the other hand, inducing an equilibrium with a higher participation rate helps cover a wider range of participants' data, thus decreases the bias. 

\begin{Prop}\label{pr_pay_biasvariance}
As budget increases, the estimator achieves a better bias-variance trade-off, i.e., the optimal objective of the overall optimization problem as in Definition \ref{def_mech_design} reduces. 
\end{Prop}



\section{Optimization of the Worst-Case Bias-Variance Trade-off}\label{sec_opt_tradeoff}



We now discuss the design of a mechanism that optimizes the worst-case bias-variance trade-off.  First, we introduce the analyst's choice of estimator in Section \ref{sec_estimator}. Second, we  characterize the worst-case bias-variance trade-off of the estimator, given a selection rule and a participation rate profile at equilibrium, in Section \ref{sec_tradeoff}. Finally, we provide our full mechanism in Section \ref{sec_solution}. 

From a mathematical perspective, our bias-variance optimization problem optimizes over two types of variables: (i) the allocation rule, which is a collection of  probabilities that participants are selected to report their data and get the payments, and (ii) the participation rate profile in equilibrium, which controls the fraction of agents in each group that join the platform in the first place. However, in practice, a platform is unlikely to be willing to sacrifice a high participation rate to improve the performance of any single statistical task. Thus, optimizing over the participation rate is not attractice.  Thus, here, we treat the participation rate as given so that our work can  apply to any platform at any growth stage, e.g., either a start-up platform with a low participation rate or a popular platform with a high participation rate.


In what follows, we first show that the optimal allocation rule under a fixed equilibrium participation rate profile is monotone in the agents' virtual costs, as defined in Definition \ref{def_vcost} in Section \ref{sec_solution}, and provide a closed-form solution for this allocation rule. Given that optimizing over the participation rate is unrealistic, we instead present structural results and conditions for a full participation rate profile. This provides a connection to previous work on data acquisition since, when there is a full participation rate profile, the analyst sees a representative sample of the population and obtains an unbiased estimator. 

\subsection{Estimator}\label{sec_estimator}





The objective of the analyst's mechanism design problem in Definition \ref{def_mech_design} is to minimize the worst-case bias-variance trade-off of a given estimator. In this section, we describe the estimator of our choice. We then characterize its worst-case bias-trade-off variance in Section \ref{sec_tradeoff}. 


The analyst is interested in estimating a population statistic using the mechanism. In this paper, we focus on estimating a mean over the population in question. For example, the analyst wishes to understand the average income, average BMI, or average ratings for a new movie. 


We use the Horvitz-Thompson estimator \cite{HTestimator}, which is the unique unbiased linear estimator for the settings where an analyst must sample at different rates from different sub-populations; in our case, agents in different groups or with different costs may be selected with different probabilities $A(\cdot)$, and in turn define several distinct sub-populations. In such a setting, the standard sample mean estimator is biased towards the sub-populations from which the analyst samples most (relatively to the sub-population size). The Horvitz-Thompson estimator eliminates this bias by re-weighting each data point by the inverse of the selection probability associated with its sub-population. In our setting, the Horvitz-Thompson estimator reweights the data of each agent $k$ by $1/A^k$, where $A^k$ is the selection probability associated with agent $k$.

We define the Horvitz-Thompson estimator formally below in Definition \ref{Def_estimator}. Recall that $\mathcal{N}$ denotes the set of participants (i.e., agents who join the platform) and is of size $N$. Let $\mathcal{O}\subset \mathcal{N}$ denote the set of participants who are selected to report their data. Let $x_k$ be the data of agent $k$.
Suppose that the agents' data is independently and identically distributed. The Horvitz-Thompson estimator is then an unbiased estimator for the mean of data of the participants in set $\mathcal{N}$, i.e., the expectation of the estimator is equal to the expected value of the participants' data.

\begin{Def}[Horvitz-Thompson estimator] \label{Def_estimator}
The Horvitz-Thompson estimator is given by
\begin{equation}
\hat{m} = \frac{1}{N}\sum_{k\in \mathcal{N}} \frac{x_k \cdot \mathbbm{1}\{k\in \mathcal{O}\}}{A^k},
\end{equation}
where $A^k$ is the selection probability for agent $k$.
\end{Def}



Although the estimator is unbiased with respect to the set of participants $\mathcal{N}$, it may be biased with respect to the overall agent set $\mathcal{S}$, when the average participation rate is less than one. When some agents do not participate, their data are not fed to the estimator and the estimator fails to capture the information of the non-participants. On the other hand, if the average participation rate is equal to one, i.e., all the agents are willing to participate, the estimator is naturally unbiased.  In conclusion, the participation rate at equilibrium is an important factor in the issue of estimation bias. Since there is an intrinsic trade-off between bias and variance, the  analyst might prefer low variance instead of low or zero bias in some cases, e.g., when the linear weight associated with the variance in equation \eqref{equ_mech_design} is high and the budget is large enough to use a large selection probability. Later, in Section \ref{sec_solution}, we present conditions under which the analyst prefers to enforce a full participation rate to achieve an unbiased estimator. 


\subsection{Characterizing the worst-case bias-variance trade-off}\label{sec_tradeoff}
We characterize the worst-case bias-variance trade-off of the estimator in this section. We start by introducing some key notation. For simplicity,  we assume that the agent's data is binary from the set of $\{0,1\}$. In Remark \ref{rem_tradeoff}, we highlight that our analysis can be generalized to continuous data in $[0,1]$. The probability of an agent being in group $i$ is denoted by $\groupProb{i}$. Let $\mathbf{q}\triangleq [\groupProb{i}]_{1\le i\le I}$. Let $p_{i}(c) \triangleq Pr[x = 1|c, i]$ denote the probability of an agent $k$ with cost $c$ in group $i$ having data point $x_k = 1$. Recall that according to Corollary \ref{cor_threshold}, an agent in group $i$ will join in the platform if her cost $c$ is no greater than the participation threshold $\hat{c}{i}$. Let $A \triangleq \{\selectionProb{c}{i}\}_{1\le i\le I}$, consisting of the selection probabilities in all groups. Furthermore, we assume a positive correlation between data and cost, which is mathematically described as follows.
\begin{assumption}\label{a_positivecorrealtion}
For each group $i$, $p_{i}(c)$ is a non-decreasing function of cost $c$. 
\end{assumption}
The assumption is often reasonable in practice. If the agent's data is of a higher value, then her cost is more likely to be higher as well, and vice versa. For example, agents with a higher income or higher BMI might care more about their privacy, hence their reporting costs tend to be higher for them as well.


\begin{Lem}\label{lem_tradeoff}
Under Assumption \ref{a_positivecorrealtion}, fix allocation rule $A$ and participation rate profile $\boldsymbol{\theta}^*$. Conditional on $\mathcal{N}$, the \textcolor{black}{supremum}  of linear combination of bias and variance of the estimator $\hat{m}$ in Definition \ref{Def_estimator} is 
\begin{equation}\label{equ_tradeoff}
\begin{aligned}
T(A,\boldsymbol{\theta}^*) = &\sup_{f \text{ consistent with } \mathcal{D}}  \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation)\\& =\sup_{p_{i}(c)\in [0,1], c \le \hat{c}{i} } \frac{\lambda}{s\left(\bar{\theta}^*\right)^2}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\frac{p_i(c)}{\selectionProb{c}{i}}f_i(c)dc-\frac{1}{\bar{\theta}^*}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right)^2\right) \\ &+(1-\lambda)(1-\bar{\theta}^*) \cdot \left(1-\frac{1}{\bar{\theta}^*}\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right).
\end{aligned}
\end{equation}
\end{Lem}



\begin{remark}\label{rem_tradeoff}
While we focus on the binary data case, we note that if the agents' data points $x_k$ are taken from the interval $[0,1]$, our proof can immediately be adapted to show that
\begin{equation}
\begin{aligned}
T(A,\boldsymbol{\theta}^*) = &\sup_{f \text{ consistent with } \mathcal{D}}  \lambda \cdot \mathbb{V}(\estimator; \jointD, \allocation)+ (1-\lambda)\mathbb{B}(\estimator; \jointD, \allocation)\\ \le& \sup_{p_{i}(c)\in [0,1], c \le \hat{c}{i} } \frac{\lambda}{s\left(\bar{\theta}^*\right)^2}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\frac{p_i(c)}{\selectionProb{c}{i}}f_i(c)dc-\frac{1}{\bar{\theta}^*}\left(\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right)^2\right) \\ &+(1-\lambda)(1-\bar{\theta}^*) \cdot \left(1-\frac{1}{\bar{\theta}^*}\sum_{i} \groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}p_{i}(c)f_i(c)dc\right).
\end{aligned}
\end{equation}

\noindent That is, the expression that we optimize over is an over-estimate of the worst-case bias-variance trade-off; in turn, our approach still provides an upper bound and does not underestimate the bias-variance trade-off when the data is non-binary. 
\end{remark}

The proof of Lemma \ref{lem_tradeoff} and Remark \ref{rem_tradeoff} are in Appendix \ref{apendixsec_tradeoff}. The basic idea is to derive the variance and the worst-case bias separately, and they both are fully characterized by the distribution of participants' data (i.e., $p_i(c)$ for $c\le \hat{c}{i}$). Thus, optimizing a linear combination of bias and variance gives the worst-case linear combination of bias and variance.


Lemma \ref{lem_tradeoff} presents  an  analytical formulation of the objective function with an auxiliary variable $p_i(c)$. This  facilitates our later analysis of the optimization problem, which is the minimization of \eqref{equ_tradeoff} subject to truthfulness constraint and budget constraint.

To conclude the subsection, we provide some interpretation about how the allocation rule $A$ and participation rate profile $\boldsymbol{\theta}^*$ affect the trade-off between bias and variance.   If the value of allocation  rule $A_i(c)$ is higher, the variance $\mathbb{V}(\estimator; \jointD, \allocation)$ is lower. However, due to the budget constraint, a higher value of allocation  rule indicates a lower participation rate, which means a possibly higher bias. Thus, due to the budget constraint,  the analyst needs to carefully trade off bias and variance. 

The analyst's objective is to minimize the above  worst-case bias-variance trade-off by choosing the allocation rule $A$ and the participation rate profile $\boldsymbol{\theta}^*$ in the equilibrium.  Next, we discuss the optimal allocation rule and participation rate profile in details.

\subsection{Optimal Allocation Rule and Conditions of Full Participation Rate}\label{sec_solution}

We now derive solutions to the worst-case bias-variance trade-off optimization problem under the budget and truthfulness constraints. First, we present the optimal allocation rule given the participation rate profile at equilibrium. Second, we identify sufficient conditions under which the optimal participation rate is one and the analyst obtains an unbiased estimator. 

\subsubsection{Optimal Allocation Rule}
We first study the design of the allocation rule, given a desired participation rate profile $\boldsymbol{\theta}^*$ at equilibrium. Recall that we focus on $\boldsymbol{\theta}^*$ in which $\bar{\theta}^*_i\ge \bar{\theta}_{\min}, \forall i$ for some positive value $\bar{\theta}_{\min}>0$ to avoid the trivial case of complete non-participation of a group. 

In this section, we first introduce the notion of virtual cost in Definition \ref{def_vcost}, which is analogous to the classical notion of virtual value in~\cite{myerson}. The virtual costs help characterize the payment function that, given a fixed allocation rule, induces agents to report their privacy costs truthfully. The characterization of payment function is in Theorem \ref{pro_payment}.  We note that the virtual cost of an agent in group $i$ depends on her privacy cost ($ \pplequ{c}{i}$) and the cost distribution ($F_i$ and $f_i$) in group $i$. 

\begin{Def}[Virtual Cost]\label{def_vcost}
 In group $i$, given participation rate profile $\boldsymbol{\theta}^*$, the virtual cost of an  agent with cost $c$ is 
 \begin{equation}\label{equ_vcost}
 \phi_i(c;\boldsymbol{\theta}^*) = c-\pplequ{c}{i} + (1-b(\boldsymbol{\theta}^*_i;\boldsymbol{\alpha}_i))\frac{F_i(c)}{f_i(c)}.
 \end{equation}
 Here, $F_i$ and $f_i$ are cdf and pdf of cost in group $i$, respectively. 
 \end{Def}

Recall that the vector $\boldsymbol{\theta}^*_i$  consists of $\bar{\theta}^*_i$ and  $\bar{\theta}^*_{-i}$. The virtual cost $\phi_i(c;\boldsymbol{\theta}^*)$  in group $i$ is decreasing in the within-group participation rate $\bar{\theta}^*_i$ and the outside-group rate $\bar{\theta}^*_{-i}$, as $h(\cdot)$ and $b(\cdot)$ are increasing in both  $\bar{\theta}^*_i$ and  $\bar{\theta}^*_{-i}$. Recall that a higher participation rate means more privacy cost. Furthermore, we assume that the virtual cost within a group is non-decreasing in cost $c$ as in \cite{dataacquisition,myerson} (Assumption \ref{a_regularity}). Note that a uniform distribution is one example satisfying the assumption.    

\begin{assumption}\label{a_regularity}[Regularity]
The virtual cost $\phi_i(c;\boldsymbol{\theta}^*)$  in group $i$ is non-decreasing. Furthermore, $f_i(c)$ is twice differentiable, in which case $F_i(c)f'_i(c)\le2(f_i(c))^2$.
\end{assumption}


 



Now we are ready to present the optimal allocation rule of each group.
\begin{The}\label{the_opt_pro}
	Under Assumptions \ref{combine}-\ref{a_regularity}, given
	a desired participation rate  profile $\boldsymbol{\theta}^*$, the optimal allocation rule of group $i$ is


	\begin{align}\label{equ_general_opt_pro}
	    A_i(c) = \begin{cases}\chi, \ \ &\text{if} \ \  \phi_{i}(c;\boldsymbol{\theta}^*) \le \hat{\phi}, \\
	\frac{\eta}{\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}}, \ \ &\text{if} \  \ \hat{\phi}<\phi_{i}(c;\boldsymbol{\theta}^*)\le \phi_{i}(\hat{c}{i};\boldsymbol{\theta}^*).
	\end{cases}
	\end{align}
The characterizations of the constants $\eta$, $\chi$, and $\hat{\phi}$ depends on the system parameters including the budget $B$, number of agents $s$, distribution of virtual cost. See \eqref{equ_continuousA} in Appendix \ref{appendixsec_proof_the_opt}.
\end{The}




 



















\begin{wrapfigure}{r}{0.5\textwidth}
    \centering
    \includegraphics[width=.38\textwidth]{allocationrule.jpg}
    \caption{Illustration of two possible structures.}
    \label{fig_allocationrule}
\end{wrapfigure}
Theorem \ref{the_opt_pro} shows the optimal allocation rule of a group can have two possible structures: \emph{Fixed then Decreasing} (FtD) or  \emph{Strictly Decreasing} (SD), depending on system parameters such as budget $B$. Figure \ref{fig_allocationrule} provides an illustration. The FtD structure (the blue and red curves in Figure \ref{fig_allocationrule}) has an allocation rule  for the group that is firstly fixed in low-cost region (i.e., the region in which  $\phi_{i}(c;\boldsymbol{\theta}^*) \le \hat{\phi}$ holds) and then strictly decreasing in the high-cost region (inversely proportional to the square root of the virtual cost). Since the allocation rule is not strictly decreasing, the mechanism can only induce agents' weak (non-strict) truthfulness, according to Theorem \ref{pro_payment}. The other structure, SD (the orange curve in Figure \ref{fig_allocationrule}),  has an  allocation rule that is strictly decreasing (inversely proportional to the square root of the virtual cost) in the whole region. The strictly monotonic structure induces strict truthfulness.
{Note that the form of the optimal allocation rule parallels that of previous work~\cite{dataacquisition}, showing that a similar form is still optimal in a more general setting. As we have discussed, the generalization beyond~\cite{dataacquisition} to include the analyst's bias-variance trade-off, the agents' privacy costs, and data correlation add technical complexity and practicality. A priori, it is not clear that the optimal form would remain similar in the more general setting.}






Note that the optimal allocation rule presented in Theorem \ref{the_opt_pro} is defined for the  participating agents, whose cost are lower than threshold $\hat{c}{i}$ for group $i$. As in the case of non-participants, we only need to ensure monotonicity to induce truthfulness. A simple example is $A_i(c)=\epsilon$ for $c\ge \hat{c}{i}$, where $\epsilon$ is a small enough non-negative value. Note that this example does not make the total expected payment exceed the budget, as the non-participants do not get the payments.   In summary, the allocation rule of the cost lower than the threshold presented in Theorem \ref{the_opt_pro} and the allocation rule of the cost higher than the threshold make up a complete menu shown to the agents, which induces agents' truthfulness and optimizes the bias-variance trade-off.


We find that, when the budget $B$ is relatively small, the optimal allocation rule has a Strictly Decreasing structure. To state the result, first define 

\begin{equation}
 l(\boldsymbol{\theta}^*)\triangleq \sum_{i} q_i \bar{\theta}^*_i(\pplequ{\hat{c}{i}}{i}-\gpplequ{\hat{c}{i}}{i}-w(\bar{\theta}^*)).
\end{equation}
    \begin{Cor}\label{cor_opt_pro}
    Under Assumptions \ref{combine}-\ref{a_regularity}, the optimal allocation rule is 
    \begin{equation}
    A_i(c) = \frac{1}{\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}} \cdot\frac{B/s-l(\boldsymbol{\theta}^*)}{\sum_{i}\groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}f_i(c)dc},
    \end{equation}
    when the participation rate profile $\boldsymbol{\theta}^*$ satisfies the following inequality:
    \begin{equation}\label{equ_a}
        (B/s-l(\boldsymbol{\theta}^*))(2\lambda+\bar{\theta}^*(1-\bar{\theta}^*)(1-\lambda)s)<\lambda\sqrt{\phi_{\min}(\boldsymbol{\theta}^*)} \cdot\sum_{i}\groupProb{i} \int_{c_{\min}}^{\hat{c}{i}}\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}f_i(c)dc.
    \end{equation}
    Furthermore, the mechanism is strictly truthful.
    \end{Cor}
    

Corollary \ref{cor_opt_pro} is a special case of Theorem \ref{the_opt_pro}.  The inequality in (\ref{equ_a}) indicates that the budget is relatively low. Suppose the budget is large enough.  The analyst can keep the allocation rule in the low-cost region fixed, instead of strictly decreasing. In this case, the agents' reporting is weak truthful. However, if the budget is low as in (\ref{equ_a}), the optimal allocation rule is strictly decreasing, which induces agents' strict truthfulness. Strict truthfulness is a more desirable property than weak truthfulness.






\subsubsection{Sufficient Conditions for Unbiased Estimation}  

Next, we present simple, easy to verify, sufficient conditions for unbiased estimation. We focus on the low-budget regime, which induces agents' strict truthfulness, according to Corollary \ref{cor_opt_pro}. By substituting the allocation rule in Corollary \ref{cor_opt_pro} to the objective function (\ref{equ_tradeoff}), we arrive at an optimization problem  over $\boldsymbol{\theta}^*$ as follows:
\begin{equation}\label{equ_obj_ratio}
\max_{\boldsymbol{\theta}^*}  \ \  T^*(\boldsymbol{\theta}^*) = \frac{\lambda}{s}\left(U(\boldsymbol{\theta}^*)-\frac{1}{\bar{\theta}^*}\right),
    \end{equation}
where 

\begin{equation}\label{equ_L}
        U(\boldsymbol{\theta}^*) \triangleq  \frac{1}{\left(\bar{\theta}^*\right)^2}\cdot \frac{\left(\sum_{i}\groupProb{i}\int_{c_{\min}}^{\hat{c}{i}}\sqrt{\phi_{i}(c;\boldsymbol{\theta}^*)}f_i(c)dc\right)^2}{B/s-l(\boldsymbol{\theta}^*)}.
    \end{equation}
The objective function in (\ref{equ_obj_ratio}) is complicated due to the complexity of $l(\boldsymbol{\theta}^*)$ in (\ref{equ_L}).  Furthermore, the complicated characterization of its derivative with respect to group $i$'s participation rate $\bar{\theta}^*_i$ adds to the complexity. Thus, we focus on identifying sufficient conditions under which the optimal participation rate is one, meaning that the analyst would like to have unbiased estimator. 

To begin, we introduce some notation and assumptions. We denote the full participation rate profile by $\boldsymbol{\theta}_f\triangleq [1]^I\in \mathbb{R}^I $, each component of which is one. We define $\Delta_i \triangleq \ppl{\hat{c}{i}}{i}- \gppl{\hat{c}{i}}{i}$. It captures the additional privacy cost of an participant (compared with non-participation) whose cost is the cost threshold in group $i$. 

We now present sufficient conditions for achieving full participation and an unbiased estimator.


\begin{Pro}\label{Pro_fullpart_benefit}
Suppose that, for all $\boldsymbol{\theta}^*$ in which $\bar{\theta}^*_i\ge \bar{\theta}_{\min}>0, \forall i$,  (i) the inequality in (\ref{equ_a}) holds, and (ii) $w'(\bar{\theta}^*)\ge  D_i(\boldsymbol{\theta}^*,B,\lambda,s,\mathbf{q})$ holds for the function $D_i(\boldsymbol{\theta}^*,B,\lambda,s,\mathbf{q})$ defined in \eqref{equ_D} of Appendix \ref{appendixsec_fullpart_benefit},  where $w'$ is the derivative of function $w(\cdot)$.  Then, the optimal participation rate profile is $\boldsymbol{\theta}_f$ and the analyst obtains an unbiased estimator.
   
   
   
   
   
   
       
   
   
   
   
   
   
        
    \end{Pro}
    




\begin{Pro}\label{pro_fullpart_loss}
Suppose that, for all $\boldsymbol{\theta}^*$ in which $\bar{\theta}^*_i\ge \bar{\theta}_{\min}>0, \forall i$, (i) the inequality in (\ref{equ_a})  holds, and (ii) $\frac{\partial \Delta_i}{\partial \bar{\theta}^*_i}\le  \delta_i(\boldsymbol{\theta}^*, B,\lambda,s,\mathbf{q})$ holds for the function $\delta_i(\boldsymbol{\theta}^*, B,\lambda,s,\mathbf{q})$ defined in \eqref{equ_delta} of Appendix \ref{appendixsec_fullpart_loss}. Then, the optimal participation rate profile is $\boldsymbol{\theta}_f$ and the analyst obtains an unbiased estimator.
   
   
   
   
   
    
   
   
   
   
   
   
   

    \end{Pro}
    
    The proofs of Proposition \ref{Pro_fullpart_benefit}
and Proposition \ref{pro_fullpart_loss} are in Appendix \ref{appendixsec_fullpart_benefit} and Appendix \ref{appendixsec_fullpart_loss}, respectively.    To understand the conditions in these two propositions, note that Condition (i) in both propositions indicates that the budget is ``small'', i.e., lower than a certain threshold, which is related to the expectation of virtual cost in the population. It ensures that the allocation rule is strictly decreasing, according to Corollary \ref{cor_opt_pro}. Further, it holds if the budget itself is relatively low, or if the expectation of the virtual cost is relatively high. Recall that in the definition of virtual cost (Definition \ref{def_vcost}), the virtual cost is determined by both the cost and data correlation strength. In summary, Condition (i) indicates that the overall cost is relatively high, or the data correlation strength is relatively weak, or the budget is relatively low. 
    
Next we discuss Conditions (ii) in the above two propositions. Recall that the participation benefit  $\benefit{\bar{\theta}}$ is increasing in the participation rate. Condition (ii) in Proposition \ref{Pro_fullpart_benefit} implies that the increment of this benefit is high as average participation rate increases, which indicates that the participation benefit is large. Meanwhile, recall that  $\Delta_i= \ppl{\hat{c}{i}}{i}- \gppl{\hat{c}{i}}{i}$ captures the addition part of the privacy cost that  does not concern data correlation. Condition (ii) in Proposition \ref{pro_fullpart_loss} implies that the increment of this part of the privacy cost is small as the group participation rate increases, which indicates that the privacy cost of participation is closed to that of non-participation. Intuitively, if Conditions (ii) in the above two propositions holds,  the analyst does not need to pay a lot to each agent to incentivize her participation. This is because the benefit of participation is significant (Condition (ii) in Proposition \ref{Pro_fullpart_benefit}) or the negative impact of participation is small (Condition (ii) in Proposition \ref{pro_fullpart_loss}). As a result, the expected payment of each agent is relatively low. This enables the analyst to increase the participation rate and  incentivize more fraction of the population. This finally leads to  a full participation rate to induce zero bias. 
  
  
\section{Concluding Remarks}

In this paper we study the design of an optimal mechanism for data acquisition in a setting where there is correlation among the data of participants that leads to information leakage.  Information leakage is a crucial and under-explored feature of data markets and our results represent the first to characterize an optimal mechanism for data acquisition in such a setting.  Additionally, our results provide the analyst the ability to optimally trade off bias and variance of the resulting estimator.  

Further, our results provide important perspectives about the consequences of correlation and information leakage for data marketplaces.  In particular, intuitively one might expect that these factors, which underlie the privacy paradox, would lead to inefficiencies where data marketplaces  exploit participants and obtain data for lower prices than otherwise.  The analysis in this paper shows that this is indeed the case.  Combined with the results of \cite{acemoglu_privacy}, there is a compelling argument that information leakage is a significant factor in market inefficiencies that lead to oversharing and reduced payments in data marketplaces.  

Thus, one may ask if it is possible to regulate data marketplaces to avoid such inefficiencies.  Unfortunately, our results highlight that typical suggestions, such as avoiding monopolistic platforms, may not be effective.  Since our results hold for any fixed participation rate, a platform can exploit information leakage regardless of its market size.  Further, differential privacy cannot eliminate the underlying issues in this case, which comes from inter-group and intra-group correlation.  Thus, an important open problem motivated by our work is: what approaches can be brought to bear to mitigate the impact of information leakage and the privacy paradox in data marketplaces?   


\bibliographystyle{unsrtnat}
