Differentially Private Equilibrium Finding in Polymatrix Games

1. Problem Statement

The paper addresses the challenge of computing Nash Equilibria (NE) or Coarse Correlated Equilibria (CCE) in polymatrix games under Differential Privacy (DP) constraints.

• Context: In multi-agent systems (e.g., financial markets, security games), players' utility functions often contain sensitive private information (e.g., reservation prices). Players must update their strategies toward an equilibrium without revealing these utilities to adversaries who may monitor communication channels.
• The Conflict: Prior work in differentially private equilibrium computation faced a fundamental trade-off: achieving high accuracy (low approximation error) required a large privacy budget (low privacy), and vice versa. Specifically, existing methods failed to simultaneously achieve vanishing error and vanishing privacy budget as the number of players ($N$) increased.
• Goal: To determine the fundamental limits of DP in games and propose an algorithm that breaks the previous trade-off, achieving both high accuracy and strong privacy guarantees as $N \to \infty$.

2. Key Contributions & Methodology

A. Impossibility Results (Hardness)

The authors first establish necessary conditions for success, proving that high accuracy and vanishing privacy are impossible under two specific regimes:

1. Full Channel Access: If an adversary can access all communication channels between players, no algorithm can simultaneously guarantee low exploitability (Nash gap) and a vanishing privacy budget.
2. Euclidean Distance Metric: If the accuracy metric is defined as the Euclidean distance to the equilibrium set (rather than utility-based exploitability), high accuracy and vanishing privacy are impossible even if the adversary accesses only a single channel.
   • Insight: These results highlight that the choice of accuracy metric (exploitability vs. Euclidean distance) and the adversary's scope are critical.

B. Proposed Algorithm: Distributed DP-CCE

The paper proposes Algorithm 1, a distributed iterative algorithm for finding a Coarse Correlated Equilibrium (CCE) in general-sum polymatrix games.

• Mechanism:
  • Players initialize with uniform strategies.
  • In each iteration, players add Gaussian noise to their current strategy and broadcast it to neighbors.
  • Players receive noisy strategies from neighbors, compute their local gradient (based on the sum of interactions with neighbors), and perform a regularized projected gradient descent step.
• Key Innovation (Adaptive Regularization):
  • The algorithm introduces a regularization term $\tau_i$ that is inversely proportional to the player's degree ($|N(i)|$).
  • $\tau_i \propto \frac{1}{|N(i)|}$.
  • Rationale: Players with fewer neighbors (low degree) have gradients that are more sensitive to changes in a single neighbor's utility matrix. Therefore, they require stronger regularization to mask the difference between adjacent games (games differing by one edge's utility). High-degree players naturally aggregate noise, mitigating sensitivity.

C. Theoretical Analysis

The authors analyze the trade-off between accuracy (exploitability) and privacy (Rényi DP budget) for two graph topologies:

1. Dense Graphs: When the graph is dense (average degree scales with $N$), the algorithm achieves both accuracy and privacy budget that scale as $O(N^{-p})$ for some $p > 0$. As $N \to \infty$, both error and privacy budget vanish.
2. Sparse Graphs: When the graph is sparse (max degree is constant), the algorithm leverages the graph's structure. Changes in utility matrices propagate slowly through the network. The privacy budget vanishes as $N \to \infty$ because most players are far from the perturbed edge, and their updates remain identical in adjacent games for many iterations.

Theorem 8.1 (Main Result): For any desired accuracy $\zeta_0$ and privacy budget $\epsilon_0$, there exists a sufficiently large number of players $N$ such that the algorithm achieves both simultaneously. This contrasts with prior work where improving one metric inevitably degraded the other regardless of $N$.

3. Experimental Results

The authors validate their theory with numerical experiments comparing their algorithm against a baseline (adapted from Huang et al., 2015).

• Setup: Experiments conducted on both dense (Erdős–Rényi, clustered) and sparse graphs with varying numbers of players ($N$) and action set sizes ($A$).
• Findings:
  • Dense Graphs: As $N$ increases, the proposed algorithm's exploitability decreases and the privacy budget decreases. In contrast, the baseline's exploitability increases or stagnates.
  • Sparse Graphs: The privacy budget decreases as $N$ increases. While exploitability reduction is slower due to convergence rates, it still outperforms the baseline in maintaining low privacy costs.
  • Conclusion: The empirical results confirm that the proposed method successfully decouples accuracy and privacy constraints in large-scale settings.

4. Significance

• Theoretical Breakthrough: This is the first work to demonstrate that in polymatrix games, it is possible to achieve simultaneously vanishing accuracy error and vanishing privacy budget as the population size grows. It overturns the prevailing belief that a strict trade-off is unavoidable.
• Structural Exploitation: The paper highlights the importance of leveraging game structure (specifically the graph topology and the "aggregative" nature of polymatrix utilities) to cancel out noise, rather than treating the game as a black-box optimization problem.
• Practical Implications: The results suggest that in large-scale decentralized systems (like large markets or sensor networks), privacy-preserving equilibrium computation is not only feasible but becomes more efficient and private as the system scales.
• Limitations & Future Work: The current framework is specific to polymatrix games. Extending these structural insights to normal-form games or extensive-form games remains an open direction.

Summary of Technical Trade-offs

Feature	Prior Work	This Paper (Proposed)
Accuracy Metric	Often Euclidean Distance	Exploitability (Nash Gap)
Adversary Model	Often Full Channel Access	Bounded Channel Access (Realistic)
Scaling with $N$	Accuracy $\uparrow$ or Privacy $\uparrow$ (Trade-off)	Both Accuracy $\downarrow$ and Privacy $\downarrow$
Key Mechanism	Uniform Noise/Regularization	Degree-Adaptive Regularization

In conclusion, this paper establishes the theoretical limits of private equilibrium finding and provides a constructive algorithm that achieves "perfect" privacy and accuracy in the limit of large populations by exploiting the specific structural properties of polymatrix games.