Game theory algorithms coordinate agents safely with performance guarantees
Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees
Computer Science and Game TheoryMultiagent Systems
Summary
Multi-agent coordination problems often involve deciding how groups of agents should work together to achieve the best outcome. The authors study a special kind of mathematical game where agents try to maximize a goal known to have solutions close to the best possible. They introduce new algorithms that let agents pick good actions more flexibly, avoiding very bad outcomes while ensuring good performance. These algorithms come with safety guarantees that bad situations won’t happen and performance guarantees that good situations will occur.
What this means in practice
- •For robotic fleet operators: Use the algorithms to safely coordinate multiple robots achieving near-optimal tasks with guarantees against very poor decisions.
- •For distributed system engineers: Design asynchronous agent strategies to manage resources with provable performance and safety in decentralized networks.
A theory result. No direct application yet.
Authors
Vartika Singh, Philip N. Brown
Abstract
We consider a game theoretic approach to solve multi-agent coordination problems with submodular maximization objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal, but that the equilibria which achieve this worst-case bound are not stable. To exploit this instability, we propose a family of algorithms which we call Truncated Noisy Best-Response (TNBR) Algorithms. These algorithms are flexibly characterized by agents asynchronously and stochastically selecting actions from a neighbourhood of their best response payoffs. We compute bounds on the recurrent classes of TNBR algorithms' associated Markov chains. Our bounds fall into two categories: first, "Performance" bounds ensure that TNBR algorithms always have a high-value recurrent state; second, "Safety" bounds ensure that TNBR algorithms never have arbitrarily-bad recurrent states. Furthermore, these two types of bounds are linked by a waterbed-like effect: every game with a poor Safety guarantee necessarily has a favorable Performance guarantee.