Differentially Private Equilibrium Finding in Polymatrix Games
This addresses privacy-preserving game theory for multi-agent systems, with incremental contributions in specific adversarial scenarios.
The paper tackles equilibrium finding in polymatrix games under differential privacy constraints, showing that high accuracy with vanishing privacy budget is impossible under certain adversarial settings, and develops a distributed algorithm that achieves vanishing Nash gap and privacy budget as players increase.
We study equilibrium finding in polymatrix games under differential privacy constraints. To start, we show that high accuracy and asymptotically vanishing differential privacy budget (as the number of players goes to infinity) cannot be achieved simultaneously under either of the two settings: (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. Then, assuming the adversary has access to a constant number of communication channels, we develop a novel 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.