Distributed Learning with Strategic Users: A Repeated Game Approach

Abdullah Basar Akbay, Junshan Zhang

Abstract

Distributed learning systems, such as Federated Learning, typically operate under the assumption that participating devices are obedient. However, in practice, users are strategic agents who may prioritize their own privacy and computational costs over global model accuracy. This paper addresses the challenge of incentivizing cooperation in distributed learning by modeling the process as a repeated game. We propose the SGD-SU framework, which utilizes Adaptive Zero-Determinant (ZD) strategies to allow a central Fusion Center to unilaterally incentivize selfish users to contribute high-quality data. Our theoretical analysis and experimental evaluations on the KDD-Cup 04 and MNIST datasets demonstrate that this mechanism ensures model convergence and maintains high performance against a variety of user strategies.

Introduction

The success of distributed learning relies on the active participation of numerous edge devices. While standard protocols assume these users follow instructions perfectly, real-world participants are often rational and self-interested. Providing accurate stochastic gradients incurs costs in terms of energy, computation, and privacy. Without proper incentives, strategic users may "defect" by submitting low-effort noise or withholding data entirely.

A significant hurdle in managing such behavior is the inability of the central Fusion Center (FC) to directly verify the integrity of reported gradients, which are inherently noisy and derived from private local data. This information asymmetry often leads to a non-cooperative Nash equilibrium where the global model fails to converge.

Methodology: The SGD-SU Framework

To overcome the problem of strategic defection, we introduce SGD-SU (Stochastic Gradient Descent with Strategic Users). This framework treats the iterative training process as a sequence of games between the FC and the users.

System model and payoff matrix for the repeated game between the Fusion Center and strategic users.

Repeated Game and ZD Strategies

The interaction is modeled as a $T$-round repeated game. In each round, a user $k$ decides whether to cooperate (send a valid gradient) or defect (send noise). The FC, in turn, decides whether to provide a reward. The core of our approach is the use of Adaptive Zero-Determinant (ZD) strategies. ZD strategies enable one player to unilaterally enforce a linear relationship between their own payoff and their opponent's payoff. We generalize these strategies to accommodate the time-varying stochastic errors inherent in gradient estimation.

Joint Estimation and Incentive Alignment

Because the FC cannot observe the user's action directly, it employs a linear classifier to estimate whether a reported gradient is informative or merely noise. Based on this classification, the FC adjusts its reward probabilities. By carefully tuning the ZD strategy parameters, the FC ensures that the user's utility-maximizing "best response" is full cooperation, effectively aligning individual incentives with the global goal of model training.

Experimental Evaluation

We evaluated the SGD-SU framework using two benchmarks: the KDD-Cup 04 (Physics) dataset for binary classification and the MNIST dataset for handwritten digit recognition via a neural network. We tested the FC's performance against several common user strategies, including Full Cooperation, Stubborn, Tit-for-Tat, and Pavlov (Win-Stay, Lose-Shift).

Key Results

Our results confirm that the SGD-SU framework successfully incentivizes cooperation and ensures model convergence.

Performance metrics including optimality gap, cooperation probability, training loss, and testing accuracy across different reward settings.
  1. Provable Convergence: Theoretical proofs and experimental data show that the optimality gap decreases over time, matching the convergence rates of standard mini-batch SGD.
  2. Incentive Robustness: Under the adaptive ZD strategy, the probability of user cooperation remains high or stabilizes at a cooperative steady state, even for complex strategies like Pavlov, which are sensitive to misclassification.
  3. High Accuracy: The system achieved high testing accuracy on MNIST and low training loss on KDD-Cup 04 across both "extortionate" and "equalizer" reward configurations.

Conclusion and Future Work

This work demonstrates that game-theoretic mechanisms can effectively manage strategic behavior in distributed learning. By using Adaptive ZD strategies, the Fusion Center can enforce cooperation without needing to directly verify private data. Future research will address the "vanishing gradient" problem, where gradients naturally shrink as the model nears the optimum, making cooperation detection more difficult. Additionally, we aim to extend this framework to handle Byzantine (malicious) users and more heterogeneous user populations.

Summary updated

Abstract

We consider a distributed learning setting where strategic users are incentivized, by a cost-sensitive fusion center, to train a learning model based on local data. The users are not obliged to provide their true gradient updates and the fusion center is not capable of validating the authenticity of reported updates. Thus motivated, we formulate the interactions between the fusion center and the users as repeated games, manifesting an under-explored interplay between machine learning and game theory. We then develop an incentive mechanism for the fusion center based on a joint gradient estimation and user action classification scheme, and study its impact on the convergence performance of distributed learning. Further, we devise an adaptive zero-determinant (ZD) strategy, thereby generalizing the celebrated ZD strategy to the repeated games with time-varying stochastic errors. Theoretical and empirical analysis show that the fusion center can incentivize the strategic users to cooperate and report informative gradient updates, thus ensuring the convergence.
BibTeX
@inproceedings{akbay2022distributed,
  author = {Abdullah Basar Akbay and Junshan Zhang},
  title = {{Distributed Learning with Strategic Users: A Repeated Game Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i6.20543},
}
Figure