Algorithm avoids poor coordination outcomes in multi-player games
ABRA: An algorithm which cannot converge to low-quality Nash equilibria
Computer Science and Game Theory
Summary
This paper looks at how groups of players can work together to achieve good results in games where their goals overlap but may compete. The authors focus on a method called ABRA that helps players avoid getting stuck in bad situations where their combined success is low. By adding some randomness and balancing it carefully, ABRA can steer the players toward better outcomes that are always more than half as good as the best possible. The authors tested ABRA in simulations and found it usually keeps the results well above that halfway mark, helping ensure better team coordination.
game theoryNash equilibriummulti-agent coordinationsubmodular objectivesapproximate best responsenoise parameterrationality parameterrecurrent classoptimizationalgorithm convergence
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.