Efficient Core-selecting Incentive Mechanism for Data Sharing in Federated Learning

In recent years, the success in the field of machine learning has been mainly attributed to the collection and use of massive amounts of data. Although the demand for data in machine learning is growing, collecting and using data are still difficult. On the one hand, data owners, or participants in federated learning, have recognized the worth of their data, so they are reluctant to provide it for free. On the other hand, privacy protection regulations such as the General Data Protection Regulation (GDPR) impose strict restrictions on access to private data [1]. To address the problem of privacy protection, federated learning has been proposed, which is a cooperative framework based on collaborative training and model sharing [2]. In federated learning, the data of participants is stored locally and used to train local models. Then these local models are aggregated by a server to create a global model. Since federated learning does not require participants to upload data to the server, it prevents possible privacy leaks during the uploading, saving, and model training processes. In recent years, federated learning has attracted attention in many fields such as healthcare, finance, and the Internet of Things [3, 4, 5].

In federated learning, economic incentives are crucial for motivating participants to cooperatively train a global model [6]. In practice, participants are reluctant to truthfully input their worthy data unless they receive satisfactory payments for their high-quality data. In addition, the global model relies on the stable cooperation of all participants and the server. Therefore, a desirable incentive mechanism should also take into account cooperative contributions and truthfulness. Along with the development of federated learning, research on incentive mechanisms has attracted many scholars’ interests [7, 8, 9]. Many methods are used to design incentive mechanisms for federated learning, including auction [10, 11, 12], contract theory [13], and matching theory [14]. Game theory investigates strategic interactions among players or agents, which provides a framework to analyze the strategic behaviors of participants in federated learning. Therefore, more and more incentive mechanisms have used game-theoretic methods to design incentive mechanisms in federated learning. Such methods include Stackelberg game [15, 16], evolutionary game [17, 18], VCG-based (Vickrey-Clarke-Groves) mechanisms [19, 20, 21, 22, 23], and Shapley value [24, 25, 26, 27].

Many existing studies in federated learning and machine learning focus on designing incentive mechanisms to provide economic incentives for participants. The VCG (Vickrey–Clarke–Groves) mechanism is famous in game theory and mechanism design theory because it satisfies the properties of incentive compatibility and individual rationality. Due to its desirable properties, the VCG mechanism motivates participants to report their private information truthfully. Therefore, the VCG-based incentive mechanism has been widely used in machine learning and federated learning [19, 20, 21, 22, 23]. To reduce computational complexity, a faithful federated learning (FFL) mechanism was proposed to compute the VCG-like payment via an incremental computation [23]. It effectively reduces computational complexity, making it suitable for large-scale training scenarios. The utility of participants under the VCG-based mechanism is equal to their marginal contribution, which motivates them to input high-quality data. In addition to computing the VCG payment, allocating payments or profits based on cooperative contributions to promote stable cooperation is also a challenge in federated learning.

Cooperative game theory offers various solution concepts to determine how benefits should be allocated. The Shapley value is a classic solution in cooperative game theory with desirable properties and interpretability, which has been widely adopted in incentive mechanisms for machine learning and federated learning [24, 28, 29, 26, 27, 25]. These methods allocate payments according to the marginal surplus of each participant, which reflects the combined worth of participants’ data. Except for Shapley value, the core is also a widely used solution concept in cooperative game theory [30, 31, 32]. It represents a stable and fair allocation set that satisfies the properties of individual rationality and coalitional rationality, which is different from Shapley value. The allocation element in the core ensures that no player or coalition has the motivation to deviate from cooperation. Due to its desirable properties, the core has been widely applied in many fields such as spectrum auctions, crowdsourcing, and transportation scenarios [33, 34, 35]. Recently, the core has also been used in federated learning to evaluate the cooperative contributions of participants [36, 37]. These methods fully analyze the existence of the core and provide a fair allocation scheme. Nevertheless, the core is a set solution that cannot provide a unique optimal solution, and the advantages of the VCG payment or marginal contribution have not been fully considered by these methods. Core-selecting mechanisms, often referred to as core-selecting auctions, are designed to ensure that the resulting allocation is in the core of the associated cooperative game [38]. Therefore, we will use the core-selecting mechanism and adopt some improvements to address potential issues that may arise in federated learning. Additionally, it is worth noting that determining the exact core in federated learning also faces computational difficulties because it requires computing additional $2^{n}$ models [39].

As shown in Table I, we give the comparison table to highlight the differences of existing incentive mechanisms.

In this paper, we propose an efficient core-selecting incentive mechanism for federated learning. First, we introduce a data sharing game for federated learning. Then we introduce a core-selecting incentive mechanism that combines the advantages of both the VCG-like payment and the core, which can promote stable cooperation among players and also motivate participants to input their high-quality data. Different from the classical core-selecting mechanism, we adopt a relaxation on the core to deal with the randomness in federated learning. Since the core-selecting incentive mechanism requires exponential time to aggregate and evaluate additional models in federated learning, it is difficult to compute the exact solution. To address this, we propose an efficient core-selecting mechanism based on sampling approximation that significantly reduces computational complexity. This mechanism adjusts the aggregation weight of participants based on their historical contributions to avoid the impact of low-quality data. In addition, we verify the theoretical results of the proposed mechanism in experiments. Further experiments show that the efficient core-selecting mechanism can motivate participants to truthfully input high-quality data and promote stable cooperation, while it reduces computational overhead compared to the core-selecting mechanism.

Our contributions are as follows:

1. 1.

   We introduce a data-sharing game for federated learning to study participants’ strategic behaviors. Based on the outcomes of this data-sharing game, we define the characteristic function and the core to measure participants’ cooperative contributions.

2. 2.

   We employ a core-selecting mechanism for federated learning, which aims to find the optimal payment based on the core to incentivize participants’ cooperation. Due to the impact of low-quality data or overfitting on the global model, the core may be empty. To address this issue, our core-selecting mechanism employs a relaxed version of the core, strong $\epsilon$-core, and minimizes the benefits of inputting false data.

3. 3.

   To avoid the core-selecting incentive mechanism implementing in an exponential time to aggregate and evaluate additional models in federated learning, we propose an efficient core-selecting incentive mechanism based on sampling approximation that significantly reduces computational complexity. This incentive mechanism aggregates new global models based on the historical contributions of participants.

The rest of this paper is organized as follows. Section II introduces the background of federated learning and formulates the problem. Section III introduces the truthful incentive mechanism for federated learning. The core-selecting mechanism is proposed in Section IV. The efficient core-selecting mechanism and its theoretical results are proposed in Section V. Experiments are given in Section VI to illustrate the performance of our method. Section VII concludes this paper.

We first introduce the background of federated learning in Section II-A, and then introduce the necessary notions and definitions in Section II-B.

The VCG (Vickrey–Clarke–Groves) mechanism is famous in game theory and mechanism design theory, which satisfies the property of incentive compatibility, i.e., telling the truth is a dominant strategy for all players [46]. The VCG mechanism was previously employed by Nix and Kantarcioglu in the context of distributed machine learning [20], and they have proposed a critical assumption in their work. Meng Zhang et al. have also investigated VCG-based mechanisms in the context of federated learning and proposed a VCG-like payment to approximate VCG payments via an incremental computation. In this section, with minor modifications, we also implement this VCG-based mechanism for our incentive mechanism framework. This truthful incentive mechanism will serve as the foundation for the core-selecting mechanism in the next section.

In federated learning, a commonly used assumption is that each dataset $D_{i}$ and the test dataset $D_{t}$ are sampled from a real distribution $\mathcal{D}$. During the training process, participant $i$ actually inputs an untruthful dataset $\hat{D}_{i}=\{\hat{x}_{ij},\hat{y}_{ij}\}_{j=1}^{m}$, where $\hat{D}_{i}$ deviates from the real probability distribution $\mathcal{D}$ and follows a probability distribution with artificial errors, i.e.,  $\mathcal{D}+\delta$.

Let $f=F(D)$ and $\hat{f}=F(\hat{D}_{i}\cup D_{-i})$, the expected risks of these two models on distribution $\mathcal{D}$ are denoted as $E_{\mathcal{D}}(f)=\int\mathcal{L}(f(x),y)d\mathcal{D}(x,y)$ and $E_{\mathcal{D}}(\hat{f})=\int\mathcal{L}(\hat{f}(x),y)d\mathcal{D}(x,y)$ where $\mathcal{L}$ is a per-sample loss function. Generally, $E_{\mathcal{D}}(f)\leq E_{\mathcal{D}}(\hat{f})$ holds because model $f$ fits the data points under the real distribution $\mathcal{D}$, whereas model $\hat{f}$ fits the noisy data points. As a result, on the test dataset $D_{t}\sim\mathcal{D}$, the performance of $F(D)$ will be better than that of $F(\hat{D}_{i}\cup D_{-i})$. Mathematically, this can be expressed as

where $I$ is a non-negative, increasing function and $dist$ is a distance function of the dataset.

This assumption is similar to the assumption proposed by Nix and Kantarcioglu [20]. It means that deviating from a real data will make a bad model’s performance more likely. Obviously, a truthful input will not decrease the model accuracy for each player $i$, and more input of truthful data will improve model performance. Nix and Kantarcioglu also mentioned the possible effects of the overfitting phenomenon. In order to verify the validity of this assumption in the context of federated learning, we will test it by inputting a noisy dataset in Section VI.

The truthful incentive mechanism is easy to operate. Given an input $\hat{D}$, each player $i\in N$ receives a global model $F(\hat{D})$ and a VCG-like payment, which is defined as

To compute the payments for all participants, additional $n$ models need to be aggregated and evaluated. Note that it is not strictly a classic VCG mechanism. The difference between this mechanism and the classical VCG mechanism is that the selection of players is not executed here. The reasons are twofold. Firstly, in order to find the optimal model and achieve a selection of players, $2^{n}$ times of aggregation and $2^{n}$ times of evaluation for all potential selection schemes are required, which are computationally expensive. Secondly, only after a participant is selected can we obtain its local model and evaluate it. Thus, the selection of participants is not considered in this paper. Although the selection is not performed by this mechanism, it still satisfies incentive compatibility.

The VCG-like payment measures the difference between the global model, i.e., $F(\hat{D})$, and the model without his input, i.e., $F(D_{-i})$. In economics, allocating benefits by marginal contributions encourages participants to adopt decisions and behaviors that have a positive impact on team benefits. If participant $i$ inputs data truthfully, its utility will be equal to its marginal contribution $w(N)-w(N\backslash i)$, which encourages participants to input high-quality data to improve $w(N)$. This truthful incentive mechanism, or the VCG-like payment, meets the requirements of the first two properties mentioned in Section II.

While the truthful incentive mechanism can motivate players to input their high-quality data, it fails to consider cooperation among all players and the server. The core is a classic set solution in cooperative games. In this section, we define the core based on the outcomes of the proposed data sharing game. The core cannot be guaranteed to be nonempty in federated learning. To address this issue, we adopt a relaxed version of the core, strong $\epsilon$-core. Then, we propose a core-selecting mechanism that selects a solution minimizing participants’ benefits of untruthful input within the strong $\epsilon$-core.

Let $\pi_{i}=v_{i}(F(\hat{D}),\hat{D}_{i})+p_{i}$ be the observable surplus of player $i$. It does not involve the private information of players and can be computed by the server. Instead of the true utility $u_{i}$, the core is defined over surplus $\pi_{i}$ because the server does not have any knowledge on the players’ original data $D_{i}$, without a guarantee on the incentive compatibility [38]. The true utility and the incentive for participants to input data truthfully will be discussed later. The server’s surplus is defined as $\pi_{0}=u_{0}=b_{0}-\sum_{i\in N}p_{i}$.

This implies that when the server selects a vector from the core, there is no motivation for any player $k$ to form a coalition $S$ with other players to deviate from coalition $N$ for any possible improvement of their total utility.

The classical core-selecting mechanism, as shown in quadratic programming (18) and Fig. 3, aims to find a surplus from the core, which is closest to the surplus vector determined by the VCG-like payment, $\pi^{VCG}=v_{i}(F(\hat{D}),\hat{D}_{i})+p_{i}^{VCG}$. It combines the advantages of the VCG-based mechanism and the core.

Intuitively speaking, with more input, $F(D)$ should perform better than $F(D_{S})$ and the core should be a nonempty set. However, there are some issues in practice. Firstly, in practical implementation, we cannot repeat training infinitely to accurately approximate the expected value of accuracy. Additionally, model overfitting may also result in $E[A(F(D))]<E[A(F(D_{T}))]$ and even $w(T)>w(N)$ holding for a coalition $T\subset N$. Both two issues result in an empty core, and the core-selecting cannot be used directly. To address this, we employ a non-empty set solution similar to the core, strong $\epsilon$-core, which adopts a relaxation $\epsilon$ to the core [47]. The strong $\epsilon$-core is defined as

In the concept of strong $\epsilon$-core [47], $\epsilon$ represents a minor perturbation or a threshold for deviation. If a coalition $S\subset N$ can increase its utility by more than the threshold, i.e., $\epsilon$, through deviating from $N$, then the coalition will choose to deviate and not collaborate with the participants in $N\backslash S$. The strong $\epsilon$-core of a game can be interpreted as the set of all allocation vectors that cannot be improved upon by any coalition if one imposes a cost of $\epsilon$ in all cases where a nontrivial coalition is formed [47].

For convenience, the surplus vector in the strong $\epsilon$-core, $\pi$ is called core surplus vector, and the surplus vector determined by the VCG-like payment, $\pi^{VCG}$ is also called VCG surplus vector. The strong $\epsilon$-core is a set solution, while the VCG surplus vector is a single point solution. Obviously, increasing $\epsilon$ can expand the strong $\epsilon$-core. A sufficiently large $\epsilon$ can ensure the VCG surplus vector is in the strong $\epsilon$-core.

The above theorem provides a lower bound on $\epsilon$ to ensure that the VCG surplus vector is in the strong $\epsilon$ core. If a very small lower bound can guarantee that the VCG surplus is in the core, we can directly employ the VCG-like payment to incentivize players. In the theorem mentioned above, this lower bound is difficult to calculate. Although we are uncertain whether the VCG surplus is in the $\epsilon$-core, we still have another way to comprehensively consider the VCG surplus and the strong $\epsilon$-core.

Theorem 4 shows that by reducing the distance between $p_{i}$ and $p_{i}^{VCG}+\epsilon$, we can limit the benefits of inputting false data. In other words, although we cannot find a VCG surplus vector in the strong $\epsilon$-core, reducing the distance between $p_{i}$ and $p_{i}^{VCG}+\epsilon$ as much as possible can still motivate participants to input data truthfully. Eventually, our core-selecting incentive mechanism for federated learning is proposed as follows.

1. Step 1:

   Before computing the payments, model $F(\hat{D}_{S})$ is trained and evaluated for each coalition $S\subseteq N$. Meanwhile, the characteristic values are calculated as

   $$w(S)=\sum_{i\in S}v_{i}(F(\hat{D}_{S}),\hat{D}_{i})+b_{0},\ \ \ \ S\subseteq N.$$

   (29)

2. Step 2:

   Next, the VCG surplus is determined as

   $$\pi_{i}^{VCG}=w(N)-w(N\backslash\{i\}),\ \ \ \ i\in N.$$

   (30)

3. Step 3:

   The following quadratic programming is solved to give a solution $\pi^{*}$.

   	$\displaystyle\min$	$\displaystyle\ \ \sigma^{2}=\sum_{i\in N}(\pi_{i}-\pi_{i}^{VCG}+\epsilon)^{2}$			(31)
   	s.t.	$\displaystyle\ \ \epsilon\geq 0,$
   		$\displaystyle\ \ \sum_{i\in N}\pi_{i}+\pi_{0}=w(N),$
   		$\displaystyle\ \ \sum_{i\in S}\pi_{i}+\pi_{0}+\epsilon\geq w(S),\ \ \ \$	$\displaystyle S\subseteq N,$
   		$\displaystyle\ \ \pi_{i}\geq 0,$	$\displaystyle i\in N\cup\{0\},$

4. Step 4:

   Finally, the payments given to participants are calculated as

   $$p_{i}=\pi_{i}^{*}-v_{i}(F(\hat{D}),\hat{D}_{i}),\ \ \ \ i\in N.$$

   (32)

The above procedure determines the observable surplus vector that we want to achieve. In particular, if the VCG surplus vector is in the $\epsilon$-core, the solution of the core-selecting incentive mechanism is equal to the VCG surplus vector. Conservative participants are prefer to input data truthfully because the payment under the core-selecting mechanism may be equal to or very close to that under the truthful incentive mechanism. Even if aggressive participants attempt to input false data, Theorem 4 indicates that the additional benefits obtained by inputting false data are also minimized. Since the selected surplus vector is taken from the strong $\epsilon$-core and $\epsilon$ is also reduced in the programming, there is little incentive for any coalition or any participant to deviate from cooperation.

The proposed core-selecting mechanism is an ideal mechanism for federated learning. However, exact computation of the core-selecting mechanism requires evaluating the additional model with $2^{n}$ times to obtain the characteristic values before solving the quadratic programming, which is computationally expensive. To address this, our method is to sample a relatively small number of coalitions from a probability distribution, and compute the desired solution on the sampled coalitions.

In our method, a set of coalition $\mathcal{S}=\{S_{1},S_{2},\cdots,S_{m}\}$ is sampled from a probability distribution $\mathcal{D}$ and the characteristic values of these coalitions are given by aggregating and evaluating $m$ additional models. Then, solving the core-selecting quadratic programming over $m$ coalitions instead of $2^{n}$ coalitions gives an approximate core surplus vector, resulting in the following quadratic programming.

The solution $\hat{\pi}$ of the above quadratic programming may not satisfy all $2^{n}$ core constraints. In order to analyze its properties, we consider that $\hat{\pi}$ satisfies each core constraint with a probability, and similar to [39], we introduce the definition of $\delta$-probable core as follows.

Given any coalition $S$ drawn from $\mathcal{D}$, the core constraint is violated with probability at most $\delta$. For the exact core-selecting surplus $\pi^{*}$, we have

The definition of $\delta$-probable core can explain the constraints of approximate quadratic programming (33). The next question we focus on is how to determine the sample size $m$. The following theorem 5 answers this question. Before presenting this theorem, we introduce two known lemmas [48].

Theorem 5 provides a theoretical result for our approximate method. The above incentives reasonably evaluate the contributions of participants. The VCG surplus can be seen as a marginal contribution, and surplus $\hat{\pi}$ can be seen as a contribution based on the approximate strong $\epsilon$-core.

Next, in order to aggregate and obtain a better model, we employ a non-uniform weighted aggregation scheme. Reputation is widely used to measure the reliability of a participant based on its past behavior [49, 50, 8]. The participant with a better reputation will be assigned a greater weight. At each round $t$, the surplus $\hat{\pi}_{i}^{t}$ can be determined. We calculate the reputation of each participant $i$ based on its contribution from round $1$ to round $t$. Let $R_{i}^{t}$ denote participant $i$’s reputation. It can be computed as

where $\phi_{0}$ is a small positive number representing the lower bound. In the next round $t+1$, we will use $R_{i}^{t}$ to aggregate the new global model as