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

Mengda Ji, Genjiu Xu, Jingyun Ge, Mingqiang LiIEEE Transactions on Computational Social Systems 2023 · arXiv

TL;DR

This paper introduces a novel incentive mechanism for federated learning that ensures participants contribute high-quality data and cooperate stably. It achieves this by adapting cooperative game theory concepts (specifically, the "core") and developing an efficient, sampling-based approach to overcome computational challenges and ensure fairness.

What Problem Does This Paper Address?

Federated learning (FL) allows multiple parties to collaboratively train a global model without sharing their raw data, thus preserving privacy. However, a key challenge is incentivizing participants to contribute their best data and to cooperate reliably. Participants are rational and aim to maximize their utility. If they aren't adequately compensated for high-quality data or if there's a risk of others benefiting more without contributing equally, they might:

  1. Provide low-quality or "fake" data: This can degrade the global model's performance.
  2. Not cooperate: They might withhold their data or participate minimally, hindering the FL process.

Existing incentive mechanisms, like those based on VCG (Vickrey-Clarke-Groves) or Shapley values, address some aspects but can be computationally expensive or fail to guarantee stable cooperation in the context of FL's inherent randomness and potential for empty "cores" (a concept from cooperative game theory representing stable payoff allocations). This paper aims to bridge this gap by designing an incentive mechanism that is truthful, individually rational, coalitionally rational, and computationally efficient.

Methods

The authors propose a core-selecting incentive mechanism for federated learning. Here's a breakdown of their approach:

  • Data Sharing Game Model: They first frame federated learning as a cooperative game where participants (players) contribute data (their "type") to train a global model. The server is also a player.
  • Characteristic Function and Core: They define a "characteristic function" that quantifies the worth of any coalition of participants. The "core" is a set of payoff allocations that are stable, meaning no coalition has an incentive to break away.
  • Addressing the Empty Core Problem: In FL, the core can be empty due to randomness or data quality issues. To tackle this, they introduce a relaxed version of the core called the "strong e-core." This allows for a small tolerance ($\epsilon$) for deviations, making the mechanism more robust.
  • Minimizing False Data Benefits: The mechanism is designed to minimize the incentive for participants to submit false data.
  • Efficient Core-Selecting Mechanism: A major contribution is an efficient core-selecting mechanism based on sampling approximation. Instead of evaluating all $2^n$ possible coalitions (which is computationally infeasible for many participants), they sample a subset of coalitions. This significantly reduces computational complexity while still providing a good approximation of the core.
  • Reputation-Based Aggregation: To further improve model quality and address potential issues with noisy data, they incorporate a non-uniform weighted aggregation scheme based on participant reputation, which is updated based on their contributions.

Datasets

The experiments were conducted using the MNIST dataset. The paper mentions using it for training and evaluating logistic regression, multi-layer perceptron (MLP), and convolutional neural network (CNN) models.

Key Insights and Ideas

  • The "Core" as a Stability Guarantee: Applying cooperative game theory's "core" concept provides a strong theoretical foundation for ensuring stable cooperation among participants.
  • Relaxing the Core for Practicality: The "strong e-core" is a crucial adaptation that makes the core concept applicable to the inherent uncertainties and potential instabilities in federated learning.
  • Sampling is Key to Efficiency: The core insight for practical deployment is that approximating the core by sampling coalitions, rather than exhaustively evaluating all possibilities, dramatically reduces computational cost without sacrificing too much accuracy.
  • Truthfulness and Cooperation are Intertwined: The mechanism aims to align individual incentives (maximizing utility) with collective goals (a high-quality global model and stable cooperation).

Key Results

  • Truthful Data Input: Experiments demonstrate that the proposed efficient core-selecting mechanism incentivizes participants to input truthful, high-quality data. The utility of participants decreases when they input noisy or false data.
  • Stable Cooperation: The mechanism effectively promotes stable cooperation among participants.
  • Computational Efficiency: The efficient core-selecting mechanism significantly reduces computational overhead compared to the exact core-selecting mechanism, with run time increasing linearly with the number of participants, as opposed to exponentially.
  • Core Accuracy: Even with a small fraction of sampled coalitions, the resultant surplus vector remains within the $\delta$-probable core, indicating good adherence to core constraints.
  • Comparison to VCG: The efficient core-selecting payment generally performs better than VCG-like payments in satisfying core constraints and achieving higher average accuracy.

Limitations and Future Work

  • Assumption on Data Quality: The mechanism relies on an assumption that deviating from truthful data input is likely to degrade model performance. While they test this with noisy data, more complex forms of data manipulation might require further investigation.
  • Computational Cost of Sampling: While significantly reduced, the sampling-based approach still incurs computational costs for model aggregation and evaluation for sampled coalitions.
  • Future Work: The authors suggest exploring the connection between federated learning and game theory further, developing more sophisticated payment schemes, and investigating the combination of reputation systems with participant selection to further enhance global model performance.

Summary updated

Abstract

Federated learning is a distributed machine learning system that uses participants’ data to train an improved global model. In federated learning, participants collaboratively train a global model, and after the training is completed, each participant receives that global model along with an incentive. Rational participants try to maximize their individual utility, and they will not input their high-quality data truthfully unless they are provided with satisfactory payments based on their contributions. Furthermore, federated learning benefits from the cooperation of participants. Accordingly, how to establish an incentive mechanism that both incentivizes inputting data truthfully and promotes cooperative contributions has become an important issue to consider. In this article, we introduce a data sharing game model for federated learning and employ game-theoretic approaches to design a core-selecting incentive mechanism by utilizing a popular concept in cooperative games, the core. In federated learning, the core can be empty, resulting in the core-selecting mechanism becoming infeasible. To address this issue, our core-selecting mechanism employs a relaxation method and simultaneously minimizes the benefits of inputting false data for all participants. Meanwhile, to reduce the computational complexity of the core-selecting mechanism, we propose an efficient core-selecting mechanism based on sampling approximation that only aggregates models on sampled coalitions to approximate the exact result. Extensive experiments demonstrate that the efficient core-selecting mechanism can incentivize truthful input of high-quality data and promote cooperation effectively, while it reduces computational overhead compared to the core-selecting mechanism.
BibTeX
@article{ji2023efficient,
  author = {Mengda Ji and Genjiu Xu and Jingyun Ge and Mingqiang Li},
  title = {{Efficient Core-Selecting Incentive Mechanism for Data Sharing in Federated Learning}},
  journal = {IEEE Transactions on Computational Social Systems},
  year = {2023},
}
Figure