Derivative-free Equilibrium Seeking in Multi-Agent Systems

Abstract

Both societal and engineering systems are growing in complexity and interconnectivity, making it increasingly challenging, and sometimes impossible, to model their dynamics and behaviors. Moreover, individuals or entities within these systems, often referred to as agents, have their own objectives that may conflict with one another. Examples include various economic systems where agents compete for profit, wind farms where upwind turbines reduce the energy extraction of downwind turbines, unwanted perturbation minimization in extremum seeking control, and cooperative source-seeking robotic vehicles. Despite having access to only limited observable information, it is crucial to ensure that all participants are content with the outcomes of these interactions. In this thesis, we choose to examine these problems within the framework of games, where each agent has their own cost function and constraints, and all costs and constraints are interconnected. Since the notion of optimum in multi-agent problems is difficult to define, we often seek to find a Nash equilibrium, i.e., a set of decisions from which no agent has an incentive to deviate.

This thesis primarily explores the development of Nash equilibrium seeking algorithms for scenarios where agents' cost functions are unknown and can only be assessed through measurements of a dynamical system's output, referred to as the zeroth-order (derivative-free) information case. We specifically concentrate on scenarios where partial derivatives can be estimated from these measurements and subsequently integrated into a full-information algorithm. Existing approaches exhibit significant drawbacks, such as the inability to handle shared constraints, stringent assumptions on the cost functions, and applicability limited to agents with continuous dynamics.