Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models
This addresses the challenge of equilibrium-seeking in multi-agent systems without requiring full mutual knowledge, which is often unrealistic in practice, though it is incremental as it builds on existing gradient-based methods.
The paper tackles the problem of finding Nash equilibria in two-player constrained games with asymmetric information, where one player only knows its own objective and constraints while the other is accessible via a best-response map. It proposes an asymmetric projected gradient descent-best response iteration, proving global linear convergence for exact maps and showing that iterates enter an O(ε) neighborhood of the equilibrium when the map has bounded error ε.
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 agents' objectives and constraints, an assumption that is often unrealistic in practice. This letter studies a class of asymmetric-information two-player constrained games with decoupled feasible sets, in which Player 1 knows its own objective and constraints while Player 2 is available only through a best-response map. For this class of games, we propose an asymmetric projected gradient descent-best response iteration that does not require full mutual knowledge of both players' optimization problems. Under suitable regularity conditions, we establish the existence and uniqueness of the Nash equilibrium and prove global linear convergence of the proposed iteration when the best-response map is exact. Recognizing that best-response maps are often learned or estimated, we further analyze the inexact case and show that, when the approximation error is uniformly bounded by $\varepsilon$, the iterates enter an explicit $O(\varepsilon)$ neighborhood of the true Nash equilibrium. Numerical results on a benchmark game corroborate the predicted convergence behavior and error scaling.