# Differentially Private Equilibrium Finding in Polymatrix Games

arXiv: https://arxiv.org/abs/2503.09538 · HTML: https://mlsanity.com/paper/2503.09538/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 37 references that are in the map.
- First posted on arXiv 12 Mar 2025.

## Builds on (most cited first, 19 of 19)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [Differentially Private Distributed Optimization](https://mlsanity.com/paper/1401.2596/) (2014)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [Differentially Private Distributed Convex Optimization via Functional Perturbation](https://mlsanity.com/paper/1512.00369/) (2015)
- [Privacy Attacks in Decentralized Learning](https://mlsanity.com/paper/2402.10001/) (2024)
- [Privacy and Truthful Equilibrium Selection for Aggregative Games](https://mlsanity.com/paper/1407.7740/) (2014)
- [Asymptotically Truthful Equilibrium Selection in Large Congestion Games](https://mlsanity.com/paper/1311.2625/) (2013)
- [Computing Approximate Nash Equilibria in Polymatrix Games](https://mlsanity.com/paper/1409.3741/) (2014)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [Differentially-private Distributed Algorithms for Aggregative Games with Guaranteed Convergence](https://mlsanity.com/paper/2209.01486/) (2022)
- [On Privatizing Equilibrium Computation in Aggregate Games over Networks](https://mlsanity.com/paper/1912.06296/) (2019)
- [Computing the Strategy to Commit to in Polymatrix Games (Extended Version)](https://mlsanity.com/paper/1807.11914/) (2018)

## Abstract (arXiv)

We study equilibrium finding in polymatrix games under differential privacy constraints. Prior work in this area fails to achieve both high-accuracy equilibria and a low privacy budget. To better understand the fundamental limitations of differential privacy in games, we show hardness results establishing that no algorithm can simultaneously obtain high accuracy and a vanishing privacy budget as the number of players tends to infinity. This impossibility holds in two regimes: (i) We seek to establish equilibrium approximation guarantees in terms of Euclidean distance to the equilibrium set, and (ii) The adversary has access to all communication channels. We then consider the more realistic setting in which the adversary can access only a bounded number of channels and propose a new distributed algorithm that: recovers strategies with simultaneously vanishing Nash gap (in expected utility, also referred to as exploitability) and privacy budget as the number of players increases. Our approach leverages structural properties of polymatrix games. To our knowledge, this is the first paper that can achieve this in equilibrium computation. Finally, we also provide numerical results to justify our algorithm.