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:
- Model Dependency: Many require explicit mathematical forms of cost functions.
- Information Constraints: Players may only observe their own costs without knowing others' actions.
- 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.
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$).
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