Paper deep dive
Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models
Mahdis Rabbani, Navid Mojahed, Shima Nazari
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%
Last extracted: 3/22/2026, 5:02:18 AM
Summary
The paper introduces an asymmetric projected gradient descent-best response iteration for solving two-player constrained games with decoupled feasible sets. It establishes conditions for the existence and uniqueness of a Nash equilibrium and proves global linear convergence when the best-response map is exact. Furthermore, it demonstrates that the algorithm is robust to inexact best-response maps, with iterates converging to an O(ε) neighborhood of the true Nash equilibrium.
Entities (4)
Relation Signals (2)
Asymmetric projected gradient descent-best response iteration → convergesto → Nash equilibrium
confidence 100% · we establish the existence and uniqueness of the Nash equilibrium and prove global linear convergence of the proposed iteration
Best-response map → defines → Player 2
confidence 95% · Player 2 is represented, from the standpoint of Player 1, through its best-response correspondence
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.17058v1
- Canonical: https://arxiv.org/abs/2603.17058v1
Trouble viewing inline? Open PDF directly →
Full Text
40,427 characters extracted from source content.
Expand or collapse full text
Asymmetric Nash Seeking via Best–Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models Mahdis Rabbani1, Navid Mojahed1, and Shima Nazari1 1Authors are with Department of Mechanical and Aerospace Engineering, University of California, Davis, One Shield Ave, Davis, CA 95616. mrabbani, nmojahed, snazari@ucdavis.edu 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 ε , the iterates enter an explicit O(ε)O( ) 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(ε)O( ) 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. I Problem Formulation We consider a constrained two-player game with decision variables x1∈X1⊂ℝn1x_1 _1 ^n_1 and x2∈X2⊂ℝn2x_2 _2 ^n_2 for Player 1 and Player 2, respectively. The feasible sets are decoupled, so the joint feasible set is X≜X1×X2,X _1×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 J1:X1×X2→ℝ,(x1,x2)↦J1(x1,x2),J_1:X_1×X_2 , (x_1,x_2) 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 BR2:X1⇉X2,BR2(x1)≜argminx2∈X2J2(x1,x2),BR_2:X_1 _2, _2(x_1) _x_2 _2J_2(x_1,x_2), (2) for some objective J2J_2 that need not be known to Player 1. Accordingly, the algorithmic development relies only on access to BR2(⋅)BR_2(·), or later, an approximation thereof. Problem 1 (Asymmetric-Information Two-Player Game) Given the feasible sets X1,X2X_1,X_2, Player 1’s cost J1J_1 in (1), and Player 2’s best-response correspondence BR2(⋅)BR_2(·) in (2), consider the two-player game in which Player 1 solves minx1∈X1J1(x1,x2), _x_1 _1J_1(x_1,x_2), while Player 2 simultaneously reacts according to x2∈BR2(x1)x_2 _2(x_1). Definition 1 (Nash equilibrium) A pair (x1⋆,x2⋆)∈X1×X2(x_1 ,x_2 ) _1×X_2 is a Nash equilibrium of Problem 1 if x1⋆∈argminx1∈X1J1(x1,x2⋆),x2⋆∈BR2(x1⋆).x_1 ∈ _x_1 _1J_1(x_1,x_2 ), x_2 _2(x_1 ). The next section characterizes conditions under which Problem 1 admits a Nash equilibrium and when that equilibrium is unique. I 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 X1X_1 and X2X_2 are nonempty, convex, and compact. Assumption A.2 The function J1:X1×X2→ℝJ_1:X_1×X_2 is continuous on X1×X2X_1×X_2. Moreover, for every fixed x2∈X2x_2 _2, the function J1(⋅,x2)J_1(·,x_2) is convex on X1X_1. Assumption A.3 For every x1∈X1x_1 _1, the correspondence BR2(x1)⊆X2BR_2(x_1) _2 is nonempty, convex, and compact, and BR2:X1⇉X2BR_2:X_1 _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 BR1(x2)≜argminx1∈X1J1(x1,x2),x2∈X2.BR_1(x_2) _x_1 _1J_1(x_1,x_2), x_2 _2. (3) Fix any x2∈X2x_2 _2. By Assumption A.1, X1X_1 is nonempty and compact, and by Assumption A.2, J1(⋅,x2)J_1(·,x_2) is continuous. Hence, by the Weierstrass extreme value theorem, BR1(x2)BR_1(x_2) is nonempty and compact. Moreover, by convexity of J1(⋅,x2)J_1(·,x_2) (Assumption A.2), the set of minimizers BR1(x2)BR_1(x_2) is convex. Next, Assumption A.2 ensures that J1J_1 is jointly continuous on X1×X2X_1×X_2, while Assumption A.1 guarantees that X1X_1 is compact. Therefore, Berge’s maximum theorem implies that BR1:X2⇉X1BR_1:X_2 _1 is upper hemicontinuous and compact-valued. Now define the product correspondence F:X⇉XF:X on X=X1×X2X=X_1×X_2 by F(x1,x2)≜BR1(x2)×BR2(x1).F(x_1,x_2) _1(x_2)×BR_2(x_1). By the preceding arguments and Assumption A.3, for every (x1,x2)∈X(x_1,x_2) the set F(x1,x2)F(x_1,x_2) is nonempty, convex, and compact, and F is upper hemicontinuous. Since XX is nonempty, convex, and compact by Assumption A.1, Kakutani’s fixed-point theorem guarantees the existence of (x1⋆,x2⋆)∈X(x_1 ,x_2 ) such that (x1⋆,x2⋆)∈F(x1⋆,x2⋆),(x_1 ,x_2 )∈ F(x_1 ,x_2 ), i.e., x1⋆∈BR1(x2⋆)x_1 _1(x_2 ) and x2⋆∈BR2(x1⋆)x_2 _2(x_1 ). By the definition of BR1BR_1 in (3), the first inclusion is equivalent to x1⋆∈argminx1∈X1J1(x1,x2⋆)x_1 ∈ _x_1 _1J_1(x_1,x_2 ), and together with x2⋆∈BR2(x1⋆)x_2 _2(x_1 ) this matches Definition 1. Therefore, (x1⋆,x2⋆)(x_1 ,x_2 ) is a Nash equilibrium of Problem 1. ∎ To state a uniqueness condition aligned with our subsequent convergence analysis, we impose the following stronger assumptions. Assumption B.1 The function J1:X1×X2→ℝJ_1:X_1×X_2 is continuous on X1×X2X_1×X_2. Moreover, for every fixed x2∈X2x_2 _2, the function J1(⋅,x2)J_1(·,x_2) is differentiable and μ-strongly convex on X1X_1 for some μ>0μ>0. Assumption B.2 For every fixed x1∈X1x_1 _1, the mapping x2↦∇x1J1(x1,x2)x_2 _x_1J_1(x_1,x_2) is Lipschitz on X2X_2 with constant L12≥0L_12≥ 0, i.e., ∀x2,y2∈X2∀ x_2,y_2 _2, ‖∇x1J1(x1,x2)−∇x1J1(x1,y2)‖≤L12‖x2−y2‖.\| _x_1J_1(x_1,x_2)- _x_1J_1(x_1,y_2)\|≤ L_12\|x_2-y_2\|. Assumption B.3 For every x1∈X1x_1 _1, the best response map BR2(x1)BR_2(x_1) is single-valued. Assumption B.4 The (single-valued) best response map BR2:X1→X2BR_2:X_1 _2 is Lipschitz on X1X_1 with constant L2≥0L_2≥ 0. Theorem 2 (Uniqueness of Nash equilibrium) Suppose Assumptions A.1 and B.1–B.4 hold. If μ>L12L2μ>L_12L_2, then the Nash equilibrium of Problem 1 is unique. Proof: Assumption B.1 implies Assumption A.2. In addition, Assumptions B.3 and B.4 imply that BR2BR_2 is a continuous single-valued map, hence upper hemicontinuous as a correspondence with nonempty, convex, and compact singleton values. Therefore, Assumption A.3 also holds. Together with Assumption A.1, existence follows from Theorem 1. To prove uniqueness, let (a1,b1)(a_1,b_1) and (a2,b2)(a_2,b_2) be two Nash equilibria of Problem 1. By Definition 1 and Assumption B.3, b1=BR2(a1),b2=BR2(a2).b_1=BR_2(a_1), b_2=BR_2(a_2). (4) Since a1a_1 minimizes J1(⋅,b1)J_1(·,b_1) over the convex set X1X_1, the first-order optimality condition for convex constrained problems yields ⟨∇x1J1(a1,b1),a2−a1⟩≥0. _x_1J_1(a_1,b_1),\,a_2-a_1 ≥ 0. Similarly, optimality of a2a_2 for J1(⋅,b2)J_1(·,b_2) implies ⟨∇x1J1(a2,b2),a1−a2⟩≥0. _x_1J_1(a_2,b_2),\,a_1-a_2 ≥ 0. Adding the two inequalities gives ⟨∇x1J1(a1,b1)−∇x1J1(a2,b2),a1−a2⟩≤0. _x_1J_1(a_1,b_1)- _x_1J_1(a_2,b_2),\,a_1-a_2 ≤ 0. (5) Add and subtract ∇x1J1(a2,b1) _x_1J_1(a_2,b_1) inside the inner product in (5). By μ-strong convexity of J1(⋅,b1)J_1(·,b_1) (Assumption B.1), we have ⟨∇x1J1(a1,b1)−∇x1J1(a2,b1), _x_1J_1(a_1,b_1)- _x_1J_1(a_2,b_1), a1−a2⟩ a_1-a_2 (6) ≥μ‖a1−a2‖2. ≥μ\|a_1-a_2\|^2. For the remaining term, Cauchy–Schwarz yields ⟨∇x1 _x_1 J1(a2,b1)−∇x1J1(a2,b2),a1−a2⟩ J_1(a_2,b_1)- _x_1J_1(a_2,b_2),\,a_1-a_2 ≥−‖∇x1J1(a2,b1)−∇x1J1(a2,b2)‖‖a1−a2‖. ≥-\| _x_1J_1(a_2,b_1)- _x_1J_1(a_2,b_2)\|\,\|a_1-a_2\|. Using Assumption B.2 and (4) together with Assumption B.4, we obtain ⟨∇x1J1(a2,b1)−∇x1 _x_1J_1(a_2,b_1)- _x_1 J1(a2,b2),a1−a2⟩ J_1(a_2,b_2),\,a_1-a_2 (7) ≥−L12‖b1−b2‖‖a1−a2‖ ≥-L_12\|b_1-b_2\|\,\|a_1-a_2\| ≥−L12L2‖a1−a2‖2. ≥-L_12L_2\|a_1-a_2\|^2. Combining (5)–(7) yields (μ−L12L2)‖a1−a2‖2≤0.(μ-L_12L_2)\|a_1-a_2\|^2≤ 0. If μ>L12L2μ>L_12L_2, then a1=a2a_1=a_2. Substituting into (4), and given Assumption B.3, gives b1=b2b_1=b_2, hence (a1,b1)=(a2,b2)(a_1,b_1)=(a_2,b_2). Therefore, the Nash equilibrium is unique. ∎ The same dominance condition μ>L12L2μ>L_12L_2 also induces a monotonicity margin that will be central to the convergence analysis of the iterative scheme developed next. IV Algorithm & Global Linear Convergence to the Equilibrium Under Assumptions A.1 and B.1–B.4, and whenever μ>L12L2μ>L_12L_2, Problem 1 admits a unique Nash equilibrium by Theorem 2. We now study a projected best-response/gradient iteration and show that it converges globally and linearly to this equilibrium. Assumption C.1 For every fixed x2∈X2x_2 _2, the function J1(⋅,x2)J_1(·,x_2) is L1L_1-smooth on X1X_1, i.e., ∀x1,y1∈X1∀ x_1,y_1 _1, ‖∇x1J1(x1,x2)−∇x1J1(y1,x2)‖≤L1‖x1−y1‖.\| _x_1J_1(x_1,x_2)- _x_1J_1(y_1,x_2)\|≤ L_1\|x_1-y_1\|. We consider the projected best-response/gradient iteration x2k x_2^k =BR2(x1k), =BR_2(x_1^k), (8) x1k+1 x_1^k+1 =ΠX1(x1k−α∇x1J1(x1k,x2k)), = _X_1\! (x_1^k-α _x_1J_1(x_1^k,x_2^k) ), where ΠX1(⋅) _X_1\! (· ) denotes the Euclidean projection onto X1X_1. Since X1X_1 is closed and convex (Assumption A.1), the projection is nonexpansive: ‖ΠX1(u)−ΠX1(v)‖≤‖u−v‖,∀u,v∈ℝn1.\| _X_1\! (u )- _X_1\! (v )\|≤\|u-v\|, ∀ u,v ^n_1. (9) Theorem 3 (Global linear convergence) Suppose Assumptions A.1, B.1–B.4, and C.1 hold. Let m≜μ−L12L2andLG≜L1+L12L2,m μ-L_12L_2 L_G L_1+L_12L_2, and note that m>0m>0 follows from μ>L12L2μ>L_12L_2. Then, for any stepsize α satisfying 0<α<2mLG2=2(μ−L12L2)(L1+L12L2)2,0<α< 2mL_G^2= 2(μ-L_12L_2)(L_1+L_12L_2)^2, the iterates generated by (8) satisfy ‖x1k−x1⋆‖≤ρ(α)k‖x10−x1⋆‖,\|x_1^k-x_1 \|≤ρ(α)^k\|x_1^0-x_1 \|, ‖x2k−x2⋆‖≤L2ρ(α)k‖x10−x1⋆‖,\|x_2^k-x_2 \|≤ L_2\,ρ(α)^k\|x_1^0-x_1 \|, where (x1⋆,x2⋆)(x_1 ,x_2 ) is the unique Nash equilibrium of Problem 1 and ρ(α)≜1−2αm+α2LG2∈(0,1).ρ(α) 1-2α m+α^2L_G^2∈(0,1). Proof: Define the map T:X1→X1T:X_1 _1 by T(x1):=ΠX1(x1−α∇x1J1(x1,BR2(x1))),T(x_1):= _X_1\! (x_1-α _x_1J_1 (x_1,BR_2(x_1) ) ), (10) and define the operator G:X1→ℝn1G:X_1 ^n_1 as G(x1):=∇x1J1(x1,BR2(x1)).G(x_1):= _x_1J_1 (x_1,BR_2(x_1) ). For any x1,y1∈X1x_1,y_1 _1, add and subtract ∇x1J1(y1,BR2(x1)) _x_1J_1(y_1,BR_2(x_1)) to obtain ∥G( \|G( x1)−G(y1)∥ x_1)-G(y_1)\| ≤‖∇x1J1(x1,BR2(x1))−∇x1J1(y1,BR2(x1))‖ ≤\| _x_1J_1(x_1,BR_2(x_1))- _x_1J_1(y_1,BR_2(x_1))\| +‖∇x1J1(y1,BR2(x1))−∇x1J1(y1,BR2(y1))‖. +\| _x_1J_1(y_1,BR_2(x_1))- _x_1J_1(y_1,BR_2(y_1))\|. By Assumption C.1, the first term is bounded by L1‖x1−y1‖L_1\|x_1-y_1\|. By Assumptions B.2 and B.4, the second term is bounded by L12‖BR2(x1)−BR2(y1)‖≤L12L2‖x1−y1‖L_12\|BR_2(x_1)-BR_2(y_1)\|≤ L_12L_2\|x_1-y_1\|. Therefore, G is Lipschitz on X1X_1 with constant LG=L1+L12L2L_G=L_1+L_12L_2, i.e., ‖G(x1)−G(y1)‖≤LG‖x1−y1‖.\|G(x_1)-G(y_1)\|≤ L_G\|x_1-y_1\|. (11) Next, using the same add–subtract decomposition and Assumption B.1, we have ⟨ G(x1)−G(y1),x1−y1⟩ G(x_1)-G(y_1),\,x_1-y_1 =⟨∇x1J1(x1,BR2(x1))−∇x1J1(y1,BR2(x1)),x1−y1⟩ = _x_1J_1(x_1,BR_2(x_1))- _x_1J_1(y_1,BR_2(x_1)),\,x_1-y_1 +⟨∇x1J1(y1,BR2(x1))−∇x1J1(y1,BR2(y1)),x1−y1⟩. + _x_1J_1(y_1,BR_2(x_1))- _x_1J_1(y_1,BR_2(y_1)),\,x_1-y_1 . The first inner product is lower bounded by μ‖x1−y1‖2μ\|x_1-y_1\|^2. For the second, Cauchy–Schwarz together with Assumptions B.2 and B.4 yields ⟨∇x1J1(y1,BR2(x1))−∇x1J1(y1, _x_1J_1(y_1,BR_2(x_1))- _x_1J_1(y_1, BR2(y1)),x1−y1⟩ _2(y_1)),\,x_1-y_1 ≥−L12L2‖x1−y1‖2. ≥-L_12L_2\|x_1-y_1\|^2. Thus, G is strongly monotone on X1X_1 with constant m=μ−L12L2>0m=μ-L_12L_2>0, i.e., ⟨G(x1)−G(y1),x1−y1⟩≥m‖x1−y1‖2. G(x_1)-G(y_1),\,x_1-y_1 ≥ m\|x_1-y_1\|^2. (12) By nonexpansiveness of the projection (9), ‖T(x1)−T(y1)‖≤‖(x1−y1)−α(G(x1)−G(y1))‖.\|T(x_1)-T(y_1)\|≤\|(x_1-y_1)-α(G(x_1)-G(y_1))\|. Expanding the square and applying the Lipschitz and strong monotonicity bounds in (11) and (12) gives ∥T(x1)−T(y1)∥2≤(1−2 \|T(x_1)-T(y_1)\|^2≤ (1-2 αm+α2LG2)∥x1−y1∥2 α m+α^2L_G^2 )\|x_1-y_1\|^2 (13) =:q(α)∥x1−y1∥2. =:q(α)\|x_1-y_1\|^2. For 0<α<2m/LG20<α<2m/L_G^2, we have q(α)∈(0,1)q(α)∈(0,1), hence T is a contraction with modulus ρ(α)=q(α)∈(0,1)ρ(α)= q(α)∈(0,1). Therefore, by the Banach fixed-point theorem, T has a unique fixed point x1∗∈X1x_1^* _1 and the iterates satisfy ‖x1k−x1∗‖≤ρ(α)k‖x10−x1∗‖.\|x_1^k-x_1^*\|≤ρ(α)^k\|x_1^0-x_1^*\|. (14) Let x2∗:=BR2(x1∗)x_2^*:=BR_2(x_1^*). Since BR2BR_2 is Lipschitz (B.4), ‖x2k−x2∗‖=‖BR2(x1k)−BR2(x1∗)‖≤L2‖x1k−x1∗‖. x_2^k-x_2^* = _2(x_1^k)-BR_2(x_1^*) ≤ L_2\, x_1^k-x_1^* . Combining with (14) gives ‖x2k−x2∗‖≤L2ρ(α)k‖x10−x1∗‖. x_2^k-x_2^* ≤ L_2\,ρ(α)^k x_1^0-x_1^* . It remains to show that x1∗x_1^* minimizes J1(⋅,x2∗)J_1(·,x_2^*) over X1X_1. From x1∗=T(x1∗)x_1^*=T(x_1^*), we have x1∗=ΠX1(x1∗−α∇x1J1(x1∗,x2∗)).x_1^*= _X_1\! (x_1^*-α _x_1J_1(x_1^*,x_2^*) ). By the characterization of Euclidean projection onto a closed convex set, y=ΠX1(z)y= _X_1\! (z ) if and only if ⟨z−y,x−y⟩≤0,∀x∈X1. z-y,\,x-y ≤ 0, ∀ x _1. Applying this with y=x1∗y=x_1^* and z=x1∗−α∇x1J1(x1∗,x2∗)z=x_1^*-α _x_1J_1(x_1^*,x_2^*) yields ⟨∇x1J1(x1∗,x2∗),x−x1∗⟩≥0,∀x∈X1. _x_1J_1(x_1^*,x_2^*),\,x-x_1^* ≥ 0, ∀ x _1. Since J1(⋅,x2∗)J_1(·,x_2^*) is convex and differentiable (B.1), this first-order condition is sufficient for optimality, hence x1∗∈argminx1∈X1J1(x1,x2∗).x_1^*∈ _x_1 _1J_1(x_1,x_2^*). Together with x2∗=BR2(x1∗)x_2^*=BR_2(x_1^*), Definition 1 implies that (x1∗,x2∗)(x_1^*,x_2^*) is a Nash equilibrium. By uniqueness (Theorem 2), (x1∗,x2∗)=(x1⋆,x2⋆)(x_1^*,x_2^*)=(x_1 ,x_2 ), which completes the proof. ∎ V Inexact Best Response & Robustness of the Algorithm The convergence result in Section IV assumes access to the exact best-response map BR2BR_2. In practice, however, an agent typically has access only to an approximation or estimate of its opponent’s reaction behavior. We therefore study the robustness of the projected best-response/gradient iteration when BR2BR_2 is replaced by an inexact map. Let BR^2:X1→X2 BR_2:X_1 _2 denote an approximation of BR2BR_2, and assume a uniform error bound: there exists ε>0 >0 such that ‖BR^2(x1)−BR2(x1)‖≤ε,∀x1∈X1.\| BR_2(x_1)-BR_2(x_1)\|≤ , ∀ x_1 _1. (15) We consider the inexact variant of (8): x2k=BR^2(x1k), x_2^k= BR_2(x_1^k), (16) x1k+1=ΠX1(x1k−α∇x1J1(x1k,x2k)). x_1^k+1= _X_1\! (x_1^k-α _x_1J_1(x_1^k,x_2^k) ). Theorem 4 (Robustness to inexact best response) Let (x1⋆,x2⋆)∈X(x_1 ,x_2 ) denote the unique Nash equilibrium of Problem 1 under Assumptions A.1, B.1–B.4, and C.1, and suppose μ>L12L2μ>L_12L_2. Let m≜μ−L12L2,LG≜L1+L12L2,m μ-L_12L_2, L_G L_1+L_12L_2, and choose α∈(0,2m/LG2)α∈(0,2m/L_G^2). If BR^2 BR_2 satisfies (15), then the iterates (16) satisfy, for all k≥0k≥ 0, ‖x1k+1−x1⋆‖≤ρ(α)‖x1k−x1⋆‖+αL12ε,\|x_1^k+1-x_1 \|≤ρ(α)\|x_1^k-x_1 \|+α L_12 , (17) where ρ(α)=1−2αm+α2LG2∈(0,1).ρ(α)= 1-2α m+α^2L_G^2∈(0,1). Consequently, lim supk→∞‖x1k−x1⋆‖≤αL121−ρ(α)ε. _k→∞\|x_1^k-x_1 \|≤ α L_121-ρ(α)\, . (18) Moreover, the sequence x2k=BR^2(x1k)x_2^k= BR_2(x_1^k) satisfies ‖x2k−x2⋆‖≤L2‖x1k−x1⋆‖+ε,\|x_2^k-x_2 \|≤ L_2\|x_1^k-x_1 \|+ , (19) and hence lim supk→∞‖x2k−x2⋆‖≤(L2αL121−ρ(α)+1)ε. _k→∞\|x_2^k-x_2 \|≤ (L_2 α L_121-ρ(α)+1 ) . (20) Proof: Let T:X1→X1T:X_1 _1 denote the exact map from (10) and define the inexact map T^:X1→X1 T:X_1 _1 by T^(x1):=ΠX1(x1−α∇x1J1(x1,BR^2(x1))). T(x_1):= _X_1\! (x_1-α _x_1J_1 (x_1, BR_2(x_1) ) ). By Theorem 3, T is a contraction on X1X_1 with modulus ρ(α)∈(0,1)ρ(α)∈(0,1), i.e. (13). Moreover, using nonexpansiveness of the projection (9), Assumption B.2, and (15), we obtain, for any x1∈X1x_1 _1, ∥T \| T (x1)−T(x1)∥ (x_1)-T(x_1)\| (21) ≤α‖∇x1J1(x1,BR^2(x1))−∇x1J1(x1,BR2(x1))‖ ≤α \| _x_1J_1 (x_1, BR_2(x_1) )- _x_1J_1 (x_1,BR_2(x_1) ) \| ≤αL12‖BR^2(x1)−BR2(x1)‖≤αL12ε. ≤α L_12\| BR_2(x_1)-BR_2(x_1)\|≤α L_12 . Now, since x1k+1=T^(x1k)x_1^k+1= T(x_1^k) and x1⋆=T(x1⋆)x_1 =T(x_1 ), we have ‖x1k+1−x1⋆‖ \|x_1^k+1-x_1 \| =‖T^(x1k)−T(x1⋆)‖ =\| T(x_1^k)-T(x_1 )\| ≤‖T^(x1k)−T(x1k)‖+‖T(x1k)−T(x1⋆)‖. ≤\| T(x_1^k)-T(x_1^k)\|+\|T(x_1^k)-T(x_1 )\|. Using the contraction property of T from Theorem 3 together with (21), immediately proves (17). Iterating (17) yields ‖x1k−x1⋆‖≤ρ(α)k‖x10−x1⋆‖+αL12ε∑i=0k−1ρ(α)i.\|x_1^k-x_1 \|≤ρ(α)^k\|x_1^0-x_1 \|+α L_12 _i=0^k-1ρ(α)^i. Since ρ(α)∈(0,1)ρ(α)∈(0,1), ∑i=0k−1ρ(α)i=1−ρ(α)k1−ρ(α), _i=0^k-1ρ(α)^i= 1-ρ(α)^k1-ρ(α), and therefore, for all k≥0k≥ 0, ‖x1k−x1⋆‖≤ρ(α)k‖x10−x1⋆‖+1−ρ(α)k1−ρ(α)αL12ε.\|x_1^k-x_1 \|≤ρ(α)^k\|x_1^0-x_1 \|+ 1-ρ(α)^k1-ρ(α)\,α L_12 . Taking lim sup as k→∞k→∞ gives (18). Finally, since x2k=BR^2(x1k)x_2^k= BR_2(x_1^k) and x2⋆=BR2(x1⋆)x_2 =BR_2(x_1 ), we write ‖x2k−x2⋆‖ \|x_2^k-x_2 \| =‖BR^2(x1k)−BR2(x1⋆)‖ =\| BR_2(x_1^k)-BR_2(x_1 )\| ≤‖BR^2(x1k)−BR2(x1k)‖ ≤\| BR_2(x_1^k)-BR_2(x_1^k)\| +‖BR2(x1k)−BR2(x1⋆)‖. +\|BR_2(x_1^k)-BR_2(x_1 )\|. The first term is bounded by ε via (15), and the second is bounded by L2‖x1k−x1⋆‖L_2\|x_1^k-x_1 \| via Assumption B.4, proving (19). Combining (19) with (18) yields (20) and concludes the proof. ∎ Theorem 4 shows that under a uniform approximation error in the opponent’s best-response map, the projected best-response/gradient iteration remains practically stable: the Player 1 iterate ultimately enters an O(ε)O( ) neighborhood of the exact Nash equilibrium, and the resulting Player 2 estimate remains within an O(ε)O( ) neighborhood of x2⋆x_2 as well. If, in addition, BR^2 BR_2 is single-valued and Lipschitz on X1X_1 with constant L^2 L_2 such that μ>L12L^2μ>L_12 L_2, then the same contraction argument as in Theorem 3 applies with BR2BR_2 replaced by BR^2 BR_2, implying linear convergence of (16) to the unique equilibrium of the perturbed game induced by BR^2 BR_2. VI Numerical Example We illustrate the theoretical results on a one-dimensional tug-of-war cart in which two agents apply opposing longitudinal forces to a point mass with viscous drag. Player 1 selects an open-loop control sequence u, while Player 2 reacts through a best-response map. The example is designed to instantiate the assumptions of Theorems 1–4 and to illustrate exact convergence, robustness to inexact best-response information, and the predicted O(ε)O( ) neighborhood scaling. Let zt=[pt,p˙t]⊤∈ℝ2z_t=[p_t,\; p_t] ^2 denote position and velocity of the cart at time step t. With sampling time Δt t, mass m, and viscous drag coefficient b, the discrete-time dynamics are zt+1=Adzt+Buut+Bvvt,t=0,…,N−1,z_t+1=A_dz_t+B_uu_t+B_vv_t, t=0,…,N-1, where z0=[0,0]⊤z_0=[0,0] and Ad=[1Δt01−Δt(b/m)],Bu=−Bv=[0Δt/m].A_d= bmatrix1& t\\ 0&1- t(b/m) bmatrix, B_u=-B_v= bmatrix0\\ t/m bmatrix. Stacking the horizon variables as u=[u0,…,uN−1]⊤,v=[v0,…,vN−1]⊤,u=[u_0,…,u_N-1] , v=[v_0,…,v_N-1] , results in the predicted state trajectory of the affine form Z(u,v)=S0+Suu+Svv.Z(u,v)=S_0+S_uu+S_vv. Figure 1: Convergence under exact and inexact best responses. (a) exact best response gives linear convergence from multiple initializations; (b) inexact best response yields convergence to an ε -dependent neighborhood. Player 1 selects u∈X1u _1 to minimize J1(u,v)=qu2‖u‖22 J_1(u,v)= q_u2\|u\|_2^2 +12Z(u,v)⊤QZ(u,v) + 12Z(u,v) QZ(u,v) −rpullCx⊤Z(u,v)+γu⊤v, -r_pull\,C_x Z(u,v)+γ\,u v, where Q=blkdiag(qpos,qvel,…,qpos,qvel)⪰0Q=blkdiag(q_pos,q_vel,…,q_pos,q_vel) 0 penalizes predicted states, and CxC_x selects position components so that Cx⊤Z(u,v)=∑t=1NptC_x Z(u,v)= _t=1^Np_t. The feasible set of Player 1 is the box X1:=u∈ℝN∣umin≤ut≤umax,t=0,…,N−1.X_1:=\u ^N u_ ≤ u_t≤ u_ ,\;t=0,…,N-1\. Player 2 is modeled through a stagewise best-response map BR2(u)=vmaxtanh(κ(vbar+creactu)),BR_2(u)=v_ \! (κ\,(v_bar+c_react\,u) ), which captures a saturating reaction. Consistent with the asymmetric-information formulation of Problem 1, Player 2 is specified here only through its reaction map BR2(⋅)BR_2(·); an explicit objective model J2J_2 is not required for the example. Since |BR2(u)t|≤vmax|BR_2(u)_t|≤ v_ , we take X2:=v∈ℝN∣‖v‖∞≤vmax.X_2:=\v ^N \|v\|_∞≤ v_ \. The constants (μ,L1,L12,L2)(μ,L_1,L_12,L_2) are computed analytically from the quadratic cost and the slope bounds of the reaction map using eigenvalue and spectral-norm bounds; in particular, μ and L1L_1 come from the Hessian with respect to u. We use N=5N=5, |u|≤3|u|≤ 3, (Δt,m,b)=(0.2,1.0,0.6)( t,m,b)=(0.2,1.0,0.6), (qu,qpos,qvel)=(0.35,0.32,0.01)(q_u,q_pos,q_vel)=(0.35,0.32,0.01), (rpull,γ)=(5.4,0.01)(r_pull,γ)=(5.4,0.01), and (vmax,κ,vbar,creact)=(1.8,0.6,0.9,0.9)(v_ ,κ,v_bar,c_react)=(1.8,0.6,0.9,0.9). These yield μ=0.3502,L1=0.3725,L12=0.0125,L2=0.9720,μ=0.3502,\,L_1=0.3725,\,L_12=0.0125,\,L_2=0.9720, so μ>L12L2μ>L_12L_2 holds and the Nash equilibrium is unique by Theorem 2. The corresponding stepsize limit is αmax=4.57 _ =4.57. We first consider the exact iteration (8) with α=0.5αmaxα=0.5\, _ , which gives ρ(α)=0.48<1ρ(α)=0.48<1. Fig. 1(a) shows ‖uk−u⋆‖2\|u^k-u \|_2 and ‖vk−v⋆‖2\|v^k-v \|_2 from multiple random initializations, together with the theoretical decay references from Theorem 3. A reference equilibrium (u⋆,v⋆)(u ,v ) is computed by iterating the exact map to a tight tolerance. The observed trajectories exhibit the predicted linear convergence, while the late-stage flattening is due to numerical tolerance. To model limited access to BR2(⋅)BR_2(·), we approximate the scalar map b(u)=vmaxtanh(κ(vbar+creactu))b(u)=v_ \! (κ(v_bar+c_reactu) ) by its first-order Taylor expansion about u=0u=0, b^(u)=vmaxtanh(κvbar)+[vmax(κcreact)sech2(κvbar)]u, b(u)=v_ (κ v_bar)+ [v_ (κ c_react)\,sech^2(κ v_bar) ]\,u, and define BR^2(u) BR_2(u) by applying b^(⋅) b(·) elementwise. Letting εstage≜supu∈U|b^(u)−b(u)| _stage _u | b(u)-b(u)|, the induced uniform ℓ2 _2 approximation error satisfies ‖BR^2(u)−BR2(u)‖2≤ε≜Nεstage,∀u∈X1.\| BR_2(u)-BR_2(u)\|_2≤ N\, _stage, ∀ u _1. We then run the inexact iteration (16) with the same stepsize. Fig. 1(b) shows that the iterates no longer converge to the exact Nash equilibrium, but instead enter and remain in a neighborhood, in agreement with Theorem 4. For the present parameters, the asymptotic bounds are lim supk→∞‖uk−u⋆‖2≤0.1641,lim supk→∞‖vk−v⋆‖2≤3.16. _k→∞\|u^k-u \|_2≤ 0.1641, _k→∞\|v^k-v \|_2≤ 3.16. The bound on vkv^k is conservative because (19) contains the additive approximation term ε directly. Finally, to validate the predicted O(ε)O( ) scaling, we sweep the uniform error level ε by injecting a constant additive perturbation d∈ℝNd ^N into the best-response oracle, i.e., BR^2(u)=BR2(u)+d BR_2(u)=BR_2(u)+d with ‖d‖2=ε\|d\|_2= , and estimate Δu(ε)≜lim supk→∞‖uk−u⋆‖2, _u( ) _k→∞\|u^k-u \|_2, using a tail-limsup over the final iterations. Fig. 2 shows that the measured steady-state deviation scales approximately linearly with ε and remains below the theoretical envelopes Ru(ε)=αL121−ρ(α)ε,Rv(ε)=L2Ru(ε)+ε.R_u( )= α L_121-ρ(α)\, , R_v( )=L_2R_u( )+ . The corresponding Player 2 deviation exhibits the same linear scaling up to the additive approximation term. Figure 2: O(ε)O( ) scaling of the steady-state deviation. VII Conclusion This paper studied a class of constrained two-player games under asymmetric information, where Player 1 knows its own objective and constraints while Player 2 is represented only through a best-response map. We established existence of a Nash equilibrium, derived a sufficient uniqueness condition, and proposed a projected gradient descent–best response iteration with global linear convergence to the unique equilibrium when the best-response map is exact. For the practically relevant inexact case, we showed that a uniformly bounded best-response approximation error yields an explicit O(ε)O( ) neighborhood bound around the true Nash equilibrium. Numerical results corroborated the predicted exact-case convergence and inexact robustness behavior. Overall, the paper shows that equilibrium seeking can remain both analyzable and robust even without an explicit opponent model. Several directions remain for future work. One is to extend the framework beyond decoupled feasible sets to games with coupled constraints, which arise naturally in shared-resource and safety-critical multi-agent settings. Another is to relax the sufficient condition μ>L12L2μ>L_12L_2, which can be restrictive in strongly coupled interactions. Acknowledgment The authors used a generative AI tool for language editing and grammar refinement only. All technical content, analysis, and conclusions were verified and finalized by the authors. References [1] S. Allen, J. P. Dickerson, and S. A. Gabriel (2022) Using inverse optimization to learn cost functions in generalized nash games. Computers & Operations Research 142, p. 105721. External Links: Document Cited by: §I. [2] B. Bateman, M. Xin, H. E. Tseng, and M. Liu (2024) Nash or stackelberg? – a comparative study for game-theoretic autonomous vehicle decision-making. IFAC-PapersOnLine 58 (28), p. 504–509. External Links: Document Cited by: §I. [3] F. Chen and W. Ren (2019) On the control of multi-agent systems: a survey. Foundations and Trends in Systems and Control 6 (4), p. 339–499. External Links: Document Cited by: §I. [4] F. Facchinei and J.-S. Pang (2003) Finite-dimensional variational inequalities and complementarity problems. Springer Series in Operations Research and Financial Engineering, Springer, New York, NY. Cited by: §I. [5] M. C. Ferris and T. S. Munson (2000) Complementarity problems in GAMS and the PATH solver. Journal of Economic Dynamics and Control 24 (2), p. 165–188. External Links: Document Cited by: §I. [6] P. T. Harker and J.-S. Pang (1990) Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical Programming 48, p. 161–220. External Links: Document Cited by: §I. [7] K. Ji, M. Orsag, and K. Han (2021) Lane-merging strategy for a self-driving car in dense traffic using the stackelberg game approach. Electronics 10 (8), p. 894. External Links: Document Cited by: §I, §I. [8] S. Le Cleac’h, M. Schwager, and Z. Manchester (2020-07) ALGAMES: a fast solver for constrained dynamic games. In Proceedings of Robotics: Science and Systems, Corvallis, Oregon, USA. External Links: Document Cited by: §I, §I. [9] J. Lei, U. V. Shanbhag, J.-S. Pang, and S. Sen (2020) On synchronous, asynchronous, and randomized best-response schemes for stochastic nash games. Mathematics of Operations Research 45 (1), p. 157–190. External Links: Document Cited by: §I. [10] X. Liu, L. Peters, and J. Alonso-Mora (2023) Learning to play trajectory games against opponents with unknown objectives. IEEE Robotics and Automation Letters 8 (7), p. 4139–4146. External Links: Document Cited by: §I, §I. [11] M. Rabbani, N. Mojahed, and S. Nazari (2026) A data driven structural decomposition of dynamic games via best response maps. Note: arXiv preprint arXiv:2602.05324 [cs.GT] Cited by: §I. [12] J. B. Rosen (1965) Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33 (3), p. 520–534. External Links: Document Cited by: §I, §I. [13] S. Y. Soltanian and W. Zhang (2025) PACE: a framework for learning and control in linear incomplete-information differential games. In Proceedings of the 7th Annual Learning for Dynamics & Control Conference, p. 1419–1433. Cited by: §I. [14] A. Turnwald, D. Althoff, D. Wollherr, and M. Buss (2016) Understanding human avoidance behavior: interaction-aware decision making based on game theory. International Journal of Social Robotics 8 (2), p. 331–351. External Links: Document Cited by: §I. [15] M. Wang, Z. Wang, J. Talbot, J. C. Gerdes, and M. Schwager (2019-06) Game theoretic planning for self-driving cars in competitive scenarios. In Proceedings of Robotics: Science and Systems, Freiburg im Breisgau, Germany. External Links: Document Cited by: §I, §I. [16] G. Williams, B. Goldfain, P. Drews, J. M. Rehg, and E. A. Theodorou (2018) Best response model predictive control for agile interactions between autonomous ground vehicles. In 2018 IEEE International Conference on Robotics and Automation (ICRA), p. 2403–2410. External Links: Document Cited by: §I. [17] X.-M. Zhang, Q.-L. Han, X. Ge, D. Ding, L. Ding, D. Yue, and C. Peng (2020) Networked control systems: a survey of trends and techniques. IEEE/CAA Journal of Automatica Sinica 7 (1), p. 1–17. External Links: Document Cited by: §I. [18] E. L. Zhu and F. Borrelli (2024) A sequential quadratic programming approach to the solution of open-loop generalized nash equilibria for autonomous racing. Note: arXiv preprint arXiv:2404.00186 [cs.RO] Cited by: §I.