Differentially Private Equilibrium Finding in Polymatrix Games
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Computing the Strategy to Commit to in Polymatrix Games (Extended Version)
Leadership games provide a powerful paradigm to model many real-world settings. Most literature focuses on games with a single follower who acts optimistically, breaking ties in favour of the leader. Unfortunately, for r…
Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability
Self-play is a technique for machine learning in multi-agent systems where a learning algorithm learns by interacting with copies of itself. Self-play is useful for generating large quantities of data for learning, but h…
Aggregate Fictitious Play for Learning in Anonymous Polymatrix Games (Extended Version)
Fictitious play (FP) is a well-studied algorithm that enables agents to learn Nash equilibrium in games with certain reward structures. However, when agents have no prior knowledge of the reward functions, FP faces a maj…
Asynchronous Gradient Play in Zero-Sum Multi-agent Games
Finding equilibria via gradient play in competitive multi-agent games has been attracting a growing amount of attention in recent years, with emphasis on designing efficient strategies where the agents operate in a decen…
Multi-Player Zero-Sum Markov Games with Networked Separable Interactions
We study a new class of Markov games, \emph(multi-player) zero-sum Markov Games} with \emph{Networked separable interactions} (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent seque…
Decision MakingSequential Decision Making