Inertia-Corrected Newton Method For Generalized Nash Equilibria in Dynamic Games with Optimality Verification
Authors: Zhiyuan Zhang, Panagiotis Tsiotras
Organizations: School of Aerospace Engineering, Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA
Newton methods efficiently find Generalized Nash Equilibria (GNE) in dynamic games by solving for the KKT necessary conditions. These methods are fast and can support multi-agent Model Predictive Control (MPC) for highly dynamic robots. However, a small KKT residual alone does not certify that the returned solution satisfies the second-order sufficient conditions for a local GNE. In this paper, we propose an efficient numerical method to verify the second-order sufficient conditions (SOSC) for a local GNE. We connect the inertia of the agent KKT matrix with the positive definiteness of the reduced Hessian of the cost function, projected onto the null space of the constraints. Furthermore, we introduce an inertia-corrected update step that improves convergence to local GNEs by destabilizing strict saddle points with weak cross-agent coupling. Our main contribution is a fast Newton solver for Constrained Dynamic Games that provides efficient optimality checking. Through numerical benchmarks, we demonstrate the proposed solver's runtime and convergence performance in practical multi-agent planning problems. We also validate the solver's real-time capabilities in physical experiments using a platform of miniature autonomous race cars.
Figures & tables
Fig. 1 : Time-lapse of a solution to the 8-car merging game. Agents successfully negotiate the merge while maintaining safety distances.
Fig. 2 : Snapshots of the 6-car intersection game.
Fig. 3 : Single-start optimality rate in the merging game with and without inertia correction. The proposed correction significantly increases the fraction of KKT-converged solutions that satisfy the per-agent SOSC.
Fig. 4 : Average KKT residual versus solver iteration for selected merging games. Solid lines use the proposed near-minimal binary-search correction. Dashed lines use the geometric baseline that increases the regularization by a factor of ten. The near-minimal correction generally shortens the transient stagnation period.
Fig. 5 : Computation time versus number of agents for the highway merging game. Both variants of the proposed solver are significantly faster than ALGAMES and iLQGames.
Fig. 6 : Computation time versus number of agents for the intersection game. Inertia correction adds negligible runtime overhead, and both variants of the proposed solver are significantly faster than ALGAMES and iLQGames.
Fig. 7 : Single-start optimality rate (SOSC-certified solutions divided by KKT-converged solutions) in the intersection game.
Fig. 8 : Snapshots of an overtake during the experiment.
Constrained general-sum dynamic games are a popular formulation for highly interactive multi-agent planning problems. In recent years, Generalized Nash Equilibrium (GNE) solvers have achieved real-time performance for small dynamic games. However, solution speed still remains a bottleneck, and controlling even a small number of agents (e.g., more than four) in a dynamic task remains elusive. In addition, Newton solvers that focus on the first-order conditions are vulnerable to non-Nash saddle points, limiting the usefulness of the provided solution. In this work, we propose a fast and versatile interior point solver for constrained dynamic games, along with a computationally efficient second-order correction that increases the probability of converging to a local GNE solution in constrained dynamic games. The performance of the proposed method is evaluated on numerical benchmarks and a physical experiment involving scaled race cars.
Zhiyuan Zhang, Panagiotis Tsiotras
School of Aerospace Engineering, Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA
Generalized Nash Equilibrium Problems (GNEPs) often arise in multi-agent engineering applications that require distributed algorithms. Unlike traditional approaches that enforce consensus on multipliers, our method removes the need to share multipliers, reducing communication and improving privacy. As a result, different initializations can lead to different GNEs, including non-variational ones. We establish convergence under sufficient conditions using an input-to-state stability (ISS) framework.
This paper studies feedback Nash equilibrium (FBNE) seeking for multi-agent trajectory planning in nonlinear dynamical systems with unknown agents' objectives and state-dependent inter-agent coupling. While dynamic game theory provides a principled framework for such problems, existing approaches typically assume fully rational agents with known objectives or rely on fixed regularization, limiting their ability to capture bounded rationality and spatially varying interaction intensity in safety-critical settings. To this end, we propose a KL-regularized dynamic game with a state-dependent weight that adaptively balances optimality and behavioral priors. To infer unknown cost parameters from demonstrated behaviors, we develop a context-aware inverse game module based on maximum-entropy inverse reinforcement learning with physics-informed regularization, ensuring structural consistency with the forward game. We establish per-iteration well-posedness of the regularized local game and show that the adaptive weighting function remains Lipschitz continuous under bounded nominal-trajectory updates. Numerical simulations and multi-robot experiments on cooperative navigation and merging scenarios validate the effectiveness of the proposed framework.
Tianle Liu, Youcheng Niu, Jing Zeng +2
College of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China