Differentially Private Distributed Algorithms for Aggregative Games Over Directed Graphs With Linear Convergence.

Area of Science:

• Distributed Systems
• Game Theory
• Cybersecurity

Background:

• Agents' cost functions in aggregative games contain sensitive information.
• Distributed Nash equilibrium (NE) seeking requires privacy preservation over directed graphs.

Purpose of the Study:

• To develop a differentially private algorithm for distributed NE seeking over directed graphs.
• To achieve linear convergence while satisfying differential privacy requirements.
• To characterize the tradeoff between convergence accuracy and privacy budget.

Main Methods:

• A novel differentially private algorithm using decaying Laplace noise.
• Establishing sufficient conditions for linear convergence via step sizes and convex combination parameters.
• Analyzing differential privacy without assuming bounded gradients.

Main Results:

• The algorithm achieves linear convergence and differential privacy.
• A quantitative relationship between convergence accuracy and privacy budget is characterized.
• Under specific conditions, the cumulative privacy budget is finite, and the algorithm converges to the exact NE.

Conclusions:

• The proposed algorithm effectively finds Nash equilibrium in privacy-sensitive distributed settings.
• It demonstrates superior convergence performance compared to existing methods.
• The study provides a framework for privacy-preserving distributed optimization.