### 5.2.2 Fairness

With the recent surge of interest in building ethical ways to train machine learning models, the topic of fairness in machine learning has been in the spotlight and, correspondingly, various metrics and algorithms to quantify and establish fairness in model training have been studied from a variety of perspectives and in different contexts [154–156]. Most fairness metrics consider the simple case of having a *privileged* group and an *unprivileged* group in the population. Under this assumption, typically one attribute of the dataset is selected as a sensitive attribute (e.g., gender, race, etc.) that defines the privileged and the unprivileged groups. The goal of fairness in machine learning is to ensure fair and non-discriminated results regardless of the membership in a sensitive attribute. The two main notions of fairness considered by the community are individual fairness and group fairness: *Individual fairness* [157] claims that similar individuals should be treated similarly, and *group fairness* requires that different demographic subgroups should receive equal treatment with respect to their sensitive attributes. While both notions of fairness are important, in this work, we focus on group fairness because our goal is to analyze and mitigate the potential bias against certain groups (e.g. demographic groups) through personalization techniques. In particular, we considered the following metrics for evaluating group fairness as a part of this work.

Without loss of generality, we shall use $S = 1$ to represent the privileged group and $S = 0$ to represent the unprivileged group in the rest of the chapter.

**DEFINITION 5.2.1.** *Equal opportunity* [158] is satisfied by a system if its prediction $\hat{Y}$ is conditionally independent of the sensitive attribute $S$ given the target label $Y$

$$ \mathbb{P}[\hat{Y} = 1 | Y = 1, S = 1] = \mathbb{P}[\hat{Y} = 1 | Y = 1, S = 0] \quad (5.5) $$

In other words, equal opportunity is satisfied if the system produces equal true positive rates across the privileged and unprivileged groups.

**DEFINITION 5.2.2.** A system satisfies equalized odds [158] if its prediction $\hat{Y}$ is conditionally independent of the sensitive attribute $S$ given the target label $Y$,

$$ \mathbb{P}[\hat{Y} = 1 | Y = y, S = 1] = \mathbb{P}[\hat{Y} = 1 | Y = y, S = 0], \quad y \in \{0, 1\} \quad (5.6) $$

In other words, in order to ensure having equalized odds, a system requires the privileged and unprivileged groups to have equal true positive rates and equal false positive rates.

**DEFINITION 5.2.3.** *Demographic parity* [157] is achieved by a system when the prediction $\hat{Y}$ of the target label $Y$ is statistically independent of the sensitive attributes $S$, i.e.,

$$ \mathbb{P}[\hat{Y} | S = 1] = \mathbb{P}[\hat{Y} | S = 0] \quad (5.7) $$

In practice, under the aforementioned metrics, we might not require the difference between
the privileged and unprivileged groups to be exactly zero but we aim to minimize this gap.

## 5.3 Related Works

Federated optimization has demonstrated suboptimal performance when the local datasets consist of samples from non-congruent distributions, resulting in the inability to simultaneously minimize both client-level and global objectives. In previous studies [138–140], researchers examined various meta-algorithms for personalization, but the assertion of preserving user privacy relies solely on clients releasing updated models or model updates, rather than transferring raw data to the server, which can have significant consequences. To address this issue, several works have focused on the privatization of the (federated) optimization algorithm within the framework of DP [27, 144, 145, 159], which adopt DP to provide defences against an *honest-but-curious* adversary. However, even in this setting, there is no guarantee of protection against sample reconstruction from the local datasets using client updates, as highlighted in [143]. Various strategies have been explored to offer local privacy guarantees, either through cryptographic approaches [160] or within the framework of local DP [146, 161, 162]. Specifically, in [162], the authors tackle the problem of personalized and locally differentially private federated learning, but only for the case of simple convex, 1-Lipschitz cost functions of the inputs. It is worth noting that this assumption is unrealistic in the majority of machine learning models and excludes many statistical modelling techniques, particularly neural networks. Finally, some research focused on designing architectures capable of providing private computing environments for remote users [163], often making use of trusted platform modules, secure processors [164], or similar mechanisms [165] improving efficiency by enforcing encryption on network transmissions, rather than memory accesses. For example, the latter work conceptualizes an architecture that could be leveraged to deploy a server that can only reveal the data being processed to clients that instantiated the server. It shall be noted, however, that cryptographic guarantees of security are orthogonal to the privacy notions of differential privacy and its generalizations.

Of late, a great deal of attention has been devoted to studying and understanding the aspects of fairness in machine learning [153, 166–171]. Most of the research on fairness focuses on developing techniques to mitigate bias in machine learning algorithms. These techniques can be categorized into three main approaches: pre-processing, in-processing, and post-processing. Pre-processing techniques [172, 173] aim to generate a less biased dataset by modifying the values or adjusting the sampling process. In the case of in-processing techniques [174, 175], the objective function is optimized while taking into account discrimination-aware regularizers. Post-processing techniques [176, 177] involve adjusting the trained model to produce fairer outcomes. However, it is worth noting that the majority of these studies primarily target centralized machine learning models as opposed to FL. Furthermore, there is a lack of research exploring the interplay between accuracy and fairness [169, 170] or privacy and fairness [153, 178]. In particular, to the best of our knowledge, disproportionately fewer works have focused on investigating the relationship between privacy and fairness. [153] formally proved that privacy and fairness can be at odds with each other with non-trivial accuracy. A few recent works on group
fairness in FL have emerged [167, 168] but they do not consider the facet of privacy-fairness trade-off.

## 5.4 An Algorithm for Private and Personalized Federated Learning

We propose an algorithm for personalized federated learning with local guarantees to provide group privacy (Algorithm 6). Locality refers to the sanitization of the information released by the client to the server, whereas group privacy refers to indistinguishability with respect to a neighbourhood of clients, defined with respect to a certain distance metric. Thus we proceed to define *neighbourhood* and *group*.

**Definition 5.4.1.** For any model parametrized by $\theta_0 \in \mathbb{R}^n$, we define its $r$-neighbourhood as the set of points in the parameter space which are at a $L_2$ distance of at most $r$ from $\theta_0$, i.e., $\{\theta \in \mathbb{R}^n: \|\theta_0 - \theta\|_2 \le r\}$. Clients whose models are parametrized by $\theta \in \mathbb{R}^n$ in the same $r$-neighbourhood are said to be in the same *group*, or *cluster*.

Algorithm 6 is motivated by the Iterative Federated Clustering Algorithm (IFCA) [138] and builds on top of it to provide formal privacy guarantees. The main differences lie in the introduction of the SanitizeUpdate function described in Algorithm 7 and $k$-means for server-side clustering of the updated models.

**Algorithm 6:** An algorithm for personalized federated learning with formal privacy guarantees in local neighbourhoods.

**Input:** number of clusters: $k$, initial hypotheses: $\theta_j^{(0)}, j \in \{1, \dots, k\}$, number of rounds: $T$, number of users per round: $U$, number of local epochs: $E$, local step size: $s$, user batch size: $B_s$, noise multiplier: $\nu$, local dataset held by user $c$: $Z_c$;
Server-side loop;
**for** $0 \le t \le T-1$ **do**
  $C^{(t)} \leftarrow \text{SAMPLEUSERSUBSET}(U)$;
  BROADCASTPARAMETERVECTORS($C^{(t)}$; $\theta_j^{(t)}$, $j \in \{1, \dots, k\}$);
  Client-side loop;
  **for** $c \in C^{(t)}$ **do**
    in parallel:;
    $\bar{j} = \operatorname*{argmin}_{j \in \{1, \dots, k\}} F_c(\theta_j^{(t)}; Z_c)$;
    $\theta_{\bar{j},c}^{(t)} \leftarrow \text{LOCALUPDATE}(\theta_j^{(t)}; s; E; Z_c)$;
    $\hat{\theta}_{\bar{j},c}^{(t)} \leftarrow \text{SANitizeUPDATE}(\theta_j^{(t)}; \nu)$;
    $\{S_1, \dots, S_k\} = \text{k-means}(\hat{\theta}_{\bar{j},c}^{(t)}, c \in C^{(t)}; \theta_j^{(t)}, j \in \{1, \dots, k\})$;
    $\theta_j^{(t+1)} \leftarrow \frac{1}{|S_{\bar{j}}|} \sum_{c \in S_{\bar{j}}} \hat{\theta}_{\bar{j},c}^{(t)}$, $\forall j \in \{1, \dots, k\}$;
**Algorithm 7:** SanitizeUpdate obfuscates a vector $\theta \in \mathbb{R}^n$ with a Laplacian noise tuned on the radius of a certain neighbourhood and centred in 0.

**function** SANITIZEUPDATE($\theta_{j,c}^{(t)}$; $\nu$)

$$ \delta_c^{(t)} = \theta_{j,c}^{(t)} - \theta_j^{(t)} $$

$$ \epsilon = \frac{n}{\nu \|\delta_c^{(t)}\|} $$

Sample $\rho \sim \mathcal{L}_{\epsilon}(0)$

$$ \hat{\theta}_{j,c}^{(t)} = \theta_{j,c}^{(t)} + \rho $$

$$ \textbf{return} \hat{\theta}_{j,c}^{(t)} $$

**end function**

### 5.4.1 The Laplace mechanism under Euclidean distance in $\mathbb{R}^n$

Algorithm 7's SanitizeUpdate is based on a generalization of the Laplace mechanism under Euclidean distance to $\mathbb{R}^n$, introduced in [179] for geo-indistinguishability in $\mathbb{R}^2$. The motivation to adopt the $L_2$ norm as a measure of distance is twofold. First, clustering is performed on $\theta$ with the k-means algorithm under Euclidean distance. Since we define clusters or groups of users based on how close their model parameters are under $L_2$ norm, we are looking for a d-privacy mechanism that obfuscates the reported values within a certain group and allows the server to discern among users belonging to different clusters. Second, parameters that are sanitized by equidistant noise vectors in $L_2$ norm are also equiprobable by construction and lead to the same bound in the increase of the cost function in first-order approximation, as shown in Proposition 5.2. The Laplace mechanism under Euclidean distance in a generic space $\mathbb{R}^n$ is defined in Proposition 5.1.

**PROPOSITION 5.1.** Abusing the notation $\mathbb{P}[\cdot]$ to denote the PDF, let $\mathcal{L}_{\epsilon}: \mathbb{R}^n \to \mathbb{R}^n$ be the Laplace mechanism with distribution $\mathcal{L}_{x_0, \epsilon}(x) = \mathbb{P}[\mathcal{L}_{\epsilon}(x_0) = x] = K e^{-\epsilon d(x,x_0)}$ with $d$ being the Euclidean distance. If $\rho \sim \mathcal{L}_{x_0, \epsilon}(x)$, then:

1. $\mathcal{L}_{x_0, \epsilon}$ is $\epsilon$-d-private and $K = \frac{\epsilon^n \Gamma(\frac{n}{2})}{2\pi^{\frac{n}{2}} \Gamma(n)}$

2. $\|\rho\|_2 \sim \gamma_{\epsilon,n}$ s.t. $\mathbb{P}[\|\rho\|_2 = r] = \frac{\epsilon^n e^{-\epsilon r} r^{n-1}}{\Gamma(n)}$

3. The $i^{th}$ component of $\rho$ has variance $\sigma_{\rho_i}^2 = \frac{n+1}{\epsilon^2}$

where $\Gamma(n)$ is the Gamma function defined for positive reals as $\int_0^\infty t^{n-1}e^{-t} dt$ which reduces to the factorial function whenever $n \in \mathbb{N}$.

**PROPOSITION 5.2.** Let $y = f(x, \theta)$ be the fitting function of a machine learning model parameterized by $\theta$, and $(X, Y) = Z$ the dataset over which the RMSE loss function $F(Z, \theta)$ is to be minimized, with $x \in X$ and $y \in Y$. If $\rho \sim \mathcal{L}_{0, \epsilon}$, the bound on the increase of the cost function does not depend on the direction of $\rho$, in first-order approximation, and:

$$ \begin{aligned} & \|F(Z, \theta + \rho)\|_2 - \|F(Z, \theta)\|_2 \le \\ & \|J_f(X, \theta)\|_2 \|\rho\|_2 + o(\|J_f(X, \theta)\|_2) \end{aligned} \qquad (5.8) $$
<figure><img src="image_27.png" /><figcaption>**Figure 5.2:** An illustration of the implementation of the Laplace mechanism to achieve $\varepsilon$-d-privacy for model parameters in $\mathbb{R}^2$</figcaption></figure>

The results in Proposition 5.1 allow to reduce the problem of sampling a point from Laplace to i) sampling the norm of such point according to the result in Item 2 of Proposition 5.1 and then ii) sample uniformly a unit (directional) vector from the hypersphere in $\mathbb{R}^n$. Much like DP, d-privacy provides a means to compute the total privacy parameters in case of repeated queries, a result known as the Compositionality Theorem for d-privacy 5.3. Although it was known as a folk result, we provide formal proof in Appendix D.

**THEOREM 5.3.** Let $\mathcal{K}_i$ be $(\varepsilon_i)$-d-private mechanism for $i \in \{1, 2\}$. Then their independent composition is $(\varepsilon_1 + \varepsilon_2)$-d-private.

## 5.4.2 A Heuristic for defining the Neighbourhood of a Client

At the $i^{th}$ iteration, when a user $c$ calls the SanitizeUpdate routine in Algorithm 7, it has already received a set of hypotheses, optimized $\theta_j^{(t)}$ (the one that fits best its data distribution), and got $\theta_{j,c}^{(t)}$. It is reasonable to assume that clients whose datasets are sampled from the same underlying data distribution $\mathcal{D}_j$ will perform an update similar to $\delta_c^{(t)}$. Therefore, we enforce points which are within the $\delta_c^{(t)}$-neighbourhood of $\hat{\theta}_{j,c}^{(t)}$ to be indistinguishable. To provide this guarantee, we tune the Laplace mechanism such that the points within the neighbourhood are $\varepsilon \|\delta_c^{(t)}\|_2$ differentially private. With the choice of $\varepsilon = n/(v\delta_c^{(t)})$, one finds that $\varepsilon \|\delta_c^{(t)}\|_2 = n/v$, and we call $v$ the *noise multiplier*. It is straightforward to observe that the larger the value of $v$ gets, the stronger is the privacy guarantee. This results from the norm of the noise vector sampled from the Laplace distribution being distributed according to Equation (D.6) whose expected value is $E[\gamma_{\varepsilon,n}(r)] = n/\varepsilon$.

# 5.5 Experiments

## 5.5.1 Characterizing privacy

In the following Section, we provide a number of experimental validations of our algorithm on different tasks and datasets. In particular, we aim to evaluate and assess the trade-off in
training personalized federated learning models under formal local privacy guarantees. Detailed experimental settings are discussed in Appendix E.

### 5.5.2 Synthetic Data

We generate data according to $k = 2$ different distributions: $y = x^T\theta_i^* + u$ and $u \sim \text{Uniform}[0, 1)$, $\forall i \in \{1, 2\}$ and $\theta_1^* = [+5, +6]^T$, $\theta_2^* = [+4, -4.5]^T$. We then assess how training progresses as we move from the Federated Averaging [180] (Figure 5.3a, 5.3b, 5.3c), to IFCA (Figure 5.3d, 5.3e, 5.3f), and finally Algorithm 6 (Figure 5.3g, 5.3h, 5.3i). When using Federated Averaging, there seems to be an obvious problem, that is using one single hypothesis is not enough to capture the diversity in the data distributions, resulting in the final parameters settling somewhere in between the optimal parameters (Figure 5.3b). On the contrary, using IFCA, shows that having multiple initial hypotheses helps in improving the performance when the clients have heterogeneous data, as the optimized clients-parameters almost overlap the optimal parameters (Figure 5.3e). Adopting our algorithm shows that on top of providing formal guarantees, we can still achieve great results in terms of proximity to the optimal parameters (Figure 5.3h) and reduction of the loss function (Figure 5.3i). Figure 5.4 provides the maximum value of privacy leakage clients incur per cluster. Further details about the experimental settings are provided in Appendix E.

### 5.5.3 Hospital Charge Data

This experiment is performed on the Hospital Charge Dataset by the Centers for Medicare and Medicaid Services of the US Government [181]. The healthcare providers are considered the set of clients willing to train a machine learning model with federated learning. The goal is to predict the cost of a service given where it is performed in the country, and what kind of procedure it is. More details on the preprocessing and training settings are included in Appendix E. To assess the trade-off between privacy, personalization and accuracy, a different number of initial hypotheses has been checked, as it is not known apriori how many distributions generated the data. Accuracy has been evaluated at different levels of the noise multiplier $\nu$. Note that, using Algorithm 6 with 1 hypothesis results in the Federated Averaging algorithm. Figure 5.5 shows that adopting multiple hypotheses drastically reduces the RMSE loss function. This is especially true when moving from 1 to 3 hypotheses. Additionally, we highlight how increasing the number of hypotheses also helps in curbing the effects of the noise multiplier even when it reaches high levels, on the right-hand side of the picture, making a compelling case for adopting formal privacy guarantees when a slight increase in the cost function is admissible. Figure 5.6 provides the empirical privacy leakage distribution of the clients involved in a particular training configuration. Table 5.1 shows privacy leakage statistics over multiple rounds and for all configurations.
<figure><img src="image_28.png" /><figcaption>**Figure 5.3:** Learning federated linear models with (a, b, c) one initial hypothesis and non-sanitized communication, (d, e, f) two initial hypotheses and non-sanitized communication, (g, h, i) two initial hypotheses and sanitized communication. The first two figures of each row show the parameter vectors released by the clients to the server.</figcaption></figure>
<figure><img src="image_29.png" /><figcaption>**Figure 5.4:** Synthetic data: max privacy leakage among clients. Privacy leakage is constant when clients with the largest privacy leakage are not sampled (by chance) to participate in those rounds.</figcaption></figure>

<table><caption>**Table 5.1:** Hospital charge data: median and maximum local privacy budgets over the whole set of clients, averaged over 10 runs with different seeds. $v = 0$ means no privacy guarantee.</caption><thead><tr><th rowspan="2">v</th><th colspan="4">Hypotheses</th></tr><tr><th>7</th><th>5</th><th>3</th><th>1</th></tr></thead><tbody><tr><td>0</td><td>-, -</td><td>-, -</td><td>-, -</td><td>-, -</td></tr><tr><td>0.1</td><td>517.0, 1551.0</td><td>418.0, 1342.0</td><td>473.0, 1386.0</td><td>528.0, 1540.0</td></tr><tr><td>1</td><td>36.3, 126.5</td><td>40.7, 127.6</td><td>44.0, 138.6</td><td>49.5, 147.4</td></tr><tr><td>2</td><td>15.4, 57.8</td><td>14.3, 54.5</td><td>22.0, 69.3</td><td>21.5, 66.6</td></tr><tr><td>3</td><td>7.7, 32.3</td><td>8.4, 36.7</td><td>12.5, 40.0</td><td>12.1, 40.0</td></tr><tr><td>5</td><td>5.7, 21.3</td><td>5.9, 22.0</td><td>5.5, 21.6</td><td>5.3, 20.9</td></tr></tbody></table>

### 5.5.4 FEMNIST Image Classification

This task consists of image-based character recognition on the FEMNIST dataset [182]. Details on the experimental settings are in Appendix E. With the choice of the range of noise multipliers $v$ the corresponding value for the privacy leakage $\varepsilon \|\delta_c^{(t)}\|_2 = n/v$ would be enormous, considering a CNN with $n = 206590$ parameters, providing no meaningful theoretical privacy guarantees. This is a common issue for local privacy mechanisms [183], and it comes from the linear dependence of the expected value of the norm of the noise vector on $n$: $\mathbb{E}[\gamma_{\varepsilon,n}(r)] = n/\varepsilon$. Still, it is possible to validate, in practice, whether this particular generalization of the Laplace mechanism can protect against a *specific* attack: DLG [143]. Figure 5.7 and Table 5.2 report the results of varying the noise multiplier values. When $v = 10^{-3}$ the ground truth image is fully reconstructed. Up to $v = 10^{-1}$ we see that at least partial reconstruction is possible. For $v \ge 1$ we see that, experimentally, the DLG attack fails to reconstruct input samples when we protect the client-server communication with the mechanism in Proposition 5.1.
<figure><img src="image_30.png" /><figcaption>**Figure 5.5:** RMSE for models trained with Algorithm 6 on the Hospital Charge Dataset. Error bars show $\pm\sigma$, with $\sigma$ the empirical standard deviation. Lower RMSE values are better for accuracy.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>**Figure 5.6:** Hospital charge data: the empirical distribution of the privacy budget over the clients for $v = 3$, 5 initial hypotheses, seed = 3, $r$ is the radius of the neighbourhood, and the total number of clients is 2062.</figcaption></figure>

<table><caption>**Table 5.2:** Effects of increasing the noise multiplier on the validation accuracy and standard deviation.</caption><thead><tr><th rowspan="2">v</th><th colspan="2">Cross Entropy loss</th><th colspan="2">RMSE loss</th></tr><tr><th>Average Accuracy</th><th>Standard Deviation</th><th>Average Accuracy</th><th>Standard Deviation</th></tr></thead><tbody><tr><td>0</td><td>0.832</td><td>± 0.012</td><td>0.801</td><td>± 0.001</td></tr><tr><td>0.001</td><td>0.843</td><td>± 0.006</td><td>0.813</td><td>± 0.014</td></tr><tr><td>0.01</td><td>0.832</td><td>± 0.017</td><td>0.805</td><td>± 0.008</td></tr><tr><td>0.1</td><td>0.834</td><td>± 0.026</td><td>0.808</td><td>± 0.019</td></tr><tr><td>1</td><td>0.834</td><td>± 0.014</td><td>0.814</td><td>± 0.012</td></tr><tr><td>3</td><td>0.835</td><td>± 0.017</td><td>0.825</td><td>± 0.010</td></tr><tr><td>5</td><td>0.812</td><td>± 0.016</td><td>0.787</td><td>± 0.003</td></tr><tr><td>10</td><td>0.692</td><td>± 0.002</td><td>0.687</td><td>± 0.014</td></tr><tr><td>15</td><td>0.561</td><td>± 0.005</td><td>0.622</td><td>± 0.003</td></tr></tbody></table>
<figure><img src="image_32.png" /><figcaption>**Figure 5.7:** Effects of the Laplace mechanism in Proposition 5.1 with different noise multipliers as a defense strategy against the DLG attack.</figcaption></figure>

### 5.5.5 Characterizing fairness

In this section, we analyze how group fairness improves with the personalization of the trained models under *d*-privacy guarantees when there are two groups with different data distributions. Experiments were performed on synthetic data and the FEMNIST image classification dataset that was used in Section 5.5.1. To ensure a thorough evaluation, we considered a variety of group fairness metrics in the experiments. In particular, we measured the fairness with respect to equal opportunity [158], equalized odds [158], and demographic parity [157] as explained in Section 5.2.2.

In particular, in Figures 5.9 and 5.10, the X-axis denotes the noise multiplier $v$ representing the amount of *d*-private noise added to the local updates as explained in Section 5.4.2 and the Y-axis denotes the difference in fairness between the privileged and unprivileged groups with respect to the different metrics of group fairness that we considered.

#### Synthetic data

Synthetic data was generated in a method similar to that in Section 5.5.2 with the following modifications for enabling ourselves to investigate the aspect of group fairness fostered by our method: i) Total number of users is 1000 and each user holds 10 samples. 800 users have data that is generated according to distributions $y = x^T\theta_1 + u$ and $u \sim \text{Uniform}[0, 1), \forall i \in \{1, 2\}$, and set as a privileged majority group $g_1$. The remaining 200 users have data that is generated according to distribution $y = x^T\theta_2 + 15 + u$ and $u \sim \text{Uniform}[0, 1), \forall i \in \{1, 2\}$, and set as an unprivileged minority group $g_2$. In this case, the sensitive attribute considered to evaluate fairness is the group id $G$ where $G \in \{g_1, g_2\}$. ii) For binary classification, we set labels by using the $z = \text{Sigmoid}(Y), \forall y, \hat{y} \in Y$. In the case of $g_1$, we assign the label 1 if the value of $z$ is greater than or equal to 0.5 and assign the label 0 otherwise. On the other
<figure><img src="image_33.png" /><figcaption>**Figure 5.8:** The first two plots from the left illustrate the spatial distribution of the samples in $g_1$ and $g_2$, respectively, and the third plot shows $g_1$ and $g_2$ superimposed together in the same space.</figcaption></figure>

hand, in the case of $g_2$, the label 1 is assigned when the $z = \text{Sigmoid}(Y - 15)$, $\forall y, \hat{y} \in Y$ is less than or equal to 0.5, and the label 0 is assigned otherwise. This setting is to simulate a situation in which discrimination occurs depending on sensitive attributes in the real world such as minorities would have experienced a higher loan rejection rate than white applicants with the same property [184]. Thus, in our experiment, label 1 could be interpreted as 'loan approved' and label 0 as 'loan denied'. The data generated in this way are shown in Figure 5.8.

We compared the fairness for two cases: one with a single hypothesis (no personalization) and the other with the number of hypotheses as 2 (with personalization) in the framework of Algorithm 6. The experimental results are demonstrated in Figure 5.9.

The results illustrated by Figure 5.9 assert that the personalization of models (i.e., Algorithm 6) enhances the group fairness under all the metrics and the levels of formal privacy guarantees compared to that of the non-personalized model. A major reason behind this significant improvement of fairness by the personalized model is that unlike the non-personalized model, which trains using data from both groups that are biased towards the majority group $g_1$, the personalized model training optimizes for each group's data distribution without disregarding the effect of the minority group $g_2$. We also observe that fairness deteriorates as the value of the noise multiplier increases, as we would expect. This is presumably due to the decreasing influence of the minority group $g_2$ as the amount of noise insertion increases. This is consistent with the philosophy behind the definition of DP and its variants. Furthermore, interestingly we
<figure><img src="image_34.png" /><figcaption>(a) Equal opportunity difference</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>(b) Equalized odds difference</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>(c) Demographic parity difference</figcaption></figure>

**Figure 5.9:** The figure shows the comparison between the personalized and non-personalized models for (from left) equal opportunity, equalized odds, and demographic parity, respectively. Experiments were performed for noise multipliers $v$ of 0.1, 1, 2, and 4. For all the metrics of fairness and the values of the noise multiplier, the personalized model is seen to possess improved fairness over the non-personalized model.

observe that the personalized model ensures better fairness than the non-personalized model even with the highest level of privacy protection. This shows that personalization in FL under $d$-privacy can be a comprehensive solution towards privacy-preserving and ethical machine learning as it provides both privacy guarantees and enhanced fairness.

## FEMNIST Image Classification

To evaluate the fairness of our method on real datasets, we considered FEMNIST image classification dataset in the same form as in Section 5.5.4. As in experiments performed with the synthetic data in Section 5.5.5, the size of the groups considered privileged and unprivileged were different denoting the existence of a majority and a minority in the population. In this part, the rotated images are set as the unprivileged group $g_2$ with a total number of sampled users of 382 forming only 20% of all users. and the un-rotated images are used to represent the privileged group $g_1$ with a total number of users of 1736. Like in the case of synthetic data considered before, the group membership was used to denote the sensitive attribute. In the case
<figure><img src="image_37.png" /><figcaption>(a) Equal opportunity difference</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>(b) Equalized odds difference</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>(c) Demographic parity difference</figcaption></figure>

**Figure 5.10:** The figure shows the comparison between the personalized and non-personalized models for equal opportunity equalized odds, and demographic parity. Experiments were performed for noise multipliers $v$ of 0.1, 1, 2, and 4. For all metrics of fairness and values of the noise multiplier, the personalized model improved fairness over the non-personalized model.

of $g_1$, we assign label 1 if the FEMNIST image label is even and 0 if it is odd. And for the $g_2$, we assign label 0 if the FEMNIST image label is even and assign 1 if it is odd. The experimental results are given by Figure 5.10.

We observe that the personalized model training harbours significantly better group fairness across all metrics compared to its non-personalized counterpart. The change in fairness due to the amount of noise added was not as notable as in the case of the synthetic dataset but it was still observed to deteriorate with an increase in the value of the noise multiplier. Personalized model training in FL under the highest level of privacy is still observed to have better fairness across all the metrics than (non-personalized) models trained in a classical FL framework even with no privacy, similar to what we observed in the experiments with the synthetic data.
# 6

# Characterizing the information leakage from
gradient updates in federated learning

## 6.1 Introduction

Substantial work in the area of privacy-preserving ML has explored the applicability of differential privacy (DP) [13, 14] in central ML model training [27]. However, such models require a trusted central server which has access to and processes the (sensitive) training data held by the clients. To circumvent the need for a centrally trusted curator, local differential privacy (LDP) [23] was proposed, in which data owners locally obfuscate their data before communicating them to the server. Unfortunately, the use of LDP has been shown to have a detrimental effect on the accuracy of ML models [185–189]. Hence, in order to ameliorate the trust model in ML-related tasks (e.g., by consolidating the possibility of having an honest-but-curious or an adversarial server) while maintaining an acceptable level of model accuracy, the notion of federated learning (FL) [26] was proposed.

FL is a distributed, collaborative approach to ML where participating clients process their data and train models locally, sharing only updates of the training process. Following this, a server aggregates the local updates across all the participating clients and communicates the aggregated update back to all the clients and the process is repeated. This, in turn, furnishes a *global* model by aggregating the local updates at each round of training. Generally, the goal of FL is privacy-aware optimization of a statistical model's parameters by minimizing a cost function over a collection of datasets which are distributed among a set of clients.

Although the ideas behind FL appear to address privacy concerns in the central model for
ML (caused by data sharing), many recent works have identified attacks which allow the recon-
struction of training data using only the shared gradients used in FL [20, 21, 190]. In particular,
Zhu et al. [20] were one of the pioneers in the area, illustrating a simple gradient-matching-
based attack in order to reconstruct the training data, which are supposedly held locally by the
participating clients. The attack is effective in an environment where the clients use simple
datasets (e.g., low-resolution images) with small batch sizes to train their local models. This
work was improved by Yin et al. [21] where the authors explored more sophisticated techniques
and used advanced computational resources to construct a gradient-inversion attack in vision-
based FL. Their attack is effective in reconstructing more complex training data (images with
high-resolution) of the participating clients even for high batch sizes. Our work is motivated by
these attacks, and aims to formally study how privacy breaches occur in FL by understanding
information leaks caused by gradient-sharing from a foundational perspective.

We commence by studying the information leakage fostered by the shared local updates for a simple example of a model trained by each client in every round. Later we extend our investigation to more realistic models under more pragmatic settings that are in use.

Contributions

The key contributions of this chapter are:

1. We provide a formal characterization of the information leakage from the shared gradient updates in federated learning.

2. We analyze the gradient-inversion type attacks in federated learning to understand their working from a foundational perspective.

3. To the best of our knowledge, we are the first to formally dissect and study such attacks in federated learning for a pragmatic multi-batch environment.

6.2 Preliminaries

We can describe a neural network in our setting as a function $F_{NN}: \mathcal{X} \to \mathbf{d}_{\mathcal{Y}}$ taking inputs $\mathcal{X}$ to distributions over labels $\mathcal{Y}$. We will assume $\mathcal{X} = \mathbb{R}^n$ for some fixed $n$.

As we aim to investigate some of the state-of-the-art gradient inversion attacks in FL given
by [20, 21], we adhere to the learning environment and model heuristics considered by them.
In particular, the nodes in the hidden layers each contain a bias term and use a ReLU activation
function, and the final layer uses a softmax activation to compute the output probabilities.

We denote by $x_i$ the $i$'th component of the input vector $\mathbf{x}$, and by $z_{k,l}$ the output from the $k$'th hidden node in layer $l$. The bias at hidden node $z_{k,l}$ is $b_{k,l}$. We write $w_{j,k,l}$ for the weight from node $j$ in layer $l-1$ to node $k$ in layer $l$. $^1$ Denote by $z_l$ the vector of outputs from hidden layer $l$, and by $\mathbf{w}_{k,l}$ the weight vector into node $k$ at layer $l$.

<footnote n="1">¹For nodes which are not connected we designate a weight of 0.</footnote>
**DEFINITION 6.2.1 (ReLU).** The ReLU activation function $f_R : \mathbb{R} \to \mathbb{R}_{\ge 0}$ is defined:

$$f_R(x) = \begin{cases} x & \text{if } x \ge 0 \\ 0 & \text{otherwise.} \end{cases} \qquad (6.1)$$

**DEFINITION 6.2.2 (Softmax probability).** The softmax function $\sigma : \mathbb{R}^k \to (0, 1]^k$ is defined

$$\sigma(z)_i = \frac{e^{z_i}}{\sum_{j=1}^{k} e^{z_j}}. \qquad (6.2)$$

Observe that $\sum_{i=1}^k \sigma(z)_i = 1$.

**DEFINITION 6.2.3 (Cross-entropy loss).** Given two probability distributions $\pi: d_y$ and $\rho: d_y$, the cross-entropy loss $\mathcal{L}: d_y \times d_y \to \mathbb{R}$ is given by

$$\mathcal{L}(\pi, \rho) = - \sum_{y \in \mathcal{Y}} \pi_y \log(\rho_y). \qquad (6.3)$$

**DEFINITION 6.2.4 (Gradient updates).** The gradient updates for a neural network consist of the vector of partial derivatives of each weight and bias w.r.t. the loss function $\mathcal{L}$. For $m$ weights $w_{k,\ell}$ into node $k$ at layer $\ell$ we have:

$$\nabla w_{k,\ell}(\mathbf{x}) = \left( \frac{\partial \mathcal{L}}{\partial w_{k,1}}, \frac{\partial \mathcal{L}}{\partial w_{k,2}}, \dots, \frac{\partial \mathcal{L}}{\partial w_{k,m}} \right) \qquad (6.4)$$

and for $m$ biases $b_\ell$ at layer $\ell$ we have

$$\nabla b_{\ell}(\mathbf{x}) = \left( \frac{\partial \mathcal{L}}{\partial b_1}, \frac{\partial \mathcal{L}}{\partial b_2}, \dots, \frac{\partial \mathcal{L}}{\partial b_m} \right). \qquad (6.5)$$

From the above, we can compute the value of the output from node $k$ at layer $\ell$ as:

$$z_{k,\ell} = f_R(w_{k,\ell} \cdot z_{(\ell-1)} + b_{k,\ell}) \qquad (6.6)$$

## 6.3 Federated learning setup

A classical cross-device FL setup involves clients training local models using their personal data and sharing the local gradient updates with a server. Each client's model is typically assumed to have an identical architecture. We assume an honest-but-curious adversary (e.g., the server) who can be trusted with the computations they are responsible for (e.g., aggregation of the shared gradients) but are efficient enough to exploit all the information they have access to (i.e., the architecture of the global model, the gradients shared with the server at each round of the federated model training, etc.) in order to reconstruct the personal data of the clients used for the local training which, in essence, defeats the whole point and motivation behind FL.

It is crucial to note that the architecture of the neural network for each of the participating
clients will determine the extent of the information that is leaked to the adversary. Furthermore, it is noteworthy to observe that with the knowledge of the model architecture used for local training and the gradients shared at each round, any scope of randomness is eradicated for the adversary and, therefore, the network is deterministic from the point of view of the attacker. Our simple leakage model is then to describe conditions under which the NN is an invertible function.

### 6.3.1 Overview of the federated model training

We consider the task of training a global model for classification tasks in a federated environment involving a set of clients C and a server S. Each client in C has a common architecture and begins with the same model parameters, which are broadcast in the first round. Thereafter, each client who is sampled to participate in a round of training trains their own model using their local (private) data before communicating the gradient updates to S. The gradients of all the participating clients in a given round are aggregated by the server and communicated back to all of the clients, who update their local models using the aggregated gradient updates. The process continues iteratively until the convergence of the collaboratively trained global model.

### 6.3.2 The neural network model

We assume that each client is equipped with a deep neural network, in which both the architecture and the initial parameters of the network (the weights and the biases) are known and common to all clients (and also known to the server). The weights and biases are initialized randomly. We assume a classical deep NN architecture, with n-dimensional inputs, r hidden layers of various dimensions (not necessarily fully connected) and an m-dimensional fully-connected output layer. Each node in the hidden layer contains a ReLU activation and a bias term. The output layer is passed through a softmax function (ie. as its activation) so that the output of the network is a probability distribution over m labels. Finally, we assume the network is trained using a cross-entropy loss function.

### 6.3.3 The NN training process

At each round of training, each client takes input from their local (private) data and passes it through the network. They then use gradient descent with backpropagation to compute updates to the weights and biases of their NN based on their own input data. They pass their proposed updates to the server, which collates them and averages them and returns these new updates to each client. Each client then updates their network based on the weights and biases sent by the server.

### 6.3.4 Adversarial assumptions

We assume that the server behaves as an honest-but-curious adversary trying to infer information about the sensitive training data. In particular, the adversary is equipped with:
a) knowledge of the architecture of the network including the activation functions at each layer and the loss function used to train the network; and

b) knowledge of the initial weights and biases of the network.

c) no trivial access to the training data (including the labels) or the output of any of the client's networks.

Note that some of the modern FL paradigms use decentralized techniques (e.g., secure aggregation) to compute the average gradient update in each round circumventing the need for a server. However, recent works like [191] have highlighted effective side-channel attacks that can *disaggregate* the averaged gradient updates reducing the threat model to that we considered in this work.

### 6.3.5 Measuring information leakage

To measure the information leakage from the system, we adopt the *information channel* model of Shannon [192] to model the flow of information from secrets to observations made by the adversary. We represent the channel as a matrix $C : \mathcal{X} \times \mathcal{Y} \rightarrow [0, 1]$ over secrets $\mathcal{X}$ and observations $\mathcal{Y}$, where $C_{\mathcal{X},\mathcal{Y}} = \mathbb{P}[Y = y | X = x]$. We usually think of $C$ as a function from $\mathcal{X}$ to distributions over $\mathcal{Y}$, written $C : \mathcal{X} \rightarrow \mathcal{D}_{\mathcal{Y}}$. In our model the observations are the gradient updates revealed to server, and the secrets are the inputs $\mathbf{x}$.

Observing that all sources of randomness in the NN model (the weights and biases) are known to the adversary, we deduce that the information channel $C$ is in fact *deterministic* (i.e. consisting of 0's and 1's only). Of particular interest is the case in which the information channel is the identity channel $I$, which means that the channel $C$ leaks *everything*, or equivalently when $C$ defines an invertible function. We will focus on this scenario in this chapter.

More generally, when $C$ is not the identity, then the adversary must make a guess at the secret; her probability of success can be defined using Bayes' rule as laid out in other works [19, 193]. We leave this approach to future work.

## 6.4 Information leakage in simple FL models

At first, we consider the objective of the collaboratively trained model to be binary classification with labels A or B and, hence, we aim to understand and analyze a simple setting where each client trains a neural network with one layer (i.e., with no hidden layer) and with a batch size of 1. We begin with an analysis of a toy neural network (TNN) depicted in Figure 6.1. The inputs are $n$-dimensional non-negative real vectors $\mathbf{x} \in \mathbb{R}_{\ge 0}^n$ and the output layer consists of 2 nodes, each containing a bias term and a softmax activation function which produces a distribution over labels $\{A, B\}$. Each client uses a cross-entropy loss function to train their network.
<figure><img src="image_40.png" /><figcaption>**Figure 6.1:** Illustration of a toy neural network consisting of a single input $x$ and a final layer with 2 nodes and a softmax activation function, interpreted as a probability distribution over labels. We include bias terms in each node in the final layer.</figcaption></figure>

## 6.4.1 Technical setup

To investigate the information leakage by the gradients and develop a foundational understanding and a formal characterization of gradient-inversion attacks in FL, w.l.o.g. we fix a client $c \in C$ and focus our analysis on the local model trained by them. Let $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{R}^n_{\ge 0}$, $|\mathbf{x}| \ne 0$ be the training data (input) used by $c$ and let $y(\mathbf{x}) \in \{A, B\}$ be the true label of $\mathbf{x}$. We assume the probability of the labels is determined exactly, so we write $y_A(\mathbf{x}) \in \{0, 1\}$ for the probability that $\mathbf{x}$ has label $A$, and correspondingly for label $B$. Denote by $z_A$ and $z_B$ the nodes of the final layer. Abusing notation, we also write $z_A(\mathbf{x})$ for the output from node $z_A$, and likewise for node $z_B$. Let $w_A \in \mathbb{R}^n$ and $w_B \in \mathbb{R}^n$ be the vectors of weights that feed into nodes $z_A$, $z_B$ respectively. Let $b_A, b_B \in \mathbb{R}$ be the biases introduced in $z_A$ and $z_B$, respectively. For input $\mathbf{x}$, let $p_A(\mathbf{x}) \in [0, 1]$ and $p_B(\mathbf{x}) \in [0, 1]$ represent the output probabilities given by the model.

From Def. 6.2.2 we derive:

$$p_A(\mathbf{x}) = \frac{e^{z_A(\mathbf{x})}}{e^{z_A(\mathbf{x})} + e^{z_B(\mathbf{x})}} \qquad (6.7)$$

$$p_B(\mathbf{x}) = \frac{e^{z_B(\mathbf{x})}}{e^{z_A(\mathbf{x})} + e^{z_B(\mathbf{x})}} \qquad (6.8)$$

Using Def. 6.2.3 we derive:

$$\mathcal{L}(p, y)(\mathbf{x}) = -y_A(\mathbf{x}) \log(p_A(\mathbf{x})) - y_B(\mathbf{x}) \log(p_B(\mathbf{x})). \qquad (6.9)$$

From Def. 6.2.4, we derive the following closed form for the gradient update vectors:

$$\nabla w_A(\mathbf{x}) = (p_A(\mathbf{x}) - y_A(\mathbf{x}))\mathbf{x} \qquad (6.10)$$

$$\nabla w_B(\mathbf{x}) = (p_B(\mathbf{x}) - y_B(\mathbf{x}))\mathbf{x} \qquad (6.11)$$

$$\nabla b(\mathbf{x}) = (p_A(\mathbf{x}) - y_A(\mathbf{x}), p_B(\mathbf{x}) - y_B(\mathbf{x})) \qquad (6.12)$$

**REMARK 6.4.1.** From (6.10) and (6.11), and knowing that $(y_A(\mathbf{x}), y_B(\mathbf{x})) =$
(0, 1) or (1, 0), we observe that corresponding components of $\nabla w_A(x)$ and $\nabla w_B(x)$ have different signs.

## 6.4.2 Analysing gradient leaks

### Gradients on biases leak everything

To lay down a rudimentary insight, we start by analysing the simplest setting: in the most primitive form of FL, recall that $\nabla w_A(x)$, $\nabla w_B(x)$ and $\nabla b(x)$ are observed by the adversary. We observe immediately that the gradients on the bias terms can be used to deduce the values of $x$ exactly.

**LEMMA 6.1.** Given a binary classification NN with no hidden layers, batch size 1 and a final layer containing bias terms, the gradient update using a cross-entropy loss function reveals the values of the input $x$ exactly.

*Proof.* In Appendix F. □

To analyze the information leakage caused by these gradient updates, we first define the notion of *gradient clones*.

**DEFINITION 6.4.1 (Gradient clones).** We call $x, x' \in \mathbb{R}$ *gradient clones* if $x \neq x'$, $|x|^2 + |x'|^2 \neq 0$, and $\nabla w_k(x) = \nabla w_k(x')$ for $k = A, B$.

Essentially, gradient clones are inputs $x$ which produce the same observations. Gradient clones exist whenever the information channel $C$ (representing the leakage to the adversary) is *not* an invertible function. The results of this section pinpoint the precise conditions under which gradient clones exist in our TNN, under the assumption that only the weight updates are shared with the adversary. In the rest of the chapter, for any vectors $v$ and $v'$, let $v \cdot v'$ denote their dot product.

**LEMMA 6.2.** If $x$ and $x'$ are gradient clones, there is some $K \in \mathbb{R}$ such that $x' = Kx$.

*Proof.* In Appendix F. □

**REMARK 6.4.2.** If the space of inputs is $\mathbb{R}_{\ge 0}^n$ or $\mathbb{R}_{\le 0}^n$ and if $x'$ is a gradient clone of $x$, then $y(x') = B$ can be trivially rejected by the comparison of the *signs* of the components of $\nabla w_B(x)$ and $\nabla w_B(x')$ and, hence, we will have $x' = Kx$ where $K > 0$. In the subsequent analysis, we assume that the domain of inputs is known to us as $\mathbb{R}_{\ge 0}^n$ (e.g., image data).

A noteworthy implication of Lemma 6.2 emerges when we consider images as inputs: two input images generate identical gradient updates iff they differ solely in their lighter or darker
shading. In practical terms, this implies an alarming lack of privacy protection for potentially sensitive images.

**LEMMA 6.3.** Setting $\gamma = \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B)$ and $\Delta = b_B - b_A$, $\mathbf{x}$ has a gradient clone iff there is some $K \in \mathbb{R}$ satisfying the equation

$$e^{K\gamma} - Ke^{\gamma} = (K-1)e^{\Delta}. \qquad (6.13)$$

The corresponding gradient clone of $\mathbf{x}$ would be $\mathbf{x}$ scaled by that $K$.

*Proof.* In Appendix F. $\square$

**THEOREM 6.4.** For any $K > 1$, if $\mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B) \le \frac{\ln K}{K-1}$, then $\mathbf{x}$ has no gradient clone scaled by that $K$.

*Proof.* In Appendix F. $\square$

**THEOREM 6.5.** $\mathbf{x}$ cannot have a gradient clone $\mathbf{x}'$ with $|\mathbf{x}'| > |\mathbf{x}|$ if there exists some $\lambda \in \mathbb{R}^+$ for which

$$\mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B) = 1 + \lambda + W_0 \left( \frac{e^{\Delta}}{e^{(1+\lambda e^{\Delta})}} \right)$$

where $\Delta = b_B - b_A$ and $W_0$ is the principal branch of the Lambert W-function.

*Proof.* In Appendix F. $\square$

**THEOREM 6.6.** $\mathbf{x}$ has a gradient clone $\mathbf{x}'$ iff all of the following hold:

$$a) \frac{e^{\Delta}}{e^{\gamma+e^{\Delta}}} - \frac{1}{\gamma} W \left( \frac{\frac{\gamma e^{\Delta}}{e^{\gamma+e^{\Delta}}}}{e^{\gamma+e^{\Delta}}} \right) \neq 1$$

$$b) e^{-1}(e^{\gamma} + e^{\Delta}) < \gamma e^{\frac{\gamma e^{\Delta}}{e^{\gamma+e^{\Delta}}}}$$

$$c) \mathbf{x}' = K\mathbf{x} \text{ with } K = \frac{e^{\Delta}}{e^{\gamma+e^{\Delta}}} - \frac{1}{\gamma} W \left( \frac{\frac{\gamma e^{\Delta}}{e^{\gamma+e^{\Delta}}}}{e^{\gamma+e^{\Delta}}} \right)$$

where $\gamma = \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B)$, $\Delta = b_B - b_A$, and $W(.)$ is the Lambert W-function.

*Proof.* In Appendix F. $\square$

**COROLLARY 6.7.** $\mathbf{x}$ has at most two gradient clones in $\mathbb{R}^n$.

*Proof.* In Appendix F. $\square$

**REMARK 6.4.3.** The results derived in this section extend naturally to arbitrary numbers of labels (i.e. multinary classification tasks).
To sum up, the implications of the above results can be summarised as:

1. For any observations $\nabla w_A, \nabla w_B$ there are at most 2 inputs (gradient clones) which could have produced those observations (Corollary 6.7).

2. Inputs $x, x'$ which produce identical observations are always scalar multiples of each other. (Lemma 6.2).

3. Given a neural network and a set of observations produced in a single round, the adversary can test whether there is exactly 1 (or exactly 2) inputs which could have produced those observations (Theorem 6.6).

**REMARK 6.4.4.** It is important to note that the focus of the aforementioned test (Thm. 6.6) is to check whether the channel is invertible or not, i.e., it checks whether the shared gradient update is unique w.r.t. the inputs resulting in them. We do not use this result to find the explicit value of the gradient clone.

### 6.4.3 Leakage from bigger batches

We now expand our analysis to models trained on batches of size greater than one. Following [21], we consider batches consisting of labels which are all distinct and use the signs of the gradient updates to recover the labels of the training batch.

For a batch $B$ of size $k$, the average gradient update obtained by training the local model by the client for every element of the batch (i.e., $\frac{1}{k} \sum_{w \in \nabla w_B} w$) is communicated to the server. Hence, we naturally extend the definition of a *gradient clone* to batches: a batch $B' \in \mathbb{R}_{\ge 0}^{n \times k}$ be called a *gradient clone* of $B \in \mathbb{R}_{\ge 0}^{n \times k}$ if $|B| = |B'|$, they comprise of the same set of labels, and $\frac{1}{k} \sum_{w \in \nabla w_B} w = \frac{1}{k} \sum_{w \in \nabla w_{B'}} w$.

Therefore, setting $\mathcal{L} = \{L_1, \dots, L_m\}$ as the set of all possible classification labels, let $B = \{x_1, \dots, x_k\} \subseteq \mathbb{R}_{\ge 0}^{n \times k}$, satisfying $m > k$, be a particular training batch used as an input to the local network trained by a client. Note that it is reasonable to assume that in real-life settings for classification tasks, the total number of possible classifying labels is higher than the size of the batches used for training. W.l.o.g., let the true labels associated with the batch $B$ be $L(B) = \{L_1, \dots, L_k\} \subset \mathcal{L}$ where $L_i = y(x_i)$ such that $y(x_i) = y(x_j)$ iff $i = j$. Using the same line of argument as presented in [21], let us assume that the adversary is able to recover the set of labels $L$ from having observed the shared gradient updates.

**LEMMA 6.8.** If batches $B = \{x_1, \dots, x_k\}$ and $B' = \{x'_1, \dots, x'_k\}$ are gradient clones, we must have $X\pi = X'\pi'$ where:

$$X = \begin{pmatrix} x_{11} & \cdots & x_{k1} \\ \vdots & \ddots & \vdots \\ x_{1n} & \cdots & x_{kn} \end{pmatrix}, \quad X' = \begin{pmatrix} x'_{11} & \cdots & x'_{k1} \\ \vdots & \ddots & \vdots \\ x'_{1n} & \cdots & x'_{kn} \end{pmatrix},$$
$$ \pi = \begin{pmatrix} p_{11} - 1 & p_{21} & \cdots & p_{k1} & \cdots p_{m1} \\ p_{12} & p_{22} - 1 & \cdots & p_{k2} & \cdots p_{m2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ p_{1k} & p_{2k} & \cdots & p_{kk} - 1 & \cdots p_{mk} \end{pmatrix}, $$

$$ \pi' = \begin{pmatrix} p'_{11} - 1 & p'_{21} & \cdots & p'_{k1} & \cdots p'_{m1} \\ p'_{12} & p'_{22} - 1 & \cdots & p'_{k2} & \cdots p'_{m2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ p'_{1k} & p'_{2k} & \cdots & p'_{kk} - 1 & \cdots p'_{mk} \end{pmatrix}, $$

and $p_{js} = \mathbb{P}[\mathbf{x}_s = L_j]$ (i.e., the output probability of the $s$th input of batch $X$ to be classified as label $L_j$) and, similarly, $p'_{js} = \mathbb{P}[\mathbf{x}'_s = L_j]$ for $s = 1, \dots, k$ and $j = 1, \dots, m$.

*Proof.* In Appendix F.

<figure><img src="image_41.png" /></figure>

As $B$ and $B'$ have the same labels, ideally we would have $p_{js} \approx p'_{js}$ for every $j \in \{1, \dots, m\}, s \in \{1, \dots, k\}$ (e.g., towards the beginning of training) and, in turn, implies $\pi \approx \pi'$. Therefore, Lemma 6.8 reduces to:

$$ (X - X')\pi = \mathbf{0}_{n \times k} \qquad (6.14) $$

An immediate consequence of this is that if $\pi$ has a right-inverse, then the input batch becomes unique w.r.t. the shared gradient updates averaged over the batch, implying the lack of privacy protection for the training data in FL.

**DEFINITION 6.4.2.** Setting the output probability of classifying $\mathbf{x}_s$ as its true label $L_s$ (i.e., $p_{ss}$) as $\sigma_s$ for all $s \in \{1, \dots, k\}$, we say that the FL model *learns well* if the output probabilities of obtaining the *wrong labels* be small and almost the same, i.e., $p_{js} \approx \frac{1-\sigma_s}{m-1}$ for each $j \in \{1, \dots, m\}$ s.t. $j \neq s$. In such a case, for each $s \in \{1, \dots, k\}$, let $p_{js} \approx \frac{1-\sigma_s}{m-1}$ be denoted by $r_s$.

Hence, under the assumption that the trained model learns well, we have:

$$ \pi = \underbrace{\begin{pmatrix} \sigma_1 - 1 & r_1 & \cdots & \cdots & r_1 \\ r_2 & \sigma_2 - 1 & \cdots & \cdots & r_2 \\ \vdots & \vdots & \ddots & \cdots & \vdots \\ r_k & r_k & \cdots & \sigma_k - 1 & r_k \end{pmatrix}}_{m} \qquad (6.15) $$

**DEFINITION 6.4.3.** We say that the batch $B = \{\mathbf{x}_1, \dots, \mathbf{x}_k\}$ consists of *similar data* if $\sigma_1 \approx \dots \approx \sigma_k$ which, in turn, would result in $r_1 \approx \dots \approx r_k$.

**REMARK 6.4.5.** Definition 6.4.3 essentially says that we call a batch of data similar if each input gives approximately the same softmax probability distribution pivoted around its corresponding true label.
<table><caption>**Table 6.1:** An example of a batch used in a given round of training consisting of datapoints which are *similar* as per Def. 6.4.3 for an FL model that has *learnt well* as per Def. 6.4.2. In other words, the images of the dog, the wolf, and the fox used in the training batch have very similar true-positive and true-negative probabilities.</caption><thead><tr><th rowspan="2">Batch</th><th colspan="3">Output probability (softmax)</th></tr><tr><th>"Dog"</th><th>"Wolf"</th><th>"Fox"</th></tr></thead><tbody><tr><td></td><td>0.70</td><td>0.13</td><td>0.17</td></tr><tr><td></td><td>0.12</td><td>0.71</td><td>0.17</td></tr><tr><td></td><td>0.13</td><td>0.15</td><td>0.72</td></tr></tbody></table>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

**THEOREM 6.9.** If the data in the batch that is used to train a certain round are *similar* and when the FL model *learns well*, the spatial arrangement of the members of the batch used for training is unique with respect to the shared gradients.

*Proof.* In Appendix F. □

**REMARK 6.4.6.** An immediate consequence of Theorem 6.9 is that if one of the elements of the training batch is identified, every other element in it can be reconstructed from the shared gradient updates (irrespective of the size of the batch or the number of dimensions of the data).

### 6.4.4 Leakage from batches size = 2:

Let us consider the case where clients use batches of size 2 to train their local models. Hence, by Lemma 6.8, $B = \{x_1, x_2\}$ and $B' = \{x'_1, x'_2\}$ are gradient clones iff:

$$ \begin{pmatrix} x_{11} & x_{21} \\ \vdots & \vdots \\ x_{1n} & x_{2n} \end{pmatrix} \begin{pmatrix} p_{11} - 1 & p_{21} & \cdots & p_{m1} \\ p_{12} & p_{22} - 1 & \cdots & p_{m2} \end{pmatrix} = \\ \begin{pmatrix} x'_{11} & x'_{21} \\ \vdots & \vdots \\ x'_{1n} & x'_{2n} \end{pmatrix} \begin{pmatrix} p'_{11} - 1 & p'_{21} & \cdots & p'_{m1} \\ p'_{12} & p'_{22} - 1 & \cdots & p'_{m2} \end{pmatrix} \quad (6.16) $$
**LEMMA 6.10.** For batch size = 2, $\pi$ (and, similarly, $\pi'$) is right-invertible.

*Proof.* In Appendix F.

<figure><img src="image_45.png" /></figure>

**REMARK 6.4.7.** A very similar line of argument used in the proof of Lemma 6.10 can be extended to show that $\pi$ (and, similarly, $\pi'$) is right invertible for batch size = 3 and, hence, all the subsequent results of this section can be extended to batches of size 3. We conjecture that this right-invertibility of $\pi$ holds for batches of size any arbitrary $k$.

**COROLLARY 6.11.** For batch size = 2, $X' = XD$ where $D = \pi\pi'^{-1}$.

*Proof.* Immediate from Lemma 6.8.

<figure><img src="image_46.png" /></figure>

**REMARK 6.4.8.** Corollary 6.11 essentially suggests that for a given input batch, a potential gradient clone would be a linear transformation of it. It is worth noting that $D$, as defined in Corollary 6.11, is a $k \times k$ matrix for a general batch of size $k$ (specifically, $2 \times 2$ in Corollary 6.11). Hence, for batch size 1 (i.e., $k = 1$), this reduces down to Lemma 6.2 and is consistent with the results presented in the earlier part of this chapter considering batches of size 1.

**THEOREM 6.12.** $d_E(\mathbf{x}_i, \mathbf{x}'_i) = d_E(\delta_{1i}\mathbf{x}_1, -\delta_{2i}\mathbf{x}_2)$ for $i = 1, 2$, where $D = \mathbf{I}_{2 \times 2} + \delta$.

*Proof.* In Appendix F.

<figure><img src="image_47.png" /></figure>

**REMARK 6.4.9.** One important implication of Theorem 6.12 is that we can derive the distance between the corresponding elements of the real training batch and a potential gradient clone of it and, hence, can deduce a bound on the space that needs to be pruned to eventually identify the real training batch.

# 6.5 Analyzing multi-layer neural networks

We now extend our analysis to a larger neural network depicted in Figure 6.2. We make the following assumptions: a) the final layer is fully connected (but not necessarily the hidden layers); b) ReLU activations are used on hidden layers with softmax on the final layer; c) $n$-dimensional real-valued inputs, $k$ hidden layers and an $\ell$-dimensional output layer, cross-entropy loss and batch size 1. We make no assumptions about the non-negativity of the inputs $\mathbf{x}$, assuming that they can take on any values in $\mathbb{R}$. We will assume ReLU activation functions throughout the network with a softmax on the final layer. We assume $n$-dimensional real-valued inputs, $r$ hidden layers and an $\ell$-dimensional output layer. We again assume that the loss function used in training is the cross entropy loss and that the batch size is 1.
<figure><img src="image_48.png" /><figcaption>**Figure 6.2:** Larger neural network example. The final layer is fully connected although this is not depicted in the diagram for simplicity of labelling. We make no assumptions about the number of hidden layers.</figcaption></figure>

From Def. 6.2.2 we derive:

$$p_i(\mathbf{x}) = \frac{e^{z_{i,k}(\mathbf{x})}}{\sum_{j=1}^{\ell} e^{z_{j,k}(\mathbf{x})}} \qquad (6.17)$$

Using Def. 6.2.3 we derive:

$$\mathcal{L}(p, y)(\mathbf{x}) = - \sum_{i=1}^{\ell} y_i(\mathbf{x}) \log(p_i(\mathbf{x})) . \qquad (6.18)$$

From Def. 6.2.4 we derive the following closed form for the gradient update vectors from the penultimate layer to the final layer:

$$\nabla w_{i,k}(\mathbf{x}) = (p_i(\mathbf{x}) - y_i(\mathbf{x}))z_{k-1} \qquad (6.19)$$

where $w_{i,k}$ is the weight vector into node i of layer r.

Finally, we derive a recursive form for the gradient update vectors between hidden layers up to the penultimate layer as follows. First, using (6.6) we derive: 2

$$\frac{\partial z_{k,l}}{\partial w_{k,l}} = z_{l-1} \qquad (6.20)$$

Then, for any hidden layer h we observe that: 3

<footnote>2This holds when the ReLU activation takes non-zero values. When it is zero, the derivative is also zero.</footnote>

<footnote>3The second line holds when the ReLU activation is non-zero. When it is zero, it contributes a zero weight.</footnote>
$$ \begin{aligned} \frac{\partial \mathcal{L}}{\partial z_{i,h}} &= \sum_{j} \frac{\partial z_{j,h+1}}{\partial z_{i,h}} \frac{\partial \mathcal{L}}{\partial z_{j,h+1}} \\ &= \sum_{j} w_{i,j,h+1} \frac{\partial \mathcal{L}}{\partial z_{j,h+1}} \end{aligned} \qquad (6.21) $$

where the summation is taken over all of the nodes connected to $z_{i,h}$ in layer $h+1$.

When $h$ is the final layer we derive:

$$ \begin{aligned} \frac{\partial \mathcal{L}}{\partial z_{i,h}} &= \sum_{j} \frac{\partial \mathcal{L}}{\partial p_{j}(\mathbf{x})} \frac{\partial p_{j}(\mathbf{x})}{\partial z_{i,h}} \\ &= p_{i}(\mathbf{x}) - y_{i}(\mathbf{x}) \end{aligned} \qquad (6.22) $$

Finally, we can compute the gradients of the weights in terms of the values in the network as follows:

$$ \begin{aligned} \nabla w_{i,h}(\mathbf{x}) &= \frac{\partial z_{i,h}}{\partial w_{i,h}} \frac{\partial \mathcal{L}}{\partial z_{i,h}} \\ &= z_{h-1} \frac{\partial \mathcal{L}}{\partial z_{i,h}} \quad [\text{using (6.20)}] \end{aligned} \qquad (6.23) $$

where the $\frac{\partial \mathcal{L}}{\partial z_{i,h}}$ term can be “unrolled” recursively (using the above equations) into a closed form in terms of $z, p, y$ and $w$ values from subsequent layers in the network.

In particular when $h$ is the first hidden layer we have that:

$$ \begin{aligned} \nabla w_{i,h}(\mathbf{x}) &= \frac{\partial z_{i,h}}{\partial w_{i,h}} \frac{\partial \mathcal{L}}{\partial z_{i,h}} \\ &= \mathbf{x} \frac{\partial \mathcal{L}}{\partial z_{i,h}} \end{aligned} \qquad (6.24) $$

### 6.5.1 Extending the TNN to a larger NN

The TNN analyzed in Section 6.4 can be viewed as a subnetwork of the larger NN that we consider in this section. In particular, we can think of the inputs $\mathbf{x}$ of the TNN as the outputs $z_{k-1}$ on the penultimate layer in the larger NN. From this perspective, the TNN results give conditions upon which we can deduce the output values in the penultimate layer. In this section we will show how knowledge of these penultimate layer values leaks the values of the secrets $\mathbf{x}$ in the larger NN.

Importantly, we note that the nodes in the penultimate layer contain ReLU activation functions, and thus all outputs $z_{k-1}$ are non-negative. In this section we will make no assumptions about the non-negativity of the inputs $\mathbf{x}$, assuming that they can take on any values in $\mathbb{R}$.
### 6.5.2 Leakage from the penultimate layer

The analysis of Section 6.4 showed that the inputs $x_i$ are leaked by the release of the gradients of the final layer (the derivatives of the loss function $\mathcal{L}$ w.r.t. the weights and biases of the final layer). In our larger NN example (cf. Figure 6.2), this corresponds to a leaking of the vector $z_{k-1}$, where here we are treating the $z_{i,k-1}$ as if they are inputs to the final layer (in orange). In other words, Lemma 6.1 tells us that the release of the gradients w.r.t. the biases on $z_k$ and the weights $w_k$ leaks the values $z_{k-1}$ exactly. We now show how this leaks the input values the $x$.

**LEMMA 6.13.** Let $z_{k-1}$ be the vector of outputs from the penultimate layer $k-1$ of a neural network. Assume a single non-zero value $z_{j,k-1}$ is revealed. Then every $z_{i,k-1}$ for $i \neq j$ can be deduced by an adversary with knowledge of the network and gradients.

*Proof.* In Appendix F. □

Lemma 6.13 tells us that knowledge of just one node of the penultimate layer is sufficient to leak the whole layer, even if the bias gradients are not revealed. Next, we show that knowledge of any hidden layer permits an adversary to learn the values in the previous layer.

**THEOREM 6.14.** Let $z_{k-1}$ denote the vectors of outputs from penultimate layer of the NN, and let $x$ be the vector of inputs. Then an adversary with knowledge of $z_{k-1}$ learns the values in $x$ exactly.

*Proof.* In Appendix F. □

Theorem 6.14 and Lemma 6.13 show that an adversary only requires knowledge of a single output value in the penultimate layer to learn the values of the inputs exactly. In Section 6.4 we derived conditions upon which the penultimate layer could be learned (by treating it as the input layer). Therefore we have characterized the conditions under which an adversary can learn the values of the inputs in a deep neural network using a softmax final activation function restricted to batches of size 1.

## 6.6 Discussion and open questions

The analyses carried out in this paper have opened up interesting avenues for future work. One intriguing future direction to pursue would be trying to formalize the trade-off between the diversity of a training batch and the corresponding information leakage that it incurs which may help the clients to optimally sample the batches to be used for training their local models. Another direction would be to widen the scope of our analysis by considering arbitrary loss and activation functions and introduce an information-channel modelling of the FL architecture to understand how an optimal defence model would look (e.g., using differential privacy and quantitative information flow) to optimize the privacy-utility trade-off in FL.
Part IV

Private data trading
"Privacy is something you can sell, but you can't buy it back."

– Bob Dylan
# An incentive mechanism for trading personal data in data markets

## 7.1 Introduction

Nowadays, as we are heading towards an information-based society, data is becoming one of the most essential resources contributing to the advancements in technology. In the past, data broker companies such as Acxiom collected personal data and sold them to companies that needed data. However, as users are becoming more and more aware of the value of their personal data and with a rise in concern about their privacy, people are less and less willing to let their data be collected for free. In this scenario, the model of data markets is starting to emerge in order to obtain high-quality personal information in exchange for compensation. Liveen [194] and Dataoup [195] are examples of prototypes of data market services where the data providers can obtain additional revenue from selling their data while the data consumers can collect the desired personal data.

The problem of privacy violation by personal data analysis is one of the major issues in such data markets. As the population is becoming increasingly aware of the negative consequences of privacy breaches (e.g., the Cambridge Analytica scandal [4]), people are reluctant to release their data unless they are properly sanitised. To facilitate this, techniques like noise insertion [13, 14], synthetic data generation [196], secure multi-party computation [197], and homomorphic encryption [198] are being actively studied.

Differential privacy provides a privacy protection framework based on solid mathematical foundations and enables quantified privacy protection according to the amount of noise insertion. However, like all privacy-protection methods, it deteriorates the data utility. If the data
provider inserts too much noise because of privacy concerns, the data consumer cannot proceed with the analytics with the required performance. Thus, the privacy protection and data utility depend on the amount of noise insertion while applying DP and this amount of noise is determined by the DP parameter $\varepsilon$. Thus, determining the appropriate value of the parameter $\varepsilon$ is a fundamental problem in differential privacy. It is difficult to establish the appropriate value of $\varepsilon$ because it depends on many factors that are difficult to quantify, like the attitude towards the privacy of the data provider, which may be different from person to person.

In this work, we propose an incentive mechanism to encourage the data providers to join the data market and motivate them to share more accurate data. The amount of noise insertion depends on the data providers' privacy preference and the incentives provided to them by data consumers. In the scope of this work, we assume a model where the data consumers decide on incentives to pay to the data provider by considering the profit to be made from the collected data. By sharing some of the consumers' profit as an incentive, the data providers can get fair prices for providing their valuable information to be used in the subsequent analytics. The proposed mechanism consists of the truthful price report mechanism and an optimization method within budget constraints. The truthful price report mechanism guarantees that the data provider takes the optimal profit when she reports her privacy price to the data consumer honestly. Based on a data provider's reported privacy price, a data consumer can maximize her profit within a potential budget constraint.

## Contributions

The key contributions of this chapter are:

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

2. We propose an optimization method to maximize the data consumer's profit and information gain with a fixed financial budget for data collection.

3. We propose a method of splitting the privacy budget for the data providers allowing them to maximize their utility gain within a fixed privacy budget dealing with multiple data consumers.

## 7.2 Related Work

### Methods for choosing $\varepsilon$

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

## Pricing mechanism

One of the solutions to find an appropriate value of $\varepsilon$, as has been explored in the literature, is to price it according to the data accuracy [205–210]. In [205], the strength of the privacy guarantee and the accuracy of the published results are considered to set the appropriate value of $\varepsilon$ and a simple model to assign the value of $\varepsilon$ that can satisfy data providers and consumers was suggested. In [206], the author proposed a compensation mechanism via auction in which data providers are rewarded based on the accuracy of the reported differentially private data and the data consumers’ budget. It is the most similar work to our study. The main differences between our work and Ghosh and Roth’s paper are as follows:

a) We define a truthful price report mechanism and formally show that a data provider gets the best profit when she reports her privacy price honestly.

b) 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 [209] 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 [210] proposes a Stackelberg game to maximize mobile users who provide their trajectory data.

Several techniques for pricing data assuming a data market environment have been studied in [211–218]. In [211], the authors suggested a data pricing mechanism to establish a balance between the privacy guarantees and the price of data in data markets. [212] proposed the data market model for IoTs and showed that the proposed pricing model has a global optimal point. In [213], the authors proposed a theoretical framework for determining prices to noisy responses to queries in differentially private data markets. However, this research cannot flexibly reflect the requirements of the data market. [215] highlighted an $\varepsilon$-choosing method based on Rubinstein bargaining and assumed 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 is reasonable to attempt to find a bridge between privacy protection level and price according to the value of $\varepsilon$ in DP. Existing
studies are attempting to find an equilibrium between data providers and consumers under the assumption that both are reasonable individuals. In this work, we follow a direction similar to existing studies and focus on the incentive mechanism that motivates a data provider to 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 $ε$.

## 7.3 Incentive mechanism for data markets

### 7.3.1 Overview of the proposed technique

Data markets aim at collecting personal data legally with the consent of the users holding the data. Typically in such scenarios, a data provider can sell her own data and get paid for it, and a data consumer can collect personal data for analysis by paying a price, resulting in a win-win situation. Naturally, the data consumer would want to collect personal data as accurately as possible at the lowest possible expenditure and the data provider would want to sell her data at a price as high as possible while protecting sensitive information. In general, every effective privacy-preserving technique affects the utility of the data negatively. In the particular case of DP, the levels of utility and privacy are determined by the parameter $ε$ and, hence, the price of the differentially private data is affected directly by the value of $ε$. Determining the appropriate value of $ε$ and the actual price of the data is critical to the success of the data market. However, this is not trivial especially when each data provider has different privacy needs [219] as is, typically, the case. We propose an incentive mechanism to find the price of the data and the value of $ε$ that can satisfy both the data provider and the data consumer.

<figure><img src="image_49.png" /><figcaption>**Figure 7.1:** An example of data trading process. In this figure, $u_i$ means the $i^{th}$ data provider and $D_j$ means the $j^{th}$ data consumer.</figcaption></figure>

We consider a scenario with $n$ data providers, $u_1, \dots, u_n$, and $m$ data consumers, $D_1, \dots, D_m$
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 "ε unit price" (e.g., 1$ per ε value 0.1) will be used to express the price per unit ε (the DP parameter used to obfuscate the reported data) as a measure of the accuracy of information. We recall that as ε increases, the data becomes less private and more information can be obtained from it, and vice versa. Thus, the price per unit ε represents the "value" of the provider's information<fnref n="1" />. The price of ε is expected to differ from one data provider to another because each individual has a different privacy requirement. We denote the ε unit price reported by $u_i$ as $p_i$ and her true ε unit price as $\pi_i$. Note that $p_i$ may not be the same as $\pi_i$ as the users reporting their ε unit price might render a piece of false information to the data consumers trying to insinuate that their data needs a higher (or lower) level of privacy protection than they really do.

Figure 7.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 (expressed in $\epsilon$ units) the consumer is willing to buy for a given $\epsilon$ unit price. Each consumer has her own 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 price (i.e., low value of $\epsilon$) or, correspondingly, a low level of privacy requirement (i.e., more accurate data). Note that the product $p_i f(p_i)$ represents the total amount that will be paid by the data producer to the consumer if they agree on the trade. The function $f$, however, has also a second purpose: as we show in Section 7.3.2, it is designed to encourage providers to demand the price that they really consider the true price of their privacy requirement rather than asking for more to manipulate the system.

Thanks to the truthful price report mechanism (cf. Section 7.3.2), the data providers report the prices of their data honestly to the data consumers in accordance with the published $f$. In the example illustrated by Figure 7.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 the deal with the value of their $\epsilon$ they would use to obfuscate their data and the total price they would receive in compensation. In the example in Figure 7.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 how determining the amount of needed information are also important topics, but they are out of the scope of the work pursued in this chapter.

<footnote n="1">¹The $\epsilon$ unit price can be of any form including but not limited to being financial. The method we propose is independent of the nature of the price, so we do not need to specify it.</footnote>
<figure><img src="image_50.png" /><figcaption>**Figure 7.2:** An example of a monotonically decreasing function $f(z)$. Let $c$ be a parameter representing the “reported value-to-admitted $\varepsilon$ value” ratio. For $z \ge 0$, we set $f(z)$ as $f(z) = \ln(e - cz)$ if $(e - cz) \le 1$, and $f(x) = 0$ otherwise.</figcaption></figure>

### 7.3.2 Truthful price report mechanism

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 that the true privacy price of each data provider is personal information that only the provider herself knows and is not obliged to disclose. To mitigate this problem, we propose a truthful price report mechanism to ensure that the data providers report their $\varepsilon$ unit prices honestly. The purpose of the mechanism is to provide incentives 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 $\varepsilon$ to purchase using $f(p_i)$, where $f$ is the $\varepsilon$-allocating function introduced in Section 7.3.1. We recall that $f$ is a monotonically decreasing function chosen by the data consumer. We assume that the domain of $f$ (i.e., the $\varepsilon$ unit price) 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 $\varepsilon$ 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 it convenient for the data provider to report the true price (we assume that the data provider knows $f$ and the strategy of the consumer in advance). It is worth noting that the incentive should be finite and, hence, the contribution of $f(z)$ should vanish as $z$ goes to $\infty$. An example of such a function is illustrated in Figure 7.2.

**DEFINITION 7.3.1 (Payment offer).** The data consumer sets the offer $\mu(p_i)$ to the provider $u_i$ as follows:

$$ \mu(p_i) = p_i f(p_i) + \int_{p_i}^{\infty} f(z) dz $$

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 $\varepsilon$ unit price and the amount to be sold, namely $\pi_i f(p_i)$.

**DEFINITION 7.3.2 (Utility of the data provider).** The utility $\rho(p_i)$, of the provider $u_i$, for the reported price $p_i$, is defined as:

$$\rho(p_i) = \mu(p_i) - \pi_i f(p_i)$$

We are now going to show that the 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) \ge \rho(p_i)$ for any $p_i \in \mathbb{R}^+$ and equality is achieved when $p_i = \pi_i$, 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 formally derive the required results via Lemmas (see also Figure 7.3 to get the intuition of the proof):

<figure><img src="image_51.png" /><figcaption>**Figure 7.3:** Graphical illustration of Theorem 7.3. We prove that $\rho(\pi_i)$ (blue hatching area) is always larger than $\rho(p_i)$ (blue rectangle area+red hatching area–green rectangle area).</figcaption></figure>

**LEMMA 7.1.** If $u_i$ reports a price greater than her true price, i.e., $p_i \ge \pi_i$, then her utility will be less than the utility for the true price, i.e., $\rho(p_i) \le \rho(\pi_i)$.

*Proof.* In Appendix G □

**LEMMA 7.2.** If $u_i$ reports a price smaller than her true price, i.e., $p_i \le \pi_i$, then her utility will be less than the utility for the true price, i.e., $\rho(p_i) \le \rho(\pi_i)$.

*Proof.* In Appendix G □

Combining Lemma 7.1 and Lemma 7.2 gives the announced result. We assume that each data producer is a rational individual, i.e., capable of identifying the best strategy to maximize her utility.

**THEOREM 7.3.** If every data producer acts rationally, then the proposed incentive mechanism guarantees the truthfulness of the system.
*Proof.* Immediate from Lemma 7.1 and Lemma 7.2. □

### 7.3.3 Optimizing the incentive mechanism

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

(a) **Maximum Information:** Maximize the total information gain of the data consumer with a fixed budget.

(b) **Maximum Profit:** Maximize the total profit of the data consumer with a fixed budget<fnref n="2" />.

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

**DEFINITION 7.3.3 (Total information).** The total information $I(u)$ obtained by the data consumer by concluding trades with each of the data providers of the tuple $u = (u_1, \dots, u_n)$ is given as $I(u) = \sum_{i=1}^n f(p_i)$.

As for the profit, we can reasonably assume it 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 (a.k.a. *payoff*) obtained by re-selling or processing the data and the price paid to the data providers to gather them.

**DEFINITION 7.3.4 (Payoff and profit).** The payoff function for the data consumer, denoted by $\tau(\cdot)$, is the benefit that the data consumer receives by processing or selling the information gathered from the different data providers. The argument of $\tau(\cdot)$ is $\varepsilon$ representing the amount of information received. We assume $\tau(\varepsilon)$ to be monotonically increasing with $\varepsilon$.

The total profit for the data consumer is given by $\sum_{i=1}^n (\tau(\varepsilon_i) - \mu(\varepsilon_i))$, where $\varepsilon_i = f(p_i)$, i.e., the $\varepsilon$-value allocated to $u_i$.

We shall consider a family of functions $F$, parameterized by $c$, to which the $\varepsilon$-allocating function $f$ belongs. The parameter $c$ reflects the data consumer's willingness to collect the information and, for technical reasons, we assume $f$ to be continuous, differentiable, and concave w.r.t. $c$. 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 (7.2) which the data consumer should adhere to for compensating for the information obtained from that data provider.

As described in previous sections, the $\varepsilon$-allocating functions should be monotonically decreasing with the $\varepsilon$ 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 7.3, that the

<footnote n="2">²Budget here refers to the budget of the data consumer to pay the data providers.</footnote>
prices reported by the data producers will be their true prices. Hence, we have:

$\mathcal{F} \subseteq \{f: f(c, p) \text{ is continuous, differentiable, and concave on } c, \text{ and decreasing with } p\} \quad (7.1)$

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

**EXAMPLE 7.3.1.** An example of such class $\mathcal{F}$ is that of Figure 7.2:

$$ \mathcal{F} = \{\ln(e - cp) : c \in \mathbb{R}^{+}\}. $$

**EXAMPLE 7.3.2.** Another example is:

$$ \mathcal{F} = \{1 - cp : c \in \mathbb{R}^{+}\}. $$

After the prices $p_1, \dots, p_n$ have been reported by the data producers $u_1, \dots, u_n$, the data consumer will try to choose an optimal $c$ maximizing her profit. Figure 7.4 illustrates an example showing one data provider's incentive graph and the payoff for the data consumer. We shall analyse the possibility to choose an optimal $c$, that, in turn, leads to an optimal $f(c, \cdot)$ addressing scenarios (a) and (b).

<figure><img src="image_52.png" /><figcaption>**Figure 7.4:** Illustrating the payoff for $c$ and the incentive plot for the data consumer involving one data provider reporting $p_1$. The Y-intercept of $\mu$ is $\int_{p_1}^{\infty} f(z)dz$.</figcaption></figure>

To fit into the context of DP, we assume that $\tau$ (the data consumer's payoff function) is additive, i.e.,

$$ \tau(a + b) = \tau(a) + \tau(b) \quad \text{for every } a, b \in \mathbb{R}^{+}. \quad (7.2) $$

This is a reasonable assumption that goes well along with the sequential compositionality property of DP, at least for small values of $\varepsilon^3$. We start by showing that the two desiderata (a) and (b) are equivalent:

<footnote n="3">³From a technical point of view, the additive property holds also for large values of $\varepsilon$. However, from a practical point of view, for large values of $\varepsilon$, 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 $\varepsilon$ units to achieve 400 $\varepsilon$ units.</footnote>
**THEOREM 7.4.** If $\tau(\cdot)$ is additive, then maximizing information and maximizing profit (desiderata (a) and (b)) are equivalent, in the sense that a $\varepsilon$-allocating function $f(\cdot, \cdot)$ that maximizes the one, maximizes also the other.

*Proof.* In Appendix G.

**COROLLARY 7.5.** If $\tau(\cdot)$ is additive, then the optimal choice of $f(\cdot, \cdot)$ w.r.t. the selected family of functions will maximize both the information gain and the profit for the data consumer.

*Proof.* Immediate from Theorem 7.4. □

We now consider the complexity problem for finding the optimal $f(\cdot, \cdot)$. Due to the assumptions made in Equation 7.1, and to the additivity of $\tau$, we can apply the method of the Lagrangians to find such $f(\cdot, \cdot)$ (cf. Appendix G).

**THEOREM 7.6.** If $\tau$ is additive, then there exists a $c$ that gives an optimal **profit-maximizing** function $f(c, \cdot) \in \mathcal{F}$, for a fixed budget, and we can derive such $c$ via the method of the Lagrangians.

*Proof.* In Appendix G. □

**THEOREM 7.7.** There exists a $c$ that gives an optimal **information-maximizing** function $f(c, \cdot) \in \mathcal{F}$, for a fixed budget, and we can derive such $c$ via the method of the Lagrangians.

*Proof.* In Appendix G.

To demonstrate how the method works, we show how to compute the specific values of $c$ on the two classes $\mathcal{F}$ of Examples 7.3.1 and 7.3.2. Such $c$ gives the optimal $\varepsilon$-allocating function $f(c, \cdot)$, maximizing $I(u)$ for a given budget. The derivations are described in detail in Appendix H. In each example, $p_i$ is the reported $\varepsilon$ unit price of $u_i$.

**EXAMPLE 7.3.3.** Let $\mathcal{F} = \{\ln(e - cp) : c \in \mathbb{R}^+\}$. The optimal parameter $c$ is the solution of the equation $\ln\left(\prod_{i=1}^{n} e^{p_i}(e - cp_i)^{\frac{e}{c}}\right) = B + \frac{n(e-1)}{c}$.

**EXAMPLE 7.3.4.** Let $\mathcal{F} = \{1 - cp : c \in \mathbb{R}^+\}$. The optimal parameter $c$ is the solution of the equation $c^2 \sum_{i=1}^{n} p_i^2 + 2Bc - n = 0$.

### 7.3.4 Discussion

In our model, for the scenario that we have considered so far, the parameter $c$ is determined by the number of providers and the budget. We observe that in both Examples 7.3.3 and 7.3.4, if $n$ increases then $c$ increases, and vice versa. This seems natural because in the families of both these examples $c$ the incentive that the consumer is going to propose decreases monotonically
with $c$. This means that the larger the offer, the smaller 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 provider can choose to whom to sell her 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 following 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.

### 7.3.5 Optimized privacy budget splitting mechanism for data providers

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, \dots, D_m$ seeking to obtain data from the user $u$. By truthful price report mechanism, as discussed in Section 7.3.2, $u$ reports her true price to $D_i$ for every $i \in \{1, \dots, m\}$. As discussed in Section 7.3.3, $D_i$ computes her optimal $\varepsilon$-allocating function $f_i$ and requests data from $u$, differentially privatized with $\varepsilon = f_i(\pi)$. After receiving $f_1, \dots, f_m$, $u$ would like to provide her data in such a way that maximizes the utility received after sharing her data. Note that, under the assumption that the data consumers collude with each other, the privacy landscape of this setting is equivalent to that of the data provider dealing with one data consumer over $m$ rounds.

**DEFINITION 7.3.5.** We say that the data provider has made a *deal* with the data consumer $D_i$ if, upon reporting the true per-unit price of her information, $\pi$, she agrees to share her data privatized with privacy parameter $\varepsilon = f_i(\pi)$.

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 $\varepsilon_{\text{total}}$, which she would not exceed at any price. Let $S = \{i_1, \dots, i_k\}$ be an arbitrary subset $\{1, \dots, m\}$. By the sequential composition property of DP, the final privacy budget exhausted by $u$ by sharing her data with an arbitrary set of data consumers $D_{i_1}, \dots, D_{i_k}$ (or, equivalently, to one data consumer in rounds $i_1, \dots, i_k$) is $\varepsilon_S = \sum_{j \in S} f_j(\pi)$. $u$'s main intention is to share her data in such a way that ensures $\varepsilon_S \le \varepsilon_{\text{total}}$ for all subset $S$ of $\{1, \dots, 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}, \dots, D_{i_k}\}$ where $S^* = \{i_1, \dots, i_k\} \subseteq \{1, \dots, m\}$, chosen as

$$S^* = \underset{S}{\operatorname{argmax}} \left\{ \sum_{j \in S} \rho(\pi, f_j) \middle| S \subseteq \{1, \dots, m\}, \sum_{j \in S} f_j(\pi) \le \varepsilon_{\text{total}} \right\} \quad (7.3)$$
We show the pseudocode for the $\varepsilon$ allocation algorithm and the entire process in Algorithms 1 and 2.

<caption>**Algorithm 8:** Optimized privacy budget splitting algorithm</caption>

**Input:** {$\varepsilon_1, \dots, \varepsilon_n$} stored in array $w$, {$p_1, \dots, p_n$} stored in array $v$, $\varepsilon_{\text{total}}$;
**Output:** List of data consumer {$D_1 \dots D_k$} that is selected to sell data;
**initiate:** Two-dimension array $m$;
**while** $i \le n$ **do**
    **while** $j \le \varepsilon_{\text{total}}$ **do**
        **if** $w[i] > \varepsilon_{\text{total}}$ **then**
            $m[i, j] := m[i-1, j]$
        **else**
            $m[i, j] := \max(m[i-1, j], m[i-1, j-w[i]] + v[i])$
    **end**
**end**
**backtrack** using the final solution $m$ and find the index of the data consumer;
**return** List of selected data consumer;

<caption>**Algorithm 9:** The proposed data trading process</caption>

**Input:** the data provider {$u_1, \dots, u_n$}, the data consumer {$D_1, \dots, D_m$};
**Output:** List of the data provider and consumer pair that trade is completed;
**while** $i \le m$ **do**
    $D_i$ calculate the parameter $c$ to optimize the $f_i(\cdot)$;
    $D_i$ inform the $f_i(\cdot)$ to the data provider
**while** $j \le n$ **do**
    $u_j$ report price $p_j$ to the data consumer
**while** $i \le m$ **do**
    **while** $j \le n$ **do**
        $D_i$ calculate the $\varepsilon_j$ based on $p_j$;
        $D_i$ inform the $\varepsilon_j$ to the $u_j$
**while** $j \le n$ **do**
    $u_j$ perform the Optimized $\varepsilon$ allocation algorithm to maximize the utility

## 7.4 Experimental results

In this section, we highlight the results of some experiments we perform to verify that the proposed optimization method can find the best profit for the data consumer. For the experiments, we consider the families $\mathcal{F}$ of Examples 7.3.3 and 7.3.4, namely $\mathcal{F} = \{\ln(e - cp) : c \in \mathbb{R}^+\}$ and $\mathcal{F} = \{1 - cp : c \in \mathbb{R}^+\}$. For these two families, the corresponding optimal parameter $c$ is formally derived in Appendix H.

The experimental variables are set as follows: we assume that there are 10 data consumers and the total number of data providers $n$ is set from 1000 to 2000 at an interval of 500. The data provider's $\varepsilon$ unit price is distributed as per $\mathcal{N}(1, 1)$ and, to align with the scaling, we map
the values of the $ε$ unit price less than 0 and more than 2 to 0 and 2, respectively. We set the unit value $ε$ to 0.1 and the maximum value of $ε$ of the data providers to 3. We consider the budget of the data consumer to be 60, 90, and 120 dealing 1,000, 1,500, and 2,000 data providers, respectively. We assumed that the data consumer earned a profit of 10 per 0.1 epsilon and assigned the parameter $c$ from 1 to 10 for comparison.

<figure><img src="image_53.png" /><figcaption>**Figure 7.5:** Experimental result of profit under a fixed budget. The log function represents the family $ln(e - cp)$ and the linear function represents the family $1 - cp$. We let the parameter $c$ range from 0 to 1. The red bin represents the optimal value of $c$, namely the $c$ that gives maximum information.</figcaption></figure>

The results are shown in Fig. 7.5. For instance, in the case of the log family $ln(e - cp)$, the optimal parameter $c$ is 5.36, and in the case of the linear family $1 - cp$, the optimal parameter $c$ is 4.9. It is easy to verify that the optimal values of $c$ correspond to those determined by solving Equations (H.2) and (H.3) for Example 7.3.3 and Equations (H.9) and (H.10) for Example 7.3.4 given in Appendix H.
8

# Establishing the price of privacy in federated data trading

## 8.1 Introduction

With the emerging trend of data markets (e.g., Data coup [195], Liveen [194], etc.) incorpo- rating DP [13, 14] for trading private data from clients in exchange for compensation in order to obtain high-quality analytics, as studied in Chapter 7, we envision a data trading framework in which groups of data providers ally to form federations in order to increase their bargaining power following the traditional model of trade unions. At the same time, federations guarantee that the members respect their engagement concerning the trade. Another important aspect of such federations is that the value of the collection of all data is usually different from the sum of the values of all members’ data. It could be larger, for instance, because the accuracy of the statistical analyses increases with the size of the dataset, or could be smaller, for instance, because of some discount offered by the federation. Data consumers are supposed to make a collective deal with a federation rather than with individual data providers, and, from their per- spective, this approach can be more reliable and efficient than dealing with individuals. Thus, data trading through federations can benefit both parties. Given such a scenario, the two crucial questions that arise which we address in this work are: (a) how to determine the price of the collective data according to the privacy preferences of each member, and (b) how to determine the individuals’ contribution to the overall value obtained from the collectively reported data in order to establish a fair distribution of the earnings within the federations.
## Contributions

The key contributions of this chapter are:

1. We propose a method to determine the price of collective differentially private data in a federated data trading environment.

2. We propose a distribution model based on game theory. More precisely, we use the notion of Shapley values from the theory of cooperative games to determine the contribution of each participant of a federation in the collective earnings and use it to ensure that each member of the federation receives fair compensation according to their contribution.

## 8.2 Related Work

As discussed in Chapter 7, data markets such as Datacoup [195] and Liveen [194] need to guarantee satisfactory privacy protection in order to encourage the data owners to participate. On this note, one of the key questions explored by the community is how to appropriately price data obfuscated by a privacy-preserving mechanism. In the context of DP, as the accuracy of data typically depends on the value of the noise parameter $\varepsilon$, this question is linked to the problem of how to establish the value of $\varepsilon$. Researchers have debated how to choose this value since the introduction of DP and there have been several proposals along this line [220–223]. In particular, [221] showed that the privacy protection level by an arbitrary $\varepsilon$ can be infringed by inference attacks, and it proposed a method for setting $\varepsilon$ based on the posterior belief. [222] considered the relation between DP and t-closeness, a notion of group privacy which prescribes that the earth movers distance between the distribution in any group $E$ and the distribution in the whole dataset does not exceed the threshold $t$, and showed that both $\varepsilon$-DP and $t$-closeness are satisfied when the $t = \max_E \frac{|E|}{N} \left( 1 + \frac{N-|E|-1}{|E|} e^\varepsilon \right)$ where $N$ is the number of records of the database.

Several other works have studied how to price the data according to the value of $\varepsilon$ [224–231]. The primary focus of such studies is to determine the price and value of the $\varepsilon$ according to the data consumer's budget, the accuracy requirement of the subsequent analytics, the privacy preference of the data providers, and the relevance of the data. In particular, the study in [230] assumed a dynamic data market and proposed an incentive mechanism for data owners to truthfully report their privacy preferences. In [228], the authors proposed a framework to find the balance between financial incentive and privacy in personal data markets where data owners sell their own data and suggested the main principles to achieve reasonable data trading. Ghosh and Roth [225] proposed a pricing mechanism based on auctions that maximizes the data accuracy under a budget constraint or minimizes the budget for the fixed data accuracy requirement under DP guarantees.

Our study differs from previous work in that, unlike the existing approaches assuming a one-to-one data trading between data consumers and providers, we consider an environment involving a data consumer and a federation of data providers.
## 8.3 Technical Preliminaries

In this work, we assume the local model of DP (i.e., each data provider obfuscates their own data locally to foster DP guarantees). When the domain of data points is finite, one of the simplest and most widely used mechanisms for LDP is k-Randomized Response (k-RR) [32]. In this work, we assume a setting where all data providers use the k-RR mechanism to locally obfuscate their data.

**DEFINITION 8.3.1 (k-Randomized Response [32]).** Let $\mathcal{X}$ be the domain of secrets of size $k < \infty$. For a given LDP parameter $\varepsilon$ and given an input $x \in \mathcal{X}$, the k-Randomized Response (k-RR) mechanism returns $y \in \mathcal{X}$ with probability

$$ \mathbb{P}[y|x] = \frac{1}{k-1+e^{\varepsilon}} \begin{cases} e^{\varepsilon} & \text{if } y=x \\ 1 & \text{otherwise} \end{cases} $$

### 8.3.1 Shapley value

When participating in data trading through a federation, *Pareto efficiency* and *symmetry* are the important properties for the intra-federation earning distribution. Pareto efficiency means that at the end of the distribution process, no change can be made without making participants worse off. Symmetry means that all players who make the same contribution must receive the same share. Obviously, the share should vary according to the member's contribution to the collective data.

Shapley value [232, 233] is a concept from game theory named in honour of Lloyd Shapley who introduced it. Shapley value, typically applied in cooperative games, introduces a method to distribute the total gain that satisfies Pareto efficiency, symmetry, and differential distribution according to a player's contribution. Thus, all participants have the advantage of being fairly incentivized. The solution based on the Shapley value is unique. Due to these properties, the Shapley value is regarded as a cutting-edge approach for designing a fair incentive distribution method based on individual contributions.

Let $N = \{1, \dots, n\}$ be a set of players involved in a cooperative game and $M \in \mathbb{R}^+$ be a financial revenue received (e.g., from the data consumer). Let $v: 2^N \to \mathbb{R}^+$ be the characteristic function, mapping each subset $S \subseteq N$ to the total expected sum of payoffs the members of $S$ can obtain by cooperation. (i.e., $v(S)$ is the total collective payoff of the players in $S$). According to the Shapley value, the benefit received by player $i$ in the cooperative game is given as follows:

$$ \psi_i(v, M) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S)) $$

We observe that $v(A) > v(B)$ for any subsets $B \subset A \subseteq N$, and hence, $v(S \cup \{i\}) - v(S)$ is positive. We call this quantity the marginal contribution of player $i$ in a given subset $S$. Note that $\psi_i(v, M)$ is the expected marginal contribution of player $i$ over all subsets $S \subseteq N$.
In this work, we use the Shapley value to distribute the earnings according to the contributions of the data providers in the federations.

# 8.4 Differentially Private Data Trading Mechanism

## 8.4.1 Mechanism outline

**Overview:** We focus on an environment with multiple federations of data providers and one data consumer who interacts with the federations in order to obtain the data (differentially privatized with varying values of $\epsilon$) in exchange for financial revenues. We assume that federations and the data consumer are aware that the data providers independently use the k-RR mechanism to obfuscate their sensitive information with their desired levels of privacy (which can differ from provider to provider). Our method provides a sensible way of splitting the earnings of a federation using the Shapley value. In addition, it also motivates an individual to cooperate with the federation they are a part of and penalises intentional and recurring non-cooperation.

**Notations and set-up:** Let $\mathcal{F} = \{F_1, \dots, F_k\}$ be a set of k federations of data providers, where each federation $F_i$ has $n_{F_i}$ members for each $i \in \{1, \dots, k\}$. For a federation $F \in \mathcal{F}$, let its members be denoted by $F = \{p_1^F, \dots, p_{n_F}^F\}$. And finally, for every federation $F$, let $p_*^F \in F$ be an elected representative of $F$ interacting with the data consumer. This approach to communication benefits both the data consumer and the data providers because (a) the data consumer minimizes her communication cost by interacting with just one representative of the federation, and (b) the reduced communication induces an additional layer of privacy.

We assume that each member $p$ of a federation, $F$ has a maximum privacy threshold $\epsilon_p^T$ with which she, independently, obfuscates her data using the k-RR mechanism. We also assume that $p$ has $d_p$ data points to potentially report.

We know from Equation (8) of [234] that if there are $m$ data providers reporting $d_1, \dots, d_m$ data points, independently privatizing them using k-RR mechanism with the privacy parameters $\epsilon_1, \dots, \epsilon_m$, the federated data of all the $m$ providers also follow a k-RR mechanism with the privacy parameter being:

$$ \epsilon = \ln \left( \frac{\sum_{i=1}^{m} d_i}{\sum_{i=1}^{m} \frac{d_i}{k-1+e^{\epsilon_i}}} + 1 - k \right). $$

We call the quantity $d_p \epsilon_p^T$ the information limit of data provider $p \in F$, and

$$ \epsilon_F^T = \ln \left( \frac{\sum_{p \in F} d_p}{\sum_{p \in F} \frac{d_p}{k-1+e^{\epsilon_p^T}}} + 1 - k \right) \quad (8.1) $$

the maximum information threshold of the federation $F$.

We now introduce the concept of a valuation function $f$ mapping financial revenues to information, representing the amount of information to be obtained for a given price. It is reasonable
to have $f$ as strictly monotonically increasing and continuous. In this work, we shall focus on the effect of the privacy parameter $\varepsilon$ and, hence, we shall regard the number of data points to be reported by each data provider as a constant and let only $\varepsilon$ can vary. We shall call $f$ the privacy valuation function.

As $f$ is strictly monotonically increasing and continuous, it is also invertible. Hence, $f^{-1}$ maps a certain privacy parameter $\varepsilon$ to the financial revenue evaluated with selling data privatized using $k$-RR with $\varepsilon$ as the parameter. Noting that $f$ essentially determines the privacy parameter of a DP mechanism ($k$-RR, in this case), it is reasonable to assume that $f$ should be not only increasing but also increasing exponentially for a linear increase of money. In fact, when $\varepsilon$ is high, it hardly makes any difference to further increase its value. For example, when $\varepsilon$ increases from 200 to 250, it practically makes no difference to the data as they were already non-private with $\varepsilon = 200$. On the other hand, if we increase $\varepsilon$ from 0 to 50, it creates a huge difference, conveying much more information. Therefore, it makes sense to set $f$ to increase exponentially with a linear increase of the financial revenue.

$f(M) = K_1(e^{K_2M} - 1)$ is an example of a privacy valuation function that we consider which takes the financial revenue $M \in \mathbb{R}^+$ as its argument, satisfying the reasonable assumptions of evaluating the DP parameter that should be used to privatize the data in exchange of the financial revenue of $M$. Here the scaling factors $K_1 \in \mathbb{R}^+$ and $K_2 \in \mathbb{R}^+$ are decided by the data consumer according to her requirements.

<figure><img src="image_54.png" /><figcaption>**Figure 8.1:** Some examples of the privacy valuation function $f$ illustrated with different values of $K_1$ and $K_2$. The data consumer decides the values of the scaling factors $K_1$ and $K_2$ according to her requirement and broadcasts the determined function to the federations.</figcaption></figure>

**Finalizing and achieving the deal:** Before the data trading commences, the data consumer, $D$, truthfully broadcasts her financial budget, $B$, and a privacy-valuation function, $f$, to all the federations. At this stage, each federation computes its maximum privacy threshold. In particular, for a federation $F$ with members $F = \{p_1, \dots, p_n\}$, and a representative $p_*, p_i$ reports $d_{p_i}$ and $\varepsilon_{p_i}^T$ to $p_*$ for all $i \in \{1, \dots, n\}$. $p_*$ computes the maximum information threshold of federation $F$, $\varepsilon_F^T$, as given by (8.1). Hence, $p_*$ places a bid to $D$ to obtain $\$M$, which maximises the earning for $F$ under the constraint of their maximum privacy threshold and the maximum
budget available from D, i.e., $p_*$ wishes to maximize $M$ within the limits $M \le B$ and $f(M) \le \varepsilon_F^T$. Thus, $p_*$ bids for sending data privatized using the $k$-RR mechanism with $\varepsilon_F^T$ in exchange of $f^{-1}(\varepsilon_F^T)$.

At the end of this bidding process by all the federations, $D$ ends up with $\varepsilon = \{\varepsilon_{F_1}^T, \dots, \varepsilon_{F_k}^T\}$, the maximum privacy thresholds of all the federations. $D$ must ensure that $\sum_{i=1}^k f^{-1}(\varepsilon_{F_i}^T) \le B$, adhering to her financial budget. In all probability, $\sum_{i=1}^k f^{-1}(\varepsilon_{F_i}^T)$ is likely to exceed $B$ in a pragmatic setup. $D$ needs a way to finalize the deal with the federations staying within her financial budget while maximizing her information gain, i.e., maximizing $\sum_{i=1}^k d_{F_i} \varepsilon_{F_i}$, where $d_{F_i}$ is the total number of data points obtained from the $i^{th}$ federation $F_i$, and $\varepsilon_{F_i}$ is the overall privacy parameter of the $k$-RR differential privacy with the combined data of all the members of $F_i$.

A way $D$ could close the deal with the federations is by proposing to receive information obfuscated with $w^* \varepsilon_{F_i}^T$ using $k$-RR mechanism to $F_i \forall i \in \{1, \dots, k\}$, where

$$w^* = \operatorname*{argmax}\left\{\sum_{i \in \{1, \dots, k\}} f^{-1}(w \varepsilon_{F_i}^T) \le B, w \in [0, 1]\right\}, \quad (8.2)$$

i.e., proportional to every federation's maximum privacy threshold ensuring that the price to be paid to the federations is within $D$'s budget. Note that $w \in [0, 1]$ guarantees that $w \varepsilon_F^T \le \varepsilon_F^T$ for every federation $F$, making the proposed privacy parameter possible to achieve by every federation as it is within their respective maximum privacy thresholds. Let the combined privacy parameter for federation $F_i$ proposed by $D$ to successfully complete the deal be denoted by $\varepsilon_{F_i}^P = w^* \varepsilon_{F_i}^T \forall i \in \{1, \dots, k\}$. We call this $\varepsilon_{F_i}^P$ to be the *promised* level of privacy to be achieved by each federation to participate in the data market.

The above method to scale down the maximum privacy parameters to propose a deal maximizing $D$'s information gain is just one of the possible approaches. In theory, any method that ensures the total price to be paid to all the federations in exchange for their data is within $D$'s budget and the privacy parameters proposed are within the corresponding privacy budgets of the federations could be implemented to furnish a revised set of privacy parameters and, in turn, the price associated with them. When all the federations are informed about the revised privacy parameters desired of them and they agree to proceed with the private-data trading with the data consumer by achieving the revised privacy parameter by combining the data of their members, we say the *deal has been sealed* between the federations and the data consumer.

Once the deal is sealed between the federations and the data consumer, $F_i$ is expected to provide data gathered from its members with an overall obfuscation with the privacy parameter $\varepsilon_{F_i}^P$ using the $k$-RR mechanism, in exchange for a price $M^i = f^{-1}(\varepsilon_{F_i}^P)$ for every $i \in \{1, \dots, k\}$. Failing to achieve this parameter of privacy for any federation results in a failure to uphold the conditions of the *deal* and makes the *deal* void for that federation, with no price received.

A rational assumption made here is that if a certain federation $F$ fails to gather data from its members such that the overall $k$-RR privacy parameter of $F$ is less than $\varepsilon_F^P$, then $F$ doesn't receive any partial compensation for its contribution, as it would incur an increase in communication
cost and time for the data consumer in proceeding to this stage and seal a new deal with F, instead of investing the revenue to a more responsible federation.

The rest of the process consists in collecting the data and it takes place within every federation F which has sealed the deal with the consumer. At the $t^{th}$ round, for $t \in \{1, 2, \dots\}$, any member p of F has the freedom of contributing $d_p^t \le d_p - \sum_{i=1}^{t-1} d_p^i$ data points privatized using k-RR mechanism with any parameter $\varepsilon_p^t$. The process continues until the overall information collected achieves a privacy level of at least $\varepsilon_F^P$. Let $\mathcal{T}$ denote the number of rounds needed by F to achieve the required privacy level. As per the deal sealed between F and D, F needs to submit $D_F = \sum_{p \in F} \sum_{i=1}^{\mathcal{T}} d_p^i$ data points to D such that the overall k-RR privacy level of the collated data, $\varepsilon_F$, is at least $\varepsilon_F^P$, and in return F receives a financial revenue of M from D.

### 8.4.2 Earning Splitting

We use the Shapley value to estimate the contribution of each data provider of the federation, in order to split the whole earning M which F would receive from D at the end of the trade. Let $\psi: \mathbb{R}^+ \times \mathbb{R}^+ \to \mathbb{R}^+$ be the valuation function used for evaluating the Shapley values of the members after each contribution. If a certain member, p, of F reports d differentially private data points with privacy parameter $\varepsilon$, $\psi_i(v)$ should give the share of contribution made by p over the total budget, M, of F, to be split across all its members. It is assumed that each member, p, of F computes her Shapley value, knows what share of revenue she would receive by contributing her data privatized with a chosen privacy parameter, and uses this knowledge to decide on $\varepsilon_p^t$ at every round t, depending on her financial desire. In our model, characteristic function $v(S)$ is as follows:

$$v(S) = \begin{cases} M, & \text{if } \varepsilon_F \ge \varepsilon_F^P \\ 0, & \text{if } \varepsilon_F < \varepsilon_F^P \end{cases}$$

where n is the number of data provider in subset S.

**EXAMPLE 8.4.1.** As an example, let us assume that there are $p_1, p_2, p_3$, and each provider's contribution $\sum_{t=1}^{\mathcal{T}} d_p^t \frac{e^{\varepsilon_p^t}}{k-1+e^{\varepsilon_p^t}}$ are 1.0, 0.5 and 0.3. And we assume that $\varepsilon_F^P$ is 1.4 and financial revenue of M is 60. In this case, the calculation of each provider's revenue using Shapley value is as follows:

Case 1) Only one data provider participates:

$$p_1: v(p_1) = 0$$

$$p_2: v(p_2) = 0$$

$$p_3: v(p_3) = 0$$

Case 2) Two providers participate: $v(p_1+)=0, v(p_2)=0$,

$$p_1: v(p_1 + p_2) - v(p_2) = M, v(p_1 + p_3) - v(p_3) = M$$

$$p_2: v(p_1 + p_2) - v(p_1) = M, v(p_2 + p_3) - v(p_3) = 0$$

$$p_3: v(p_1 + p_3) - v(p_1) = 0, v(p_2 + p_3) - v(p_2) = 0$$
Case 3) All providers participate:

$$p_1 : v(p_1 + p_2 + p_3) - v(p_2 + p_3) = M$$

$$p_2 : v(p_1 + p_2 + p_3) - v(p_1 + p_3) = M$$

$$p_3 : v(p_1 + p_2 + p_3) - v(p_1 + p_2) = 0$$

According to the above results, the share of each user, according to their Shapley values, is as follows:

$$\psi_1(v) = \frac{0!2!}{3!}0 + \frac{1!1!}{3!}M + \frac{1!1!}{3!}M + \frac{2!0!}{3!}M = \frac{4M}{6} = 40$$

$$\psi_2(v) = \frac{0!2!}{3!}0 + \frac{1!1!}{3!}M + \frac{1!1!}{3!}0 + \frac{2!0!}{3!}M = \frac{2M}{6} = 20$$

$$\psi_3(v) = \frac{0!2!}{3!}0 + \frac{1!1!}{3!}0 + \frac{1!1!}{3!}0 + \frac{2!0!}{3!}0 = \frac{0M}{6} = 0$$

In this example, $p_3$ has no effect on achieving the $\varepsilon_F^P$. Thus, $p_3$ is excluded from the revenue distribution. If the revenue were distributed proportionally, without considering the Shapley values, the revenue of $p_1$ would be 33, $p_2$ is 17, and $p_3$ is 10. It would mean $p_1$ and $p_2$ would receive lower revenues even though their contribution are sufficient to achieve the $\varepsilon_F^P$, irrespective of the participation of $p_3$. The Shapley value enables the distribution of revenues only for those who have contributed to achieving the goal.

One of the problems of computing the Shapley values is the high computational complexity involved. If there is a large number of players, i.e., the size of a federation is large, the total number of subsets to be considered becomes considerably large, engendering a limitation to real-world applications. To overcome this, we use a *pruning technique* to reduce the computational complexity of the mechanism. A given federation *F* receives revenue *M* only when $\varepsilon_F \ge \varepsilon_F^P$, as per the deal sealed with the data consumer. Therefore, it is not necessary to calculate for Shapley values for the cases where $\varepsilon_F < \varepsilon_F^P$, since such cases do not contribute towards the overall Shapley value evaluated for the members of *F*.

The data trading between the data consumer and the federations would typically continue periodically for a length of time. For example, Acxiom, a data broker company, periodically collects and manages personal data related to daily life, such as consumption patterns and occupations. Periodic data collection has a higher value than one-time data collection because it can track temporal trends. For simplicity of explanation, let us assume that the trading occurs every year. Hence, we consider a yearly period to illustrate the final two steps of our proposed mechanism – *swift data collection* and the *penalty scheme*. This would ensure that the data collection process is as quick as possible for every federation every year. Additionally, this would motivate the members to cooperate and act in the best interests of their respective federations by not, unnecessarily, withholding their privacy contributions to hinder achieving the privacy goals of their group, as per the deal finalized with *D*.

Let $R \in \mathbb{N}$ be the *tolerance period*. For a member $p \in F$, we denote $d(m)_p^i$ to be the number of data points reported by $p$ in the $i^{th}$ round of data collection of year $m$ and we denote $\varepsilon(m)_p^i$ to be the corresponding privacy parameter used by $p$ to obfuscate the data points. Let $T_m$ be the number of rounds of data collection needed in year $m$ by federation *F* to achieve their privacy
goal. We denote the total number of data points reported by $p$ in the year $m$ by $d(m)_p$, and observe that $d(m)_p = \sum_{i=1}^{T_m} d(m)_p^i$. Let $\varepsilon(m)^P$ denote the value of the privacy parameter of the combined $k$-RR mechanism of the collated data that $F$ needs, in order to successfully uphold the condition of the deal sealed with $D$.

**DEFINITION 8.4.1 (Contributed privacy level).** For a given member $p \in F$, we define the contributed privacy level of $p$ in year $m$ as

$$ \varepsilon(m)_p = \sum_{i=1}^{T_m} \varepsilon(m)_p^i $$

**DEFINITION 8.4.2 (Privacy saving).** For a given member $p \in F$, we define the privacy saving of $p$ over a tolerance period $R$ (given by a set of some previous years), decided by the federation $F$, as

$$ \Delta_p = \sum_{m \in R} \left( d(m)_p \varepsilon_p^T - d(m)_p \varepsilon(m)_p \right) $$

**Swift data collection:** It is in the best interest of $F$, and all its members, to reduce the communication cost, time, and resources over the data collection rounds, and achieve the goal of $\varepsilon^P$ as soon as possible, to catalyze the trade with $D$, and receive the financial revenue. We aim to capture this through our mechanism, and enable the members not to “hold back” their data well below their capacity.

To do this, in our model we design the Shapley valuation function, $\psi$, such that for $p \in F$, in year $m$, $\psi(N_p \varepsilon(m))_{p}^{t+1}$, $d(m)_p$, $M) = \psi(\varepsilon(m))_{p}^{t}$, $d(m)_p$, $M)$, where $N_p \in \mathbb{Z}^+$ is the catalyzing parameter of the data collection, decided by the federation, directly proportional to $\Delta_p$. In particular, for $p \in F$, and a tolerance period $R$ decided, in prior, by $F$, it is a reasonable approach to make $N_p \propto \Delta_p$, as this would mean that any member $p \in F$, reporting $d(m)_p$ data points, would need to use $N_p$ times higher value of $\varepsilon$ in the $(t+1)^{st}$ round of data collection in the year $m$, as compared to that in the $t^{th}$ round for the same number of data points reported to get the same share of the benefit of the federation's overall revenue, where $N_p$ is decided by how much privacy savings $p$ has had over a fixed period of $R$.

This is made to ensure that if a member of a federation has been holding back her information by using high values of privacy parameters over a period of time, she should need to compensate in the following year by helping to quicken up the process of data collection of her federation. This should motivate the members of $F$ to report their data with a high value of the privacy parameter in earlier rounds than later, staying within their privacy budgets, so that the number of rounds needed to achieve $\varepsilon(m)^P$ is reduced.

**Penalty scheme:** It is desirable to have every member of any given federation cooperate with the other members of the same federation and facilitate the trading process in the best interest of the federation, to the best of their ability. That is why, in our mechanism, we incorporate an idea of a penalty scheme for the members of a federation who are being selfish by keeping a substantial
gap between their maximum privacy threshold and their contributed privacy level, wishing to enjoy benefits of the revenue at an unfair cost of other members providing information privatized with almost their maximum privacy threshold. To prevent such non-cooperation and attempted “free ride”, we design a penalty scheme in the mechanism.

**DEFINITION 8.4.3 (Free rider).** We call a certain member $p \in F$ to be a free rider if $\Delta_p \ge \delta_F$, for some $\delta_F \in \mathbb{R}^+$. Here, $\delta_F$ is a threshold decided by the federation $F$ beforehand and informed to all the members of $F$.

Thus, in the ideal case, every member of $F$ would have their privacy savings to be 0 if everyone contributed information to the best of their abilities, i.e., provided data obfuscated with their maximum privacy parameter. But to capture a pragmatic scenario as a federation, a threshold amount of privacy savings is tolerated for every member. Under the penalty scheme, if a certain member $p \in F$ qualifies as a free rider, she is excluded from the federation and is given a demerit point by the federation, that can be recorded by a central system keeping track of every member of every federation, preventing $p$ from getting admission to any other federation for her tendency to free ride. This would mean $p$ and has the responsibility of trading with the data consumer by herself. We could define the Shapley valuation function used to determine the share of $p$'s contribution such that $f^{-1}(\varepsilon_p^T) < \psi(v, M)$, implying that the revenue to be received by $p$ dealing directly with $D$, providing one data point obfuscated with her maximum privacy threshold with respect to the privacy valuation function $f$, would be giving a much lower revenue than what $p$ would receive being a member of federation $F$. Imposing the penalty scheme is expected to drive every member of a given federation to be cooperating with the interests of the federation and all the other fellow members to the best of their abilities, preventing potential free riders. Our proposed mechanism is elucidated by Algorithms 10, 11 and 12.

**THEOREM 8.1.** If the privacy valuation function used in order to impose the penalty scheme to any member $p$ of a federation $F$ is $f(m) = K_1(e^{K_2m} - 1)$, the Shapley valuation function $\psi$ chosen must satisfy

$$ \frac{\ln\left(\frac{\varepsilon_p^T}{K_1} + 1\right)}{K_2} < \psi\left(\varepsilon_p^T, \frac{\ln\left(\frac{w^*\varepsilon_p^T}{K_1} + K\right)}{K_2}\right), $$

where $K = \frac{1}{K_1} \sum_{\substack{p' \ne p \\ p' \in F}} d(m)_{p'} \varepsilon_{p'}^T + 1$ and $w^*$ is the scaling parameter as given by (8.2).

*Proof.* In Appendix I. □

## 8.5 Experimental results
**Algorithm 10: Federation based data trading algorithm**

**Input:** Federation F, Data consumer D;
**Output:** $\varepsilon_F^P$ and M;
D broadcasts total budget B and f;
Federation F computes the $\varepsilon_F^T = \sum_{i=1}^n d_{p_i} \varepsilon_{p_i}^T$;
$p_*$ places a bid to D to obtain revenue M;
F and D “seal the deal” to determine the $\varepsilon_F^P$ and M;

while $\varepsilon_F \le \varepsilon_F^P$ and $t \le T$ do

SWIFTDATACOLLECTION(F, $\varepsilon_F^P$);
$p_*$ computes the overall privacy $\varepsilon_F$

if $\varepsilon_F \ge \varepsilon_{F_i}^P$ then

F receives the revenue M;
$p_*$ computes the Shapley value $\psi_i(v, M)$;
$p_i$ get their share of the revenue M

else

deal fails

**Algorithm 11: Swift data collection algorithm**

**Input:** $F = \{p_1, \dots, p_{n_F}\}, \varepsilon_F^P$;

**Output:** $\varepsilon(m)^t$;

**Function** SwiftDataCollection($F, \varepsilon_F^P$):

while $i \le n_F$ do
    Compute $\Delta_{p_i}$;
    Compute the catalyzing parameter $N_{p_i}$;
    Determine the $\varepsilon(m)^{t-1}_{p_i} = N_{p_i} \varepsilon(m)^{t-1}$

In this section, we show the experimental results that illustrate the efficient working of the proposed method in order to obtain the promised $\varepsilon$ and reduce the computation time for Shapley value evaluation. The number of data providers constituting the federation is set to 25, 50, 75, and 100, respectively. The $\varepsilon_p^T$ is sampled independently for each member $p$ following $\mathcal{N}(5, 1)$ and we only consider the values in the range [1, 10]. The hardware environment used for the experiments was an Intel(R) i5-9400H CPU with 16 GB of memory.

### 8.5.1 Number of rounds needed for data collection

Achieving the $\varepsilon_F^P$ is the key to the participation of F in the data market. If $\varepsilon_F^P$ is not achieved as the collated information level for the federation, there is no revenue from the data consumer. Thus, it is important to encourage the data providers to report sufficient data in order to reach

**Algorithm 12: Penalty scheme**

**Input:** $F = \{p_1, \dots, p_{n_F}\}, \Delta_F = \{\Delta_{p_1}, \dots, \Delta_{p_{n_F}}\}, \delta_F$;

**Output:** Updated F;

while $i \le n_F$ do

if $\Delta_{p_i} \ge \delta_F$ then
    $F \setminus \{i\}$
<figure><img src="image_55.png" /><figcaption>**Figure 8.2:** The number of rounds required by a federation (of varying sizes) to achieve the privacy level (i.e., information accuracy) to be reported to the data consumer is less for the catalyzing method introduced in the data collection than its non-catalyzing counterpart.</figcaption></figure>

the goal of the deal sealed with the data consumer. The swift data collection is a way to catalyze the process of obtaining data from the members of every federation *F* minimising the number of rounds of data collection to achieve $\epsilon_F^p$. Furthermore, we set $N_p = \frac{\Delta_p}{d(m)_p \epsilon_F^p}$ for a certain member *p* in federation *F* to motivate the data providers who have larger privacy savings to provide more information per round.

In the experiment, $\epsilon_F^p$ is set to be 125, 250, 375 and 500, respectively. Data provider *p* determines $\epsilon(m)_p^t$ randomly in the first round, and then computes $\epsilon(m)_p^t$ according to $N_p$, for every *p* in the federation. We compare two cases, the catalyzing method and the non-catalyzing method.

As illustrated in Figure 8.2, we see that both catalyzing data collection and its non-catalyzing counterpart achieve the promised epsilon values within 5 rounds of data collection, but it can be seen that the catalyzing method achieves $\epsilon_F^p$ earlier because data providers decide the privacy level used to obfuscate their data with considering their privacy savings resulting in a *swift data collection*.

### 8.5.2 Number of free riders by penalty scheme

The penalty scheme that prevents free riders is based on the premise that trading data by participating in a federation is more beneficial than trading data directly with data consumers (Theorem 8.1). We evaluated the number of free riders in the catalyzing and non-catalyzing methods according to the increase of the threshold $\delta_F$ in the experiment.

Figure 8.3 shows that the number of free riders increases in both techniques as the threshold
<figure><img src="image_56.png" /><figcaption>**Figure 8.3:** The number of free riders incurred by the penalty scheme (for varying sizes of the federation and the tolerance threshold) is significantly less adapting the catalyzing method for data collection than the non-catalyzing method.</figcaption></figure>

value $\delta_F$ is set to 1, 2, and 3. However, the non-catalyzing method allows more free riders than the catalyzing method which changes the accuracy of the reported information according to privacy saving $\Delta_P$. In other words, the catalyzing method and penalty scheme help to keep members in the federation by inducing them to reach the target epsilon quicker and, in turn, enables the method to work efficiently.

### 8.5.3 Reduced Shapley value computation time

<table><caption>**Table 8.1:** Computation time of brute force and proposed pruning method</caption><thead><tr><td># of data providers</td><td>brute force(Sec)</td><td>pruning method (Sec)</td></tr></thead><tbody><tr><td>15</td><td>0.003</td><td>0.0007</td></tr><tr><td>18</td><td>0.02</td><td>0.001</td></tr><tr><td>21</td><td>0.257</td><td>0.0049</td></tr><tr><td>24</td><td>2.313</td><td>0.009</td></tr><tr><td>27</td><td>19.706</td><td>0.019</td></tr></tbody></table>

As mentioned in Section 8.4.2, one of the limitations of Shapley value evaluation is to compute it for all combinations of subsets. Through this experiment, we demonstrate that the proposed pruning technique reduces the computation time for calculating the Shapley values. We compared the computation times of the proposed method with the brute force method that calculates all the cases by increasing the number of data providers in the federation from 15 to 27. Table 8.1 shows that the computation time of Shapley value evaluation increases exponentially because the total number of subsets to be considered does the same. The proposed pruning technique can calculate the Shapley values in less time by removing unnecessary computations.
# 9

## Conclusion and Future Work

In this thesis, we have explored the relationship between privacy and utility from a foundational standpoint. Primarily, we focused on the interaction of differentially private systems and their close variants with the utility of the data providers (often the users of various data-driven services) and the data consumers (often the providers of such services) in a variety of domains. We used the insights gained through the theoretical and experimental analysis to investigate the optimality of privacy guarantees with a wide range of context-specific notions for utility. This chapter is aimed to bring together and reconcile the ideas explored in this thesis to show how the core theme of understanding and optimizing the privacy-utility trade-off has been addressed by this thesis and how these open up new avenues for future work. In summary:

i) Part II of the thesis elaborately studied the triadic interaction between the privacy of the users, their quality of service, and the statistical utility of the collected noisy data in the context of location-based services.

ii) Part III of the thesis analysed privacy-preserving aspects of the collaborative and federated approach to model training and dissected the interplay of privacy with the utility in the context of ethical and trustworthy machine learning.

iii) Part IV of the thesis furnished an efficient and practical model of private data trading by enhancing the functionality of data markets and optimizing the privacy requirements of the clients with the financial utility of the data collectors.

### Part II: Optimizing location-privacy preserving mechanisms

Chapter 3 bridged together some key ideas from rate-distortion theory and expectation maximization in statistics by establishing a duality between the Blahut-Arimoto algorithm and the
iterative Bayesian update and unravelled the comprehensive privacy-preserving properties of the Blahut-Arimoto algorithm, especially for location data. Benefitting from all the privacy-preserving and utility-friendly characteristics of the Blahut-Arimoto algorithm and its systematic entanglement with the iterative Bayesian update, PRIVIC, a mechanism for incremental collection of location-data, was proposed which instituted a rudimentary stepping stone heading towards a multi-faceted trade-off between the formal standard of location-privacy, privacy from an information theoretical perspective, quality of service for the users, and the statistical precision of the noisy data.

Chapter 4 theorised a bounded paradigm for geo-indistinguishability called approximate geo-indistinguishability and used it to propose a location privacy-preserving navigation protocol for the use case of electric vehicles making repeated queries during their journeys looking for available charging stations. Our method protects the privacy of both the specific query locations and the trace of the entire journey while fostering a high quality of service for the users and aiding in efficient route planning and traffic prediction by considering real-time queries. Considering a practical use case that is enduring a day-to-day surge in its social relevance, this study highlighted a method to obtain “privacy for free”, substantially enhancing the privacy-utility trade-off in the domain of navigation-based queries for vehicles especially when the points of interest (e.g., charging stations for electric vehicles) are sparse in the map.

The analyses carried out in Part II presents an in-depth understanding and illuminates the potential for enhancing the privacy-utility trade-off pertaining to both the users and service providers in location-based services. However, in addition to taking a step towards optimizing the location-privacy guarantees with different parameters of utility, this work unfurls a range of open questions that would be extremely interesting to address in future works. One such is to characterize the vulnerability of PRIVIC in handling malicious users falsely reporting their locations to compromise the privacy of the honest users located in isolated points in the map as presented in Section 3.8 of Chapter 3. In particular, we have seen that when all the users who are involved in sharing the locations and adhering to PRIVIC are honest, the Blahut-Arimoto algorithm, through its intrinsic elastic distinguishability metric, protects the locations isolated from the crowd much better than the Laplace mechanism, the canonical mechanism for geo-indistinguishability, does. However, considering adversarial users aiming to break the extensive privacy guarantees offered by PRIVIC, we highlight a major vulnerability of the Blahut-Arimoto algorithm, the elastic distinguishability metric, and, in turn, PRIVIC. Therefore, one of the major future directions to pursue is to propose a generalized and more robust version of PRIVIC that can handle such malicious data sharing. One possible way to formalise this idea could be by incorporating some penalty scheme, along the lines of what has been proposed in Section 8.4.2 of Chapter 8, to identify and exclude dishonest users intending to break the system.

Another important future avenue leading on from the work carried out in Part II is to re-evaluate the extensive privacy guarantees and the optimization of privacy with the different kinds of utility that PRIVIC offers by considering a correlation between the shared data and a change in the prior distribution. In practice, location-based services like *Pokémon Go* and *Tinder* collect and, in turn, use location data from users at different timesteps that are (obviously)
correlated and the original distribution changes over time [235, 236]. Hence, an important
goal moving forward is to examine the functionality of PRIVIC capturing such realistic scenar-
ios where the original distribution of the users' locations alters and the collected data are not
necessarily i.i.d. in nature. An added advantage of being potentially able to handle correlations
between the shared locations in the context of location-privacy preserving mechanisms is that it
would open up complimentary avenues of future work from Chapter 4 and enable us to extend
geo-indistinguishability and approximate geo-indistinguishability to traces as opposed to just
individual locations. There have been a few approaches explored in the literature [112, 237] to
privatize correlated locations and trajectories as opposed to independently sampled individual
locations. We plan to incorporate these with our work to propose more robust, pragmatic, and
efficient location-privacy-enhancing technologies with an optimal privacy-utility trade-off.

Part III: Investigating privacy guarantees of federated learning

Chapter 5 investigated personalized federated learning with metric privacy guarantees enabling a privacy-preserving collaborative paradigm for federated model training catering to the diversity present amongst the clients and their datasets. Our mechanism shows particular promise for machine learning models with a relatively small number of parameters. For larger models, experimental results demonstrate the effectiveness of the Laplace mechanism to defend against the gradient-inversion attacks like DLG. Additionally, we also evaluate the fairness of the trained personalized federated learning models under d-privacy using various group fairness metrics and concluded that personalized models significantly improve group fairness across all evaluated metrics and privacy levels, effectively mitigating biases towards the majority group, unlike non-personalized models. Remarkably, even with the highest level of privacy protection, personalized models consistently maintain superior fairness compared to their non-personalized counterparts, making a strong case for personalized model training in federated learning under d-privacy as a comprehensive solution for privacy-preserving and ethical machine learning. On the other hand, Chapter 6 presented a thorough foundational analysis to study the information leakage caused by the classical paradigm of (non-personalized) federated learning and, hence, dissected the working of the gradient-inversion-based data-reconstruction attacks threatening the very philosophy behind federated learning.

The work pursued in Part III of this thesis, alongside bespeaking various absorbing aspects
of privacy-preserving machine learning through the recently popularized federated approach,
unfolds many interesting open questions to be studied in the future. One of the major future
lines of work would be to incorporate more practical notions of user-oriented privacy (e.g.,
vulnerability against being identified in the training set in a black-box setting) with personalized
federated learning with *d*-provacy guarantees. Chapter 5 provided a solid ground to believe
that combining metric privacy with personalized model training in a federated environment
provides a win-win situation from the perspective of the model's accuracy, privacy, and fairness
standards. However, the information about the clusters could potentially unravel some gaping
holes in shielding personalized models from membership inference attacks from malicious third
parties. Such a study would be a gripping avenue of future work to comprehensively understand
the multimodal privacy-utility trade-off involved in personalized federated learning. A more ambitious goal would be to appropriately modify the IFCA algorithm<fnref n="1" /> to minimize the strength of membership inference attacks under a given level of privacy budget and an acceptable level of accuracy and fairness. A third line of study which can be really appealing to pursue in the future could be to combine the approach of explaining the information leakage from shared gradient updates, as presented in Chapter 6, with the privacy-preserving personalized federated learning method as proposed in Chapter 5 and, more ambitiously, to analyse the potential risks of membership inference attacks that personalized model training entails from a foundational and information theoretical perspective and fabricate appropriate defence mechanisms accordingly.

## Part IV: Optimally trading private data in data markets

Chapter 7 envisioned a scenario where data consumers trade directly with the data providers to obtain (privatized) data in exchange for financial compensation. This work started by proposing a truthful incentive mechanism to ensure that data providers do not indulge in dishonest reporting of their privacy requirements in the quest of earning more revenue which, eventually, enabled optimizing the privacy budgets of users, their financial benefits from the trade, and the profit of the data consumers. Chapter 8 considered an environment in which data providers form federations dealing with the data consumers. This chapter proposed a method for efficiently and swiftly trading locally differentially private data in such federated data markets and fairly splitting the earnings within federations by factoring in the contributions of each member. In addition, this chapter introduced the notion of a penalty scheme to penalize the free riders hindering the coherent and smooth functioning of federated data markets. The work exhibits an interdisciplinary approach by combining aspects of economics, game theory, and differential privacy to address the burning topic of appropriate pricing of differentially private data and a fair approach to motivate users to comply with the working of federated data markets.

The methods proposed in Part IV evolve some exciting prospects for potential future works. One very interesting avenue to explore in the future would be to integrate the notion of the truthful incentive mechanism of Chapter 7 in auditing differential privacy noise to ensure that genuine privacy requirements of users are satisfied. Another exciting line of future works following the theme of Chapter 8 would be to incentivize clients participating in federated model training (especially, in a cross-silo setting) to comply with the system and, in turn, with the help of the game theoretical methods used in Chapter 8 to fairly split the earnings within the participating silos. Finally, as elaborated earlier, it would be intriguing to integrate the idea of a penalty scheme, as introduced in Chapter 8, with PRIVIC (in Chapter 3) to deal with adversarial users keen to break the privacy of isolated locations in the maps.

**Final remark** To conclude, we remark that while the kernel of the investigations in this thesis has been to study and enhance the trade-off between privacy and utility to ensure that users of data-driven services and the corresponding service providers churn out the maximum possible

<footnote n="1">¹the algorithm used for personalized model training in Chapter 5</footnote>
benefit they can whilst upholding the fundamental right to privacy in a formal way, many in-
teresting and diverse applications of differential privacy and its variants are yet to be explored
which, in their own unique ways, will open up different notions of utility and, corresponding,
privacy-utility trade-offs. Some of the findings of this thesis have immense potential to be ap-
plied in a wide variety of domains in pursuit of achieving an optimal mechanism for privacy
and utility. Hence, we ambitiously envision that building up on the work carried out in this
thesis and with further advancements in research and technology, given the required thresholds
for privacy guarantees and for a number of notions of utility, we will be able to systematically
construct a system involving the optimal mechanism to satisfy these required goals in a way that
both the users and the providers of the service involved are motivated to conform to the working
of the system.
References

[1] B. Marr. *How much data do we create every day? the mind-blowing stats everyone should read* (2022). URL https://www.forbes.com/sites/bernardmarr/2018/05/21/how-much-data-do-we-create-every-day-the-mind-blowing-stats-everyone-should-read/.

[2] Wikipedia contributors. *2021 facebook leak* — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=2021_Facebook_leak&oldid=1157893507 (2023). [Online; accessed 13-July-2023].

[3] J. Silverstein. *Hundreds of millions of facebook user records were exposed on amazon cloud server* (2019). URL https://www.cbsnews.com/news/millions-facebook-user-records-exposed-amazon-cloud-server/.

[4] Wikipedia contributors. *Facebook–cambridge analytica data scandal* — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Facebook%E2%80%93Cambridge_Analytica_data_scandal&oldid=1162404364 (2023). [Online; accessed 13-July-2023].

[5] Wikipedia contributors. *2018 google data breach* — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=2018_Google_data_breach&oldid=1148797801 (2023). [Online; accessed 13-July-2023].

[6] D. MacMillan and R. MacMillan. *Google exposed user data, feared repercussions of closing to public* (2018). URL https://www.wsj.com/articles/google-exposed-user-data-feared-repercussions-of-disclosing-to-public-1539017194.

[7] Wikipedia contributors. *Yahoo! data breaches* — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Yahoo!_data_breaches&oldid=1086724827 (2022). [Online; accessed 10-May-2022].

[8] A. Narayanan and V. Shmatikov. *Robust de-anonymization of large sparse datasets*. In *Proceedings of the Symposium on Security and Privacy (SP)*, pp. 111–125 (IEEE, 2008).

[9] O. e Office of the Victorian Information Commissioner. *Disclosure of myki travel information*. URL https://ovic.vic.gov.au/wp-content/uploads/2019/08/Report-of-investigation_disclosure-of-myki-travel-information.pdf.

[10] T. Dalenius. *Towards a methodology for statistical disclosure control*. Statistik Tidskrift **15**, 429 (1977).
[11] L. Sweeney. *k-anonymity: A model for protecting privacy*. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems **10**(5), 557 (2002).

[12] S. Garfinkel, J. M. Abowd, and C. Martindale. *Understanding database reconstruction attacks on public data*. Communications of the ACM **62**(3), 46 (2019).

[13] C. Dwork, F. McSherry, K. Nissim, and A. Smith. *Calibrating noise to sensitivity in private data analysis*. In S. Halevi and T. Rabin, eds., *Theory of Cryptography*, pp. 265–284 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2006).

[14] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. *Our data, ourselves: Privacy via distributed noise generation*. In S. Vaudenay, ed., *Advances in Cryptology - EUROCRYPT 2006*, pp. 486–503 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2006).

[15] N. Fernandes, M. Dras, and A. McIver. *Processing text for privacy: An information flow perspective*. In K. Havelund, J. Peleska, B. Roscoe, and E. P. de Vink, eds., *Formal Methods - 22nd International Symposium, FM 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 15-17, 2018, Proceedings*, vol. 10951 of Lecture Notes in Computer Science, pp. 3–21 (Springer, 2018). URL https://doi.org/10.1007/978-3-319-95582-7_1.

[16] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. *Geo-indistinguishability: Differential privacy for location-based systems*. In *Proceedings of the 2013 ACM SIGSAC Conference on Computer &; Communications Security*, CCS '13, p. 901–914 (Association for Computing Machinery, New York, NY, USA, 2013). URL https://doi.org/10.1145/2508859.2516735.

[17] K. Chatzikokolakis, M. E. Andrés, N. E. Bordenabe, and C. Palamidessi. *Broadening the scope of differential privacy using metrics*. In *International Symposium on Privacy Enhancing Technologies Symposium*, pp. 82–102 (Springer, 2013).

[18] J. Hsu, M. Gaboardi, A. Haeberlen, S. Khanna, A. Narayan, B. C. Pierce, and A. Roth. *Differential privacy: An economic method for choosing epsilon*. In *IEEE 27th Computer Security Foundations Symposium, CSF 2014, Vienna, Austria, 19-22 July, 2014*, pp. 398–410 (IEEE Computer Society, 2014). URL https://doi.org/10.1109/CSF.2014.35.

[19] M. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and G. Smith. *The Science of Quantitative Information Flow*. Information Security and Cryptography (Springer, Springer Nature, United States, 2020).

[20] L. Zhu, Z. Liu, and S. Han. *Deep leakage from gradients*. In *Annual Conference on Neural Information Processing Systems (NeurIPS)* (2019).

[21] H. Yin, A. Mallya, A. Vahdat, J. M. Alvarez, J. Kautz, and P. Molchanov. *See through*
gradients: Image batch recovery via gradinversion. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 16332-16341 (IEEE Computer Society, Los Alamitos, CA, USA, 2021). URL https://doi.ieeecomputersociety.org/10.1109/CVPR46437.2021.01607.

[22] S. L. Garfinkel, J. M. Abowd, and S. Powazek. Issues encountered deploying differential privacy. In Proceedings of the 2018 Workshop on Privacy in the Electronic Society, pp. 133-137 (2018).

[23] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 429-438 (2013).

[24] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. Optimal geo-indistinguishable mechanisms for location privacy. In Proceedings of the 21st ACM Conference on Computer and Communications Security (CCS 2014) (2014).

[25] N. Fernandes, A. McIver, and C. Morgan. The laplace mechanism has optimal utility for differential privacy over continuous queries. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021., pp. 1-12 (IEEE, 2021). URL https://doi.org/10.1109/LICS52264.2021.9470718.

[26] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communication-Efficient Learning of Deep Networks from Decentralized Data. In A. Singh and J. Zhu, eds., Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, vol. 54 of Proceedings of Machine Learning Research, pp. 1273-1282 (PMLR, 2017). URL https://proceedings.mlr.press/v54/mcmahan17a.html.

[27] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep Learning with Differential Privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '16, pp. 308-318 (ACM, New York, NY, USA, 2016). URL http://doi.acm.org/10.1145/2976749.2978318.

[28] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang. Learning Differentially Private Re-current Language Models. In International Conference on Learning Representations (2018). URL https://openreview.net/forum?id=BJ0hF1Z0b.

[29] H. B. McMahan, G. Andrew, U. Erlingsson, S. Chien, I. Mironov, N. Papernot, and P. Kairouz. A general approach to adding differential privacy to iterative training proce-dures (2019). 1812.06210.

[30] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers. Protection against reconstruction and its applications in private federated learning (2019). URL https://arxiv.org/pdf/1812.00984.

[31] R. Agrawal, R. Srikant, and D. Thomas. Privacy preserving olap. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 251-262 (2005).
[32] P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy. In International Conference on Machine Learning, pp. 2436–2444 (PMLR, 2016).

[33] D. Agrawal and C. C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. In Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '01, p. 247–255 (Association for Computing Machinery, New York, NY, USA, 2001). URL https://doi.org/10.1145/375551.375602.

[34] E. ElSalamouny and C. Palamidessi. Full convergence of the iterative bayesian update and applications to mechanisms for privacy protection. CoRR abs/1909.02961 (2019). 1909.02961, URL http://arxiv.org/abs/1909.02961.

[35] L. V. Kantorovich. Mathematical Methods of Organizing and Planning Production, vol. 6 (INFORMS, 1960).

[36] Úlfar Erlingsson, V. Pihur, and A. Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 21st ACM Conference on Computer and Communications Security (Scottsdale, Arizona, 2014). URL https://arxiv.org/abs/1407.6981.

[37] R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.-Y. Le Boudec. Protecting location privacy: Optimal strategy against localization attacks. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS '12, p. 617–627 (Association for Computing Machinery, New York, NY, USA, 2012). URL https://doi.org/10.1145/2382196.2382261.

[38] R. Shokri. Privacy games: Optimal user-centric data obfuscation. Proceedings on Privacy Enhancing Technologies 2015(2), 299 (2015). URL https://doi.org/10.1515/popets-2015-0024.

[39] F. Galli, S. Biswas, K. Jung, C. Palamidessi, and T. Cucinotta. Group privacy for personalized federated learning. arXiv preprint arXiv:2206.03396 (2022).

[40] K. Chatzikokolakis, C. Palamidessi, and M. Stronati. Constructing elastic distinguishability metrics for location privacy. Proceedings on Privacy Enhancing Technologies 2015(2), 156 (2015). URL https://doi.org/10.1515/popets-2015-0023.

[41] R. E. Blahut. Computation of channel capacity and rate-distortion functions. IEEE Trans. Inform. Theory 18, 460 (1972).

[42] S. Arimoto. An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEE Trans. Inf. Theory 18, 14 (1972).

[43] S. Oya, C. Troncoso, and F. Pérez-González. Back to the drawing board: Revisiting the design of optimal location privacy-preserving mechanisms. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1959–1972 (ACM, 2017). URL http://doi.acm.org/10.1145/3133956.3134004.
[44] C. E. Shannon. *A mathematical theory of communication*. The Bell System Technical Journal **27**(3), 379 (1948).

[45] I. Csiszar. *On the computation of rate-distortion functions (corresp.).* Information Theory, IEEE Transactions on **20**, 122 (1974).

[46] E. ElSalamouny and C. Palamidessi. *Generalized iterative bayesian update and applications to mechanisms for privacy protection*. In *2020 IEEE European Symposium on Security and Privacy (EuroS P)*, pp. 490–507 (2020).

[47] J. Brickell and V. Shmatikov. *The cost of privacy: Destruction of data-mining utility in anonymized data publishing*. In *Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, KDD '08, p. 70–78 (Association for Computing Machinery, New York, NY, USA, 2008). URL https://doi.org/10.1145/1401890.1401904.

[48] S. Ioannidis, A. Montanari, U. Weinsberg, S. Bhagat, N. Fawaz, and N. Taft. *Privacy trade-offs in predictive analytics*. In *The 2014 ACM International Conference on Measurement and Modeling of Computer Systems*, SIGMETRICS '14, p. 57–69 (Association for Computing Machinery, New York, NY, USA, 2014). URL https://doi.org/10.1145/2591971.2592011.

[49] A. Ghosh, T. Roughgarden, and M. Sundararajan. *Universally utility-maximizing privacy mechanisms*. SIAM Journal on Computing **41**(6), 1673 (2012). URL https://doi.org/10.1137/09076828X; URL https://doi.org/10.1137/09076828X.

[50] M. Gupte and M. Sundararajan. *Universally optimal privacy mechanisms for minimax agents*. In *Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems*, PODS '10, p. 135–146 (Association for Computing Machinery, New York, NY, USA, 2010). URL https://doi.org/10.1145/1807085.1807105.

[51] C. Li, M. Hay, V. Rastogi, G. Miklau, and A. McGregor. *Optimizing linear counting queries under differential privacy*. In *Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems*, PODS '10, p. 123–134 (Association for Computing Machinery, New York, NY, USA, 2010). URL https://doi.org/10.1145/1807085.1807104.

[52] S. Oya, C. Troncoso, and F. Pérez-González. *Rethinking location privacy for unknown mobility behaviors*. In *2019 IEEE European Symposium on Security and Privacy (EuroS P)*, pp. 416–431 (2019).

[53] M. Romanelli, K. Chatzikokolakis, and C. Palamidessi. *Optimal obfuscation mechanisms via machine learning*. In *2020 IEEE 33rd Computer Security Foundations Symposium (CSF)*, pp. 153–168 (2020).

[54] W. Zhang, M. Li, R. Tandon, and H. Li. *Online location trace privacy: An information theoretic approach*. IEEE Transactions on Information Forensics and Security **14**(1), 235 (2019).
[55] U. I. Atmaca, S. Biswas, C. Maple, and C. Palamidessi. *A privacy preserving querying mechanism with high utility for electric vehicles* (2022). 2206.02060.

[56] P. Cuff and L. Yu. *Differential privacy as a mutual information constraint*. In *Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security (CCS)*, CCS '16, pp. 43–54 (ACM, New York, NY, USA, 2016). URL http://doi.acm.org/10.1145/2976749.2978308.

[57] B. Köpf and D. A. Basin. *An information-theoretic model for adaptive side-channel attacks*. In P. Ning, S. D. C. di Vimercati, and P. F. Syverson, eds., *Proceedings of the 2007 ACM Conference on Computer and Communications Security (CCS 2007)*, pp. 286–296 (ACM, 2007).

[58] Y. Zhu and R. Bettati. *Anonymity vs. information leakage in anonymity systems*. In *Proc. of ICDCS*, pp. 514–524 (IEEE Computer Society, 2005).

[59] K. Chatzikokolakis, C. Palamidessi, and P. Panangaden. *Anonymity protocols as noisy channels*. Information and Computation **206**(2–4), 378 (2008). URL http://hal.inria.fr/inria-00349225/en/.

[60] M. Abadi and D. G. Andersen. *Learning to protect communications with adversarial neural cryptography*. CoRR abs/1610.06918 (2016). 1610.06918, URL http://arxiv.org/abs/1610.06918.

[61] A. Tripathy, Y. Wang, and P. Ishwar. *Privacy-preserving adversarial networks*. In *57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019*, Monticello, IL, USA, September 24-27, 2019, pp. 495–505 (IEEE, 2019). URL https://doi.org/10.1109/ALLERTON.2019.8919758.

[62] C. Huang, P. Kairouz, X. Chen, L. Sankar, and R. Rajagopal. *Context-aware generative adversarial privacy*. Entropy **19**(12) (2017).

[63] P. Syverson. *Why i'm not an entropist*. In B. Christianson, J. A. Malcolm, V. Matyáš, and M. Roe, eds., *Security Protocols XVII*, pp. 213–230 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2013).

[64] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. *Optimal geo-indistinguishable mechanisms for location privacy*. In *Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security*, CCS '14, p. 251–262 (Association for Computing Machinery, New York, NY, USA, 2014). URL https://doi.org/10.1145/2660267.2660345.

[65] K. Chatzikokolakis, C. Palamidessi, and M. Stronati. *Constructing elastic distinguishability metrics for location privacy*. *Proceedings on Privacy Enhancing Technologies 2015*(2), 156 (2015). URL https://doi.org/10.1515/popets-2015-0023.

[66] K. Chatzikokolakis, E. ElSalamouny, and C. Palamidessi. *Efficient utility improvement for location privacy*. *Proceedings on Privacy Enhancing Technologies 2017*(4), 308 (2017). URL https://doi.org/10.1515/popets-2017-0051.
[67] J.-W. Byun, T. Li, E. Bertino, N. Li, and Y. Sohn. *Privacy-preserving incremental data dissemination*. J. Comput. Secur. **17**(1), 43–68 (2009).

[68] J.-W. Byun, Y. Sohn, E. Bertino, and N. Li. *Secure anonymization for incremental datasets*. In W. Jonker and M. Petković, eds., *Secure Data Management*, pp. 48–63 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2006).

[69] A. Anjum, G. Raschia, M. Gelgon, A. Khan, N. Ahmad, M. Ahmed, S. Suhail, M. M. Alam, et al. *τ-safety: A privacy model for sequential publication with arbitrary updates*. computers & security **66**, 20 (2017).

[70] Y. Wang, X. Wu, and D. Hu. *Using randomized response for differential privacy preserving data collection*. In *EDBT/ICDT Workshops*, vol. 1558, pp. 0090–6778 (2016).

[71] M. E. Gursoy, A. Tamersoy, S. Truex, W. Wei, and L. Liu. *Secure and utility-aware data collection with condensed local differential privacy*. IEEE Transactions on Dependable and Secure Computing **18**(5), 2365 (2021).

[72] J. Leskovec and A. Krevl. *SNAP Datasets: Stanford large network dataset collection*. http://snap.stanford.edu/data/loc-Gowalla.html (2014).

[73] E. Cho, S. A. Myers, and J. Leskovec. *Friendship and mobility: user movement in location-based social networks*. In *Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining*, pp. 1082–1090 (2011).

[74] J. Nash. *Non-cooperative games*. Annals of Mathematics **54**(2), 286 (1951). URL http://www.jstor.org/stable/1969529.

[75] E. Gal-or. *Hotelling's spatial competition as a model of sales*. Economics Letters **9**(1), 1 (1982). URL https://www.sciencedirect.com/science/article/pii/0165176582900891.

[76] R. Shokri, G. Theodorakopoulos, G. Danezis, J.-P. Hubaux, and J.-Y. Le Boudec. *Quantifying location privacy: The case of sporadic location exposure*. In S. Fischer-Hübner and N. Hopper, eds., *Privacy Enhancing Technologies*, pp. 57–76 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2011).

[77] E. Ferrero, S. Alessandrini, and A. Balanzino. *Impact of the electric vehicles on the air pollution from a highway*. Applied Energy **169**, 450 (2016).

[78] K. Hampshire, R. German, A. Pridmore, and J. Fons. *Electric vehicles from life cycle and circular economy perspectives*. Version **2**, 25 (2018).

[79] R. Zhang and S. Fujimori. *The role of transport electrification in global climate change mitigation scenarios*. Environmental Research Letters **15**(3), 034019 (2020).

[80] R. Hickman and D. Banister. *Looking over the horizon: Transport and reduced co2 emissions in the uk by 2030*. Transport Policy **14**(5), 377 (2007).
[81] S. Kufeoglu and D. K. K. Hong. *Emissions performance of electric vehicles: A case study from the united kingdom*. Applied Energy **260**, 114241 (2020).

[82] E. P. Seymour Millen. *Transport and environment statistics 2021 annual report* (May 2021). URL https://assets.publishing.service.gov.uk/government/uploads/system/uploads/attachment_data/file/984685/transport-and-environment-statistics-2021.pdf.

[83] T. Gersdorf, P. Hertzke, P. Schaufuss, and S. Schenk. *Mckinsey electric vehicle index: Europe cushions a global plunge in ev sales* (2020).

[84] R. Hensley, S. Knupfer, and D. Pinner. *Electrifying cars: How three industries will evolve*. McKinsey Quarterly **3**(2009), 87 (2009).

[85] P. Gao, R. Hensley, and A. Zielke. *A road map to the future for the auto industry*. McKinsey Quarterly, Oct pp. 1–11 (2014).

[86] M. Lombardi, K. Panerali, S. Rousselet, and J. Scalise. *Electric vehicles for smarter cities: the future of energy and mobility*. In *World Economic Forum*. http://www3.weforum.org/docs/WEF_2018_%20Electric_From_Smoarter_Cities.pdf (2018).

[87] A. Ostermann, Y. Fabel, K. Ouan, and H. Koo. *Forecasting charging point occupancy using supervised learning algorithms*. Energies **15**(9), 3409 (2022).

[88] A. Sao, N. Tempelmeier, and E. Demidova. *Deep information fusion for electric vehicle charging station occupancy forecasting*. In *2021 IEEE International Intelligent Transportation Systems Conference (ITSC)*, pp. 3328–3333 (2021).

[89] L. Gillam, K. Katsaros, M. Dianati, and A. Mouzakitis. *Exploring edges for connected and autonomous driving*. In *IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)*, pp. 148–153 (IEEE, 2018).

[90] C. Maple, M. Bradbury, A. T. Le, and K. Ghirardello. *A connected and autonomous vehicle reference architecture for attack surface analysis*. Applied Sciences **9**(23), 5101 (2019).

[91] D. Hahn, A. Munir, and V. Behzadan. *Security and privacy issues in intelligent transportation systems: Classification and challenges*. IEEE Intelligent Transportation Systems Magazine **13**(1), 181 (2019).

[92] X. Lin and X. Li. *Achieving efficient cooperative message authentication in vehicular ad hoc networks*. IEEE Transactions on Vehicular Technology **62**(7), 3339 (2013).

[93] N. Kumar, R. Iqbal, S. Misra, and J. J. Rodrigues. *An intelligent approach for building a secure decentralized public key infrastructure in vanet*. Journal of Computer and System Sciences **81**(6), 1042 (2015).

[94] P. Zhao, G. Zhang, S. Wan, G. Liu, and T. Umer. *A survey of local differential privacy for securing internet of vehicles*. The Journal of Supercomputing **76**(11), 8391 (2020).
[95] T. Franke and J. F. Krems. Understanding charging behaviour of electric vehicle users. Transportation Research Part F: Traffic Psychology and Behaviour **21**, 75 (2013).

[96] R. R. Kumar and K. Alok. Adoption of electric vehicle: A literature review and prospects for sustainability. Journal of Cleaner Production **253**, 119911 (2020).

[97] Z. Tian, T. Jung, Y. Wang, F. Zhang, L. Tu, C. Xu, C. Tian, and X.-Y. Li. Real-time charging station recommendation system for electric-vehicle taxis. IEEE Transactions on Intelligent Transportation Systems **17**(11), 3098 (2016).

[98] W. Zhang, H. Liu, F. Wang, T. Xu, H. Xin, D. Dou, and H. Xiong. Intelligent electric vehicle charging recommendation based on multi-agent reinforcement learning. In Proceedings of the Web Conference 2021, pp. 1856–1867 (2021).

[99] R. Flocea, A. Hîncu, A. Robu, S. Senocico, A. Traciu, B. M. Remus, M. S. Răboacă, and C. Filote. Electric vehicle smart charging reservation algorithm. Sensors **22**(8), 2834 (2022).

[100] G. Wang, W. Li, J. Zhang, Y. Ge, Z. Fu, F. Zhang, Y. Wang, and D. Zhang. sharedcharging: Data-driven shared charging for large-scale heterogeneous electric vehicle fleets. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies **3**(3), 1 (2019).

[101] PlugShare. Privacy policy (2023). URL https://company plugshare com/privacy.html.

[102] ChargePoint. Privacy and cookie policy for europe (2023). URL https://eu(chargepoint. com/privacy_policy.

[103] C.-Y. Chow, M. F. Mokbel, and W. G. Aref. Casper* query processing for location services without compromising privacy. ACM Transactions on Database Systems (TODS) **34**(4), 1 (2009).

[104] B. Niu, Q. Li, X. Zhu, G. Cao, and H. Li. Achieving k-anonymity in privacy-aware location-based services. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications, pp. 754–762 (IEEE, 2014).

[105] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. **9**(3–4), 211–407 (2014). URL https://doi.org/10.1561/ 0400000042.

[106] N. Guo, L. Ma, and T. Gao. Independent mix zone for location privacy in vehicular networks. IEEE Access **6**, 16842 (2018).

[107] S. Amini, J. Lindqvist, J. I. Hong, M. Mou, R. Raheja, J. Lin, N. Sadeh, and E. Tochb. Caché: Caching location-enhanced content to improve user privacy. SIGMOBILE Mob. Com- put. Commun. Rev. **14**(3), 19–21 (2011).

[108] P. Asuquo, H. Cruickshank, J. Morley, C. P. A. Ogah, A. Lei, W. Hathal, S. Bao, and Z. Sun. Security and privacy in location-based services for vehicular and mobile communications:
*An overview, challenges, and countermeasures*. IEEE Internet of Things Journal **5**(6), 4778 (2018).

[109] L. Zhou, L. Yu, S. Du, H. Zhu, and C. Chen. *Achieving differentially private location privacy in edge-assistant connected vehicles*. IEEE Internet of Things Journal **6**(3), 4472 (2018).

[110] L. Luo, Z. Han, C. Xu, and G. Zhao. *A geo-indistinguishable location privacy preservation scheme for location-based services in vehicular networks*. In *International Conference on Algorithms and Architectures for Parallel Processing*, pp. 610–623 (Springer, 2019).

[111] C. Qiu, A. C. Squicciarini, C. Pang, N. Wang, and B. Wu. *Location privacy protection in vehicle-based spatial crowdsourcing via geo-indistinguishability*. IEEE Transactions on Mobile Computing pp. 1–1 (2020).

[112] T. Cunningham, G. Cormode, H. Ferhatosmanoglu, and D. Srivastava. *Real-world trajectory sharing with local differential privacy*. Proc. VLDB Endow. **14**(11), 2283–2295 (2021).

[113] K. Chatzikokolakis, E. ElSalamouny, and C. Palamidessi. *Efficient utility improvement for location privacy*. Proceedings on Privacy Enhancing Technologies **2017**(4), 308 (2017).

[114] A. Ghosh, T. Roughgarden, and M. Sundararajan. *Universally utility-maximizing privacy mechanisms* (2009). 0811.2841.

[115] E. Bulut and M. C. Kisacikoglu. *Mitigating range anxiety via vehicle-to-vehicle social charging system*. In *2017 IEEE 85th Vehicular Technology Conference (VTC Spring)*, pp. 1–5 (IEEE, 2017).

[116] W. Duan, J. Gu, M. Wen, G. Zhang, Y. Ji, and S. Mumtaz. *Emerging technologies for 5g-iov networks: Applications, trends and opportunities*. IEEE Network **34**(5), 283 (2020).

[117] H. Ji, O. Alfarraj, and A. Tolba. *Artificial intelligence-empowered edge of vehicles: Architecture, enabling technologies, and applications*. IEEE Access **8**, 61020 (2020).

[118] H. Patil and V. N. Kalkhambkar. *Grid integration of electric vehicles for economic benefits: A review*. Journal of Modern Power Systems and Clean Energy **9**(1), 13 (2020).

[119] L. Gillam, K. Katsaros, M. Dianati, and A. Mouzakitis. *Exploring edges for connected and autonomous driving*. In *IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)*, pp. 148–153 (2018).

[120] H. Seo, K.-D. Lee, S. Yasukawa, Y. Peng, and P. Sartori. *Lte evolution for vehicle-to-everything services*. IEEE communications magazine **54**(6), 22 (2016).

[121] A. Paverd, A. Martin, and I. Brown. *Modelling and automatically analysing privacy properties for honest-but-curious adversaries*. Tech. Rep (2014).

[122] OpenStreetMap contributors. *Planet dump retrieved from https://planet.osm.org*. https://www.openstreetmap.org (2022).
[123] A. F. D. C. U.S. Department of Energy. Alternative fuels data center: Data downloads (2023). URL https://afdc.energy.gov/data_download/.

[124] M. T. Agency. Datasf (2023). URL https://data.sfgov.org/browse?Department-Metrics_Publishing-Department=Municipal+Transportation+Agency+.

[125] M. Piorkowski, N. Sarafijanovic-Djukic, and M. Grossglauser. Crawdad data set epfl/mobility (v. 2009-02-24) (2009).

[126] X. Li, Y. Ren, L. T. Yang, N. Zhang, B. Luo, J. Weng, and X. Liu. Perturbation-hidden: Enhancement of vehicular privacy for location-based services in internet of vehicles. IEEE Transactions on Network Science and Engineering 8(3), 2073 (2021).

[127] L. Zhang, X. Meng, K.-K. R. Choo, Y. Zhang, and F. Dai. Privacy-preserving cloud establishment and data dissemination scheme for vehicular cloud. IEEE Transactions on Dependable and Secure Computing 17(3), 634 (2018).

[128] J. Freudiger, M. Raya, M. Félegyházi, P. Papadimitratos, and J.-P. Hubaux. Mix-zones for location privacy in vehicular networks. In ACM Workshop on Wireless Networking for Intelligent Transportation Systems (WiN-ITS), CONF (2007).

[129] H. Jiang, J. Li, P. Zhao, F. Zeng, Z. Xiao, and A. Iyengar. Location privacy-preserving mechanisms in location-based services: A comprehensive survey. ACM Comput. Surv. 54(1) (2021).

[130] H. Zang and J. Bolot. Anonymization of location data does not work: A large-scale measurement study. In Proceedings of the 17th annual international conference on Mobile computing and networking, pp. 145–156 (2011).

[131] C. Hecht, J. Figgener, and D. U. Sauer. Predicting electric vehicle charging station availability using ensemble machine learning. Energies 14(23), 7834 (2021).

[132] A. Nait-Sidi-Moh, A. Ruzmetov, M. Bakhouya, Y. Naitmalek, and J. Gaber. A prediction model of electric vehicle charging requests. Procedia Computer Science 141, 127 (2018).

[133] T.-Y. Ma and S. Faye. Multistep electric vehicle charging station occupancy prediction using hybrid lstm neural networks. Energy 244, 123217 (2022).

[134] A. Almaghrebi, F. Aljuheshi, M. Rafaie, K. James, and M. Alahmad. Data-driven charging demand prediction at public charging stations using supervised machine learning regression methods. Energies 13(16), 4231 (2020).

[135] R. Luo, Y. Zhang, Y. Zhou, H. Chen, L. Yang, J. Yang, and R. Su. Deep learning approach for long-term prediction of electric vehicle (ev) charging station availability. In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pp. 3334–3339 (IEEE, 2021).
[136] D. Le Métayer and S. J. De. PRIAM: a Privacy Risk Analysis Methodology. In G. Livraga, V. Torra, A. Aldini, F. Martinelli, and N. Suri, eds., Data Privacy Management and Security Assurance (Springer, Heraklion, Greece, 2016). URL https://hal.inria.fr/hal-01420983.

[137] NIST. Nist privacy framework core. URL https://www.nist.gov/system/files/documents/2021/05/05/NIST-Privacy-Framework-V1.0-Core-PDF.pdf.

[138] A. Ghosh, J. Chung, D. Yin, and K. Ramchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems 33, 19586 (2020).

[139] Y. Mansour, M. Mohri, J. Ro, and A. T. Suresh. Three approaches for personalization with applications to federated learning. arXiv preprint arXiv:2002.10619 (2020).

[140] F. Sattler, K.-R. Müller, and W. Samek. Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints. IEEE transactions on neural networks and learning systems 32(8), 3710 (2020).

[141] B. Hitaj, G. Ateniese, and F. Perez-Cruz. Deep models under the gan: information leakage from collaborative deep learning. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pp. 603–618 (2017).

[142] M. Nasr, R. Shokri, and A. Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP), pp. 739–753 (IEEE, 2019).

[143] L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients. Advances in Neural Information Processing Systems 32 (2019).

[144] G. Andrew, O. Thakkar, B. McMahan, and S. Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems 34 (2021).

[145] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations (2018). URL https://openreview.net/forum?id=BJ0hF1Z0b.

[146] S. Truex, L. Liu, K.-H. Chow, M. E. Gursoy, and W. Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking, pp. 61–66 (2020).

[147] Y. Zhao, J. Zhao, M. Yang, T. Wang, N. Wang, L. Lyu, D. Niyato, and K.-Y. Lam. Local differential privacy-based federated learning for internet of things. IEEE Internet of Things Journal 8(11), 8836 (2020).

[148] S. Biswas and C. Palamidessi. Privic: A privacy-preserving method for incremental collection of location data (2023). 2206.10525.

[149] N. Fernandes, A. McIver, C. Palamidessi, and M. Ding. Universal optimality and robust utility bounds for metric differential privacy. In 2022 IEEE 35th Computer Security Foundations Symposium (CSF), pp. 348–363 (2022).
[150] F. Galli, S. Biswas, K. Jung, T. Cucinotta, and C. Palamidessi. *Group privacy for personalized federated learning*. In *Proceedings of the 9th International Conference on Information Systems Security and Privacy - ICISSP*, pp. 252–263 (SciTePress - INSTICC, 2023).

[151] R. Berk, H. Heidari, S. Jabbari, M. Kearns, and A. Roth. *Fairness in criminal justice risk assessments: The state of the art*. *Sociological Methods & Research* **50**(1), 3 (2021).

[152] A. Chouldechova. *Fair prediction with disparate impact: A study of bias in recidivism prediction instruments*. *Big data* **5**(2), 153 (2017).

[153] S. Agarwal. *Trade-offs between fairness and privacy in machine learning*. *ijcai 2021 workshop on ai for social good*. 2021 (2022).

[154] S. Verma and J. Rubin. *Fairness definitions explained*. In *Proceedings of the international workshop on software fairness*, pp. 1–7 (2018).

[155] R. Hanna and L. Linden. *Measuring discrimination in education*. Tech. rep., National Bureau of Economic Research (2009).

[156] K. Makhlouf, S. Zhioua, and C. Palamidessi. *On the applicability of machine learning fairness notions*. *ACM SIGKDD Explorations Newsletter* **23**(1), 14 (2021).

[157] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. *Fairness through awareness*. In *Proceedings of the 3rd innovations in theoretical computer science conference*, pp. 214–226 (2012).

[158] M. Hardt, E. Price, and N. Srebro. *Equality of opportunity in supervised learning*. Advances in neural information processing systems **29** (2016).

[159] R. C. Geyer, T. Klein, and M. Nabi. *Differentially private federated learning: A client level perspective*. *arXiv preprint arXiv:1712.07557* (2017).

[160] K. A. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. *Practical secure aggregation for federated learning on user-held data*. In *NIPS Workshop on Private Multi-Party Machine Learning* (2016). URL https://arxiv.org/abs/1611.04482.

[161] N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan. *cpsgd: Communication-efficient and differentially-private distributed sgd*. Advances in Neural Information Processing Systems **31** (2018).

[162] R. Hu, Y. Guo, H. Li, Q. Pei, and Y. Gong. *Personalized federated learning with differential privacy*. *IEEE Internet of Things Journal* **7**(10), 9530 (2020).

[163] K. A. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. *Practical secure aggregation for federated learning on user-held data*. In *NIPS Workshop on Private Multi-Party Machine Learning* (2016). URL https://arxiv.org/abs/1611.04482.
[164] S. Chhabra, Y. Solihin, R. Lal, and M. Hoekstra. *An analysis of secure processor architectures*. Transactions on computational science VII pp. 101–121 (2010).

[165] T. Cucinotta, D. Cherubini, and E. Jul. *Confidential execution of cloud services*. In *CLOSER*, pp. 616–621 (2014).

[166] A. Chhabra, K. Masalkovaitė, and P. Mohapatra. *An overview of fairness in clustering*. IEEE Access 9, 130698 (2021).

[167] Y. H. Ezzeldin, S. Yan, C. He, E. Ferrara, and S. Avestimehr. *Fairfed: Enabling group fairness in federated learning*. In *1st NeurIPS Workshop on New Frontiers in Federated Learning* (2021). URL https://arxiv.org/abs/1611.04482.

[168] L. Chu, L. Wang, Y. Dong, J. Pei, Z. Zhou, and Y. Zhang. *Fedfair: Training fair models in cross-silo federated learning*. arXiv preprint arXiv:2109.05662 (2021).

[169] A. K. Menon and R. C. Williamson. *The cost of fairness in binary classification*. In *Conference on Fairness, accountability and transparency*, pp. 107–118 (PMLR, 2018).

[170] M. Wick, J.-B. Tristan, et al. *Unlocking fairness: a trade-off revisited*. Advances in neural information processing systems 32 (2019).

[171] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan. *A survey on bias and fairness in machine learning*. ACM Computing Surveys (CSUR) 54(6), 1 (2021).

[172] S. Biswas and H. Rajan. *Fair preprocessing: towards understanding compositional fairness of data transformers in machine learning pipeline*. In *Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering*, pp. 981–993 (2021).

[173] F. Kamiran and T. Calders. *Data preprocessing techniques for classification without discrimination*. Knowledge and information systems 33(1), 1 (2012).

[174] M. Wan, D. Zha, N. Liu, and N. Zou. *In-processing modeling techniques for machine learning fairness: A survey*. ACM Transactions on Knowledge Discovery from Data 17(3), 1 (2023).

[175] T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. *Fairness without demographics in repeated loss minimization*. In *International Conference on Machine Learning*, pp. 1929–1938 (PMLR, 2018).

[176] F. Petersen, D. Mukherjee, Y. Sun, and M. Yurochkin. *Post-processing for individual fairness*. Advances in Neural Information Processing Systems 34, 25944 (2021).

[177] A. Noriega-Campero, M. A. Bakker, B. Garcia-Bulle, and A. Pentland. *Active fairness in algorithmic decision making*. In *Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society*, pp. 77–83 (2019).
[178] R. Cummings, V. Gupta, D. Kimpara, and J. Morgenstern. *On the compatibility of privacy and fairness*. In *Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization*, pp. 309–315 (2019).

[179] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi. *Geo-indistinguishability: Differential privacy for location-based systems*. In *Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security*, pp. 901–914 (2013).

[180] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtarik, A. T. Suresh, and D. Bacon. *Federated learning: Strategies for improving communication efficiency*. In *NIPS Workshop on Private Multi-Party Machine Learning* (2016). URL https://arxiv.org/abs/1610.05492.

[181] CMMS. *Centers for medicare and medicaid services* (2021). Accessed: 2022-09-21, URL https://www.cms.gov/mmrr/News/mmrr-news-2013-03-hosp-chg-data.html.

[182] S. Caldas, S. M. K. Duddu, P. Wu, T. Li, J. Konečný, H. B. McMahan, V. Smith, and A. Talwalkar. *Leaf: A benchmark for federated settings*. Workshop on Federated Learning for Data Privacy and Confidentiality (2019).

[183] R. Bassily, K. Nissim, U. Stemmer, and A. Guha Thakurta. *Practical locally private heavy hitters*. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds., *Advances in Neural Information Processing Systems*, vol. 30 (Curran Associates, Inc., Red Hook, NY, USA, 2017). URL https://proceedings.neurips.cc/paper/2017/file/3d779cae2d46cf6a8a99a35ba4167977-Paper.pdf.

[184] R. Bartlett, A. Morse, R. Stanton, and N. Wallace. *Consumer-lending discrimination in the fintech era*. Journal of Financial Economics 143(1), 30 (2022).

[185] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. *What can we learn privately?* SIAM Journal on Computing 40(3), 793 (2011). https://doi.org/10.1137/090756090, URL https://doi.org/10.1137/090756090.

[186] P. Kairouz, S. Oh, and P. Viswanath. *Extremal mechanisms for local differential privacy*. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, eds., *Advances in Neural Information Processing Systems*, vol. 27 (Curran Associates, Inc., 2014). URL https://proceedings.neurips.cc/paper_files/paper/2014/file/86df7dcfd896fcaf2674f757a2463eba-Paper.pdf.

[187] J. Ullman. *Tight lower bounds for locally differentially private selection*. arXiv preprint arXiv:1802.02638 (2018).

[188] R. Bassily, K. Nissim, U. Stemmer, and A. Guha Thakurta. *Practical locally private heavy hitters*. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds., *Advances in Neural Information Processing Systems*, vol. 30 (Curran Associates, Inc., 2017). URL https://proceedings.neurips.cc/paper_files/paper/2017/file/3d779cae2d46cf6a8a99a35ba4167977-Paper.pdf.
[189] F. Galli., S. Biswas., K. Jung., T. Cucinotta., and C. Palamidessi. *Group privacy for personalized federated learning*. In *Proceedings of the 9th International Conference on Information Systems Security and Privacy - ICISSP*, pp. 252–263. INSTICC (SciTePress, 2023).

[190] J. Zhu and M. Blaschko. *R-gap: Recursive gradient attack on privacy* (2021). 2010.07733.

[191] M. Lam, G.-Y. Wei, D. Brooks, V. J. Reddi, and M. Mitzenmacher. *Gradient disaggregation: Breaking privacy in federated learning by reconstructing the user participant matrix* (2021). 2106.06089.

[192] C. E. Shannon. *A mathematical theory of communication*. The Bell System Technical Journal **27**(3), 379 (1948).

[193] N. Fernandes. *Differential privacy for metric spaces : information-theoretic models for privacy and utility with new applications to metric domains*. Theses, Institut Polytechnique de Paris ; Macquarie University (Sydney, Australie) (2021). URL https://theses.hal.science/tel-03344453.

[194] *Liveen - blockchain-based social network platform that provides fair rewards for the users' contents*. https://www.liveen.com/. (Accessed on 05/26/2021).

[195] *Datacoup - reclaim your personal data*. https://datacoup.com/. (Accessed on 09/02/2021).

[196] C. M. Bowen and J. Snoke. *Comparative study of differentially private synthetic data algorithms from the nist pscr differential privacy synthetic data challenge*. arXiv preprint arXiv:1911.12704 (2019).

[197] N. Volgushev, M. Schwarzkopf, B. Getchell, M. Varia, A. Lapets, and A. Bestavros. *Conclave: secure multi-party computation on big data*. In *Proceedings of the Fourteenth EuroSys Conference 2019*, pp. 1–18 (2019).

[198] A. Acar, H. Aksu, A. S. Uluagac, and M. Conti. *A survey on homomorphic encryption schemes: Theory and implementation*. ACM Computing Surveys (CSUR) **51**(4), 1 (2018).

[199] J. Tang, A. Korolova, X. Bai, X. Wang, and X. Wang. *Privacy loss in apple's implementation of differential privacy on macos 10.12*. arXiv preprint arXiv:1709.02753 (2017).

[200] J. Lee and C. Clifton. *How much is enough? choosing ε for differential privacy*. In *International Conference on Information Security*, pp. 325–340 (Springer, 2011).

[201] Y. Chen, S. Chong, I. A. Kash, T. Moran, and S. Vadhan. *Truthful mechanisms for agents that value privacy*. ACM Transactions on Economics and Computation (TEAC) **4**(3), 1 (2016).

[202] K. Ligett and A. Roth. *Take it or leave it: Running a survey when privacy comes at a cost*. In *International workshop on internet and network economics*, pp. 378–391 (Springer, 2012).
[203] D. Xiao. *Is privacy compatible with truthfulness?* In *Proceedings of the 4th conference on Innovations in Theoretical Computer Science*, pp. 67–86 (2013).

[204] K. Nissim, C. Orlandi, and R. Smorodinsky. *Privacy-aware mechanism design*. In *Proceedings of the 13th ACM Conference on Electronic Commerce*, pp. 774–789 (2012).

[205] J. Hsu, M. Gaboardi, A. Haeberlen, S. Khanna, A. Narayan, B. C. Pierce, and A. Roth. *Differential privacy: An economic method for choosing epsilon*. In *2014 IEEE 27th Computer Security Foundations Symposium*, pp. 398–410 (IEEE, 2014).

[206] A. Ghosh and A. Roth. *Selling privacy at auction*. In *Proceedings of the 12th ACM conference on Electronic commerce*, pp. 199–208 (2011).

[207] P. Dandekar, N. Fawaz, and S. Ioannidis. *Privacy auctions for recommender systems*. ACM Transactions on Economics and Computation (TEAC) **2**(3), 1 (2014).

[208] A. Roth. *Buying private data at auction: the sensitive surveyor's problem*. ACM SIGecom Exchanges **11**(1), 1 (2012).

[209] L. K. Fleischer and Y.-H. Lyu. *Approximately optimal auctions for selling privacy when costs are correlated with data*. In *Proceedings of the 13th ACM conference on electronic commerce*, pp. 568–585 (2012).

[210] W. Li, C. Zhang, Z. Liu, and Y. Tanaka. *Incentive mechanism design for crowdsourcing-based indoor localization*. IEEE Access **6**, 54042 (2018).

[211] R. Nget, Y. Cao, and M. Yoshikawa. *How to balance privacy and money through pricing mechanism in personal data market*. arXiv preprint arXiv:1705.02982 (2017).

[212] H. Oh, S. Park, G. M. Lee, H. Heo, and J. K. Choi. *Personal data trading scheme for data brokers in iot data marketplaces*. IEEE Access **7**, 40120 (2019).

[213] C. Li, D. Y. Li, G. Miklau, and D. Suciu. *A theory of pricing private data*. ACM Transactions on Database Systems (TODS) **39**(4), 1 (2014).

[214] C. Aperjis and B. A. Huberman. *A market for unbiased private data: Paying individuals according to their privacy attitudes*. Available at SSRN 2046861 (2012).

[215] K. Jung and S. Park. *Privacy bargaining with fairness: Privacy-price negotiation system for applying differential privacy in data market environments*. In *2019 IEEE International Conference on Big Data (Big Data)*, pp. 1389–1394 (IEEE, 2019).

[216] S. Krehbiel. *Choosing epsilon for privacy as a service*. Proc. Priv. Enhancing Technol. **2019**(1), 192 (2019).

[217] T. Zhang and Q. Zhu. *On the differential private data market: Endogenous evolution, dynamic pricing, and incentive compatibility*. arXiv preprint arXiv:2101.04357 (2021).
[218] Z. Jorgensen, T. Yu, and G. Cormode. *Conservative or liberal? personalized differential privacy*. In *2015 IEEE 31St international conference on data engineering*, pp. 1023–1034 (IEEE, 2015).

[219] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. *What can we learn privately?* SIAM Journal on Computing **40**(3), 793 (2011).

[220] J. Tang, A. Korolova, X. Bai, X. Wang, and X. Wang. *Privacy loss in apple's implementation of differential privacy on macos 10.12*. arXiv preprint arXiv:1709.02753 (2017).

[221] J. Lee and C. Clifton. *How much is enough? choosing $\epsilon$ for differential privacy*. In *International Conference on Information Security*, pp. 325–340 (Springer, 2011).

[222] J. Domingo-Ferrer and J. Soria-Comas. *From t-closeness to differential privacy and vice versa in data anonymization*. Knowledge-Based Systems **74**, 151 (2015).

[223] N. Holohan, S. Antonatos, S. Braghin, and P. Mac Aonghusa. $(k, \epsilon)$-anonymity: *k* - anonymity with $\epsilon$-differential privacy. arXiv preprint arXiv:1710.01615 (2017).

[224] J. Hsu, M. Gaboardi, A. Haeberlen, S. Khanna, A. Narayan, B. C. Pierce, and A. Roth. *Differential privacy: An economic method for choosing epsilon*. In *2014 IEEE 27th Computer Security Foundations Symposium*, pp. 398–410 (IEEE, 2014).

[225] A. Ghosh and A. Roth. *Selling privacy at auction*. In *Proceedings of the 12th ACM conference on Electronic commerce*, pp. 199–208 (2011).

[226] A. Roth. *Buying private data at auction: the sensitive surveyor's problem*. ACM SIGecom Exchanges **11**(1), 1 (2012).

[227] L. K. Fleischer and Y.-H. Lyu. *Approximately optimal auctions for selling privacy when costs are correlated with data*. In *Proceedings of the 13th ACM conference on electronic commerce*, pp. 568–585 (2012).

[228] R. Nget, Y. Cao, and M. Yoshikawa. *How to balance privacy and money through pricing mechanism in personal data market*. arXiv preprint arXiv:1705.02982 (2017).

[229] C. Li, D. Y. Li, G. Miklau, and D. Suciu. *A theory of pricing private data*. ACM Transactions on Database Systems (TODS) **39**(4), 1 (2014).

[230] T. Zhang and Q. Zhu. *On the differential private data market: Endogenous evolution, dynamic pricing, and incentive compatibility*. arXiv preprint arXiv:2101.04357 (2021).

[231] K. Jung and S. Park. *Privacy bargaining with fairness: Privacy-price negotiation system for applying differential privacy in data market environments*. In *2019 IEEE International Conference on Big Data (Big Data)*, pp. 1389–1394 (IEEE, 2019).

[232] E. Winter. *The shapley value*. Handbook of game theory with economic applications **3**, 2025 (2002).