Algorithm avoids low quality outcomes in multi-agent coordination games
ABRA: An algorithm which cannot converge to low-quality Nash equilibria
Computer Science and Game Theory
Summary
When multiple decision-makers try to work together to achieve the best outcome, some stable solutions can be poor. The paper studies a new algorithm named ABRA that uses a bit of randomness and control to prevent settling on bad stable solutions. The authors prove that ABRA will not end up stuck on solutions that are worse than half of the best possible overall result. Their simulation tests also show ABRA usually performs well above this halfway mark.
What this means in practice
- •For multi-agent system designers: Improve coordination algorithms by using ABRA to avoid poor stable outcomes in collaborative multi-agent problems.
- •For distributed control engineers: Implement ABRA to ensure control strategies avoid low-performance equilibria when multiple controllers coordinate on submodular objectives.
Authors
Vartika Singh, Philip N. Brown
Abstract
We consider a game theoretic approach to solve multi-agent coordination problems with submodular objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal. A recent work further shows that the equilibria which achieve this worst-case bound are not stable. Leveraging this, we design an Approximate Best Response Algorithm (ABRA) governed by a noise parameter and a rationality parameter. The noise allows ABRA to escape the bad equilibria and the rationality parameter balances any degradation in the objective function caused by the noise. We show for any two-player game that if ABRA converges to a Nash equilibrium, its system objective value is strictly more than 50% of optimal plus a term controlled by the noise parameter. Otherwise, ABRA converges to some recurrent class: if a recurrent class contains any action profile yielding system objective less than 50% of the optimal, the class must also contain either the optimal action profile or an action profile yielding system objective strictly more than 50\% of the optimal by the same amount in addition to a factor controlled by noise parameter. The time that ABRA spends in such action profiles can be controlled using the rationality parameter. Using numerical simulations, we show that the minimum expected objective function is typically well above half of the optimal.