Distributed Algorithms for Aggregative Games on Graphs

• 成果类型: Article
• 署名作者: Koshal, Jayash; Nedic, Angelia; Shanbhag, Uday V.
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1501
• 发表日期: 2016
• 页码: 680-704
• 关键词: monotone nash games; osnr optimization; CONVERGENCE; consensus; networks; agents

摘要

We consider a class of Nash games, termed as aggregative games, being played over a networked system. In an aggregative game, a player's objective is a function of the aggregate of all the players' decisions. Every player maintains an estimate of this aggregate, and the players exchange this information with their local neighbors over a connected network. We study distributed synchronous and asynchronous algorithms for information exchange and equilibrium computation over such a network. Under standard conditions, we establish the almost-sure convergence of the obtained sequences to the equilibrium point. We also consider extensions of our schemes to aggregative games where the players' objectives are coupled through a more general form of aggregate function. Finally, we present numerical results that demonstrate the performance of the proposed schemes.