Fixed-Time Nash Equilibrium Seeking in Non-Cooperative Games

Jorge I. Poveda, Miroslav Krstić, Tamer Başar

Abstract

We introduce a novel class of Nash equilibrium seeking dynamics for non-cooperative games with a finite number of players, where the convergence to the Nash equilibrium is bounded by a KL function with a settling time that can be upper bounded by a positive constant that is independent of the initial conditions of the players, and which can be prescribed a priori by the system designer. The dynamics are model-free, in the sense that the mathematical forms of the cost functions of the players are unknown. Instead, in order to update its own action, each player needs to have access only to real-time evaluations of its own cost, as well as to auxiliary states of neighboring players characterized by a communication graph. Stability and convergence properties are established for both potential games and strongly monotone games. Numerical examples are presented to illustrate our theoretical results.

Introduction

In non-cooperative games—ranging from power grid management to social networks—players aim to minimize their individual costs. The optimal steady state, where no player can improve their situation by changing their strategy unilaterally, is the Nash Equilibrium (NE).

Existing algorithms for finding the NE often struggle with three primary challenges:

  1. Model Dependency: Many require explicit mathematical forms of cost functions.
  2. Information Constraints: Players may only observe their own costs without knowing others' actions.
  3. Convergence Speed: Traditional methods typically offer asymptotic or exponential convergence, where the time to reach equilibrium depends on the starting state. In time-critical engineering, a guaranteed settling time ($T^*$) independent of initial conditions is highly desirable.

Methodology: Fixed-Time Nash Equilibrium Seeking (FxTNES)

The proposed FxTNES algorithm enables distributed agents to reach an optimal state by a user-prescribed deadline without prior knowledge of their cost functions. It integrates several key control theory concepts:

  • Extremum Seeking (ES): A model-free technique using small dither signals (oscillations) to probe unknown functions and estimate gradients.
  • Fixed-Time Stability: Unlike standard stability, fixed-time dynamics use non-Lipschitz terms to ensure the system settles within a bounded interval chosen by the designer.
  • Singular Perturbation & Averaging: Averaging theory for non-smooth systems ensures that the average behavior of players reliably converges despite fast dither oscillations.
  • Distributed Consensus: Players communicate over a graph to account for cost coupling with neighbors' actions.

Key Results and Insights

The FxTNES algorithm was evaluated through synthetic numerical simulations of a three-player non-cooperative game with quadratic cost functions, benchmarked against traditional gradient-based NES dynamics.

Comparison of FxTNES (solid) and traditional NES (dashed) dynamics. FxTNES converges to the Nash Equilibrium before the prescribed time $T^*_S$, regardless of initial conditions.

Prescribed Performance and Robustness

A defining feature of FxTNES is that the settling time is upper-bounded by a constant. As shown in the simulation results, while traditional NES algorithms take variable amounts of time to settle based on starting points, FxTNES consistently reaches the equilibrium before the prescribed time $T^*_S$. This allows designers to set convergence speed as a design requirement by adjusting gains ($k$).

Evolution of player actions $u_i(t)$ showing the dither signals. FxTNES (black) exhibits significantly faster convergence and tighter transient envelopes compared to traditional NES (colored).

Furthermore, FxTNES improves transient performance. As illustrated above, it prevents the large overshoots often seen in traditional extremum seeking when initial conditions are large. The algorithm achieves "practical" stability, converging to a small neighborhood around the NE due to the persistent dither signals required for gradient estimation.

Conclusion and Future Work

FxTNES provides a robust, model-free framework for reaching Nash Equilibria within a guaranteed timeframe. While the current work assumes an undirected, connected communication graph, future research will explore dynamic games with moving equilibria and more complex, time-varying communication topologies.

Summary updated

Abstract

We introduce a novel class of Nash equilibrium seeking dynamics for non-cooperative games with a finite number of players, where the convergence to the Nash equilibrium is bounded by a KL function with a settling time that can be upper bounded by a positive constant that is independent of the initial conditions of the players, and which can be prescribed a priori by the system designer. The dynamics are model-free, in the sense that the mathematical forms of the cost functions of the players are unknown. Instead, in order to update its own action, each player needs to have access only to real-time evaluations of its own cost, as well as to auxiliary states of neighboring players characterized by a communication graph. Stability and convergence properties are established for both potential games and strongly monotone games. Numerical examples are presented to illustrate our theoretical results.
BibTeX
@inproceedings{poveda2020fixed,
  author = {Jorge I. Poveda and Miroslav Krstić and Tamer Başar},
  title = {{Fixed-Time Nash Equilibrium Seeking in Non-Cooperative Games}},
  booktitle = {CDC},
  year = {2020},
  doi = {10.1109/cdc42340.2020.9304146},
}
Figure