An Incentive Mechanism for Trading Personal Data in Data Markets

The contributions of this paper are as follows:

1. (i)

   Truthful price report mechanism: We propose an incentive mechanism that guarantees that the data provider maximizes her benefit when she reports her privacy price honestly.

2. (ii)

   Optimized incentive mechanism within the budget constraints: We propose an optimization method to maximize the data consumer’s profit and information gain in the setting where the data consumer has a fixed financial budget for data collection.

3. (iii)

   Optimized privacy budget splitting mechanism: We propose a method of splitting the privacy budget for the data providers, that allows them to maximize her utility-gain within a fixed privacy budget, in a multiple data consumer environment.

The properties of our methods are both proved formally and validated through experiments.

The structure of this paper is as follows: we explain the related works and preliminaries in Sections 2 and 3, respectively. We describe the proposed incentive mechanism in Section 4 and validate the proposed incentive mechanism through experiments in Section 5. Our conclusion and some potential directions of future work are discussed in Section 6.

In differential privacy concept, parameter $\epsilon$ is the knob to control the privacy-utility trade off. The smaller the $\epsilon$, the higher is the privacy protection level and the more it deteriorates the data utility. Conversely, a larger $\epsilon$ decreases the privacy protection level and enhances the data utility. However, there is no gold standard to determine the appropriate value of $\epsilon$. Apple has been promoting the use of differential privacy to protect user data since iOS 10 was released, but the analysis of [7] showed the $\epsilon$ value was set at approximately 10 without any particular reason. The work of [8] showed that the privacy protection level set by an arbitrary $\epsilon$ can be infringed by inference using previously disclosed information and proposed an $\epsilon$ setting method considering posterior probability. This matter is the main factor that undermines the claim that personal information is protected by differential privacy. Much research have been conducted to study and solve this problem [9, 10, 11, 12]. Although a lot of research is being done in this area, the problem of determining a reasonable way of choosing an optimal value for $\epsilon$ still remains open, as there are many factors to consider in deciding the value of $\epsilon$, and more studies are still needed. In this paper, we propose a technique to determine an appropriate value of $\epsilon$ by setting a price of the privacy of the data provider.

One of the solutions to find an appropriate value of $\epsilon$ is to price it according to the data accuracy [13, 14, 15, 16, 17, 18]. In [13], strength of the privacy guarantee and the accuracy of the published results are considered to set the $\epsilon$ value, and a simple $\epsilon$ setting model that can satisfy data providers and consumers was suggested. In [14], the author proposed a compensation mechanism via auction in which data providers are rewarded based on data accuracy and data consumer’s budget when they provide data with differential privacy. It is the most similar work to our study. The main differences between our paper and Ghosh and Roth’s work are as follows:

1. (i)

   We define a truthful price report mechanism that a data provider get a best profit when she reports her privacy price honestly, and prove it.

2. (ii)

   We propose an optimized incentive mechanism to maximize the data consumer’s profit with a fixed expense budget, and a privacy budget splitting method to maximize the data provider’s utility-gain in a multi-data consumer environment.

In [17] the authors design a mechanism that can estimate statistics accurately without compromising the user’s privacy. They propose a Bayesian incentive and privacy-preserving mechanism that guarantees privacy and data accuracy. The study of [18] proposes a Stackelberg game to maximize mobile users who provides their trajectory data.

Several techniques for pricing data assuming a data market environment have been studied in [19, 20, 21, 22, 23, 24, 25, 26].

In [19] the authors suggested a data pricing mechanism to make the balance between privacy and price in data market environment. In [20], the authors propose the data market model in the IoT environment and show the proposed pricing model has a global optimal point. In [21] the authors proposed a theoretical framework for determining prices to noisy query answer in the differentially private data market. However, this research cannot flexibly reflect the requirements of the data market. In the study of [23], the author proposed an $\epsilon$-choosing method based on Rubinstein bargaining and assumes a market manager that mediates a data provider and consumer in the data trading.

It is realistic to consider personal data as a digital asset, and reasonable to attempt to find a bridge between privacy protection level and price according to the value of $\epsilon$ in differential privacy, as has been done in this paper. Existing studies are attempting to find an equilibrium between data providers and consumers under the assumption that both are reasonable individuals. In this paper, we follow a research direction similar to existing studies, and focus on the incentive mechanism that motivates a data provider report her privacy price honestly. In particular, we consider that the value of differentially private data increases non-linearly with respect to the increase of the value of $\epsilon$.

The data market aims at collecting personal data legally with the consent of the provider. A data provider can sell her own data and get paid for it, and a data consumer can collect the personal data for analysis by paying a price, resulting in a win-win situation.

Naturally, the data consumer wants to collect personal data as accurately as possible at the lowest possible price, and the data provider wants to sell her data at a price as high as possible while protecting sensitive information. In general, every effective protection technique affects the utility of the data negatively. In the particular case of differential privacy, the levels of utility and privacy are determined by the parameter $\epsilon$; thus, the data price is affected directly by the value of $\epsilon$.

Determining the appropriate value of $\epsilon$ and the actual price of the data are critical to the success of the data market. However this is not an easy task, also because each data provider has different privacy needs [30].

We propose an incentive mechanism to find the price of the data and the value of $\epsilon$ that can satisfy both the data provider and the data consumer. The proposed method consists of two parts: an incentive mechanism encouraging the data provider to report her privacy price honestly to the data consumer, and an optimization scheme to maximize both the data consumer and provider’s profit within a budget constraint.

We consider a scenario with $n$ data providers, $u_{1},\ldots,u_{n}$, and $m$ data consumers, $D_{1},\ldots,D_{m}$, and where each provider and consumer proceeds with the deal independently (we use the term “data provider” and “data producer” interchangeably, in the same sense). The term “$\epsilon$ unit price” (e.g., $1$$ per $\epsilon$ value $0.1$) will be used to express the price, where $\epsilon$ is the parameter of differential privacy, which is a measure of the accuracy of information. We recall that, as $\epsilon$ increases, the data becomes less private and more information can be obtained from it, and vice versa. Thus, the price per unit $\epsilon$ represents the “value” of the provider’s information¹¹1The $\epsilon$ unit price can be of any form, including a monetary one. The method we propose is independent from the nature of the price, so we do not need to specify it.. The price of $\epsilon$ is expected to differ from one data provider to another, because each individual has a different privacy need. We denote the $\epsilon$ unit price reported by $u_{i}$ as $p_{i}$ and her true $\epsilon$ unit price as $\pi_{i}$.

Fig. 1 illustrates how the process works. At first, every data consumer broadcasts a function $f$ to the data providers, which represents the amount of data (expresses in $\epsilon$ units) the consumer is willing to buy for a given $\epsilon$ unit price. Each consumer has her own such function, and it can differ from one consumer to another. We will call it $\epsilon$-allocating function. We assume $f$ to be monotonically decreasing, as the consumers naturally prefer to buy more data from those data producers who are willing to offer them for less. Note that the product $p_{i}f(p_{i})$ represents the total amount that will be payed by the data producer to the consumer if they agree on the trade. The function $f$ however has also a second purpose: as we shown in Section 4.2, it is designed to encourage providers to demand the price that they really consider the true price of their privacy, rather than asking for more.

Then, thanks to the truthful price report mechanism (cf. Section 4.2), the data providers report the prices of their data honestly to the data consumers in accordance with the published $f$. In the example in Fig. 1, $u_{1}$ reports her $\epsilon$ price per $0.1$ as $1$$ and $u_{2}$ reports her $\epsilon$ price per $0.1$ as $2$$. Finally, the data consumer checks the price reported by the data provider and determines the total price and value of $\epsilon$ to be obtained from each provider using $f$. In this example, the data consumer $D_{1}$ determines $\epsilon_{1}$ to be 0.7 and $\epsilon_{2}$ to be 0.4.

Then, the data providers select the consumers to whom to sell their data in order to maximize their profits, and confirm with them the values of their $\epsilon$ and the total price they would receive. In the example in Fig. 1, $D_{1}$ pays 7$ to $u_{1}$ and 8$ to $u_{2}$. Finally, the data providers add noise to their data based on the determined $\epsilon$ and share the sanitized data with the respective consumers, and the consumers pay the corresponding prices to the providers. We assume that data providers and consumers keep the promise of the value of $\epsilon$ and compensation decided in the deal, once confirmed.

This process can be repeated until the data consumers exhaust all their budget or achieve the targeted amount of information. The task of allocating a suitable budget in each round and the how to determine the amount of needed information are also important topics, but they are out of the scope of this paper and are left for future work.

For the correct functioning of the data trading, the data provider should be honest and demand her true privacy price. However, she may be motivated to report a higher price, in the hope to persuade the data consumer that the information is “more valuable”, and be willing to pay more. Note also that the true privacy price of each data provider is a personal information that only the provider herself knows and is not obliged to disclose.

To solve this problem, we propose a truthful price report mechanism to ensure that the data providers report their $\epsilon$ unit prices honestly. The purpose of the mechanism is to provide incentive so that the providers are guaranteed to get the greatest profit when they report their true price.

When the data provider reports her price $p_{i}$, the data consumer determines the amount of $\epsilon$ to purchase using $f(p_{i})$, where $f$ is the $\epsilon$-allocating function introduced in Section 4.1. We recall that $f$ is a monotonically decreasing function, chosen by the consumer. We assume that the domain of $f$, the $\epsilon$ price unit, is normalized to take values in the interval $[0,1]$. The total price for the data estimated by the consumer is the product of the $\epsilon$ price unit and the amount to be purchased, namely, $p_{i}f(p_{i})$. To this value, the consumer adds an incentive $\int_{p_{i}}^{\infty}f(z)\,dz$, the purpose of which is to make convenient for the data producer to report the true price (we assume that the data producer knows $f$ and the strategy of the consumer in advance). The consumer should of course choose $f$ so to be happy with the incentive. In particular, the incentive should be finite, so the contribution of $f(z)$ should vanish as $z$ goes to ${\infty}$. An example of such a function is illustrated in Fig. 2.

Thus the data consumer sets the offer $\mu(p_{i})$ to the provider $u_{i}$ as follows:

We now illustrate how this strategy achieves its purpose of convincing the consumer to report her true price. We start by defining the utility that the data provider obtains by selling her data as the difference between the offer and the true price of her data, represented by the product of the true $\epsilon$ unit price and the amount to be sold, namely $\pi_{i}f(p_{i})$:

We are now going to show that he proposed mechanism guarantees truthfulness. The basic reason is that each provider $u_{i}$ achieves the best utility when reporting the true price. Namely, $\rho(\pi_{i})\geq\rho(p_{i})$ for any $p_{i}\in\mathbb{R^{+}}$, where we recall that $\pi_{i}$ is the true price of the provider $u_{i}$. The only technical condition is that the function $f$ is monotonically decreasing. Under this assumption, we have the following results (see also Fig. 3 to get the intuition of the proof):

In this section, we propose an optimization mechanism to identify an optimal function $f$ for the data consumer with respect to the following two desiderata:

1. (i)

   Maximum Information: maximize the total information gain of the data consumer with a fixed budget.

2. (ii)

   Maximum Profit: maximize the total profit of the data consumer with a fixed budget.

By “budget” here we mean the budget of the data consumer to pay the data providers.

We start by introducing the notions of total information and profit for the consumer. Note that, by the sequential compositionality of differential privacy, the total information is the sum of the information obtained from each data provider.

As for the profit, we can reasonably assume to be monotonically increasing with the amount of information obtained, and that the total profit is the sum of the profits obtained with each individual trading. The latter is naturally defined as the difference between the benefit (aka payoff) obtained by re-selling or processing the data, and the price payed to the data provider.

We will consider a family of functions $\mathcal{F}$ indexed by a parameter $c$, to which the $\epsilon$-allocating function $f$ belongs. The parameter $c$ reflects the data consumer’s will to collect the information and, for technical reasons, we assume $f$ to be continuous, differentiable and concave with respect to it. For each data provider, different values of $c$ will give different $f$, that, in turn, will give rise to a different incentive-curve as per equation (2), which the data consumer should adhere to for compensating for the information obtained from that data provider.

As described in previous sections, the $\epsilon$-allocating functions should be monotonically decreasing with the $\epsilon$ unit price, as the consumer is motivated to buy more information from the consumers that offer it at a lower price. This property also ensures, by Theorem 4.1, that the prices reported by the data producers will be their true prices. Hence we impose the following constraint on $\mathcal{F}$:

Note that we have added the parameter $c$ as an additional argument in $f$, so $f$ has now two arguments.

After the prices $p_{1},\ldots,p_{n}$ have been reported by the data producers $u_{1},\ldots,u_{n}$, the data consumer will try to choose an optimal $c$ maximizing her profit. Fig. 4 illustrates an example with two data provider’s incentive graph and payoff for data consumer.

We will analyse the possibility to choose an optimal $c$, that, in turn, leads to an optimal $f(c,\cdot)$ addressing scenarios (i) and (ii).

In the context of differential privacy, we may assume that $\tau$ (the data consumer’s payoff function) is additive, i.e.,

This is a reasonable assumption that goes well along with the sequential compositionality property of differential privacy, at least for small values of $\epsilon$²²2From a technical point of view, the additive property holds also for large values of $\epsilon$. However, from a practical point of view, for large values of $\epsilon$, for instance $200$ and $400$, then the original information is almost entirely revealed in both cases, and would not make sense to pay twice the price of $200$ $\epsilon$ units to achieve $400$ $\epsilon$ units..

We start by showing that the two desiderata (i) and (ii) are equivalent:

In our model, for the scenario we have considered so far, the parameter $c$ is determined by the number of providers and the budget. We observe that, in both Examples 3 and 4, if $n$ increases than $c$ increases, and vice versa. This seems natural, because in the families of both these example $c$ the incentive that the consumer is going to propose decreases monotonically with $c$. This means that the larger is the offer, the smaller is the incentive that the consumer needs to be paying. In other words, the examples confirm the well known market law according to which the price decreases when the offer increases, and vice versa.

We note that we have been assuming that there is enough offer to satisfy the consumer’s demand. If this hypothesis is not satisfied, i.e., if the offer is smaller than the demand, then the situation is quite different: now the data producer can choose to whom to sell hid data. In particular, the data consumer who sets a lower $c$ will have a better chance to buy data because, naturally, the provider prefers to sell her data to the data consumers who give a higher incentive. In the next section we explore in more detail the process, from the perspective of the data provider, in the case in which the demand is higher than the offer.

After optimizing an incentive mechanism for a given data consumer dealing with multiple data providers, we focus on the flip side of the setup. We assume a scenario in which a given data provider has to provide her data to multiple data consumers, and that there is enough demand so that she can sell all her data.

Let there be $m$ data consumers, $D_{1},\ldots,D_{m}$ seeking to obtain data from the user $u$. By truthful price report mechanism, as discussed in Section 4.2, $u$ reports her true price to each $D_{i}$. As discussed in Section 4.3, $D_{i}$ computes her optimal $\epsilon$-allocating function $f_{i}$ and requests data from $u$, differentially privatized with $\epsilon=f_{i}(\pi)$. After receiving $f_{1},\ldots,f_{m}$, $u$ would like to provide her data in such a way that maximizes her utility received after sharing her data.

It is important to note here that $u$ is not obliged to deal with any data consumer $D_{i}$, even after receiving $f_{i}$. Realistically, $u$ has a privacy budget of $\epsilon_{\text{total}}$, which she would not exceed at any price. Let $S=\{i_{1},\ldots,i_{k}\}$ be an arbitrary subset $\{1,\ldots,m\}$. By the sequential composition property of differential privacy, the final privacy parameter achieved by $u$ by sharing her data to an arbitrary set of data consumers $D_{i_{1}},\ldots,D_{i_{k}}$ is $\epsilon_{S}=\sum_{j\in S}f_{j}(\pi)$. $u$’s main intention is to share her data in such a way that ensures $\epsilon_{S}\leq\epsilon_{\text{total}}$ for all subset $S$ of $\{1,\ldots,n\}$, while maximizing $\sum_{j\in S}\rho_{i}(\pi,f_{j})$, i.e., the total utility received. Reducing it down to the 0/1 knapsack problem, we propose that $u$ should be dealing with $\{D_{i_{1}},\ldots,D_{i_{k}}\}$ where $S^{*}=\{i_{1},\ldots,i_{k}\}\subseteq\{1,\ldots,m\}$, chosen as

We show the pseudocode for the $\epsilon$ allocation algorithm and the entire process in Algorithms 1 and 2.