1 Tracking-Based Distributed Equilibrium Seeking for Aggregative Games

2025-04-30 0 0 725.56KB 39 页 10玖币

侵权投诉

Tracking-Based Distributed Equilibrium Seeking

for Aggregative Games

Guido Carnevale, Filippo Fabiani, Filiberto Fele, Kostas Margellos, Giuseppe

Notarstefano

Abstract

We propose fully-distributed algorithms for Nash equilibrium seeking in aggregative games over

networks. We ﬁrst consider the case where local constraints are present and we design an algorithm

combining, for each agent, (i) the projected pseudo-gradient descent and (ii) a tracking mechanism

to locally reconstruct the aggregative variable. To handle coupling constraints arising in generalized

settings, we propose another distributed algorithm based on (i) a recently emerged augmented primal-dual

scheme and (ii) two tracking mechanisms to reconstruct, for each agent, both the aggregative variable

and the coupling constraint satisfaction. Leveraging tools from singular perturbations analysis, we

prove linear convergence to the Nash equilibrium for both schemes. Finally, we run extensive numerical

simulations to conﬁrm the effectiveness of our methods and compare them with state-of-the-art distributed

equilibrium-seeking algorithms.

I. INTRODUCTION

Recent years have seen an increasing attention to the computation of (generalized) Nash

equilibria in games over networks [1]–[3]. Indeed, numerous applications falling within different

This result is part of the project “Distributed Optimization for Cooperative Machine Learning in Complex Networks” (No

PGR10067) that has received funding from the Ministero degli Affari Esteri e della Cooperazione Internazionale. F. Fele gratefully

acknowledges support from grant RYC2021-033960-I funded by MCIN/AEI/ 10.13039/501100011033 and European Union

NextGenerationEU/PRTR, as well as from grant PID2022-142946NA-I00 funded by MCIN/AEI/ 10.13039/501100011033 and by

ERDF A way of making Europe.

G. Carnevale and G. Notarstefano are with the Department of Electrical, Electronic and Information Engineering, Alma Mater

Studiorum - Universita‘ di Bologna, Bologna, Italy (

name.lastname@unibo.it

) F. Fabiani is with the IMT School for

Advanced Studies Lucca, Piazza San Francesco 19, 55100 Lucca, Italy (

filippo.fabiani@imtlucca.it

). F. Fele is with

the Department of Systems Engineering and Automation, University of Seville, Spain (

ffele@us.es

). K. Margellos is with

the Department of Engineering Science, University of Oxford, UK (kostas.margellos@eng.ox.ac.uk).

February 13, 2024 DRAFT

arXiv:2210.14547v3 [eess.SY] 12 Feb 2024

domains such as smart grids management [4], [5], economic market analysis [6], cooperative

control of robots [7], electric vehicles charging [8]–[10], network congestion control [11], and

synchronization of coupled oscillators in power grids [12] can be modeled as networks of selﬁsh

agents – aiming at optimizing their strategy according to an associated individual cost function –

that compete with each other over shared resources.

Among these examples, one can often ﬁnd instances modeled as an aggregative game, where

the strategies of all the agents in the network are coupled through the so-called aggregative

variable (expressing, e.g., the mean strategy), upon which each agent’s cost function depends;

see, e.g., [13]–[15] for a comprehensive overview. Our work investigates such a framework

proposing novel distributed algorithms for generalized Nash equilibrium (GNE) seeking under

partial information, i.e., assuming that each agent is only aware of its own local information (e.g.,

its strategy set and cost function) and can communicate only with few agents in the network.

This restriction naturally calls for the design of fully-distributed mechanisms for GNE seeking.

Our approach is motivated by recent developments in cooperative optimization, where agents

in a network collaborate to minimize the sum of individual objective functions depending both

on local decision variables and an aggregative variable [16]–[20].

A. Related work

In the context of NE problems in aggregative form, ﬁrst attempts to design equilibrium

seeking algorithms involve semi-decentralized approaches in which a central entity gathers and

shares global quantities (such as the aggregative variable and/or a dual multiplier) with all the

agents [21]–[28].

To relax the communication requirements, [29] proposes a gradient-based algorithm for

non-generalized games with diminishing step-size that relies on dynamic averaging consensus

(see, e.g., [30], [31]) to reconstruct the aggregative variable in each agent. Such a method

has been reﬁned in [32] to deal with privacy issues and, as a consequence, only guarantees

approximate equilibrium computations. In [33], the distributed computation of an approximate

Nash equilibrium is guaranteed through a best-response-based algorithm requiring multiple

communication exchanges per iteration. In [34], instead, an asynchronous distributed algorithm

based on proximal dynamics is proposed.

Looking at GNE problems where the agents’ strategies are coupled also by means of constraints,

in [35] the distributed computation of an approximate NE is guaranteed through an algorithm

February 13, 2024 DRAFT

requiring, however, several communication exchanges per iteration. Exact convergence is instead

guaranteed in [36], where a distributed algorithm with diminishing step-size is proposed, combining

dynamic tracking mechanisms, monotone operator splitting, and the Krasnosel’skii-Mann ﬁxed-

point iteration. An exactly convergent distributed equilibrium-seeking algorithm with constant

step-size is given in [37], where the authors propose a distributed method based on a forward-

backward splitting of two preconditioned operators requiring a double communication exchange

per iteration. Finally, distributed equilibrium-seeking algorithms based on proximal best-responses

are proposed in [38].

B. Contributions

The main contribution of the paper is the design and the analysis of novel, fully distributed

iterative – i.e., discrete-time – algorithms for (generalized) NE seeking in aggregative games

over networks. First, to address the case where local constraints are present, we combine a

projected pseudo-gradient method with a local, auxiliary variable that compensates for the lack

of knowledge of the aggregative variable in each agent. Successively, we deal with the case of

coupling constraints, however, no local constraints are present. To achieve this, we take inspiration

from a recent augmented primal-dual scheme for centralized, continuous-time optimization [39]

and resort to (i) an averaging step to enforce consensus among the agents’ multipliers and (ii) two

auxiliary variables to locally reconstruct both the aggregative variable and the coupling constraint

status. Both iterative schemes are analyzed from a system-theoretic perspective that allows us to

establish linear convergence to the (G)NE. To the best of our knowledge, the algorithm proposed

for the case where coupling constraints are present is the ﬁrst distributed scheme in the literature

with guaranteed linear convergence to a GNE (see Appendix A for the formal deﬁnition). As such,

it constitutes the main contribution of our paper. Moreover, as discussed in detail in Section

II-B

such a linear convergence rate is enabled by our system-theoretic interpretation, which offers

a new proof-line perspective. Further, we also guarantee linear convergence when only local

constraints are present. A similar result is also achieved by the recent contribution [38] (see [38,

Rem. 12]): our algorithm complements the proximal best-response scheme of [38] by constituting

its gradient-based counterpart. Proximal algorithms require solving some optimization program

(which in turn may rely on some iterative method), whereas our projected gradient descent step

can allow a simpler update rule if the projection can be performed in an easy manner. As such,

gradient-based approaches are often computationally less intensive compared to proximal ones,

February 13, 2024 DRAFT

as veriﬁed in the numerical simulations of Section V (see Table III); however, such a conclusion

is case-dependent.

As a side technical contribution, in contrast with existing methods, our algorithms (i) do not

require compactness of the local feasible sets and (ii) allow for a general form of the aggregative

variable, thus not necessarily requiring the mean of the agents’ strategies to operate. To better

classify our work within the existing literature, Tables I and II compare it with the most relevant

works. Speciﬁcally, Table I considers the framework without coupling constraints, while Table II

the one with coupling constraints (GNE) (note that some of the technical conditions and variables

appearing in the table entries will become clear in the sequel).

The analysis of our iterative algorithms is carried out by relying on a singular perturbations

approach that allows us to see each procedure as the interconnection between a slow subsystem

and a fast one. Speciﬁcally, the slow dynamics are produced by the update of the strategies

and, in the case with coupling constraints, of the mean of the multipliers over the network. The

fast dynamics, instead, describes the evolution of the auxiliary variables used to compensate for

the lack of knowledge of the global quantities and, in the case with coupling constraints, the

consensus error among the agents’ multipliers. Based on this interpretation, we construct two

auxiliary, simpliﬁed subsystems, known as boundary layer and reduced system, to separately

study the fast and slow dynamics, respectively. Leveraging this connection, we ﬁrst provide

the convergence properties of these auxiliary dynamics with Lyapunov-based arguments, and

then we merge the obtained results to establish linear convergence to the (G)NE of the whole

interconnection. This last step relies on a general theorem (cf. Theorem II.5) considering a class

of singularly perturbed systems that includes the proposed iterative algorithms. In detail, this

theorem shows that global exponential stability results for the interconnection can be achieved,

while typical results in literature only provide semi-global properties (see [40, Prop. 8.1], or

[41, Ch. 11] for the continuous-time case). To the best of our knowledge, similar results are

not yet available in the literature: besides the construction of a novel, fully distributed iterative

mechanism with appealing features for their practical implementation, they offer a new proof

line for equilibrium-seeking problems.

Finally, we provide detailed numerical simulations to conﬁrm the effectiveness of our methods

and compare them with state-of-the-art distributed NE-seeking algorithms.

February 13, 2024 DRAFT

[29] [33] [32] [38] Our algorithm

Linear rate ✗ ✗ ✗ ✓ ✓

Step-size Diminishing - Diminishing - Constant

Exactness ✓✗ ✗ ✓ ✓

Communications per iterate 1v1 1 1

Equilibrium assumptions Fstrictly monotone ∃!equilibrium,

xi,br(·)non-expansive

Fstrongly monotone Fstrongly monotone Fstrongly monotone

Local constraint set Compact and convex Compact and convex Unconstrained Closed and convex Closed and convex

Gradient unboundedness ✓ ✓ ✗✓ ✓

Aggregative variable 1

i=1

xi1

i=1

xi1

i=1

xi1

i=1

xi1

i=1

ϕi(xi)

Algorithmic structure Gradient-based Best-response-based Gradient-based Proximal-based Gradient-based

Graph Undirected,

time-varying

Directed Undirected,

time-varying

Undirected Directed

TABLE I: Setup without coupling constraints.

[35] [36] [37] [38] Our algorithm

Linear rate ✗ ✗ ✗ ✗ ✓

Step-size Constant Diminishing Constant - Constant

Exactness ✗✓ ✓ ✓ ✓

Communications per iterate v1 2 1 1

Equilibrium assumptions Fstrongly monotone Fcocoercive Fstrongly monotone Fstrongly monotone Fstrongly monotone

Local constraints Compact and convex Compact and convex Compact and convex Closed and convex Unconstrained

Coupling constraints Not speciﬁed SCQ SCQ SCQ κ1I≤AA⊤≤κ2I

Gradient unboundedness ✗✓ ✓ ✓ ✓

Aggregative variable 1

i=1

xi1

i=1

xi1

i=1

xi1

i=1

xi1

i=1

ϕi(xi)

Algorithmic structure Gradient-based Gradient-based Gradient-based Proximal-based Gradient-based

Graph Directed Undirected,

time-varying

Undirected Undirected Directed

TABLE II: Setup with coupling constraints, where SCQ stands for Slater’s Constraint Qualiﬁcation.

C. Paper organization

In Section II we introduce aggregative games over networks, while in Section

III-A

we propose

and analyze a novel distributed algorithm to ﬁnd NE when only local constraints are present. In

Section IV we devise a novel distributed GNE-seeking algorithm to address the case of linear

coupling constraints. Finally, in Section V we provide detailed numerical simulations to test our

methods. The proof of the result on singular perturbations – instrumental in the derivation of our

main theorems – is deferred to Appendix B; Appendices C – D gather the proofs of all other

technical results and lemmas.

Notation: A matrix

M∈Rn×n

is Schur if all its eigenvalues lie in the open unit disc. The

February 13, 2024 DRAFT

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1Tracking-BasedDistributedEquilibriumSeekingforAggregativeGamesGuidoCarnevale,FilippoFabiani,FilibertoFele,KostasMargellos,GiuseppeNotarstefanoAbstractWeproposefully-distributedalgorithmsforNashequilibriumseekinginaggregativegamesovernetworks.Wefirstconsiderthecasewherelocalconstraintsarepresentandw...

展开>> 收起<<

1 Tracking-Based Distributed Equilibrium Seeking for Aggregative Games.pdf

共39页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Tracking-Based Distributed Equilibrium Seeking for Aggregative Games

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: