Summary
Coordinating multiple agents to work together well is a hard problem, especially when trying to maximize their collective benefits. The authors look at using game theory, where each agent picks actions that are best for itself, but in a way that also leads to good overall results. They propose a new method called Truncated Noisy Best-Response (TNBR), allowing agents to pick not only the very best choice but also other good choices nearby, with some randomness. This approach helps avoid unstable situations and ensures that the agents’ overall performance stays good without ever getting too bad. The authors also find an interesting balance: if the method risks some poor safety in certain situations, it guarantees better performance overall.
game theorymulti-agent coordinationsubmodular maximizationNash equilibriumbest responseMarkov chainsperformance boundssafety guaranteesstochastic algorithms
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.