Optimal Selection and Control in Monotone and Dynamic Games

Recent engineering developments have surrounded us with intelligent devices, which are required to autonomously take rational decisions while interacting with the physical world. These systems are increasingly widespread, interacting and interconnected, thus resulting in decision problems that involve multiple rational agents, generally with conflicting objectives and interrelated operating constraints. Currently relevant examples include autonomous driving, traffic routing, clearance of autonomous bidding markets, power consumption and production scheduling on the electricity grid, control of robotic swarms, and autonomous racing. The mathematical framework for formulating these problems is known as a game. Over the past decade, there has been significant progress in the development of algorithms that determine an action which is simultaneously rational (i.e. optimal) for each agent, namely, a generalized Nash equilibrium (GNE). This solution is particularly favorable as it is self-enforcing, in the sense that no decision maker can improve its payoff by unilaterally deviating from it. However, currently available algorithms for the computation of a GNE present numerous shortcomings, which limit their applicability to real-world non-cooperative decision processes and that we address in this thesis.

First of all, GNE problems typically admit multiple solutions, but currently available algorithms only compute an arbitrary, initialization-dependent GNE. In applications where a predictable and well-defined solution is necessary, it becomes important to select a specific GNE (among potentially infinitely many) that optimizes an arbitrary metric or a secondary, cooperative objective. We develop the first optimal GNE selection algorithms. We compare two different algorithm design methods, both developed under the framework of operator theory: the first, i.e. the hybrid steepest descent method (HSDM), entails a gradient descent of the selection function with vanishing step size combined with a GNE seeking algorithm, while the second requires the solution of a sequence of Variational Inequalities (VIs) with a vanishing regularizing term. Both design methods lead to algorithms that are suitable to distributing the computation between a central node and the agents, and we include ad-hoc algorithms for the particular cases of aggregative and cocoercive games.

Secondly, we consider time-varying games, motivated by the need for algorithms that continuously monitor and control physical multiagent systems. In such games, the agents must track an evolving solution with limited computation time between the problem's updates. This scenario is particularly relevant when the agents are affected by disturbances whose time-scale is comparable to the algorithm convergence rate. The challenge lies in finding algorithms that exhibit fast convergence and a robustness property to external disturbances, both typically associated with a linear convergence rate. We derive and study the asymptotic tracking error of a fully-distributed algorithm (i.e., without a central coordinator) for GNE problems with linear equality constraints. For a time-varying GNE selection problem, we find the HSDM with constant stepsize to be linearly convergent to an approximate solution. We find that the approximation error can be controller by an appropriate choice of the stepsize and number of iterations per time step, and we derive a bound to the asymptotic tracking error.

Finally, again driven by the need of applying GNE seeking algorithms to the control of physical systems, we consider dynamic games, where the decision each agent has to take is a time sequence of inputs to a dynamical system. In this case, the coupling between the agents emerges not only through the objectives and constraints, but also through the system dynamics. Ideally, one should compute the GNE solution by predicting the dynamics over an indefinitely long horizon. This is typically computationally intractable, especially when constraints are present. We then approximate the infinite-horizon control sequence by recomputing at each time instant the solutions to a finite-time equilibrium problem, a method typically known as receding-horizon control (or model predictive control, in the single-agent case). We derive a novel characterization of the infinite horizon objective achieved by the Nash equilibrium trajectory, and we show that one can recover the infinite-horizon performance by including this expression in the agents' objectives as an additive terminal cost. With this result, we conclude asymptotic stability of the steady state under a receding-horizon game-theoretic control action. Compared to the literature, we do not assume stability of the uncontrolled plant, nor we introduce auxiliary constraints. Furthermore, we find that the asymptotic stability of the steady state can be obtained with a more generic terminal cost if the game is potential, as we demonstrate on a practical traffic routing application.