Asymmetric Nash Seeking via Best–Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models
Mahdis Rabbani, Navid Mojahed, Shima Nazari · 2026
Read Asymmetric Nash Seeking via Best–Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models by Mahdis Rabbani, Navid Mojahed, Shima Nazari (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-17058.txt.
Introduction
Rabbani, Mojahed, and Nazari study Nash equilibrium seeking when the two players hold unequal information. Many methods assume each player knows the other's objectives and constraints, which is often unrealistic. Here, player 1 knows only its own problem, while player 2 is reachable through a best response map. The authors propose an iteration that mixes projected gradient descent with that map. They prove existence and uniqueness of the equilibrium, plus global linear convergence when the map is exact. When the map is inexact, iterates still land near the true equilibrium.
Catalog record
| CREATOR | Mahdis Rabbani, Navid Mojahed, Shima Nazari |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32116 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.17058
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymmetric Nash Seeking via Best–Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models Mahdis Rabbani, Navid Mojahed, Shima Nazari 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 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 ( ε ) O(\varepsilon) neighborhood of the true Nash equilibrium. Numerical results on a benchmark game corroborate the predicted convergence behavior and error scaling. I Introduction Strategic decision-making in multi-agent systems is central to autonomy, robotics, and networked control, where agents pursue individual objectives while influencing one another through coupled decisions and shared environments [ 3 , 17 , 15 , 14 ] . In such settings, Nash equilibrium (NE) provides a principled notion of interaction-consistent behavior and underlies a broad class of game-theoretic planning and control methods [ 12 , 15 , 14 ] . This viewpoint is especially appealing in interaction-aware autonomy, where mutual adaptation arises naturally in scenarios such as lane changes, merges, overtaking, and human–robot interaction [ 8 , 15 , 7 , 14 ] . A central limitation of many equilibrium-based methods is their information assumption. Classical equilibrium analysis and computation typically assume that the game is explicitly known, including all players’ objectives and feasible sets [ 12 , 4 , 6 , 5 ] . This assumption is built into both foundational theory and practical game solvers, including VI/KKT-based approaches and modern constrained dynamic-game solvers such as ALGAMES and DG-SQP [ 4 , 6 , 8 , 18 ] . A complementary fixed-point viewpoint leads to iterative best-response (IBR) schemes and related Jacobi/Gauss–Seidel updates [ 9 , 16 , 15 ] . However, both perspectives still rely on access to either the full joint game model or repeatedly evaluable opponent best responses, which is restrictive in interactive settings where surrounding agents are observed only through behavior rather than through their internal optimization problems [ 9 , 10 ] . To address this asymmetry, recent efforts have sought to recover missing opponent information from data, for example by learning latent objectives or adapting opponent models online [ 1 , 10 , 13 ] . In contrast, we study 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 represented only through a best-response map [ 11 ] . Thus, Player 2’s objective, model, and constraints need not be explicitly accessible. Importantly, the best-response map is treated here as an information structure , not as a leader–follower reformulation; our goal is to characterize and seek the simultaneous-move Nash equilibrium of the original game under asymmetric information, rather than a Stackelberg solution [ 7 , 2 ] . The main contributions of this paper are as follows: • We introduce a class of asymmetric-information two-player constrained games with decoupled feasible sets, in which the opponent is represented directly through a best-response map rather than an explicit objective model, and establish existence and uniqueness of Nash equilibrium for this class under regularity assumptions. • We propose an asymmetric projected gradient descent–best response iteration and show that, under stronger regularity assumptions, it converges globally and linearly to the unique Nash equilibrium. • We analyze the practically important case of an approximate best-response map and prove robustness: under a uniform approximation error bound, the proposed iteration enters an explicit O(\varepsilon) neighborhood of the true Nash equilibrium. Taken together, these results turn the best-response-map viewpoint from a modeling abstraction into a provably convergent equilibrium-seeking framework for constrained games with asymmetric information. II Problem Formulation We consider a constrained two-player game with decision variables x_{1}\in\mathrm{X}_{1}\subset\mathbb{R}^{n_{1}} and x_{2}\in\mathrm{X}_{2}\subset\mathbb{R}^{n_{2}} for Player 1 and Player 2, respectively. The feasible sets are decoupled, so the joint feasible set is \mathrm{X}\triangleq\mathrm{X}_{1}\times\mathrm{X}_{2}, and there is no explicit coupling through shared constraints. Thus, the interaction enters through the cost functions and the induced reaction behavior rather than through joint feasibility conditions. Player 1 is described by a cost function J_{1}:\mathrm{X}_{1}\times\mathrm{X}_{2}\to\mathbb{R},\qquad(x_{1},x_{2})\mapsto J_{1}(x_{1},x_{2}), (1) which may depend on both players’ decisions. In contrast, Player 2 is represented, from the standpoint of Player 1, through its best-response correspondence \mathrm{BR}_{2}:\mathrm{X}_{1}\rightrightarrows\mathrm{X}_{2},\quad\mathrm{BR}_{2}(x_{1})\triangleq\arg\min_{x_{2}\in\mathrm{X}_{2}}J_{2}(x_{1},x_{2}), (2) for some objective J_{2} that need not be known to Player 1. Accordingly, the algorithmic development relies only on access to \mathrm{BR}_{2}(\cdot) , or later, an approximation thereof. Problem 1 ( Asymmetric-Information Two-Player Game ) Given the feasible sets \mathrm{X}_{1},\mathrm{X}_{2} , Player 1’s cost J_{1} in ( 1 ), and Player 2’s best-response correspondence \mathrm{BR}_{2}(\cdot) in ( 2 ), consider the two-player game in which Player 1 solves \min_{x_{1}\in\mathrm{X}_{1}}J_{1}(x_{1},x_{2}), while Player 2 simultaneously reacts according to x_{2}\in\mathrm{BR}_{2}(x_{1}) . Definition 1 (Nash equilibrium) A pair (x_{1}^{\star},x_{2}^{\star})\in\mathrm{X}_{1}\times\mathrm{X}_{2} is a Nash equilibrium of Problem 1 if x_{1}^{\star}\in\arg\min_{x_{1}\in\mathrm{X}_{1}}J_{1}(x_{1},x_{2}^{\star}),\qquad x_{2}^{\star}\in\mathrm{BR}_{2}(x_{1}^{\star}). The next section characterizes conditions under which Problem 1 admits a Nash equilibrium and when that equilibrium is unique. III Existence & Uniqueness of the Equilibrium This section investigates existence and uniqueness of a Nash equilibrium for Problem 1 . We first establish existence under general regularity conditions that allow Player 2’s best-response map to be set-valued, and then impose stronger assumptions under which the best response becomes single-valued and the equilibrium is unique. Assumption A.1 The feasible sets \mathrm{X}_{1} and \mathrm{X}_{2} are nonempty, convex, and compact. Assumption A.2 The function J_{1}:\mathrm{X}_{1}\times\mathrm{X}_{2}\to\mathbb{R} is continuous on \mathrm{X}_{1}\times\mathrm{X}_{2} . Moreover, for every fixed x_{2}\in\mathrm{X}_{2} , the function J_{1}(\cdot,x_{2}) is convex on \mathrm{X}_{1} . Assumption A.3 For every x_{1}\in\mathrm{X}_{1} , the correspondence \mathrm{BR}_{2}(x_{1})\subseteq\mathrm{X}_{2} is nonempty, convex, and compact, and \mathrm{BR}_{2}:\mathrm{X}_{1}\rightrightarrows\mathrm{X}_{2} is upper hemicontinuous. Theorem 1 (Existence of Nash equilibrium) Under Assumptions A.1 – A.3 , Problem 1 admits at least one Nash equilibrium. Proof: Define Player 1’s best-response correspondence \mathrm{BR}_{1}(x_{2})\triangleq\arg\min_{x_{1}\in\mathrm{X}_{1}}J_{1}(x_{1},x_{2}),\qquad x_{2}\in\mathrm{X}_{2}. (3) Fix any x_{2}\in\mathrm{X}_{2} . By Assumption A.1 , \mathrm{X}_{1} is nonempty and compact, and by Assumption A.2 , J_{1}(\cdot,x_{2}) is continuous. Hence, by the Weierstrass extreme value theorem, \mathrm{BR}_{1}(x_{2}) is nonempty and compact. Moreover, by convexity of J_{1}(\cdot,x_{2}) (Assumption A.2 ), the set of minimizers \mathrm{BR}_{1}(x_{2}) is convex. Next, Assumption A.2 ensures that J_{1} is jointly continuous on \mathrm{X}_{1}\times\mathrm{X}_{2} , while Assumption A.1 guarantees that \mathrm{X}_{1} is compact. Therefore, Berge’s maximum theorem implies that \mathrm{BR}_{1}:\mathrm{X}_{2}\rightrightarrows\mathrm{X}_{1} is upper hemicontinuous and compact-valued. Now define the product correspondence F:\mathrm{X}\rightrightarrows\mathrm{X} on \mathrm{X}=\mathrm{X}_{1}\times\mathrm{X}_{2} by F(x_{1},x_{2})\triangleq\mathrm{BR}_{1}(x_{2})\times\mathrm{BR}_{2}(x_{1}). By the preceding arguments and Assumption A.3 , for every (x_{1},x_{2})\in\mathrm{X} the set F(x_{1},x_{2}) is nonempty, convex, and compact, and F is upper hemicontinuous. Since \mathrm{X} is