We address the generalized Nash equilibrium seeking problem for a population of agents playing aggregative games with affine coupling constraints. We focus on semi-decentralized communication architectures, where there is a central coordinator able to gather and broadcast signals of aggregative nature to the agents. By exploiting the framework of monotone operator theory and operator splitting, we first critically review the most relevant available algorithms and then design two novel schemes: 1) a single-layer, fixed-step algorithm with convergence guarantee for general (noncocoercive, nonstrictly) monotone aggregative games and 2) a single-layer proximal-type algorithm for a class of monotone aggregative games with linearly coupled cost functions. We also design novel accelerated variants of the algorithms via (alternating) inertial and over-relaxation steps. Finally, we show via numerical simulations that the proposed algorithms outperform those in the literature in terms of convergence speed.

We address the generalized Nash equilibrium seeking problem in a partial-decision information scenario, where each agent can only exchange information with some neighbors, although its cost function possibly depends on the strategies of all agents. The few existing methods build on projected pseudo-gradient dynamics, and require either double-layer iterations or conservative conditions on the step sizes. To overcome both these flaws and improve efficiency, we design the first fully-distributed single-layer algorithms based on proximal best-response. Our schemes are fixed-step and allow for inexact updates, which is crucial for reducing the computational complexity. Under standard assumptions on the game primitives, we establish convergence to a variational equilibrium (with linear rate for games without coupling constraints) by recasting our algorithms as proximal-point methods, opportunely preconditioned to distribute the computation among the agents. Since our analysis hinges on a restricted monotonicity property, we also provide new general results that significantly extend the domain of applicability of proximal-point methods. Besides, our operator-theoretic approach favors the implementation of provably correct acceleration schemes that can further improve the convergence speed. Finally, the potential of our algorithms is demonstrated numerically, revealing much faster convergence with respect to projected pseudo-gradient methods and validating our theoretical findings.

In future distribution grids, prosumers (i.e., energy consumers with storage and/or production capabilities) will trade energy with each other and with the main grid. To ensure an efficient and safe operation of energy trading, in this paper, we formulate a peer-to-peer energy market of prosumers as a generalized aggregative game, in which a network operator is responsible to enforce the operational constraints of the system. We design a distributed market-clearing mechanism with convergence guarantee to an economically-efficient, strategically-stable, and operationally-safe configuration (i.e., a variational generalized Nash equilibrium). Numerical studies on the IEEE 37-bus testcase show the scalability of the proposed approach and suggest that active participation in the market is beneficial for both prosumers and the network operator.

We design the first fully distributed algorithm for generalized Nash equilibrium seeking in aggregative games on a time-varying communication network, under partial-decision information, i.e., the agents have no direct access to the aggregate decision. The algorithm is derived by integrating dynamic tracking into a projected pseudo-gradient algorithm. The convergence analysis relies on the framework of monotone operator splitting and the Krasnosel'skii-Mann fixed-point iteration with errors.

In this article, we study proximal type dynamics in the context of multiagent network games. We analyze several conjugations of this class of games, providing convergence results. Specifically, we look into synchronous/asynchronous dynamics with time-invariant communication network and synchronous dynamics with time-varying communication networks. Finally, we validate the theoretical results via numerical simulations on opinion dynamics.

In this paper, we present three distributed algorithms to solve a class of Generalized Nash Equilibrium (GNE) seeking problems in strongly monotone games. The first one (SD-GENO) is based on synchronous updates of the agents, while the second and the third (AD-GEED and AD-GENO) represent asynchronous solutions that are robust to communication delays. AD-GENO can be seen as a refinement of AD-GEED, since it only requires node auxiliary variables, enhancing the scalability of the algorithm. Our main contribution is to prove convergence to a v-GNE variational-GNE (vGNE) of the game via an operator-theoretic approach. Finally, we apply the algorithms to network Cournot games and show how different activation sequences and delays affect convergence. We also compare the proposed algorithms to a state-of-the-art algorithm solving a similar problem, and observe that AD-GENO outperforms it.

State convergence is essential in many scientific areas, e.g. multi-agent consensus/disagreement, distributed optimization, computational game theory, multi-agent learning over networks. In this paper, we study for the first time the state convergence problem in uncertain linear systems. Preliminarily, we characterize state convergence in linear systems via equivalent linear matrix inequalities. In the presence of uncertainty, we complement the canonical definition of (weak) convergence with a stronger notion of convergence, which requires the existence of a common kernel among the generator matrices of the difference/differential inclusion (strong convergence). We investigate under which conditions the two definitions are equivalent. Then, we characterize strong and weak convergence via Lyapunov arguments, (linear) matrix inequalities and separability of the eigenvalues of the generator matrices. Finally, we show that, unlike asymptotic stability, state convergence lacks of duality.

In this paper, we study multi-agent network games subject to affine time-varying coupling constraints and a time-varying communication network. We focus on the class of games adopting proximal dynamics and study their convergence to a persistent equilibrium. The assumptions considered to solve the problem are discussed and motivated. We develop an iterative equilibrium seeking algorithm, using only local information, that converges to a special class of game equilibria. Its derivation is motivated by several examples, showing that the original game dynamics fail to converge. Finally, we apply the designed algorithm to solve a constrained consensus problem, illustrating the theoretical results.

We address the Nash equilibrium problem in a partial-decision information scenario, where each agent can only observe the actions of some neighbors, while its cost possibly depends on the strategies of other agents. Our main contribution is the design of a fully-distributed, single-layer, fixed-step algorithm, based on a proximal best-response augmented with consensus terms. To derive our algorithm, we follow an operator-theoretic approach. First, we recast the Nash equilibrium problem as that of finding a zero of a monotone operator. Then, we demonstrate that the resulting inclusion can be solved in a fully-distributed way via a proximal-point method, thanks to the use of a novel preconditioning matrix. Under strong monotonicity and Lipschitz continuity of the game mapping, we prove linear convergence of our algorithm to a Nash equilibrium. Furthermore, we show that our method outperforms the fastest known gradient-based schemes, both in terms of guaranteed convergence rate, via theoretical analysis, and in practice, via numerical simulations.

We consider the economic dispatch problem for a day-ahead, peer-to-peer (P2P) electricity market of prosumers (i.e., energy consumers who can also produce electricity) in a distribution network. In our model, each prosumer has the capability of producing power through its dispatchable or non-dispatchable generation units and/or has a storage energy unit. Furthermore, we consider a hybrid main grid & P2P market in which each prosumer can trade power both with the main grid and with (some of) the other prosumers. First, we cast the economic dispatch problem as a noncooperative game with coupling constraints. Then, we design a fully-scalable algorithm to steer the system to a generalized Nash equilibrium (GNE). Finally, we show through numerical studies that the proposed methodology has the potential to ensure safe and efficient operation of the power grid.

We address the demand-side management (DSM) problem for smart grids where the users have energy generation and storage capabilities, and where the energy price depends on the renewable energy sources and on the aggregate electricity demand. Each user aims at reducing its economic cost by selecting the best energy schedule subject to its local preferences and global restrictions on the aggregate net demand. From a game-theoretic perspective, we model the problem as a generalized Nash equilibrium problem. We propose a shrinking-horizon semi-decentralized DSM algorithm that exploits the most recent forecast on the renewable energy sources to perform real-time adjustments on the energy usage of the users. We investigate the potential of the proposed approach via numerical simulations on realistic scenarios, where we observe improved social welfare compared to day-ahead DSM algorithms.

We address the generalized Nash equilibrium seeking problem for a population of noncooperative agents playing potential games with linear coupling constraints over a communication network. We consider a class of generalized potential games where the coupling in the cost functions of the agents is linear, i.e., J{i}(x{i}, x{-i}): =f{i}(x{i})+ ell{i}(x{-i}){ top}x{i} where ell{i} is linear. By exploiting this special structure, we design a distributed algorithm with convergence guarantee under mild assumptions, i.e., (non-strict) monotonicity of the pseudo-subdifferential mapping. The potential of the proposed algorithm is shown via numerical simulations on a networked Nash Cournot game, where we observe faster convergence with respect to standard projected pseudo-gradient algorithms.

We design a distributed algorithm for generalized Nash equilibrium seeking in aggregative games with linear coupling constraints under partial-decision information, i.e., the agents have no direct access to the aggregate decision. The algorithm is derived by including dynamic tracking together with a standard projected pseudo-gradient algorithm in a fully-distributed fashion. The convergence analysis of the algorithm relies on the framework of monotone operator splitting and Krasnosel'skii-Mann fixed-point iteration with errors.

In this paper, we propose an asynchronous distributed algorithm for the computation of generalized Nash equilibria in noncooperative games, where the players interact via an undirected communication graph. Specifically, we extend the paper 'Asynchronous distributed algorithm for seeking generalized Nash equilibria' by Yi and Pavel: we redesign the asynchronous update rule using auxiliary variables over the nodes rather than over the edges. This key modification renders the algorithm scalable for highly interconnected games. The derived asynchronous algorithm is robust against delays in the communication and it eliminates the idle times between computations, hence modeling a more realistic interaction between players with different update frequencies. We address the problem from an operator-theoretic perspective and design the algorithm via a preconditioned forward-backward splitting. Finally, we numerically simulate the algorithm for the Cournot competition in networked markets.

We address the generalized aggregative equilibrium seeking problem for noncooperative agents playing average aggregative games with affine coupling constraints. First, we use operator theory to characterize the generalized aggregative equilibria of the game as the zeros of a monotone set-valued operator. Then, we massage the Douglas-Rachford splitting to solve the monotone inclusion problem and derive a single layer, semi-decentralized algorithm whose global convergence is guaranteed under mild assumptions. The potential of the proposed Douglas-Rachford algorithm is shown on a simplified resource allocation game, where we observe faster convergence with respect to forward-backward algorithms.