For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria
Although it has been known since the 1970s that a globally optimal strategy profile in a common-payoff game is a Nash equilibrium, global optimality is a strict requirement that limits the result's applicability. In this work, we show that any locally optimal symmetric strategy profile is also a (global) Nash equilibrium. Furthermore, we show that this result is robust to perturbations to the common payoff and to the local optimum. Applied to machine learning, our result provides a global guarantee for any gradient method that finds a local optimum in symmetric strategy space. While this result indicates stability to unilateral deviation, we nevertheless identify broad classes of games where mixed local optima are unstable under joint, asymmetric deviations. We analyze the prevalence of instability by running learning algorithms in a suite of symmetric games, and we conclude by discussing the applicability of our results to multi-agent RL, cooperative inverse RL, and decentralized POMDPs.
Code (1)
Similar Papers 제목 키워드 기반
On the coordination efficiency of strategic multi-agent robotic teams
We study the problem of achieving decentralized coordination by a group of strategic decision makers choosing to engage or not in a task in a stochastic setting. First, we define a class of symmetric utility games that e…
Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models
Nash equilibria provide a principled framework for modeling interactions in multi-agent decision-making and control. However, many equilibrium-seeking methods implicitly assume that each agent has access to the other age…
An algorithmic solution to the Blotto game using multi-marginal couplings
We describe an efficient algorithm to compute solutions for the general two-player Blotto game on n battlefields with heterogeneous values. While explicit constructions for such solutions have been limited to specific, l…
Complexity Aspects of Fundamental Questions in Polynomial Optimization
In this thesis, we settle the computational complexity of some fundamental questions in polynomial optimization. These include the questions of (i) finding a local minimum, (ii) testing local minimality of a point, and (…
On the relation between Sion's minimax theorem and existence of Nash equilibrium in asymmetric multi-players zero-sum game with only one alien
We consider the relation between Sion's minimax theorem for a continuous function and a Nash equilibrium in an asymmetric multi-players zero-sum game in which only one player is different from other players, and the game…