Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models

• URL: http://arxiv.org/abs/2603.17058v1
• Date: Tue, 17 Mar 2026 18:45:56 GMT
• Title: Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models
• Abstract summary: Nash equilibria provide a principled framework for modeling interactions in multi-agent decision-making and control.<n>This letter studies a class of asymmetric-information two-player constrained games with decoupled feasible sets.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Generalized Distributional Alignment Games for Unbiased Answer-Level Fine-Tuning [49.24876001249647]
  Distributional Alignment Game framework provides powerful variational perspective on Answer-Level Fine-Tuning (ALFT)<n>Standard algorithms for these games rely on estimating logarithmic rewards from small batches, introducing a systematic bias due to Jensen's inequality that can destabilize training.<n>We generalize the alignment game to arbitrary Bregman divergences, showing that for a family of geometries inducing rewards, we can construct provably exact and unbiased estimators.
  arXiv  Detail & Related papers  (2026-05-04T10:34:42Z)
• A Data Driven Structural Decomposition of Dynamic Games via Best Response Maps [0.0]
  This paper introduces a conceptually novel formulation for dynamic games by restructuring the equilibrium computation.<n>The proposed formulation is supported by mathematical proofs, accompanying a large-scale Monte Carlo study in a two-player open-loop dynamic game motivated by the autonomous racing problem.
  arXiv  Detail & Related papers  (2026-02-05T05:44:53Z)
• Accelerating Nash Learning from Human Feedback via Mirror Prox [36.04055906691423]
  We introduce Nash Mirror Prox ($mathtNash-MP$), an online NLHF algorithm that leverages the Mirror Prox optimization scheme to achieve fast and stable convergence to the Nash equilibrium.<n>Our theoretical analysis establishes that Nash-MP exhibits last-iterate linear convergence towards the $beta$-regularized Nash equilibrium.<n>We show that Nash-MP exhibits last-iterate linear convergence for the exploitability gap and uniformly for the span semi-norm of log-probabilities.
  arXiv  Detail & Related papers  (2025-05-26T09:17:32Z)
• Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guarantees [91.88803125231189]
  Reinforcement Learning from Human Feedback (RLHF) has been highly successful in aligning large language models with human preferences.<n>While prevalent methods like DPO have demonstrated strong performance, they frame interactions with the language model as a bandit problem.<n>In this paper, we address these challenges by modeling the alignment problem as a two-player constant-sum Markov game.
  arXiv  Detail & Related papers  (2025-02-18T09:33:48Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  We study how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating. The lower level requires solving the Nash equilibrium under a given reward function, which makes the overall problem challenging to optimize in an end-to-end way. We propose a backpropagation scheme that differentiates through the Nash equilibrium, which provides the gradient feedback for the upper level.
  arXiv  Detail & Related papers  (2023-02-20T16:05:04Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  We study the problem of finding an approximate Nash equilibrium of games with continuous action sets. We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile.
  arXiv  Detail & Related papers  (2023-01-20T23:55:30Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Multiplayer Performative Prediction: Learning in Decision-Dependent Games [18.386569111954213]
  This paper formulates a new game theoretic framework for multi-player performative prediction. We focus on two distinct solution concepts, namely (i) performatively stable equilibria and (ii) Nash equilibria of the game. We show that under mild assumptions, the performatively stable equilibria can be found efficiently by a variety of algorithms.
  arXiv  Detail & Related papers  (2022-01-10T15:31:10Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
  arXiv  Detail & Related papers  (2021-08-17T07:06:46Z)
• Bounded rationality for relaxing best response and mutual consistency: An information-theoretic model of partial self-reference [0.0]
  This work focuses on some of the assumptions underlying rationality such as mutual consistency and best-response. We consider ways to relax these assumptions using concepts from level-$k$ reasoning and quantal response equilibrium (QRE) respectively.
  arXiv  Detail & Related papers  (2021-06-30T06:56:56Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games. By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria.
  arXiv  Detail & Related papers  (2021-05-27T06:10:24Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.