Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models
New method achieves global linear convergence for asymmetric games where agents only see opponent reactions, not objectives.
A team of researchers including Mahdis Rabbani, Navid Mojahed, and Shima Nazari has developed a breakthrough algorithm for finding Nash equilibria in asymmetric-information games, addressing a fundamental limitation in multi-agent systems. Traditional equilibrium-seeking methods typically assume each agent has complete knowledge of other agents' objectives and constraints—an unrealistic requirement in practical applications like robotics, economics, and autonomous systems. Their proposed "asymmetric projected gradient descent-best response iteration" enables Player 1 to find equilibrium while only observing Player 2's reactions through a best-response map, without needing access to Player 2's internal optimization problem.
Under standard regularity conditions, the researchers proved both existence and uniqueness of the Nash equilibrium, with their algorithm achieving global linear convergence when the best-response map is exact. More importantly, they analyzed the practical case where response models are learned or estimated, showing that even with approximation errors bounded by ε, the algorithm's iterates converge to an explicit O(ε) neighborhood of the true equilibrium. Numerical experiments on benchmark games confirmed both the predicted convergence behavior and error scaling, demonstrating robustness to imperfect models.
The work, submitted to IEEE L-CSS and CDC 2026, represents significant progress toward practical multi-agent systems where agents operate with partial information. This addresses real-world scenarios where agents might use machine learning models to predict opponent behavior rather than having perfect knowledge of their objectives. The mathematical guarantees provide a foundation for deploying more robust multi-agent algorithms in competitive environments where full transparency between agents cannot be assumed.
- Algorithm works with asymmetric information where agents only see opponent reactions, not objectives/constraints
- Proves global linear convergence to Nash equilibrium with exact models and O(ε) proximity with bounded errors
- Validated on benchmark games with numerical results matching theoretical predictions
Why It Matters
Enables practical multi-agent systems in robotics and economics where agents can't fully know each other's goals, using learned response models instead.