Proof.Theper-playith actioninhindsight pro lea is xed: '(a)= X However, see, thisratewouldbeveryslow, andtheconvergencemetric, notverystrong, e.g., inexpectediterates. Given >0, consider Moreauenvelop' (a) .

Pseudo-games are a natural and well-known generalization of normal-form games, in which the actions taken by each player affect not only the other players' payoffs, as in games, but also the other players' strategy sets. The solution concept par excellence for pseudo-games is the generalized Nash equilibrium (GNE), i.e., a strategy profile at which each player's strategy is feasible and no player can improve their payoffs by unilaterally deviating to another strategy in the strategy set determined by the other players' strategies. The computation of GNE in pseudo-games has long been a problem of interest, due to applications in a wide variety of fields, from environmental protection to logistics to telecommunications. Although computing GNE is PPAD-hard in general, it is still of interest to try to compute them in restricted classes of pseudo-games. One approach is to search for a strategy profile that minimizes exploitability, i.e., the sum of the regrets across all players. As exploitability is nondifferentiable in general, developing efficient first-order methods that minimize it might not seem possible at first glance. We observe, however, that the exploitability-minimization problem can be recast as a min-max optimization problem, and thereby obtain polynomial-time first-order methods to compute a refinement of GNE, namely the variational equilibria (VE), in convex-concave cumulative regret pseudo-games with jointly convex constraints. More generally, we also show that our methods find the stationary points of the exploitability in polynomial time in Lipschitz-smooth pseudo-games with jointly convex constraints. Finally, we demonstrate in experiments that our methods not only outperform known algorithms, but that even in pseudo-games where they are not guaranteed to converge to a GNE, they may do so nonetheless, with proper initialization.

We address safe multi-robot interaction under uncertainty. In particular, we formulate a chance-constrained linear quadratic Gaussian game with coupling constraints and system uncertainties. We find a tractable reformulation of the game and propose a dual ascent algorithm. We prove that the algorithm converges to a generalized Nash equilibrium of the reformulated game, ensuring the satisfaction of the chance constraints. We test our method in driving simulations and real-world robot experiments. Our method ensures safety under uncertainty and generates less conservative trajectories than single-agent model predictive control.

In this paper, we reveal the intrinsic duality between graph neural networks (GNNs) and evolutionary algorithms (EAs), bridging two traditionally distinct fields. Building on this insight, we propose Graph Neural Evolution (GNE), a novel evolutionary algorithm that models individuals as nodes in a graph and leverages designed frequency-domain filters to balance global exploration and local exploitation. Through the use of these filters, GNE aggregates high-frequency (diversity-enhancing) and low-frequency (stability-promoting) information, transforming EAs into interpretable and tunable mechanisms in the frequency domain. Extensive experiments on benchmark functions demonstrate that GNE consistently outperforms state-of-the-art algorithms such as GA, DE, CMA-ES, SDAES, and RL-SHADE, excelling in complex landscapes, optimal solution shifts, and noisy environments. Its robustness, adaptability, and superior convergence highlight its practical and theoretical value. Beyond optimization, GNE establishes a conceptual and mathematical foundation linking EAs and GNNs, offering new perspectives for both fields. Its framework encourages the development of task-adaptive filters and hybrid approaches for EAs, while its insights can inspire advances in GNNs, such as improved global information propagation and mitigation of oversmoothing. GNE's versatility extends to solving challenges in machine learning, including hyperparameter tuning and neural architecture search, as well as real-world applications in engineering and operations research. By uniting the dynamics of EAs with the structural insights of GNNs, this work provides a foundation for interdisciplinary innovation, paving the way for scalable and interpretable solutions to complex optimization problems.

We propose a novel method for fast and accurate training of physics-informed neural networks (PINNs) to find solutions to boundary value problems (BVPs) and initial boundary value problems (IBVPs). By combining the methods of training deep neural networks (DNNs) and Extreme Learning Machines (ELMs), we develop a model which has the expressivity of DNNs with the fine-tuning ability of ELMs. We showcase the superiority of our proposed method by solving several BVPs and IBVPs which include linear and non-linear ordinary differential equations (ODEs), partial differential equations (PDEs) and coupled PDEs. The examples we consider include a stiff coupled ODE system where traditional numerical methods fail, a 3+1D non-linear PDE, Kovasznay flow and Taylor-Green vortex solutions to incompressible Navier-Stokes equations and pure advection solution of 1+1 D compressible Euler equation. The Theory of Functional Connections (TFC) is used to exactly impose initial and boundary conditions (IBCs) of (I)BVPs on PINNs. We propose a modification to the TFC framework named Reduced TFC and show a significant improvement in the training and inference time of PINNs compared to IBCs imposed using TFC. Furthermore, Reduced TFC is shown to be able to generalize to more complex boundary geometries which is not possible with TFC. We also introduce a method of applying boundary conditions at infinity for BVPs and numerically solve the pure advection in 1+1 D Euler equations using these boundary conditions.

Dynamic games can be an effective approach for modeling interactive behavior between multiple competitive agents in autonomous racing and they provide a theoretical framework for simultaneous prediction and control in such scenarios. In this work, we propose DG-SQP, a numerical method for the solution of local generalized Nash equilibria (GNE) for open-loop general-sum dynamic games for agents with nonlinear dynamics and constraints. In particular, we formulate a sequential quadratic programming (SQP) approach which requires only the solution of a single convex quadratic program at each iteration. The three key elements of the method are a non-monotonic line search for solving the associated KKT equations, a merit function to handle zero sum costs, and a decaying regularization scheme for SQP step selection. We show that our method achieves linear convergence in the neighborhood of local GNE and demonstrate the effectiveness of the approach in the context of head-to-head car racing, where we show significant improvement in solver success rate when comparing against the state-of-the-art PATH solver for dynamic games. An implementation of our solver can be found at https://github.com/zhu-edward/DGSQP.

This paper considers a class of noncooperative games in which the feasible decision sets of all players are coupled together by a coupled inequality constraint. Adopting the variational inequality formulation of the game, we first introduce a new local edge-based equilibrium condition and develop a distributed primal-dual proximal algorithm with full information. Considering challenges when communication delays occur, we devise an asynchronous distributed algorithm to seek a generalized Nash equilibrium. This asynchronous scheme arbitrarily activates one player to start new computations independently at different iteration instants, which means that the picked player can use the involved out-dated information from itself and its neighbors to perform new updates. A distinctive attribute is that the proposed algorithms enable the derivation of new distributed forward-backward-like extensions. In theoretical aspect, we provide explicit conditions on algorithm parameters, for instance, the step-sizes to establish a sublinear convergence rate for the proposed synchronous algorithm. Moreover, the asynchronous algorithm guarantees almost sure convergence in expectation under the same step-size conditions and some standard assumptions. An interesting observation is that our analysis approach improves the convergence rate of prior synchronous distributed forward-backward-based algorithms. Finally, the viability and performance of the proposed algorithms are demonstrated by numerical studies on the networked Cournot competition.

Given a large graph with few node labels, how can we (a) identify whether there is generalized network-effects (GNE) of the graph or not, (b) estimate GNE to explain the interrelations among node classes, and (c) exploit GNE to improve downstream tasks such as predicting the unknown labels accurately and efficiently? The knowledge of GNE is valuable for various tasks like node classification and targeted advertising. However, identifying and understanding GNE such as homophily, heterophily or their combination is challenging in real-world graphs due to limited availability of node labels and noisy edges. We propose NetEffect, a graph mining approach to address the above issues, enjoying the following properties: (i) Principled: a statistical test to determine the presence of GNE in a graph with few node labels; (ii) General and Explainable: a closed-form solution to estimate the specific type of GNE observed; and (iii) Accurate and Scalable: the integration of GNE for accurate and fast node classification. Applied on public, real-world graphs, NetEffect discovers the unexpected absence of GNE in numerous graphs, which previously thought to exhibit heterophily. Further, we show that incorporating GNE is effective on node classification. On a large real-world graph with 1.6M nodes and 22.3M edges, NetEffect achieves over 7 times speedup (14 minutes vs. 2 hours) compared to most competitors.

We study generalized games with full row rank equality constraints and we provide a strikingly simple proof of strong monotonicity of the associated KKT operator. This allows us to show linear convergence to a variational equilibrium of the resulting primal-dual pseudo-gradient dynamics. Then, we propose a fully-distributed algorithm with linear convergence guarantee for aggregative games under partial-decision information. Based on these results, we establish stability properties for online GNE seeking in games with time-varying cost functions and constraints. Finally, we illustrate our findings numerically on an economic dispatch problem for peer-to-peer energy markets.