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

1. Problem Formulation

The paper addresses the challenge of finding Nash Equilibria (NE) in asymmetric-information, two-player constrained games.

• Context: In many multi-agent systems (e.g., robotics, autonomous driving), agents interact but do not have full knowledge of each other's internal optimization problems (objectives and constraints).
• The Setup:
  • Player 1: Has full knowledge of its own objective function $J_1(x_1, x_2)$ and feasible set $X_1$.
  • Player 2: Is not modeled by an explicit objective function $J_2$ or constraints known to Player 1. Instead, Player 2 is represented solely by a Best-Response (BR) map, $BR_2(x_1)$, which maps Player 1's action to Player 2's optimal reaction.
  • Feasibility: The feasible sets $X_1$ and $X_2$ are decoupled (no shared constraints), meaning interaction occurs only through the cost functions and the reaction behavior.
• Goal: Player 1 seeks a strategy $x_1$ such that $(x_1, BR_2(x_1))$ constitutes a Nash Equilibrium, without needing to know $J_2$.

2. Methodology

The authors propose an iterative algorithm and provide rigorous theoretical analysis regarding existence, uniqueness, and convergence.

A. Algorithm: Asymmetric Projected Gradient Descent–Best Response

The core algorithm is a fixed-point iteration where Player 1 updates its strategy based on the gradient of its cost and the current reaction of Player 2:

1. Reaction Step: Player 2 reacts to Player 1's current state $x_1^k$ via the map: $x_2^k = BR_2(x_1^k)$.
2. Update Step: Player 1 performs a projected gradient descent step:
   $$x_1^{k+1} = \Pi_{X_1} \left( x_1^k - \alpha \nabla_{x_1} J_1(x_1^k, x_2^k) \right)$$
   where $\Pi_{X_1}$ is the Euclidean projection onto the convex set $X_1$, and $\alpha$ is the step size.

B. Theoretical Framework

The analysis relies on several regularity assumptions:

• Existence: Requires convex, compact feasible sets and continuity/convexity of $J_1$. The authors use Kakutani's Fixed-Point Theorem to prove the existence of at least one NE.
• Uniqueness & Convergence: Requires stronger conditions:
  • $J_1$ is $\mu$-strongly convex in $x_1$.
  • The gradient $\nabla_{x_1} J_1$ is Lipschitz continuous with respect to $x_2$ (constant $L_{12}$).
  • The BR map $BR_2$ is single-valued and Lipschitz continuous (constant $L_2$).
  • Key Condition: $\mu > L_{12}L_2$. This condition ensures that the "self-stabilizing" strength of Player 1's objective outweighs the coupling effects of Player 2's reaction.

3. Key Contributions

1. New Game Class Definition: Formalized a class of games where one player is modeled purely as a black-box best-response map, moving away from the standard assumption that all agents' objectives are known.
2. Existence and Uniqueness Proofs: Established conditions under which a unique Nash Equilibrium exists for this asymmetric setup.
3. Global Linear Convergence: Proved that the proposed projected gradient-BR iteration converges globally and linearly to the unique NE when the BR map is exact. The convergence rate depends on the step size and the condition number derived from $\mu, L_{12},$ and $L_2$.
4. Robustness to Inexact Models: Analyzed the scenario where the BR map is an approximation (e.g., learned from data) with a uniform error bound $\epsilon$.
   • Result: The algorithm does not diverge; instead, the iterates converge to an explicit $O(\epsilon)$ neighborhood of the true Nash Equilibrium.
   • This provides a theoretical guarantee for using learned or estimated reaction models in control and decision-making.

4. Results

• Theoretical Bounds:
  • Exact Case: The error $\|x_1^k - x_1^*\|$ decays as $\rho(\alpha)^k$, where $\rho(\alpha) \in (0,1)$.
  • Inexact Case: The steady-state error is bounded by $\frac{\alpha L_{12}}{1-\rho(\alpha)}\epsilon$ for Player 1 and scales similarly for Player 2.
• Numerical Validation:
  • A "tug-of-war" cart simulation was used.
  • Exact BR: The algorithm demonstrated linear convergence from multiple random initializations, matching theoretical decay rates.
  • Inexact BR: When the BR map was approximated (via Taylor expansion) or perturbed with noise, the iterates converged to a stable neighborhood around the true NE.
  • Scaling: The size of the steady-state error was shown to scale linearly with the approximation error $\epsilon$, confirming the $O(\epsilon)$ theoretical prediction.

5. Significance

• Practical Applicability: This work bridges the gap between theoretical game theory and real-world applications where opponent models are unknown or must be learned. It validates the use of "black-box" reaction models in multi-agent control.
• Robustness: It provides a safety guarantee: even if the model of the other agent is imperfect (which is common in learning-based approaches), the system will not fail catastrophically but will settle near the optimal equilibrium.
• Framework for Learning: The results support the integration of data-driven opponent modeling (e.g., inverse reinforcement learning) into equilibrium-seeking algorithms, ensuring that the resulting control policies remain stable and convergent.
• Future Directions: The authors note that extending this to coupled constraints (shared resources) and relaxing the strong convexity condition are promising avenues for future research.

In summary, the paper transforms the best-response map from a mere modeling abstraction into a provably convergent and robust framework for asymmetric multi-agent decision-making.